sirius.kernel.commons

Class Trie<V>

java.lang.Object

sirius.kernel.commons.Trie<V>

Type Parameters:

V - the type of values managed by the trie

public class Trie<V>
extends Object

A map like data structure which associates strings (char sequences) to values.

A trie is a highly efficient data structure for iterating through a string and retrieving a previously stored value. Checking containment or retrieving a value has guaranteed O(n) runtime, where n is the length of the processed string, independent of the size of the trie.

An Example: If we have a list of stop words: "one", "two", "three" and want to detect if these occur in a given text, we can do the following:

 
 Trie<Boolean> trie = Trie.create();

 trie.put("one", true);
 trie.put("two", true);
 trie.put("three", true);

 String check = "I'd like to have three beer please";
 Trie.ContainmentIterator<Boolean> iter = trie.iterator();

 for(int i = 0; i < check.length(); i++) {
     if (!iter.doContinue(check.charAt(i))) {
         if (iter.isCompleted()) {
             System.out.println("Found!");
         } else {
             iter.resetWith(check.charAt(i));
         }
     }
 }

 
 

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static interface	Trie.ContainmentIterator<V> Represents an iterator which navigates through the trie character by character.

Constructor Summary

Constructors

Constructor and Description
Trie()

Method Summary

Modifier and Type	Method and Description
boolean	containsKey(CharSequence key) Determines if the given key is contained in the trie.
static <V> Trie<V>	create() Creates a new Trie without forcing you to re-type the generics.
V	get(CharSequence key) Returns the value associated with the given key.
Set<String>	getAllKeysBeginningWith(String prefix) Performs a prefix search within this Trie's key set
Trie.ContainmentIterator<V>	iterator() Generates a new iterator for the underlying trie.
Set<String>	keySet() Retrieves all keys that are stored in this Trie.
void	put(CharSequence key, V value) Associates the given key with the given value.
int	size() Retrieves the number of keys that are stored in this Trie.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Trie

public Trie()

Method Detail

create

public static <V> Trie<V> create()

Creates a new Trie without forcing you to re-type the generics.

Type Parameters:

V - the type of values managed by the trie

Returns:

a new instance of Trie

containsKey

public boolean containsKey(@Nonnull
                           CharSequence key)

Determines if the given key is contained in the trie.

Parameters:

key - the key to check for.

Returns:

true if a value is associated with the path represented by the given key, false otherwise

iterator

public Trie.ContainmentIterator<V> iterator()

Generates a new iterator for the underlying trie.

Returns:

a new iterator to navigate through the underlying trie

get

public V get(@Nonnull
             CharSequence key)

Returns the value associated with the given key.

Parameters:

key - the path to navigate through

Returns:

the value associated with the path defined by the given key or null if no value is present

put

public void put(@Nonnull
                CharSequence key,
                @Nonnull
                V value)

Associates the given key with the given value.

Parameters:

key - the path to store the given value

value - the value to store in the trie.

keySet

public Set<String> keySet()

Retrieves all keys that are stored in this Trie.

Returns:

a Set of all keys that are stored in this Trie

size

public int size()

Retrieves the number of keys that are stored in this Trie.

Returns:

the size of this Trie's key set

getAllKeysBeginningWith

public Set<String> getAllKeysBeginningWith(String prefix)

Performs a prefix search within this Trie's key set

Parameters:

prefix - to search for

Returns:

all keys that are beginning with the given prefix (may include prefix itself)