Ignore:
Timestamp:
07/30/13 09:38:43 (11 years ago)
Author:
pharms
Message:
  • added support for symbol management strategy in tries, especially for storing them
  • adapted comparator approach accordingly
  • provided default implementation for symbol management strategies
  • added, extended and improved java doc
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/SymbolMap.java

    r1257 r1282  
    1616 
    1717import java.io.Serializable; 
    18 import java.util.ArrayList; 
    19 import java.util.Arrays; 
    2018import java.util.Collection; 
    21 import java.util.HashMap; 
    22 import java.util.Iterator; 
    23 import java.util.LinkedList; 
    24 import java.util.List; 
    25 import java.util.Map; 
    26 import java.util.Map.Entry; 
    2719 
    2820/** 
    2921 * <p> 
    30  * This class is a data structure for holding symbols which is more efficient than a simple list. 
    31  * This data structure can be used with a comparator to adapt the effective list behavior and to 
    32  * define the equals strategy for comparing objects. After a certain size ({@link #MAX_LIST_SIZE}), 
    33  * the symbol map creates a symbol index consisting of buckets. This allows searching for symbols 
    34  * in a more efficient order as the search can start in the most appropriate of the internal 
    35  * buckets. 
     22 * This interface defines a data structure for holding symbols. Its implementations can be used to 
     23 * improve the performance of a trie by tuning its internal symbol storage management. 
    3624 * </p> 
    3725 * <p> 
    38  * The class is called a map, although it is not. It may contain the same element as separate keys. 
    39  * This implementation is done for performance improvements. If it is required to really assure, 
    40  * that a key exists only once, then each call to the {@link #addSymbol(Object, Object)} method 
    41  * should be done only, if the {@link #containsSymbol(Object)} method for the same symbol returns 
    42  * false. 
     26 * The interface is called a map, although it is not necessarily. It may contain the same element 
     27 * as separate keys. This is allowed for performance improvements. If it is required to really 
     28 * assure, that a key exists only once, then each call to the {@link #addSymbol(Object, Object)} 
     29 * method should be done only, if the {@link #containsSymbol(Object)} method for the same symbol 
     30 * returns false. 
     31 * </p> 
     32 * <p> 
     33 * Mapping a symbol to the value null is possible. In this case {@link #getValue(Object)} returns 
     34 * null for the symbol. But {@link #containsSymbol(Object)} returns true. 
    4335 * </p> 
    4436 *  
    45  * @see SymbolComparator 
     37 * @author Patrick Harms 
    4638 *  
    47  * @author Patrick Harms 
     39 * @param <T> 
     40 *            Type of the symbols that are stored 
     41 * @param <V> 
     42 *            Type of the values associated with the symbols 
     43 *             
     44 * @see SymbolStrategy 
    4845 */ 
    49 public class SymbolMap<K, V> implements Serializable { 
    50  
    51     /** 
    52      * <p> 
    53      * default serial version UID 
    54      * </p> 
    55      */ 
    56     private static final long serialVersionUID = 1L; 
    57  
    58     /** 
    59      * <p> 
    60      * the maximum number of symbols in this map which is still only treated as list instead of 
    61      * using buckets. 
    62      * </p> 
    63      */ 
    64     private static final int MAX_LIST_SIZE = 15; 
    65      
    66     /** 
    67      * <p> 
    68      * Comparator to be used for comparing the symbols with each other and to determine a bucket 
    69      * search order 
    70      * </p> 
    71      */ 
    72     private SymbolComparator<K> comparator; 
    73  
    74     /** 
    75      * <p> 
    76      * Internally maintained plain list of symbols and associated values 
    77      * </p> 
    78      */ 
    79     private List<Map.Entry<K, V>> symbolList; 
    80  
    81     /** 
    82      * <p> 
    83      * If the size of the map exceeds {@link #MAX_LIST_SIZE}, this is the symbol index using buckets 
    84      * for optimizing the search order. 
    85      * </p> 
    86      */ 
    87     private Map<Integer, List<Map.Entry<K, V>>> symbolBuckets; 
    88      
    89     /** 
    90      * <p> 
    91      * When using buckets, not any symbol may be associated a correct bucket by the used 
    92      * comparator. Therefore, we set a default bucket for all such symbols. This may change 
    93      * if the comparator defines the same bucket for a specific symbol. 
    94      * </p> 
    95      */ 
    96     private int defaultBucket = 0; 
    97      
    98     /** 
    99      * <p> 
    100      * Instantiates a symbol map with a comparator 
    101      * </p> 
    102      * 
    103      * @param comparator the comparator to use for comparing symbols and for determining bucket 
    104      *                   search orders 
    105      *  
    106      * @throws IllegalArgumentException if the provided comparator is null 
    107      */ 
    108     public SymbolMap(SymbolComparator<K> comparator) { 
    109         if (comparator == null) { 
    110             throw new IllegalArgumentException("comparator must not be null"); 
    111         } 
    112          
    113         this.comparator = comparator; 
    114         this.symbolList = new ArrayList<Map.Entry<K, V>>(); 
    115     } 
    116  
    117     /** 
    118      * <p> 
    119      * Copy constructure 
    120      * </p> 
    121      *  
    122      * @param otherMap the other map to be copied including its comparator 
    123      *  
    124      * @throws IllegalArgumentException if the provided other map is null 
    125      */ 
    126     public SymbolMap(SymbolMap<K, V> otherMap) { 
    127         if (otherMap == null) { 
    128             throw new IllegalArgumentException("otherMap must not be null"); 
    129         } 
    130  
    131         this.comparator = otherMap.comparator; 
    132         this.symbolList = new ArrayList<Map.Entry<K, V>>(otherMap.symbolList); 
    133          
    134         if (this.symbolList.size() > MAX_LIST_SIZE) { 
    135             createSymbolBuckets(); 
    136         } 
    137     } 
     46public interface SymbolMap<K, V> extends Serializable { 
    13847 
    13948    /** 
    … …  
    14453     * @return as described 
    14554     */ 
    146     public int size() { 
    147         return symbolList.size(); 
    148     } 
     55    public int size(); 
    14956 
    15057    /** 
    … …  
    15562     * @return as described 
    15663     */ 
    157     public boolean isEmpty() { 
    158         return symbolList.isEmpty(); 
    159     } 
     64    public boolean isEmpty(); 
    16065 
    16166    /** 
    … …  
    17075     * @throws IllegalArgumentException if the provided symbol is null 
    17176     */ 
    172     public boolean containsSymbol(K symbol) { 
    173         if (symbol == null) { 
    174             throw new IllegalArgumentException("symbol must not be null"); 
    175         } 
    176          
    177         return getEntry(symbol) != null; 
    178     } 
     77    public boolean containsSymbol(K symbol); 
    17978 
    18079    /** 
    … …  
    19190     * @throws IllegalArgumentException if the provided symbol is null 
    19291     */ 
    193     public V getValue(K symbol) { 
    194         if (symbol == null) { 
    195             throw new IllegalArgumentException("symbol must not be null"); 
    196         } 
    197          
    198         Map.Entry<K, V> entry = getEntry(symbol); 
    199          
    200         if (entry != null) { 
    201             return entry.getValue(); 
    202         } 
    203         else { 
    204             return null; 
    205         } 
    206     } 
     92    public V getValue(K symbol); 
    20793 
    20894    /** 
    … …  
    21096     * Adds a symbol and an associated value to the map. If the value is null, the symbol is added, 
    21197     * anyway and {@link #containsSymbol(Object)} will return true for that symbol. Adding the 
    212      * same symbol twice will produce two entries. This is contradictory to typical map 
     98     * same symbol twice may produce two entries. This is contradictory to typical map 
    21399     * implementations. To prevent this, the {@link #containsSymbol(Object)} and 
    214100     * {@link #removeSymbol(Object)} methods should be used to ensure map behavior. 
    … …  
    222108     * @throws IllegalArgumentException if the provided symbol is null 
    223109     */ 
    224     public void addSymbol(K symbol, V value) { 
    225         if (symbol == null) { 
    226             throw new IllegalArgumentException("symbol must not be null"); 
    227         } 
    228          
    229         Map.Entry<K, V> entry = new SymbolMapEntry(symbol, value); 
    230          
    231         symbolList.add(entry); 
    232              
    233         if (symbolList.size() > MAX_LIST_SIZE) { 
    234             if (symbolBuckets == null) { 
    235                 createSymbolBuckets(); 
    236             } 
    237             else { 
    238                 addToSymbolBucket(entry); 
    239             } 
    240         } 
    241     } 
     110    public void addSymbol(K symbol, V value); 
    242111 
    243112    /** 
    … …  
    253122     * @throws IllegalArgumentException if the provided symbol is null 
    254123     */ 
    255     public V removeSymbol(K symbol) { 
    256         if (symbol == null) { 
    257             throw new IllegalArgumentException("symbol must not be null"); 
    258         } 
    259          
    260         for (int i = 0; i < symbolList.size(); i++) { 
    261             if (comparator.equals(symbolList.get(i).getKey(), symbol)) { 
    262                 // found the symbol. Remove it from the list, and if required, also from the map. 
    263                 V value = symbolList.remove(i).getValue(); 
    264                  
    265                 if (symbolList.size() > MAX_LIST_SIZE) { 
    266                     removeFromSymbolBuckets(symbol); 
    267                 } 
    268                  
    269                 return value; 
    270             } 
    271         } 
    272          
    273         return null; 
    274     } 
     124    public V removeSymbol(K symbol); 
    275125 
    276126    /** 
    … …  
    281131     * @return as described 
    282132     */ 
    283     public Collection<K> getSymbols() { 
    284         return new ReadOnlyCollectionFacade<K>(symbolList, new SymbolFacade()); 
    285     } 
     133    public Collection<K> getSymbols(); 
    286134     
    287135    /** 
    … …  
    294142     * @return as described 
    295143     */ 
    296     public Collection<V> getValues() { 
    297         return new ReadOnlyCollectionFacade<V>(symbolList, new ValueFacade()); 
    298     } 
     144    public Collection<V> getValues(); 
    299145     
    300146    /** 
    … …  
    303149     * </p> 
    304150     */ 
    305     public void clear() { 
    306         symbolList.clear(); 
    307         symbolBuckets = null; 
    308     } 
     151    public void clear(); 
    309152 
    310153    /* (non-Javadoc) 
    … …  
    312155     */ 
    313156    @Override 
    314     public int hashCode() { 
    315         return symbolList.size(); 
    316     } 
     157    public int hashCode(); 
    317158 
    318159    /* (non-Javadoc) 
    319160     * @see java.lang.Object#equals(java.lang.Object) 
    320161     */ 
    321     @SuppressWarnings("unchecked") 
    322162    @Override 
    323     public boolean equals(Object obj) { 
    324         if (this == obj) { 
    325             return true; 
    326         } 
    327         else if (this.getClass().isInstance(obj)) { 
    328             SymbolMap<K, V> other = (SymbolMap<K, V>) obj; 
    329              
    330             return (symbolList.size() == other.symbolList.size()) && 
    331                    (symbolList.containsAll(other.symbolList)); 
    332         } 
    333         else { 
    334             return false; 
    335         } 
    336     } 
    337  
    338     /** 
    339      * <p> 
    340      * Internally used to create symbol buckets in case the number of stored symbols increased 
    341      * above {@link #MAX_LIST_SIZE}. 
    342      * </p> 
    343      */ 
    344     private void createSymbolBuckets() { 
    345         //System.out.println("creating symbol buckets"); 
    346         symbolBuckets = new HashMap<Integer, List<Map.Entry<K, V>>>(); 
    347          
    348         for (Map.Entry<K, V> symbol : symbolList) { 
    349             addToSymbolBucket(symbol); 
    350         } 
    351     } 
    352  
    353     /** 
    354      * <p> 
    355      * Adds a symbol and its value to its corresponding bucket. The corresponding bucket is 
    356      * retrieved from the symbol comparator. It is the first element of the search order returned 
    357      * by the symbol comparator. If the comparator does not define a search order for the symbol 
    358      * the entry is added to the default bucket. If the comparator defines a bucket id 
    359      * identical to the default bucket id, the default bucket id is shifted to another value. 
    360      * </p> 
    361      */ 
    362     private void addToSymbolBucket(Map.Entry<K, V> symbolEntry) { 
    363         int bucketId = defaultBucket; 
    364         int[] bucketSearchOrder = comparator.getBucketSearchOrder(symbolEntry.getKey()); 
    365          
    366         if ((bucketSearchOrder != null) && (bucketSearchOrder.length > 0)) { 
    367             bucketId = bucketSearchOrder[0]; 
    368              
    369             if (bucketId == defaultBucket) { 
    370                 setNewDefaultBucketId(); 
    371             } 
    372         } 
    373          
    374         List<Map.Entry<K, V>> list = symbolBuckets.get(bucketId); 
    375          
    376         if (list == null) { 
    377             list = new LinkedList<Map.Entry<K, V>>(); 
    378             symbolBuckets.put(bucketId, list); 
    379         } 
    380          
    381         list.add(symbolEntry); 
    382     } 
    383      
    384     /** 
    385      * <p> 
    386      * Removes the entry for a given symbol from the buckets. It uses the bucket search order 
    387      * defined by the symbol comparator to find the symbol as fast as possible. 
    388      * </p> 
    389      */ 
    390     private Map.Entry<K, V> removeFromSymbolBuckets(K symbol) { 
    391         int bucketId = defaultBucket; 
    392         int[] bucketSearchOrder = comparator.getBucketSearchOrder(symbol); 
    393          
    394         if ((bucketSearchOrder != null) && (bucketSearchOrder.length > 0)) { 
    395             bucketId = bucketSearchOrder[0]; 
    396         } 
    397          
    398         List<Map.Entry<K, V>> list = symbolBuckets.get(bucketId); 
    399         Map.Entry<K, V> result = null; 
    400          
    401         if (list != null) { 
    402             for (int i = 0; i < list.size(); i++) { 
    403                 if (comparator.equals(list.get(i).getKey(), symbol)) { 
    404                     result = list.remove(i); 
    405                     break; 
    406                 } 
    407             } 
    408              
    409             if (list.isEmpty()) { 
    410                 symbolBuckets.remove(bucketId); 
    411             } 
    412         } 
    413          
    414         return result; 
    415     } 
    416  
    417     /** 
    418      * <p> 
    419      * Updates the default bucket id to a new one 
    420      * </p> 
    421      */ 
    422     private void setNewDefaultBucketId() { 
    423         int oldDefaultBucket = defaultBucket; 
    424         do { 
    425             defaultBucket += 1; 
    426         } 
    427         while (symbolBuckets.containsKey(defaultBucket)); 
    428          
    429         symbolBuckets.put(defaultBucket, symbolBuckets.get(oldDefaultBucket)); 
    430     } 
    431  
    432     /** 
    433      * <p> 
    434      * searches for the entry belonging to the given symbol. The method either uses the list if 
    435      * buckets are not used yet, or it uses the buckets and searches them in the order defined 
    436      * by the comparator. If the symbol isn't found and the comparator does not refer all buckets, 
    437      * then also the other buckets are searched for the symbol. 
    438      * </p> 
    439      */ 
    440     private Map.Entry<K, V> getEntry(K symbol) { 
    441         Map.Entry<K, V> entry = null; 
    442         if (symbolBuckets == null) { 
    443             entry = lookup(symbol, symbolList); 
    444         } 
    445         else { 
    446             int[] bucketSearchOrder = comparator.getBucketSearchOrder(symbol); 
    447             for (int bucketId : bucketSearchOrder) { 
    448                 List<Map.Entry<K, V>> list = symbolBuckets.get(bucketId); 
    449                 if (list != null) { 
    450                     entry = lookup(symbol, list); 
    451                     if (entry != null) { 
    452                         break; 
    453                     } 
    454                 } 
    455             } 
    456              
    457             // try to search the other buckets 
    458             if (entry == null) { 
    459                 Arrays.sort(bucketSearchOrder); 
    460                 for (Map.Entry<Integer, List<Map.Entry<K, V>>> bucket : symbolBuckets.entrySet()) { 
    461                     if (Arrays.binarySearch(bucketSearchOrder, bucket.getKey()) < 0) { 
    462                         List<Map.Entry<K, V>> list = bucket.getValue(); 
    463                         if (list != null) { 
    464                             entry = lookup(symbol, list); 
    465                             if (entry != null) { 
    466                                 break; 
    467                             } 
    468                         } 
    469                     } 
    470                 } 
    471             } 
    472         } 
    473          
    474         return entry; 
    475     } 
    476  
    477     /** 
    478      * <p> 
    479      * Convenience method to look up a symbol in a list of entries using the comparator. 
    480      * </p> 
    481      */ 
    482     private Map.Entry<K, V> lookup(K symbol, List<Map.Entry<K, V>> list) { 
    483         for (Map.Entry<K, V> candidate : list) { 
    484             if (comparator.equals(candidate.getKey(), symbol)) { 
    485                 return candidate; 
    486             } 
    487         } 
    488          
    489         return null; 
    490     } 
    491  
    492     /** 
    493      * <p> 
    494      * Internally used data structure for storing symbol value pairs 
    495      * </p> 
    496      *  
    497      * @author Patrick Harms 
    498      */ 
    499     private class SymbolMapEntry implements Map.Entry<K, V> { 
    500          
    501         /** 
    502          * the symbol to map to a value 
    503          */ 
    504         private K symbol; 
    505          
    506         /** 
    507          * the value associated with the symbol 
    508          */ 
    509         private V value; 
    510  
    511         /** 
    512          * <p> 
    513          * Simple constructor for initializing the entry with a symbol and its associated value. 
    514          * </p> 
    515          */ 
    516         private SymbolMapEntry(K symbol, V value) { 
    517             super(); 
    518             this.symbol = symbol; 
    519             this.value = value; 
    520         } 
    521  
    522         /* (non-Javadoc) 
    523          * @see java.util.Map.Entry#getKey() 
    524          */ 
    525         @Override 
    526         public K getKey() { 
    527             return symbol; 
    528         } 
    529  
    530         /* (non-Javadoc) 
    531          * @see java.util.Map.Entry#getValue() 
    532          */ 
    533         @Override 
    534         public V getValue() { 
    535             return value; 
    536         } 
    537  
    538         /* (non-Javadoc) 
    539          * @see java.util.Map.Entry#setValue(java.lang.Object) 
    540          */ 
    541         @Override 
    542         public V setValue(V value) { 
    543             V oldValue = this.value; 
    544             this.value = value; 
    545             return oldValue; 
    546         } 
    547  
    548         /* (non-Javadoc) 
    549          * @see java.lang.Object#hashCode() 
    550          */ 
    551         @Override 
    552         public int hashCode() { 
    553             return symbol.hashCode(); 
    554         } 
    555  
    556         /* (non-Javadoc) 
    557          * @see java.lang.Object#equals(java.lang.Object) 
    558          */ 
    559         @SuppressWarnings("unchecked") 
    560         @Override 
    561         public boolean equals(Object obj) { 
    562             if (this == obj) { 
    563                 return true; 
    564             } 
    565             else if (this.getClass().isInstance(obj)) { 
    566                 SymbolMapEntry other = (SymbolMapEntry) obj; 
    567                 return (symbol.equals(other.symbol) && 
    568                         (value == null ? other.value == null : value.equals(other.value))); 
    569             } 
    570             else { 
    571                 return false; 
    572             } 
    573         } 
    574  
    575         /* (non-Javadoc) 
    576          * @see java.lang.Object#toString() 
    577          */ 
    578         @Override 
    579         public String toString() { 
    580             return symbol + "=" + value; 
    581         } 
    582  
    583     } 
    584  
    585     /** 
    586      * <p> 
    587      * Used to create an efficient facade for accessing the internal list of entries either only 
    588      * for the symbols or only for the values. It is a default implementation of the collection 
    589      * interface. The entry facade provided to the constructor decides, if either the list 
    590      * accesses only the symbols or only the values.  
    591      * </p> 
    592      *  
    593      * @author Patrick Harms 
    594      */ 
    595     private class ReadOnlyCollectionFacade<TYPE> implements Collection<TYPE> { 
    596          
    597         /** 
    598          * the list facaded by this facade 
    599          */ 
    600         private List<Map.Entry<K, V>> list; 
    601          
    602         /** 
    603          * the facade to be used for the entries 
    604          */ 
    605         private EntryFacade<TYPE> entryFacade; 
    606          
    607         /** 
    608          * <p> 
    609          * Initializes the facade with the facaded list and the facade to be used for the entries 
    610          * </p> 
    611          */ 
    612         private ReadOnlyCollectionFacade(List<Map.Entry<K, V>> list, EntryFacade<TYPE> entryFacade) 
    613         { 
    614             this.list = list; 
    615             this.entryFacade = entryFacade; 
    616         } 
    617  
    618         /* (non-Javadoc) 
    619          * @see java.util.Collection#size() 
    620          */ 
    621         @Override 
    622         public int size() { 
    623             return list.size(); 
    624         } 
    625  
    626         /* (non-Javadoc) 
    627          * @see java.util.Collection#isEmpty() 
    628          */ 
    629         @Override 
    630         public boolean isEmpty() { 
    631             return list.isEmpty(); 
    632         } 
    633  
    634         /* (non-Javadoc) 
    635          * @see java.util.Collection#contains(java.lang.Object) 
    636          */ 
    637         @Override 
    638         public boolean contains(Object o) { 
    639             if (o == null) { 
    640                 for (Map.Entry<K, V> entry : list) { 
    641                     if (entryFacade.getFacadedElement(entry) == null) { 
    642                         return true; 
    643                     } 
    644                 } 
    645             } 
    646             else { 
    647                 for (Map.Entry<K, V> entry : list) { 
    648                     if (o.equals(entryFacade.getFacadedElement(entry))) { 
    649                         return true; 
    650                     } 
    651                 } 
    652             } 
    653              
    654             return false; 
    655         } 
    656  
    657         /* (non-Javadoc) 
    658          * @see java.util.Collection#toArray() 
    659          */ 
    660         @Override 
    661         public Object[] toArray() { 
    662             Object[] result = new Object[list.size()]; 
    663              
    664             for (int i = 0; i < list.size(); i++) { 
    665                 result[i] = entryFacade.getFacadedElement(list.get(i)); 
    666             } 
    667              
    668             return result; 
    669         } 
    670  
    671         /* (non-Javadoc) 
    672          * @see java.util.Collection#toArray(T[]) 
    673          */ 
    674         @SuppressWarnings("unchecked") 
    675         @Override 
    676         public <T> T[] toArray(T[] a) { 
    677             T[] result = a; 
    678              
    679             for (int i = 0; i < list.size(); i++) { 
    680                 result[i] = (T) entryFacade.getFacadedElement(list.get(i)); 
    681             } 
    682              
    683             return result; 
    684         } 
    685  
    686         /* (non-Javadoc) 
    687          * @see java.util.Collection#add(java.lang.Object) 
    688          */ 
    689         @Override 
    690         public boolean add(TYPE e) { 
    691             throw new UnsupportedOperationException("this collection is read only"); 
    692         } 
    693  
    694         /* (non-Javadoc) 
    695          * @see java.util.Collection#remove(java.lang.Object) 
    696          */ 
    697         @Override 
    698         public boolean remove(Object o) { 
    699             throw new UnsupportedOperationException("this collection is read only"); 
    700         } 
    701  
    702         /* (non-Javadoc) 
    703          * @see java.util.Collection#containsAll(java.util.Collection) 
    704          */ 
    705         @Override 
    706         public boolean containsAll(Collection<?> c) { 
    707             for (Object candidate : c) { 
    708                 if (!contains(candidate)) { 
    709                     return false; 
    710                 } 
    711             } 
    712              
    713             return true; 
    714         } 
    715  
    716         /* (non-Javadoc) 
    717          * @see java.util.Collection#addAll(java.util.Collection) 
    718          */ 
    719         @Override 
    720         public boolean addAll(Collection<? extends TYPE> c) { 
    721             throw new UnsupportedOperationException("this collection is read only"); 
    722         } 
    723  
    724         /* (non-Javadoc) 
    725          * @see java.util.Collection#removeAll(java.util.Collection) 
    726          */ 
    727         @Override 
    728         public boolean removeAll(Collection<?> c) { 
    729             throw new UnsupportedOperationException("this collection is read only"); 
    730         } 
    731  
    732         /* (non-Javadoc) 
    733          * @see java.util.Collection#retainAll(java.util.Collection) 
    734          */ 
    735         @Override 
    736         public boolean retainAll(Collection<?> c) { 
    737             throw new UnsupportedOperationException("this collection is read only"); 
    738         } 
    739  
    740         /* (non-Javadoc) 
    741          * @see java.util.Collection#clear() 
    742          */ 
    743         @Override 
    744         public void clear() { 
    745             throw new UnsupportedOperationException("this collection is read only"); 
    746         } 
    747  
    748         /* (non-Javadoc) 
    749          * @see java.util.Collection#iterator() 
    750          */ 
    751         @Override 
    752         public Iterator<TYPE> iterator() { 
    753             return new ReadOnlyCollectionIteratorFacade<TYPE>(list.iterator(), entryFacade); 
    754         } 
    755          
    756     } 
    757  
    758     /** 
    759      * <p> 
    760      * Implementation of an iterator to facade an iterator on the internal list of symbol entries. 
    761      * </p> 
    762      *  
    763      * @author Patrick Harms 
    764      */ 
    765     private class ReadOnlyCollectionIteratorFacade<TYPE> implements Iterator<TYPE> { 
    766          
    767         /** 
    768          * the facaded iterator 
    769          */ 
    770         private Iterator<Map.Entry<K, V>> iterator; 
    771          
    772         /** 
    773          * the facade for the entries provided by the facaded iterator 
    774          */ 
    775         private EntryFacade<TYPE> entryFacade; 
    776          
    777         /** 
    778          * <p> 
    779          * initialized this facade with the facaded iterator and the entry facade to be used for 
    780          * the entries. 
    781          * </p> 
    782          */ 
    783         private ReadOnlyCollectionIteratorFacade(Iterator<Map.Entry<K, V>> iterator, 
    784                                                  EntryFacade<TYPE>         entryFacade) 
    785         { 
    786             this.iterator = iterator; 
    787             this.entryFacade = entryFacade; 
    788         } 
    789  
    790         /* (non-Javadoc) 
    791          * @see java.util.Iterator#hasNext() 
    792          */ 
    793         @Override 
    794         public boolean hasNext() { 
    795             return iterator.hasNext(); 
    796         } 
    797  
    798         /* (non-Javadoc) 
    799          * @see java.util.Iterator#next() 
    800          */ 
    801         @Override 
    802         public TYPE next() { 
    803             return entryFacade.getFacadedElement(iterator.next()); 
    804         } 
    805  
    806         /* (non-Javadoc) 
    807          * @see java.util.Iterator#remove() 
    808          */ 
    809         @Override 
    810         public void remove() { 
    811             throw new UnsupportedOperationException("this iterator is read only"); 
    812         } 
    813          
    814     } 
    815          
    816     /** 
    817      * <p> 
    818      * Used to facade symbol entries and to return only this part of an entry, that is relevant. 
    819      * </p> 
    820      *  
    821      * @author Patrick Harms 
    822      */ 
    823     private abstract class EntryFacade<T> { 
    824          
    825         /** 
    826          * <p> 
    827          * Returns only the part of an entry that is relevant or required. 
    828          * </p> 
    829          * 
    830          * @param entry of which the part shall be returned 
    831          *  
    832          * @return the part of the entry to be returned 
    833          */ 
    834         protected abstract T getFacadedElement(Entry<K, V> entry); 
    835          
    836     } 
    837      
    838     /** 
    839      * <p> 
    840      * Implementation of the entry facade returning the entries key, i.e. the symbol. 
    841      * </p> 
    842      *  
    843      * @author Patrick Harms 
    844      */ 
    845     private class SymbolFacade extends EntryFacade<K> { 
    846  
    847         /* (non-Javadoc) 
    848          * @see ReadOnlyCollectionIteratorFacade#getFacadedElement(Entry) 
    849          */ 
    850         @Override 
    851         protected K getFacadedElement(Entry<K, V> entry) { 
    852             return entry.getKey(); 
    853         } 
    854     } 
    855      
    856     /** 
    857      * <p> 
    858      * Implementation of the entry facade returning the entries value, i.e. the value associated to 
    859      * the symbol. 
    860      * </p> 
    861      *  
    862      * @author Patrick Harms 
    863      */ 
    864     private class ValueFacade extends EntryFacade<V> { 
    865  
    866         /* (non-Javadoc) 
    867          * @see ReadOnlyCollectionIteratorFacade#getFacadedElement(Entry) 
    868          */ 
    869         @Override 
    870         protected V getFacadedElement(Entry<K, V> entry) { 
    871             return entry.getValue(); 
    872         } 
    873     } 
     163    public boolean equals(Object obj); 
    874164 
    875165} 
Note: See TracChangeset for help on using the changeset viewer.