source: trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TaskSymbolBucketedMap.java @ 2146

//   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.tasktrees.temporalrelation;

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;

import de.ugoe.cs.autoquest.eventcore.Event;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTask;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTaskInstance;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptional;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance;
import de.ugoe.cs.autoquest.usageprofiles.SymbolMap;

/**
 * <p>
 * This class is a data structure for holding task instances in form of a symbol map. It 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 task instances. After a
 * certain size ({@link #MAX_LIST_SIZE}), the map creates an index consisting of buckets of similar
 * task instances. This allows searching for task instances 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 task instances 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
 * @param <V>
 */
class TaskSymbolBucketedMap<V> implements SymbolMap<ITask, V>, Serializable {

    /**
     * <p>
     * default serial version UID
     * </p>
     */
    private static final long serialVersionUID = 1L;

    /**
     * <p>
     * the maximum number of task instances in this map which is still only treated as list
     * instead of using buckets.
     * </p>
     */
    private static final int MAX_LIST_SIZE = 15;
    
    /**
     * <p>
     * the id of the default event bucket
     * </p>
     */
    private static final int DEFAULT_EVENT_BUCKET_ID = 4;
    
    /**
     * <p>
     * the id of the default sequence bucket
     * </p>
     */
    private static final int DEFAULT_SEQUENCE_BUCKET_ID = 0;
    
    /**
     * <p>
     * the id of the default selection bucket
     * </p>
     */
    private static final int DEFAULT_SELECTION_BUCKET_ID = 1;
    
    /**
     * <p>
     * the id of the default iteration bucket
     * </p>
     */
    private static final int DEFAULT_ITERATION_BUCKET_ID = 2;
    
    /**
     * <p>
     * the id of the default optional bucket
     * </p>
     */
    private static final int DEFAULT_OPTIONAL_BUCKET_ID = 3;
    
    /**
     * <p>
     * the default bucket search order for events
     * </p>
     */
    private static final int[] DEFAULT_EVENT_BUCKET_SEARCH_ORDER = new int[]
        { DEFAULT_EVENT_BUCKET_ID, DEFAULT_ITERATION_BUCKET_ID, DEFAULT_OPTIONAL_BUCKET_ID,
          DEFAULT_SELECTION_BUCKET_ID };
    
    /**
     * <p>
     * the default bucket search order for sequences
     * </p>
     */
    private static final int[] DEFAULT_SEQUENCE_BUCKET_SEARCH_ORDER = new int[]
        { DEFAULT_SEQUENCE_BUCKET_ID, DEFAULT_ITERATION_BUCKET_ID, DEFAULT_OPTIONAL_BUCKET_ID,
          DEFAULT_SELECTION_BUCKET_ID };
    
    /**
     * <p>
     * the default bucket search order for selection
     * </p>
     */
    private static final int[] DEFAULT_SELECTION_BUCKET_SEARCH_ORDER = new int[]
        { DEFAULT_SELECTION_BUCKET_ID, DEFAULT_EVENT_BUCKET_ID, DEFAULT_ITERATION_BUCKET_ID,
          DEFAULT_OPTIONAL_BUCKET_ID, DEFAULT_SEQUENCE_BUCKET_ID };
    
    /**
     * <p>
     * the default bucket search order for iterations
     * </p>
     */
    private static final int[] DEFAULT_ITERATION_BUCKET_SEARCH_ORDER = new int[]
        { DEFAULT_ITERATION_BUCKET_ID, DEFAULT_OPTIONAL_BUCKET_ID, DEFAULT_SELECTION_BUCKET_ID,
          DEFAULT_EVENT_BUCKET_ID, DEFAULT_SEQUENCE_BUCKET_ID };
    
    /**
     * <p>
     * the default bucket search order for optional
     * </p>
     */
    private static final int[] DEFAULT_OPTIONAL_BUCKET_SEARCH_ORDER = new int[]
        { DEFAULT_OPTIONAL_BUCKET_ID, DEFAULT_EVENT_BUCKET_ID, DEFAULT_ITERATION_BUCKET_ID,
          DEFAULT_SELECTION_BUCKET_ID, DEFAULT_SEQUENCE_BUCKET_ID };
    
    /**
     * <p>
     * Comparator to be used for comparing the task instances with each other
     * </p>
     */
    private TaskComparator comparator;

