Package fj.data.hamt
Class HashArrayMappedTrie<K,V>
java.lang.Object
fj.data.hamt.HashArrayMappedTrie<K,V>
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 Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionstatic <K,
V> HashArrayMappedTrie <K, V> Creates an empty trie.static <V> HashArrayMappedTrie
<Integer, V> Create and empty trie keyed by integer.Returns an optional value for the given key k.Returns an optional value for the given key k for those nodes between lowIndex (inclusive) and highIndex (exclusive).<B> B
Performs a left-fold reduction across this trie.<B> B
Performs a left-fold reduction across this trie.<B> B
foldLeftOnNode
(F2<B, Node<K, V>, B> f, B b) Performs a left-fold reduction across this trie.getSeq()
private static <K,
V> HashArrayMappedTrie <K, V> Static constructor for a HAMT instance.boolean
isEmpty()
Returns if the trie is empty.int
length()
Returns the number of elements in the trie.Adds the product of key-value (k, v) pairs to the trie.Adds the key-value pair (k, v) to the trie.private HashArrayMappedTrie
<K, V> Sets the key-value pair (k, v) for the bit range lowIndex (inclusive) to highIndex (exclusive).toList()
Returns a list of key-value pairs.Returns the list of key-value pairs, ordered by key.toStream()
Returns a stream of key-value pairs.toString()
-
Field Details
-
seq
-
bitSet
-
hash
-
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
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
Creates an empty trie. -
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
Returns an optional value for the given key k. -
find
Returns an optional value for the given key k for those nodes between lowIndex (inclusive) and highIndex (exclusive). -
set
Adds the key-value pair (k, v) to the trie. -
set
Adds the product of key-value (k, v) pairs to the trie. -
set
Sets the key-value pair (k, v) for the bit range lowIndex (inclusive) to highIndex (exclusive). -
toStream
Returns a stream of key-value pairs. -
toList
Returns the list of key-value pairs, ordered by key. -
toList
Returns a list of key-value pairs. -
toString
-
foldLeftOnNode
Performs a left-fold reduction across this trie. -
foldLeft
Performs a left-fold reduction across this trie. -
foldLeft
Performs a left-fold reduction across this trie. -
getBitSet
-
getSeq
-
length
public int length()Returns the number of elements in the trie.
-