Index: trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/SymbolMap.java
===================================================================
--- trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/SymbolMap.java	(revision 1257)
+++ trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/SymbolMap.java	(revision 1282)
@@ -16,124 +16,33 @@
 
 import java.io.Serializable;
-import java.util.ArrayList;
-import java.util.Arrays;
 import java.util.Collection;
-import java.util.HashMap;
-import java.util.Iterator;
-import java.util.LinkedList;
-import java.util.List;
-import java.util.Map;
-import java.util.Map.Entry;
 
 /**
  * <p>
- * This class is a data structure for holding symbols which is more efficient than a simple list.
- * This data structure can be used with a comparator to adapt the effective list behavior and to
- * define the equals strategy for comparing objects. After a certain size ({@link #MAX_LIST_SIZE}),
- * the symbol map creates a symbol index consisting of buckets. This allows searching for symbols
- * in a more efficient order as the search can start in the most appropriate of the internal
- * buckets.
+ * This interface defines a data structure for holding symbols. Its implementations can be used to
+ * improve the performance of a trie by tuning its internal symbol storage management.
  * </p>
  * <p>
- * The class is called a map, although it is not. It may contain the same element as separate keys.
- * This implementation is done for performance improvements. If it is required to really assure,
- * that a key exists only once, then each call to the {@link #addSymbol(Object, Object)} method
- * should be done only, if the {@link #containsSymbol(Object)} method for the same symbol returns
- * false.
+ * The interface is called a map, although it is not necessarily. It may contain the same element
+ * as separate keys. This is allowed for performance improvements. If it is required to really
+ * assure, that a key exists only once, then each call to the {@link #addSymbol(Object, Object)}
+ * method should be done only, if the {@link #containsSymbol(Object)} method for the same symbol
+ * returns false.
+ * </p>
+ * <p>
+ * Mapping a symbol to the value null is possible. In this case {@link #getValue(Object)} returns
+ * null for the symbol. But {@link #containsSymbol(Object)} returns true.
  * </p>
  * 
- * @see SymbolComparator
+ * @author Patrick Harms
  * 
- * @author Patrick Harms
+ * @param <T>
+ *            Type of the symbols that are stored
+ * @param <V>
+ *            Type of the values associated with the symbols
+ *            
+ * @see SymbolStrategy
  */
