org.apache.jena.atlas.lib

Class Trie<T>

java.lang.Object

org.apache.jena.atlas.lib.Trie<T>

Type Parameters:

T - Type of the value stored.

public final class Trie<T>
extends Object

An implementation of a classic Trie, this is a mapping from strings to some value type optimized for fast prefix search and match. If you do not need prefix search then you should typically use a standard Map instead.

The empty or null string may be used as a special key to refer to the root node of the trie.

A Trie cannot store null values since null is used as an internal marker to indicate that there is no value associated with a key. This is necessary because the nature of the data structure means that adding a key potentially adds multiple keys many of which will not be associated with a value.

Constructor Summary

Constructors

Constructor and Description
Trie()

Method Summary

Methods

Modifier and Type	Method and Description
void	add(String key, T value) Adds a value to the trie overwriting any existing value
boolean	contains(String key) Gets whether a key exists in the trie and has a non-null value mapped to it
boolean	contains(String key, boolean requireValue) Gets whether a key exists in the trie and meets the given value criteria
boolean	contains(String key, T value) Gets whether a key value pair are present in the trie
T	get(String key) Gets the value associated with a key
T	longestMatch(String key) Finds the longest match for a given key i.e.
List<T>	partialSearch(String key) Performs a search and returns any value associated with any partial or whole prefix of the key
List<T>	prefixSearch(String prefix) Performs a prefix search and returns all values mapped under the given prefix.
void	remove(String key) Removes a value from the trie
T	shortestMatch(String key) Finds the shortest match for a given key i.e.

Methods inherited from class java.lang.Object

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

Constructor Detail

Trie

public Trie()

Method Detail

add

public void add(String key,
       T value)

Adds a value to the trie overwriting any existing value

Note that a null value is treated as if the key does not actually exist in the tree so trying to add a null is a no-op. If you want to remove a key use the remove(String) method instead.

Parameters:

key - Key

value - Value

remove

public void remove(String key)

Removes a value from the trie

This doesn't actually remove the key per-se rather sets the value associated with the key to null.

Parameters:

key - Key

contains

public boolean contains(String key)

Gets whether a key exists in the trie and has a non-null value mapped to it

Parameters:

key - Key

Returns:

True if the key exists and has a non-null value mapped to it

contains

public boolean contains(String key,
               boolean requireValue)

Gets whether a key exists in the trie and meets the given value criteria

Parameters:

key - Key

requireValue - If true a key must have a non-null value associated with it to be considered to be contained in the tree, if false then the key must merely map to a node in the trie

Returns:

True if the key exists and the value criteria is met, false otherwise

contains

public boolean contains(String key,
               T value)

Gets whether a key value pair are present in the trie

Parameters:

key - Key

value - Value

Returns:

True if the key value pair exists in the trie, false otherwise

get

public T get(String key)

Gets the value associated with a key

Parameters:

key - Key

Returns:

Value

prefixSearch

public List<T> prefixSearch(String prefix)

Performs a prefix search and returns all values mapped under the given prefix. The entirety of the prefix must be matches, if you only want part of the prefix to be matched use the partialSearch(String) method instead.

Parameters:

prefix - Prefix

Returns:

List of values associated with the given key

partialSearch

public List<T> partialSearch(String key)

Performs a search and returns any value associated with any partial or whole prefix of the key

Parameters:

key - Key

Returns:

List of values associated with any partial prefix of the key

shortestMatch

public T shortestMatch(String key)

Finds the shortest match for a given key i.e. returns the value associated with the shortest prefix of the key that has a value

Parameters:

key - Key

Returns:

Shortest Match or null if no possible matches

longestMatch

public T longestMatch(String key)

Finds the longest match for a given key i.e. returns the value associated with the longest prefix of the key that has a value

Parameters:

key - Key

Returns:

Longest Match or null if no possible matches