    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    }