com.illucit.instatrie.trie

Class Trie<T extends Serializable>

java.lang.Object

com.illucit.instatrie.trie.Trie<T>

Type Parameters:

T - payload data type

All Implemented Interfaces:

PrefixDictionary<T>, Serializable

public class Trie<T extends Serializable>
extends Object
implements PrefixDictionary<T>

Trie data structure to store string chains together with payload data. This trie structure is very efficient to determine whether a string (prefix) is contained in the trie or to get the payload data associated with a string.

This data structure is not threadsafe, so simultanious access by multiple concurrent threads is not permitted, if one of them makes modifications to the node structure.

Author:

Christian Simon

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
Trie() Create empty trie.
Trie(TrieNode<T> root) Create a trie with an existing root node.

Method Summary

Modifier and Type	Method and Description
void	clear() Clear all contained words and playload data.
boolean	contains(char[] word) Check if a word is included exactly in the trie.
boolean	containsPrefix(char[] word) Check if a word is either included completely or as prefix in the trie.
void	delete(char[] word) Delete the data associated with the given word.
T	getData(char[] word) Get data associated with the word in the trie, or null if the word was not included.
int	getDepth() Get depth of the trie.
TrieNode<T>	getNode(char[] word, boolean exact) Find a node that represents the given word.
TrieNode<T>	getRoot() Get the root node of the trie.
void	insert(char[] word, int startIndex, int endIndex, T data) Insert a substring of word with payload data inside the trie.
String	toString() Get String representation of trie.
void	updateOrInsertData(char[] word, Function<T,T> updateFunction) Insert or update data in the trie.
boolean	walkPath(char[] word, Consumer<TrieNode<T>> consumer, boolean includePrefixMatch) Walk the trie down along a path (up to the outermost node still matching the word) and call the consumer function every time (from the root to the outermost node).

Methods inherited from class java.lang.Object

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

Methods inherited from interface com.illucit.instatrie.trie.PrefixDictionary

contains, containsPrefix, delete, getData, insert, insert, insert, insert, insert, insert, insert, updateOrInsertData

Constructor Detail

Trie

public Trie()

Create empty trie.

Trie

public Trie(TrieNode<T> root)

Create a trie with an existing root node.

Parameters:

root - root node

Method Detail

getRoot

public TrieNode<T> getRoot()

Get the root node of the trie.

Returns:

root node

clear

public void clear()

Description copied from interface: PrefixDictionary

Clear all contained words and playload data.

Specified by:

clear in interface PrefixDictionary<T extends Serializable>

insert

public void insert(char[] word,
                   int startIndex,
                   int endIndex,
                   T data)

Description copied from interface: PrefixDictionary

Insert a substring of word with payload data inside the trie.

Specified by:

insert in interface PrefixDictionary<T extends Serializable>

Parameters:

word - word to be inserted

startIndex - index to begin the substring with (inclusive)

endIndex - index to end the substring at (exclusive)

data - payload data

updateOrInsertData

public void updateOrInsertData(char[] word,
                               Function<T,T> updateFunction)

Description copied from interface: PrefixDictionary

Insert or update data in the trie. If the word is already included in the trie, the update function is called with the current value and the value associated with the word is updated with the return value of the function. If the word is not included in the trie, the updateFunction is called with null and the returned value is inserted for the word.

Specified by:

updateOrInsertData in interface PrefixDictionary<T extends Serializable>

Parameters:

word - word to search

updateFunction - function that returns the inserted value (if input data is null) or returns the updates value (if input data is present)

containsPrefix

public final boolean containsPrefix(char[] word)

Description copied from interface: PrefixDictionary

Check if a word is either included completely or as prefix in the trie.

Specified by:

containsPrefix in interface PrefixDictionary<T extends Serializable>

Parameters:

word - word to search for

Returns:

true if the word is included either completely or as prefix of another word

contains

public boolean contains(char[] word)

Description copied from interface: PrefixDictionary

Check if a word is included exactly in the trie.

Specified by:

contains in interface PrefixDictionary<T extends Serializable>

Parameters:

word - word to search for

Returns:

true if the word is included in the trie

delete

public void delete(char[] word)

Description copied from interface: PrefixDictionary

Delete the data associated with the given word. If the word is not contained in the dictionary, nothing happens.

Specified by:

delete in interface PrefixDictionary<T extends Serializable>

Parameters:

word - word to search for

getData

public T getData(char[] word)

Description copied from interface: PrefixDictionary

Get data associated with the word in the trie, or null if the word was not included.

Specified by:

getData in interface PrefixDictionary<T extends Serializable>

Parameters:

word - word to search

Returns:

Daten am gefundenen Knoten order null

getNode

public TrieNode<T> getNode(char[] word,
                           boolean exact)

Find a node that represents the given word. If the search is exact, null is returned if the node is only a substring node of the next found node.

Parameters:

word - word to search for

exact - flag if exact node search should be performed

Returns:

node or null, if not found (exact)

walkPath

public boolean walkPath(char[] word,
                        Consumer<TrieNode<T>> consumer,
                        boolean includePrefixMatch)

Walk the trie down along a path (up to the outermost node still matching the word) and call the consumer function every time (from the root to the outermost node).

Parameters:

word - word to walk upon

consumer - consumer function to call on every node

includePrefixMatch - if this flag is true, the last node is also included if the word parameter is only a prefix of the path of this node (no exact match)

Returns:

true if the word was found completely, false otherwise

getDepth

public int getDepth()

Description copied from interface: PrefixDictionary

Get depth of the trie.

Specified by:

getDepth in interface PrefixDictionary<T extends Serializable>

Returns:

depth of trie

toString

public String toString()

Get String representation of trie.

Overrides:

toString in class Object

Returns:

String representation of root node