Package implement persistent array using a variant of rope data structure.
Fundamentally, it can be viewed as a binary-tree of array-blocks, where
each leaf-node is a block of contiguous item of type
T, while intermediate
nodes only hold references to the child nodes, left and right.
To be more precise, intermediate nodes in the tree are organised similar
to rope structure, as a tuple of (weight, left, right) where weight
is the sum of all items present in the leaf-nodes under the left-branch.
Here is a quick list of situation that might require using
- When array size is too large with repeated insert and remove operation.
- When shared ownership is required.
- When shared ownership across concurrent threads.
- To support undo/redo operation for array modifications.
- When splitting up of array and/or joining arrays are frequently done.
- Lazy clone of array using copy-on-write.
rc::Vector is cheap, it creates a shared ownership
of the underlying tree. This is great for applications requiring
shared-ownership, but at the cost of copy-on-write for every mutation in
the Vector, like insert, remove, delete. For applications requiring only
single-ownership insert_mut, remove_mut, delete_mut gives better
performance because the underlying tree is mutated in-place. To help decide
what method to use when, methods that perform in-place mutation are
arc::Vector<T> is thread safe through
Arc. To trade-off
thread-safety for performance use
rc::Vector type, which is same as
arc::Vector type except for using
std::rc::Rc instead of
std::sync::Arc for shared ownership. That is,
traits are not available for
rc::Vector type while it is available
Module implement thread-safe persistent array.
Module implement persistent array, faster but not thread safe.
Error variants that can be returned by this package's API.
Leaf node shall not exceed this default size, refer [Vector::set_leaf_size] for optimal configuration.
Type alias for Result return type, used by this package.