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
Location:
trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles
Files:
3 added
5 edited

Legend:

Unmodified
Added
Removed

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

    r1251 r1282  
    2626public class DefaultSymbolComparator<T> implements SymbolComparator<T> { 
    2727 
    28     /**  */ 
     28    /** 
     29     * default serial version UID 
     30     */ 
    2931    private static final long serialVersionUID = 1L; 
    3032 
    … …  
    4244    } 
    4345 
    44     /* (non-Javadoc) 
    45      * @see de.ugoe.cs.autoquest.usageprofiles.SymbolComparator#getBucketSearchOrder(Object) 
    46      */ 
    47     @Override 
    48     public int[] getBucketSearchOrder(T symbol) { 
    49         if (symbol != null) { 
    50             return new int[] { symbol.hashCode() }; 
    51         } 
    52         else { 
    53             return null; 
    54         } 
    55     } 
    56  
    5746} 

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

    r1251 r1282  
    2929     * <p> 
    3030     * compares two symbols and returns true, if the concrete comparison strategy sees both 
    31      * symbols as equal. The method must be commutative, i.e., 
    32      * <code>equals(symbol1, symbol2) == equals(symbol2, symbol1)</code>. 
     31     * symbols as equal. The method must be commutative and transitive, i.e., 
     32     * <code>equals(symbol1, symbol2) == equals(symbol2, symbol1)</code> and 
     33     * <code>if (equals(symbol1, symbol2) && equals(symbol2, symbol3)) then 
     34     * equals(symbol1, symbol3)</code>. 
    3335     * </p> 
    3436     * 
    … …  
    3941     */ 
    4042    public boolean equals(T symbol1, T symbol2); 
    41      
    42     /** 
    43      * <p> 
    44      * returns a search order for buckets. This method can be used for optimizing a search for 
    45      * equal symbols. The client of this class can store symbols in buckets of similar symbols. 
    46      * Those buckets get an id denoted by an integer. The most appropriate bucket for a symbol is 
    47      * the first element in the array returned by this method. The symbol should therefore be put 
    48      * into that bucket. 
    49      * </p> 
    50      * <p> 
    51      * In case a search for an equal symbol shall be performed at the client side, the client 
    52      * checks the available buckets in the order given as return value of this method. All other 
    53      * buckets are searched afterwards. In this scenario it is ensured, that the equal symbol is 
    54      * found as soon as possible as the search always starts in the most appropriate bucket. 
    55      * However, the other buckets are searched, as well, if no equal symbol is found. Therefore, 
    56      * in the worst case, all buckets are searched. In the optimal case, the equal symbol is found 
    57      * in the first bucket. 
    58      * </p> 
    59      * <p> 
    60      * The returned array should contain different integers in each field. This allows a most 
    61      * efficient search. If an integer is repeated, it is up to the clien, if this is ignored. 
    62      * </p> 
    63      * 
    64      * @param symbol the symbol for which the bucket order is to be returned 
    65      *  
    66      * @return a search order for buckets as described 
    67      *  
    68      * @see SymbolMap 
    69      */ 
    70     public int[] getBucketSearchOrder(T symbol); 
     43 
    7144} 

  • 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} 

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

    r1251 r1282  
    2929/** 
    3030 * <p> 
    31  * This class implements a <it>trie</it>, i.e., a tree of sequences that the occurence of 
    32  * subsequences up to a predefined length. This length is the trie order. 
     31 * This class implements a <it>trie</it>, i.e., a tree of sequences that represents the occurrence 
     32 * of subsequences up to a predefined length. This length is the trie order. 
    3333 * </p> 
    3434 *  
    … …  
    5151    /** 
    5252     * <p> 
    53      * Collection of all symbols occuring in the trie. 
     53     * Collection of all symbols occurring in the trie. 
    5454     * </p> 
    5555     */ 
    … …  
    6565    /** 
    6666     * <p> 
    67      * Comparator to be used for comparing the symbols with each other 
    68      * </p> 
    69      */ 
    70     private SymbolComparator<T> comparator; 
    71  
    72     /** 
    73      * <p> 
    74      * Contructor. Creates a new Trie with a {@link DefaultSymbolComparator}. 
     67     * Strategy for handling symbols, i.e., for comparing and storing them 
     68     * </p> 
     69     */ 
     70    private SymbolStrategy<T> strategy; 
     71 
     72    /** 
     73     * <p> 
     74     * Constructor. Creates a new trie with a {@link DefaultSymbolStrategy}. 
    7575     * </p> 
    7676     */ 
    7777    public Trie() { 
    78         this(new DefaultSymbolComparator<T>()); 
    79     } 
    80  
    81     /** 
    82      * <p> 
    83      * Contructor. Creates a new Trie with that uses a specific {@link SymbolComparator}. 
    84      * </p> 
    85      */ 
    86     public Trie(SymbolComparator<T> comparator) { 
    87         this.comparator = comparator; 
    88         rootNode = new TrieNode<T>(comparator); 
    89         knownSymbols = new SymbolMap<T, T>(this.comparator); 
    90     } 
    91  
    92     /** 
    93      * <p> 
    94      * Copy-Constructor. Creates a new Trie as the copy of other. The other trie must not be null. 
     78        this(new DefaultSymbolStrategy<T>()); 
     79    } 
     80 
     81    /** 
     82     * <p> 
     83     * Constructor. Creates a new trie that uses a specific {@link SymbolStrategy}. 
     84     * </p> 
     85     *  
     86     * @param strategy 
     87     *            strategy to be used for managing symbols 
     88     *  
     89     * @throws IllegalArgumentException 
     90     *            if the strategy is null 
     91     */ 
     92    public Trie(SymbolStrategy<T> strategy) { 
     93        if (strategy == null) { 
     94            throw new IllegalArgumentException("strategy must not be null"); 
     95        } 
     96        this.strategy = strategy; 
     97        rootNode = new TrieNode<T>(strategy); 
     98        knownSymbols = strategy.createSymbolMap(); 
     99    } 
     100 
     101    /** 
     102     * <p> 
     103     * Copy-Constructor. Creates a new trie as the copy of other. The other trie must not be null. 
    95104     * </p> 
    96105     *  
    97106     * @param other 
    98      *            Trie that is copied 
     107     *            trie that is copied 
     108     *  
     109     * @throws IllegalArgumentException 
     110     *            if the other trie is null 
    99111     */ 
    100112    public Trie(Trie<T> other) { 
    … …  
    103115        } 
    104116        rootNode = new TrieNode<T>(other.rootNode); 
    105         knownSymbols = new SymbolMap<T, T>(other.knownSymbols); 
    106         comparator = other.comparator; 
    107     } 
    108  
    109     /** 
    110      * <p> 
    111      * Returns a collection of all symbols occuring in the trie. 
    112      * </p> 
    113      *  
    114      * @return symbols occuring in the trie 
     117        strategy = other.strategy; 
     118        knownSymbols = strategy.copySymbolMap(other.knownSymbols); 
     119    } 
     120 
     121    /** 
     122     * <p> 
     123     * Returns a collection of all symbols occurring in the trie. 
     124     * </p> 
     125     *  
     126     * @return symbols occurring in the trie 
    115127     */ 
    116128    public Collection<T> getKnownSymbols() { 
    … …  
    202214    /** 
    203215     * <p> 
    204      * Returns the number of occurences of the given sequence. 
     216     * Returns the number of occurrences of the given sequence. 
    205217     * </p> 
    206218     *  
    207219     * @param sequence 
    208      *            sequence whose number of occurences is required 
    209      * @return number of occurences of the sequence 
     220     *            sequence whose number of occurrences is required 
     221     * @return number of occurrences of the sequence 
    210222     */ 
    211223    public int getCount(List<T> sequence) { 
    … …  
    220232    /** 
    221233     * <p> 
    222      * Returns the number of occurences of the given prefix and a symbol that follows it.<br> 
     234     * Returns the number of occurrences of the given prefix and a symbol that follows it.<br> 
    223235     * Convenience function to simplify usage of {@link #getCount(List)}. 
    224236     * </p> 
    … …  
    228240     * @param follower 
    229241     *            suffix of the sequence 
    230      * @return number of occurences of the sequence 
     242     * @return number of occurrences of the sequence 
    231243     * @see #getCount(List) 
    232244     */ 
    … …  
    326338     * <p> 
    327339     * used to recursively process the trie. The provided processor will be called for any path 
    328      * through the tree. The processor may abort the processing through returns values of its 
     340     * through the trie. The processor may abort the processing through return values of its 
    329341     * {@link TrieProcessor#process(List, int)} method. 
    330342     * </p> 
    … …  
    348360     * </p> 
    349361     *  
    350      * @param context   the context of the currently processed trie node, i.e. the preceeding 
     362     * @param context   the context of the currently processed trie node, i.e. the preceding 
    351363     *                  symbols 
    352364     * @param child     the processed trie node 
    … …  
    489501     * <p> 
    490502     * adds a new symbol to the collection of known symbols if this symbol is not already 
    491      * contained. The symbols are compared using the comparator. 
     503     * contained. 
    492504     * </p> 
    493505     * 
    … …  
    496508    private void addToKnownSymbols(T symbol) { 
    497509        if (!knownSymbols.containsSymbol(symbol)) { 
    498             knownSymbols.addSymbol(symbol, symbol); 
     510            knownSymbols.addSymbol(symbol, null); 
    499511        } 
    500512    } 
    … …  
    529541        /** 
    530542         * <p> 
    531          * Contructor. Creates a new TrieVertex. 
     543         * Constructor. Creates a new TrieVertex. 
    532544         * </p> 
    533545         *  
    … …  
    635647     */ 
    636648    public void updateKnownSymbols() { 
    637         knownSymbols = new SymbolMap<T, T>(this.comparator); 
     649        knownSymbols = strategy.createSymbolMap(); 
    638650        for (TrieNode<T> node : rootNode.getChildren()) { 
    639651            addToKnownSymbols(node.getSymbol()); 
    … …  
    643655    /** 
    644656     * <p> 
    645      * Two Tries are defined as equal, if their {@link #rootNode} are equal. 
     657     * Two tries are defined as equal, if their {@link #rootNode}s are equal. 
    646658     * </p> 
    647659     *  

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

    r1251 r1282  
    2929 * <p> 
    3030 * This class implements a node of a trie. Each node is associated with a symbol and has a counter. 
    31  * The counter marks the number of occurences of the sequence defined by the path from the root of 
     31 * The counter marks the number of occurrences of the sequence defined by the path from the root of 
    3232 * the trie to this node. 
    3333 * </p> 
    … …  
    5050    /** 
    5151     * <p> 
    52      * Counter for the number of occurences of the sequence. 
     52     * Counter for the number of occurrences of the sequence. 
    5353     * </p> 
    5454     */ 
    … …  
    7171    /** 
    7272     * <p> 
    73      * Comparator to be used for comparing the symbols with each other 
    74      * </p> 
    75      */ 
    76     private SymbolComparator<T> comparator; 
     73     * Strategy for handling symbols, i.e., for comparing and storing them 
     74     * </p> 
     75     */ 
     76    private SymbolStrategy<T> strategy; 
    7777 
    7878    /** 
    … …  
    8080     * Constructor. Creates a new TrieNode without a symbol associated.<br> 
    8181     * <b>This constructor should only be used to create the root node of the trie!</b> 
    82      * The comparator used by the tree node will be a {@link DefaultSymbolComparator}. 
     82     * The strategy used by the trie node will be a {@link DefaultSymbolStrategy}. 
    8383     * </p> 
    8484     */ 
    8585    TrieNode() { 
    86         this(new DefaultSymbolComparator<T>()); 
     86        this(new DefaultSymbolStrategy<T>()); 
    8787    } 
    8888 
    … …  
    9090     * <p> 
    9191     * Constructor. Creates a new TrieNode. The symbol must not be null. 
    92      * The comparator used by the tree node will be a {@link DefaultSymbolComparator}. 
     92     * The strategy used by the trie node will be a {@link DefaultSymbolStrategy}. 
    9393     * </p> 
    9494     *  
    9595     * @param symbol 
    9696     *            symbol associated with the trie node 
     97     *  
     98     * @throws IllegalArgumentException 
     99     *            if the provided symbol is null 
    97100     */ 
    98101    TrieNode(T symbol) { 
    99         this(symbol, new DefaultSymbolComparator<T>()); 
     102        this(symbol, new DefaultSymbolStrategy<T>()); 
    100103    } 
    101104 
    … …  
    103106     * <p> 
    104107     * Constructor. Creates a new TrieNode without a symbol associated using the provided 
    105      * comparator.<br> 
     108     * strategy.<br> 
    106109     * <b>This constructor should only be used to create the root node of the trie!</b> 
    107      * <br>The comparator must not be null. 
    108      * </p> 
    109      */ 
    110     TrieNode(SymbolComparator<T> comparator) { 
    111         if (comparator == null) { 
    112             throw new IllegalArgumentException("comparator must not be null!"); 
    113         } 
    114         this.comparator = comparator; 
     110     * <br>The strategy must not be null. 
     111     * </p> 
     112     *  
     113     * @param strategy 
     114     *            the strategy used for comparing and storing symbols 
     115     *  
     116     * @throws IllegalArgumentException 
     117     *            if the provided strategy is null 
     118     */ 
     119    TrieNode(SymbolStrategy<T> strategy) { 
     120        if (strategy == null) { 
     121            throw new IllegalArgumentException("strategy must not be null!"); 
     122        } 
     123        this.strategy = strategy; 
    115124        this.symbol = null; 
    116125        count = 0; 
    117         children = new SymbolMap<T, TrieNode<T>>(this.comparator); 
    118     } 
    119  
    120     /** 
    121      * <p> 
    122      * Constructor. Creates a new TrieNode using the provided comparator. The symbol and the 
    123      * comparator must not be null. 
     126        children = strategy.createSymbolMap(); 
     127    } 
     128 
     129    /** 
     130     * <p> 
     131     * Constructor. Creates a new TrieNode using the provided strategy. The symbol and the 
     132     * strategy must not be null. 
    124133     * </p> 
    125134     *  
    126135     * @param symbol 
    127136     *            symbol associated with the trie node 
    128      */ 
    129     TrieNode(T symbol, SymbolComparator<T> comparator) { 
     137     * @param strategy 
     138     *            the strategy used for comparing and storing symbols 
     139     *  
     140     * @throws IllegalArgumentException 
     141     *            if the provided symbol or strategy is null 
     142     */ 
     143    TrieNode(T symbol, SymbolStrategy<T> strategy) { 
    130144        if (symbol == null) { 
    131145            throw new IllegalArgumentException 
    … …  
    134148        this.symbol = symbol; 
    135149         
    136         if (comparator == null) { 
    137             throw new IllegalArgumentException("comparator must not be null!"); 
    138         } 
    139         this.comparator = comparator; 
     150        if (strategy == null) { 
     151            throw new IllegalArgumentException("strategy must not be null!"); 
     152        } 
     153        this.strategy = strategy; 
    140154 
    141155        count = 0; 
    142         children = new SymbolMap<T, TrieNode<T>>(this.comparator); 
     156        children = strategy.createSymbolMap(); 
    143157    } 
    144158 
    … …  
    148162     * </p> 
    149163     *  
    150      * @param other 
     164     * @param other the trie node to create the copy of 
     165     *  
     166     * @throws IllegalArgumentException 
     167     *            if the provided node is null 
    151168     */ 
    152169    TrieNode(TrieNode<T> other) { 
    … …  
    156173        symbol = other.symbol; 
    157174        count = other.count; 
    158         comparator = other.comparator; 
    159         children = new SymbolMap<T, TrieNode<T>>(this.comparator); 
     175        strategy = other.strategy; 
     176        children = strategy.createSymbolMap(); 
    160177         
    161178        for (TrieNode<T> child : other.children.getValues()) { 
    … …  
    175192    public void add(List<T> subsequence) { 
    176193        if (!subsequence.isEmpty()) { 
    177             if (!comparator.equals(symbol, subsequence.get(0))) { // should be guaranteed by 
    178                                                                   // the recursion/TrieRoot! 
     194            if (!strategy.getSymbolComparator().equals(symbol, subsequence.get(0))) { 
     195                // should be guaranteed by the recursion/TrieRoot! 
    179196                throw new AssertionError("Invalid trie operation!"); 
    180197            } 
    … …  
    201218    /** 
    202219     * <p> 
    203      * Returns the number of occurences of the sequence represented by the node. 
    204      * </p> 
    205      *  
    206      * @return number of occurences of the sequence represented by the node 
     220     * Returns the number of occurrences of the sequence represented by the node. 
     221     * </p> 
     222     *  
     223     * @return number of occurrences of the sequence represented by the node 
    207224     */ 
    208225    public int getCount() { 
    … …  
    224241        TrieNode<T> node = getChild(symbol); 
    225242        if (node == null) { 
    226             node = new TrieNode<T>(symbol, comparator); 
     243            node = new TrieNode<T>(symbol, strategy); 
    227244            children.addSymbol(symbol, node); 
    228245        } 
    … …  
    283300    /** 
    284301     * <p> 
    285      * Returns a collection of all symbols that follow a this node, i.e., the symbols associated 
     302     * Returns a collection of all symbols that follow this node, i.e., the symbols associated 
    286303     * with the children of this node. 
    287304     * </p> 
    … …  
    399416    /** 
    400417     * <p> 
    401      * Recursive methods that collects all nodes that are ancestors of leafs and stores them in the 
     418     * Recursive method that collects all nodes that are ancestors of leafs and stores them in the 
    402419     * set. 
    403420     * </p> 
    … …  
    457474     * <p> 
    458475     * Two TrieNodes are defined as equal, if their {@link #count}, {@link #symbol}, and 
    459      * {@link #children} are equal. For the comparison of their symbols the comparator is used. 
     476     * {@link #children} are equal. For the comparison of their symbols the comparator provided 
     477     * by the symbol management strategy is used. 
    460478     * </p> 
    461479     *  
    … …  
    477495                return count == otherNode.count && 
    478496                    symbol.getClass().isInstance(((TrieNode) other).symbol) && 
    479                     comparator.equals(symbol, ((TrieNode<T>) other).symbol) && 
     497                    strategy.getSymbolComparator().equals(symbol, ((TrieNode<T>) other).symbol) && 
    480498                    children.equals(((TrieNode) other).children); 
    481499            } 
Note: See TracChangeset for help on using the changeset viewer.