/*
 * Copyright (c) 2005 Bruno Martins
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the organization nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
 * THE POSSIBILITY OF SUCH DAMAGE.
 */
package org.apache.solr.spelling.suggest.jaspell;

import java.io.BufferedReader;
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.List;
import java.util.Locale;
import java.util.zip.GZIPInputStream;
import org.apache.lucene.util.Accountable;
import org.apache.lucene.util.IOUtils;
import org.apache.lucene.util.RamUsageEstimator;

/**
 * Implementation of a Ternary Search Trie, a data structure for storing <code>String</code> objects
 * that combines the compact size of a binary search tree with the speed of a digital search trie,
 * and is therefore ideal for practical use in sorting and searching data.
 *
 * <p>This data structure is faster than hashing for many typical search problems, and supports a
 * broader range of useful problems and operations. Ternary searches are faster than hashing and
 * more powerful, too.
 *
 * <p>The theory of ternary search trees was described at a symposium in 1997 (see "Fast Algorithms
 * for Sorting and Searching Strings," by J.L. Bentley and R. Sedgewick, Proceedings of the 8th
 * Annual ACM-SIAM Symposium on Discrete Algorithms, January 1997). Algorithms in C, Third Edition,
 * by Robert Sedgewick (Addison-Wesley, 1998) provides yet another view of ternary search trees.
 *
 * @deprecated Migrate to one of the newer suggesters which are much more RAM efficient.
 */
@Deprecated
public class JaspellTernarySearchTrie implements Accountable {

  /** An inner class of Ternary Search Trie that represents a node in the trie. */
  protected static final class TSTNode implements Accountable {

    /** Index values for accessing relatives array. */
    static final int PARENT = 0, LOKID = 1, EQKID = 2, HIKID = 3;

    /** The key to the node. */
    Object data;

    /** The relative nodes. */
    final TSTNode[] relatives = new TSTNode[4];

    /** The char used in the split. */
    char splitchar;

    /**
     * Constructor method.
     *
     * @param splitchar The char used in the split.
     * @param parent The parent node.
     */
    TSTNode(char splitchar, TSTNode parent) {
      this.splitchar = splitchar;
      relatives[PARENT] = parent;
    }

    @Override
    public long ramBytesUsed() {
      long mem = RamUsageEstimator.shallowSizeOf(this) + RamUsageEstimator.shallowSizeOf(relatives);
      // We don't need to add parent since our parent added itself:
      for (int i = 1; i < 4; i++) {
        TSTNode node = relatives[i];
        if (node != null) {
          mem += node.ramBytesUsed();
        }
      }
      return mem;
    }
  }

  /**
   * Compares characters by alphabetical order.
   *
   * @param cCompare2 The first char in the comparison.
   * @param cRef The second char in the comparison.
   * @return A negative number, 0 or a positive number if the second char is less, equal or greater.
   */
  private static int compareCharsAlphabetically(char cCompare2, char cRef) {
    return Character.toLowerCase(cCompare2) - Character.toLowerCase(cRef);
  }

  /* what follows is the original Jaspell code.
  private static int compareCharsAlphabetically(int cCompare2, int cRef) {
    int cCompare = 0;
    if (cCompare2 >= 65) {
      if (cCompare2 < 89) {
        cCompare = (2 * cCompare2) - 65;
      } else if (cCompare2 < 97) {
        cCompare = cCompare2 + 24;
      } else if (cCompare2 < 121) {
        cCompare = (2 * cCompare2) - 128;
      } else cCompare = cCompare2;
    } else cCompare = cCompare2;
    if (cRef < 65) {
      return cCompare - cRef;
    }
    if (cRef < 89) {
      return cCompare - ((2 * cRef) - 65);
    }
    if (cRef < 97) {
      return cCompare - (cRef + 24);
    }
    if (cRef < 121) {
      return cCompare - ((2 * cRef) - 128);
    }
    return cCompare - cRef;
  }
  */

  /** The default number of values returned by the <code>matchAlmost</code> method. */
  private int defaultNumReturnValues = -1;

