Package fj.data.hamt

Class HashArrayMappedTrie<K,​V>


  • public final class HashArrayMappedTrie<K,​V>
    extends java.lang.Object
    A hash array mapped trie (HAMT) is an implementation of an associative array that combines the characteristics of a hash table and an array mapped trie. It is a refined version of the more general notion of a hash tree. Based on "Ideal Hash Trees" by Phil Bagwell, available from http://lampwww.epfl.ch/papers/idealhashtrees.pdf
    • Field Detail

      • bitSet

        private final BitSet bitSet
      • hash

        private final Hash<K> hash
      • equal

        private final Equal<K> equal
      • SIZE

        public static final int SIZE
      • MAX_INDEX

        public static final int MAX_INDEX
    • Constructor Detail

      • HashArrayMappedTrie

        private HashArrayMappedTrie​(BitSet bs,
                                    Seq<Node<K,​V>> s,
                                    Equal<K> e,
                                    Hash<K> h)
        Creates an empty trie for the bitset, sequence of nodes, equal and hash.
        Parameters:
        bs - - The set of bits to indicate which of the SIZE nodes in the sequence are used.
        s - - The sequence of HAMT nodes - either a HAMT or a key-value pair.
        e - - Equality instance for keys.
        h - - Hash instance for keys.
    • Method Detail

      • emptyKeyInteger

        public static <V> HashArrayMappedTrie<java.lang.Integer,​V> emptyKeyInteger()
        Create and empty trie keyed by integer.
      • isEmpty

        public boolean isEmpty()
        Returns if the trie is empty.
      • find

        public Option<V> find​(K k)
        Returns an optional value for the given key k.
      • find

        public Option<V> find​(K k,
                              int lowIndex,
                              int highIndex)
        Returns an optional value for the given key k for those nodes between lowIndex (inclusive) and highIndex (exclusive).
      • set

        private HashArrayMappedTrie<K,​V> set​(K k,
                                                   V v,
                                                   int lowIndex,
                                                   int highIndex)
        Sets the key-value pair (k, v) for the bit range lowIndex (inclusive) to highIndex (exclusive).
      • toStream

        public Stream<P2<K,​V>> toStream()
        Returns a stream of key-value pairs.
      • toList

        public List<P2<K,​V>> toList​(Ord<K> o)
        Returns the list of key-value pairs, ordered by key.
      • toList

        public List<P2<K,​V>> toList()
        Returns a list of key-value pairs.
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • foldLeftOnNode

        public <B> B foldLeftOnNode​(F2<B,​Node<K,​V>,​B> f,
                                    B b)
        Performs a left-fold reduction across this trie.
      • foldLeft

        public <B> B foldLeft​(F2<B,​P2<K,​V>,​B> f,
                              F2<B,​HashArrayMappedTrie<K,​V>,​B> g,
                              B b)
        Performs a left-fold reduction across this trie.
      • foldLeft

        public <B> B foldLeft​(F2<B,​P2<K,​V>,​B> f,
                              B b)
        Performs a left-fold reduction across this trie.
      • getBitSet

        public BitSet getBitSet()
      • length

        public int length()
        Returns the number of elements in the trie.