Package io.vavr.collection
Class BitMappedTrie<T>
java.lang.Object
io.vavr.collection.BitMappedTrie<T>
- All Implemented Interfaces:
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
FieldsModifier and TypeFieldDescriptionprivate final Object
(package private) static final int
(package private) static final int
(package private) static final int
private final int
private static final BitMappedTrie
<?> private final int
private final int
private static final long
-
Constructor Summary
ConstructorsModifierConstructorDescriptionprivate
BitMappedTrie
(ArrayType<T> type, Object array, int offset, int length, int depthShift) -
Method Summary
Modifier and TypeMethodDescriptionprivate BitMappedTrie
<T> (package private) BitMappedTrie
<T> 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> (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> private int
(package private) static int
firstDigit
(int num, int depthShift) (package private) T
get
(int index) (package private) Object
getLeaf
(int index) fetch the leaf, corresponding to the given index.private Object
getLeafGeneral
(int index) private int
private boolean
private boolean
iterator()
(package private) static int
lastDigit
(int num) (package private) int
length()
(package private) <U> BitMappedTrie
<U> private <U> int
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) (package private) static <T> BitMappedTrie
<T> private static <T> BitMappedTrie
<T> private BitMappedTrie
<T> (package private) 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) (package private) BitMappedTrie
<T> take
(int n) private static int
treeSize
(int branchCount, int depthShift) (package private) BitMappedTrie
<T> private NodeModifier
updateLeafWith
(ArrayType<T> type, T element) (package private) <T2> int
visit
(LeafVisitor<T2> visitor)
-
Field Details
-
BRANCHING_BASE
static final int BRANCHING_BASE- See Also:
-
BRANCHING_FACTOR
static final int BRANCHING_FACTOR- See Also:
-
BRANCHING_MASK
static final int BRANCHING_MASK- See Also:
-
serialVersionUID
private static final long serialVersionUID- See Also:
-
EMPTY
-
type
-
array
-
offset
private final int offset -
length
private final int length -
depthShift
private final int depthShift
-
-
Constructor Details
-
BitMappedTrie
-
-
Method Details
-
firstDigit
static int firstDigit(int num, int depthShift) -
digit
static int digit(int num, int depthShift) -
lastDigit
static int lastDigit(int num) -
empty
-
treeSize
private static int treeSize(int branchCount, int depthShift) -
ofAll
-
ofAll
-
boxed
-
prependAll
-
prepend
-
isFullLeft
private boolean isFullLeft() -
prependToLeaf
-
appendAll
-
append
-
isFullRight
private boolean isFullRight() -
appendToLeaf
-
update
-
updateLeafWith
-
drop
-
take
-
arePointingToSameLeaf
private boolean arePointingToSameLeaf(int i, int j) -
collapsed
private static <T> BitMappedTrie<T> collapsed(ArrayType<T> type, Object array, int offset, int length, int shift) -
modify
-
modifyNonLeaf
private Object modifyNonLeaf(Object root, int depthShift, int index, NodeModifier node, NodeModifier leaf) -
setNewNode
-
get
-
getLeaf
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
-
iterator
-
visit
-
getMin
-
filter
-
filter
-
map
-
map
-
length
int length()
-