Ignore:
Timestamp:
09/05/14 19:33:12 (10 years ago)
Author:
rkrimmel
Message:

Used Eclipse code cleanup

File:
1 edited

Legend:

Unmodified
Added
Removed

  • branches/autoquest-core-tasktrees-alignment/src/main/java/de/ugoe/cs/autoquest/tasktrees/temporalrelation/TaskSymbolBucketedMap.java

    r1408 r1733  
    3636/** 
    3737 * <p> 
    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. 
     38 * This class is a data structure for holding task instances in form of a symbol 
     39 * map. It is more efficient than a simple list. This data structure can be used 
     40 * with a comparator to adapt the effective list behavior and to define the 
     41 * equals strategy for comparing task instances. After a certain size ( 
     42 * {@link #MAX_LIST_SIZE}), the map creates an index consisting of buckets of 
     43 * similar task instances. This allows searching for task instances in a more 
     44 * efficient order as the search can start in the most appropriate of the 
     45 * internal buckets. 
    4446 * </p> 
    4547 * <p> 
    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. 
     48 * The class is called a map, although it is not. It may contain the same task 
     49 * instances as separate keys. This implementation is done for performance 
     50 * improvements. If it is required to really assure, that a key exists only 
     51 * once, then each call to the {@link #addSymbol(Object, Object)} method should 
     52 * be done only, if the {@link #containsSymbol(Object)} method for the same 
     53 * symbol returns false. 
    5154 * </p> 
    5255 *  
    … …  
    5659 * @param <V> 
    5760 */ 
    58 class TaskSymbolBucketedMap<V> implements SymbolMap<ITaskInstance, V>, Serializable { 
    59  
    60     /** 
    61      * <p> 
    62      * default serial version UID 
    63      * </p> 
    64      */ 
    65     private static final long serialVersionUID = 1L; 
    66  
    67     /** 
    68      * <p> 
    69      * the maximum number of task instances in this map which is still only treated as list 
    70      * instead of using buckets. 
    71      * </p> 
    72      */ 
    73     private static final int MAX_LIST_SIZE = 15; 
    74      
    75     /** 
    76      * <p> 
    77      * Comparator to be used for comparing the task instances with each other 
    78      * </p> 
    79      */ 
    80     private TaskInstanceComparator comparator; 
    81  
    82     /** 
    83      * <p> 
    84      * Internally maintained plain list of task instances and associated values 
    85      * </p> 
    86      */ 
    87     private List<Map.Entry<ITaskInstance, V>> symbolList; 
    88  
    89     /** 
    90      * <p> 
    91      * If the size of the map exceeds {@link #MAX_LIST_SIZE}, this is the index using buckets 
    92      * for optimizing the search order. 
    93      * </p> 
    94      */ 
    95     private Map<Integer, List<Map.Entry<ITaskInstance, V>>> symbolBuckets; 
    96      
    97     /** 
    98      * <p> 
    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. 
    102      * </p> 
    103      */ 
    104     private int defaultBucket = 0; 
    105      
    106     /** 
    107      * <p> 
    108      * Instantiates a task instance map with a comparator 
    109      * </p> 
    110      * 
    111      * @param comparator the comparator to use for comparing task instances 
    112      *  
    113      * @throws IllegalArgumentException if the provided comparator is null 
    114      */ 
    115     public TaskSymbolBucketedMap(TaskInstanceComparator comparator) { 
    116         if (comparator == null) { 
    117             throw new IllegalArgumentException("comparator must not be null"); 
    118         } 
    119          
    120         this.comparator = comparator; 
    121         this.symbolList = new ArrayList<Map.Entry<ITaskInstance, V>>(); 
    122     } 
    123  
    124     /** 
    125      * <p> 
    126      * Copy constructor 
    127      * </p> 
    128      *  
    129      * @param otherMap the other map to be copied including its comparator 
    130      *  
    131      * @throws IllegalArgumentException if the provided other map is null 
    132      */ 
    133     public TaskSymbolBucketedMap(TaskSymbolBucketedMap<V> otherMap) { 
    134         if (otherMap == null) { 
    135             throw new IllegalArgumentException("otherMap must not be null"); 
    136         } 
    137  
    138         this.comparator = otherMap.comparator; 
    139         this.symbolList = new ArrayList<Map.Entry<ITaskInstance, V>>(otherMap.symbolList); 
    140          
    141         if (this.symbolList.size() > MAX_LIST_SIZE) { 
    142             createSymbolBuckets(); 
    143         } 
    144     } 
    145  
    146     /** 
    147      * <p> 
    148      * Returns the size of the map, i.e. the number of task instance entries 
    149      * </p> 
    150      *  
    151      * @return as described 
    152      */ 
    153     public int size() { 
    154         return symbolList.size(); 
    155     } 
    156  
    157     /** 
    158      * <p> 
    159      * Returns true if this map is empty, i.e. if {@link #size()} returns 0 
    160      * </p> 
    161      *  
    162      * @return as described 
    163      */ 
    164     public boolean isEmpty() { 
    165         return symbolList.isEmpty(); 
    166     } 
    167  
    168     /** 
    169      * <p> 
    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 
    174      *  
    175      * @return as described 
    176      *  
    177      * @throws IllegalArgumentException if the provided task instance is null 
    178      */ 
    179     public boolean containsSymbol(ITaskInstance symbol) { 
    180         if (symbol == null) { 
    181             throw new IllegalArgumentException("symbol must not be null"); 
    182         } 
    183          
    184         return getEntry(symbol) != null; 
    185     } 
    186  
    187     /** 
    188      * <p> 
    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 
    195      *  
    196      * @return as described 
    197      *  
    198      * @throws IllegalArgumentException if the provided task instance is null 
    199      */ 
    200     public V getValue(ITaskInstance symbol) { 
    201         if (symbol == null) { 
    202             throw new IllegalArgumentException("symbol must not be null"); 
    203         } 
    204          
    205         Map.Entry<ITaskInstance, V> entry = getEntry(symbol); 
    206          
    207         if (entry != null) { 
    208             return entry.getValue(); 
    209         } 
    210         else { 
    211             return null; 
    212         } 
    213     } 
    214  
    215     /** 
    216      * <p> 
    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 
    227      *  
    228      * @return as described 
    229      *  
    230      * @throws IllegalArgumentException if the provided task instance is null 
    231      */ 
    232     public void addSymbol(ITaskInstance symbol, V value) { 
    233         if (symbol == null) { 
    234             throw new IllegalArgumentException("symbol must not be null"); 
    235         } 
    236          
    237         Map.Entry<ITaskInstance, V> entry = new SymbolMapEntry(symbol, value); 
    238          
    239         symbolList.add(entry); 
    240              
    241         if (symbolList.size() > MAX_LIST_SIZE) { 
    242             if (symbolBuckets == null) { 
    243                 createSymbolBuckets(); 
    244             } 
    245             else { 
    246                 addToSymbolBucket(entry); 
    247             } 
    248         } 
    249     } 
    250  
    251     /** 
    252      * <p> 
    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 
    258      *  
    259      * @return as described 
    260      *  
    261      * @throws IllegalArgumentException if the provided task instance is null 
    262      */ 
    263     public V removeSymbol(ITaskInstance symbol) { 
    264         if (symbol == null) { 
    265             throw new IllegalArgumentException("symbol must not be null"); 
    266         } 
    267          
    268         for (int i = 0; i < symbolList.size(); i++) { 
    269             if (comparator.equals(symbolList.get(i).getKey(), symbol)) { 
    270                 // found the symbol. Remove it from the list, and if required, also from the map. 
    271                 V value = symbolList.remove(i).getValue(); 
    272                  
    273                 if (symbolList.size() > MAX_LIST_SIZE) { 
    274                     removeFromSymbolBuckets(symbol); 
    275                 } 
    276                  
    277                 return value; 
    278             } 
    279         } 
    280          
    281         return null; 
    282     } 
    283  
    284     /** 
    285      * <p> 
    286      * Returns a collection of all task instances in this map. 
    287      * </p> 
    288      * 
    289      * @return as described 
    290      */ 
    291     public Collection<ITaskInstance> getSymbols() { 
    292         return new ReadOnlyCollectionFacade<ITaskInstance>(symbolList, new SymbolFacade()); 
    293     } 
    294      
    295     /** 
    296      * <p> 
    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. 
    300      * </p> 
    301      * 
    302      * @return as described 
    303      */ 
    304     public Collection<V> getValues() { 
    305         return new ReadOnlyCollectionFacade<V>(symbolList, new ValueFacade()); 
    306     } 
    307      
    308     /** 
    309      * <p> 
    310      * Removes all task instances and associated values from the map. 
    311      * </p> 
    312      */ 
    313     public void clear() { 
    314         symbolList.clear(); 
    315         symbolBuckets = null; 
    316     } 
    317  
    318     /* (non-Javadoc) 
    319      * @see java.lang.Object#hashCode() 
    320      */ 
    321     @Override 
    322     public int hashCode() { 
    323         return symbolList.size(); 
    324     } 
    325  
    326     /* (non-Javadoc) 
    327      * @see java.lang.Object#equals(java.lang.Object) 
    328      */ 
    329     @SuppressWarnings("unchecked") 
    330     @Override 
    331     public boolean equals(Object obj) { 
    332         if (this == obj) { 
    333             return true; 
    334         } 
    335         else if (this.getClass().isInstance(obj)) { 
    336             TaskSymbolBucketedMap<V> other = (TaskSymbolBucketedMap<V>) obj; 
    337              
    338             return (symbolList.size() == other.symbolList.size()) && 
    339                    (symbolList.containsAll(other.symbolList)); 
    340         } 
    341         else { 
    342             return false; 
    343         } 
    344     } 
    345  
    346     /** 
    347      * <p> 
    348      * Internally used to create task instance buckets in case the number of stored task instances 
    349      * increased above {@link #MAX_LIST_SIZE}. 
    350      * </p> 
    351      */ 
    352     private void createSymbolBuckets() { 
    353         //System.out.println("creating symbol buckets"); 
    354         symbolBuckets = new HashMap<Integer, List<Map.Entry<ITaskInstance, V>>>(); 
    355          
    356         for (Map.Entry<ITaskInstance, V> symbol : symbolList) { 
    357             addToSymbolBucket(symbol); 
    358         } 
    359     } 
    360  
    361     /** 
    362      * <p> 
    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. 
    368      * </p> 
    369      */ 
    370     private void addToSymbolBucket(Map.Entry<ITaskInstance, V> symbolEntry) { 
    371         int bucketId = defaultBucket; 
    372         int[] bucketSearchOrder = getBucketSearchOrder(symbolEntry.getKey()); 
    373          
    374         if ((bucketSearchOrder != null) && (bucketSearchOrder.length > 0)) { 
    375             bucketId = bucketSearchOrder[0]; 
    376              
    377             if (bucketId == defaultBucket) { 
    378                 setNewDefaultBucketId(); 
    379             } 
    380         } 
    381          
    382         List<Map.Entry<ITaskInstance, V>> list = symbolBuckets.get(bucketId); 
    383          
    384         if (list == null) { 
    385             list = new LinkedList<Map.Entry<ITaskInstance, V>>(); 
    386             symbolBuckets.put(bucketId, list); 
    387         } 
    388          
    389         list.add(symbolEntry); 
    390     } 
    391      
    392     /** 
    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) { 
    399         // 0 = sequence; 1 = selection; 2 = iteration; 3 = optional; 4 = event task in general; 
    400         // other = hashCode of name of event type 
    401          
    402         if (taskInstance instanceof IEventTaskInstance) { 
    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, 
    406             // selections, and finally the rest. 
    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 };                        
    410         } 
    411         else if (taskInstance instanceof ISequenceInstance) { 
    412             return new int[] { 0, 2, 3, 1 };                        
    413         } 
    414         else if (taskInstance instanceof ISelectionInstance) { 
    415             return new int[] { 1, 4, 2, 3 };                        
    416         } 
    417         else if (taskInstance instanceof IIterationInstance) { 
    418             return new int[] { 2, 1, 4 };                        
    419         } 
    420          
    421         return null; 
    422     } 
    423  
    424     /** 
    425      * <p> 
    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. 
    428      * </p> 
    429      */ 
    430     private Map.Entry<ITaskInstance, V> removeFromSymbolBuckets(ITaskInstance symbol) { 
    431         int bucketId = defaultBucket; 
    432         int[] bucketSearchOrder = getBucketSearchOrder(symbol); 
    433          
    434         if ((bucketSearchOrder != null) && (bucketSearchOrder.length > 0)) { 
    435             bucketId = bucketSearchOrder[0]; 
    436         } 
    437          
    438         List<Map.Entry<ITaskInstance, V>> list = symbolBuckets.get(bucketId); 
    439         Map.Entry<ITaskInstance, V> result = null; 
    440          
    441         if (list != null) { 
    442             for (int i = 0; i < list.size(); i++) { 
    443                 if (comparator.equals(list.get(i).getKey(), symbol)) { 
    444                     result = list.remove(i); 
    445                     break; 
    446                 } 
    447             } 
    448              
    449             if (list.isEmpty()) { 
    450                 symbolBuckets.remove(bucketId); 
    451             } 
    452         } 
    453          
    454         return result; 
    455     } 
    456  
    457     /** 
    458      * <p> 
    459      * Updates the default bucket id to a new one 
    460      * </p> 
    461      */ 
    462     private void setNewDefaultBucketId() { 
    463         int oldDefaultBucket = defaultBucket; 
    464         do { 
    465             defaultBucket += 1; 
    466         } 
    467         while (symbolBuckets.containsKey(defaultBucket)); 
    468          
    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. 
    479      * </p> 
    480      */ 
    481     private Map.Entry<ITaskInstance, V> getEntry(ITaskInstance symbol) { 
    482         Map.Entry<ITaskInstance, V> entry = null; 
    483         if (symbolBuckets == null) { 
    484             entry = lookup(symbol, symbolList); 
    485         } 
    486         else { 
    487             int[] bucketSearchOrder = getBucketSearchOrder(symbol); 
    488             for (int bucketId : bucketSearchOrder) { 
    489                 List<Map.Entry<ITaskInstance, V>> list = symbolBuckets.get(bucketId); 
    490                 if (list != null) { 
    491                     entry = lookup(symbol, list); 
    492                     if (entry != null) { 
    493                         break; 
    494                     } 
    495                 } 
    496             } 
    497              
    498             // try to search the other buckets 
    499             if (entry == null) { 
    500                 Arrays.sort(bucketSearchOrder); 
    501                 for (Map.Entry<Integer, List<Map.Entry<ITaskInstance, V>>> bucket : symbolBuckets.entrySet()) { 
    502                     if (Arrays.binarySearch(bucketSearchOrder, bucket.getKey()) < 0) { 
    503                         List<Map.Entry<ITaskInstance, V>> list = bucket.getValue(); 
    504                         if (list != null) { 
    505                             entry = lookup(symbol, list); 
    506                             if (entry != null) { 
    507                                 break; 
    508                             } 
    509                         } 
    510                     } 
    511                 } 
    512             } 
    513         } 
    514          
    515         return entry; 
    516     } 
    517  
    518     /** 
    519      * <p> 
    520      * Convenience method to look up a symbol in a list of entries using the comparator. 
    521      * </p> 
    522      */ 
    523     private Map.Entry<ITaskInstance, V> lookup(ITaskInstance symbol, List<Map.Entry<ITaskInstance, V>> list) { 
    524         for (Map.Entry<ITaskInstance, V> candidate : list) { 
    525             if (comparator.equals(candidate.getKey(), symbol)) { 
    526                 return candidate; 
    527             } 
    528         } 
    529          
    530         return null; 
    531     } 
    532  
    533     /** 
    534      * <p> 
    535      * Internally used data structure for storing task instance - value pairs 
    536      * </p> 
    537      *  
    538      * @author Patrick Harms 
    539      */ 
    540     private class SymbolMapEntry implements Map.Entry<ITaskInstance, V> { 
    541          
    542         /** 
    543          * the task instance to map to a value 
    544          */ 
    545         private ITaskInstance symbol; 
    546          
    547         /** 
    548          * the value associated with the symbol 
    549          */ 
    550         private V value; 
    551  
    552         /** 
    553          * <p> 
    554          * Simple constructor for initializing the entry with a task instance and its associated 
    555          * value. 
    556          * </p> 
    557          */ 
    558         private SymbolMapEntry(ITaskInstance symbol, V value) { 
    559             super(); 
    560             this.symbol = symbol; 
    561             this.value = value; 
    562         } 
    563  
    564         /* (non-Javadoc) 
    565          * @see java.util.Map.Entry#getKey() 
    566          */ 
    567         @Override 
    568         public ITaskInstance getKey() { 
    569             return symbol; 
    570         } 
    571  
    572         /* (non-Javadoc) 
    573          * @see java.util.Map.Entry#getValue() 
    574          */ 
    575         @Override 
    576         public V getValue() { 
    577             return value; 
    578         } 
    579  
    580         /* (non-Javadoc) 
    581          * @see java.util.Map.Entry#setValue(java.lang.Object) 
    582          */ 
    583         @Override 
    584         public V setValue(V value) { 
    585             V oldValue = this.value; 
    586             this.value = value; 
    587             return oldValue; 
    588         } 
    589  
    590         /* (non-Javadoc) 
    591          * @see java.lang.Object#hashCode() 
    592          */ 
    593         @Override 
    594         public int hashCode() { 
    595             return symbol.hashCode(); 
    596         } 
    597  
    598         /* (non-Javadoc) 
    599          * @see java.lang.Object#equals(java.lang.Object) 
    600          */ 
    601         @SuppressWarnings("unchecked") 
    602         @Override 
    603         public boolean equals(Object obj) { 
    604             if (this == obj) { 
    605                 return true; 
    606             } 
    607             else if (this.getClass().isInstance(obj)) { 
    608                 SymbolMapEntry other = (SymbolMapEntry) obj; 
    609                 return (symbol.equals(other.symbol) && 
    610                         (value == null ? other.value == null : value.equals(other.value))); 
    611             } 
    612             else { 
    613                 return false; 
    614             } 
    615         } 
    616  
    617         /* (non-Javadoc) 
    618          * @see java.lang.Object#toString() 
    619          */ 
    620         @Override 
    621         public String toString() { 
    622             return symbol + "=" + value; 
    623         } 
    624  
    625     } 
    626  
    627     /** 
    628      * <p> 
    629      * Used to create an efficient facade for accessing the internal list of entries either only 
    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.  
    633      * </p> 
    634      *  
    635      * @author Patrick Harms 
    636      */ 
    637     private class ReadOnlyCollectionFacade<TYPE> implements Collection<TYPE> { 
    638          
    639         /** 
    640          * the list facaded by this facade 
    641          */ 
    642         private List<Map.Entry<ITaskInstance, V>> list; 
    643          
    644         /** 
    645          * the facade to be used for the entries 
    646          */ 
    647         private EntryFacade<TYPE> entryFacade; 
    648          
    649         /** 
    650          * <p> 
    651          * Initializes the facade with the facaded list and the facade to be used for the entries 
    652          * </p> 
    653          */ 
    654         private ReadOnlyCollectionFacade(List<Map.Entry<ITaskInstance, V>> list, 
    655                                          EntryFacade<TYPE>                 entryFacade) 
    656         { 
    657             this.list = list; 
    658             this.entryFacade = entryFacade; 
    659         } 
    660  
    661         /* (non-Javadoc) 
    662          * @see java.util.Collection#size() 
    663          */ 
    664         @Override 
    665         public int size() { 
    666             return list.size(); 
    667         } 
    668  
    669         /* (non-Javadoc) 
    670          * @see java.util.Collection#isEmpty() 
    671          */ 
    672         @Override 
    673         public boolean isEmpty() { 
    674             return list.isEmpty(); 
    675         } 
    676  
    677         /* (non-Javadoc) 
    678          * @see java.util.Collection#contains(java.lang.Object) 
    679          */ 
    680         @Override 
    681         public boolean contains(Object o) { 
    682             if (o == null) { 
    683                 for (Map.Entry<ITaskInstance, V> entry : list) { 
    684                     if (entryFacade.getFacadedElement(entry) == null) { 
    685                         return true; 
    686                     } 
    687                 } 
    688             } 
    689             else { 
    690                 for (Map.Entry<ITaskInstance, V> entry : list) { 
    691                     if (o.equals(entryFacade.getFacadedElement(entry))) { 
    692                         return true; 
    693                     } 
    694                 } 
    695             } 
    696              
    697             return false; 
    698         } 
    699  
    700         /* (non-Javadoc) 
    701          * @see java.util.Collection#toArray() 
    702          */ 
    703         @Override 
    704         public Object[] toArray() { 
    705             Object[] result = new Object[list.size()]; 
    706              
    707             for (int i = 0; i < list.size(); i++) { 
    708                 result[i] = entryFacade.getFacadedElement(list.get(i)); 
    709             } 
    710              
    711             return result; 
    712         } 
    713  
    714         /* (non-Javadoc) 
    715          * @see java.util.Collection#toArray(T[]) 
    716          */ 
    717         @SuppressWarnings("unchecked") 
    718         @Override 
    719         public <T> T[] toArray(T[] a) { 
    720             T[] result = a; 
    721              
    722             for (int i = 0; i < list.size(); i++) { 
    723                 result[i] = (T) entryFacade.getFacadedElement(list.get(i)); 
    724             } 
    725              
    726             return result; 
    727         } 
    728  
    729         /* (non-Javadoc) 
    730          * @see java.util.Collection#add(java.lang.Object) 
    731          */ 
    732         @Override 
    733         public boolean add(TYPE e) { 
    734             throw new UnsupportedOperationException("this collection is read only"); 
    735         } 
    736  
    737         /* (non-Javadoc) 
    738          * @see java.util.Collection#remove(java.lang.Object) 
    739          */ 
    740         @Override 
    741         public boolean remove(Object o) { 
    742             throw new UnsupportedOperationException("this collection is read only"); 
    743         } 
    744  
    745         /* (non-Javadoc) 
    746          * @see java.util.Collection#containsAll(java.util.Collection) 
    747          */ 
    748         @Override 
    749         public boolean containsAll(Collection<?> c) { 
    750             for (Object candidate : c) { 
    751                 if (!contains(candidate)) { 
    752                     return false; 
    753                 } 
    754             } 
    755              
    756             return true; 
    757         } 
    758  
    759         /* (non-Javadoc) 
    760          * @see java.util.Collection#addAll(java.util.Collection) 
    761          */ 
    762         @Override 
    763         public boolean addAll(Collection<? extends TYPE> c) { 
    764             throw new UnsupportedOperationException("this collection is read only"); 
    765         } 
    766  
    767         /* (non-Javadoc) 
    768          * @see java.util.Collection#removeAll(java.util.Collection) 
    769          */ 
    770         @Override 
    771         public boolean removeAll(Collection<?> c) { 
    772             throw new UnsupportedOperationException("this collection is read only"); 
    773         } 
    774  
    775         /* (non-Javadoc) 
    776          * @see java.util.Collection#retainAll(java.util.Collection) 
    777          */ 
    778         @Override 
    779         public boolean retainAll(Collection<?> c) { 
    780             throw new UnsupportedOperationException("this collection is read only"); 
    781         } 
    782  
    783         /* (non-Javadoc) 
    784          * @see java.util.Collection#clear() 
    785          */ 
    786         @Override 
    787         public void clear() { 
    788             throw new UnsupportedOperationException("this collection is read only"); 
    789         } 
    790  
    791         /* (non-Javadoc) 
    792          * @see java.util.Collection#iterator() 
    793          */ 
    794         @Override 
    795         public Iterator<TYPE> iterator() { 
    796             return new ReadOnlyCollectionIteratorFacade<TYPE>(list.iterator(), entryFacade); 
    797         } 
    798          
    799     } 
    800  
    801     /** 
    802      * <p> 
    803      * Implementation of an iterator to facade an iterator on the internal list of task instance 
    804      * entries. 
    805      * </p> 
    806      *  
    807      * @author Patrick Harms 
    808      */ 
    809     private class ReadOnlyCollectionIteratorFacade<TYPE> implements Iterator<TYPE> { 
    810          
    811         /** 
    812          * the facaded iterator 
    813          */ 
    814         private Iterator<Map.Entry<ITaskInstance, V>> iterator; 
    815          
    816         /** 
    817          * the facade for the entries provided by the facaded iterator 
    818          */ 
    819         private EntryFacade<TYPE> entryFacade; 
    820          
    821         /** 
    822          * <p> 
    823          * initialized this facade with the facaded iterator and the entry facade to be used for 
    824          * the entries. 
    825          * </p> 
    826          */ 
    827         private ReadOnlyCollectionIteratorFacade(Iterator<Map.Entry<ITaskInstance, V>> iterator, 
    828                                                  EntryFacade<TYPE>                     entryFacade) 
    829         { 
    830             this.iterator = iterator; 
    831             this.entryFacade = entryFacade; 
    832         } 
    833  
    834         /* (non-Javadoc) 
    835          * @see java.util.Iterator#hasNext() 
    836          */ 
    837         @Override 
    838         public boolean hasNext() { 
    839             return iterator.hasNext(); 
    840         } 
    841  
    842         /* (non-Javadoc) 
    843          * @see java.util.Iterator#next() 
    844          */ 
    845         @Override 
    846         public TYPE next() { 
    847             return entryFacade.getFacadedElement(iterator.next()); 
    848         } 
    849  
    850         /* (non-Javadoc) 
    851          * @see java.util.Iterator#remove() 
    852          */ 
    853         @Override 
    854         public void remove() { 
    855             throw new UnsupportedOperationException("this iterator is read only"); 
    856         } 
    857          
    858     } 
    859          
    860     /** 
    861      * <p> 
    862      * Used to facade task instance entries and to return only this part of an entry, that is 
    863      * relevant. 
    864      * </p> 
    865      *  
    866      * @author Patrick Harms 
    867      */ 
    868     private abstract class EntryFacade<T> { 
    869          
    870         /** 
    871          * <p> 
    872          * Returns only the part of an entry that is relevant or required. 
    873          * </p> 
    874          * 
    875          * @param entry of which the part shall be returned 
    876          *  
    877          * @return the part of the entry to be returned 
    878          */ 
    879         protected abstract T getFacadedElement(Entry<ITaskInstance, V> entry); 
    880          
    881     } 
    882      
    883     /** 
    884      * <p> 
    885      * Implementation of the entry facade returning the entries key, i.e. the symbol. 
    886      * </p> 
    887      *  
    888      * @author Patrick Harms 
    889      */ 
    890     private class SymbolFacade extends EntryFacade<ITaskInstance> { 
    891  
    892         /* (non-Javadoc) 
    893          * @see ReadOnlyCollectionIteratorFacade#getFacadedElement(Entry) 
    894          */ 
    895         @Override 
    896         protected ITaskInstance getFacadedElement(Entry<ITaskInstance, V> entry) { 
    897             return entry.getKey(); 
    898         } 
    899     } 
    900      
    901     /** 
    902      * <p> 
    903      * Implementation of the entry facade returning the entries value, i.e. the value associated to 
    904      * the symbol. 
    905      * </p> 
    906      *  
    907      * @author Patrick Harms 
    908      */ 
    909     private class ValueFacade extends EntryFacade<V> { 
    910  
    911         /* (non-Javadoc) 
    912          * @see ReadOnlyCollectionIteratorFacade#getFacadedElement(Entry) 
    913          */ 
    914         @Override 
    915         protected V getFacadedElement(Entry<ITaskInstance, V> entry) { 
    916             return entry.getValue(); 
    917         } 
    918     } 
     61class TaskSymbolBucketedMap<V> implements SymbolMap<ITaskInstance, V>, 
     62                Serializable { 
     63 
     64        /** 
     65         * <p> 
     66         * Used to facade task instance entries and to return only this part of an 
     67         * entry, that is relevant. 
     68         * </p> 
     69         *  
     70         * @author Patrick Harms 
     71         */ 
     72        private abstract class EntryFacade<T> { 
     73 
     74                /** 
     75                 * <p> 
     76                 * Returns only the part of an entry that is relevant or required. 
     77                 * </p> 
     78                 * 
     79                 * @param entry 
     80                 *            of which the part shall be returned 
     81                 *  
     82                 * @return the part of the entry to be returned 
     83                 */ 
     84                protected abstract T getFacadedElement(Entry<ITaskInstance, V> entry); 
     85 
     86        } 
     87 
     88        /** 
     89         * <p> 
     90         * Used to create an efficient facade for accessing the internal list of 
     91         * entries either only for the task instances or only for the values. It is 
     92         * a default implementation of the collection interface. The entry facade 
     93         * provided to the constructor decides, if either the list accesses only the 
     94         * task instances or only the values. 
     95         * </p> 
     96         *  
     97         * @author Patrick Harms 
     98         */ 
     99        private class ReadOnlyCollectionFacade<TYPE> implements Collection<TYPE> { 
     100 
     101                /** 
     102                 * the list facaded by this facade 
     103                 */ 
     104                private final List<Map.Entry<ITaskInstance, V>> list; 
     105 
     106                /** 
     107                 * the facade to be used for the entries 
     108                 */ 
     109                private final EntryFacade<TYPE> entryFacade; 
     110 
     111                /** 
     112                 * <p> 
     113                 * Initializes the facade with the facaded list and the facade to be 
     114                 * used for the entries 
     115                 * </p> 
     116                 */ 
     117                private ReadOnlyCollectionFacade( 
     118                                List<Map.Entry<ITaskInstance, V>> list, 
     119                                EntryFacade<TYPE> entryFacade) { 
     120                        this.list = list; 
     121                        this.entryFacade = entryFacade; 
     122                } 
     123 
     124                /* 
     125                 * (non-Javadoc) 
     126                 *  
     127                 * @see java.util.Collection#add(java.lang.Object) 
     128                 */ 
     129                @Override 
     130                public boolean add(TYPE e) { 
     131                        throw new UnsupportedOperationException( 
     132                                        "this collection is read only"); 
     133                } 
     134 
     135                /* 
     136                 * (non-Javadoc) 
     137                 *  
     138                 * @see java.util.Collection#addAll(java.util.Collection) 
     139                 */ 
     140                @Override 
     141                public boolean addAll(Collection<? extends TYPE> c) { 
     142                        throw new UnsupportedOperationException( 
     143                                        "this collection is read only"); 
     144                } 
     145 
     146                /* 
     147                 * (non-Javadoc) 
     148                 *  
     149                 * @see java.util.Collection#clear() 
     150                 */ 
     151                @Override 
     152                public void clear() { 
     153                        throw new UnsupportedOperationException( 
     154                                        "this collection is read only"); 
     155                } 
     156 
     157                /* 
     158                 * (non-Javadoc) 
     159                 *  
     160                 * @see java.util.Collection#contains(java.lang.Object) 
     161                 */ 
     162                @Override 
     163                public boolean contains(Object o) { 
     164                        if (o == null) { 
     165                                for (final Map.Entry<ITaskInstance, V> entry : list) { 
     166                                        if (entryFacade.getFacadedElement(entry) == null) { 
     167                                                return true; 
     168                                        } 
     169                                } 
     170                        } else { 
     171                                for (final Map.Entry<ITaskInstance, V> entry : list) { 
     172                                        if (o.equals(entryFacade.getFacadedElement(entry))) { 
     173                                                return true; 
     174                                        } 
     175                                } 
     176                        } 
     177 
     178                        return false; 
     179                } 
     180 
     181                /* 
     182                 * (non-Javadoc) 
     183                 *  
     184                 * @see java.util.Collection#containsAll(java.util.Collection) 
     185                 */ 
     186                @Override 
     187                public boolean containsAll(Collection<?> c) { 
     188                        for (final Object candidate : c) { 
     189                                if (!contains(candidate)) { 
     190                                        return false; 
     191                                } 
     192                        } 
     193 
     194                        return true; 
     195                } 
     196 
     197                /* 
     198                 * (non-Javadoc) 
     199                 *  
     200                 * @see java.util.Collection#isEmpty() 
     201                 */ 
     202                @Override 
     203                public boolean isEmpty() { 
     204                        return list.isEmpty(); 
     205                } 
     206 
     207                /* 
     208                 * (non-Javadoc) 
     209                 *  
     210                 * @see java.util.Collection#iterator() 
     211                 */ 
     212                @Override 
     213                public Iterator<TYPE> iterator() { 
     214                        return new ReadOnlyCollectionIteratorFacade<TYPE>(list.iterator(), 
     215                                        entryFacade); 
     216                } 
     217 
     218                /* 
     219                 * (non-Javadoc) 
     220                 *  
     221                 * @see java.util.Collection#remove(java.lang.Object) 
     222                 */ 
     223                @Override 
     224                public boolean remove(Object o) { 
     225                        throw new UnsupportedOperationException( 
     226                                        "this collection is read only"); 
     227                } 
     228 
     229                /* 
     230                 * (non-Javadoc) 
     231                 *  
     232                 * @see java.util.Collection#removeAll(java.util.Collection) 
     233                 */ 
     234                @Override 
     235                public boolean removeAll(Collection<?> c) { 
     236                        throw new UnsupportedOperationException( 
     237                                        "this collection is read only"); 
     238                } 
     239 
     240                /* 
     241                 * (non-Javadoc) 
     242                 *  
     243                 * @see java.util.Collection#retainAll(java.util.Collection) 
     244                 */ 
     245                @Override 
     246                public boolean retainAll(Collection<?> c) { 
     247                        throw new UnsupportedOperationException( 
     248                                        "this collection is read only"); 
     249                } 
     250 
     251                /* 
     252                 * (non-Javadoc) 
     253                 *  
     254                 * @see java.util.Collection#size() 
     255                 */ 
     256                @Override 
     257                public int size() { 
     258                        return list.size(); 
     259                } 
     260 
     261                /* 
     262                 * (non-Javadoc) 
     263                 *  
     264                 * @see java.util.Collection#toArray() 
     265                 */ 
     266                @Override 
     267                public Object[] toArray() { 
     268                        final Object[] result = new Object[list.size()]; 
     269 
     270                        for (int i = 0; i < list.size(); i++) { 
     271                                result[i] = entryFacade.getFacadedElement(list.get(i)); 
     272                        } 
     273 
     274                        return result; 
     275                } 
     276 
     277                /* 
     278                 * (non-Javadoc) 
     279                 *  
     280                 * @see java.util.Collection#toArray(T[]) 
     281                 */ 
     282                @SuppressWarnings("unchecked") 
     283                @Override 
     284                public <T> T[] toArray(T[] a) { 
     285                        final T[] result = a; 
     286 
     287                        for (int i = 0; i < list.size(); i++) { 
     288                                result[i] = (T) entryFacade.getFacadedElement(list.get(i)); 
     289                        } 
     290 
     291                        return result; 
     292                } 
     293 
     294        } 
     295 
     296        /** 
     297         * <p> 
     298         * Implementation of an iterator to facade an iterator on the internal list 
     299         * of task instance entries. 
     300         * </p> 
     301         *  
     302         * @author Patrick Harms 
     303         */ 
     304        private class ReadOnlyCollectionIteratorFacade<TYPE> implements 
     305                        Iterator<TYPE> { 
     306 
     307                /** 
     308                 * the facaded iterator 
     309                 */ 
     310                private final Iterator<Map.Entry<ITaskInstance, V>> iterator; 
     311 
     312                /** 
     313                 * the facade for the entries provided by the facaded iterator 
     314                 */ 
     315                private final EntryFacade<TYPE> entryFacade; 
     316 
     317                /** 
     318                 * <p> 
     319                 * initialized this facade with the facaded iterator and the entry 
     320                 * facade to be used for the entries. 
     321                 * </p> 
     322                 */ 
     323                private ReadOnlyCollectionIteratorFacade( 
     324                                Iterator<Map.Entry<ITaskInstance, V>> iterator, 
     325                                EntryFacade<TYPE> entryFacade) { 
     326                        this.iterator = iterator; 
     327                        this.entryFacade = entryFacade; 
     328                } 
     329 
     330                /* 
     331                 * (non-Javadoc) 
     332                 *  
     333                 * @see java.util.Iterator#hasNext() 
     334                 */ 
     335                @Override 
     336                public boolean hasNext() { 
     337                        return iterator.hasNext(); 
     338                } 
     339 
     340                /* 
     341                 * (non-Javadoc) 
     342                 *  
     343                 * @see java.util.Iterator#next() 
     344                 */ 
     345                @Override 
     346                public TYPE next() { 
     347                        return entryFacade.getFacadedElement(iterator.next()); 
     348                } 
     349 
     350                /* 
     351                 * (non-Javadoc) 
     352                 *  
     353                 * @see java.util.Iterator#remove() 
     354                 */ 
     355                @Override 
     356                public void remove() { 
     357                        throw new UnsupportedOperationException( 
     358                                        "this iterator is read only"); 
     359                } 
     360 
     361        } 
     362 
     363        /** 
     364         * <p> 
     365         * Implementation of the entry facade returning the entries key, i.e. the 
     366         * symbol. 
     367         * </p> 
     368         *  
     369         * @author Patrick Harms 
     370         */ 
     371        private class SymbolFacade extends EntryFacade<ITaskInstance> { 
     372 
     373                /* 
     374                 * (non-Javadoc) 
     375                 *  
     376                 * @see ReadOnlyCollectionIteratorFacade#getFacadedElement(Entry) 
     377                 */ 
     378                @Override 
     379                protected ITaskInstance getFacadedElement(Entry<ITaskInstance, V> entry) { 
     380                        return entry.getKey(); 
     381                } 
     382        } 
     383 
     384        /** 
     385         * <p> 
     386         * Internally used data structure for storing task instance - value pairs 
     387         * </p> 
     388         *  
     389         * @author Patrick Harms 
     390         */ 
     391        private class SymbolMapEntry implements Map.Entry<ITaskInstance, V> { 
     392 
     393                /** 
     394                 * the task instance to map to a value 
     395                 */ 
     396                private final ITaskInstance symbol; 
     397 
     398                /** 
     399                 * the value associated with the symbol 
     400                 */ 
     401                private V value; 
     402 
     403                /** 
     404                 * <p> 
     405                 * Simple constructor for initializing the entry with a task instance 
     406                 * and its associated value. 
     407                 * </p> 
     408                 */ 
     409                private SymbolMapEntry(ITaskInstance symbol, V value) { 
     410                        super(); 
     411                        this.symbol = symbol; 
     412                        this.value = value; 
     413                } 
     414 
     415                /* 
     416                 * (non-Javadoc) 
     417                 *  
     418                 * @see java.lang.Object#equals(java.lang.Object) 
     419                 */ 
     420                @SuppressWarnings("unchecked") 
     421                @Override 
     422                public boolean equals(Object obj) { 
     423                        if (this == obj) { 
     424                                return true; 
     425                        } else if (this.getClass().isInstance(obj)) { 
     426                                final SymbolMapEntry other = (SymbolMapEntry) obj; 
     427                                return (symbol.equals(other.symbol) && (value == null ? other.value == null 
     428                                                : value.equals(other.value))); 
     429                        } else { 
     430                                return false; 
     431                        } 
     432                } 
     433 
     434                /* 
     435                 * (non-Javadoc) 
     436                 *  
     437                 * @see java.util.Map.Entry#getKey() 
     438                 */ 
     439                @Override 
     440                public ITaskInstance getKey() { 
     441                        return symbol; 
     442                } 
     443 
     444                /* 
     445                 * (non-Javadoc) 
     446                 *  
     447                 * @see java.util.Map.Entry#getValue() 
     448                 */ 
     449                @Override 
     450                public V getValue() { 
     451                        return value; 
     452                } 
     453 
     454                /* 
     455                 * (non-Javadoc) 
     456                 *  
     457                 * @see java.lang.Object#hashCode() 
     458                 */ 
     459                @Override 
     460                public int hashCode() { 
     461                        return symbol.hashCode(); 
     462                } 
     463 
     464                /* 
     465                 * (non-Javadoc) 
     466                 *  
     467                 * @see java.util.Map.Entry#setValue(java.lang.Object) 
     468                 */ 
     469                @Override 
     470                public V setValue(V value) { 
     471                        final V oldValue = this.value; 
     472                        this.value = value; 
     473                        return oldValue; 
     474                } 
     475 
     476                /* 
     477                 * (non-Javadoc) 
     478                 *  
     479                 * @see java.lang.Object#toString() 
     480                 */ 
     481                @Override 
     482                public String toString() { 
     483                        return symbol + "=" + value; 
     484                } 
     485 
     486        } 
     487 
     488        /** 
     489         * <p> 
     490         * Implementation of the entry facade returning the entries value, i.e. the 
     491         * value associated to the symbol. 
     492         * </p> 
     493         *  
     494         * @author Patrick Harms 
     495         */ 
     496        private class ValueFacade extends EntryFacade<V> { 
     497 
     498                /* 
     499                 * (non-Javadoc) 
     500                 *  
     501                 * @see ReadOnlyCollectionIteratorFacade#getFacadedElement(Entry) 
     502                 */ 
     503                @Override 
     504                protected V getFacadedElement(Entry<ITaskInstance, V> entry) { 
     505                        return entry.getValue(); 
     506                } 
     507        } 
     508 
     509        /** 
     510         * <p> 
     511         * default serial version UID 
     512         * </p> 
     513         */ 
     514        private static final long serialVersionUID = 1L; 
     515 
     516        /** 
     517         * <p> 
     518         * the maximum number of task instances in this map which is still only 
     519         * treated as list instead of using buckets. 
     520         * </p> 
     521         */ 
     522        private static final int MAX_LIST_SIZE = 15; 
     523 
     524        /** 
     525         * <p> 
     526         * Comparator to be used for comparing the task instances with each other 
     527         * </p> 
     528         */ 
     529        private final TaskInstanceComparator comparator; 
     530 
     531        /** 
     532         * <p> 
     533         * Internally maintained plain list of task instances and associated values 
     534         * </p> 
     535         */ 
     536        private final List<Map.Entry<ITaskInstance, V>> symbolList; 
     537 
     538        /** 
     539         * <p> 
     540         * If the size of the map exceeds {@link #MAX_LIST_SIZE}, this is the index 
     541         * using buckets for optimizing the search order. 
     542         * </p> 
     543         */ 
     544        private Map<Integer, List<Map.Entry<ITaskInstance, V>>> symbolBuckets; 
     545 
     546        /** 
     547         * <p> 
     548         * When using buckets, not any task instance may be associated a correct 
     549         * bucket. Therefore, we set a default bucket for all such task instances. 
     550         * This may change if the same bucket for a specific symbol is selected. 
     551         * </p> 
     552         */ 
     553        private int defaultBucket = 0; 
     554 
     555        /** 
     556         * <p> 
     557         * Instantiates a task instance map with a comparator 
     558         * </p> 
     559         * 
     560         * @param comparator 
     561         *            the comparator to use for comparing task instances 
     562         *  
     563         * @throws IllegalArgumentException 
     564         *             if the provided comparator is null 
     565         */ 
     566        public TaskSymbolBucketedMap(TaskInstanceComparator comparator) { 
     567                if (comparator == null) { 
     568                        throw new IllegalArgumentException("comparator must not be null"); 
     569                } 
     570 
     571                this.comparator = comparator; 
     572                this.symbolList = new ArrayList<Map.Entry<ITaskInstance, V>>(); 
     573        } 
     574 
     575        /** 
     576         * <p> 
     577         * Copy constructor 
     578         * </p> 
     579         *  
     580         * @param otherMap 
     581         *            the other map to be copied including its comparator 
     582         *  
     583         * @throws IllegalArgumentException 
     584         *             if the provided other map is null 
     585         */ 
     586        public TaskSymbolBucketedMap(TaskSymbolBucketedMap<V> otherMap) { 
     587                if (otherMap == null) { 
     588                        throw new IllegalArgumentException("otherMap must not be null"); 
     589                } 
     590 
     591                this.comparator = otherMap.comparator; 
     592                this.symbolList = new ArrayList<Map.Entry<ITaskInstance, V>>( 
     593                                otherMap.symbolList); 
     594 
     595                if (this.symbolList.size() > MAX_LIST_SIZE) { 
     596                        createSymbolBuckets(); 
     597                } 
     598        } 
     599 
     600        /** 
     601         * <p> 
     602         * Adds a task instance and an associated value to the map. If the value is 
     603         * null, the task instance is added, anyway and 
     604         * {@link #containsSymbol(Object)} will return true for that task instance. 
     605         * Adding the same task instance twice will produce two entries. This is 
     606         * contradictory to typical map implementations. To prevent this, the 
     607         * {@link #containsSymbol(Object)} and {@link #removeSymbol(Object)} methods 
     608         * should be used to ensure map behavior. 
     609         * </p> 
     610         *  
     611         * @param symbol 
     612         *            the task instance to add to the map 
     613         * @param value 
     614         *            the value to associate to the task instance in this map 
     615         *  
     616         * @return as described 
     617         *  
     618         * @throws IllegalArgumentException 
     619         *             if the provided task instance is null 
     620         */ 
     621        @Override 
     622        public void addSymbol(ITaskInstance symbol, V value) { 
     623                if (symbol == null) { 
     624                        throw new IllegalArgumentException("symbol must not be null"); 
     625                } 
     626 
     627                final Map.Entry<ITaskInstance, V> entry = new SymbolMapEntry(symbol, 
     628                                value); 
     629 
     630                symbolList.add(entry); 
     631 
     632                if (symbolList.size() > MAX_LIST_SIZE) { 
     633                        if (symbolBuckets == null) { 
     634                                createSymbolBuckets(); 
     635                        } else { 
     636                                addToSymbolBucket(entry); 
     637                        } 
     638                } 
     639        } 
     640 
     641        /** 
     642         * <p> 
     643         * Adds a task instance and its value to its corresponding bucket. The 
     644         * corresponding bucket is the first element of the array returned by the 
     645         * method {@link #getBucketSearchOrder(ITaskInstance)}. If no search order 
     646         * for a task instance is defined, the entry is added to the default bucket. 
     647         * If the bucket id identical to the default bucket id, the default bucket 
     648         * id is shifted to another value. 
     649         * </p> 
     650         */ 
     651        private void addToSymbolBucket(Map.Entry<ITaskInstance, V> symbolEntry) { 
     652                int bucketId = defaultBucket; 
     653                final int[] bucketSearchOrder = getBucketSearchOrder(symbolEntry 
     654                                .getKey()); 
     655 
     656                if ((bucketSearchOrder != null) && (bucketSearchOrder.length > 0)) { 
     657                        bucketId = bucketSearchOrder[0]; 
     658 
     659                        if (bucketId == defaultBucket) { 
     660                                setNewDefaultBucketId(); 
     661                        } 
     662                } 
     663 
     664                List<Map.Entry<ITaskInstance, V>> list = symbolBuckets.get(bucketId); 
     665 
     666                if (list == null) { 
     667                        list = new LinkedList<Map.Entry<ITaskInstance, V>>(); 
     668                        symbolBuckets.put(bucketId, list); 
     669                } 
     670 
     671                list.add(symbolEntry); 
     672        } 
     673 
     674        /** 
     675         * <p> 
     676         * Removes all task instances and associated values from the map. 
     677         * </p> 
     678         */ 
     679        @Override 
     680        public void clear() { 
     681                symbolList.clear(); 
     682                symbolBuckets = null; 
     683        } 
     684 
     685        /** 
     686         * <p> 
     687         * Returns true if the provided task instance was stored in this map. 
     688         * </p> 
     689         *  
     690         * @param symbol 
     691         *            the task instance to check if it was stored in this map 
     692         *  
     693         * @return as described 
     694         *  
     695         * @throws IllegalArgumentException 
     696         *             if the provided task instance is null 
     697         */ 
     698        @Override 
     699        public boolean containsSymbol(ITaskInstance symbol) { 
     700                if (symbol == null) { 
     701                        throw new IllegalArgumentException("symbol must not be null"); 
     702                } 
     703 
     704                return getEntry(symbol) != null; 
     705        } 
     706 
     707        /** 
     708         * <p> 
     709         * Internally used to create task instance buckets in case the number of 
     710         * stored task instances increased above {@link #MAX_LIST_SIZE}. 
     711         * </p> 
     712         */ 
     713        private void createSymbolBuckets() { 
     714                // System.out.println("creating symbol buckets"); 
     715                symbolBuckets = new HashMap<Integer, List<Map.Entry<ITaskInstance, V>>>(); 
     716 
     717                for (final Map.Entry<ITaskInstance, V> symbol : symbolList) { 
     718                        addToSymbolBucket(symbol); 
     719                } 
     720        } 
     721 
     722        /* 
     723         * (non-Javadoc) 
     724         *  
     725         * @see java.lang.Object#equals(java.lang.Object) 
     726         */ 
     727        @SuppressWarnings("unchecked") 
     728        @Override 
     729        public boolean equals(Object obj) { 
     730                if (this == obj) { 
     731                        return true; 
     732                } else if (this.getClass().isInstance(obj)) { 
     733                        final TaskSymbolBucketedMap<V> other = (TaskSymbolBucketedMap<V>) obj; 
     734 
     735                        return (symbolList.size() == other.symbolList.size()) 
     736                                        && (symbolList.containsAll(other.symbolList)); 
     737                } else { 
     738                        return false; 
     739                } 
     740        } 
     741 
     742        /** 
     743         * <p> 
     744         * returns the search order for a task instance which is different for event 
     745         * task instances, sequence instances, selection instances, and iteration 
     746         * instances 
     747         * </p> 
     748         */ 
     749        private int[] getBucketSearchOrder(ITaskInstance taskInstance) { 
     750                // 0 = sequence; 1 = selection; 2 = iteration; 3 = optional; 4 = event 
     751                // task in general; 
     752                // other = hashCode of name of event type 
     753 
     754                if (taskInstance instanceof IEventTaskInstance) { 
     755                        // event tasks are most likely equal to those of the same type 
     756                        // happening on the same 
     757                        // target. Afterwards, they should be equal to those of the event 
     758                        // type with the same 
     759                        // name. Afterwards, they may be equal to iterations, optionals, 
     760                        // other event tasks, 
     761                        // selections, and finally the rest. 
     762                        final Event event = ((IEventTaskInstance) taskInstance).getEvent(); 
     763                        return new int[] { 
     764                                        event.getTarget().hashCode() 
     765                                                        + event.getType().getName().hashCode(), 
     766                                        event.getType().getName().hashCode(), 2, 3, 4, 1 }; 
     767                } else if (taskInstance instanceof ISequenceInstance) { 
     768                        return new int[] { 0, 2, 3, 1 }; 
     769                } else if (taskInstance instanceof ISelectionInstance) { 
     770                        return new int[] { 1, 4, 2, 3 }; 
     771                } else if (taskInstance instanceof IIterationInstance) { 
     772                        return new int[] { 2, 1, 4 }; 
     773                } 
     774 
     775                return null; 
     776        } 
     777 
     778        /** 
     779         * <p> 
     780         * searches for the entry belonging to the given task instance. The method 
     781         * either uses the list if buckets are not used yet, or it uses the buckets 
     782         * and searches them in the order defined by the method 
     783         * {@link #getBucketSearchOrder(ITaskInstance)}. If the task instances isn't 
     784         * found and the bucket search order does not refer all buckets, then also 
     785         * the other buckets are searched for the task instance. 
     786         * </p> 
     787         */ 
     788        private Map.Entry<ITaskInstance, V> getEntry(ITaskInstance symbol) { 
     789                Map.Entry<ITaskInstance, V> entry = null; 
     790                if (symbolBuckets == null) { 
     791                        entry = lookup(symbol, symbolList); 
     792                } else { 
     793                        final int[] bucketSearchOrder = getBucketSearchOrder(symbol); 
     794                        for (final int bucketId : bucketSearchOrder) { 
     795                                final List<Map.Entry<ITaskInstance, V>> list = symbolBuckets 
     796                                                .get(bucketId); 
     797                                if (list != null) { 
     798                                        entry = lookup(symbol, list); 
     799                                        if (entry != null) { 
     800                                                break; 
     801                                        } 
     802                                } 
     803                        } 
     804 
     805                        // try to search the other buckets 
     806                        if (entry == null) { 
     807                                Arrays.sort(bucketSearchOrder); 
     808                                for (final Map.Entry<Integer, List<Map.Entry<ITaskInstance, V>>> bucket : symbolBuckets 
     809                                                .entrySet()) { 
     810                                        if (Arrays.binarySearch(bucketSearchOrder, bucket.getKey()) < 0) { 
     811                                                final List<Map.Entry<ITaskInstance, V>> list = bucket 
     812                                                                .getValue(); 
     813                                                if (list != null) { 
     814                                                        entry = lookup(symbol, list); 
     815                                                        if (entry != null) { 
     816                                                                break; 
     817                                                        } 
     818                                                } 
     819                                        } 
     820                                } 
     821                        } 
     822                } 
     823 
     824                return entry; 
     825        } 
     826 
     827        /** 
     828         * <p> 
     829         * Returns a collection of all task instances in this map. 
     830         * </p> 
     831         * 
     832         * @return as described 
     833         */ 
     834        @Override 
     835        public Collection<ITaskInstance> getSymbols() { 
     836                return new ReadOnlyCollectionFacade<ITaskInstance>(symbolList, 
     837                                new SymbolFacade()); 
     838        } 
     839 
     840        /** 
     841         * <p> 
     842         * Returns the value associated to the provided task instance in this map. 
     843         * If there is no value associated to the given task instance or if the task 
     844         * instance is not stored in this map, the method returns null. 
     845         * </p> 
     846         *  
     847         * @param symbol 
     848         *            the task instance to return the value for 
     849         *  
     850         * @return as described 
     851         *  
     852         * @throws IllegalArgumentException 
     853         *             if the provided task instance is null 
     854         */ 
     855        @Override 
     856        public V getValue(ITaskInstance symbol) { 
     857                if (symbol == null) { 
     858                        throw new IllegalArgumentException("symbol must not be null"); 
     859                } 
     860 
     861                final Map.Entry<ITaskInstance, V> entry = getEntry(symbol); 
     862 
     863                if (entry != null) { 
     864                        return entry.getValue(); 
     865                } else { 
     866                        return null; 
     867                } 
     868        } 
     869 
     870        /** 
     871         * <p> 
     872         * Returns a collection of all values associated to task instances in this 
     873         * map. May contain null values, if some of the task instances are mapped to 
     874         * null. The length of the returned collection is in any case the same as 
     875         * the size of the map. 
     876         * </p> 
     877         * 
     878         * @return as described 
     879         */ 
     880        @Override 
     881        public Collection<V> getValues() { 
     882                return new ReadOnlyCollectionFacade<V>(symbolList, new ValueFacade()); 
     883        } 
     884 
     885        /* 
     886         * (non-Javadoc) 
     887         *  
     888         * @see java.lang.Object#hashCode() 
     889         */ 
     890        @Override 
     891        public int hashCode() { 
     892                return symbolList.size(); 
     893        } 
     894 
     895        /** 
     896         * <p> 
     897         * Returns true if this map is empty, i.e. if {@link #size()} returns 0 
     898         * </p> 
     899         *  
     900         * @return as described 
     901         */ 
     902        @Override 
     903        public boolean isEmpty() { 
     904                return symbolList.isEmpty(); 
     905        } 
     906 
     907        /** 
     908         * <p> 
     909         * Convenience method to look up a symbol in a list of entries using the 
     910         * comparator. 
     911         * </p> 
     912         */ 
     913        private Map.Entry<ITaskInstance, V> lookup(ITaskInstance symbol, 
     914                        List<Map.Entry<ITaskInstance, V>> list) { 
     915                for (final Map.Entry<ITaskInstance, V> candidate : list) { 
     916                        if (comparator.equals(candidate.getKey(), symbol)) { 
     917                                return candidate; 
     918                        } 
     919                } 
     920 
     921                return null; 
     922        } 
     923 
     924        /** 
     925         * <p> 
     926         * Removes the entry for a given task instance from the buckets. It uses the 
     927         * bucket search order defined to find the task instance as fast as 
     928         * possible. 
     929         * </p> 
     930         */ 
     931        private Map.Entry<ITaskInstance, V> removeFromSymbolBuckets( 
     932                        ITaskInstance symbol) { 
     933                int bucketId = defaultBucket; 
     934                final int[] bucketSearchOrder = getBucketSearchOrder(symbol); 
     935 
     936                if ((bucketSearchOrder != null) && (bucketSearchOrder.length > 0)) { 
     937                        bucketId = bucketSearchOrder[0]; 
     938                } 
     939 
     940                final List<Map.Entry<ITaskInstance, V>> list = symbolBuckets 
     941                                .get(bucketId); 
     942                Map.Entry<ITaskInstance, V> result = null; 
     943 
     944                if (list != null) { 
     945                        for (int i = 0; i < list.size(); i++) { 
     946                                if (comparator.equals(list.get(i).getKey(), symbol)) { 
     947                                        result = list.remove(i); 
     948                                        break; 
     949                                } 
     950                        } 
     951 
     952                        if (list.isEmpty()) { 
     953                                symbolBuckets.remove(bucketId); 
     954                        } 
     955                } 
     956 
     957                return result; 
     958        } 
     959 
     960        /** 
     961         * <p> 
     962         * Removes a task instance and its associated value from the map. If the 
     963         * task instance is stored several times, only the first of its occurrences 
     964         * is removed. 
     965         * </p> 
     966         *  
     967         * @param symbol 
     968         *            the task instance to be removed from the map 
     969         *  
     970         * @return as described 
     971         *  
     972         * @throws IllegalArgumentException 
     973         *             if the provided task instance is null 
     974         */ 
     975        @Override 
     976        public V removeSymbol(ITaskInstance symbol) { 
     977                if (symbol == null) { 
     978                        throw new IllegalArgumentException("symbol must not be null"); 
     979                } 
     980 
     981                for (int i = 0; i < symbolList.size(); i++) { 
     982                        if (comparator.equals(symbolList.get(i).getKey(), symbol)) { 
     983                                // found the symbol. Remove it from the list, and if required, 
     984                                // also from the map. 
     985                                final V value = symbolList.remove(i).getValue(); 
     986 
     987                                if (symbolList.size() > MAX_LIST_SIZE) { 
     988                                        removeFromSymbolBuckets(symbol); 
     989                                } 
     990 
     991                                return value; 
     992                        } 
     993                } 
     994 
     995                return null; 
     996        } 
     997 
     998        /** 
     999         * <p> 
     1000         * Updates the default bucket id to a new one 
     1001         * </p> 
     1002         */ 
     1003        private void setNewDefaultBucketId() { 
     1004                final int oldDefaultBucket = defaultBucket; 
     1005                do { 
     1006                        defaultBucket += 1; 
     1007                } while (symbolBuckets.containsKey(defaultBucket)); 
     1008 
     1009                symbolBuckets 
     1010                                .put(defaultBucket, symbolBuckets.remove(oldDefaultBucket)); 
     1011        } 
     1012 
     1013        /** 
     1014         * <p> 
     1015         * Returns the size of the map, i.e. the number of task instance entries 
     1016         * </p> 
     1017         *  
     1018         * @return as described 
     1019         */ 
     1020        @Override 
     1021        public int size() { 
     1022                return symbolList.size(); 
     1023        } 
    9191024 
    9201025} 
Note: See TracChangeset for help on using the changeset viewer.