Package io.vavr.collection
Class BitMappedTrie<T>
- java.lang.Object
-
- io.vavr.collection.BitMappedTrie<T>
-
- All Implemented Interfaces:
java.io.Serializable
final class BitMappedTrie<T> extends java.lang.Object implements java.io.Serializable
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
Fields Modifier and Type Field Description private java.lang.Object
array
(package private) static int
BRANCHING_BASE
(package private) static int
BRANCHING_FACTOR
(package private) static int
BRANCHING_MASK
private int
depthShift
private static BitMappedTrie<?>
EMPTY
private int
length
private int
offset
private static long
serialVersionUID
(package private) ArrayType<T>
type
-
Constructor Summary
Constructors Modifier Constructor Description private
BitMappedTrie(ArrayType<T> type, java.lang.Object array, int offset, int length, int depthShift)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private BitMappedTrie<T>
append(java.util.Iterator<? extends T> iterator, int size)
(package private) BitMappedTrie<T>
appendAll(java.lang.Iterable<? extends T> iterable)
private NodeModifier
appendToLeaf(java.util.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, java.lang.Object array, int offset, int length, int shift)
(package private) static int
digit(int num, int depthShift)
(package private) BitMappedTrie<T>
drop(int n)
(package private) static <T> BitMappedTrie<T>
empty()
(package private) BitMappedTrie<T>
filter(java.util.function.Predicate<? super T> predicate)
private int
filter(java.util.function.Predicate<? super T> predicate, java.lang.Object results, int index, T leaf, int start, int end)
(package private) static int
firstDigit(int num, int depthShift)
(package private) T
get(int index)
(package private) java.lang.Object
getLeaf(int index)
fetch the leaf, corresponding to the given index.private java.lang.Object
getLeafGeneral(int index)
private int
getMin(int start, int index, java.lang.Object leaf)
private boolean
isFullLeft()
private boolean
isFullRight()
(package private) Iterator<T>
iterator()
(package private) static int
lastDigit(int num)
(package private) int
length()
(package private) <U> BitMappedTrie<U>
map(java.util.function.Function<? super T,? extends U> mapper)
private <U> int
map(java.util.function.Function<? super T,? extends U> mapper, java.lang.Object results, int index, T leaf, int start, int end)
private java.lang.Object
modify(java.lang.Object root, int depthShift, int index, NodeModifier node, NodeModifier leaf)
private java.lang.Object
modifyNonLeaf(java.lang.Object root, int depthShift, int index, NodeModifier node, NodeModifier leaf)
(package private) static <T> BitMappedTrie<T>
ofAll(java.lang.Object array)
private static <T> BitMappedTrie<T>
ofAll(java.lang.Object array, ArrayType<T> type, int size)
private BitMappedTrie<T>
prepend(java.util.Iterator<? extends T> iterator, int size)
(package private) BitMappedTrie<T>
prependAll(java.lang.Iterable<? extends T> iterable)
private NodeModifier
prependToLeaf(java.util.Iterator<? extends T> iterator)
private java.lang.Object
setNewNode(NodeModifier node, int previousIndex, java.lang.Object array, int offset)
(package private) BitMappedTrie<T>
take(int n)
private static int
treeSize(int branchCount, int depthShift)
(package private) BitMappedTrie<T>
update(int index, T element)
private NodeModifier
updateLeafWith(ArrayType<T> type, T element)
(package private) <T2> int
visit(LeafVisitor<T2> visitor)
-
-
-
Field Detail
-
BRANCHING_BASE
static final int BRANCHING_BASE
- See Also:
- Constant Field Values
-
BRANCHING_FACTOR
static final int BRANCHING_FACTOR
- See Also:
- Constant Field Values
-
BRANCHING_MASK
static final int BRANCHING_MASK
- See Also:
- Constant Field Values
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
EMPTY
private static final BitMappedTrie<?> EMPTY
-
array
private final java.lang.Object array
-
offset
private final int offset
-
length
private final int length
-
depthShift
private final int depthShift
-
-
Method Detail
-
firstDigit
static int firstDigit(int num, int depthShift)
-
digit
static int digit(int num, int depthShift)
-
lastDigit
static int lastDigit(int num)
-
empty
static <T> BitMappedTrie<T> empty()
-
treeSize
private static int treeSize(int branchCount, int depthShift)
-
ofAll
static <T> BitMappedTrie<T> ofAll(java.lang.Object array)
-
ofAll
private static <T> BitMappedTrie<T> ofAll(java.lang.Object array, ArrayType<T> type, int size)
-
boxed
private BitMappedTrie<T> boxed()
-
prependAll
BitMappedTrie<T> prependAll(java.lang.Iterable<? extends T> iterable)
-
prepend
private BitMappedTrie<T> prepend(java.util.Iterator<? extends T> iterator, int size)
-
isFullLeft
private boolean isFullLeft()
-
prependToLeaf
private NodeModifier prependToLeaf(java.util.Iterator<? extends T> iterator)
-
appendAll
BitMappedTrie<T> appendAll(java.lang.Iterable<? extends T> iterable)
-
append
private BitMappedTrie<T> append(java.util.Iterator<? extends T> iterator, int size)
-
isFullRight
private boolean isFullRight()
-
appendToLeaf
private NodeModifier appendToLeaf(java.util.Iterator<? extends T> iterator, int leafSize)
-
update
BitMappedTrie<T> update(int index, T element)
-
updateLeafWith
private NodeModifier updateLeafWith(ArrayType<T> type, T element)
-
drop
BitMappedTrie<T> drop(int n)
-
take
BitMappedTrie<T> take(int n)
-
arePointingToSameLeaf
private boolean arePointingToSameLeaf(int i, int j)
-
collapsed
private static <T> BitMappedTrie<T> collapsed(ArrayType<T> type, java.lang.Object array, int offset, int length, int shift)
-
modify
private java.lang.Object modify(java.lang.Object root, int depthShift, int index, NodeModifier node, NodeModifier leaf)
-
modifyNonLeaf
private java.lang.Object modifyNonLeaf(java.lang.Object root, int depthShift, int index, NodeModifier node, NodeModifier leaf)
-
setNewNode
private java.lang.Object setNewNode(NodeModifier node, int previousIndex, java.lang.Object array, int offset)
-
get
T get(int index)
-
getLeaf
java.lang.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!
-
getLeafGeneral
private java.lang.Object getLeafGeneral(int index)
-
visit
<T2> int visit(LeafVisitor<T2> visitor)
-
getMin
private int getMin(int start, int index, java.lang.Object leaf)
-
filter
BitMappedTrie<T> filter(java.util.function.Predicate<? super T> predicate)
-
filter
private int filter(java.util.function.Predicate<? super T> predicate, java.lang.Object results, int index, T leaf, int start, int end)
-
map
<U> BitMappedTrie<U> map(java.util.function.Function<? super T,? extends U> mapper)
-
map
private <U> int map(java.util.function.Function<? super T,? extends U> mapper, java.lang.Object results, int index, T leaf, int start, int end)
-
length
int length()
-
-