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/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     *  
Note: See TracChangeset for help on using the changeset viewer.