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