Search Part VIII: Optimized prefix tries

by rocketegg0

HTML

<script src="https://cdnjs.cloudflare.com/ajax/libs/angular.js/1.4.7/angular.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/angular.js/1.5.0-beta.1/angular-sanitize.min.js"></script>
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.5/css/bootstrap.min.css">
<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/3.10.1/lodash.min.js"></script>
<div ng-controller="MyCtrl">
    <h2>Part 8: Compressed Prefix Tries</h2>
    <div>Search: <input type="text" ng-model="textIn"></input></div>
    <div>Limit: <input type="number" ng-model="limit"></input>
        <p>Use 0 for unlimited, Use '*' for wildcard</p>
    </div>
    <div>Add word: <input type="text" ng-model="addword"></input>
        <button ng-click="addWord(addword)">Add</button>
    </div>
    <div>Remove word: <input type="text" ng-model="removeword"></input>
        <button ng-click="removeWord(removeword)">Remove</button>
    </div>
    <div>
        <button ng-click="root.optimize()">Optimize root</button>
    </div>
    <div class="row">
        <div class="col-xs-12">
            <table>
                <caption>Search Results ({{ intersectedResults.length }})</caption>
                <tr>
                    <th>Words (Intersected)</th>
                </tr>
                <tr ng-repeat="word in intersectedResults track by $index">
                    <td><a ng-href="#{{word}}" ng-click="select(word)">{{::word}}</a></td>
                </tr>
            </table>
        </div>
    </div>
    <div class="row">
        <div class="table-responsive col-xs-6">
            <table>
                <caption>Search Results ({{ results.length }})</caption>
                <tr>
                    <th>Words (Prefix)</th>
                </tr>
                <tr ng-repeat="word in results">
                    <td><a ng-href="#{{word}}" ng-click="select(word)">{{::word}}</a></td>
                </tr>
            </table>
        </div>
        <div...

CSS

h2 {
    font-size: 150%;
}

table {
    margin-top: 10px;
    border: 1px solid #ccc;
    width: 100%;
}

table th {
    font-weight: bold;
}

em {
    font-style:italic;
}

strong {
    font-weight: bold;
}
pre {
    line-height:.5;
}

JavaScript

var myApp = angular.module('myApp',['ngSanitize']);

myApp.controller('MyCtrl', function($scope, $http) {
    
    // Compute unique hash words
    var toHash = function(dict) {
        return Object.keys(dict.split(' ').reduce(function(memo, word) {
            if (!memo.hasOwnProperty(word)) { memo[word] = true; }
            return memo;
        }, {})).sort();
    };
    
    // Compute prefix trie
    var toTrie = function(words) {
        var root = new Node();
        words.forEach(function(word) { root.insertc(word.toLowerCase()); });
        return root;
    };
    
    var reverse = function(words) {
        return words.map(function(word) { return word.reverse(); });
    };
    
    var wildcard = function(textIn) {
        if (!textIn) { return; }
        var substrs = textIn.split('*');
        var p = textIn[0] === '*' ? 1 : 0;
        var s = textIn[textIn.length-1] === '*' ? 1 : 0;
        var prefixes = substrs.length > 1 ? substrs.slice(p, substrs.length - 1 + s) : substrs;
        var suffixes = substrs.length > 1 ? substrs.slice(1 - p, substrs.length - s) : substrs;
        
        $scope.results = _(prefixes).map(function(prefix) {
            return $scope.autocomplete(prefix, $scope.root);
        }).flatten().value();
        $scope.reverseResults = reverse(_(suffixes).map(function(suffix) {
            return $scope.autocomplete(suffix.reverse(), $scope.reverseRoot);
        }).flatten().value());
        $scope.intersectedResults = _.intersection($scope.results, $scope.reverseResults);
    };
    
    $scope.select = function(word) { $scope.textIn = word; };
    
    $scope.addWord = function(word) {
        $scope.root.insertc(word);
        $scope.rendering = $scope.root.print();
    };
    
    $scope.removeWord = function(word) {
        $scope.root.removec(word);
        $scope.rendering = $scope.root.print();
    };
    
    $scope.autocomplete = function(textIn, root) {
        if (!textIn || textIn.length < 1) { return []; }
   ...