    /**
     * <p>
     * Internally maintained plain list of task instances and associated values
     * </p>
     */
    private List<Map.Entry<ITask, V>> symbolList;

    /**
     * <p>
     * If the size of the map exceeds {@link #MAX_LIST_SIZE}, this is the index using buckets
     * for optimizing the search order.
     * </p>
     */
    private Map<Integer, List<Map.Entry<ITask, V>>> symbolBuckets;
    
    /**
     * <p>
     * When using buckets, not any task instance may be associated a correct bucket. Therefore, we
     * set a default bucket for all such task instances. This may change if the same bucket for a
     * specific symbol is selected.
     * </p>
     */
    private int defaultBucket = 0;
    
    /**
     * <p>
     * the adjustable bucket search order for events. This array is initialized for reuse as
     * otherwise for any lookup of a bucket search order for an individual event, this array would
     * be recreated.
     * </p>
     */
    private final int[] ADJUSTABLE_EVENT_SPECIFIC_BUCKET_SEARCH_ORDER = new int[]
        { 0, 0, DEFAULT_ITERATION_BUCKET_ID, DEFAULT_OPTIONAL_BUCKET_ID, DEFAULT_EVENT_BUCKET_ID,
          DEFAULT_SELECTION_BUCKET_ID };
    
    /**
     * <p>
     * Instantiates a task instance map with a comparator
     * </p>
     *
     * @param comparator the comparator to use for comparing task instances
     * 
     * @throws IllegalArgumentException if the provided comparator is null
     */
    public TaskSymbolBucketedMap(TaskComparator comparator) {
        if (comparator == null) {
            throw new IllegalArgumentException("comparator must not be null");
        }
        
        this.comparator = comparator;
        this.symbolList = new ArrayList<Map.Entry<ITask, V>>();
    }

    /**
     * <p>
     * Copy constructor
     * </p>
     * 
     * @param otherMap the other map to be copied including its comparator
     * 
     * @throws IllegalArgumentException if the provided other map is null
     */
    public TaskSymbolBucketedMap(TaskSymbolBucketedMap<V> otherMap) {
        if (otherMap == null) {
            throw new IllegalArgumentException("otherMap must not be null");
        }

        this.comparator = otherMap.comparator;
        this.symbolList = new ArrayList<Map.Entry<ITask, V>>(otherMap.symbolList);
        
        if (this.symbolList.size() > MAX_LIST_SIZE) {
            createSymbolBuckets();
        }
    }

    /**
     * <p>
     * Returns the size of the map, i.e. the number of task instance 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 task instance was stored in this map.
     * </p>
     * 
     * @param symbol the task instance to check if it was stored in this map
     * 
     * @return as described
     * 
     * @throws IllegalArgumentException if the provided task instance is null
     */
    public boolean containsSymbol(ITask symbol) {
        if (symbol == null) {
            throw new IllegalArgumentException("symbol must not be null");
        }
        
        return getEntry(symbol) != null;
    }

    /**
     * <p>
     * Returns the value associated to the provided task instance in this map. If there is no value
     * associated to the given task instance or if the task instance is not stored in this map,
     * the method returns null.
     * </p>
     * 
     * @param symbol the task instance to return the value for
     * 
     * @return as described
     * 
     * @throws IllegalArgumentException if the provided task instance is null
     */
    public V getValue(ITask symbol) {
        if (symbol == null) {
            throw new IllegalArgumentException("symbol must not be null");
        }
        
        Map.Entry<ITask, V> entry = getEntry(symbol);
        
        if (entry != null) {
            return entry.getValue();
        }
        else {
            return null;
        }
    }

