Struct IntervalSet

pub struct IntervalSet<T> { /* private fields */ }

IntervalSet is an efficient structure for storing sets of consecutive numbers. Instead of storing an individual entry per value, only the lower and upper bounds (Interval) are stored.

Usage

use s2n_quic_transport::interval_set::IntervalSet;

let mut set = IntervalSet::new();

set.insert_value(0);
set.insert_value(1);
set.insert_value(2);
set.insert_value(3);

// because 0 to 3 are consecutive, only a single interval is stored
assert_eq!(set.interval_len(), 1);

set.insert_value(5);
set.insert_value(6);

// 5 and 6 are not consecutive with 0 to 3 so a new entry is created
assert_eq!(set.interval_len(), 2);

set.insert_value(4);

// inserting a 4 merges all of the intervals into a single entry
assert_eq!(set.interval_len(), 1);

// ranges of numbers can be inserted at the same time
set.insert(12..15);
set.insert(18..=21);

assert_eq!(set.interval_len(), 3);

// ranges can also be removed
set.remove(0..22);

assert_eq!(set.interval_len(), 0);

Implementations

impl<T> IntervalSet<T>

pub fn new() -> IntervalSet<T>

Creates an empty IntervalSet

Examples

let mut set = IntervalSet::new();
assert!(set.insert(0..4).is_ok());

pub fn with_capacity(capacity: usize) -> IntervalSet<T>

Creates an empty IntervalSet with a specific capacity. This preallocates enough memory for capacity elements, so that the IntervalSet does not have to be reallocated until it contains at least that many values.

Examples

let mut set = IntervalSet::with_capacity(10);
assert!(set.insert(0..4).is_ok());

pub fn with_limit(limit: NonZeroUsize) -> IntervalSet<T>

Creates an empty IntervalSet with a specific limit. The number of elements in the set cannot exceed this amount, otherwise insert calls will be rejected.

Examples

use core::num::NonZeroUsize;
let mut set = IntervalSet::with_limit(NonZeroUsize::new(1).unwrap());
assert!(set.insert(0..4).is_ok());
assert!(set.insert(12..16).is_err());
assert!(set.insert(4..12).is_ok());
assert!(set.insert(12..16).is_ok());

pub fn set_limit(&mut self, limit: NonZeroUsize)

Sets an element limit for the given IntervalSet. The number of elements in the set cannot exceed this amount, otherwise insert calls will be rejected

Note: calling this will not drop existing intervals that exceed the new limit and will only be applied to later calls to insert.

Examples

use core::num::NonZeroUsize;
let mut set = IntervalSet::new();
assert!(set.insert(0..4).is_ok());
set.set_limit(NonZeroUsize::new(1).unwrap());
assert!(set.insert(4..8).is_ok());
assert!(set.insert(12..16).is_err());

pub fn remove_limit(&mut self)

Removes the element limit for the given IntervalSet.

Examples

use core::num::NonZeroUsize;
let mut set = IntervalSet::with_limit(NonZeroUsize::new(1).unwrap());
assert!(set.insert(0..4).is_ok());
assert!(set.insert(4..8).is_ok());
assert!(set.insert(12..16).is_err());
set.remove_limit();
assert!(set.insert(12..16).is_ok());

pub fn interval_len(&self) -> usize

Returns the number of intervals in IntervalSet.

Examples

let mut set = IntervalSet::new();
assert_eq!(set.interval_len(), 0);
assert!(set.insert(0..4).is_ok());
assert_eq!(set.interval_len(), 1);

pub fn capacity(&self) -> usize

Returns the allocated capacity of the IntervalSet.

Examples

let mut set = IntervalSet::with_capacity(1);
assert_eq!(set.capacity(), 1);
assert!(set.insert(0..4).is_ok());
assert!(set.insert(6..10).is_ok());
assert!(set.capacity() > 1);

pub fn clear(&mut self)

Clears all elements contained in the IntervalSet.

Examples

let mut set = IntervalSet::new();
assert!(set.insert(0..4).is_ok());
set.clear();
assert!(set.is_empty());

pub fn pop_min(&mut self) -> Option<Interval<T>>

Removes the lowest Interval in the set, if any

Examples

let mut set = IntervalSet::new();
assert_eq!(set.pop_min(), None);
assert!(set.insert(0..4).is_ok());
assert_eq!(set.pop_min(), Some((0..4).into()));

impl<T: IntervalBound> IntervalSet<T>

pub fn count(&self) -> usize

Returns the number of elements in IntervalSet.

Examples

let mut set = IntervalSet::new();
assert_eq!(set.count(), 0);
assert!(set.insert(0..4).is_ok());
assert_eq!(set.count(), 4);

pub fn is_empty(&self) -> bool

Returns true if the IntervalSet has no intervals.

Examples

let mut set = IntervalSet::new();
assert!(set.is_empty());
assert!(set.insert(0..4).is_ok());
assert!(!set.is_empty());

pub fn insert<R: RangeBounds<T>>( &mut self, interval: R, ) -> Result<(), IntervalSetError>

Inserts the supplied interval into the IntervalSet

