Package fj.data.hamt

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.