  /** the number of differences allowed in a call to the <code>matchAlmostKey</code> method. */
  private int matchAlmostDiff;

  /** The base node in the trie. */
  private TSTNode rootNode;

  private final Locale locale;

  /** Constructs an empty Ternary Search Trie. */
  public JaspellTernarySearchTrie() {
    this(Locale.ROOT);
  }

  /** Constructs an empty Ternary Search Trie, specifying the Locale used for lowercasing. */
  public JaspellTernarySearchTrie(Locale locale) {
    this.locale = locale;
  }

  // for loading
  void setRoot(TSTNode newRoot) {
    rootNode = newRoot;
  }

  // for saving
  TSTNode getRoot() {
    return rootNode;
  }

  /**
   * Constructs a Ternary Search Trie and loads data from a <code>Path</code> into the Trie. The
   * file is a normal text document, where each line is of the form word TAB float.
   *
   * @param file The <code>Path</code> with the data to load into the Trie.
   * @exception IOException A problem occurred while reading the data.
   */
  public JaspellTernarySearchTrie(Path file) throws IOException {
    this(file, false);
  }

  /**
   * Constructs a Ternary Search Trie and loads data from a <code>File</code> into the Trie. The
   * file is a normal text document, where each line is of the form "word TAB float".
   *
   * @param file The <code>File</code> with the data to load into the Trie.
   * @param compression If true, the file is compressed with the GZIP algorithm, and if false, the
   *     file is a normal text document.
   * @exception IOException A problem occurred while reading the data.
   */
  public JaspellTernarySearchTrie(Path file, boolean compression) throws IOException {
    this();
    BufferedReader in;
    if (compression)
      in =
          new BufferedReader(
              IOUtils.getDecodingReader(
                  new GZIPInputStream(Files.newInputStream(file)), StandardCharsets.UTF_8));
    else in = Files.newBufferedReader(file, StandardCharsets.UTF_8);
    try {
      String word;
      int pos;
      Float occur, one = 1f;
      while ((word = in.readLine()) != null) {
        pos = word.indexOf('\t');
        occur = one;
        if (pos != -1) {
          occur = Float.parseFloat(word.substring(pos + 1).trim());
          word = word.substring(0, pos);
        }
        String key = word.toLowerCase(locale);
        if (rootNode == null) {
          rootNode = new TSTNode(key.charAt(0), null);
        }
        TSTNode node = null;
        if (key.length() > 0 && rootNode != null) {
          TSTNode currentNode = rootNode;
          int charIndex = 0;
          while (true) {
            if (currentNode == null) break;
            int charComp = compareCharsAlphabetically(key.charAt(charIndex), currentNode.splitchar);
            if (charComp == 0) {
              charIndex++;
              if (charIndex == key.length()) {
                node = currentNode;
                break;
              }
              currentNode = currentNode.relatives[TSTNode.EQKID];
            } else if (charComp < 0) {
              currentNode = currentNode.relatives[TSTNode.LOKID];
            } else {
              currentNode = currentNode.relatives[TSTNode.HIKID];
            }
          }
          Float occur2 = null;
          if (node != null) occur2 = ((Float) (node.data));
          if (occur2 != null) {
            occur += occur2.floatValue();
          }
          currentNode = getOrCreateNode(word.trim().toLowerCase(locale));
          currentNode.data = occur;
        }
      }
    } finally {
      IOUtils.close(in);
    }
  }

  /**
   * Deletes the node passed in as an argument. If this node has non-null data, then both the node
   * and the data will be deleted. It also deletes any other nodes in the trie that are no longer
   * needed after the deletion of the node.
   *
   * @param nodeToDelete The node to delete.
   */
  private void deleteNode(TSTNode nodeToDelete) {
    if (nodeToDelete == null) {
      return;
    }
    nodeToDelete.data = null;
    while (nodeToDelete != null) {
      nodeToDelete = deleteNodeRecursion(nodeToDelete);
      // deleteNodeRecursion(nodeToDelete);
    }
  }

