Skip to content

Instantly share code, notes, and snippets.

@olslash
Last active August 29, 2015 14:05
Show Gist options
  • Save olslash/3b5fb7d3edf43ec0b9b2 to your computer and use it in GitHub Desktop.
Save olslash/3b5fb7d3edf43ec0b9b2 to your computer and use it in GitHub Desktop.
T9 blogpost - 7
function getDeeperSuggestions(root, maxDepth) {
// We traverse down every possible branch from the result node (the node
// corresponding to the keypad entry), saving words we see as we go and
// stopping when we reach the specified depth.sug
// deepSuggestions is an array with (maxDepth) subarrays.
// Each of the subarrays will be one depth level's suggestions.
var deepSuggestions = [];
while(deepSuggestions.length < maxDepth) {
deepSuggestions.push([]);
}
// The traverse function (below) fills deepSuggestions with results.
traverse(root, 0);
// Each level is sorted individually, because we want shallower results
// to always be suggested first. (this is an implementation detail and
// there's a possibility sorting everything together might give
// better results in practice.)
deepSuggestions = deepSuggestions.map(function(level) {
return level.sort(function(a, b) {
return b[1] - a[1];
});
});
// At this point, deepSuggestions is an array of arrays (one for each
// level of depth). Each of those subarrays contains word tuples.
return deepSuggestions.reduce(function(result, level) {
// Merge each level into a single flat array.
return result.concat(level.map(function(wordTuple) {
// Keep only the word itself, discarding the frequency number
return wordTuple[0];
}));
}, []);
function traverse(root, depth) {
// Basic tree traversal, collecting results up to the required depth.
if(depth <= maxDepth && depth !== 0) { // Result already has depth 0
var d = depth - 1;
deepSuggestions[d] = deepSuggestions[d].concat(root.words);
}
if(depth === maxDepth) { return; }
for(var childKey in root.children) {
traverse(root.children[childKey], depth + 1);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment