Crate iset

This crates implements map and set with interval keys (ranges x..y). IntervalMap is implemented using red-black binary tree, where each node contains information about the smallest start and largest end in its subtree. The tree takes O(N) space and allows insertion in O(log N). IntervalMap allows to search for all entries overlapping a query (interval or a point, output would be sorted by keys). Search takes O(log N + K) where K is the size of the output. Additionally, you can extract smallest/largest interval with its value in O(log N).

IntervalSet is a newtype over IntervalMap with empty values.

Any iterator that goes over the IntervalMap or IntervalSet returns intervals/values sorted lexicographically by intervals.

This crate allows to write interval maps and sets to .dot files (see IntervalMap::write_dot, IntervalMap::write_dot_without_values and IntervalSet::write_dot). You can disable this feature using cargo build --no-default-features, in that case the crate supports no_std environments.

Since version 0.0.5, this crate supports serialization/deserialization (use optional feature serde).

Re-exports

pub use iter::*;

Modules

iter	Module with various iterators over IntervalMap and IntervalSet.

Macros

interval_map	Macros for IntervalMap creation.
interval_set	Macros for IntervalSet creation.

Structs

IntervalMap	Map with interval keys (ranges x..y).
IntervalSet	Set with interval keys (ranges x..y). Newtype over IntervalMap<T, ()>.

Traits

IndexType

Trait for index types: used in the inner representation of IntervalMap and IntervalSet.

Type Definitions

DefaultIx

Default index type.