  /**
   * Recursively visits each node to be deleted.
   *
   * <p>To delete a node, first set its data to null, then pass it into this method, then pass the
   * node returned by this method into this method (make sure you don't delete the data of any of
   * the nodes returned from this method!) and continue in this fashion until the node returned by
   * this method is <code>null</code>.
   *
   * <p>The TSTNode instance returned by this method will be next node to be operated on by <code>
   * deleteNodeRecursion</code> (This emulates recursive method call while avoiding the JVM overhead
   * normally associated with a recursive method.)
   *
   * @param currentNode The node to delete.
   * @return The next node to be called in deleteNodeRecursion.
   */
  private TSTNode deleteNodeRecursion(TSTNode currentNode) {
    if (currentNode == null) {
      return null;
    }
    if (currentNode.relatives[TSTNode.EQKID] != null || currentNode.data != null) {
      return null;
    }
    // can't delete this node if it has a non-null eq kid or data
    TSTNode currentParent = currentNode.relatives[TSTNode.PARENT];
    boolean lokidNull = currentNode.relatives[TSTNode.LOKID] == null;
    boolean hikidNull = currentNode.relatives[TSTNode.HIKID] == null;
    int childType;
    if (currentParent.relatives[TSTNode.LOKID] == currentNode) {
      childType = TSTNode.LOKID;
    } else if (currentParent.relatives[TSTNode.EQKID] == currentNode) {
      childType = TSTNode.EQKID;
    } else if (currentParent.relatives[TSTNode.HIKID] == currentNode) {
      childType = TSTNode.HIKID;
    } else {
      rootNode = null;
      return null;
    }
    if (lokidNull && hikidNull) {
      currentParent.relatives[childType] = null;
      return currentParent;
    }
    if (lokidNull) {
      currentParent.relatives[childType] = currentNode.relatives[TSTNode.HIKID];
      currentNode.relatives[TSTNode.HIKID].relatives[TSTNode.PARENT] = currentParent;
      return currentParent;
    }
    if (hikidNull) {
      currentParent.relatives[childType] = currentNode.relatives[TSTNode.LOKID];
      currentNode.relatives[TSTNode.LOKID].relatives[TSTNode.PARENT] = currentParent;
      return currentParent;
    }
    int deltaHi = currentNode.relatives[TSTNode.HIKID].splitchar - currentNode.splitchar;
    int deltaLo = currentNode.splitchar - currentNode.relatives[TSTNode.LOKID].splitchar;
    int movingKid;
    TSTNode targetNode;
    if (deltaHi == deltaLo) {
      if (Math.random() < 0.5) {
        deltaHi++;
      } else {
        deltaLo++;
      }
    }
    if (deltaHi > deltaLo) {
      movingKid = TSTNode.HIKID;
      targetNode = currentNode.relatives[TSTNode.LOKID];
    } else {
      movingKid = TSTNode.LOKID;
      targetNode = currentNode.relatives[TSTNode.HIKID];
    }
    while (targetNode.relatives[movingKid] != null) {
      targetNode = targetNode.relatives[movingKid];
    }
    targetNode.relatives[movingKid] = currentNode.relatives[movingKid];
    currentParent.relatives[childType] = targetNode;
    targetNode.relatives[TSTNode.PARENT] = currentParent;
    if (!lokidNull) {
      currentNode.relatives[TSTNode.LOKID] = null;
    }
    if (!hikidNull) {
      currentNode.relatives[TSTNode.HIKID] = null;
    }
    return currentParent;
  }

  /**
   * Retrieve the object indexed by a key.
   *
   * @param key A <code>String</code> index.
   * @return The object retrieved from the Ternary Search Trie.
   */
  public Object get(CharSequence key) {
    TSTNode node = getNode(key);
    if (node == null) {
      return null;
    }
    return node.data;
  }

  /**
   * Retrieve the <code>Float</code> indexed by key, increment it by one unit and store the new
   * <code>Float</code>.
   *
   * @param key A <code>String</code> index.
   * @return The <code>Float</code> retrieved from the Ternary Search Trie.
   */
  public Float getAndIncrement(String key) {
    String key2 = key.trim().toLowerCase(locale);
    TSTNode node = getNode(key2);
    if (node == null) {
      return null;
    }
    Float aux = (Float) (node.data);
    if (aux == null) {
      aux = 1f;
    } else {
      aux = (float) (aux.intValue() + 1);
    }
    put(key2, aux);
    return aux;
  }

