/**
* @class
* A Trie node
* @description A single node of a Trie structure.
*/
class TrieNode {
constructor(){
// For memory optimisation we use an array instead of anything else
// The property name must be short, we assume exponential amounts of instances
this._ = [false, {}, null]; // is_leaf, children, leaf_meta
}
// Properties by accessor function, we care mostly about memory, not access times
get is_leaf(){
return this._[0];
}
set is_leaf(v){
return this._[0] = v;
}
get children(){
return this._[1];
}
get meta(){
return this._[2];
}
set meta(data){
return this._[2] = data;
}
// Main algorithms, structural not recursive
/**
* Retrieve the node instance that holds the key.
* If touch is set then missing nodes will be created.
* Guarantees that an instance will be returned.
* The implementation is structural, not recursive.
* @param {String} key
* @param {Boolean} [touch=false]
* @returns {TrieNode}
*/
getNodeForKey(key, touch=false){
let current_key = key;
let current_node = this;
while(current_key.length > 0){
const letter = current_key.charAt(0);
const child = current_node.children[letter];
if(child){
current_node = child;
}else{
// Does not exist
if(touch){
const new_node = new TrieNode();
current_node.children[letter] = new_node;
current_node = new_node;
}else{
return null;
}
}
current_key = current_key.substr(1);
}
return current_node;
}
// High-level functions
/**
* Put a value into the structure. Attach some data to it.
* @param {String} key
* @param {*} value
*/
put(key, value){
const node = this.getNodeForKey(key, true);
node.is_leaf = true;
node.meta = value;
}
/**
* Retrieve the data attached to a key.
* @param {*} key
* @returns {*}
*/
get(key){
const node = this.getNodeForKey(key);
if(node && node.is_leaf)
return node.meta;
return null;
}
// Iterator, iterative not recursive
[Symbol.iterator](){
// The stack describes what should be called next
var state_stack = [];
// -1 means leaf
state_stack.push([this, -1, '']);
return {
next(){
while(state_stack.length > 0){
const opt = state_stack.slice(-1)[0];
const node = opt[0];
const child_idx = opt[1];
const prefix = opt[2];
if(child_idx == -1){
opt[1]++;
if(node.is_leaf){
// Try first child next
return {value: [prefix, node.meta], done: false}
}
}else{
const children = Object.keys(node.children);
const child = node.children[children[opt[1]]];
if(child){
state_stack.push([child, -1, prefix+children[opt[1]]]);
opt[1]++;
}else{
// Done with this one
state_stack.pop();
}
}
}
return {value: undefined, done: true};
}
}
}
}
module.exports = TrieNode;