001package org.maltparser.core.symbol.trie; 002 003import org.maltparser.core.helper.HashMap; 004 005import org.maltparser.core.symbol.SymbolException; 006 007/** 008 009@author Johan Hall 010*/ 011public 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 child = new TrieNode(c, this); 081 children.put(c,child); 082 } else { 083 child = children.get(c); 084 if (child == null) { 085 child = new TrieNode(c, this); 086 children.put(c,child); 087 } 088 } 089 if (isWord) { 090 child.addEntry(table, code); 091 } 092 return child; 093 } 094 } 095 096 /** 097 * Adds an entry if it does not exist 098 * 099 * @param table which symbol table to add an entry 100 * @param code the integer representation of the string value 101 * @throws SymbolException 102 */ 103 private void addEntry(TrieSymbolTable table, int code) throws SymbolException { 104 if (table == null) { 105 throw new SymbolException("Symbol table cannot be found. "); 106 } 107 if (cachedValueEntry == null) { 108 if (code != -1) { 109 cachedValueEntry = code; 110 table.updateValueCounter(code); 111 } else { 112 cachedValueEntry = table.increaseValueCounter(); 113 } 114 cachedKeyEntry = table; 115 } else if (!table.equals(cachedKeyEntry)) { 116 if (entries == null) { 117 entries = new HashMap<TrieSymbolTable, Integer>(); 118 } 119 if (!entries.containsKey(table)) { 120 if (code != -1) { 121 entries.put(table, code); 122 table.updateValueCounter(code); 123 } else { 124 entries.put(table, table.increaseValueCounter()); 125 } 126 } 127 } 128 } 129 130 /** 131 * Returns the child node that corresponds to the character 132 * 133 * @param c the character of the child node 134 * @return the child node 135 */ 136 public TrieNode getChild(char c) { 137 if (cachedKeyChar == c) { 138 return cachedValueTrieNode; 139 } else if (children != null) { 140 return children.get(c); 141 } 142 return null; 143 } 144 145 146 147 /** 148 * Returns the entry of the symbol table 'table' 149 * 150 * @param table which symbol table 151 * @return the entry of the symbol table 'table' 152 */ 153 public Integer getEntry(TrieSymbolTable table) { 154 if (table != null) { 155 if (table.equals(cachedKeyEntry)) { 156 return cachedValueEntry; 157 } else if (entries != null) { 158 return entries.get(table); 159 } 160 } 161 return null; 162 } 163 164 /** 165 * Returns the character of the trie node 166 * 167 * @return the character of the trie node 168 */ 169 public char getCharacter() { 170 return character; 171 } 172 173 /** 174 * Returns the parent node 175 * 176 * @return the parent node 177 */ 178 public TrieNode getParent() { 179 return parent; 180 } 181 182 public boolean equals(Object obj) { 183 return super.equals(obj); 184 } 185 186 public int hashCode() { 187 return super.hashCode(); 188 } 189 190 public String toString() { 191 final StringBuilder sb = new StringBuilder(); 192 sb.append(character); 193 return sb.toString(); 194 } 195}