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 }