Package com.gengoai.collection.tree

Class Trie<V>

java.lang.Object

com.gengoai.collection.tree.Trie<V>

Type Parameters:

V - the value type of the trie.

All Implemented Interfaces:

Serializable, Map<String,V>

public class Trie<V>
extends Object
implements Serializable, Map<String,V>

A basic Trie implementation that uses hashmaps to store its child nodes. The find(String, CharMatcher) method provides functionality to find all elements of the trie in the specified string in longest-first style using the specified CharPredicate to accept or reject matches based on the character after the match, e.g. only match if the next character is whitespace.

Note that views of the trie, i.e. keySet(), values(), entrySet(), and the resulting map from prefix(), are unmodifiable.

Author:

David B. Bracewell

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from interface java.util.Map

Map.Entry<K extends Object,V extends Object>

Constructor Summary

Constructors

Constructor	Description
Trie()	Instantiates a new Trie.
Trie(Map<String,V> map)	Instantiates a new Trie initializing the values to those in the given map.

Method Summary

Modifier and Type	Method	Description
void	clear()
boolean	containsKey(Object key)
boolean	containsValue(Object value)
Set<Map.Entry<String,V>>	entrySet()
List<TrieMatch<V>>	find(String text, CharMatcher delimiter)	Matches the strings in the trie against a specified text.
V	get(Object key)
boolean	isEmpty()
Set<String>	keySet()
Map<String,V>	prefix(String prefix)	Returns an unmodifiable map view of this Trie containing only those elements with the given prefix.
Iterator<String>	prefixKeyIterator(String prefix)
V	put(String key, V value)
void	putAll(Map<? extends String,? extends V> m)
V	remove(Object key)
int	size()
Map<String,Integer>	suggest(String string)	Suggest map.
Map<String,Integer>	suggest(String string, int maxCost)	Suggest map.
Map<String,Integer>	suggest(String string, int maxCost, int substitutionCost)	Suggest map.
String	toString()
Trie<V>	trimToSize()	Compresses the memory of the individual trie nodes.
Collection<V>	values()

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Map

compute, computeIfAbsent, computeIfPresent, equals, forEach, getOrDefault, hashCode, merge, putIfAbsent, remove, replace, replace, replaceAll

Constructor Detail

Trie

public Trie()

Instantiates a new Trie.

Trie

public Trie(Map<String,V> map)

Instantiates a new Trie initializing the values to those in the given map.

Parameters:

map - A map of string to value used to populate the trie.

Method Detail

clear

public void clear()

Specified by:

clear in interface Map<String,V>

containsKey

public boolean containsKey(Object key)

Specified by:

containsKey in interface Map<String,V>

containsValue

public boolean containsValue(Object value)

Specified by:

containsValue in interface Map<String,V>

entrySet

public Set<Map.Entry<String,V>> entrySet()

Specified by:

entrySet in interface Map<String,V>

find

public List<TrieMatch<V>> find(String text,
                               CharMatcher delimiter)

Matches the strings in the trie against a specified text. Matching is doing using a greedy longest match wins way. The give CharPredicate is used to determine if matches are accepted, e.g. only accept a match followed by a whitespace character.

Parameters:

text - the text to find the trie elements in

delimiter - the predicate that specifies acceptable delimiters

Returns:

the list of matched elements

get

public V get(Object key)

Specified by:

get in interface Map<String,V>

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface Map<String,V>

keySet

public Set<String> keySet()

Specified by:

keySet in interface Map<String,V>

prefix

public Map<String,V> prefix(String prefix)

Returns an unmodifiable map view of this Trie containing only those elements with the given prefix.

Parameters:

prefix - the prefix to match

Returns:

A unmodifiable map view of the trie whose elements have the given prefix

prefixKeyIterator

public Iterator<String> prefixKeyIterator(String prefix)

put

public V put(String key,
             V value)

Specified by:

put in interface Map<String,V>

putAll

public void putAll(Map<? extends String,? extends V> m)

Specified by:

putAll in interface Map<String,V>

remove

public V remove(Object key)

Specified by:

remove in interface Map<String,V>

size

public int size()

Specified by:

size in interface Map<String,V>

suggest

public Map<String,Integer> suggest(String string)

Suggest map.

Parameters:

string - the string

Returns:

the map

suggest

public Map<String,Integer> suggest(String string,
                                         int maxCost)

Suggest map.

Parameters:

string - the string

maxCost - the max cost

Returns:

the map

suggest

public Map<String,Integer> suggest(String string,
                                         int maxCost,
                                         int substitutionCost)

Suggest map.

Parameters:

string - the string

maxCost - the max cost

substitutionCost - the substitution cost

Returns:

the map

toString

public String toString()

Overrides:

toString in class Object

trimToSize

public Trie<V> trimToSize()

Compresses the memory of the individual trie nodes.

Returns:

this trie

values

public Collection<V> values()

Specified by:

values in interface Map<String,V>