(function () {
"use strict";
/**
* Implementation of a Ternary Search Trie
* @class TernarySearchTrie
* @classdesc
* Data structure supporting String keys, for fast retrieval of
* values associated with string and provide prefix searches.
* [Reference: Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne]
* @desc
* #### Example -
* ```js
* var TernarySearchTrie = require("dsjslib").TernarySearchTrie
* var tst=new TernarySearchTrie()
* ```
*/
function TernarySearchTrie() {
this.mkNode_ = function (ch, val, lt, gt, eq) {
return {c : ch || null, l : lt || null, g : gt || null,
e : eq || null, v : val || null};
};
this.root = null;
}
TernarySearchTrie.prototype.getNode_ = function (node, key, pos) {
if (!node) {
return null;
}
var path = key.charAt(pos) === node.c ? 'e' : key.charAt(pos) > node.c ? 'g' : 'l';
var isEq = path === 'e';
var nextNode = node[path];
return (pos === key.length - 1) ?
(isEq ? node : nextNode ? this.getNode_(nextNode, key, pos) : null)
: this.getNode_(nextNode, key, isEq ? ++pos : pos);
};
/**
* @memberOf TernarySearchTrie.prototype
* @see {@link RWayTrie#get}
*/
TernarySearchTrie.prototype.get = function (key) {
var node = this.getNode_(this.root, key, 0);
return node && node.v;
};
/**
* Similar to BST delete but with some additional twist
* A node with a equal child pointer can't be deleted but
* the value is set to null. Also deletion may propagate up the chain
* @param parent
* @param node
* @param path
* @param isKey
* @return {*}
* @private
*/
TernarySearchTrie.prototype.deleteNode_ = function (parent, node, path) {
if (!node) {
return null;
}
var continueDel = false;
if (node.e) {
node.v = null;
return;
}
var numChild = node.l ? (node.g ? 2 : 1) : (node.g ? 1 : 0);
switch (numChild) {
case(0):
if (!parent) {
this.root = null;
}
else {
parent[path] = null;
continueDel = true;
}
break;
case(1):
var child = node.l || node.g;
if (!parent) {
this.root = child;
} else {
parent[path] = child;
}
continueDel = false;
break;
case(2):
var rChild = node.g;
var p = node;
var suc = rChild;
while (suc.l) {
p = suc;
suc = suc.l;
}
this.deleteNode_(p, suc, 'l');
node.e = suc.e;
node.c = suc.c;
node.v = suc.v;
}
return continueDel;
};
TernarySearchTrie.prototype.recDelete_ = function (parent, node, path, key, pos) {
if (!node) {
return null;
}
var nextPath = key.charAt(pos) === node.c ? 'e' : key.charAt(pos) > node.c ? 'g' : 'l';
var isEq = nextPath === 'e';
var nextNode = node[nextPath];
var continueDel = (pos === key.length - 1 ?
(isEq ? this.deleteNode_(parent, node, path)
: this.recDelete_(node, nextNode, nextPath, key, pos)) :
this.recDelete_(node, nextNode, nextPath, key, isEq ? ++pos : pos));
return continueDel && this.deleteNode_(parent, node, path);
};
/**
* @memberOf TernarySearchTrie.prototype
* @see {@link RWayTrie#delete}
* @function delete
*/
TernarySearchTrie.prototype['delete'] = function (key) {
this.recDelete_(null, this.root, null, key, 0);
};
TernarySearchTrie.prototype.putNode_ = function (node, key, val, pos) {
var ch = key.charAt(pos);
var path = ch === node.c ? 'e' : ch > node.c ? 'g' : 'l';
var isEq = path === 'e';
var recNode = node[path];
if (isEq && pos === (key.length - 1)) {
node.v = val;
return this;//no need to recurse, the chars already exist
}
if (recNode) {
this.putNode_(recNode, key, val, isEq ? ++pos : pos);
} else {/*make and insert nodes*/
var inserted = this.mkNode_(key.charAt(isEq ? ++pos : pos));
node[path] = inserted;
pos++;
while (pos < key.length) {
inserted.e = this.mkNode_(key.charAt(pos));
inserted = inserted.e;
pos++;
}
if (pos === key.length) {
inserted.v = val;
}
}
return this;
};
/**
* @memberOf TernarySearchTrie.prototype
* @see {@link RWayTrie#put}
*/
TernarySearchTrie.prototype.put = function (key, val) {
if (!this.root) {
this.root = this.mkNode_(key.charAt(0));
}
return this.putNode_(this.root, key, val, 0);
};
TernarySearchTrie.prototype.keysWithPrefix_ = function (startAtNode, prefix, keys, nEqKeyPath) {
if (!startAtNode) {
return;
}
if (startAtNode.v) {
keys.push({'key' : prefix, 'value' : startAtNode.v});
}
var nodes = [startAtNode.l, startAtNode.e, startAtNode.g];
if (nodes[0])this.keysWithPrefix_(nodes[0], nEqKeyPath + nodes[0].c, keys, nEqKeyPath);
if (nodes[1])this.keysWithPrefix_(nodes[1], prefix + nodes[1].c, keys, nEqKeyPath + startAtNode.c);
if (nodes[2])this.keysWithPrefix_(nodes[2], nEqKeyPath + nodes[2].c, keys, nEqKeyPath);
};
/**
* @memberOf TernarySearchTrie.prototype
* @see {@link RWayTrie#keysWithPrefix}
*/
TernarySearchTrie.prototype.keysWithPrefix = function (prefix) {
var keys = [], node = this.getNode_(this.root, prefix, 0);
if (!node) {
return keys;
}
if (!node.e) {
return [
{'key' : prefix, 'value' : node.v}
];
}
this.keysWithPrefix_(node.e, prefix + node.e.c, keys, prefix);
return keys;
};
/**
* @memberOf TernarySearchTrie.prototype
* @see {@link RWayTrie#entrySet}
*/
TernarySearchTrie.prototype.entrySet = function () {
var that = this, keys = [];
if (this.root) {
var superNode = this.mkNode_('', '', null, null, this.root);
this.keysWithPrefix_(superNode.e, superNode.e.c, keys, '');
}
return keys;
};
module.exports = TernarySearchTrie;
}());