Class ZFastTrie.Handle2NodeMap<U>

  • Enclosing class:
    ZFastTrie<T>

    protected static final class ZFastTrie.Handle2NodeMap<U>
    extends java.lang.Object
    A linear-probing hash map that compares keys using signatures as a first try.
    • 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 entry node.
      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.
    • Field Detail

      • transform

        protected final it.unimi.dsi.bits.TransformationStrategy<? super U> transform
        The transformation strategy.
      • 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 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 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:
        java.lang.IllegalStateException - if n is not in the table.
      • 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 java.lang.String toString()
        Overrides:
        toString in class java.lang.Object