title: Case Insensitive Ternary Search Tree
body: <p>I had been using <a href="http://en.wikipedia.org/wiki/Ternary_search_tree" rel="nofollow noreferrer">Ternary Search Tree</a> for a while, as the data structure to implement a auto complete drop down combo box. Which means, when user type "fo", the drop down combo box will display</p>
  
  <p>foo
  food
  football</p>
  
  <p>The problem is, my current used of Ternary Search Tree is case sensitive. My implementation is as follow. It had been used by real world for around 1++ yeas. Hence, I consider it as quite reliable.</p>
  
  <p><a href="http://jstock.cvs.sourceforge.net/viewvc/jstock/jstock/src/org/yccheok/jstock/engine/TernarySearchTree.java?view=markup" rel="nofollow noreferrer">My Ternary Search Tree code</a></p>
  
  <p>However, I am looking for a case insensitive Ternary Search Tree, which means, when I type "fo", the drop down combo box will show me</p>
  
  <p>foO
  Food
  fooTBall</p>
  
  <p>Here are some key interface for TST, where I hope the new case insentive TST may have similar interface too.</p>
  
  <pre><code>    /** 
   * Stores value in the TernarySearchTree. The value may be retrieved using key.
   * @param key A string that indexes the object to be stored.
   * @param value The object to be stored in the tree.
   */    
  public void put(String key, E value) {
      getOrCreateNode(key).data = value;
  }
  
  /**
   * Retrieve the object indexed by key.
   * @param key A String index.
   * @return Object The object retrieved from the TernarySearchTree.
   */
  public E get(String key) {
      TSTNode&lt;E&gt; node = getNode(key);
      if(node==null) return null;
      return node.data;
  }
  </code></pre>
  
  <p>An example of usage is as follow. TSTSearchEngine is using TernarySearchTree as the core backbone.</p>
  
  <p><a href="http://jstock.cvs.sourceforge.net/viewvc/jstock/jstock/src/org/yccheok/jstock/engine/TSTSearchEngine.java?revision=1.2&amp;view=markup" rel="nofollow noreferrer">Example usage of Ternary Search Tree</a></p>
  
  <pre><code>// There is stock named microsoft and MICROChip inside stocks ArrayList.
  TSTSearchEngine&lt;Stock&gt; engine = TSTSearchEngine&lt;Stock&gt;(stocks);
  // I wish it would return microsoft and MICROCHIP. Currently, it just return microsoft.
  List&lt;Stock&gt; results = engine.searchAll("micro"); 
  </code></pre>