Package fj.data.hamt
Class HashArrayMappedTrie<K,V>
- java.lang.Object
-
- fj.data.hamt.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
-
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description static <K,V>
HashArrayMappedTrie<K,V>empty(Equal<K> e, Hash<K> h)
Creates an empty trie.static <V> HashArrayMappedTrie<java.lang.Integer,V>
emptyKeyInteger()
Create and empty trie keyed by integer.Option<V>
find(K k)
Returns an optional value for the given key k.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).<B> B
foldLeft(F2<B,P2<K,V>,B> f, B b)
Performs a left-fold reduction across this trie.<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.<B> B
foldLeftOnNode(F2<B,Node<K,V>,B> f, B b)
Performs a left-fold reduction across this trie.BitSet
getBitSet()
Seq<Node<K,V>>
getSeq()
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.boolean
isEmpty()
Returns if the trie is empty.int
length()
Returns the number of elements in the trie.HashArrayMappedTrie<K,V>
set(List<P2<K,V>> list)
Adds the product of key-value (k, v) pairs to the trie.HashArrayMappedTrie<K,V>
set(K k, V v)
Adds the key-value pair (k, v) to the trie.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).List<P2<K,V>>
toList()
Returns a list of key-value pairs.List<P2<K,V>>
toList(Ord<K> o)
Returns the list of key-value pairs, ordered by key.Stream<P2<K,V>>
toStream()
Returns a stream of key-value pairs.java.lang.String
toString()
-
-
-
Field Detail
-
bitSet
private final BitSet bitSet
-
BITS_IN_INDEX
public static final int BITS_IN_INDEX
- See Also:
- Constant Field Values
-
SIZE
public static final int SIZE
-
MIN_INDEX
public static final int MIN_INDEX
- See Also:
- Constant Field Values
-
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
-
empty
public static <K,V> HashArrayMappedTrie<K,V> empty(Equal<K> e, Hash<K> h)
Creates an empty trie.
-
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.
-
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, 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).
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.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.
-
-