trie

trie.js

'use strict';

function Trie() {
    this.children = {};
}

Trie.prototype = {
    search: function (str) {
        var current = this;

        for (var idx = 0; idx < str.length; idx++) {
            current = current.children[str[idx]];

            if (!current) {
                return undefined;
            }
        }

        return current.end ? current : undefined;
    },

    insert: function (str) {
        var current = this;

        for (var idx = 0; idx < str.length; idx++) {
            current = current.children[str[idx]] || (current.children[str[idx]] = new Node(str[idx], (idx + 1) >= str.length));
        }

        current.end = true;
    }
};

function Node(value, end) {
    Node.super_.apply(this);
    this.value = value;
    this.end = end;
}

require('util').inherits(Node, Trie);

module.exports = Trie;