Package eu.bandm.tools.util

Class Trie<K extends Comparable<? super K>,V>

java.lang.Object

eu.bandm.tools.util.Trie<K,V>

public class Trie<K extends Comparable<? super K>,V>
extends Object

Implementation of optimized prefix retrieval data structures. The data is of form K* -> V. The implementaiion follows the paradigm of Rose trees.

The Trie data are immutable, all operations on them are executed by a separate Trie.Evaluator. This must be equipped with a Monoid for V, to realizes the combination of data when combining Tries.

Both key K and values V are non-optional: null is not allowed, because ".hashCode" is called on them. The contents of an instance of Trie are always prefixed closed, i.e. if there is a value for the key "a.b.c", then one can retrieve values fo "a" and "a.b". In many application contexts the inner leaves are mapped to the neutral element of V.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static interface	Trie.Automaton<K,V>
static class	Trie.Evaluator<K extends Comparable<? super K>,V>	Realizes alebraic operation on Tries.
static class	Trie.Functor<K extends Comparable<? super K>>
static class	Trie.Node<K extends Comparable<? super K>,V>	Immutable data, each instance represents one cell (inner node or leaf) of the whole Trie.

Method Summary

Modifier and Type	Method	Description
static <K extends Comparable<? super K>> Function<Boolean,Trie<K,Boolean>>	append(Trie<K,Boolean> cont)
Trie.Automaton<K,V>	automaton(V bottom)
static <K extends Comparable<? super K>> Trie<K,Boolean>	empty()	Empty Set, when using Tries to represent "sets of K*", by V=Boolean.
static <K extends Comparable<? super K>> Trie<K,Boolean>	epsilon()	Set containing the empty K-string, when using Tries to represent "sets of K*", by V=Boolean.
boolean	equals(Trie<?,?> t)	evident
boolean	equals(Object o)	evident
int	hashCode()	evident
protected static <A, B> SortedEntryList<A,B>	list()	Auxiliary factory method to construct an empty list of the given type.
static void	main(String[] args)
protected static <A, B> BisectionMap<A,B>	map(SortedEntryList<A,B> entries)	FIXME ???
static <K extends Comparable<? super K>, V> Trie<K,V>	sequence(V pre, Iterable<? extends K> keys, V post)
static <K extends Comparable<? super K>> Trie<K,Boolean>	singleton(K key)	Singlteon set containing a K-string with length=1, when using Tries to represent "sets of K*", by V=Boolean.
static <K extends Comparable<? super K>, V> Trie<K,V>	singleton(V pre, K key, V post)
String	toString()	evident
static <K extends Comparable<? super K>, V> Trie<K,V>	unit(V value)

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Method Details

toString

public String toString()

evident

Overrides:

toString in class Object

hashCode

public int hashCode()

evident

Overrides:

hashCode in class Object

equals

public boolean equals(Object o)

evident

Overrides:

equals in class Object

equals

public boolean equals(Trie<?,?> t)

evident

list

protected static <A,
B> SortedEntryList<A,B> list()

Auxiliary factory method to construct an empty list of the given type.

map

protected static <A,
B> BisectionMap<A,B> map(SortedEntryList<A,B> entries)

FIXME ???

unit

public static <K extends Comparable<? super K>,
V>
Trie<K,V> unit(V value)

singleton

public static <K extends Comparable<? super K>,
V>
Trie<K,V> singleton(V pre,
 K key,
 V post)

sequence

public static <K extends Comparable<? super K>,
V>
Trie<K,V> sequence(V pre,
 Iterable<? extends K> keys,
 V post)

empty

public static <K extends Comparable<? super K>>
Trie<K,Boolean> empty()

Empty Set, when using Tries to represent "sets of K*", by V=Boolean.

epsilon

public static <K extends Comparable<? super K>>
Trie<K,Boolean> epsilon()

Set containing the empty K-string, when using Tries to represent "sets of K*", by V=Boolean.

singleton

public static <K extends Comparable<? super K>>
Trie<K,Boolean> singleton(K key)

Singlteon set containing a K-string with length=1, when using Tries to represent "sets of K*", by V=Boolean.

append

public static <K extends Comparable<? super K>>
Function<Boolean,Trie<K,Boolean>> append(Trie<K,Boolean> cont)

automaton

public Trie.Automaton<K,V> automaton(V bottom)

main

public static void main(String[] args)