Trie Node
by Isai Damier

/***************************************************************************
 * Author: Isai Damier
 * Title: Trie.java
 * Project: geekviewpoint
 * Package: datastructure
 *
 * Description:
 *  A trie is a tree data-structure that stores words by compressing common
 *  prefixes. To illustrate, following is a word list and its resulting trie.
 *
 *   WORDS: rat, rats, rattle, rate, rates, rating, can, cane,
 *          canny, cant, cans, cat, cats, cattle, cattles.
 *
 *   TRIE:
 *         ___________|____________
 *        |                        |
 *        r                        c
 *        a                ________a___________
 *        t~              |                    |
 *    ____|_____          n~                   t~
 *   |   |  |   |    _____|_____        _______|______
 *   s~  t  e~  i   |   |   |   |      |              t
 *       l  s~  n   e~  n   t~  s~     s~             l
 *       e~     g~      y~                            e~
 *                                                    s~
 *
 *   Each ~ in the figure indicates where a prefix is a word.
 *
 *   Generally, a trie has all the benefits of a hash table without
 *   any of the disadvantages.
 *
 *   --------------------------------------------------------------
 *          | HASH TABLE | TRIE     | explanations
 *   --------------------------------------------------------------
 *   Memory |    O(n)    |  < O(n)  | trie uses prefix compression.
 *          |            |          | Hence it does not store each
 *          |            |          | word explicitly
 *  ----------------------------------------------------------------
 *   Search |   O(1)     |  O(1)    | trie is technically faster.
 *          |            | pseudo-  | Given a word, computing a
 *          |            | constant | hash takes at least as long
 *          |            |          | as traversing a trie. Plus,
 *          |            |          | trie has no collision.
 *  ----------------------------------------------------------------
 *
 *  Tries are particularly superior to hash tables when it comes to solving
 *  problems such as word puzzles like boggle. In such puzzles the objective
 *  is to find how many words in a given list are valid. So if for example
 *  at a particular instance in boggle you have a list of one billion words
 *  all starting with zh-, whereas the dictionary has no words starting with
 *  zh-; then: if the dictionary is a hash table, you must compute the entire
 *  hashcode for each word and do one billion look-ups; if on the other hand
 *  the dictionary is a trie, you only do the equivalent of partially
 *  computing one hashcode! That's a saving of over one billion fold!
 *
 *  This implementations of trie uses an array to store the children
 *  nodes, where the numerical value of each char serves as index.
 **************************************************************************/ 
 /********************************************************************
 * Author: Isai Damier
 * Title: TrieNode
 * Project: geekviewpoint
 * Package: algorithms.trie
 *
 * Description:
 *  This is a very simple node class for the Trie data structure. An array
 *  is used to hold the references/pointers to the children/next nodes.
 *  The numerical value of each char serves as index. The array could be
 *
 *   TrieNode[] next = new TrieNode[256];//256 or 26 or etc.
 *
 *  Different implementation of the TrieNode presents different conveniences
 *  and restrictions. For instance, using an array as opposed to a hashmap
 *  for storing the pointers to the next nodes means not having access to
 *  a cheap isEmpty() function. Hence we must declare and track our own
 *  nextIsEmpty variable.
 *
 *  Map<Character,TrieNode> next = new HashMap<>();//map alternative
 *******************************************************************/
package algorithms.trie;

public class TrieNode {

  public char value;
  boolean word = false;
  TrieNode[] next = new TrieNode[256];
  private int nextLength = 0;

  public TrieNode(char c) {
    value = c;
  }

  void setChild(char c, TrieNode node){
    next[c]=node;
    nextLength++;
  }
  void clearNext() {
    next = new TrieNode[256];
    nextLength = 0;
  }

  boolean nextIsEmpty(){
    return nextLength == 0;
  }

  int nextSize(){
    return nextLength;
  }
}