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    
016            
017            public Trie() {
018                    root = new TrieNode(' ', null);
019                    sb = new StringBuilder();
020            }
021            
022            public TrieNode addValue(String value, TrieSymbolTable table, int code) throws SymbolException {
023                    TrieNode node = root;
024                    final char[] chars = value.toCharArray();
025                    for (int i = chars.length-1; i>=0; i--) {
026                            if (i == 0) {
027                                    node = node.getOrAddChild(true, chars[i], table, code);
028                            } else {
029                                    node = node.getOrAddChild(false, chars[i], table, code);
030                            }
031                    }
032                    return node;
033            }
034            
035            public TrieNode addValue(StringBuilder symbol, TrieSymbolTable table, int code) throws SymbolException {
036                    TrieNode node = root;
037                    for (int i = symbol.length()-1; i>=0; i--) {
038                            if (i == 0) {
039                                    node = node.getOrAddChild(true, symbol.charAt(i), table, code);
040                            } else {
041                                    node = node.getOrAddChild(false, symbol.charAt(i), table, code);
042                            }
043                    }
044                    return node;
045            }
046            
047            public String getValue(TrieNode node, TrieSymbolTable table) {
048                    sb.setLength(0);
049                    TrieNode tmp = node;
050                    while (tmp != root) { // && tmp != null) {
051                            sb.append(tmp.getCharacter());
052                            tmp = tmp.getParent();
053                    }
054                    return sb.toString();
055            }
056            
057            public Integer getEntry(String value, TrieSymbolTable table) {
058                    TrieNode node = root;
059                    final char[] chars = value.toCharArray();
060                    int i=chars.length-1;
061                    for (;i>=0 && node != null;i--) {
062                            node = node.getChild(chars[i]);
063                    }
064                    if (i < 0 && node != null) {
065                            return node.getEntry(table);
066                    } 
067                    return null;
068            }
069            
070            public boolean equals(Object obj) {
071                    if (this == obj)
072                            return true;
073                    if (obj == null)
074                            return false;
075                    if (getClass() != obj.getClass())
076                            return false;
077                    return ((root == null) ? ((Trie)obj).root == null : root.equals(((Trie)obj).root));
078            }
079    
080            public int hashCode() {
081                    return 31 * 7 + (null == root ? 0 : root.hashCode());
082            }
083    }