Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* Trie implementation in JavaScript
- * @version 0.1
- * Author - Jeff Long
- */
- (function() {
- /**
- * Trie(value) Initialize a new tree with base node x.
- *
- * @param {String} value
- * @return {Trie} trie
- */
- var Trie = function(value) {
- var value = value || '';
- this.children = [];
- this.endpoint = false;
- // Add a word if it's passed in
- if (value.length > 1) {
- this.value = '';
- this.add(value);
- } else {
- this.value = value;
- }
- return this;
- };
- Trie.prototype = {
- /**
- * add(word) adds a word to the trie
- *
- * @param {String} word
- * @return {Trie} trie
- */
- add: function(word) {
- if (word.forEach) {
- word.forEach(function(w) {
- this.add(w);
- }.bind(this));
- return this;
- }
- var node = this;
- for (var i in word) {
- var code = word.charCodeAt(i);
- if (node.children[code] !== undefined) {
- node = node.children[code];
- } else {
- node = node.children[code] = new Trie(code);
- }
- }
- node.endpoint = true;
- return this;
- },
- /**
- * getParent(word) returns a parent trie
- * based on the passed word
- *
- * @param {String} word
- * @return {Trie|Boolean} parentNode
- */
- getParent: function(word) {
- var parentNode = this;
- for (var i in word) {
- parentNode = parentNode.children[word.charCodeAt(i)];
- if (node === undefined) {
- return false;
- } else if (parseInt(i) === (word.length - 2)) {
- return parentNode;
- }
- }
- return false;
- },
- /**
- * remove(word) deletes a word from the trie
- *
- * @param {String} word
- * @return {Boolean} success
- */
- remove: function(word) {
- var parent = this.getParent(word);
- var charCode = word.charCodeAt(word.length - 1);
- if (!parent) {
- return false;
- }
- var node = parent.children[charCode];
- if (node.getChildren().length > 0) {
- node.endpoint = false;
- } else {
- delete parent.children[charCode];
- }
- if (parent.getChildren().length === 0) {
- node = parent;
- var level = 1;
- while (node.getChildren().length === 0 && !node.endpoint) {
- parent = this.getParent(word.substr(0, (word.length - level))) || this;
- delete parent.children[node.value];
- node = parent;
- level++;
- }
- }
- return true;
- },
- /**
- * contains(word) determines if a word is in the trie
- *
- * @param {String} word
- * @return {Boolean}
- */
- contains: function(word) {
- var parent = this.getParent(word);
- if (!parent || parent.children.length === 0) {
- return false;
- }
- var node = parent.children[word.charCodeAt(word.length - 1)] || {};
- return node.hasOwnProperty('endpoint') && node.endpoint !== false;
- },
- /**
- * getChildren() returns children of current node.
- * When you push an element to an array in Javascript at position x,
- * all indexes < x are automatically initialized as undefined. This filters
- * them out so we can use character codes for indexes.
- *
- * @return {Array} children
- */
- getChildren: function() {
- return this.children.filter(function(child) { return child !== undefined; });
- },
- /**
- * wordCount() returns a count of words from the trie.
- *
- * @return {Integer} count
- */
- wordCount: function() {
- var count = 0;
- function countWords(node) {
- for (var idx in node.children) {
- if (node.children[idx].endpoint) {
- count++;
- }
- countWords(node.children[idx]);
- }
- }
- countWords(this);
- return count;
- },
- /**
- * getJSON() returns a more readable representation of current data.
- *
- * @return {Object} data
- */
- getJSON: function() {
- var output = {
- wordcount: this.wordCount(),
- words: []
- };
- function getValues(node, depth) {
- for (var i in node.children) {
- var child = node.children[i] || false;
- if (child) {
- output.words.push({ char: String.fromCharCode(child.value),
- depth: depth,
- endpoint: child.endpoint });
- getValues(child, (depth + 1));
- }
- }
- }
- getValues(this, 0);
- return output;
- }
- };
- module.exports = Trie;
- })();
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement