Package eu.bandm.tools.util

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

java.lang.Object

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

Enclosing class:

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

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

Realizes alebraic operation on Tries.

Field Summary

Fields

Modifier and Type	Field	Description
(package private) final V	horizon
(package private) final int	limit
protected final Trie.Node<K,V>	unit
(package private) final Monoid<V>	values

Constructor Summary

Constructors

Constructor	Description
Evaluator()	Calls Evaluator(Monoid,Object,int) with no limit, no horizon and the discrete monoid, which treats null as neutral element (read "no value entered here").
Evaluator(Monoid<V> values, V horizon, int limit)

Method Summary

Modifier and Type	Method	Description
protected Trie.Node<K,V>	compose(Trie.Node<K,V> x, Function<V,Trie.Node<K,V>> f, int limit)
Trie<K,V>	compose(Trie<K,V> x, Function<V,Trie<K,V>> f)
Trie<K,V>	compose(Trie<K,V> x, Function<V,Trie<K,V>> f, int limit)
protected SortedMap<K,Trie.Node<K,V>>	compose(SortedMap<K,Trie.Node<K,V>> x, Function<V,Trie.Node<K,V>> f, int limit)
protected Iterator<Map.Entry<List<? extends K>,V>>	entries(Trie.Node<K,V> x, List<? extends K> path)
Iterable<Map.Entry<List<? extends K>,V>>	entries(Trie<K,V> x)	Fundamental retrieval operation: Get the list of Map.Entry containing prefix (from K*) and values.
protected <W> W	fold(BiFunction<? super V,? super SortedMap<K,W>,? extends W> fun, Trie.Node<K,V> x)
<W> W	fold(BiFunction<? super V,? super SortedMap<K,W>,? extends W> fun, Trie<K,V> x)	Special kind of folding as follows: For all leaf nodes fun is applied to their value and to an empty map.
protected <W> Trie<K,W>	foldNode(BiFunction<? super V,? super SortedMap<K,Trie.Node<K,W>>,? extends Trie.Node<K,W>> fun, Trie<K,V> x)
protected <W> Trie<K,W>	foldValue(BiFunction<? super V,? super SortedMap<K,W>,? extends W> fun, Trie<K,V> x)
Trie<K,V>	iterate(Function<V,Trie<K,V>> f, V init)
protected boolean	leq(BiPredicate<? super V,? super V> valueLeq, Trie.Node<K,V> x, Trie.Node<K,V> y)
boolean	leq(BiPredicate<? super V,? super V> valueLeq, Trie<K,V> x, Trie<K,V> y)
protected Trie.Node<K,V>	restrict(Trie.Node<K,V> x, Iterator<? extends K> i)
Trie<K,V>	restrict(Trie<K,V> x, Iterable<? extends K> path)	Fundamental retrieval operation: Get the subtree starting at the given key prefix.
V	select(Trie<K,V> x, Iterable<? extends K> path)	Fundamental retrieval operation: Get the value entry at the given key prefix.
protected Trie.Node<K,V>	trim(Trie.Node<K,V> x, int limit)	Prunes tree at the given maximal depth and inserts the "horizon" element, as defined in the constructor call Evaluator(Monoid,Object,int).
protected Trie.Node<K,V>	union(Trie.Node<K,V> x, Trie.Node<K,V> y)
Trie<K,V>	union(Trie<K,V> x, Trie<K,V> y)	Unify Trie data using Monoid function on values.
protected SortedMap<K,Trie.Node<K,V>>	union(SortedMap<K,Trie.Node<K,V>> x, SortedMap<K,Trie.Node<K,V>> y)

Methods inherited from class java.lang.Object

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

Field Details

values

final Monoid<V> values

horizon

final V horizon

limit

final int limit

unit

protected final Trie.Node<K extends Comparable<? super K>,V> unit

Constructor Details

Evaluator

public Evaluator()

Calls Evaluator(Monoid,Object,int) with no limit, no horizon and the discrete monoid, which treats null as neutral element (read "no value entered here").

Evaluator

public Evaluator(Monoid<V> values,
 V horizon,
 int limit)

Parameters:

limit - the maximal depth for pruning tries

horizon - the element which replaces pruned subtrees

values - the Monoid required for combining values when unifying branches

Method Details

union

public Trie<K,V> union(Trie<K,V> x,
 Trie<K,V> y)

Unify Trie data using Monoid function on values.

union

protected Trie.Node<K,V> union(Trie.Node<K,V> x,
 Trie.Node<K,V> y)

union

protected SortedMap<K,Trie.Node<K,V>> union(SortedMap<K,Trie.Node<K,V>> x,
 SortedMap<K,Trie.Node<K,V>> y)

compose

public Trie<K,V> compose(Trie<K,V> x,
 Function<V,Trie<K,V>> f)

compose

public Trie<K,V> compose(Trie<K,V> x,
 Function<V,Trie<K,V>> f,
 int limit)

compose

protected Trie.Node<K,V> compose(Trie.Node<K,V> x,
 Function<V,Trie.Node<K,V>> f,
 int limit)

compose

protected SortedMap<K,Trie.Node<K,V>> compose(SortedMap<K,Trie.Node<K,V>> x,
 Function<V,Trie.Node<K,V>> f,
 int limit)

trim

protected Trie.Node<K,V> trim(Trie.Node<K,V> x,
 int limit)

Prunes tree at the given maximal depth and inserts the "horizon" element, as defined in the constructor call Evaluator(Monoid,Object,int).

leq

public boolean leq(BiPredicate<? super V,? super V> valueLeq,
 Trie<K,V> x,
 Trie<K,V> y)

leq

protected boolean leq(BiPredicate<? super V,? super V> valueLeq,
 Trie.Node<K,V> x,
 Trie.Node<K,V> y)

iterate

public Trie<K,V> iterate(Function<V,Trie<K,V>> f,
 V init)

select

public V select(Trie<K,V> x,
 Iterable<? extends K> path)

Fundamental retrieval operation: Get the value entry at the given key prefix.

restrict

public Trie<K,V> restrict(Trie<K,V> x,
 Iterable<? extends K> path)

Fundamental retrieval operation: Get the subtree starting at the given key prefix.

restrict

protected Trie.Node<K,V> restrict(Trie.Node<K,V> x,
 Iterator<? extends K> i)

entries

protected Iterator<Map.Entry<List<? extends K>,V>> entries(Trie.Node<K,V> x,
 List<? extends K> path)

entries

public Iterable<Map.Entry<List<? extends K>,V>> entries(Trie<K,V> x)

Fundamental retrieval operation: Get the list of Map.Entry containing prefix (from K*) and values.

fold

public <W> W fold(BiFunction<? super V,? super SortedMap<K,W>,? extends W> fun,
 Trie<K,V> x)

Special kind of folding as follows:
For all leaf nodes fun is applied to their value and to an empty map. This yields a value from W.
For each inner node the result from W is calculated by applying fun to its value (form V) and to a map K->W which collects the folding results of its childs sequence.

fold

protected <W> W fold(BiFunction<? super V,? super SortedMap<K,W>,? extends W> fun,
 Trie.Node<K,V> x)

foldValue

protected <W> Trie<K,W> foldValue(BiFunction<? super V,? super SortedMap<K,W>,? extends W> fun,
 Trie<K,V> x)

foldNode

protected <W> Trie<K,W> foldNode(BiFunction<? super V,? super SortedMap<K,Trie.Node<K,W>>,? extends Trie.Node<K,W>> fun,
 Trie<K,V> x)