lucene-java-3.4.0/lucene/contrib/spellchecker/src/java/org/apache/lucene/search/suggest/jaspell/JaspellTernarySearchTrie.java

   1 package org.apache.lucene.search.suggest.jaspell;
   2
   3 /**
   4  * Copyright (c) 2005 Bruno Martins
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  * 3. Neither the name of the organization nor the names of its contributors
  16  *    may be used to endorse or promote products derived from this software
  17  *    without specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  22  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
  23  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  29  * THE POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 import java.io.BufferedReader;
  33 import java.io.File;
  34 import java.io.FileInputStream;
  35 import java.io.IOException;
  36 import java.io.InputStreamReader;
  37 import java.util.List;
  38 import java.util.Vector;
  39 import java.util.zip.GZIPInputStream;
  40
  41 /**
  42  * Implementation of a Ternary Search Trie, a data structure for storing
  43  * <code>String</code> objects that combines the compact size of a binary search
  44  * tree with the speed of a digital search trie, and is therefore ideal for
  45  * practical use in sorting and searching data.</p>
  46  * <p>
  47  *
  48  * This data structure is faster than hashing for many typical search problems,
  49  * and supports a broader range of useful problems and operations. Ternary
  50  * searches are faster than hashing and more powerful, too.
  51  * </p>
  52  * <p>
  53  *
  54  * The theory of ternary search trees was described at a symposium in 1997 (see
  55  * "Fast Algorithms for Sorting and Searching Strings," by J.L. Bentley and R.
  56  * Sedgewick, Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete
  57  * Algorithms, January 1997). Algorithms in C, Third Edition, by Robert
  58  * Sedgewick (Addison-Wesley, 1998) provides yet another view of ternary search
  59  * trees.
  60  *
  61  * @author Bruno Martins
  62  *
  63  */
  64 public class JaspellTernarySearchTrie {
  65
  66   /**
  67    * An inner class of Ternary Search Trie that represents a node in the trie.
  68    */
  69   protected final class TSTNode {
  70
  71     /** Index values for accessing relatives array. */
  72     protected final static int PARENT = 0, LOKID = 1, EQKID = 2, HIKID = 3;
  73
  74     /** The key to the node. */
  75     protected Object data;
  76
  77     /** The relative nodes. */
  78     protected TSTNode[] relatives = new TSTNode[4];
  79
  80     /** The char used in the split. */
  81     protected char splitchar;
  82
  83     /**
  84      * Constructor method.
  85      *
  86      *@param splitchar
  87      *          The char used in the split.
  88      *@param parent
  89      *          The parent node.
  90      */
  91     protected TSTNode(char splitchar, TSTNode parent) {
  92       this.splitchar = splitchar;
  93       relatives[PARENT] = parent;
  94     }
  95   }
  96
  97   /**
  98    * Compares characters by alfabetical order.
  99    *
 100    *@param cCompare2
 101    *          The first char in the comparison.
 102    *@param cRef
 103    *          The second char in the comparison.
 104    *@return A negative number, 0 or a positive number if the second char is
 105    *         less, equal or greater.
 106    */
 107   private static int compareCharsAlphabetically(char cCompare2, char cRef) {
 108     return Character.toLowerCase(cCompare2) - Character.toLowerCase(cRef);
 109   }
 110
 111   /* what follows is the original Jaspell code.
 112   private static int compareCharsAlphabetically(int cCompare2, int cRef) {
 113     int cCompare = 0;
 114     if (cCompare2 >= 65) {
 115       if (cCompare2 < 89) {
 116         cCompare = (2 * cCompare2) - 65;
 117       } else if (cCompare2 < 97) {
 118         cCompare = cCompare2 + 24;
 119       } else if (cCompare2 < 121) {
 120         cCompare = (2 * cCompare2) - 128;
 121       } else cCompare = cCompare2;
 122     } else cCompare = cCompare2;
 123     if (cRef < 65) {
 124       return cCompare - cRef;
 125     }
 126     if (cRef < 89) {
 127       return cCompare - ((2 * cRef) - 65);
 128     }
 129     if (cRef < 97) {
 130       return cCompare - (cRef + 24);
 131     }
 132     if (cRef < 121) {
 133       return cCompare - ((2 * cRef) - 128);
 134     }
 135     return cCompare - cRef;
 136   }
 137   */
 138
 139   /**
 140    * The default number of values returned by the <code>matchAlmost</code>
 141    * method.
 142    */
 143   private int defaultNumReturnValues = -1;
 144
 145   /**
 146    * the number of differences allowed in a call to the
 147    * <code>matchAlmostKey</code> method.
 148    */
 149   private int matchAlmostDiff;
 150
 151   /** The base node in the trie. */
 152   private TSTNode rootNode;
 153
 154   /**
 155    * Constructs an empty Ternary Search Trie.
 156    */
 157   public JaspellTernarySearchTrie() {
 158   }
 159
 160   // for loading
 161   void setRoot(TSTNode newRoot) {
 162     rootNode = newRoot;
 163   }
 164
 165   // for saving
 166   TSTNode getRoot() {
 167     return rootNode;
 168   }
 169
 170   /**
 171    * Constructs a Ternary Search Trie and loads data from a <code>File</code>
 172    * into the Trie. The file is a normal text document, where each line is of
 173    * the form word TAB float.
 174    *
 175    *@param file
 176    *          The <code>File</code> with the data to load into the Trie.
 177    *@exception IOException
 178    *              A problem occured while reading the data.
 179    */
 180   public JaspellTernarySearchTrie(File file) throws IOException {
 181     this(file, false);
 182   }
 183
 184   /**
 185    * Constructs a Ternary Search Trie and loads data from a <code>File</code>
 186    * into the Trie. The file is a normal text document, where each line is of
 187    * the form "word TAB float".
 188    *
 189    *@param file
 190    *          The <code>File</code> with the data to load into the Trie.
 191    *@param compression
 192    *          If true, the file is compressed with the GZIP algorithm, and if
 193    *          false, the file is a normal text document.
 194    *@exception IOException
 195    *              A problem occured while reading the data.
 196    */
 197   public JaspellTernarySearchTrie(File file, boolean compression)
 198           throws IOException {
 199     this();
 200     BufferedReader in;
 201     if (compression)
 202       in = new BufferedReader(new InputStreamReader(new GZIPInputStream(
 203               new FileInputStream(file))));
 204     else in = new BufferedReader(new InputStreamReader((new FileInputStream(
 205             file))));
 206     String word;
 207     int pos;
 208     Float occur, one = new Float(1);
 209     int numWords = 0;
 210     while ((word = in.readLine()) != null) {
 211       numWords++;
 212       pos = word.indexOf("\t");
 213       occur = one;
 214       if (pos != -1) {
 215         occur = Float.parseFloat(word.substring(pos + 1).trim());
 216         word = word.substring(0, pos);
 217       }
 218       String key = word.toLowerCase();
 219       if (rootNode == null) {
 220         rootNode = new TSTNode(key.charAt(0), null);
 221       }
 222       TSTNode node = null;
 223       if (key.length() > 0 && rootNode != null) {
 224         TSTNode currentNode = rootNode;
 225         int charIndex = 0;
 226         while (true) {
 227           if (currentNode == null) break;
 228           int charComp = compareCharsAlphabetically(key.charAt(charIndex),
 229                   currentNode.splitchar);
 230           if (charComp == 0) {
 231             charIndex++;
 232             if (charIndex == key.length()) {
 233               node = currentNode;
 234               break;
 235             }
 236             currentNode = currentNode.relatives[TSTNode.EQKID];
 237           } else if (charComp < 0) {
 238             currentNode = currentNode.relatives[TSTNode.LOKID];
 239           } else {
 240             currentNode = currentNode.relatives[TSTNode.HIKID];
 241           }
 242         }
 243         Float occur2 = null;
 244         if (node != null) occur2 = ((Float) (node.data));
 245         if (occur2 != null) {
 246           occur += occur2.floatValue();
 247         }
 248         currentNode = getOrCreateNode(word.trim().toLowerCase());
 249         currentNode.data = occur;
 250       }
 251     }
 252     in.close();
 253   }
 254
 255   /**
 256    * Deletes the node passed in as an argument. If this node has non-null data,
 257    * then both the node and the data will be deleted. It also deletes any other
 258    * nodes in the trie that are no longer needed after the deletion of the node.
 259    *
 260    *@param nodeToDelete
 261    *          The node to delete.
 262    */
 263   private void deleteNode(TSTNode nodeToDelete) {
 264     if (nodeToDelete == null) {
 265       return;
 266     }
 267     nodeToDelete.data = null;
 268     while (nodeToDelete != null) {
 269       nodeToDelete = deleteNodeRecursion(nodeToDelete);
 270       // deleteNodeRecursion(nodeToDelete);
 271     }
 272   }
 273
 274   /**
 275    * Recursively visits each node to be deleted.
 276    *
 277    * To delete a node, first set its data to null, then pass it into this
 278    * method, then pass the node returned by this method into this method (make
 279    * sure you don't delete the data of any of the nodes returned from this
 280    * method!) and continue in this fashion until the node returned by this
 281    * method is <code>null</code>.
 282    *
 283    * The TSTNode instance returned by this method will be next node to be
 284    * operated on by <code>deleteNodeRecursion</code> (This emulates recursive
 285    * method call while avoiding the JVM overhead normally associated with a
 286    * recursive method.)
 287    *
 288    *@param currentNode
 289    *          The node to delete.
 290    *@return The next node to be called in deleteNodeRecursion.
 291    */
 292   private TSTNode deleteNodeRecursion(TSTNode currentNode) {
 293     if (currentNode == null) {
 294       return null;
 295     }
 296     if (currentNode.relatives[TSTNode.EQKID] != null
 297             || currentNode.data != null) {
 298       return null;
 299     }
 300     // can't delete this node if it has a non-null eq kid or data
 301     TSTNode currentParent = currentNode.relatives[TSTNode.PARENT];
 302     boolean lokidNull = currentNode.relatives[TSTNode.LOKID] == null;
 303     boolean hikidNull = currentNode.relatives[TSTNode.HIKID] == null;
 304     int childType;
 305     if (currentParent.relatives[TSTNode.LOKID] == currentNode) {
 306       childType = TSTNode.LOKID;
 307     } else if (currentParent.relatives[TSTNode.EQKID] == currentNode) {
 308       childType = TSTNode.EQKID;
 309     } else if (currentParent.relatives[TSTNode.HIKID] == currentNode) {
 310       childType = TSTNode.HIKID;
 311     } else {
 312       rootNode = null;
 313       return null;
 314     }
 315     if (lokidNull && hikidNull) {
 316       currentParent.relatives[childType] = null;
 317       return currentParent;
 318     }
 319     if (lokidNull) {
 320       currentParent.relatives[childType] = currentNode.relatives[TSTNode.HIKID];
 321       currentNode.relatives[TSTNode.HIKID].relatives[TSTNode.PARENT] = currentParent;
 322       return currentParent;
 323     }
 324     if (hikidNull) {
 325       currentParent.relatives[childType] = currentNode.relatives[TSTNode.LOKID];
 326       currentNode.relatives[TSTNode.LOKID].relatives[TSTNode.PARENT] = currentParent;
 327       return currentParent;
 328     }
 329     int deltaHi = currentNode.relatives[TSTNode.HIKID].splitchar
 330             - currentNode.splitchar;
 331     int deltaLo = currentNode.splitchar
 332             - currentNode.relatives[TSTNode.LOKID].splitchar;
 333     int movingKid;
 334     TSTNode targetNode;
 335     if (deltaHi == deltaLo) {
 336       if (Math.random() < 0.5) {
 337         deltaHi++;
 338       } else {
 339         deltaLo++;
 340       }
 341     }
 342     if (deltaHi > deltaLo) {
 343       movingKid = TSTNode.HIKID;
 344       targetNode = currentNode.relatives[TSTNode.LOKID];
 345     } else {
 346       movingKid = TSTNode.LOKID;
 347       targetNode = currentNode.relatives[TSTNode.HIKID];
 348     }
 349     while (targetNode.relatives[movingKid] != null) {
 350       targetNode = targetNode.relatives[movingKid];
 351     }
 352     targetNode.relatives[movingKid] = currentNode.relatives[movingKid];
 353     currentParent.relatives[childType] = targetNode;
 354     targetNode.relatives[TSTNode.PARENT] = currentParent;
 355     if (!lokidNull) {
 356       currentNode.relatives[TSTNode.LOKID] = null;
 357     }
 358     if (!hikidNull) {
 359       currentNode.relatives[TSTNode.HIKID] = null;
 360     }
 361     return currentParent;
 362   }
 363
 364   /**
 365    * Retrieve the object indexed by a key.
 366    *
 367    *@param key
 368    *          A <code>String</code> index.
 369    *@return The object retrieved from the Ternary Search Trie.
 370    */
 371   public Object get(String key) {
 372     TSTNode node = getNode(key.trim().toLowerCase());
 373     if (node == null) {
 374       return null;
 375     }
 376     return node.data;
 377   }
 378
 379   /**
 380    * Retrieve the <code>Float</code> indexed by key, increment it by one unit
 381    * and store the new <code>Float</code>.
 382    *
 383    *@param key
 384    *          A <code>String</code> index.
 385    *@return The <code>Float</code> retrieved from the Ternary Search Trie.
 386    */
 387   public Float getAndIncrement(String key) {
 388     String key2 = key.trim().toLowerCase();
 389     TSTNode node = getNode(key2);
 390     if (node == null) {
 391       return null;
 392     }
 393     Float aux = (Float) (node.data);
 394     if (aux == null) {
 395       aux = new Float(1);
 396     } else {
 397       aux = new Float(aux.intValue() + 1);
 398     }
 399     put(key2, aux);
 400     return aux;
 401   }
 402
 403   /**
 404    * Returns the key that indexes the node argument.
 405    *
 406    *@param node
 407    *          The node whose index is to be calculated.
 408    *@return The <code>String</code> that indexes the node argument.
 409    */
 410   protected String getKey(TSTNode node) {
 411     StringBuffer getKeyBuffer = new StringBuffer();
 412     getKeyBuffer.setLength(0);
 413     getKeyBuffer.append("" + node.splitchar);
 414     TSTNode currentNode;
 415     TSTNode lastNode;
 416     currentNode = node.relatives[TSTNode.PARENT];
 417     lastNode = node;
 418     while (currentNode != null) {
 419       if (currentNode.relatives[TSTNode.EQKID] == lastNode) {
 420         getKeyBuffer.append("" + currentNode.splitchar);
 421       }
 422       lastNode = currentNode;
 423       currentNode = currentNode.relatives[TSTNode.PARENT];
 424     }
 425     getKeyBuffer.reverse();
 426     return getKeyBuffer.toString();
 427   }
 428
 429   /**
 430    * Returns the node indexed by key, or <code>null</code> if that node doesn't
 431    * exist. Search begins at root node.
 432    *
 433    *@param key
 434    *          A <code>String</code> that indexes the node that is returned.
 435    *@return The node object indexed by key. This object is an instance of an
 436    *         inner class named <code>TernarySearchTrie.TSTNode</code>.
 437    */
 438   public TSTNode getNode(String key) {
 439     return getNode(key, rootNode);
 440   }
 441
 442   /**
 443    * Returns the node indexed by key, or <code>null</code> if that node doesn't
 444    * exist. The search begins at root node.
 445    *
 446    *@param key2
 447    *          A <code>String</code> that indexes the node that is returned.
 448    *@param startNode
 449    *          The top node defining the subtrie to be searched.
 450    *@return The node object indexed by key. This object is an instance of an
 451    *         inner class named <code>TernarySearchTrie.TSTNode</code>.
 452    */
 453   protected TSTNode getNode(String key2, TSTNode startNode) {
 454     String key = key2.trim().toLowerCase();
 455     if (key == null || startNode == null || key.length() == 0) {
 456       return null;
 457     }
 458     TSTNode currentNode = startNode;
 459     int charIndex = 0;
 460     while (true) {
 461       if (currentNode == null) {
 462         return null;
 463       }
 464       int charComp = compareCharsAlphabetically(key.charAt(charIndex),
 465               currentNode.splitchar);
 466       if (charComp == 0) {
 467         charIndex++;
 468         if (charIndex == key.length()) {
 469           return currentNode;
 470         }
 471         currentNode = currentNode.relatives[TSTNode.EQKID];
 472       } else if (charComp < 0) {
 473         currentNode = currentNode.relatives[TSTNode.LOKID];
 474       } else {
 475         currentNode = currentNode.relatives[TSTNode.HIKID];
 476       }
 477     }
 478   }
 479
 480   /**
 481    * Returns the node indexed by key, creating that node if it doesn't exist,
 482    * and creating any required intermediate nodes if they don't exist.
 483    *
 484    *@param key
 485    *          A <code>String</code> that indexes the node that is returned.
 486    *@return The node object indexed by key. This object is an instance of an
 487    *         inner class named <code>TernarySearchTrie.TSTNode</code>.
 488    *@exception NullPointerException
 489    *              If the key is <code>null</code>.
 490    *@exception IllegalArgumentException
 491    *              If the key is an empty <code>String</code>.
 492    */
 493   protected TSTNode getOrCreateNode(String key) throws NullPointerException,
 494           IllegalArgumentException {
 495     if (key == null) {
 496       throw new NullPointerException(
 497               "attempt to get or create node with null key");
 498     }
 499     if (key.length() == 0) {
 500       throw new IllegalArgumentException(
 501               "attempt to get or create node with key of zero length");
 502     }
 503     if (rootNode == null) {
 504       rootNode = new TSTNode(key.charAt(0), null);
 505     }
 506     TSTNode currentNode = rootNode;
 507     int charIndex = 0;
 508     while (true) {
 509       int charComp = compareCharsAlphabetically(key.charAt(charIndex),
 510               currentNode.splitchar);
 511       if (charComp == 0) {
 512         charIndex++;
 513         if (charIndex == key.length()) {
 514           return currentNode;
 515         }
 516         if (currentNode.relatives[TSTNode.EQKID] == null) {
 517           currentNode.relatives[TSTNode.EQKID] = new TSTNode(key
 518                   .charAt(charIndex), currentNode);
 519         }
 520         currentNode = currentNode.relatives[TSTNode.EQKID];
 521       } else if (charComp < 0) {
 522         if (currentNode.relatives[TSTNode.LOKID] == null) {
 523           currentNode.relatives[TSTNode.LOKID] = new TSTNode(key
 524                   .charAt(charIndex), currentNode);
 525         }
 526         currentNode = currentNode.relatives[TSTNode.LOKID];
 527       } else {
 528         if (currentNode.relatives[TSTNode.HIKID] == null) {
 529           currentNode.relatives[TSTNode.HIKID] = new TSTNode(key
 530                   .charAt(charIndex), currentNode);
 531         }
 532         currentNode = currentNode.relatives[TSTNode.HIKID];
 533       }
 534     }
 535   }
 536
 537   /**
 538    * Returns a <code>List</code> of keys that almost match the argument key.
 539    * Keys returned will have exactly diff characters that do not match the
 540    * target key, where diff is equal to the last value passed in as an argument
 541    * to the <code>setMatchAlmostDiff</code> method.
 542    * <p>
 543    * If the <code>matchAlmost</code> method is called before the
 544    * <code>setMatchAlmostDiff</code> method has been called for the first time,
 545    * then diff = 0.
 546    *
 547    *@param key
 548    *          The target key.
 549    *@return A <code>List</code> with the results.
 550    */
 551   public List<String> matchAlmost(String key) {
 552     return matchAlmost(key, defaultNumReturnValues);
 553   }
 554
 555   /**
 556    * Returns a <code>List</code> of keys that almost match the argument key.
 557    * Keys returned will have exactly diff characters that do not match the
 558    * target key, where diff is equal to the last value passed in as an argument
 559    * to the <code>setMatchAlmostDiff</code> method.
 560    * <p>
 561    * If the <code>matchAlmost</code> method is called before the
 562    * <code>setMatchAlmostDiff</code> method has been called for the first time,
 563    * then diff = 0.
 564    *
 565    *@param key
 566    *          The target key.
 567    *@param numReturnValues
 568    *          The maximum number of values returned by this method.
 569    *@return A <code>List</code> with the results
 570    */
 571   public List<String> matchAlmost(String key, int numReturnValues) {
 572     return matchAlmostRecursion(rootNode, 0, matchAlmostDiff, key,
 573             ((numReturnValues < 0) ? -1 : numReturnValues), new Vector<String>(), false);
 574   }
 575
 576   /**
 577    * Recursivelly vists the nodes in order to find the ones that almost match a
 578    * given key.
 579    *
 580    *@param currentNode
 581    *          The current node.
 582    *@param charIndex
 583    *          The current char.
 584    *@param d
 585    *          The number of differences so far.
 586    *@param matchAlmostNumReturnValues
 587    *          The maximum number of values in the result <code>List</code>.
 588    *@param matchAlmostResult2
 589    *          The results so far.
 590    *@param upTo
 591    *          If true all keys having up to and including matchAlmostDiff
 592    *          mismatched letters will be included in the result (including a key
 593    *          that is exactly the same as the target string) otherwise keys will
 594    *          be included in the result only if they have exactly
 595    *          matchAlmostDiff number of mismatched letters.
 596    *@param matchAlmostKey
 597    *          The key being searched.
 598    *@return A <code>List</code> with the results.
 599    */
 600   private List<String> matchAlmostRecursion(TSTNode currentNode, int charIndex,
 601           int d, String matchAlmostKey, int matchAlmostNumReturnValues,
 602           List<String> matchAlmostResult2, boolean upTo) {
 603     if ((currentNode == null)
 604             || (matchAlmostNumReturnValues != -1 && matchAlmostResult2.size() >= matchAlmostNumReturnValues)
 605             || (d < 0) || (charIndex >= matchAlmostKey.length())) {
 606       return matchAlmostResult2;
 607     }
 608     int charComp = compareCharsAlphabetically(matchAlmostKey.charAt(charIndex),
 609             currentNode.splitchar);
 610     List<String> matchAlmostResult = matchAlmostResult2;
 611     if ((d > 0) || (charComp < 0)) {
 612       matchAlmostResult = matchAlmostRecursion(
 613               currentNode.relatives[TSTNode.LOKID], charIndex, d,
 614               matchAlmostKey, matchAlmostNumReturnValues, matchAlmostResult,
 615               upTo);
 616     }
 617     int nextD = (charComp == 0) ? d : d - 1;
 618     boolean cond = (upTo) ? (nextD >= 0) : (nextD == 0);
 619     if ((matchAlmostKey.length() == charIndex + 1) && cond
 620             && (currentNode.data != null)) {
 621       matchAlmostResult.add(getKey(currentNode));
 622     }
 623     matchAlmostResult = matchAlmostRecursion(
 624             currentNode.relatives[TSTNode.EQKID], charIndex + 1, nextD,
 625             matchAlmostKey, matchAlmostNumReturnValues, matchAlmostResult, upTo);
 626     if ((d > 0) || (charComp > 0)) {
 627       matchAlmostResult = matchAlmostRecursion(
 628               currentNode.relatives[TSTNode.HIKID], charIndex, d,
 629               matchAlmostKey, matchAlmostNumReturnValues, matchAlmostResult,
 630               upTo);
 631     }
 632     return matchAlmostResult;
 633   }
 634
 635   /**
 636    * Returns an alphabetical <code>List</code> of all keys in the trie that
 637    * begin with a given prefix. Only keys for nodes having non-null data are
 638    * included in the <code>List</code>.
 639    *
 640    *@param prefix
 641    *          Each key returned from this method will begin with the characters
 642    *          in prefix.
 643    *@return A <code>List</code> with the results.
 644    */
 645   public List<String> matchPrefix(String prefix) {
 646     return matchPrefix(prefix, defaultNumReturnValues);
 647   }
 648
 649   /**
 650    * Returns an alphabetical <code>List</code> of all keys in the trie that
 651    * begin with a given prefix. Only keys for nodes having non-null data are
 652    * included in the <code>List</code>.
 653    *
 654    *@param prefix
 655    *          Each key returned from this method will begin with the characters
 656    *          in prefix.
 657    *@param numReturnValues
 658    *          The maximum number of values returned from this method.
 659    *@return A <code>List</code> with the results
 660    */
 661   public List<String> matchPrefix(String prefix, int numReturnValues) {
 662     Vector<String> sortKeysResult = new Vector<String>();
 663     TSTNode startNode = getNode(prefix);
 664     if (startNode == null) {
 665       return sortKeysResult;
 666     }
 667     if (startNode.data != null) {
 668       sortKeysResult.addElement(getKey(startNode));
 669     }
 670     return sortKeysRecursion(startNode.relatives[TSTNode.EQKID],
 671             ((numReturnValues < 0) ? -1 : numReturnValues), sortKeysResult);
 672   }
 673
 674   /**
 675    * Returns the number of nodes in the trie that have non-null data.
 676    *
 677    *@return The number of nodes in the trie that have non-null data.
 678    */
 679   public int numDataNodes() {
 680     return numDataNodes(rootNode);
 681   }
 682
 683   /**
 684    * Returns the number of nodes in the subtrie below and including the starting
 685    * node. The method counts only nodes that have non-null data.
 686    *
 687    *@param startingNode
 688    *          The top node of the subtrie. the node that defines the subtrie.
 689    *@return The total number of nodes in the subtrie.
 690    */
 691   protected int numDataNodes(TSTNode startingNode) {
 692     return recursiveNodeCalculator(startingNode, true, 0);
 693   }
 694
 695   /**
 696    * Returns the total number of nodes in the trie. The method counts nodes
 697    * whether or not they have data.
 698    *
 699    *@return The total number of nodes in the trie.
 700    */
 701   public int numNodes() {
 702     return numNodes(rootNode);
 703   }
 704
 705   /**
 706    * Returns the total number of nodes in the subtrie below and including the
 707    * starting Node. The method counts nodes whether or not they have data.
 708    *
 709    *@param startingNode
 710    *          The top node of the subtrie. The node that defines the subtrie.
 711    *@return The total number of nodes in the subtrie.
 712    */
 713   protected int numNodes(TSTNode startingNode) {
 714     return recursiveNodeCalculator(startingNode, false, 0);
 715   }
 716
 717   /**
 718    * Stores a value in the trie. The value may be retrieved using the key.
 719    *
 720    *@param key
 721    *          A <code>String</code> that indexes the object to be stored.
 722    *@param value
 723    *          The object to be stored in the Trie.
 724    */
 725   public void put(String key, Object value) {
 726     getOrCreateNode(key.trim().toLowerCase()).data = value;
 727   }
 728
 729   /**
 730    * Recursivelly visists each node to calculate the number of nodes.
 731    *
 732    *@param currentNode
 733    *          The current node.
 734    *@param checkData
 735    *          If true we check the data to be different of <code>null</code>.
 736    *@param numNodes2
 737    *          The number of nodes so far.
 738    *@return The number of nodes accounted.
 739    */
 740   private int recursiveNodeCalculator(TSTNode currentNode, boolean checkData,
 741           int numNodes2) {
 742     if (currentNode == null) {
 743       return numNodes2;
 744     }
 745     int numNodes = recursiveNodeCalculator(
 746             currentNode.relatives[TSTNode.LOKID], checkData, numNodes2);
 747     numNodes = recursiveNodeCalculator(currentNode.relatives[TSTNode.EQKID],
 748             checkData, numNodes);
 749     numNodes = recursiveNodeCalculator(currentNode.relatives[TSTNode.HIKID],
 750             checkData, numNodes);
 751     if (checkData) {
 752       if (currentNode.data != null) {
 753         numNodes++;
 754       }
 755     } else {
 756       numNodes++;
 757     }
 758     return numNodes;
 759   }
 760
 761   /**
 762    * Removes the value indexed by key. Also removes all nodes that are rendered
 763    * unnecessary by the removal of this data.
 764    *
 765    *@param key
 766    *          A <code>string</code> that indexes the object to be removed from
 767    *          the Trie.
 768    */
 769   public void remove(String key) {
 770     deleteNode(getNode(key.trim().toLowerCase()));
 771   }
 772
 773   /**
 774    * Sets the number of characters by which words can differ from target word
 775    * when calling the <code>matchAlmost</code> method.
 776    * <p>
 777    * Arguments less than 0 will set the char difference to 0, and arguments
 778    * greater than 3 will set the char difference to 3.
 779    *
 780    *@param diff
 781    *          The number of characters by which words can differ from target
 782    *          word.
 783    */
 784   public void setMatchAlmostDiff(int diff) {
 785     if (diff < 0) {
 786       matchAlmostDiff = 0;
 787     } else if (diff > 3) {
 788       matchAlmostDiff = 3;
 789     } else {
 790       matchAlmostDiff = diff;
 791     }
 792   }
 793
 794   /**
 795    * Sets the default maximum number of values returned from the
 796    * <code>matchPrefix</code> and <code>matchAlmost</code> methods.
 797    * <p>
 798    * The value should be set this to -1 to get an unlimited number of return
 799    * values. note that the methods mentioned above provide overloaded versions
 800    * that allow you to specify the maximum number of return values, in which
 801    * case this value is temporarily overridden.
 802    *
 803    **@param num
 804    *          The number of values that will be returned when calling the
 805    *          methods above.
 806    */
 807   public void setNumReturnValues(int num) {
 808     defaultNumReturnValues = (num < 0) ? -1 : num;
 809   }
 810
 811   /**
 812    * Returns keys sorted in alphabetical order. This includes the start Node and
 813    * all nodes connected to the start Node.
 814    * <p>
 815    * The number of keys returned is limited to numReturnValues. To get a list
 816    * that isn't limited in size, set numReturnValues to -1.
 817    *
 818    *@param startNode
 819    *          The top node defining the subtrie to be searched.
 820    *@param numReturnValues
 821    *          The maximum number of values returned from this method.
 822    *@return A <code>List</code> with the results.
 823    */
 824   protected List<String> sortKeys(TSTNode startNode, int numReturnValues) {
 825     return sortKeysRecursion(startNode, ((numReturnValues < 0) ? -1
 826             : numReturnValues), new Vector<String>());
 827   }
 828
 829   /**
 830    * Returns keys sorted in alphabetical order. This includes the current Node
 831    * and all nodes connected to the current Node.
 832    * <p>
 833    * Sorted keys will be appended to the end of the resulting <code>List</code>.
 834    * The result may be empty when this method is invoked, but may not be
 835    * <code>null</code>.
 836    *
 837    *@param currentNode
 838    *          The current node.
 839    *@param sortKeysNumReturnValues
 840    *          The maximum number of values in the result.
 841    *@param sortKeysResult2
 842    *          The results so far.
 843    *@return A <code>List</code> with the results.
 844    */
 845   private List<String> sortKeysRecursion(TSTNode currentNode,
 846           int sortKeysNumReturnValues, List<String> sortKeysResult2) {
 847     if (currentNode == null) {
 848       return sortKeysResult2;
 849     }
 850     List<String> sortKeysResult = sortKeysRecursion(
 851             currentNode.relatives[TSTNode.LOKID], sortKeysNumReturnValues,
 852             sortKeysResult2);
 853     if (sortKeysNumReturnValues != -1
 854             && sortKeysResult.size() >= sortKeysNumReturnValues) {
 855       return sortKeysResult;
 856     }
 857     if (currentNode.data != null) {
 858       sortKeysResult.add(getKey(currentNode));
 859     }
 860     sortKeysResult = sortKeysRecursion(currentNode.relatives[TSTNode.EQKID],
 861             sortKeysNumReturnValues, sortKeysResult);
 862     return sortKeysRecursion(currentNode.relatives[TSTNode.HIKID],
 863             sortKeysNumReturnValues, sortKeysResult);
 864   }
 865
 866 }