eu.bandm.tools.ops

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

java.lang.Object

eu.bandm.tools.ops.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 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.
FIXME (bt+ml tel 20140621) K must implement "Comparable", version with "Comparator" could be appropriate.
FIXME (bt+ml tel 20140621) K ist non-opt und V ist non-opt wg. hashcode() The contents are always prefixed closed, in many application contexts the inner leaves are mapped to the neutral element of V. Is realized as "Rose Trees".

Nested Class Summary

Nested Classes

Modifier and Type	Class and 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 leave) of the whole Trie.

Method Summary

Modifier and Type	Method and 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(Object o)
boolean	equals(Trie t)
int	hashCode()
static void	main(String[] args)
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()
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 Detail

toString

public String toString()

Overrides:

toString in class Object

hashCode

public int hashCode()

Overrides:

hashCode in class Object

equals

public boolean equals(Object o)

Overrides:

equals in class Object

equals

public boolean equals(Trie t)

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)