Ignore:
Timestamp:
02/27/14 14:48:52 (11 years ago)
Author:
pharms
Message:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/autoquest-core-tasktrees/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TaskSymbolBucketedMap.java

    r1294 r1408  
    2626import java.util.Map.Entry; 
    2727 
    28 import de.ugoe.cs.autoquest.eventcore.IEventType; 
     28import de.ugoe.cs.autoquest.eventcore.Event; 
    2929import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTaskInstance; 
    3030import de.ugoe.cs.autoquest.tasktrees.treeifc.IIterationInstance; 
     
    3535 
    3636/** 
    37  * TODO correct comment 
    3837 * <p> 
    39  * This class is a data structure for holding symbols which is more efficient than a simple list. 
    40  * This data structure can be used with a comparator to adapt the effective list behavior and to 
    41  * define the equals strategy for comparing objects. After a certain size ({@link #MAX_LIST_SIZE}), 
    42  * the symbol map creates a symbol index consisting of buckets. This allows searching for symbols 
    43  * in a more efficient order as the search can start in the most appropriate of the internal 
    44  * buckets. 
     38 * This class is a data structure for holding task instances in form of a symbol map. It is more 
     39 * efficient than a simple list. This data structure can be used with a comparator to adapt the 
     40 * effective list behavior and to define the equals strategy for comparing task instances. After a 
     41 * certain size ({@link #MAX_LIST_SIZE}), the map creates an index consisting of buckets of similar 
     42 * task instances. This allows searching for task instances in a more efficient order as the search 
     43 * can start in the most appropriate of the internal buckets. 
    4544 * </p> 
    4645 * <p> 
    47  * The class is called a map, although it is not. It may contain the same element as separate keys. 
    48  * This implementation is done for performance improvements. If it is required to really assure, 
    49  * that a key exists only once, then each call to the {@link #addSymbol(Object, Object)} method 
    50  * should be done only, if the {@link #containsSymbol(Object)} method for the same symbol returns 
    51  * false. 
     46 * The class is called a map, although it is not. It may contain the same task instances as 
     47 * separate keys. This implementation is done for performance improvements. If it is required to 
     48 * really assure, that a key exists only once, then each call to the 
     49 * {@link #addSymbol(Object, Object)} method should be done only, if the 
     50 * {@link #containsSymbol(Object)} method for the same symbol returns false. 
    5251 * </p> 
    5352 *  
     
    6867    /** 
    6968     * <p> 
    70      * the maximum number of symbols in this map which is still only treated as list instead of 
    71      * using buckets. 
     69     * the maximum number of task instances in this map which is still only treated as list 
     70     * instead of using buckets. 
    7271     * </p> 
    7372     */ 
     
    7675    /** 
    7776     * <p> 
    78      * Comparator to be used for comparing the symbols with each other and to determine a bucket 
    79      * search order 
     77     * Comparator to be used for comparing the task instances with each other 
    8078     * </p> 
    8179     */ 
     
    8482    /** 
    8583     * <p> 
    86      * Internally maintained plain list of symbols and associated values 
     84     * Internally maintained plain list of task instances and associated values 
    8785     * </p> 
    8886     */ 
     
    9189    /** 
    9290     * <p> 
    93      * If the size of the map exceeds {@link #MAX_LIST_SIZE}, this is the symbol index using buckets 
     91     * If the size of the map exceeds {@link #MAX_LIST_SIZE}, this is the index using buckets 
    9492     * for optimizing the search order. 
    9593     * </p> 
     
    9997    /** 
    10098     * <p> 
    101      * When using buckets, not any symbol may be associated a correct bucket by the used 
    102      * comparator. Therefore, we set a default bucket for all such symbols. This may change 
    103      * if the comparator defines the same bucket for a specific symbol. 
     99     * When using buckets, not any task instance may be associated a correct bucket. Therefore, we 
     100     * set a default bucket for all such task instances. This may change if the same bucket for a 
     101     * specific symbol is selected. 
    104102     * </p> 
    105103     */ 
     
    108106    /** 
    109107     * <p> 
    110      * Instantiates a symbol map with a comparator 
     108     * Instantiates a task instance map with a comparator 
    111109     * </p> 
    112110     * 
    113      * @param comparator the comparator to use for comparing symbols and for determining bucket 
    114      *                   search orders 
     111     * @param comparator the comparator to use for comparing task instances 
    115112     *  
    116113     * @throws IllegalArgumentException if the provided comparator is null 
     
    127124    /** 
    128125     * <p> 
    129      * Copy constructure 
     126     * Copy constructor 
    130127     * </p> 
    131128     *  
     
    149146    /** 
    150147     * <p> 
    151      * Returns the size of the map, i.e. the number of symbol entries 
     148     * Returns the size of the map, i.e. the number of task instance entries 
    152149     * </p> 
    153150     *  
     
    171168    /** 
    172169     * <p> 
    173      * Returns true if the provided symbol was stored in this map. 
    174      * </p> 
    175      *  
    176      * @param symbol the symbol to check if it was stored in this map 
     170     * Returns true if the provided task instance was stored in this map. 
     171     * </p> 
     172     *  
     173     * @param symbol the task instance to check if it was stored in this map 
    177174     *  
    178175     * @return as described 
    179176     *  
    180      * @throws IllegalArgumentException if the provided symbol is null 
     177     * @throws IllegalArgumentException if the provided task instance is null 
    181178     */ 
    182179    public boolean containsSymbol(ITaskInstance symbol) { 
     
    190187    /** 
    191188     * <p> 
    192      * Returns the value associated to the provided symbol in this map. If there is no value 
    193      * associated to the given symbol or if the symbol is not stored in this map, the method 
    194      * returns null. 
    195      * </p> 
    196      *  
    197      * @param symbol the symbol to return the value for 
     189     * Returns the value associated to the provided task instance in this map. If there is no value 
     190     * associated to the given task instance or if the task instance is not stored in this map, 
     191     * the method returns null. 
     192     * </p> 
     193     *  
     194     * @param symbol the task instance to return the value for 
    198195     *  
    199196     * @return as described 
    200197     *  
    201      * @throws IllegalArgumentException if the provided symbol is null 
     198     * @throws IllegalArgumentException if the provided task instance is null 
    202199     */ 
    203200    public V getValue(ITaskInstance symbol) { 
     
    218215    /** 
    219216     * <p> 
    220      * Adds a symbol and an associated value to the map. If the value is null, the symbol is added, 
    221      * anyway and {@link #containsSymbol(Object)} will return true for that symbol. Adding the 
    222      * same symbol twice will produce two entries. This is contradictory to typical map 
    223      * implementations. To prevent this, the {@link #containsSymbol(Object)} and 
    224      * {@link #removeSymbol(Object)} methods should be used to ensure map behavior. 
    225      * </p> 
    226      *  
    227      * @param symbol the symbol to add to the map 
    228      * @param value  the value to associate to the symbol in this map 
     217     * Adds a task instance and an associated value to the map. If the value is null, the task 
     218     * instance is added, anyway and {@link #containsSymbol(Object)} will return true for that 
     219     * task instance. Adding the same task instance twice will produce two entries. This is 
     220     * contradictory to typical map implementations. To prevent this, the 
     221     * {@link #containsSymbol(Object)} and {@link #removeSymbol(Object)} methods should be used to 
     222     * ensure map behavior. 
     223     * </p> 
     224     *  
     225     * @param symbol the task instance to add to the map 
     226     * @param value  the value to associate to the task instance in this map 
    229227     *  
    230228     * @return as described 
    231229     *  
    232      * @throws IllegalArgumentException if the provided symbol is null 
     230     * @throws IllegalArgumentException if the provided task instance is null 
    233231     */ 
    234232    public void addSymbol(ITaskInstance symbol, V value) { 
     
    253251    /** 
    254252     * <p> 
    255      * Removes a symbol and its associated value from the map. If the symbol is stored several 
    256      * times, the first of its occurrences is removed.  
    257      * </p> 
    258      *  
    259      * @param symbol the symbol to be removed from the map 
     253     * Removes a task instance and its associated value from the map. If the task instance is 
     254     * stored several times, only the first of its occurrences is removed.  
     255     * </p> 
     256     *  
     257     * @param symbol the task instance to be removed from the map 
    260258     *  
    261259     * @return as described 
    262260     *  
    263      * @throws IllegalArgumentException if the provided symbol is null 
     261     * @throws IllegalArgumentException if the provided task instance is null 
    264262     */ 
    265263    public V removeSymbol(ITaskInstance symbol) { 
     
    286284    /** 
    287285     * <p> 
    288      * Returns a collection of all symbols in this map. 
     286     * Returns a collection of all task instances in this map. 
    289287     * </p> 
    290288     * 
     
    297295    /** 
    298296     * <p> 
    299      * Returns a collection of all values associated to symbols in this map. May contain null 
    300      * values, if some of the symbols are mapped to null. The length of the returned collection 
    301      * is in any case the same as the size of the map. 
     297     * Returns a collection of all values associated to task instances in this map. May contain 
     298     * null values, if some of the task instances are mapped to null. The length of the returned 
     299     * collection is in any case the same as the size of the map. 
    302300     * </p> 
    303301     * 
     
    310308    /** 
    311309     * <p> 
    312      * Removes all symbols and associated values from the map. 
     310     * Removes all task instances and associated values from the map. 
    313311     * </p> 
    314312     */ 
     
    348346    /** 
    349347     * <p> 
    350      * Internally used to create symbol buckets in case the number of stored symbols increased 
    351      * above {@link #MAX_LIST_SIZE}. 
     348     * Internally used to create task instance buckets in case the number of stored task instances 
     349     * increased above {@link #MAX_LIST_SIZE}. 
    352350     * </p> 
    353351     */ 
     
    363361    /** 
    364362     * <p> 
    365      * Adds a symbol and its value to its corresponding bucket. The corresponding bucket is 
    366      * retrieved from the symbol comparator. It is the first element of the search order returned 
    367      * by the symbol comparator. If the comparator does not define a search order for the symbol 
    368      * the entry is added to the default bucket. If the comparator defines a bucket id 
    369      * identical to the default bucket id, the default bucket id is shifted to another value. 
     363     * Adds a task instance and its value to its corresponding bucket. The corresponding bucket is 
     364     * the first element of the array returned by the method 
     365     * {@link #getBucketSearchOrder(ITaskInstance)}. If no search order for a task instance is 
     366     * defined, the entry is added to the default bucket. If the bucket id identical to the default 
     367     * bucket id, the default bucket id is shifted to another value. 
    370368     * </p> 
    371369     */ 
     
    393391     
    394392    /** 
    395      *  
    396      */ 
    397     public int[] getBucketSearchOrder(ITaskInstance taskInstance) { 
     393     * <p> 
     394     * returns the search order for a task instance which is different for event task instances, 
     395     * sequence instances, selection instances, and iteration instances 
     396     * </p> 
     397     */ 
     398    private int[] getBucketSearchOrder(ITaskInstance taskInstance) { 
    398399        // 0 = sequence; 1 = selection; 2 = iteration; 3 = optional; 4 = event task in general; 
    399400        // other = hashCode of name of event type 
    400401         
    401402        if (taskInstance instanceof IEventTaskInstance) { 
    402             // event tasks are most likely equal to those of the event type with the same name, 
    403             // Afterwards, they may be equal to iterations, optionals, other event tasks, 
     403            // event tasks are most likely equal to those of the same type happening on the same 
     404            // target. Afterwards, they should be equal to those of the event type with the same 
     405            // name. Afterwards, they may be equal to iterations, optionals, other event tasks, 
    404406            // selections, and finally the rest. 
    405             IEventType eventType = ((IEventTaskInstance) taskInstance).getEvent().getType(); 
    406             return new int[] { eventType.getName().hashCode(), 2, 3, 4, 1 };                        
     407            Event event = ((IEventTaskInstance) taskInstance).getEvent(); 
     408            return new int[] { event.getTarget().hashCode() + event.getType().getName().hashCode(), 
     409                               event.getType().getName().hashCode(), 2, 3, 4, 1 };                        
    407410        } 
    408411        else if (taskInstance instanceof ISequenceInstance) { 
     
    421424    /** 
    422425     * <p> 
    423      * Removes the entry for a given symbol from the buckets. It uses the bucket search order 
    424      * defined by the symbol comparator to find the symbol as fast as possible. 
     426     * Removes the entry for a given task instance from the buckets. It uses the bucket search order 
     427     * defined to find the task instance as fast as possible. 
    425428     * </p> 
    426429     */ 
     
    464467        while (symbolBuckets.containsKey(defaultBucket)); 
    465468         
    466         symbolBuckets.put(defaultBucket, symbolBuckets.get(oldDefaultBucket)); 
    467     } 
    468  
    469     /** 
    470      * <p> 
    471      * searches for the entry belonging to the given symbol. The method either uses the list if 
    472      * buckets are not used yet, or it uses the buckets and searches them in the order defined 
    473      * by the comparator. If the symbol isn't found and the comparator does not refer all buckets, 
    474      * then also the other buckets are searched for the symbol. 
     469        symbolBuckets.put(defaultBucket, symbolBuckets.remove(oldDefaultBucket)); 
     470    } 
     471 
     472    /** 
     473     * <p> 
     474     * searches for the entry belonging to the given task instance. The method either uses the 
     475     * list if buckets are not used yet, or it uses the buckets and searches them in the order 
     476     * defined by the method {@link #getBucketSearchOrder(ITaskInstance)}. If the task instances 
     477     * isn't found and the bucket search order does not refer all buckets, then also the other 
     478     * buckets are searched for the task instance. 
    475479     * </p> 
    476480     */ 
     
    529533    /** 
    530534     * <p> 
    531      * Internally used data structure for storing symbol value pairs 
     535     * Internally used data structure for storing task instance - value pairs 
    532536     * </p> 
    533537     *  
     
    537541         
    538542        /** 
    539          * the symbol to map to a value 
     543         * the task instance to map to a value 
    540544         */ 
    541545        private ITaskInstance symbol; 
     
    548552        /** 
    549553         * <p> 
    550          * Simple constructor for initializing the entry with a symbol and its associated value. 
     554         * Simple constructor for initializing the entry with a task instance and its associated 
     555         * value. 
    551556         * </p> 
    552557         */ 
     
    623628     * <p> 
    624629     * Used to create an efficient facade for accessing the internal list of entries either only 
    625      * for the symbols or only for the values. It is a default implementation of the collection 
    626      * interface. The entry facade provided to the constructor decides, if either the list 
    627      * accesses only the symbols or only the values.  
     630     * for the task instances or only for the values. It is a default implementation of the 
     631     * collection interface. The entry facade provided to the constructor decides, if either the 
     632     * list accesses only the task instances or only the values.  
    628633     * </p> 
    629634     *  
     
    647652         * </p> 
    648653         */ 
    649         private ReadOnlyCollectionFacade(List<Map.Entry<ITaskInstance, V>> list, EntryFacade<TYPE> entryFacade) 
     654        private ReadOnlyCollectionFacade(List<Map.Entry<ITaskInstance, V>> list, 
     655                                         EntryFacade<TYPE>                 entryFacade) 
    650656        { 
    651657            this.list = list; 
     
    795801    /** 
    796802     * <p> 
    797      * Implementation of an iterator to facade an iterator on the internal list of symbol entries. 
     803     * Implementation of an iterator to facade an iterator on the internal list of task instance 
     804     * entries. 
    798805     * </p> 
    799806     *  
     
    819826         */ 
    820827        private ReadOnlyCollectionIteratorFacade(Iterator<Map.Entry<ITaskInstance, V>> iterator, 
    821                                                  EntryFacade<TYPE>         entryFacade) 
     828                                                 EntryFacade<TYPE>                     entryFacade) 
    822829        { 
    823830            this.iterator = iterator; 
     
    853860    /** 
    854861     * <p> 
    855      * Used to facade symbol entries and to return only this part of an entry, that is relevant. 
     862     * Used to facade task instance entries and to return only this part of an entry, that is 
     863     * relevant. 
    856864     * </p> 
    857865     *  
Note: See TracChangeset for help on using the changeset viewer.