    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    }