it.unimi.dsi.mg4j.util
Class ImmutableBinaryTrie

java.lang.Object
  extended by it.unimi.dsi.mg4j.util.ImmutableBinaryTrie
All Implemented Interfaces:
Serializable
Direct Known Subclasses:
ImmutableTriePrefixTree

Deprecated. Moved to dsiutils.

@Deprecated
public class ImmutableBinaryTrie
extends Object
implements Serializable

An immutable implementation of binary tries.

Instance of this class are built starting from a lexicographically ordered list of BitVectors 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:
0.9.2
Author:
Sebastiano Vigna
See Also:
Serialized Form

Nested Class Summary
protected static class ImmutableBinaryTrie.Node
          Deprecated. A node in the trie.
 
Field Summary
protected  ImmutableBinaryTrie.Node root
          Deprecated. The root of the trie.
static long serialVersionUID
          Deprecated.  
 
Constructor Summary
ImmutableBinaryTrie(List<BitVector> words)
          Deprecated. Creates a trie from a list of binary words.
 
Method Summary
 int get(BitVector word)
          Deprecated. Return the index of the specified word, or -1 if the word is not this trie.
 int get(BooleanIterator iterator)
          Deprecated. Return the index of the word returned by the given iterator, or -1 if the word is not this trie.
 Interval getApproximatedInterval(BitVector word)
          Deprecated. Returns an approximated prefix interval around the specified word.
 Interval getApproximatedInterval(BooleanIterator iterator)
          Deprecated. Returns an approximated prefix interval around the word returned by the specified iterator.
 Interval getInterval(BitVector word)
          Deprecated. Returns an interval given by the smallest and the largest word in the trie starting with the specified word.
 Interval getInterval(BooleanIterator iterator)
          Deprecated. Returns an interval given by the smallest and the largest word in the trie starting with the word returned by the given iterator.
 int size()
          Deprecated. Returns the number of binary words in this trie.
 String toString()
          Deprecated.  
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

serialVersionUID

public static final long serialVersionUID
Deprecated. 
See Also:
Constant Field Values

root

protected final ImmutableBinaryTrie.Node root
Deprecated. 
The root of the trie.

Constructor Detail

ImmutableBinaryTrie

public ImmutableBinaryTrie(List<BitVector> words)
Deprecated. 
Creates a trie from a list of binary words.

Parameters:
words - a list of distinct, lexicographically increasing binary words.
Method Detail

size

public int size()
Deprecated. 
Returns the number of binary words in this trie.

Returns:
the number of binary words in this trie.

get

public int get(BitVector word)
Deprecated. 
Return the index of the specified word, or -1 if the word is not this trie.

Parameters:
word - a word.
Returns:
the index of the specified word, or -1 if the word is not this trie.
See Also:
get(BooleanIterator)

get

public int get(BooleanIterator iterator)
Deprecated. 
Return the index of the word returned by the given iterator, or -1 if the word is not 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 this trie.
See Also:
get(BitVector)

getInterval

public Interval getInterval(BitVector word)
Deprecated. 
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(BooleanIterator)

getInterval

public Interval getInterval(BooleanIterator iterator)
Deprecated. 
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 inteval if no such words exist).
See Also:
getInterval(BitVector)

getApproximatedInterval

public Interval getApproximatedInterval(BitVector word)
Deprecated. 
Returns an approximated prefix interval around the specified word.

Parameters:
word - a word.
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 the Interval returned by this method, whereas the last word extending word would be in the word interval given by the right extreme of the Interval returned by this method.
See Also:
getApproximatedInterval(BooleanIterator)

getApproximatedInterval

public Interval getApproximatedInterval(BooleanIterator iterator)
Deprecated. 
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 the Interval returned by this method, whereas the last word extending word would be in the word interval given by the right extreme of the Interval returned by this method.
See Also:
getApproximatedInterval(BitVector)

toString

public String toString()
Deprecated. 
Overrides:
toString in class Object