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

Field Summary

Fields
Modifier and Type	Field	Description
`static int`	`BITS_IN_INDEX`
`private BitSet`	`bitSet`
`private Equal<K>`	`equal`
`private Hash<K>`	`hash`
`static int`	`MAX_INDEX`
`static int`	`MIN_INDEX`
`private Seq<Node<K,V>>`	`seq`
`static int`	`SIZE`

Constructor Summary

Constructors
Modifier	Constructor	Description
`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.

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()`

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

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:

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)
```
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 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()
```

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

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

Class HashArrayMappedTrie<K,​V>

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

seq

bitSet

hash

equal

BITS_IN_INDEX

SIZE

MIN_INDEX

MAX_INDEX

Constructor Detail

HashArrayMappedTrie

Method Detail

empty

emptyKeyInteger

isEmpty

hamt

find

find

set

set

set

toStream

toList

toList

toString

foldLeftOnNode

foldLeft

foldLeft

getBitSet

getSeq

length

Class HashArrayMappedTrie<K,V>