// 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.IEventTaskInstance; import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance; import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelectionInstance; import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequenceInstance; import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance; import de.ugoe.cs.autoquest.usageprofiles.SymbolMap; /** *
* 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. *
** 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. *
* * @see SymbolComparator * * @author Patrick Harms * @param* default serial version UID *
*/ private static final long serialVersionUID = 1L; /** ** the maximum number of task instances 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 task instances with each other *
*/ private TaskInstanceComparator comparator; /** ** Internally maintained plain list of task instances and associated values *
*/ private List* If the size of the map exceeds {@link #MAX_LIST_SIZE}, this is the index using buckets * for optimizing the search order. *
*/ private Map* 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. *
*/ private int defaultBucket = 0; /** ** Instantiates a task instance map with a comparator *
* * @param comparator the comparator to use for comparing task instances * * @throws IllegalArgumentException if the provided comparator is null */ public TaskSymbolBucketedMap(TaskInstanceComparator comparator) { if (comparator == null) { throw new IllegalArgumentException("comparator must not be null"); } this.comparator = comparator; this.symbolList = new ArrayList* Copy constructor *
* * @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 task instance 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 task instance was stored in this map. *
* * @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(ITaskInstance symbol) { if (symbol == null) { throw new IllegalArgumentException("symbol must not be null"); } return getEntry(symbol) != null; } /** ** 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. *
* * @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(ITaskInstance symbol) { if (symbol == null) { throw new IllegalArgumentException("symbol must not be null"); } Map.Entry* 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. *
* * @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(ITaskInstance symbol, V value) { if (symbol == null) { throw new IllegalArgumentException("symbol must not be null"); } Map.Entry* 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. *
* * @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(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 task instances in this map. *
* * @return as described */ public Collection* 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. *
* * @return as described */ public Collection* Removes all task instances 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 task instance buckets in case the number of stored task instances * increased above {@link #MAX_LIST_SIZE}. *
*/ private void createSymbolBuckets() { //System.out.println("creating symbol buckets"); symbolBuckets = new HashMap* 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. *
*/ private void addToSymbolBucket(Map.Entry* returns the search order for a task instance which is different for event task instances, * sequence instances, selection instances, and iteration instances *
*/ private int[] getBucketSearchOrder(ITaskInstance taskInstance) { // 0 = sequence; 1 = selection; 2 = iteration; 3 = optional; 4 = event task in general; // other = hashCode of name of event type if (taskInstance instanceof IEventTaskInstance) { // 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. Event event = ((IEventTaskInstance) taskInstance).getEvent(); return new int[] { event.getTarget().hashCode() + event.getType().getName().hashCode(), event.getType().getName().hashCode(), 2, 3, 4, 1 }; } else if (taskInstance instanceof ISequenceInstance) { return new int[] { 0, 2, 3, 1 }; } else if (taskInstance instanceof ISelectionInstance) { return new int[] { 1, 4, 2, 3 }; } else if (taskInstance instanceof IIterationInstance) { return new int[] { 2, 1, 4 }; } return null; } /** ** 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. *
*/ 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.remove(oldDefaultBucket)); } /** ** 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. *
*/ 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 task instance - value pairs *
* * @author Patrick Harms */ private class SymbolMapEntry implements Map.Entry* Simple constructor for initializing the entry with a task instance 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 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. *
* * @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 task instance * 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 task instance 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