Vavr 0.10.6 · io.vavr.collection.BitMappedTrie · APIdia, the JavaDoc alternative

A `bit-mapped trie` is a very wide and shallow tree (for integer indices the depth will be `≤6`). Each node has a maximum of `32` children (configurable). Access to a given position is done by converting the index to a base 32 number and using each digit to descend down the tree. Modifying the tree is done similarly, but along the way the path is copied, returning a new root every time. `Append` inserts in the last leaf, or if the tree is full from the right, it adds another layer on top of it (the old root will be the first of the new one). `Prepend` is done similarly, but an offset is needed, because adding a new top node (where the current root would be the last node of the new root) shifts the indices by half of the current tree's full size. The `offset` shifts them back to the correct index. `Slice` is done by trimming the path from the root and discarding any `leading`/`trailing` values in effectively constant time (without memory leak, as in `Java`/`Clojure`).

Field Summary

Modifier and Type	Field and Description
private final Object	array
pack-priv static final int	BRANCHING_BASE
pack-priv static final int	BRANCHING_FACTOR
pack-priv static final int	BRANCHING_MASK
private final int	depthShift
private static final BitMappedTrie<?>	EMPTY
private final int	length
private final int	offset
private static final long	serialVersionUID
pack-priv final ArrayType<T>	type

Constructor Summary

Access	Constructor and Description
private	BitMappedTrie(ArrayType<T> type, Object array, int offset, int length, int depthShift)

Method Summary

Modifier and Type	Method and Description
private BitMappedTrie<T>	append(Iterator<? extends T> iterator, int size)
pack-priv BitMappedTrie<T>	appendAll(Iterable<? extends T> iterable)
private NodeModifier	appendToLeaf(Iterator<? extends T> iterator, int leafSize)
private boolean	arePointingToSameLeaf(int i, int j)
private BitMappedTrie<T>	boxed()
private static <T> BitMappedTrie<T>	collapsed(ArrayType<T> type, Object array, int offset, int length, int shift)
pack-priv static int	digit(int num, int depthShift)
pack-priv BitMappedTrie<T>	drop(int n)
pack-priv static <T> BitMappedTrie<T>	empty()
pack-priv BitMappedTrie<T>	filter(Predicate<? super T> predicate)
private int	filter(Predicate<? super T> predicate, Object results, int index, T leaf, int start, int end)
pack-priv static int	firstDigit(int num, int depthShift)
pack-priv T	get(int index)
pack-priv Object	getLeaf(int index) fetch the leaf, corresponding to the given index.
private Object	getLeafGeneral(int index)
private int	getMin(int start, int index, Object leaf)
private boolean	isFullLeft()
private boolean	isFullRight()
pack-priv Iterator<T>	iterator()
pack-priv static int	lastDigit(int num)
pack-priv int	length()
pack-priv <U> BitMappedTrie<U>	map(Function<? super T, ? extends U> mapper)
private <U> int	map(Function<? super T, ? extends U> mapper, Object results, int index, T leaf, int start, int end)
private Object	modify(Object root, int depthShift, int index, NodeModifier node, NodeModifier leaf)
private Object	modifyNonLeaf(Object root, int depthShift, int index, NodeModifier node, NodeModifier leaf)
pack-priv static <T> BitMappedTrie<T>	ofAll(Object array)
private static <T> BitMappedTrie<T>	ofAll(Object array, ArrayType<T> type, int size)
private BitMappedTrie<T>	prepend(Iterator<? extends T> iterator, int size)
pack-priv BitMappedTrie<T>	prependAll(Iterable<? extends T> iterable)
private NodeModifier	prependToLeaf(Iterator<? extends T> iterator)
private Object	setNewNode(NodeModifier node, int previousIndex, Object array, int offset)
pack-priv BitMappedTrie<T>	take(int n)
private static int	treeSize(int branchCount, int depthShift)
pack-priv BitMappedTrie<T>	update(int index, T element)
private NodeModifier	updateLeafWith(ArrayType<T> type, T element)
pack-priv <T2> int	visit(LeafVisitor<T2> visitor)

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

array	back to summary
private final Object array Annotations @SuppressWarnings:serial

BRANCHING_BASE	back to summary
pack-priv static final int BRANCHING_BASE

BRANCHING_FACTOR	back to summary
pack-priv static final int BRANCHING_FACTOR

