The goog.structs.Trie Class

goog.structs.Trie(opt_trie)

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

opt_trie {Object=}
Optional goog.structs.Trie or Object to initialize trie with.

.add(key, 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.

key {string}
The key.
value {*}
The value.

.clear()

Completely empties a trie of all keys and values. ~O(1)

.clone()

Clones a trie and returns a new trie. O(N), where N is the number of nodes in the trie.

returns {goog.structs.Trie}
A new goog.structs.Trie with the same key value pairs.

.containsKey(key)

Checks to see if a certain key is in the trie. O(L), where L is the length of the key.

key {string}
A key that may be in the trie.
returns {boolean}
Whether the trie contains key.

.containsValue(value)

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.

value {*}
A value that may be in the trie.
returns {boolean}
Whether the trie contains the value.

.get(key)

Retrieves a value from the trie given a key. O(L), where L is the length of the key.

key {string}
The key to retrieve from the trie.
returns {*}
The value of the key in the trie, or undefined if the trie does not contain this key.

.getCount()

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.

returns {number}
The number of pairs.

.getKeyAndPrefixes(key, opt_keyStartIndex)

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.

key {string}
The key to use for lookup. The given key as well as all prefixes of the key are retrieved.
opt_keyStartIndex {?number=}
Optional position in key to start lookup from. Defaults to 0 if not specified.
returns {Object}
Map of end index of matching prefixes and corresponding values. Empty if no match found.

.getKeys(opt_prefix)

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).

opt_prefix {string=}
Find only keys with this optional prefix.
returns {Array}
The keys in the trie.

.getValues()

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_.

returns {Array}
The values in the trie.

.isEmpty()

Returns true if this trie contains no elements. ~O(1).

returns {boolean}
True iff this trie contains no elements.

.remove(key)

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.

key {string}
A key that should be removed from the trie.
returns {*}
The value whose key was removed.

.set(key, value)

Sets the given key/value pair in the trie. O(L), where L is the length of the key.

key {string}
The key.
value {*}
The value.

.setAll(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.

trie {Object|goog.structs.Trie}
Object containing the data to add.

Documentation generated using JvJsDoc, version 0.5 on 2012-09-03.