|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectcom.limegroup.gnutella.util.Trie
An information reTRIEval tree, a.k.a., a prefix tree. A Trie is similar to a dictionary, except that keys must be strings. Furthermore, Trie provides an efficient means (getPrefixedBy()) to find all values given just a PREFIX of a key.
All retrieval operations run in O(nm) time, where n is the size of the key/prefix and m is the size of the alphabet. Some implementations may reduce this to O(n log m) or even O(n) time. Insertion operations are assumed to be infrequent and may be slower. The space required is roughly linear with respect to the sum of the sizes of all keys in the tree, though this may be reduced if many keys have common prefixes.
The Trie can be set to ignore case. Doing so is the same as making all keys and prefixes lower case. That means the original keys cannot be extracted from the Trie.
Restrictions (not necessarily limitations!)
Nested Class Summary | |
class |
Trie.NodeIterator
|
Constructor Summary | |
Trie(boolean ignoreCase)
Constructs a new, empty tree. |
Method Summary | |
java.lang.Object |
add(java.lang.String key,
java.lang.Object value)
Maps the given key (which may be empty) to the given value. |
java.lang.String |
canonicalCase(java.lang.String s)
Returns the canonical version of the given string. |
void |
clear()
Makes this empty. |
java.lang.Object |
get(java.lang.String key)
Returns the value associated with the given key, or null if none. |
java.util.Iterator |
getPrefixedBy(java.lang.String prefix)
Returns an iterator (of Object) of the values mapped by keys in this that start with the given prefix, in any order. |
java.util.Iterator |
getPrefixedBy(java.lang.String prefix,
int startOffset,
int stopOffset)
Same as getPrefixedBy(prefix.substring(startOffset, stopOffset). |
boolean |
remove(java.lang.String key)
Ensures no values are associated with the given key. |
java.lang.String |
toString()
Returns a string representation of the tree state of this, i.e., the concrete state. |
void |
trim(Function valueCompactor)
Ensures that this consumes the minimum amount of memory. |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Constructor Detail |
public Trie(boolean ignoreCase)
Method Detail |
public void clear()
public java.lang.String canonicalCase(java.lang.String s)
In the basic version, strings are added and searched without modification. So this simply returns its parameter s.
Other overrides may also perform a conversion to the NFC form (interoperable across platforms) or to the NFKC form after removal of accents and diacritics from the NFKD form (ideal for searches using strings in natural language).
Made public instead of protected, because the public Prefix operations below may need to use a coherent conversion of search prefixes.
public java.lang.Object add(java.lang.String key, java.lang.Object value)
public java.lang.Object get(java.lang.String key)
public boolean remove(java.lang.String key)
public java.util.Iterator getPrefixedBy(java.lang.String prefix)
public java.util.Iterator getPrefixedBy(java.lang.String prefix, int startOffset, int stopOffset)
Important: canonicalization of prefix substring is NOT performed here! But it can be performed early on the whole buffer using the public method canonicalCase(String) of this.
canonicalCase(String)
public void trim(Function valueCompactor) throws java.lang.IllegalArgumentException, java.lang.ClassCastException
This method should typically be called after add(..)'ing a number of nodes. Insertions can be done after the call to compact, but they might be slower. Because this method only affects the performance of this, there is no modifies clause listed.
java.lang.IllegalArgumentException
java.lang.ClassCastException
public java.lang.String toString()
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |