Class goog.structs.Trie

Class for a Trie datastructure. Trie data structures are made out of trees of Trie classes.

Instance Method Summary
	`add(string key, <Any Type> value)` Adds the given key/value pair in the trie. Throw an exception if the key already exists in the trie. O(L), where L is the length of the key.
	`clear()` Completely empties a trie of all keys and values. ~O(1)
	`clone() ⇒ ?goog.structs.Trie` Clones a trie and returns a new trie. O(N), where N is the number of nodes in the trie.
	`containsKey(string key) ⇒ boolean` Checks to see if a certain key is in the trie. O(L), where L is the length of the key.
	`containsValue(<Any Type> value) ⇒ boolean` Checks to see if a certain value is in the trie. Worst case is O(N) where N is the number of nodes in the trie.
	`get(string key) ⇒ <Any Type>` Retrieves a value from the trie given a key. O(L), where L is the length of the key.
	`getCount() ⇒ number` Returns the number of key value pairs in the trie. O(N), where N is the number of nodes in the trie. TODO: This could be optimized by storing a weight (count below) in every node.
	`getKeyAndPrefixes(string key, ?number= opt_keyStartIndex) ⇒ ?Object` Retrieves all values from the trie that correspond to prefixes of the given input key. O(L), where L is the length of the key.
	`getKeys(string= opt_prefix) ⇒ ?Array` Gets the keys of the trie. Not returned in any reliable order. O(N) where N is the number of nodes in the trie (or prefix subtree).
	`getKeysInternal_(string keySoFar, ?Array allKeys)` Private method to get keys from the trie. Builds the keys as it goes.
	`getValues() ⇒ ?Array` Gets the values of the trie. Not returned in any reliable order. O(N) where N is the number of nodes in the trie. Calls getValuesInternal_.
	`getValuesInternal_(?Array allValues)` Gets the values of the trie. Not returned in any reliable order. O(N) where N is the number of nodes in the trie. Builds the values as it goes.
	`isEmpty() ⇒ boolean` Returns true if this trie contains no elements. ~O(1).
	`remove(string key) ⇒ <Any Type>` Removes a key from the trie or throws an exception if the key is not in the trie. O(L), where L is the length of the key.
	`set(string key, <Any Type> value)` Sets the given key/value pair in the trie. O(L), where L is the length of the key.
	`setAll((Object\|goog.structs.Trie\|null) trie)` Adds multiple key/value pairs from another goog.structs.Trie or Object. O(N) where N is the number of nodes in the trie.
	`setOrAdd_(string key, <Any Type> value, boolean= opt_add)` Helper function for set and add. Adds the given key/value pair to the trie, or, if the key already exists, sets the value of the key. If opt_add is true, then throws an exception if the key already has a value in the trie. O(L), where L is the length of the key.