#map #library #data

nightly gap_query_interval_tree

A crate that provides a gap-query optimized interval-tree data-structure

3 releases (breaking)

0.2.0 Dec 3, 2023
0.1.0 Jul 1, 2023
0.0.1 Jun 11, 2023

#2425 in Data structures

28 downloads per month

AGPL-3.0-or-later

30KB
488 lines

A crate that provides a gap-query optimized interval-tree data-structure.

no_std is supported and should work with the default features.

There are three main operations available on this data-structure: insertion, removal and gap-queries. Each of which are O(log(N) + K) where N is the total number of intervals in the tree and K is the number of intervals required to be processed.

Here are visualizations of the three operations:

Insertion

insertion

Removal

removal

Gap-Query

gap-query


lib.rs:

A crate that provides a gap-query optimized interval-tree data-structure.

no_std is supported and should work with the default features.

There are three main operations available on this data-structure: insertion, removal and gap-queries. Each of which are O(log(N) + K) where N is the total number of intervals in the tree and K is the number of intervals required to be processed.

Here are visualizations of the three operations:

Insertion

Removal

Gap-Query

Dependencies

~1.4–2MB
~43K SLoC