Package it.unimi.dsi.sux4j.util
Class ZFastTrie.Handle2NodeMap<U>
- java.lang.Object
-
- it.unimi.dsi.sux4j.util.ZFastTrie.Handle2NodeMap<U>
-
-
Field Summary
Fields Modifier and Type Field Description protected int
length
The number of slots in the table (always a power of two).protected int
mask
length
− 1.protected ZFastTrie.InternalNode<U>[]
node
The node table.protected long[]
signature
The signature of the handle of the corresponding entrynode
.protected int
size
The number of elements in the table.protected it.unimi.dsi.bits.TransformationStrategy<? super U>
transform
The transformation strategy.
-
Constructor Summary
Constructors Constructor Description Handle2NodeMap(int size, it.unimi.dsi.bits.TransformationStrategy<? super U> transform)
Creates a new handle-to-node map using a given transformation strategy and expected number of elements.Handle2NodeMap(it.unimi.dsi.bits.TransformationStrategy<? super U> transform)
Creates a new handle-to-node map using a given transformation strategy.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
addNew(ZFastTrie.InternalNode<U> v)
Adds a new entry to the table.void
addNew(ZFastTrie.InternalNode<U> n, long s)
Adds a new entry to the table.protected void
assertTable()
void
clear()
protected ZFastTrie.InternalNode<U>
find(it.unimi.dsi.bits.BitVector v, long handleLength, long[] state)
Find a node with given handle using signatures.protected ZFastTrie.InternalNode<U>
findExact(it.unimi.dsi.bits.BitVector v, long handleLength, long[] state)
Find a node with given handle using handles.ZFastTrie.InternalNode<U>
get(it.unimi.dsi.bits.BitVector handle)
Retrieves a node given its handle.protected int
hash(long s)
Generates a hash table position starting from a signature.it.unimi.dsi.fastutil.objects.ObjectSet<it.unimi.dsi.bits.LongArrayBitVector>
keySet()
void
removeExisting(ZFastTrie.InternalNode<U> n, long s)
Removes an existing entry from the table.void
replaceExisting(ZFastTrie.InternalNode<U> oldNode, ZFastTrie.InternalNode<U> newNode, long s)
Replaces an entry with a given node.int
size()
java.lang.String
toString()
it.unimi.dsi.fastutil.objects.ObjectSet<ZFastTrie.Node<U>>
values()
-
-
-
Field Detail
-
transform
protected final it.unimi.dsi.bits.TransformationStrategy<? super U> transform
The transformation strategy.
-
node
protected ZFastTrie.InternalNode<U>[] node
The node table.
-
signature
protected long[] signature
The signature of the handle of the corresponding entrynode
.
-
size
protected int size
The number of elements in the table.
-
length
protected int length
The number of slots in the table (always a power of two).
-
mask
protected int mask
length
− 1.
-
-
Constructor Detail
-
Handle2NodeMap
public Handle2NodeMap(int size, it.unimi.dsi.bits.TransformationStrategy<? super U> transform)
Creates a new handle-to-node map using a given transformation strategy and expected number of elements.- Parameters:
size
- the expected number of elements.transform
- the transformation strategy used for this map.
-
Handle2NodeMap
public Handle2NodeMap(it.unimi.dsi.bits.TransformationStrategy<? super U> transform)
Creates a new handle-to-node map using a given transformation strategy.- Parameters:
transform
- the transformation strategy used for this map.
-
-
Method Detail
-
assertTable
protected void assertTable()
-
hash
protected int hash(long s)
Generates a hash table position starting from a signature.- Parameters:
s
- a signature.- Returns:
- the hash table position of
s
.
-
find
protected ZFastTrie.InternalNode<U> find(it.unimi.dsi.bits.BitVector v, long handleLength, long[] state)
Find a node with given handle using signatures.Note that this function just compares signatures (except for duplicates, which are checked explicitly). Thus, it might return false positives when queried with keys that are not handles. Nonetheless, it will always return a correct result on a handle.
- Parameters:
v
- a bit vector.handleLength
- the length of the prefix ofv
that will be used as a handle.state
- the hash state ofv
precomputed byHashes.preprocessMurmur(BitVector, long)
.- Returns:
- a node with the specified handle signature, or
null
.
-
findExact
protected ZFastTrie.InternalNode<U> findExact(it.unimi.dsi.bits.BitVector v, long handleLength, long[] state)
Find a node with given handle using handles.Note that this function compares handles. Thus, it always returns a correct value.
- Parameters:
v
- a bit vector.handleLength
- the length of the prefix ofv
that will be used as a handle.state
- the hash state ofv
precomputed byHashes.preprocessMurmur(BitVector, long)
.- Returns:
- a node with the specified handle, or
null
.
-
clear
public void clear()
-
keySet
public it.unimi.dsi.fastutil.objects.ObjectSet<it.unimi.dsi.bits.LongArrayBitVector> keySet()
-
values
public it.unimi.dsi.fastutil.objects.ObjectSet<ZFastTrie.Node<U>> values()
-
replaceExisting
public void replaceExisting(ZFastTrie.InternalNode<U> oldNode, ZFastTrie.InternalNode<U> newNode, long s)
Replaces an entry with a given node.- Parameters:
oldNode
- a node appearing in the table.newNode
- a node with the same handle asoldNode
.s
- the signature of the handle ofoldNode
andnewNode
.
-
removeExisting
public void removeExisting(ZFastTrie.InternalNode<U> n, long s)
Removes an existing entry from the table.- Parameters:
n
- the node to be removed.s
- the signature of the handle ofn
.- Throws:
java.lang.IllegalStateException
- ifn
is not in the table.
-
addNew
public void addNew(ZFastTrie.InternalNode<U> v)
Adds a new entry to the table.- Parameters:
v
- a node.- See Also:
addNew(ZFastTrie.InternalNode, long)
-
addNew
public void addNew(ZFastTrie.InternalNode<U> n, long s)
Adds a new entry to the table.Note that as long as the handle of the given node is not in the table this function will always perform correctly. Otherwise, the table will end up containing two copies of the same key (i.e., handle).
- Parameters:
n
- a node.s
- the signature of the handle ofn
.
-
size
public int size()
-
get
public ZFastTrie.InternalNode<U> get(it.unimi.dsi.bits.BitVector handle)
Retrieves a node given its handle.- Parameters:
handle
- a handle.- Returns:
- the node with given handle, or
null
if there is no such node (ifexact
is false, a false positive might be returned).
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-