BRANCHING_MASK	back to summary
pack-priv static final int BRANCHING_MASK

depthShift	back to summary
private final int depthShift

EMPTY	back to summary
private static final BitMappedTrie<?> EMPTY

length	back to summary
private final int length

offset	back to summary
private final int offset

serialVersionUID	back to summary
private static final long serialVersionUID

type	back to summary
pack-priv final ArrayType<T> type

Constructor Detail

BitMappedTrie	back to summary
private BitMappedTrie(ArrayType<T> type, Object array, int offset, int length, int depthShift)

Method Detail

append	back to summary
private BitMappedTrie<T> append(Iterator<? extends T> iterator, int size)

appendAll	back to summary
pack-priv BitMappedTrie<T> appendAll(Iterable<? extends T> iterable)

appendToLeaf	back to summary
private NodeModifier appendToLeaf(Iterator<? extends T> iterator, int leafSize)

arePointingToSameLeaf	back to summary
private boolean arePointingToSameLeaf(int i, int j)

boxed	back to summary
private BitMappedTrie<T> boxed()

collapsed	back to summary
private static <T> BitMappedTrie<T> collapsed(ArrayType<T> type, Object array, int offset, int length, int shift)

digit	back to summary
pack-priv static int digit(int num, int depthShift)

drop	back to summary
pack-priv BitMappedTrie<T> drop(int n)

empty	back to summary
pack-priv static <T> BitMappedTrie<T> empty() Annotations @SuppressWarnings:unchecked

filter	back to summary
pack-priv BitMappedTrie<T> filter(Predicate<? super T> predicate)

filter	back to summary
private int filter(Predicate<? super T> predicate, Object results, int index, T leaf, int start, int end)

firstDigit	back to summary
pack-priv static int firstDigit(int num, int depthShift)

get	back to summary
pack-priv T get(int index)

getLeaf	back to summary
pack-priv Object getLeaf(int index) fetch the leaf, corresponding to the given index. Node: the offset and length should be taken into consideration as there may be leading and trailing garbage. Also, the returned array is mutable, but should not be mutated! Annotations @SuppressWarnings:WeakerAccess

getLeaf

back to summary

pack-priv Object getLeaf(int index)

fetch the leaf, corresponding to the given index. Node: the offset and length should be taken into consideration as there may be leading and trailing garbage. Also, the returned array is mutable, but should not be mutated!

Annotations

@SuppressWarnings:WeakerAccess

getLeafGeneral	back to summary
private Object getLeafGeneral(int index)

getMin	back to summary
private int getMin(int start, int index, Object leaf)

isFullLeft	back to summary
private boolean isFullLeft()

isFullRight	back to summary
private boolean isFullRight()

iterator	back to summary
pack-priv Iterator<T> iterator()

lastDigit	back to summary
pack-priv static int lastDigit(int num)

length	back to summary
pack-priv int length()

map	back to summary
pack-priv <U> BitMappedTrie<U> map(Function<? super T, ? extends U> mapper)

map	back to summary
private <U> int map(Function<? super T, ? extends U> mapper, Object results, int index, T leaf, int start, int end)

modify	back to summary
private Object modify(Object root, int depthShift, int index, NodeModifier node, NodeModifier leaf)

modifyNonLeaf	back to summary
private Object modifyNonLeaf(Object root, int depthShift, int index, NodeModifier node, NodeModifier leaf)

ofAll	back to summary
pack-priv static <T> BitMappedTrie<T> ofAll(Object array)

ofAll	back to summary
private static <T> BitMappedTrie<T> ofAll(Object array, ArrayType<T> type, int size)

prepend	back to summary
private BitMappedTrie<T> prepend(Iterator<? extends T> iterator, int size)

prependAll	back to summary
pack-priv BitMappedTrie<T> prependAll(Iterable<? extends T> iterable)

prependToLeaf	back to summary
private NodeModifier prependToLeaf(Iterator<? extends T> iterator)

setNewNode	back to summary
private Object setNewNode(NodeModifier node, int previousIndex, Object array, int offset)

take	back to summary
pack-priv BitMappedTrie<T> take(int n)

treeSize	back to summary
private static int treeSize(int branchCount, int depthShift)

update	back to summary
pack-priv BitMappedTrie<T> update(int index, T element)

updateLeafWith	back to summary
private NodeModifier updateLeafWith(ArrayType<T> type, T element)