GG2002/interval_map

rb-interval-map

rb-interval-map is a map based on interval tree. It fully implements the insertion and deletion functionality of a red-black tree, ensuring that each modification operation requires at most $O(logN)$ time complexity.

The implementation of the interval tree in rb-interval-map references "Introduction to Algorithms" (3rd ed., Section 14.3: Interval trees, pp. 348–354).

To safely and efficiently handle insertion and deletion operations in Rust, rb-interval-map innovatively uses arrays to simulate pointers for managing the parent-child references in the red-black tree. This approach also ensures that rb-interval-map has the Send and Unpin traits, allowing it to be safely transferred between threads and to maintain a fixed memory location during asynchronous operations.

rb-interval-map implements an IntervalMap struct:

• It accepts Interval<T> as the key, where T can be any type that implements Ord trait. Therefore, intervals such as $[1, 2)$ and $["aaa", "bbb")$ are allowed
• The value can be of any type

rb-interval-map supports insert, delete, and iter fns. Traversal is performed in the order of Interval<T> . For instance, with intervals of type Interval<u32>:

• $[1,4)<[2,5)$, because $1<2$
• $[1,4)<[1,5)$, because $4<5$

So the order of intervals in IntervalMap is $[1,4)<[1,5)<[2,5)$.

Currently, rb-interval-map only supports half-open intervals, i.e., $[...,...)$.

Benchmark

The benchmark was conducted on a platform with AMD R7 7840H + DDR5 5600MHz. The result are as follows:

1. Only insert

   insert	100	1000	10, 000	100, 000
   Total time	5.4168 µs	80.518 µs	2.2823 ms	36.528 ms

2. Insert N and remove N

   insert_and_remove	100	1000	10, 000	100, 000
   Total time	10.333 µs	223.43 µs	4.9358 ms	81.634 ms

TODO

• Support for $(...,...)$, $[...,...]$ and $(...,...]$ interval types. There's no way to support these interval type without performance loss now.
• Add Point type for Interval To support Point type, it should also support $[...,...]$, so it couldn't be supported now, either. But you could write code like examples/new_point.
• Add more tests like etcd.
• Refine iter mod.