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/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.