Struct IntervalSet

Source

pub struct IntervalSet<Ix = u32> { /* private fields */ }

Expand description

A set of non-overlapping intervals with automatic merging.

IntervalSet stores a collection of non-overlapping intervals. When inserting intervals that overlap or are adjacent, they are automatically merged into a single interval.

§Type Parameters

Ix - The index type for interval bounds. Defaults to u32.

§Examples

use intervalmap::IntervalSet;

let mut set = IntervalSet::new();
set.insert(0..10);
set.insert(5..15);  // Merges with [0, 10) to form [0, 15)

assert!(set.contains(7));
assert!(!set.contains(20));

Implementations§

Source §

impl<Ix: IndexType> IntervalSet<Ix>

Source

pub fn new() -> Self

Creates a new, empty IntervalSet.

§Examples

use intervalmap::IntervalSet;

let set: IntervalSet<u32> = IntervalSet::new();
assert!(set.is_empty());

Source

pub fn len(&self) -> usize

Returns the number of intervals in the set.

Source

pub fn is_empty(&self) -> bool

Returns true if the set contains no intervals.

Source

pub fn clear(&mut self)

Removes all intervals from the set.

Source

pub fn contains(&self, point: Ix) -> bool

Returns true if the set contains an interval covering the given point.

§Examples

use intervalmap::IntervalSet;

let mut set = IntervalSet::new();
set.insert(0..10);

assert!(set.contains(5));
assert!(!set.contains(10));

Source

pub fn get_interval(&self, point: Ix) -> Option<Range<Ix>>

Returns the interval containing the given point, if any.

§Examples

use intervalmap::IntervalSet;

let mut set = IntervalSet::new();
set.insert(5..15);

assert_eq!(set.get_interval(10), Some(5..15));
assert_eq!(set.get_interval(20), None);

Source

pub fn iter(&self) -> IterSet<'_, Ix>

Returns an iterator over the intervals in the set.

Intervals are yielded in ascending order by start position.

§Examples

use intervalmap::IntervalSet;

let mut set = IntervalSet::new();
set.insert(0..10);
set.insert(20..30);

let intervals: Vec<_> = set.iter().collect();
assert_eq!(intervals, vec![0..10, 20..30]);

Source

pub fn first(&self) -> Option<Range<Ix>>

Returns the first (lowest) interval, or None if empty.

This is an O(log n) operation.

§Examples

use intervalmap::IntervalSet;

let mut set = IntervalSet::new();
assert_eq!(set.first(), None);

set.insert(10..20);
set.insert(0..5);
assert_eq!(set.first(), Some(0..5));

Source

pub fn last(&self) -> Option<Range<Ix>>

Returns the last (highest) interval, or None if empty.

This is an O(log n) operation.

§Examples

use intervalmap::IntervalSet;

let mut set = IntervalSet::new();
assert_eq!(set.last(), None);

set.insert(0..5);
set.insert(10..20);
assert_eq!(set.last(), Some(10..20));

Source

pub fn span(&self) -> Option<Range<Ix>>

Returns the bounding interval that spans from the start of the first interval to the end of the last interval, or None if empty.

This is an O(log n) operation.

§Examples

use intervalmap::IntervalSet;

let mut set = IntervalSet::new();
assert_eq!(set.span(), None);

set.insert(5..10);
set.insert(20..30);
assert_eq!(set.span(), Some(5..30));

Source §

impl<Ix: IndexType + One + Bounded> IntervalSet<Ix>

Source

pub fn overlaps<R: RangeBounds<Ix>>(&self, range: R) -> bool

Returns true if any interval in the set overlaps with the given range.

This is an O(log n) operation.

§Examples

use intervalmap::IntervalSet;

let mut set = IntervalSet::new();
set.insert(10..20);

assert!(set.overlaps(15..25));
assert!(set.overlaps(5..15));
assert!(!set.overlaps(0..5));
assert!(!set.overlaps(25..30));

Source

pub fn covers<R: RangeBounds<Ix>>(&self, range: R) -> bool

Returns true if the entire range is covered by intervals in the set.

This is an O(log n + k) operation where k is the number of intervals overlapping the range.

§Examples

use intervalmap::IntervalSet;

let mut set = IntervalSet::new();
set.insert(0..10);
set.insert(10..20);

assert!(set.covers(5..15));
assert!(set.covers(0..20));
assert!(!set.covers(0..25));  // 20..25 not covered

Source

pub fn insert<R: RangeBounds<Ix>>(&mut self, range: R)

