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}