  /**
   * Returns the key that indexes the node argument.
   *
   * @param node The node whose index is to be calculated.
   * @return The <code>String</code> that indexes the node argument.
   */
  protected String getKey(TSTNode node) {
    StringBuilder getKeyBuffer = new StringBuilder();
    getKeyBuffer.setLength(0);
    getKeyBuffer.append("").append(node.splitchar);
    TSTNode currentNode;
    TSTNode lastNode;
    currentNode = node.relatives[TSTNode.PARENT];
    lastNode = node;
    while (currentNode != null) {
      if (currentNode.relatives[TSTNode.EQKID] == lastNode) {
        getKeyBuffer.append("").append(currentNode.splitchar);
      }
      lastNode = currentNode;
      currentNode = currentNode.relatives[TSTNode.PARENT];
    }
    getKeyBuffer.reverse();
    return getKeyBuffer.toString();
  }

  /**
   * Returns the node indexed by key, or <code>null</code> if that node doesn't exist. Search begins
   * at root node.
   *
   * @param key A <code>String</code> that indexes the node that is returned.
   * @return The node object indexed by key. This object is an instance of an inner class named
   *     <code>TernarySearchTrie.TSTNode</code>.
   */
  public TSTNode getNode(CharSequence key) {
    return getNode(key, rootNode);
  }

  /**
   * Returns the node indexed by key, or <code>null</code> if that node doesn't exist. The search
   * begins at root node.
   *
   * @param key A <code>String</code> that indexes the node that is returned.
   * @param startNode The top node defining the subtrie to be searched.
   * @return The node object indexed by key. This object is an instance of an inner class named
   *     <code>TernarySearchTrie.TSTNode</code>.
   */
  protected TSTNode getNode(CharSequence key, TSTNode startNode) {
    if (key == null || startNode == null || key.length() == 0) {
      return null;
    }
    TSTNode currentNode = startNode;
    int charIndex = 0;
    while (true) {
      if (currentNode == null) {
        return null;
      }
      int charComp = compareCharsAlphabetically(key.charAt(charIndex), currentNode.splitchar);
      if (charComp == 0) {
        charIndex++;
        if (charIndex == key.length()) {
          return currentNode;
        }
        currentNode = currentNode.relatives[TSTNode.EQKID];
      } else if (charComp < 0) {
        currentNode = currentNode.relatives[TSTNode.LOKID];
      } else {
        currentNode = currentNode.relatives[TSTNode.HIKID];
      }
    }
  }

  /**
   * Returns the node indexed by key, creating that node if it doesn't exist, and creating any
   * required intermediate nodes if they don't exist.
   *
   * @param key A <code>String</code> that indexes the node that is returned.
   * @return The node object indexed by key. This object is an instance of an inner class named
   *     <code>TernarySearchTrie.TSTNode</code>.
   * @exception NullPointerException If the key is <code>null</code>.
   * @exception IllegalArgumentException If the key is an empty <code>String</code>.
   */
  protected TSTNode getOrCreateNode(CharSequence key)
      throws NullPointerException, IllegalArgumentException {
    if (key == null) {
      throw new NullPointerException("attempt to get or create node with null key");
    }
    if (key.length() == 0) {
      throw new IllegalArgumentException("attempt to get or create node with key of zero length");
    }
    if (rootNode == null) {
      rootNode = new TSTNode(key.charAt(0), null);
    }
    TSTNode currentNode = rootNode;
    int charIndex = 0;
    while (true) {
      int charComp = compareCharsAlphabetically(key.charAt(charIndex), currentNode.splitchar);
      if (charComp == 0) {
        charIndex++;
        if (charIndex == key.length()) {
          return currentNode;
        }
        if (currentNode.relatives[TSTNode.EQKID] == null) {
          currentNode.relatives[TSTNode.EQKID] = new TSTNode(key.charAt(charIndex), currentNode);
        }
        currentNode = currentNode.relatives[TSTNode.EQKID];
      } else if (charComp < 0) {
        if (currentNode.relatives[TSTNode.LOKID] == null) {
          currentNode.relatives[TSTNode.LOKID] = new TSTNode(key.charAt(charIndex), currentNode);
        }
        currentNode = currentNode.relatives[TSTNode.LOKID];
      } else {
        if (currentNode.relatives[TSTNode.HIKID] == null) {
          currentNode.relatives[TSTNode.HIKID] = new TSTNode(key.charAt(charIndex), currentNode);
        }
        currentNode = currentNode.relatives[TSTNode.HIKID];
      }
    }
  }

