csw5-trie-final.js

const Base26 = require('./base26')

/** The Radix of the Trie. In thise case, base 26 */
const R = 26

/**
 * An node contains a value and links that point to other nodes.
 * @typedef {Object} Node
 * @property {any} value
 * @property {Array} next
 */

/**
 * Create a new Node. Sub-structure used in the Trie.
 *
 * @class
 * @private
 * @param {any} [value=null]
 */
function Node (value = null) {
  this.value = value
  this.next = new Array(R)
}

/**
 * Class representing an R-way Trie Symbol Table for processing
 * key/val pairs whereby the keys are strings.
 */
class Trie {
  /** Create a Trie with an empty Root {@link Node} */
  constructor () {
    this.root = new Node()
  }

  /**
   * Adds key/val pairs to the Trie. Duplicate keys
   * are not possible though the value of the key is the most recent insert.
   *
   * @param {string} key
   * @param {any} [val=null]
   */
  put (key = '', val = null) {
    this.root = recursiveInsert(this.root, key, val, 0)
  }

  /**
   * Retrieves keys that match a given pattern. A wildcard
   * is denoted by a dot ('.'). Keys will be in sorted
   * order.
   *
   * @example
   * // returns ['pest', 'test']
   * const trie = new Trie()
   * trie.put('test')
   * trie.put('pest')
   * console.log(trie.keysThatMatch('.est'))
   *
   * @param {string} pattern
   * @returns {Array.<string>} the matching keys, if any
   */
  keysThatMatch (pattern) {
    const q = []
    collect(this.root, '', pattern, q)
    return q
  }
}

// private helper method to insert a key/val through
// a recursive walk
const recursiveInsert = (node, key, val, d) => {
  if (!node) node = new Node()
  if (d === key.length) {
    node.value = val
    return node
  }
  let c = Base26.getBase26Digit(key[d])
  node.next[c] = recursiveInsert(node.next[c], key, val, d + 1)
  return node
}

// private helper method to find all keys that
// match a pattern through a recursive walk
const collect = (node, pre, pattern, q) => {
  if (!node) { return }
  let d = pre.length
  if (d === pattern.length && node.value) { q.push(pre) }
  if (d === pattern.length) { return }

  let next
  pattern[d] === '.'
    ? next = '.'
    : next = Base26.getBase26Digit(pattern[d])

  for (let c = 0; c < R; c++) {
    if (next === '.' || next === c) {
      collect(node.next[c], pre + (Base26.getUTF16(c)), pattern, q)
    }
  }
}

if (process.env.NODE_ENV === 'test') {
  // only expose private objects for testing purposes
  module.exports = {
    R,
    recursiveInsert,
    Node,
    Trie
  }
} else {
  // in production, development - only Class Trie is exposed.
  module.exports = Trie
}