001    package org.maltparser.core.symbol.trie;
002    
003    
004    import org.maltparser.core.symbol.SymbolException;
005    
006    /**
007    *
008    * @author Johan Hall
009    * @since 1.0
010    **/
011    public class Trie {
012            private final TrieNode root;
013            private final StringBuilder sb;
014    
015            public Trie() {
016                    root = new TrieNode(' ', null);
017                    sb = new StringBuilder();
018            }
019            
020            public TrieNode addValue(String value, TrieSymbolTable table, int code) throws SymbolException {
021                    TrieNode node = root;
022                    final char[] chars = value.toCharArray();
023                    for (int i = chars.length-1; i>=0; i--) {
024                            if (i == 0) {
025                                    node = node.getOrAddChild(true, chars[i], table, code);
026                            } else {
027                                    node = node.getOrAddChild(false, chars[i], table, code);
028                            }
029                    }
030                    return node;
031            }
032            
033            public TrieNode addValue(StringBuilder symbol, TrieSymbolTable table, int code) throws SymbolException {
034                    TrieNode node = root;
035                    for (int i = symbol.length()-1; i>=0; i--) {
036                            if (i == 0) {
037                                    node = node.getOrAddChild(true, symbol.charAt(i), table, code);
038                            } else {
039                                    node = node.getOrAddChild(false, symbol.charAt(i), table, code);
040                            }
041                    }
042                    return node;
043            }
044            
045            public String getValue(TrieNode node, TrieSymbolTable table) {
046                    sb.setLength(0);
047                    TrieNode tmp = node;
048                    while (tmp != root) { // && tmp != null) {
049                            sb.append(tmp.getCharacter());
050                            tmp = tmp.getParent();
051                    }
052                    return sb.toString();
053            }
054            
055            public TrieEntry getEntry(String value, TrieSymbolTable table) {
056                    TrieNode node = root;
057                    final char[] chars = value.toCharArray();
058                    int i=chars.length-1;
059                    for (;i>=0 && node != null;i--) {
060                            node = node.getChild(chars[i]);
061                    }
062                    if (i < 0 && node != null) {
063                            return node.getEntry(table);
064                    } 
065                    return null;
066            }
067            
068            public boolean equals(Object obj) {
069                    if (this == obj)
070                            return true;
071                    if (obj == null)
072                            return false;
073                    if (getClass() != obj.getClass())
074                            return false;
075                    return ((root == null) ? ((Trie)obj).root == null : root.equals(((Trie)obj).root));
076            }
077    
078            public int hashCode() {
079                    return 31 * 7 + (null == root ? 0 : root.hashCode());
080            }
081    }