Struct segmap::set::SegmentSet

pub struct SegmentSet<T> { /* fields omitted */ }

SegmentSet

A set based on a SegmentMap. Like SegmentMap, adjacent ranges will be merged into a single range.

See SegmentMap’s documentation for more details on implementation. The internal representation of this struct is is a SegmentMap<T, ()>

Examples

let mut set = SegmentSet::new();

// Add some ranges
set.insert(0..5);
set.insert(5..10); // Note, this will be merged with 0..5!
set.insert(20..25);

// Check if a point is covered
assert!(set.contains(&7));
assert!(!set.contains(&12));

// Remove a range (or parts of some ranges)
assert!(set.contains(&5));
assert!(set.contains(&24));
set.remove(3..6);
set.remove(22..);
assert!(!set.contains(&5));
assert!(!set.contains(&24));

// Check which ranges are covered
assert!(set.into_iter().eq(vec![
    Segment::from(0..3),
    Segment::from(6..10),
    Segment::from(20..22),
]));

Implementations

impl<T> SegmentSet<T>

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

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn into_vec(self) -> Vec<Segment<T>>

Converts the set into a Vec by chaining [into_iter] and [collect]

impl<T> SegmentSet<T>

pub fn iter_difference<'a>(&'a self, other: &'a Self) -> Difference<'a, T> where
    T: Ord, 

pub fn difference<'a>(&'a self, other: &'a Self) -> SegmentSet<&'a T> where
    T: Ord, 

Return a set representing the difference of two sets

I.e. All elements in self that are not in other

If you need an iterator over the different items, use [SegmentSet::difference_iter], which is called here internally. However, this may be slightly faster if you need a set.

impl<T> SegmentSet<T>

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

pub fn intersection<'a>(&'a self, other: &'a Self) -> SegmentSet<&'a T> where
    T: Ord, 

impl<T> SegmentSet<T>

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

pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SegmentSet<&'a T> where
    T: Ord, 

impl<T> SegmentSet<T>

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

pub fn union<'a>(&'a self, other: &'a Self) -> SegmentSet<&'a T> where
    T: Ord, 

impl<T: Ord> SegmentSet<T>

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

Check whether self and other are disjoint sets

That is, the intersection between self and other is empty

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

Check whether self is a subset of other

That is, all elements of self exist in other, or (as implemented) self.difference(other) is empty

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

pub fn subset<R: RangeBounds<T>>(&self, range: R) -> SegmentSet<T> where
    T: Clone + Ord, 

pub fn complement(&self) -> SegmentSet<&T> where
    T: Ord, 

impl<T> SegmentSet<T>

pub fn new() -> Self where
    T: Ord, 

Makes a new empty SegmentSet.

pub fn full() -> Self where
    T: Ord, 

Make a new SegmentSet with a single range present, representing all possible values.

// Thus, this
let full = SegmentSet::<u32>::full();

// Is equivalent to
let mut manual = SegmentSet::new();
manual.insert(..);

assert_eq!(full, manual);

pub fn clear(&mut self)

Clears the set, removing all elements.

Examples

let mut set = SegmentSet::new();
set.insert(0..1);
set.clear();
assert!(set.is_empty());

pub fn contains(&self, value: &T) -> bool where
    T: Clone + Ord, 

Returns true if any range in the set covers the specified value.

Examples

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

pub fn get_range_for(&self, value: &T) -> Option<&Segment<T>> where
    T: Clone + Ord, 

Returns a reference to the range covering the given value, if any.

Examples

let mut set = SegmentSet::new();
set.insert(0..5);

assert_eq!(set.get_range_for(&3), Some(&Segment::from(0..5)));
assert!(set.get_range_for(&6).is_none());

pub fn insert<R>(&mut self, range: R) where
    R: RangeBounds<T>,
    T: Clone + Ord, 

Insert a range into the set.

If the inserted range either overlaps or is immediately adjacent any existing range, then the ranges will be coalesced into a single contiguous range.

Examples

let mut set = SegmentSet::new();
set.insert(0..5);
assert!(!set.is_empty())

See Also

• SegmentMap::insert and SegmentMap::set for the internal map’s insertion semantics. Because values are always () and returning overwritten values is not necessary, this method uses set.

pub fn remove<R>(&mut self, range: R) -> bool where
    R: RangeBounds<T>,
    T: Clone + Ord, 

