001 package org.maltparser.core.symbol.trie;
002
003 import org.maltparser.core.helper.HashMap;
004
005 import org.maltparser.core.symbol.SymbolException;
006
007 /**
008
009 @author Johan Hall
010 */
011 public class TrieNode {
012 /**
013 * Initial capacity of the hash maps.
014 */
015 // private final static int INITIAL_CAPACITY = 2;
016 /**
017 * the character that corresponds to the trie node
018 */
019 private final char character;
020 /**
021 * Maps a symbol table into an entry (if not cached)
022 */
023 private HashMap<TrieSymbolTable,Integer> entries;
024 /**
025 * Maps a symbol table (cachedKeyEntry) into an entry (cachedValueEntry), caches only the first occurrence.
026 */
027 private TrieSymbolTable cachedKeyEntry;
028 private Integer cachedValueEntry;
029
030 /**
031 * Maps a character into a child trie node (if not cached)
032 */
033 private HashMap<Character,TrieNode> children;
034 private char cachedKeyChar;
035 private TrieNode cachedValueTrieNode;
036
037 /**
038 * The parent trie node
039 */
040 private final TrieNode parent;
041
042 /**
043 * Constructs a trie node
044 *
045 * @param character which character that the trie node belongs to
046 * @param parent the parent trie node
047 */
048 public TrieNode(char character, TrieNode parent) {
049 this.character = character;
050 this.parent = parent;
051 }
052
053 /**
054 * Adds and/or retrieve a child trie node. It only adds a entry if the parameter isWord is true.
055 *
056 * @param isWord true if it is a word (entry), otherwise false
057 * @param c the character to the child node
058 * @param table which symbol table to look in or add to
059 * @param code the integer representation of the string value
060 * @return the child trie node that corresponds to the character
061 * @throws SymbolException
062 */
063 public TrieNode getOrAddChild(boolean isWord, char c, TrieSymbolTable table, int code) throws SymbolException {
064 if (cachedValueTrieNode == null) {
065 cachedValueTrieNode = new TrieNode(c, this);
066 cachedKeyChar = c;
067 if (isWord) {
068 cachedValueTrieNode.addEntry(table, code);
069 }
070 return cachedValueTrieNode;
071 } else if (cachedKeyChar == c) {
072 if (isWord) {
073 cachedValueTrieNode.addEntry(table, code);
074 }
075 return cachedValueTrieNode;
076 } else {
077 TrieNode child = null;
078 if (children == null) {
079 children = new HashMap<Character, TrieNode>();
080 // children = new HashMap<Character, TrieNode>(INITIAL_CAPACITY);
081 child = new TrieNode(c, this);
082 children.put(c,child);
083 } else {
084 child = children.get(c);
085 if (child == null) {
086 child = new TrieNode(c, this);
087 children.put(c,child);
088 }
089 }
090 if (isWord) {
091 child.addEntry(table, code);
092 }
093 return child;
094 }
095 }
096
097 /**
098 * Adds an entry if it does not exist
099 *
100 * @param table which symbol table to add an entry
101 * @param code the integer representation of the string value
102 * @throws SymbolException
103 */
104 private void addEntry(TrieSymbolTable table, int code) throws SymbolException {
105 if (table == null) {
106 throw new SymbolException("Symbol table cannot be found. ");
107 }
108 if (cachedValueEntry == null) {
109 if (code != -1) {
110 cachedValueEntry = code; //new TrieEntry(code,true);
111 table.updateValueCounter(code);
112 } else {
113 cachedValueEntry = table.increaseValueCounter(); //new TrieEntry(table.increaseValueCounter(),false);
114 }
115 cachedKeyEntry = table;
116 } else if (!table.equals(cachedKeyEntry)) {
117 if (entries == null) {
118 entries = new HashMap<TrieSymbolTable, Integer>();
119 // entries = new HashMap<TrieSymbolTable, TrieEntry>(INITIAL_CAPACITY);
120 }
121 if (!entries.containsKey(table)) {
122 if (code != -1) {
123 entries.put(table, code); //new TrieEntry(code,true));
124 table.updateValueCounter(code);
125 } else {
126 entries.put(table, table.increaseValueCounter()); //new TrieEntry(table.increaseValueCounter(),false));
127 }
128 }
129 }
130 }
131
132 /**
133 * Returns the child node that corresponds to the character
134 *
135 * @param c the character of the child node
136 * @return the child node
137 */
138 public TrieNode getChild(char c) {
139 if (cachedKeyChar == c) {
140 return cachedValueTrieNode;
141 } else if (children != null) {
142 return children.get(c);
143 }
144 return null;
145 }
146
147
148
149 /**
150 * Returns the entry of the symbol table 'table'
151 *
152 * @param table which symbol table
153 * @return the entry of the symbol table 'table'
154 */
155 public Integer getEntry(TrieSymbolTable table) {
156 if (table != null) {
157 if (table.equals(cachedKeyEntry)) {
158 return cachedValueEntry;
159 } else if (entries != null) {
160 return entries.get(table);
161 }
162 }
163 return null;
164 }
165
166 /**
167 * Returns the character of the trie node
168 *
169 * @return the character of the trie node
170 */
171 public char getCharacter() {
172 return character;
173 }
174
175 /**
176 * Returns the parent node
177 *
178 * @return the parent node
179 */
180 public TrieNode getParent() {
181 return parent;
182 }
183
184 public boolean equals(Object obj) {
185 return super.equals(obj);
186 }
187
188 public int hashCode() {
189 return super.hashCode();
190 }
191
192 public String toString() {
193 final StringBuilder sb = new StringBuilder();
194 sb.append(character);
195 return sb.toString();
196 }
197 }