Inserts an interval into the set.

If the interval overlaps or is adjacent to existing intervals, they will be merged.

§Examples

use intervalmap::IntervalSet;

let mut set = IntervalSet::new();
set.insert(0..10);
set.insert(10..20);  // Merges into [0, 20)

assert_eq!(set.len(), 1);

Source

pub fn remove<R: RangeBounds<Ix>>(&mut self, range: R)

Removes an interval from the set.

Any existing intervals that overlap with the removed range will be split, with the overlapping portions removed.

§Examples

use intervalmap::IntervalSet;

let mut set = IntervalSet::new();
set.insert(0..20);
set.remove(5..15);

// Result: [0,5) and [15,20)
assert!(set.contains(3));
assert!(!set.contains(10));
assert!(set.contains(17));

Source

pub fn union(&self, other: &Self) -> Self

Returns a new set containing all intervals from both sets.

Overlapping and adjacent intervals are merged automatically.

§Examples

use intervalmap::interval_set;

let a = interval_set!{ 0..10, 20..30 };
let b = interval_set!{ 5..25 };
let union = a.union(&b);

assert_eq!(union.len(), 1);
assert!(union.contains(15));

Source

pub fn intersection(&self, other: &Self) -> Self

Returns a new set containing only intervals covered by both sets.

§Examples

use intervalmap::interval_set;

let a = interval_set!{ 0..10, 20..30 };
let b = interval_set!{ 5..25 };
let intersection = a.intersection(&b);

let intervals: Vec<_> = intersection.iter().collect();
assert_eq!(intervals, vec![5..10, 20..25]);

Source

pub fn difference(&self, other: &Self) -> Self

Returns a new set containing intervals from self that are not in other.

§Examples

use intervalmap::interval_set;

let a = interval_set!{ 0..20 };
let b = interval_set!{ 5..15 };
let difference = a.difference(&b);

let intervals: Vec<_> = difference.iter().collect();
assert_eq!(intervals, vec![0..5, 15..20]);

Source

pub fn symmetric_difference(&self, other: &Self) -> Self

Returns a new set containing intervals that are in either set, but not both.

§Examples

use intervalmap::interval_set;

let a = interval_set!{ 0..10 };
let b = interval_set!{ 5..15 };
let sym_diff = a.symmetric_difference(&b);

let intervals: Vec<_> = sym_diff.iter().collect();
assert_eq!(intervals, vec![0..5, 10..15]);

Source

pub fn gaps(&self) -> Gaps<'_, Ix>

Returns an iterator over the gaps between intervals in the set.

This iterates over the ranges that are NOT covered by any interval in the set, but only between the first and last intervals. It does not yield unbounded gaps before the first interval or after the last.

§Examples

use intervalmap::IntervalSet;

let mut set = IntervalSet::new();
set.insert(0..10);
set.insert(20..30);
set.insert(40..50);

let gaps: Vec<_> = set.gaps().collect();
assert_eq!(gaps, vec![10..20, 30..40]);

Source

pub fn iter_overlapping<R: RangeBounds<Ix>>( &self, range: R, ) -> IterOverlapping<'_, Ix>

Returns an iterator over intervals that overlap with the given range.

This is an O(log n + k) operation where k is the number of overlapping intervals.

§Examples

use intervalmap::IntervalSet;

let mut set = IntervalSet::new();
set.insert(0..10);
set.insert(20..30);
set.insert(40..50);

let overlapping: Vec<_> = set.iter_overlapping(15..45).collect();
assert_eq!(overlapping, vec![20..30, 40..50]);

Source

pub fn retain<F: FnMut(&Range<Ix>) -> bool>(&mut self, f: F)

Keeps only the intervals matching the predicate.

§Examples

use intervalmap::IntervalSet;

let mut set = IntervalSet::new();
set.insert(0..10);
set.insert(20..30);
set.insert(40..50);

// Keep only intervals that start before 25
set.retain(|r| r.start < 25);

let intervals: Vec<_> = set.iter().collect();
assert_eq!(intervals, vec![0..10, 20..30]);

Source

pub fn split_at(&mut self, point: Ix)

Splits all intervals at the given point.

If an interval contains the point, it will be split into two intervals: one ending at the point and one starting at the point.

§Examples

use intervalmap::IntervalSet;

let mut set = IntervalSet::new();
set.insert(0..20);

set.split_at(10);

let intervals: Vec<_> = set.iter().collect();
assert_eq!(intervals, vec![0..10, 10..20]);