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, removal and search in O(log N). IntervalMap allows to search for all entries overlapping a query (interval or a point, output would be sorted by keys) in O(log N + K) where K is the size of the output.

IntervalSet is a newtype over IntervalMap with empty values.

Features

By default, iset is no_std. Three optional features are:

• std: no additional effects,
• serde: Serialization/Deserialization (requires std environment),
• dot: allows to write interval maps and sets to .dot files (requires std).

Re-exports

• pub use ix::DefaultIx;
• pub use set::IntervalSet;
• pub use entry::Entry;

Modules

• entry
• iter
  Module with various iterators over IntervalMap and IntervalSet.
• ix
  Wrapper around integer types, used as indices within IntervalMap and IntervalSet.
• set
  IntervalSet implementation.

Macros

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

Structs

• IntervalMap
  Map with interval keys (x..y).