-public class SymbolMap<K, V> implements Serializable {
-
-    /**
-     * <p>
-     * default serial version UID
-     * </p>
-     */
-    private static final long serialVersionUID = 1L;
-
-    /**
-     * <p>
-     * the maximum number of symbols in this map which is still only treated as list instead of
-     * using buckets.
-     * </p>
-     */
-    private static final int MAX_LIST_SIZE = 15;
-    
-    /**
-     * <p>
-     * Comparator to be used for comparing the symbols with each other and to determine a bucket
-     * search order
-     * </p>
-     */
-    private SymbolComparator<K> comparator;
-
-    /**
-     * <p>
-     * Internally maintained plain list of symbols and associated values
-     * </p>
-     */
-    private List<Map.Entry<K, V>> symbolList;
-
-    /**
-     * <p>
-     * If the size of the map exceeds {@link #MAX_LIST_SIZE}, this is the symbol index using buckets
-     * for optimizing the search order.
-     * </p>
-     */
-    private Map<Integer, List<Map.Entry<K, V>>> symbolBuckets;
-    
-    /**
-     * <p>
-     * When using buckets, not any symbol may be associated a correct bucket by the used
-     * comparator. Therefore, we set a default bucket for all such symbols. This may change
-     * if the comparator defines the same bucket for a specific symbol.
-     * </p>
-     */
-    private int defaultBucket = 0;
-    
-    /**
-     * <p>
-     * Instantiates a symbol map with a comparator
-     * </p>
-     *
-     * @param comparator the comparator to use for comparing symbols and for determining bucket
-     *                   search orders
-     * 
-     * @throws IllegalArgumentException if the provided comparator is null
-     */
-    public SymbolMap(SymbolComparator<K> comparator) {
-        if (comparator == null) {
-            throw new IllegalArgumentException("comparator must not be null");
-        }
-        
-        this.comparator = comparator;
-        this.symbolList = new ArrayList<Map.Entry<K, V>>();
-    }
-
-    /**
-     * <p>
-     * Copy constructure
-     * </p>
-     * 
-     * @param otherMap the other map to be copied including its comparator
-     * 
-     * @throws IllegalArgumentException if the provided other map is null
-     */
-    public SymbolMap(SymbolMap<K, V> otherMap) {
-        if (otherMap == null) {
-            throw new IllegalArgumentException("otherMap must not be null");
-        }
-
-        this.comparator = otherMap.comparator;
-        this.symbolList = new ArrayList<Map.Entry<K, V>>(otherMap.symbolList);
-        
-        if (this.symbolList.size() > MAX_LIST_SIZE) {
-            createSymbolBuckets();
-        }
-    }
+public interface SymbolMap<K, V> extends Serializable {
 
     /**
@@ -144,7 +53,5 @@
      * @return as described
      */
-    public int size() {
-        return symbolList.size();
-    }
+    public int size();
 
     /**
@@ -155,7 +62,5 @@
      * @return as described
      */
-    public boolean isEmpty() {
-        return symbolList.isEmpty();
-    }
+    public boolean isEmpty();
 
     /**
@@ -170,11 +75,5 @@
      * @throws IllegalArgumentException if the provided symbol is null
      */
-    public boolean containsSymbol(K symbol) {
-        if (symbol == null) {
-            throw new IllegalArgumentException("symbol must not be null");
-        }
-        
-        return getEntry(symbol) != null;
-    }
+    public boolean containsSymbol(K symbol);
 
     /**
@@ -191,18 +90,5 @@
      * @throws IllegalArgumentException if the provided symbol is null
      */
-    public V getValue(K symbol) {
-        if (symbol == null) {
-            throw new IllegalArgumentException("symbol must not be null");
-        }
-        
-        Map.Entry<K, V> entry = getEntry(symbol);
-        
-        if (entry != null) {
-            return entry.getValue();
-        }
-        else {
-            return null;
-        }
-    }
+    public V getValue(K symbol);
 
     /**
@@ -210,5 +96,5 @@
      * Adds a symbol and an associated value to the map. If the value is null, the symbol is added,
      * anyway and {@link #containsSymbol(Object)} will return true for that symbol. Adding the
-     * same symbol twice will produce two entries. This is contradictory to typical map
+     * same symbol twice may produce two entries. This is contradictory to typical map
      * implementations. To prevent this, the {@link #containsSymbol(Object)} and
      * {@link #removeSymbol(Object)} methods should be used to ensure map behavior.
@@ -222,22 +108,5 @@
      * @throws IllegalArgumentException if the provided symbol is null
      */
-    public void addSymbol(K symbol, V value) {
-        if (symbol == null) {
-            throw new IllegalArgumentException("symbol must not be null");
-        }
-        
-        Map.Entry<K, V> entry = new SymbolMapEntry(symbol, value);
-        
-        symbolList.add(entry);
-            
-        if (symbolList.size() > MAX_LIST_SIZE) {
-            if (symbolBuckets == null) {
-                createSymbolBuckets();
-            }
-            else {
-                addToSymbolBucket(entry);
-            }
-        }
-    }
+    public void addSymbol(K symbol, V value);
 
     /**
@@ -253,24 +122,5 @@
      * @throws IllegalArgumentException if the provided symbol is null
      */
-    public V removeSymbol(K symbol) {
-        if (symbol == null) {
-            throw new IllegalArgumentException("symbol must not be null");
-        }
-        
-        for (int i = 0; i < symbolList.size(); i++) {
-            if (comparator.equals(symbolList.get(i).getKey(), symbol)) {
-                // found the symbol. Remove it from the list, and if required, also from the map.
-                V value = symbolList.remove(i).getValue();
-                
-                if (symbolList.size() > MAX_LIST_SIZE) {
-                    removeFromSymbolBuckets(symbol);
-                }
-                
-                return value;
-            }
-        }
-        
-        return null;
-    }
+    public V removeSymbol(K symbol);
 
     /**
@@ -281,7 +131,5 @@
      * @return as described
      */
-    public Collection<K> getSymbols() {
-        return new ReadOnlyCollectionFacade<K>(symbolList, new SymbolFacade());
-    }
+    public Collection<K> getSymbols();
     
     /**
@@ -294,7 +142,5 @@
      * @return as described
      */
-    public Collection<V> getValues() {
-        return new ReadOnlyCollectionFacade<V>(symbolList, new ValueFacade());
-    }
+    public Collection<V> getValues();
     
     /**
@@ -303,8 +149,5 @@
      * </p>
      */
-    public void clear() {
-        symbolList.clear();
-        symbolBuckets = null;
-    }
+    public void clear();
 
     /* (non-Javadoc)
@@ -312,564 +155,11 @@
      */
     @Override
-    public int hashCode() {
-        return symbolList.size();
-    }
+    public int hashCode();
 
     /* (non-Javadoc)
      * @see java.lang.Object#equals(java.lang.Object)
      */
-    @SuppressWarnings("unchecked")
     @Override
-    public boolean equals(Object obj) {
-        if (this == obj) {
-            return true;
-        }
-        else if (this.getClass().isInstance(obj)) {
-            SymbolMap<K, V> other = (SymbolMap<K, V>) obj;
-            
-            return (symbolList.size() == other.symbolList.size()) &&
-                   (symbolList.containsAll(other.symbolList));
-        }
-        else {
-            return false;
-        }
-    }
-
-    /**
-     * <p>
-     * Internally used to create symbol buckets in case the number of stored symbols increased
-     * above {@link #MAX_LIST_SIZE}.
-     * </p>
-     */
-    private void createSymbolBuckets() {
-        //System.out.println("creating symbol buckets");
-        symbolBuckets = new HashMap<Integer, List<Map.Entry<K, V>>>();
-        
-        for (Map.Entry<K, V> symbol : symbolList) {
-            addToSymbolBucket(symbol);
-        }
-    }
-
-    /**
-     * <p>
-     * Adds a symbol and its value to its corresponding bucket. The corresponding bucket is
-     * retrieved from the symbol comparator. It is the first element of the search order returned
-     * by the symbol comparator. If the comparator does not define a search order for the symbol
-     * the entry is added to the default bucket. If the comparator defines a bucket id
-     * identical to the default bucket id, the default bucket id is shifted to another value.
-     * </p>
-     */
-    private void addToSymbolBucket(Map.Entry<K, V> symbolEntry) {
-        int bucketId = defaultBucket;
-        int[] bucketSearchOrder = comparator.getBucketSearchOrder(symbolEntry.getKey());
-        
-        if ((bucketSearchOrder != null) && (bucketSearchOrder.length > 0)) {
-            bucketId = bucketSearchOrder[0];
-            
-            if (bucketId == defaultBucket) {
-                setNewDefaultBucketId();
-            }
-        }
-        
-        List<Map.Entry<K, V>> list = symbolBuckets.get(bucketId);
-        
-        if (list == null) {
-            list = new LinkedList<Map.Entry<K, V>>();
-            symbolBuckets.put(bucketId, list);
-        }
-        
-        list.add(symbolEntry);
-    }
-    
-    /**
-     * <p>
-     * Removes the entry for a given symbol from the buckets. It uses the bucket search order
-     * defined by the symbol comparator to find the symbol as fast as possible.
-     * </p>
-     */
-    private Map.Entry<K, V> removeFromSymbolBuckets(K symbol) {
-        int bucketId = defaultBucket;
-        int[] bucketSearchOrder = comparator.getBucketSearchOrder(symbol);
-        
-        if ((bucketSearchOrder != null) && (bucketSearchOrder.length > 0)) {
-            bucketId = bucketSearchOrder[0];
-        }
-        
-        List<Map.Entry<K, V>> list = symbolBuckets.get(bucketId);
-        Map.Entry<K, V> result = null;
-        
-        if (list != null) {
-            for (int i = 0; i < list.size(); i++) {
-                if (comparator.equals(list.get(i).getKey(), symbol)) {
-                    result = list.remove(i);
-                    break;
-                }
-            }
-            
-            if (list.isEmpty()) {
-                symbolBuckets.remove(bucketId);
-            }
-        }
-        
-        return result;
-    }
-
-    /**
-     * <p>
-     * Updates the default bucket id to a new one
-     * </p>
-     */
-    private void setNewDefaultBucketId() {
-        int oldDefaultBucket = defaultBucket;
-        do {
-            defaultBucket += 1;
-        }
-        while (symbolBuckets.containsKey(defaultBucket));
-        
-        symbolBuckets.put(defaultBucket, symbolBuckets.get(oldDefaultBucket));
-    }
-
-    /**
-     * <p>
-     * searches for the entry belonging to the given symbol. The method either uses the list if
-     * buckets are not used yet, or it uses the buckets and searches them in the order defined
-     * by the comparator. If the symbol isn't found and the comparator does not refer all buckets,
-     * then also the other buckets are searched for the symbol.
-     * </p>
-     */
-    private Map.Entry<K, V> getEntry(K symbol) {
-        Map.Entry<K, V> entry = null;
-        if (symbolBuckets == null) {
-            entry = lookup(symbol, symbolList);
-        }
-        else {
-            int[] bucketSearchOrder = comparator.getBucketSearchOrder(symbol);
-            for (int bucketId : bucketSearchOrder) {
-                List<Map.Entry<K, V>> list = symbolBuckets.get(bucketId);
-                if (list != null) {
-                    entry = lookup(symbol, list);
-                    if (entry != null) {
-                        break;
-                    }
-                }
-            }
-            
-            // try to search the other buckets
-            if (entry == null) {
-                Arrays.sort(bucketSearchOrder);
-                for (Map.Entry<Integer, List<Map.Entry<K, V>>> bucket : symbolBuckets.entrySet()) {
-                    if (Arrays.binarySearch(bucketSearchOrder, bucket.getKey()) < 0) {
-                        List<Map.Entry<K, V>> list = bucket.getValue();
-                        if (list != null) {
-                            entry = lookup(symbol, list);
-                            if (entry != null) {
-                                break;
-                            }
-                        }
-                    }
-                }
-            }
-        }
-        
-        return entry;
-    }
-
-    /**
-     * <p>
-     * Convenience method to look up a symbol in a list of entries using the comparator.
-     * </p>
-     */
-    private Map.Entry<K, V> lookup(K symbol, List<Map.Entry<K, V>> list) {
-        for (Map.Entry<K, V> candidate : list) {
-            if (comparator.equals(candidate.getKey(), symbol)) {
-                return candidate;
-            }
-        }
-        
-        return null;
-    }
-
-    /**
-     * <p>
-     * Internally used data structure for storing symbol value pairs
-     * </p>
-     * 
-     * @author Patrick Harms
-     */
-    private class SymbolMapEntry implements Map.Entry<K, V> {
-        
-        /**
-         * the symbol to map to a value
-         */
-        private K symbol;
-        
-        /**
-         * the value associated with the symbol
-         */
-        private V value;
-
-        /**
-         * <p>
-         * Simple constructor for initializing the entry with a symbol and its associated value.
-         * </p>
-         */
-        private SymbolMapEntry(K symbol, V value) {
-            super();
-            this.symbol = symbol;
-            this.value = value;
-        }
-
-        /* (non-Javadoc)
-         * @see java.util.Map.Entry#getKey()
-         */
-        @Override
-        public K getKey() {
-            return symbol;
-        }
-
-        /* (non-Javadoc)
-         * @see java.util.Map.Entry#getValue()
-         */
-        @Override
-        public V getValue() {
-            return value;
-        }
-
-        /* (non-Javadoc)
-         * @see java.util.Map.Entry#setValue(java.lang.Object)
-         */
-        @Override
-        public V setValue(V value) {
-            V oldValue = this.value;
-            this.value = value;
-            return oldValue;
-        }
-
-        /* (non-Javadoc)
-         * @see java.lang.Object#hashCode()
-         */
-        @Override
-        public int hashCode() {
-            return symbol.hashCode();
-        }
-
-        /* (non-Javadoc)
-         * @see java.lang.Object#equals(java.lang.Object)
-         */
-        @SuppressWarnings("unchecked")
-        @Override
-        public boolean equals(Object obj) {
-            if (this == obj) {
-                return true;
-            }
-            else if (this.getClass().isInstance(obj)) {
-                SymbolMapEntry other = (SymbolMapEntry) obj;
-                return (symbol.equals(other.symbol) &&
-                        (value == null ? other.value == null : value.equals(other.value)));
-            }
-            else {
-                return false;
-            }
-        }
-
-        /* (non-Javadoc)
-         * @see java.lang.Object#toString()
-         */
-        @Override
-        public String toString() {
-            return symbol + "=" + value;
-        }
-
-    }
-
-    /**
-     * <p>
-     * Used to create an efficient facade for accessing the internal list of entries either only
-     * for the symbols or only for the values. It is a default implementation of the collection
-     * interface. The entry facade provided to the constructor decides, if either the list
-     * accesses only the symbols or only the values. 
-     * </p>
-     * 
-     * @author Patrick Harms
-     */
-    private class ReadOnlyCollectionFacade<TYPE> implements Collection<TYPE> {
-        
-        /**
-         * the list facaded by this facade
-         */
-        private List<Map.Entry<K, V>> list;
-        
-        /**
-         * the facade to be used for the entries
-         */
-        private EntryFacade<TYPE> entryFacade;
-        
-        /**
-         * <p>
-         * Initializes the facade with the facaded list and the facade to be used for the entries
-         * </p>
-         */
-        private ReadOnlyCollectionFacade(List<Map.Entry<K, V>> list, EntryFacade<TYPE> entryFacade)
-        {
-            this.list = list;
-            this.entryFacade = entryFacade;
-        }
-
-        /* (non-Javadoc)
-         * @see java.util.Collection#size()
-         */
-        @Override
-        public int size() {
-            return list.size();
-        }
-
-        /* (non-Javadoc)
-         * @see java.util.Collection#isEmpty()
-         */
-        @Override
-        public boolean isEmpty() {
-            return list.isEmpty();
-        }
-
-        /* (non-Javadoc)
-         * @see java.util.Collection#contains(java.lang.Object)
-         */
-        @Override
-        public boolean contains(Object o) {
-            if (o == null) {
-                for (Map.Entry<K, V> entry : list) {
-                    if (entryFacade.getFacadedElement(entry) == null) {
-                        return true;
-                    }
-                }
-            }
-            else {
-                for (Map.Entry<K, V> entry : list) {
-                    if (o.equals(entryFacade.getFacadedElement(entry))) {
-                        return true;
-                    }
-                }
-            }
-            
-            return false;
-        }
-
-        /* (non-Javadoc)
-         * @see java.util.Collection#toArray()
-         */
-        @Override
-        public Object[] toArray() {
-            Object[] result = new Object[list.size()];
-            
-            for (int i = 0; i < list.size(); i++) {
-                result[i] = entryFacade.getFacadedElement(list.get(i));
-            }
-            
-            return result;
-        }
-
-        /* (non-Javadoc)
-         * @see java.util.Collection#toArray(T[])
-         */
-        @SuppressWarnings("unchecked")
-        @Override
-        public <T> T[] toArray(T[] a) {
-            T[] result = a;
-            
-            for (int i = 0; i < list.size(); i++) {
-                result[i] = (T) entryFacade.getFacadedElement(list.get(i));
-            }
-            
-            return result;
-        }
-
-        /* (non-Javadoc)
-         * @see java.util.Collection#add(java.lang.Object)
-         */
-        @Override
-        public boolean add(TYPE e) {
-            throw new UnsupportedOperationException("this collection is read only");
-        }
-
-        /* (non-Javadoc)
-         * @see java.util.Collection#remove(java.lang.Object)
-         */
-        @Override
-        public boolean remove(Object o) {
-            throw new UnsupportedOperationException("this collection is read only");
-        }
-
-        /* (non-Javadoc)
-         * @see java.util.Collection#containsAll(java.util.Collection)
-         */
-        @Override
-        public boolean containsAll(Collection<?> c) {
-            for (Object candidate : c) {
-                if (!contains(candidate)) {
-                    return false;
-                }
-            }
-            
-            return true;
-        }
-
-        /* (non-Javadoc)
-         * @see java.util.Collection#addAll(java.util.Collection)
-         */
-        @Override
-        public boolean addAll(Collection<? extends TYPE> c) {
-            throw new UnsupportedOperationException("this collection is read only");
-        }
-
-        /* (non-Javadoc)
-         * @see java.util.Collection#removeAll(java.util.Collection)
-         */
-        @Override
-        public boolean removeAll(Collection<?> c) {
-            throw new UnsupportedOperationException("this collection is read only");
-        }
-
-        /* (non-Javadoc)
-         * @see java.util.Collection#retainAll(java.util.Collection)
-         */
-        @Override
-        public boolean retainAll(Collection<?> c) {
-            throw new UnsupportedOperationException("this collection is read only");
-        }
-
-        /* (non-Javadoc)
-         * @see java.util.Collection#clear()
-         */
-        @Override
-        public void clear() {
-            throw new UnsupportedOperationException("this collection is read only");
-        }
-
-        /* (non-Javadoc)
-         * @see java.util.Collection#iterator()
-         */
-        @Override
-        public Iterator<TYPE> iterator() {
-            return new ReadOnlyCollectionIteratorFacade<TYPE>(list.iterator(), entryFacade);
-        }
-        
-    }
-
-    /**
-     * <p>
-     * Implementation of an iterator to facade an iterator on the internal list of symbol entries.
-     * </p>
-     * 
-     * @author Patrick Harms
-     */
-    private class ReadOnlyCollectionIteratorFacade<TYPE> implements Iterator<TYPE> {
-        
-        /**
-         * the facaded iterator
-         */
-        private Iterator<Map.Entry<K, V>> iterator;
-        
-        /**
-         * the facade for the entries provided by the facaded iterator
-         */
-        private EntryFacade<TYPE> entryFacade;
-        
-        /**
-         * <p>
-         * initialized this facade with the facaded iterator and the entry facade to be used for
-         * the entries.
-         * </p>
-         */
-        private ReadOnlyCollectionIteratorFacade(Iterator<Map.Entry<K, V>> iterator,
-                                                 EntryFacade<TYPE>         entryFacade)
-        {
-            this.iterator = iterator;
-            this.entryFacade = entryFacade;
-        }
-
-        /* (non-Javadoc)
-         * @see java.util.Iterator#hasNext()
-         */
-        @Override
-        public boolean hasNext() {
-            return iterator.hasNext();
-        }
-
-        /* (non-Javadoc)
-         * @see java.util.Iterator#next()
-         */
-        @Override
-        public TYPE next() {
-            return entryFacade.getFacadedElement(iterator.next());
-        }
-
-        /* (non-Javadoc)
-         * @see java.util.Iterator#remove()
-         */
-        @Override
-        public void remove() {
-            throw new UnsupportedOperationException("this iterator is read only");
-        }
-        
-    }
-        
-    /**
-     * <p>
-     * Used to facade symbol entries and to return only this part of an entry, that is relevant.
-     * </p>
-     * 
-     * @author Patrick Harms
-     */
-    private abstract class EntryFacade<T> {
-        
-        /**
-         * <p>
-         * Returns only the part of an entry that is relevant or required.
-         * </p>
-         *
-         * @param entry of which the part shall be returned
-         * 
-         * @return the part of the entry to be returned
-         */
-        protected abstract T getFacadedElement(Entry<K, V> entry);
-        
-    }
-    
-    /**
-     * <p>
-     * Implementation of the entry facade returning the entries key, i.e. the symbol.
-     * </p>
-     * 
-     * @author Patrick Harms
-     */
-    private class SymbolFacade extends EntryFacade<K> {
-
-        /* (non-Javadoc)
-         * @see ReadOnlyCollectionIteratorFacade#getFacadedElement(Entry)
-         */
-        @Override
-        protected K getFacadedElement(Entry<K, V> entry) {
-            return entry.getKey();
-        }
-    }
-    
-    /**
-     * <p>
-     * Implementation of the entry facade returning the entries value, i.e. the value associated to
-     * the symbol.
-     * </p>
-     * 
-     * @author Patrick Harms
-     */
-    private class ValueFacade extends EntryFacade<V> {
-
-        /* (non-Javadoc)
-         * @see ReadOnlyCollectionIteratorFacade#getFacadedElement(Entry)
-         */
-        @Override
-        protected V getFacadedElement(Entry<K, V> entry) {
-            return entry.getValue();
-        }
-    }
+    public boolean equals(Object obj);
 
 }