Removes a range from the set returning if all or any of it was present.

Examples

let mut set = SegmentSet::new();
set.insert(0..5);
assert!(set.remove(0..2));

See Also

• SegmentMap::remove and SegmentMap::clear_range for the internal map’s removal semantics. However, this method will not allocate anything to return.
• SegmentSet::take if you want the removed elements

pub fn take<R>(&mut self, range: R) -> Self where
    R: RangeBounds<T>,
    T: Clone + Ord, 

Removes a range from the set, returning a set containing the removed elements

Examples

let mut set = SegmentSet::new();
set.insert(0..5);
let removed = set.take(0..2);

See Also

• SegmentMap::remove and SegmentMap::clear_range for the internal map’s removal semantics. However, this method will not allocate anything to return.
• SegmentSet::remove if you don’t want the removed elements

pub fn retain<F>(&mut self, f: F) where
    T: Ord,
    F: FnMut(&Segment<T>) -> bool, 

Retains only the elements specified by the predicate.

In other words, remove all ranges f(v) returns false.

Examples

let mut set = SegmentSet::new();
set.insert(0..4);
set.insert(5..9);
set.insert(10..14);
set.insert(15..19);
set.insert(20..24);

// Keep only the ranges with even numbered starts
set.retain(|r| r.start_value().unwrap() % 2 == 0);

assert!(set.contains(&0));
assert!(set.contains(&10));
assert!(set.contains(&12));
assert!(set.contains(&20));
assert!(set.contains(&23));

assert!(!set.contains(&15));

See Also

• SegmentMap::retain, which is called internally

pub fn append(&mut self, other: &mut Self) where
    T: Clone + Ord, 

Moves all elements from other into Self, leaving other empty.

Examples

let mut a = SegmentSet::new();
a.insert(0..1);
a.insert(1..2);
a.insert(2..3);

let mut b = SegmentSet::new();
b.insert(2..3);
b.insert(3..4);
b.insert(4..5);

a.append(&mut b);

// Ranges in a should all be coalesced to 0..5
assert!(a.into_iter().eq(vec![
    Segment::from(0..5)
]));
assert!(b.is_empty());

pub fn split_off(&mut self, at: Bound<T>) -> Self where
    T: Clone + Ord, 

Split the set into two at the given bound. Returns everything including and after that bound.

Examples

Basic Usage

let mut a = SegmentSet::new();
a.insert(0..1);
a.insert(2..3);
a.insert(4..5);
a.insert(6..7);

let b = a.split_off(Bound::Included(4));

assert!(a.into_iter().eq(vec![
    Segment::from(0..1),
    Segment::from(2..3),
]));
assert!(b.into_iter().eq(vec![
    Segment::from(4..5),
    Segment::from(6..7),
]));

Mixed Bounds

let mut a = SegmentSet::new();
a.insert(0..7);

let c = a.split_off(Bound::Excluded(4));
let b = a.split_off(Bound::Included(2));

assert!(a.into_iter().eq(vec![
    Segment::from(0..2)
]));
assert!(b.into_iter().eq(vec![
    Segment::from(2..=4)
]));
assert!(c.into_iter().eq(vec![
    Segment::new(Bound::Excluded(4), Bound::Excluded(7))
]));

impl<T: Clone + Ord> SegmentSet<&T>

pub fn cloned(&self) -> SegmentSet<T>

Trait Implementations

impl<T: Ord + Clone> Add<&'_ SegmentSet<T>> for &SegmentSet<T>

Set Union

type Output = SegmentSet<T>

The resulting type after applying the + operator.

fn add(self, rhs: &SegmentSet<T>) -> SegmentSet<T>

Performs the + operation.

impl<'a, T: Ord + Clone> BitAnd<&'a SegmentSet<T>> for &'a SegmentSet<T>

Set Intersection A & B

