Lib.rs

Details

The tree is implicit, meaning that nodes do not store explicit pointers to their children. The only thing we store in a node is your data. This is similar to how binary heaps work: all nodes in the tree reside in an array, the root always at index 0, and given a node with index i, its left/right children are found at indices 2*i+1 and 2*i+2. Thus no dynamic memory allocation or deallocation is required. This makes it possible to implement a fast clone operation: instead of traversing the tree, allocating and copying each node individually, we are able to allocate the whole array in a single call and efficiently copy the entire content. The tree also supports a refill operation (currently only implemented for T: Copy), which copies the contents of the master tree into self without allocating at all.

As to delete-range operation, we use a custom algorithm running in O(k + log n) time, where k is the number of items deleted (and returned) and n is the initial size of the tree. Detailed description.

An exhaustive automated test for delete-range has been written and is found in lib.rs. I have tested all trees up to the size n=10. All the other supported operations have been tested extensively for every variation of the tree (we use slightly different algorithms for IntervalTree and for the filtered variants). In general, I feel the quality is already pretty good. If you find any bugs, please open an issue.

The library has been optimized for speed based on profiling. A significant amount of unsafe code is employed. Every occurrence of unsafe code has been carefully reviewed, most have been annotated with comments elaborating on safety.

Usage

Performance

Benchmarks

The first set of benchmarks compares TeardownTree::delete_range() against:

1. BTreeSet::remove() in Rust's standard library
2. Treap
3. SplayTree
4. TeardownSet::delete(), which deletes a single element

I made straightforward modifications to Treap and SplayTree in order to add support for delete_range, however BTreeSet lacks an equivalent operation (it has an O(log n) split, but not merge, see Rust #34666), therefore BTreeSet::remove() is used instead.

As the graph above shows, on my machine the whole refill/teardown sequence on a tree of 1,000,000 u64 items (we refill the tree with elements from the master copy, then delete 1000 items at a time until the tree is empty), is ~20 times faster with TeardownTreeSet<usize>::delete_range() than with BTreeSet<usize>::remove(). It also consumes 45% less memory.

Another set of benchmarks exposes the overhead of several variations of the data structure and its algorithms.

For details, please see the benchmarks page.

Drawbacks

1. No insert operation (yet?..)
2. The storage is not deallocated until the structure is dropped.
3. Fine print regarding complexity: delete_range works in O(k + log n) time, where n is the initial size of the tree, not its current size (if you have already deleted m items, the next delete_range operation will still take O(log n) time in the worst case, not necessarily O(log(n-m))). The same applies to the other logarithmic operations.
4. Performance is sensitive to the size of your data. Starting from a certain size, it is faster to use a TeardownSet<Box<(Key,Value)>> or store the key-value pairs separately and use external handles as keys (e.g. TeardownSet<INDEX_INTO_EXTERNAL_VEC> or TeardownSet<&MyKey>). It's probably a good idea to run some benchmarks to know what's best in your case.