DevTools: introduce Trie data structure

third_party/WebKit/Source/devtools/front_end/common/TextDictionary.js

 /*
  * Copyright (C) 2013 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met:
  *
  *     * Redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer.
  *     * Redistributions in binary form must reproduce the above
@@ skipping 17 matching lines @@
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
 /**
  * @constructor
  */
 WebInspector.TextDictionary = function()
 {
     /** @type {!Map<string, number>} */
     this._words = new Map();
+    this._index = new Trie();
 }
 
 WebInspector.TextDictionary.prototype = {
     /**
      * @param {string} word
      */
     addWord: function(word)
     {
         var count = this._words.get(word) || 0;
         ++count;
         this._words.set(word, count);
+        this._index.add(word);
     },
 
     /**
      * @param {string} word
      */
     removeWord: function(word)
     {
         var count = this._words.get(word) || 0;
         if (!count)
             return;
+        this._index.remove(word);
         if (count === 1) {
             this._words.delete(word);
             return;
         }
         --count;
         this._words.set(word, count);
     },
 
     /**
      * @param {string} prefix
      * @return {!Array.<string>}
      */
     wordsWithPrefix: function(prefix)
     {
-        var words = [];
-        for (var word of this._words.keys()) {
-            if (word.startsWith(prefix))
-                words.push(word);
-        }
-        return words;
+        return this._index.words(prefix);
     },
 
     /**
      * @param {string} word
      * @return {boolean}
      */
     hasWord: function(word)
     {
         return this._words.has(word);
     },
 
     /**
      * @param {string} word
      * @return {number}
      */
     wordCount: function(word)
     {
         return this._words.get(word) || 0;
     },
 
     reset: function()
     {
         this._words.clear();
+        this._index.clear();
     }
 }