Examples

let mut set = IntervalSet::new();
assert!(set.insert(0..4).is_ok());
assert!(set.contains(&3));
assert!(!set.contains(&5));

pub fn insert_front<R: RangeBounds<T>>( &mut self, interval: R, ) -> Result<(), IntervalSetError>

Inserts the supplied interval at the beginning of the IntervalSet. This method can be used to optimize insertion when the interval is less than all of the current intervals.

Examples

let mut set = IntervalSet::new();
assert!(set.insert_front(0..4).is_ok());
assert!(set.contains(&3));
assert!(!set.contains(&5));

pub fn insert_value(&mut self, value: T) -> Result<(), IntervalSetError>

Inserts a single value into the IntervalSet

Examples

let mut set = IntervalSet::new();
assert!(set.insert_value(1).is_ok());
assert!(set.contains(&1));
assert!(!set.contains(&0));
assert!(!set.contains(&2));

pub fn union(&mut self, other: &Self) -> Result<(), IntervalSetError>

Performs a union, i.e., all the values in self or other will be present in self

Examples

let mut a = IntervalSet::new();
assert!(a.insert(0..4).is_ok());
let mut b = IntervalSet::new();
assert!(b.insert(4..8).is_ok());
a.union(&b);
assert_eq!(a.iter().collect::<Vec<_>>(), (0..8).collect::<Vec<_>>());

pub fn remove<R: RangeBounds<T>>( &mut self, interval: R, ) -> Result<(), IntervalSetError>

Removes the supplied interval from the IntervalSet

Examples

let mut set = IntervalSet::new();
assert!(set.insert(1..3).is_ok());
assert!(set.remove(0..4).is_ok());
assert!(set.is_empty());

pub fn remove_value(&mut self, value: T) -> Result<(), IntervalSetError>

Removes a single value from the IntervalSet

Examples

let mut set = IntervalSet::new();
assert!(set.insert_value(1).is_ok());
assert!(set.remove_value(1).is_ok());
assert!(!set.contains(&1));

pub fn difference(&mut self, other: &Self) -> Result<(), IntervalSetError>

Performs a difference, i.e., all the values that are in self but not in other will be present in self.

Examples

let mut set_a = IntervalSet::new();
assert!(set_a.insert(0..=10).is_ok());
let mut set_b = IntervalSet::new();
assert!(set_b.insert(4..=8).is_ok());
assert!(set_a.difference(&set_b).is_ok());
assert_eq!(set_a.iter().collect::<Vec<_>>(), vec![0, 1, 2, 3, 9, 10]);

pub fn intersection(&mut self, other: &Self) -> Result<(), IntervalSetError>

Performs an intersection, i.e., all the values in both self and other will be present in self.

Examples

let mut set_a = IntervalSet::new();
assert!(set_a.insert(0..=10).is_ok());
let mut set_b = IntervalSet::new();
assert!(set_b.insert(4..=8).is_ok());
assert!(set_a.intersection(&set_b).is_ok());
assert_eq!(set_a.iter().collect::<Vec<_>>(), vec![4, 5, 6, 7, 8]);

pub fn intersection_iter<'a>(&'a self, other: &'a Self) -> Intersection<'a, T>

Returns an iterator of Intervals over the intersection, i.e., all the values in both self and other will be returned.

Examples

let mut set_a = IntervalSet::new();
assert!(set_a.insert(0..=10).is_ok());
let mut set_b = IntervalSet::new();
assert!(set_b.insert(4..=8).is_ok());
let intersection = set_a.intersection_iter(&set_b).flatten();
assert_eq!(intersection.collect::<Vec<_>>(), vec![4, 5, 6, 7, 8]);

pub fn iter(&self) -> Iter<'_, T>

Returns an iterator over all of the values contained in the given IntervalSet.

Examples

let mut set = IntervalSet::new();
assert!(set.insert(0..5).is_ok());
assert!(set.insert(10..15).is_ok());
let items: Vec<_> = set.iter().collect();
assert_eq!(vec![0, 1, 2, 3, 4, 10, 11, 12, 13, 14], items);

pub fn min_value(&self) -> Option<T>

Returns the smallest value in the given IntervalSet. If no items are present in the set, None is returned.

Examples

let mut set = IntervalSet::new();
assert_eq!(set.min_value(), None);
assert!(set.insert(0..5).is_ok());
assert_eq!(set.min_value(), Some(0));

pub fn max_value(&self) -> Option<T>

Returns the largest value in the given IntervalSet. If no items are present in the set, None is returned.

Examples

let mut set = IntervalSet::new();
assert_eq!(set.max_value(), None);
assert!(set.insert(0..5).is_ok());
assert_eq!(set.max_value(), Some(4));

pub fn contains(&self, value: &T) -> bool

Returns true if the set contains a value

Examples

let mut set = IntervalSet::new();
assert_eq!(set.contains(&1), false);
assert!(set.insert(0..5).is_ok());
assert_eq!(set.contains(&1), true);

impl<T: Copy> IntervalSet<T>

pub fn intervals(&self) -> IntervalIter<'_, T>