  /**
   * Returns a <code>List</code> of keys that almost match the argument key. Keys returned will have
   * exactly diff characters that do not match the target key, where diff is equal to the last value
   * passed in as an argument to the <code>setMatchAlmostDiff</code> method.
   *
   * <p>If the <code>matchAlmost</code> method is called before the <code>setMatchAlmostDiff</code>
   * method has been called for the first time, then diff = 0.
   *
   * @param key The target key.
   * @return A <code>List</code> with the results.
   */
  public List<String> matchAlmost(String key) {
    return matchAlmost(key, defaultNumReturnValues);
  }

  /**
   * Returns a <code>List</code> of keys that almost match the argument key. Keys returned will have
   * exactly diff characters that do not match the target key, where diff is equal to the last value
   * passed in as an argument to the <code>setMatchAlmostDiff</code> method.
   *
   * <p>If the <code>matchAlmost</code> method is called before the <code>setMatchAlmostDiff</code>
   * method has been called for the first time, then diff = 0.
   *
   * @param key The target key.
   * @param numReturnValues The maximum number of values returned by this method.
   * @return A <code>List</code> with the results
   */
  public List<String> matchAlmost(CharSequence key, int numReturnValues) {
    return matchAlmostRecursion(
        rootNode,
        0,
        matchAlmostDiff,
        key,
        ((numReturnValues < 0) ? -1 : numReturnValues),
        new ArrayList<>(),
        false);
  }

  /**
   * Recursivelly vists the nodes in order to find the ones that almost match a given key.
   *
   * @param currentNode The current node.
   * @param charIndex The current char.
   * @param d The number of differences so far.
   * @param matchAlmostNumReturnValues The maximum number of values in the result <code>List</code>.
   * @param matchAlmostResult2 The results so far.
   * @param upTo If true all keys having up to and including matchAlmostDiff mismatched letters will
   *     be included in the result (including a key that is exactly the same as the target string)
   *     otherwise keys will be included in the result only if they have exactly matchAlmostDiff
   *     number of mismatched letters.
   * @param matchAlmostKey The key being searched.
   * @return A <code>List</code> with the results.
   */
  private List<String> matchAlmostRecursion(
      TSTNode currentNode,
      int charIndex,
      int d,
      CharSequence matchAlmostKey,
      int matchAlmostNumReturnValues,
      List<String> matchAlmostResult2,
      boolean upTo) {
    if ((currentNode == null)
        || (matchAlmostNumReturnValues != -1
            && matchAlmostResult2.size() >= matchAlmostNumReturnValues)
        || (d < 0)
        || (charIndex >= matchAlmostKey.length())) {
      return matchAlmostResult2;
    }
    int charComp =
        compareCharsAlphabetically(matchAlmostKey.charAt(charIndex), currentNode.splitchar);
    List<String> matchAlmostResult = matchAlmostResult2;
    if ((d > 0) || (charComp < 0)) {
      matchAlmostResult =
          matchAlmostRecursion(
              currentNode.relatives[TSTNode.LOKID],
              charIndex,
              d,
              matchAlmostKey,
              matchAlmostNumReturnValues,
              matchAlmostResult,
              upTo);
    }
    int nextD = (charComp == 0) ? d : d - 1;
    boolean cond = (upTo) ? (nextD >= 0) : (nextD == 0);
    if ((matchAlmostKey.length() == charIndex + 1) && cond && (currentNode.data != null)) {
      matchAlmostResult.add(getKey(currentNode));
    }
    matchAlmostResult =
        matchAlmostRecursion(
            currentNode.relatives[TSTNode.EQKID],
            charIndex + 1,
            nextD,
            matchAlmostKey,
            matchAlmostNumReturnValues,
            matchAlmostResult,
            upTo);
    if ((d > 0) || (charComp > 0)) {
      matchAlmostResult =
          matchAlmostRecursion(
              currentNode.relatives[TSTNode.HIKID],
              charIndex,
              d,
              matchAlmostKey,
              matchAlmostNumReturnValues,
              matchAlmostResult,
              upTo);
    }
    return matchAlmostResult;
  }

