// 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.IEventType; import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTask; import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration; 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; /** * TODO correct comment *
* 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. *
** 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. *
* * @see SymbolComparator * * @author Patrick Harms * @param* default serial version UID *
*/ private static final long serialVersionUID = 1L; /** ** the maximum number of symbols in this map which is still only treated as list instead of * using buckets. *
*/ private static final int MAX_LIST_SIZE = 15; /** ** Comparator to be used for comparing the symbols with each other and to determine a bucket * search order *
*/ private TaskComparator comparator; /** ** Internally maintained plain list of symbols and associated values *
*/ private List* If the size of the map exceeds {@link #MAX_LIST_SIZE}, this is the symbol index using buckets * for optimizing the search order. *
*/ private Map* 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. *
*/ private int defaultBucket = 0; /** ** Instantiates a symbol map with a comparator *
* * @param comparator the comparator to use for comparing symbols and for determining bucket * search orders * * @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* Copy constructure *
* * @param otherMap the other map to be copied including its comparator * * @throws IllegalArgumentException if the provided other map is null */ public TaskSymbolBucketedMap(TaskSymbolBucketedMap* Returns the size of the map, i.e. the number of symbol entries *
* * @return as described */ public int size() { return symbolList.size(); } /** ** Returns true if this map is empty, i.e. if {@link #size()} returns 0 *
* * @return as described */ public boolean isEmpty() { return symbolList.isEmpty(); } /** ** Returns true if the provided symbol was stored in this map. *
* * @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(ITaskInstance symbol) { if (symbol == null) { throw new IllegalArgumentException("symbol must not be null"); } return getEntry(symbol) != null; } /** ** 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. *
* * @param symbol the symbol to return the value for * * @return as described * * @throws IllegalArgumentException if the provided symbol is null */ public V getValue(ITaskInstance symbol) { if (symbol == null) { throw new IllegalArgumentException("symbol must not be null"); } Map.Entry* 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. *
* * @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(ITaskInstance symbol, V value) { if (symbol == null) { throw new IllegalArgumentException("symbol must not be null"); } Map.Entry* Removes a symbol and its associated value from the map. If the symbol is stored several * times, the first of its occurrences is removed. *
* * @param symbol the symbol to be removed from the map * * @return as described * * @throws IllegalArgumentException if the provided symbol is null */ public V removeSymbol(ITaskInstance 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; } /** ** Returns a collection of all symbols in this map. *
* * @return as described */ public Collection* 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. *
* * @return as described */ public Collection* Removes all symbols and associated values from the map. *
*/ 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* Internally used to create symbol buckets in case the number of stored symbols increased * above {@link #MAX_LIST_SIZE}. *
*/ private void createSymbolBuckets() { //System.out.println("creating symbol buckets"); symbolBuckets = new HashMap* 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. *
*/ private void addToSymbolBucket(Map.Entry* 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. *
*/ private Map.Entry* Updates the default bucket id to a new one *
*/ private void setNewDefaultBucketId() { int oldDefaultBucket = defaultBucket; do { defaultBucket += 1; } while (symbolBuckets.containsKey(defaultBucket)); symbolBuckets.put(defaultBucket, symbolBuckets.get(oldDefaultBucket)); } /** ** 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. *
*/ private Map.Entry* Convenience method to look up a symbol in a list of entries using the comparator. *
*/ private Map.Entry* Internally used data structure for storing symbol value pairs *
* * @author Patrick Harms */ private class SymbolMapEntry implements Map.Entry* Simple constructor for initializing the entry with a symbol and its associated value. *
*/ private SymbolMapEntry(ITaskInstance symbol, V value) { super(); this.symbol = symbol; this.value = value; } /* (non-Javadoc) * @see java.util.Map.Entry#getKey() */ @Override public ITaskInstance 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; } } /** ** 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. *
* * @author Patrick Harms */ private class ReadOnlyCollectionFacade* Initializes the facade with the facaded list and the facade to be used for the entries *
*/ private ReadOnlyCollectionFacade(List* Implementation of an iterator to facade an iterator on the internal list of symbol entries. *
* * @author Patrick Harms */ private class ReadOnlyCollectionIteratorFacade* initialized this facade with the facaded iterator and the entry facade to be used for * the entries. *
*/ private ReadOnlyCollectionIteratorFacade(Iterator* Used to facade symbol entries and to return only this part of an entry, that is relevant. *
* * @author Patrick Harms */ private abstract class EntryFacade* Returns only the part of an entry that is relevant or required. *
* * @param entry of which the part shall be returned * * @return the part of the entry to be returned */ protected abstract T getFacadedElement(Entry* Implementation of the entry facade returning the entries key, i.e. the symbol. *
* * @author Patrick Harms */ private class SymbolFacade extends EntryFacade* Implementation of the entry facade returning the entries value, i.e. the value associated to * the symbol. *
* * @author Patrick Harms */ private class ValueFacade extends EntryFacade