goog.structs.Trie<VALUE>
| Provided By |
|---|
Class for a Trie datastructure. Trie data structures are made out of trees of Trie classes.
new Trie<VALUE>( opt_trie )
| Parameters |
|
|---|
Instance Methods
this.add( key, value ) → void
voidAdds 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.
| Overrides | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Parameters |
|
this.clear() → void
voidCompletely empties a trie of all keys and values. ~O(1)
| Overrides | |
|---|---|
| Parameters | None. |
this.clone() → goog.structs.Trie<(VALUE|null)>
goog.structs.Trie<(VALUE|null)>Clones a trie and returns a new trie. O(N), where N is the number of nodes in the trie.
| Overrides | |||
|---|---|---|---|
| Parameters | None. | ||
| Returns |
|
this.containsKey( key ) → boolean
booleanthis.containsPrefix( prefix ) → boolean
booleanthis.containsValue( value ) → boolean
booleanChecks 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.
| Overrides | |||||
|---|---|---|---|---|---|
| Parameters |
| ||||
| Returns |
|
this.get( key ) → ?
?Retrieves a value from the trie given a key. O(L), where L is the length of the key.
| Overrides | |||||
|---|---|---|---|---|---|
| Parameters |
| ||||
| Returns |
|
this.getCount() → number
numberReturns 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.
| Overrides | |||
|---|---|---|---|
| Parameters | None. | ||
| Returns |
|
this.getKeyAndPrefixes( key, opt_keyStartIndex ) → Object<?, (VALUE|null)>
Object<?, (VALUE|null)>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.
| Overrides | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Parameters |
| ||||||||
| Returns |
|
this.getValues() → Array<(VALUE|null)>
Array<(VALUE|null)>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_.
| Overrides | |||
|---|---|---|---|
| Parameters | None. | ||
| Returns |
|
this.isEmpty() → boolean
booleanReturns true if this trie contains no elements. ~O(1).
| Overrides | |||
|---|---|---|---|
| Parameters | None. | ||
| Returns |
|
this.remove( key ) → VALUE
VALUERemoves 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.
| Overrides | |||||
|---|---|---|---|---|---|
| Parameters |
| ||||
| Returns |
|
this.set( key, value ) → void
voidSets the given key/value pair in the trie. O(L), where L is the length of the key.
| Overrides | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Parameters |
|
this.setAll( trie ) → void
voidAdds multiple key/value pairs from another goog.structs.Trie or Object. O(N) where N is the number of nodes in the trie.
| Overrides | |||||
|---|---|---|---|---|---|
| Parameters |
|