Class ImmutableBinaryTrie<T>
- All Implemented Interfaces:
Function<T,
,Long> Object2LongFunction<T>
,Serializable
,Function<T,
,Long> ToLongFunction<T>
Instance of this class are built starting from a lexicographically ordered
list of BitVector
s representing binary words. Each word
is assigned its position (starting from 0) in the list. The words are then organised in a
binary trie with path compression.
Once the trie has been built, it is possible to ask whether a word w is contained in the trie (getting back its position in the list), the interval given by the words extending w and the approximated interval defined by w.
- Since:
- 2.0
- Author:
- Sebastiano Vigna
- See Also:
-
Nested Class Summary
Modifier and TypeClassDescriptionprotected static class
A node in the trie. -
Field Summary
Fields inherited from class it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction
defRetValue
-
Constructor Summary
ConstructorDescriptionImmutableBinaryTrie
(Iterable<? extends T> elements, TransformationStrategy<? super T> transformationStrategy) Creates a trie from a set of elements. -
Method Summary
Modifier and TypeMethodDescriptionprotected ImmutableBinaryTrie.Node
buildTrie
(ObjectList<LongArrayBitVector> elements, int pos) Builds a trie recursively.boolean
containsKey
(Object element) long
get
(BooleanIterator iterator) Return the index of the word returned by the given iterator, or -1 if the word is not in this trie.getApproximatedInterval
(BooleanIterator iterator) Returns an approximated prefix interval around the word returned by the specified iterator.getApproximatedInterval
(T element) Returns an approximated interval around the specified word.long
getInterval
(BitVector word) Returns an interval given by the smallest and the largest word in the trie starting with the specified word.getInterval
(BooleanIterator iterator) Returns an interval given by the smallest and the largest word in the trie starting with the word returned by the given iterator.long
int
size()
Returns the number of binary words in this trie.toString()
Methods inherited from class it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction
defaultReturnValue, defaultReturnValue
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
Methods inherited from interface it.unimi.dsi.fastutil.objects.Object2LongFunction
andThen, andThenByte, andThenChar, andThenDouble, andThenFloat, andThenInt, andThenLong, andThenObject, andThenReference, andThenShort, applyAsLong, composeByte, composeChar, composeDouble, composeFloat, composeInt, composeLong, composeObject, composeReference, composeShort, get, getOrDefault, getOrDefault, put, put, remove, removeLong
-
Field Details
-
root
The root of the trie.
-
-
Constructor Details
-
ImmutableBinaryTrie
public ImmutableBinaryTrie(Iterable<? extends T> elements, TransformationStrategy<? super T> transformationStrategy) Creates a trie from a set of elements.- Parameters:
elements
- a set of elementstransformationStrategy
- a transformation strategy that must turnelements
into a list of distinct, lexicographically increasing (in iteration order) binary words.
-
-
Method Details
-
buildTrie
Builds a trie recursively.The trie will contain the suffixes of words in
words
starting atpos
.- Parameters:
elements
- a list of elements.pos
- a starting position.- Returns:
- a trie containing the suffixes of words in
words
starting atpos
.
-
size
public int size()Returns the number of binary words in this trie. -
getIndex
-
getLong
- Specified by:
getLong
in interfaceObject2LongFunction<T>
-
containsKey
- Specified by:
containsKey
in interfaceFunction<T,
Long>
-
get
Return the index of the word returned by the given iterator, or -1 if the word is not in this trie.- Parameters:
iterator
- a boolean iterator that will be used to find a word in this trie.- Returns:
- the index of the specified word, or -1 if the word returned by the iterator is not in this trie.
- See Also:
-
getInterval
Returns an interval given by the smallest and the largest word in the trie starting with the specified word.- Parameters:
word
- a word.- Returns:
- an interval given by the smallest and the largest word in the trie
that start with
word
(thus, the empty inteval if no such words exist). - See Also:
-
getInterval
Returns an interval given by the smallest and the largest word in the trie starting with the word returned by the given iterator.- Parameters:
iterator
- an iterator.- Returns:
- an interval given by the smallest and the largest word in the trie
that start with the word returned by
iterator
(thus, the empty interval if no such words exist). - See Also:
-
getApproximatedInterval
Returns an approximated interval around the specified word.Given a word w, the corresponding approximated interval is defined as follows: if the words in the approximator are thought of as left interval extremes in a larger lexicographically ordered set of words, and we number these word intervals using the indices of their left extremes, then the first word extending w would be in the word interval given by the left extreme of the interval returned by this method, whereas the last word extending w would be in the word interval given by the right extreme of the interval returned by this method. If no word in the larger set could possibly extend w (because w is smaller than the lexicographically smallest word in the approximator) the result is just an empty interval.
- Parameters:
element
- an element.- Returns:
- an approximated interval around the specified word.
- See Also:
-
getApproximatedInterval
Returns an approximated prefix interval around the word returned by the specified iterator.- Parameters:
iterator
- an iterator.- Returns:
- an approximated interval around the specified word: if the words in this trie
are thought of as left interval extremes in a larger lexicographically ordered set of words,
and we number these word intervals using the indices of their left extremes,
then the first word extending
word
would be in the word interval given by the left extreme of theLongInterval
returned by this method, whereas the last word extendingword
would be in the word interval given by the right extreme of theLongInterval
returned by this method. - See Also:
-
toString
-