Class HashArrayMappedTrie<K,V>

java.lang.Object
fj.data.hamt.HashArrayMappedTrie<K,V>
public final class HashArrayMappedTrie<K,V> extends 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 Details

    • seq

      private final Seq<Node<K,V>> seq

    • bitSet

      private final BitSet bitSet

    • hash

      private final Hash<K> hash

    • equal

      private final Equal<K> equal

    • BITS_IN_INDEX

      public static final int BITS_IN_INDEX
      See Also:

    • SIZE

      public static final int SIZE

    • MIN_INDEX

      public static final int MIN_INDEX
      See Also:

    • MAX_INDEX

      public static final int MAX_INDEX

  • Constructor Details

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

    • empty

      public static <K,V> HashArrayMappedTrie<K,V> empty(Equal<K> e, Hash<K> h)
      Creates an empty trie.

    • emptyKeyInteger

      public static <V> HashArrayMappedTrie<Integer,V> emptyKeyInteger()
      Create and empty trie keyed by integer.

    • isEmpty

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

    • hamt

      private static <K,V> HashArrayMappedTrie<K,V> hamt(BitSet bs, Seq<Node<K,V>> s, Equal<K> e, Hash<K> h)
      Static constructor for a HAMT instance.

    • 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

      public HashArrayMappedTrie<K,V> set(K k, V v)
      Adds the key-value pair (k, v) to the trie.

    • set

      public HashArrayMappedTrie<K,V> set(List<P2<K,V>> list)
      Adds the product of key-value (k, v) pairs to the trie.

    • 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 String toString()
      Overrides:
      toString in class 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()

    • getSeq

      public Seq<Node<K,V>> getSeq()

    • length

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