001package org.maltparser.core.symbol.trie;
002
003
004import org.maltparser.core.symbol.SymbolException;
005
006/**
007*
008* @author Johan Hall
009* @since 1.0
010**/
011public class Trie {
012        private final TrieNode root;
013
014
015        
016        public Trie() {
017                root = new TrieNode(' ', null);
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                final StringBuilder sb = new StringBuilder();
047                TrieNode tmp = node;
048                while (tmp != root) { 
049                        sb.append(tmp.getCharacter());
050                        tmp = tmp.getParent();
051                }
052                return sb.toString();
053        }
054        
055        public Integer 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}