# interval_map `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 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, `interval_map` innovatively **uses arrays to simulate pointers** for managing the parent-child references in the red-black tree. This approach also ensures that 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. `interval_map` implements an `IntervalMap` struct: - It accepts `Interval` 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 `interval_map` supports `insert`, `delete`, and `iter` fns. Traversal is performed in the order of `Interval` . For instance, with intervals of type `Interval`: - $[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, `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](examples/new_point.rs). - [x] Add more tests like [etcd](https://github.com/etcd-io/etcd/blob/main/pkg/adt/interval_tree_test.go). - [x] Refine iter mod.