Returns an iterator of Intervals contained in the IntervalSet

Examples

let mut set = IntervalSet::new();
set.insert(0..=10);
assert_eq!(set.intervals().collect::<Vec<_>>(), vec![0..=10]);

pub fn ranges(&self) -> RangeIter<'_, T>

Returns an iterator of Ranges contained in the IntervalSet

Examples

let mut set = IntervalSet::new();
set.insert(0..=10);
assert_eq!(set.ranges().collect::<Vec<_>>(), vec![0..11]);

pub fn inclusive_ranges(&self) -> RangeInclusiveIter<'_, T>

Returns an iterator of RangeInclusives contained in the IntervalSet

Examples

let mut set = IntervalSet::new();
set.insert(0..=10);
assert_eq!(set.inclusive_ranges().collect::<Vec<_>>(), vec![0..=10]);

Trait Implementations

impl<T: Clone> Clone for IntervalSet<T>

fn clone(&self) -> IntervalSet<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Copy + Debug> Debug for IntervalSet<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Default for IntervalSet<T>

fn default() -> Self

Returns the “default value” for a type.

impl<'a, T: 'a + IntervalBound> Extend<&'a Interval<T>> for IntervalSet<T>

fn extend<I: IntoIterator<Item = &'a Interval<T>>>(&mut self, intervals: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<'a, T: 'a + IntervalBound> Extend<&'a Range<T>> for IntervalSet<T>

fn extend<I: IntoIterator<Item = &'a Range<T>>>(&mut self, intervals: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<'a, T: 'a + IntervalBound> Extend<&'a RangeInclusive<T>> for IntervalSet<T>

fn extend<I: IntoIterator<Item = &'a RangeInclusive<T>>>( &mut self, intervals: I, )

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T: IntervalBound> Extend<Interval<T>> for IntervalSet<T>

fn extend<I: IntoIterator<Item = Interval<T>>>(&mut self, intervals: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T: IntervalBound> Extend<Range<T>> for IntervalSet<T>

fn extend<I: IntoIterator<Item = Range<T>>>(&mut self, intervals: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T: IntervalBound> Extend<RangeInclusive<T>> for IntervalSet<T>

fn extend<I: IntoIterator<Item = RangeInclusive<T>>>(&mut self, intervals: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T: IntervalBound> From<Interval<T>> for IntervalSet<T>

fn from(interval: Interval<T>) -> Self

Converts to this type from the input type.

impl<T: IntervalBound> From<Range<T>> for IntervalSet<T>

fn from(interval: Range<T>) -> Self

Converts to this type from the input type.

impl<T: IntervalBound> From<RangeInclusive<T>> for IntervalSet<T>

fn from(interval: RangeInclusive<T>) -> Self

Converts to this type from the input type.

impl<'a, T: 'a + IntervalBound> FromIterator<&'a Interval<T>> for IntervalSet<T>

fn from_iter<I: IntoIterator<Item = &'a Interval<T>>>(intervals: I) -> Self

Creates a value from an iterator.

impl<'a, T: 'a + IntervalBound> FromIterator<&'a Range<T>> for IntervalSet<T>

fn from_iter<I: IntoIterator<Item = &'a Range<T>>>(intervals: I) -> Self

Creates a value from an iterator.

impl<'a, T: 'a + IntervalBound> FromIterator<&'a RangeInclusive<T>> for IntervalSet<T>

fn from_iter<I: IntoIterator<Item = &'a RangeInclusive<T>>>( intervals: I, ) -> Self

Creates a value from an iterator.

impl<'a, T: 'a + IntervalBound> FromIterator<&'a T> for IntervalSet<T>

fn from_iter<I: IntoIterator<Item = &'a T>>(values: I) -> Self

Creates a value from an iterator.

impl<T: IntervalBound> FromIterator<Interval<T>> for IntervalSet<T>

fn from_iter<I: IntoIterator<Item = Interval<T>>>(intervals: I) -> Self

Creates a value from an iterator.

impl<T: IntervalBound> FromIterator<Range<T>> for IntervalSet<T>

fn from_iter<I: IntoIterator<Item = Range<T>>>(intervals: I) -> Self

Creates a value from an iterator.

impl<T: IntervalBound> FromIterator<RangeInclusive<T>> for IntervalSet<T>

fn from_iter<I: IntoIterator<Item = RangeInclusive<T>>>(intervals: I) -> Self

Creates a value from an iterator.

impl<T: IntervalBound> FromIterator<T> for IntervalSet<T>

fn from_iter<I: IntoIterator<Item = T>>(values: I) -> Self

Creates a value from an iterator.

impl<T: Ord> Ord for IntervalSet<T>

fn cmp(&self, other: &IntervalSet<T>) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<T: PartialEq> PartialEq for IntervalSet<T>

fn eq(&self, other: &IntervalSet<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: PartialOrd> PartialOrd for IntervalSet<T>

fn partial_cmp(&self, other: &IntervalSet<T>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<T: Eq> Eq for IntervalSet<T>

impl<T> StructuralPartialEq for IntervalSet<T>