Class ZFastTrie.Handle2NodeMap<U>

java.lang.Object
it.unimi.dsi.sux4j.util.ZFastTrie.Handle2NodeMap<U>
Enclosing class:
ZFastTrie<T>
protected static final class ZFastTrie.Handle2NodeMap<U> extends Object
A linear-probing hash map that compares keys using signatures as a first try.

  • Field Details

    • 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 entry node.

    • 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 Details

    • 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 Details

    • 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 of v that will be used as a handle.
      state - the hash state of v precomputed by Hashes.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 of v that will be used as a handle.
      state - the hash state of v precomputed by Hashes.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 as oldNode.
      s - the signature of the handle of oldNode and newNode.

    • 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 of n.
      Throws:
      IllegalStateException - if n 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

      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 of n.

    • 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 (if exact is false, a false positive might be returned).

    • toString

      public String toString()
      Overrides:
      toString in class Object