Name: collection
Owner: Parity Technologies
Description: Deterministic, copy-on-write, balanced search trees
Forked from: krl/collection
Created: 2017-04-28 14:02:50.0
Updated: 2017-04-28 14:02:52.0
Pushed: 2017-04-14 20:17:01.0
Size: 44
Language: Rust
GitHub Committers
| User | Most Recent Commit | # Commits |
|---|
Other Committers
| User | Most Recent Commit | # Commits |
|---|
This library implements persistent datastructures for Rust, where the complexity of the union operation can be sublinear in practical cases.
This is achieved by using deterministically balanced trees, where the
split-points of the tree are determined by the Weight of the elements
in the collection.
That T implements Weight, means that T, or parts of T can be Hashed
this hash is then used to determine the weight, essentialy by counting
leading zeroes in the hash. The weight then determines how many levels to
split.
Cloning a collection is a constant time operation. This is achieved by
the Stash abstraction, which keeps a collection of Nodes, referenced by
a Location indirection.
Each collection can carry different kinds of metadata, metadata is defined
as the operations &T -> Meta<T>, and a binary operation combining
two Meta<T> with each other. So, to implement a Set, you would use
Max<T>, and if you also want constant-time equality checking, you would
add CheckSum<T>
Collection comes with 3 pre-defined sets of operations making up a Set, a Vector, and a Map.
To define a collection, you use the collection! macro:
collection!(Set<T> {
max: Max<T>,
checksum: CheckSum<u64>,
} where T: Ord + Hash);
collection!(Vector<T> {
cardinality: Cardinality<usize>,
checksum: CheckSum<u64>,
} where T: Hash);
collection!(Map<T> {
key: Key<T::Key>,
keysum: KeySum<u64>,
valsum: ValSum<u64>,
} where T: Keyed,
T::Key: Hash,
T::Value: Hash);
GPLv3