Enum OrderedSet 

pub enum OrderedSet {
    Interval {
        start: u32,
        end: u32,
    },
    Sorted(Arc<[u32]>),
}

Ordered set of indices — either a contiguous interval or sorted array.

The Interval variant provides O(1) membership tests for contiguous ranges. The Sorted variant provides O(log n) membership tests for arbitrary selections.

Variants

Interval

Contiguous range [start, end) — O(1) membership test

Fields

start: u32

end: u32

Sorted(Arc<[u32]>)

Sorted unique indices — O(log n) membership test

Implementations

impl OrderedSet

pub fn interval(start: u32, end: u32) -> Self

Create a contiguous interval [start, end).

Panics

Panics if start > end.

pub fn from_sorted(indices: Vec<u32>) -> Self

Create a Sorted set from a Vec<u32>.

The input must already be sorted and contain no duplicates. This function panics if either condition is violated, keeping the invariant that Sorted always holds valid data.

If you need to accept arbitrary input, sort and dedup before calling:

let mut v = vec![3u32, 1, 2, 1];
v.sort_unstable();
v.dedup();
let set = OrderedSet::from_sorted(v);

pub fn len(&self) -> usize

Returns the number of elements in the set.

pub fn is_empty(&self) -> bool

Returns true if the set contains no elements.

pub fn contains(&self, idx: u32) -> bool

Returns true if idx is a member of this set.

pub fn iter(&self) -> impl Iterator<Item = u32> + '_

Iterate over the elements of this set in ascending order.

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

Compute the union of this set and other.

Uses a merge-style algorithm on two sorted iterators — O(n + m). Returns an OrderedSet::Sorted.

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

Compute the intersection of this set and other.

Uses a merge-style algorithm — O(n + m). Returns an OrderedSet::Sorted.

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

Compute the set difference self \ other (elements in self but not other).

Uses a merge-style algorithm — O(n + m). Returns an OrderedSet::Sorted.

Trait Implementations

impl Clone for OrderedSet

fn clone(&self) -> OrderedSet

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for OrderedSet

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

Formats the value using the given formatter.

impl PartialEq for OrderedSet

fn eq(&self, other: &OrderedSet) -> 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 StructuralPartialEq for OrderedSet