    /**
     * <p>
     * Adds a task instance and an associated value to the map. If the value is null, the task
     * instance is added, anyway and {@link #containsSymbol(Object)} will return true for that
     * task instance. Adding the same task instance 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 task instance to add to the map
     * @param value  the value to associate to the task instance in this map
     * 
     * @return as described
     * 
     * @throws IllegalArgumentException if the provided task instance is null
     */
    public void addSymbol(ITask symbol, V value) {
        if (symbol == null) {
            throw new IllegalArgumentException("symbol must not be null");
        }
        
        Map.Entry<ITask, 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 task instance and its associated value from the map. If the task instance is
     * stored several times, only the first of its occurrences is removed. 
     * </p>
     * 
     * @param symbol the task instance to be removed from the map
     * 
     * @return as described
     * 
     * @throws IllegalArgumentException if the provided task instance is null
     */
    public V removeSymbol(ITask 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 task instances in this map.
     * </p>
     *
     * @return as described
     */
    public Collection<ITask> getSymbols() {
        return new ReadOnlyCollectionFacade<ITask>(symbolList, new SymbolFacade());
    }
    
    /**
     * <p>
     * Returns a collection of all values associated to task instances in this map. May contain
     * null values, if some of the task instances 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 task instances 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)) {
            TaskSymbolBucketedMap<V> other = (TaskSymbolBucketedMap<V>) obj;
            
            return (symbolList.size() == other.symbolList.size()) &&
                   (symbolList.containsAll(other.symbolList));
        }
        else {
            return false;
        }
    }

    /**
     * <p>
     * Internally used to create task instance buckets in case the number of stored task instances
     * increased above {@link #MAX_LIST_SIZE}.
     * </p>
     */
    private void createSymbolBuckets() {
        symbolBuckets = new HashMap<Integer, List<Map.Entry<ITask, V>>>();
        
        for (Map.Entry<ITask, V> symbol : symbolList) {
            addToSymbolBucket(symbol);
        }
    }

    /**
     * <p>
     * Adds a task instance and its value to its corresponding bucket. The corresponding bucket is
     * the first element of the array returned by the method
     * {@link #getBucketSearchOrder(ITaskInstance)}. If no search order for a task instance is
     * defined, the entry is added to the default bucket. If the bucket id identical to the default
     * bucket id, the default bucket id is shifted to another value.
     * </p>
     */
    private void addToSymbolBucket(Map.Entry<ITask, V> symbolEntry) {
        int bucketId = defaultBucket;
        int[] bucketSearchOrder = getBucketSearchOrder(symbolEntry.getKey());
        
        if ((bucketSearchOrder != null) && (bucketSearchOrder.length > 0)) {
            bucketId = bucketSearchOrder[0];
            
            if (bucketId == defaultBucket) {
                setNewDefaultBucketId();
            }
        }
        
        List<Map.Entry<ITask, V>> list = symbolBuckets.get(bucketId);
        
        if (list == null) {
            list = new LinkedList<Map.Entry<ITask, V>>();
            symbolBuckets.put(bucketId, list);
        }
        
        list.add(symbolEntry);
    }
    
    /**
     * <p>
     * returns the search order for a task instance which is different for event task instances,
     * sequence instances, selection instances, and iteration instances
     * </p>
     */
    private int[] getBucketSearchOrder(ITask task) {
        // 0 = sequence; 1 = selection; 2 = iteration; 3 = optional; 4 = event task in general;
        // other = hashCode of name of event type
        
        if (task instanceof IEventTask) {
            // event tasks are most likely equal to those of the same type happening on the same
            // target. Afterwards, they should be equal to those of the event type with the same
            // name. Afterwards, they may be equal to iterations, optionals, other event tasks,
            // selections, and finally the rest.
            
            Collection<ITaskInstance> instances = task.getInstances();
            
            if (instances.size() > 0) {
                Event event = ((IEventTaskInstance) instances.iterator().next()).getEvent();
                
                ADJUSTABLE_EVENT_SPECIFIC_BUCKET_SEARCH_ORDER[0] =
                    event.getTarget().hashCode() + event.getType().getName().hashCode();
                ADJUSTABLE_EVENT_SPECIFIC_BUCKET_SEARCH_ORDER[1] =
                    event.getType().getName().hashCode();
                
                return ADJUSTABLE_EVENT_SPECIFIC_BUCKET_SEARCH_ORDER;
            }
            else {
                return DEFAULT_EVENT_BUCKET_SEARCH_ORDER;
            }
        }
        else if (task instanceof ISequence) {
            return DEFAULT_SEQUENCE_BUCKET_SEARCH_ORDER;
        }
        else if (task instanceof ISelection) {
            return DEFAULT_SELECTION_BUCKET_SEARCH_ORDER;
        }
        else if (task instanceof IIteration) {
            return DEFAULT_ITERATION_BUCKET_SEARCH_ORDER;
        }
        else if (task instanceof IOptional) {
            return DEFAULT_OPTIONAL_BUCKET_SEARCH_ORDER;
        }
        
        return null;
    }

    /**
     * <p>
     * Removes the entry for a given task instance from the buckets. It uses the bucket search order
     * defined to find the task instance as fast as possible.
     * </p>
     */
    private Map.Entry<ITask, V> removeFromSymbolBuckets(ITask symbol) {
        int bucketId = defaultBucket;
        int[] bucketSearchOrder = getBucketSearchOrder(symbol);
        
        if ((bucketSearchOrder != null) && (bucketSearchOrder.length > 0)) {
            bucketId = bucketSearchOrder[0];
        }
        
        List<Map.Entry<ITask, V>> list = symbolBuckets.get(bucketId);
        Map.Entry<ITask, 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.remove(oldDefaultBucket));
    }

    /**
     * <p>
     * searches for the entry belonging to the given task instance. 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 method {@link #getBucketSearchOrder(ITaskInstance)}. If the task instances
     * isn't found and the bucket search order does not refer all buckets, then also the other
     * buckets are searched for the task instance.
     * </p>
     */
    private Map.Entry<ITask, V> getEntry(ITask symbol) {
        Map.Entry<ITask, V> entry = null;
        if (symbolBuckets == null) {
            entry = lookup(symbol, symbolList);
        }
        else {
            int[] bucketSearchOrder = getBucketSearchOrder(symbol);
            for (int bucketId : bucketSearchOrder) {
                List<Map.Entry<ITask, V>> list = symbolBuckets.get(bucketId);
                if (list != null) {
                    entry = lookup(symbol, list);
                    if (entry != null) {
                        break;
                    }
                }
            }
            
            // try to search the other buckets (may be required, if bucket separation given by
            // bucket ids is different from logical bucket separation of comparator
            if (entry == null) {
                // create a copy of the search order to be able to sort and afterwards binary
                // search it. The original version MUST NOT BE SORTED.
                int[] bucketSearchOrderCopy =
                    Arrays.copyOf(bucketSearchOrder, bucketSearchOrder.length);
                
                Arrays.sort(bucketSearchOrderCopy);
                for (Map.Entry<Integer, List<Map.Entry<ITask, V>>> bucket : symbolBuckets.entrySet()) {
                    if (Arrays.binarySearch(bucketSearchOrderCopy, bucket.getKey()) < 0) {
                        List<Map.Entry<ITask, 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<ITask, V> lookup(ITask symbol, List<Map.Entry<ITask, V>> list) {
        for (Map.Entry<ITask, V> candidate : list) {
            if (comparator.equals(candidate.getKey(), symbol)) {
                return candidate;
            }
        }
        
        return null;
    }

    /**
     * <p>
     * Internally used data structure for storing task instance - value pairs
     * </p>
     * 
     * @author Patrick Harms
     */
    private class SymbolMapEntry implements Map.Entry<ITask, V> {
        
        /**
         * the task instance to map to a value
         */
        private ITask symbol;
        
        /**
         * the value associated with the symbol
         */
        private V value;

        /**
         * <p>
         * Simple constructor for initializing the entry with a task instance and its associated
         * value.
         * </p>
         */
        private SymbolMapEntry(ITask symbol, V value) {
            super();
            this.symbol = symbol;
            this.value = value;
        }

        /* (non-Javadoc)
         * @see java.util.Map.Entry#getKey()
         */
        @Override
        public ITask 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 task instances 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 task instances 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<ITask, 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<ITask, 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<ITask, V> entry : list) {
                    if (entryFacade.getFacadedElement(entry) == null) {
                        return true;
                    }
                }
            }
            else {
                for (Map.Entry<ITask, 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 task instance
     * entries.
     * </p>
     * 
     * @author Patrick Harms
     */
    private class ReadOnlyCollectionIteratorFacade<TYPE> implements Iterator<TYPE> {
        
        /**
         * the facaded iterator
         */
        private Iterator<Map.Entry<ITask, 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<ITask, 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 task instance 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<ITask, 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<ITask> {

        /* (non-Javadoc)
         * @see ReadOnlyCollectionIteratorFacade#getFacadedElement(Entry)
         */
        @Override
        protected ITask getFacadedElement(Entry<ITask, 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<ITask, V> entry) {
            return entry.getValue();
        }
    }

}