### 9 releases (4 stable)

1.1.2 | Oct 22, 2022 |
---|---|

1.1.1 | Jul 17, 2022 |

0.2.3 | Jan 23, 2020 |

0.2.1 | Nov 9, 2019 |

0.1.1 | Nov 8, 2019 |

#**312** in Data structures

**255** downloads per month

Used in **3** crates
(2 directly)

**MIT**license

66KB

1K
SLoC

# Unbounded Interval Tree

A Rust implementation of an interval tree, based on the one described by Cormen et al., (2009), Introduction to Algorithms (3rd ed., Section 14.3: Interval trees, pp. 348–354). An interval tree is useful to query efficiently a database of intervals. This implementation is generic in that it works with intervals of values implementing

traits. The bounds can be inclusive, exclusive, or unbounded. Here are some examples of valid intervals:`Ord``+``Clone`

- [5, 9] <- inclusive/inclusive integers
- [-2.3, 18.81) <- inclusive/exclusive floats
- ("abc", "hi"] <- exclusive/inclusive strings
- (-inf, November 7 2019] <- unbounded/inclusive dates
- [(1, 5), (2, 9)] <- inclusive/inclusive tuples of integers

## How To Use

I would suggest to look at the examples part of the documentation (as they are tested by the Rust ecosystem), but here's a current example.

`use` `unbounded_interval_tree``::`IntervalTree`;`
`use` `std``::``ops``::``Bound``::``{`Included`,` Excluded`,` Unbounded`}``;`
`//` Default interval tree.
`let` `mut` tree `=` `IntervalTree``::`default`(``)``;`
`//` Ranges are defined as a 2-ple of Bounds.
`let` interval1 `=` `(`Included`(``5``)``,` Excluded`(``9``)``)``;`
`let` interval2 `=` `(`Unbounded`,` Included`(``-``2``)``)``;`
`let` interval3 `=` `(`Included`(``30``)``,` Included`(``30``)``)``;`
`//` Add intervals to the tree.
tree`.``insert``(`interval1`)``;`
tree`.``insert``(`interval2`)``;`
tree`.``insert``(`interval3`)``;`
`//` Iterate through the intervals inorder.
`for` `(`start`,` end`)` `in` tree`.``iter``(``)` `{`
`println!``(``"`Start: `{:?}``\t`End: `{:?}``"``,` start`,` end`)``;`
`}`
`//` Get overlapping intervals.
`let` overlaps `=` tree`.``get_interval_overlaps``(``&``(``0``..``30``)``)``;`
`//` Get the difference between the database
`//` of intervals and the query interval.
`let` diff `=` tree`.``get_interval_difference``(``&``(``0``..``=``30``)``)``;`

## Roadmap

*What's next...*

- Allow to remove intervals from the tree (started in the

branch).`delete`- I have added a

method to the API. Removing leaves is significantly simpler with this data structure, hence I started by tackling this problem.`remove_random_leaf`

- I have added a
- Keep the tree balanced, by rotating during insertions/deletions
- Assert that the start bound of an interval is smaller or equal to the end bound of the same interval.

#### Dependencies

~245–485KB