org.limewire.collection
Class StringTrie<V>

java.lang.Object
  org.limewire.collection.StringTrie<V>

public class StringTrie<V>
extends 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(String)) 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, which is the same as making all keys and prefixes lower case. Therefore, ignoring case means the original keys cannot be extracted from the Trie.

Restrictions (not necessarily limitations)

• Keys and values may not be null.
• The interface to this is not complete.

See Tries for a discussion of Tries.

This class is not thread-safe.

Constructor Summary

StringTrie(boolean ignoreCase)
Constructs a new, empty tree.

Method Summary

V	add(String key, V value) Maps the given key (which may be empty) to the given value.
String	canonicalCase(String s) Returns the canonical version of the given string.
void	clear() Makes this empty.
V	get(String key) Returns the value associated with the given key, or null if none.
Iterator<V>	getIterator() Returns all values (entire Trie)
Iterator<V>	getPrefixedBy(String prefix) Returns an iterator (of V) of the values mapped by keys in this that start with the given prefix, in any order.
Iterator<V>	getPrefixedBy(String prefix, int startOffset, int stopOffset) Same as getPrefixedBy(prefix.substring(startOffset, stopOffset).
boolean	remove(String key) Ensures no values are associated with the given key.
int	size()
String	toString() Returns a string representation of the tree state of this, i.e., the concrete state.
void	trim(Function<V,? extends V> 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

StringTrie

public StringTrie(boolean ignoreCase)

Constructs a new, empty tree.

Method Detail

clear

public void clear()

Makes this empty.

canonicalCase

public String canonicalCase(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 (inter-operable 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 V add(String key,
             V 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 V get(String key)

Returns the value associated with the given key, or null if none.

Returns:

the Object value or null

remove

public boolean remove(String key)

Ensures no values are associated with the given key.

Returns:

true if any values were actually removed

getPrefixedBy

public Iterator<V> getPrefixedBy(String prefix)

Returns an iterator (of V) 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 Iterator<V> getPrefixedBy(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)

getIterator

public Iterator<V> getIterator()

Returns all values (entire Trie)

size

public int size()

Returns:

the number of values stored in the trie.

trim

public void trim(Function<V,? extends V> valueCompactor)
          throws IllegalArgumentException,
                 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:

IllegalArgumentException

ClassCastException

toString

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

Overrides:

toString in class Object