  /**
   * Returns an alphabetical <code>List</code> of all keys in the trie that begin with a given
   * prefix. Only keys for nodes having non-null data are included in the <code>List</code>.
   *
   * @param prefix Each key returned from this method will begin with the characters in prefix.
   * @return A <code>List</code> with the results.
   */
  public List<String> matchPrefix(String prefix) {
    return matchPrefix(prefix, defaultNumReturnValues);
  }

  /**
   * Returns an alphabetical <code>List</code> of all keys in the trie that begin with a given
   * prefix. Only keys for nodes having non-null data are included in the <code>List</code>.
   *
   * @param prefix Each key returned from this method will begin with the characters in prefix.
   * @param numReturnValues The maximum number of values returned from this method.
   * @return A <code>List</code> with the results
   */
  public List<String> matchPrefix(CharSequence prefix, int numReturnValues) {
    List<String> sortKeysResult = new ArrayList<>();
    TSTNode startNode = getNode(prefix);
    if (startNode == null) {
      return sortKeysResult;
    }
    if (startNode.data != null) {
      sortKeysResult.add(getKey(startNode));
    }
    return sortKeysRecursion(
        startNode.relatives[TSTNode.EQKID],
        ((numReturnValues < 0) ? -1 : numReturnValues),
        sortKeysResult);
  }

  /**
   * Returns the number of nodes in the trie that have non-null data.
   *
   * @return The number of nodes in the trie that have non-null data.
   */
  public int numDataNodes() {
    return numDataNodes(rootNode);
  }

  /**
   * Returns the number of nodes in the subtrie below and including the starting node. The method
   * counts only nodes that have non-null data.
   *
   * @param startingNode The top node of the subtrie. the node that defines the subtrie.
   * @return The total number of nodes in the subtrie.
   */
  protected int numDataNodes(TSTNode startingNode) {
    return recursiveNodeCalculator(startingNode, true, 0);
  }

  /**
   * Returns the total number of nodes in the trie. The method counts nodes whether or not they have
   * data.
   *
   * @return The total number of nodes in the trie.
   */
  public int numNodes() {
    return numNodes(rootNode);
  }

  /**
   * Returns the total number of nodes in the subtrie below and including the starting Node. The
   * method counts nodes whether or not they have data.
   *
   * @param startingNode The top node of the subtrie. The node that defines the subtrie.
   * @return The total number of nodes in the subtrie.
   */
  protected int numNodes(TSTNode startingNode) {
    return recursiveNodeCalculator(startingNode, false, 0);
  }

  /**
   * Stores a value in the trie. The value may be retrieved using the key.
   *
   * @param key A <code>String</code> that indexes the object to be stored.
   * @param value The object to be stored in the Trie.
   */
  public void put(CharSequence key, Object value) {
    getOrCreateNode(key).data = value;
  }

  /**
   * Recursivelly visists each node to calculate the number of nodes.
   *
   * @param currentNode The current node.
   * @param checkData If true we check the data to be different of <code>null</code>.
   * @param numNodes2 The number of nodes so far.
   * @return The number of nodes accounted.
   */
  private int recursiveNodeCalculator(TSTNode currentNode, boolean checkData, int numNodes2) {
    if (currentNode == null) {
      return numNodes2;
    }
    int numNodes =
        recursiveNodeCalculator(currentNode.relatives[TSTNode.LOKID], checkData, numNodes2);
    numNodes = recursiveNodeCalculator(currentNode.relatives[TSTNode.EQKID], checkData, numNodes);
    numNodes = recursiveNodeCalculator(currentNode.relatives[TSTNode.HIKID], checkData, numNodes);
    if (checkData) {
      if (currentNode.data != null) {
        numNodes++;
      }
    } else {
      numNodes++;
    }
    return numNodes;
  }

