Skip to content

Instantly share code, notes, and snippets.

@yonatanmn
Created April 18, 2016 16:20
Show Gist options
  • Save yonatanmn/bff1b8dd80fc549da08d209f8917faa4 to your computer and use it in GitHub Desktop.
Save yonatanmn/bff1b8dd80fc549da08d209f8917faa4 to your computer and use it in GitHub Desktop.
Trie for autocomplete in JS
function wordToLtrsArr(w){return w.split('')}
function tail(arr){return arr.slice(1)}
function goTo(o,wp){
if(!wp.length){return o}
var firstLetter = wp[0];
var point = o[firstLetter];
return point ? goTo(point,tail(wp)) : {};
}
var endSym = Symbol.for('end')
var TrieProto = {
insert(w){
var point = this.tree;
wordToLtrsArr(w).forEach(function(e,i){
if(!point[e]){
point[e] = {};
}
point = point[e];
if(w.length - 1 === i){point[endSym] = true}
});
},
autoComplete(wp){
var point = goTo(this.tree, wp);
var stack = [];
function reduceObjToArr(o, trace){
for(k in o){
if(o[k][endSym]){stack.push(trace + k)}
reduceObjToArr(o[k], trace + k)
}
}
reduceObjToArr(point, '')
return stack.map(function(e){return wp + e});
}
};
var TrieDesc = {
tree:{
value:{},
enumerable:true
}
}
function createTrie(){
return Object.create(TrieProto,TrieDesc);
}
var x = createTrie();
x.insert('hello')
x.insert('hello')
x.insert('helloi')
x.insert('hella')
x.insert('hem')
x.insert('herr')
x.insert('he')
x.insert('kerr')
x.insert('ke')
x.autoComplete('he');
//=> ["hello", "helloi", "hella", "hem", "herr"]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment