Trie

Trie.js

class Node {
  constructor(character) {
    this.edges = {};
    this.data = undefined; // where we will store the flag data / capitalized names
    this.character = character;
    this.endOfWord = false;
  }
}

export default class Trie extends Node {
  getAllPossibilities(string) {
    // find the trie that lies below the depth of a given string
    const getDanglingTrie = (string, trie) => {
      let node = trie;
      while (string && node) {
        node = node.edges[string[0]];
        string = string.slice(1);
      }
      return node;
    };

    const matchedWords = [];
    const findMatchedWords = (partialString, node) => {
      // find all results that begin with the given string and store them
      Object.values(node.edges).forEach(child => {
        // do a depth first search for each of the edges of this node
        const newString = partialString + child.character;
        if (child.endOfWord) {
          // found a leaf of this trie
          matchedWords.push({ string: newString, data: child.data });
        }

        // go down another layer
        findMatchedWords(newString, child);
      });
    }

    const trie = getDanglingTrie(string, this);
    // if there's any trie left after this string, find all of it's values
    if (trie) {
      findMatchedWords(string, trie);
    }

    return matchedWords;
  }

  storeWord(string, data) {
    // starting at the first letter, iterate thru the entire word
    // each letter is an edge off of the previous letter's node
    // at the end of the string, store an 'endOfWord' flag and store the given data object
    const recurseDownString = (node, substr) => {
      if (!node.edges[substr[0]]) {
        node.edges[substr[0]] = new Node(substr[0]);
        if (substr.length === 1) {
          node.edges[substr[0]].endOfWord = true;
          node.edges[substr[0]].data = data;
        }
      }
      if (substr.length > 1) {
        recurseDownString(node.edges[substr[0]], substr.slice(1));
      }
    };
    recurseDownString(this, string);
  }
}