com.limegroup.gnutella.util
Class Trie

java.lang.Object
  extended bycom.limegroup.gnutella.util.Trie

public class Trie
extends java.lang.Object

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

See http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Trie.html for a discussion of Tries.


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

Trie

public Trie(boolean ignoreCase)
Constructs a new, empty tree.

Method Detail

clear

public void clear()
Makes this empty.


canonicalCase

public java.lang.String canonicalCase(java.lang.String s)
Returns the canonical version of the given string.

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.


add

public java.lang.Object add(java.lang.String key,
                            java.lang.Object value)
Maps the given key (which may be empty) to the given value.

Returns:
the old value associated with key, or null if none

get

public java.lang.Object get(java.lang.String key)
Returns the value associated with the given key, or null if none.

Returns:
the Object value or null

remove

public boolean remove(java.lang.String key)
Ensures no values are associated with the given key.

Returns:
true if any values were actually removed

getPrefixedBy

public 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. That is, the returned iterator contains exactly the values v for which there exists a key k so that k.startsWith(prefix) and get(k) == v. The remove() operation on the iterator is unimplemented.


getPrefixedBy

public java.util.Iterator getPrefixedBy(java.lang.String prefix,
                                        int startOffset,
                                        int stopOffset)
Same as getPrefixedBy(prefix.substring(startOffset, stopOffset). This is useful as an optimization in certain applications to avoid allocations.

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.

See Also:
canonicalCase(String)

trim

public void trim(Function valueCompactor)
          throws java.lang.IllegalArgumentException,
                 java.lang.ClassCastException
Ensures that this consumes the minimum amount of memory. If valueCompactor is not null, also sets each node's value to valueCompactor.apply(node). Any exceptions thrown by a call to valueCompactor are thrown by this.

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.

Throws:
java.lang.IllegalArgumentException
java.lang.ClassCastException

toString

public java.lang.String toString()
Returns a string representation of the tree state of this, i.e., the concrete state. (The version of toString commented out below returns a representation of the abstract state of this.