fn bitand(self, rhs: &'a SegmentSet<T>) -> SegmentSet<&'a T>

Returns the intersection of self and rhs as a new BTreeSet<T>.

Examples

use std::collections::BTreeSet;

let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
let b: BTreeSet<_> = vec![2, 3, 4].into_iter().collect();

let result = &a & &b;
let result_vec: Vec<_> = result.into_iter().collect();
assert_eq!(result_vec, [2, 3]);

type Output = SegmentSet<&'a T>

The resulting type after applying the & operator.

impl<'a, T: Ord + Clone> BitAnd<SegmentSet<T>> for SegmentSet<T>

type Output = SegmentSet<T>

The resulting type after applying the & operator.

fn bitand(self, rhs: SegmentSet<T>) -> SegmentSet<T>

Performs the & operation.

impl<T: Ord + Clone> BitOr<&'_ SegmentSet<T>> for &SegmentSet<T>

Set Union

fn bitor(self, rhs: &SegmentSet<T>) -> SegmentSet<T>

Returns the union of self and rhs as a new BTreeSet<T>.

Examples

use std::collections::BTreeSet;

let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
let b: BTreeSet<_> = vec![3, 4, 5].into_iter().collect();

let result = &a | &b;
let result_vec: Vec<_> = result.into_iter().collect();
assert_eq!(result_vec, [1, 2, 3, 4, 5]);

type Output = SegmentSet<T>

The resulting type after applying the | operator.

impl<'a, T: Ord + Clone> BitXor<&'a SegmentSet<T>> for &'a SegmentSet<T>

Set Symmetric Difference

fn bitxor(self, rhs: &'a SegmentSet<T>) -> SegmentSet<&'a T>

Returns the symmetric difference of self and rhs as a new BTreeSet<T>.

Examples

use std::collections::BTreeSet;

let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect();
let b: BTreeSet<_> = vec![2, 3, 4].into_iter().collect();

let result = &a ^ &b;
let result_vec: Vec<_> = result.into_iter().collect();
assert_eq!(result_vec, [1, 4]);

type Output = SegmentSet<&'a T>

The resulting type after applying the ^ operator.

impl<T: Clone> Clone for SegmentSet<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for SegmentSet<T> where
    T: Ord + Clone, 

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

Formats the value using the given formatter.

impl<T> Default for SegmentSet<T> where
    T: Clone + Ord, 

fn default() -> Self

Returns the “default value” for a type.

impl<'a, T: 'a + Ord + Copy> Extend<&'a Segment<T>> for SegmentSet<T>

fn extend<I: IntoIterator<Item = &'a Segment<T>>>(&mut self, iter: 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: Clone + Ord> Extend<Segment<T>> for SegmentSet<T>

fn extend<Iter: IntoIterator<Item = Segment<T>>>(&mut self, iter: Iter)

Insert all the items from iter into self.

NOTE: Inserted items will overwrite existing ranges in self if they overlap. If you don’t want to overwrite existing ranges, use [extend_into_gaps].

Clone is required for insertion, since we can’t guarantee elements in iter are ordered or non-overlapping, so ranges may need to be split.

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<K, V> From<SegmentMap<K, V>> for SegmentSet<K> where
    K: Ord, 

fn from(map: SegmentMap<K, V>) -> Self

Performs the conversion.

impl<Item: RangeBounds<T>, T: Clone + Ord> FromIterator<Item> for SegmentSet<T>

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

Creates a value from an iterator.

impl<T> IntoIterator for SegmentSet<T>

type Item = Segment<T>

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T: Ord + Clone> Not for &'a SegmentSet<T>

Set Complement

type Output = SegmentSet<&'a T>

The resulting type after applying the ! operator.

fn not(self) -> Self::Output

Performs the unary ! operation.

impl<T: Ord + Clone> Not for SegmentSet<T>

type Output = SegmentSet<T>

The resulting type after applying the ! operator.

fn not(self) -> Self::Output

Performs the unary ! operation.

impl<T: PartialEq> PartialEq<SegmentSet<T>> for SegmentSet<T>

fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

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

This method tests for !=.

impl<'a, T: Ord + Clone> Sub<&'a SegmentSet<T>> for &'a SegmentSet<T>

Set Difference

type Output = SegmentSet<&'a T>

The resulting type after applying the - operator.

fn sub(self, rhs: &'a SegmentSet<T>) -> SegmentSet<&'a T>

Performs the - operation.

impl<T: Ord + Clone> SubAssign<&'_ SegmentSet<T>> for SegmentSet<T>

Set Removal // TODO: self.into_difference() may be quicker for these?

fn sub_assign(&mut self, rhs: &SegmentSet<T>)

Performs the -= operation.

impl<T: Ord + Clone> SubAssign<SegmentSet<T>> for SegmentSet<T>

Set Removal

fn sub_assign(&mut self, rhs: SegmentSet<T>)

Performs the -= operation.