  /**
   * Removes the value indexed by key. Also removes all nodes that are rendered unnecessary by the
   * removal of this data.
   *
   * @param key A <code>string</code> that indexes the object to be removed from the Trie.
   */
  public void remove(String key) {
    deleteNode(getNode(key.trim().toLowerCase(locale)));
  }

  /**
   * Sets the number of characters by which words can differ from target word when calling the
   * <code>matchAlmost</code> method.
   *
   * <p>Arguments less than 0 will set the char difference to 0, and arguments greater than 3 will
   * set the char difference to 3.
   *
   * @param diff The number of characters by which words can differ from target word.
   */
  public void setMatchAlmostDiff(int diff) {
    if (diff < 0) {
      matchAlmostDiff = 0;
    } else if (diff > 3) {
      matchAlmostDiff = 3;
    } else {
      matchAlmostDiff = diff;
    }
  }

  /**
   * Sets the default maximum number of values returned from the <code>matchPrefix</code> and <code>
   * matchAlmost</code> methods.
   *
   * <p>The value should be set this to -1 to get an unlimited number of return values. note that
   * the methods mentioned above provide overloaded versions that allow you to specify the maximum
   * number of return values, in which case this value is temporarily overridden.
   *
   * @param num The number of values that will be returned when calling the methods above.
   */
  public void setNumReturnValues(int num) {
    defaultNumReturnValues = (num < 0) ? -1 : num;
  }

  /**
   * Returns keys sorted in alphabetical order. This includes the start Node and all nodes connected
   * to the start Node.
   *
   * <p>The number of keys returned is limited to numReturnValues. To get a list that isn't limited
   * in size, set numReturnValues to -1.
   *
   * @param startNode The top node defining the subtrie to be searched.
   * @param numReturnValues The maximum number of values returned from this method.
   * @return A <code>List</code> with the results.
   */
  protected List<String> sortKeys(TSTNode startNode, int numReturnValues) {
    return sortKeysRecursion(
        startNode, ((numReturnValues < 0) ? -1 : numReturnValues), new ArrayList<>());
  }

  /**
   * Returns keys sorted in alphabetical order. This includes the current Node and all nodes
   * connected to the current Node.
   *
   * <p>Sorted keys will be appended to the end of the resulting <code>List</code>. The result may
   * be empty when this method is invoked, but may not be <code>null</code>.
   *
   * @param currentNode The current node.
   * @param sortKeysNumReturnValues The maximum number of values in the result.
   * @param sortKeysResult2 The results so far.
   * @return A <code>List</code> with the results.
   */
  private List<String> sortKeysRecursion(
      TSTNode currentNode, int sortKeysNumReturnValues, List<String> sortKeysResult2) {
    if (currentNode == null) {
      return sortKeysResult2;
    }
    List<String> sortKeysResult =
        sortKeysRecursion(
            currentNode.relatives[TSTNode.LOKID], sortKeysNumReturnValues, sortKeysResult2);
    if (sortKeysNumReturnValues != -1 && sortKeysResult.size() >= sortKeysNumReturnValues) {
      return sortKeysResult;
    }
    if (currentNode.data != null) {
      sortKeysResult.add(getKey(currentNode));
    }
    sortKeysResult =
        sortKeysRecursion(
            currentNode.relatives[TSTNode.EQKID], sortKeysNumReturnValues, sortKeysResult);
    return sortKeysRecursion(
        currentNode.relatives[TSTNode.HIKID], sortKeysNumReturnValues, sortKeysResult);
  }

  @Override
  public long ramBytesUsed() {
    long mem = RamUsageEstimator.shallowSizeOf(this);
    final TSTNode root = getRoot();
    if (root != null) {
      mem += root.ramBytesUsed();
    }
    return mem;
  }
}
