source: trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/SymbolMap.java @ 1257

//   Copyright 2012 Georg-August-Universität Göttingen, Germany
//
//   Licensed under the Apache License, Version 2.0 (the "License");
//   you may not use this file except in compliance with the License.
//   You may obtain a copy of the License at
//
//       http://www.apache.org/licenses/LICENSE-2.0
//
//   Unless required by applicable law or agreed to in writing, software
//   distributed under the License is distributed on an "AS IS" BASIS,
//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//   See the License for the specific language governing permissions and
//   limitations under the License.

package de.ugoe.cs.autoquest.usageprofiles;

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.
 * </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.
 * </p>
 * 
 * @see SymbolComparator
 * 
 * @author Patrick Harms
 */
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();
        }
    }

    /**
     * <p>
     * Returns the size of the map, i.e. the number of symbol entries
     * </p>
     * 
     * @return as described
     */
    public int size() {
        return symbolList.size();
    }

    /**
     * <p>
     * Returns true if this map is empty, i.e. if {@link #size()} returns 0
     * </p>
     * 
     * @return as described
     */
    public boolean isEmpty() {
        return symbolList.isEmpty();
    }

    /**
     * <p>
     * Returns true if the provided symbol was stored in this map.
     * </p>
     * 
     * @param symbol the symbol to check if it was stored in this map
     * 
     * @return as described
     * 
     * @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;
    }

    /**
     * <p>
     * Returns the value associated to the provided symbol in this map. If there is no value
     * associated to the given symbol or if the symbol is not stored in this map, the method
     * returns null.
     * </p>
     * 
     * @param symbol the symbol to return the value for
     * 
     * @return as described
     * 
     * @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;
        }
    }

    /**
     * <p>
     * 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
     * implementations. To prevent this, the {@link #containsSymbol(Object)} and
     * {@link #removeSymbol(Object)} methods should be used to ensure map behavior.
     * </p>
     * 
     * @param symbol the symbol to add to the map
     * @param value  the value to associate to the symbol in this map
     * 
     * @return as described
     * 
     * @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);
            }
        }
    }

    /**
     * <p>
     * Removes a symbol and its associated value from the map. If the symbol is stored several
     * times, the first of its occurrences is removed. 
     * </p>
     * 
     * @param symbol the symbol to be removed from the map
     * 
     * @return as described
     * 
     * @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;
    }

    /**
     * <p>
     * Returns a collection of all symbols in this map.
     * </p>
     *
     * @return as described
     */
    public Collection<K> getSymbols() {
        return new ReadOnlyCollectionFacade<K>(symbolList, new SymbolFacade());
    }
    
    /**
     * <p>
     * Returns a collection of all values associated to symbols in this map. May contain null
     * values, if some of the symbols are mapped to null. The length of the returned collection
     * is in any case the same as the size of the map.
     * </p>
     *
     * @return as described
     */
    public Collection<V> getValues() {
        return new ReadOnlyCollectionFacade<V>(symbolList, new ValueFacade());
    }
    
    /**
     * <p>
     * Removes all symbols and associated values from the map.
     * </p>
     */
    public void clear() {
        symbolList.clear();
        symbolBuckets = null;
    }

    /* (non-Javadoc)
     * @see java.lang.Object#hashCode()
     */
    @Override
    public int hashCode() {
        return symbolList.size();
    }

    /* (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();
        }
    }

}