Struct Set

pub struct Set<T, C = Natural<T>>
where
    C: Compare<T>,
{ /* private fields */ }

An ordered set based on a binary search tree.

The behavior of this set is undefined if an item’s ordering relative to any other item changes while the item is in the set. This is normally only possible through Cell, RefCell, or unsafe code.

Implementations

impl<T> Set<T>

where T: Ord,

pub fn new() -> Self

Creates an empty set ordered according to the natural order of its items.

Examples

let mut set = tree::Set::new();

set.insert(2);
set.insert(1);
set.insert(3);

let mut it = set.iter();
assert_eq!(it.next(), Some(&1));
assert_eq!(it.next(), Some(&2));
assert_eq!(it.next(), Some(&3));
assert_eq!(it.next(), None);

impl<T, C> Set<T, C>

where C: Compare<T>,

pub fn with_cmp(cmp: C) -> Self

Creates an empty set ordered according to the given comparator.

Examples

use compare::{Compare, natural};

let mut set = tree::Set::with_cmp(natural().rev());

set.insert(2);
set.insert(1);
set.insert(3);

let mut it = set.iter();
assert_eq!(it.next(), Some(&3));
assert_eq!(it.next(), Some(&2));
assert_eq!(it.next(), Some(&1));
assert_eq!(it.next(), None);

pub fn is_empty(&self) -> bool

Checks if the set is empty.

Examples

let mut set = tree::Set::new();
assert!(set.is_empty());

set.insert(2);
assert!(!set.is_empty());

pub fn len(&self) -> usize

Returns the number of items in the set.

Examples

let mut set = tree::Set::new();
assert_eq!(set.len(), 0);

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

pub fn cmp(&self) -> &C

Returns a reference to the set’s comparator.

Examples

use compare::{Compare, natural};

let set = tree::Set::new();
assert!(set.cmp().compares_lt(&1, &2));

let set: tree::Set<_, _> = tree::Set::with_cmp(natural().rev());
assert!(set.cmp().compares_gt(&1, &2));

pub fn clear(&mut self)

Removes all items from the set.

Examples

let mut set = tree::Set::new();

set.insert(2);
set.insert(1);
set.insert(3);

assert_eq!(set.len(), 3);
assert_eq!(set.iter().next(), Some(&1));

set.clear();

assert_eq!(set.len(), 0);
assert_eq!(set.iter().next(), None);

pub fn insert(&mut self, item: T) -> bool

Inserts an item into the set, returning true if the set did not already contain the item.

Examples

let mut set = tree::Set::new();
assert!(!set.contains(&1));
assert!(set.insert(1));
assert!(set.contains(&1));
assert!(!set.insert(1));

pub fn remove<Q: ?Sized>(&mut self, item: &Q) -> bool

where C: Compare<Q, T>,

Removes the given item from the set, returning true if the set contained the item.

Examples

let mut set = tree::Set::new();

set.insert(2);
set.insert(1);
set.insert(3);

assert_eq!(set.len(), 3);
assert!(set.contains(&1));
assert!(set.remove(&1));

assert_eq!(set.len(), 2);
assert!(!set.contains(&1));
assert!(!set.remove(&1));

pub fn entry(&mut self, item: T) -> Entry<'_, T>

Returns the set’s entry corresponding to the given item.

Examples

use tree::set::Entry;

let mut set = tree::Set::new();

set.insert(2);
set.insert(1);
set.insert(3);

match set.entry(1) {
    Entry::Occupied(e) => {
        assert_eq!(*e.get(), 1);
        assert_eq!(e.remove(), 1);
    }
    Entry::Vacant(_) => panic!("expected an occupied entry"),
}

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

match set.entry(4) {
    Entry::Occupied(_) => panic!("expected a vacant entry"),
    Entry::Vacant(e) => e.insert(),
}

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

pub fn contains<Q: ?Sized>(&self, item: &Q) -> bool

where C: Compare<Q, T>,

Checks if the set contains the given item.

Examples

let mut set = tree::Set::new();
assert!(!set.contains(&1));
set.insert(1);
assert!(set.contains(&1));

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

Returns a reference to the set’s maximum item, or None if the set is empty.

Examples

let mut set = tree::Set::new();
assert_eq!(set.max(), None);

set.insert(2);
set.insert(1);
set.insert(3);

assert_eq!(set.max(), Some(&3));

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

Removes and returns the set’s maximum item, or None if the set is empty.

Examples

let mut set = tree::Set::new();
assert_eq!(set.remove_max(), None);

set.insert(2);
set.insert(1);
set.insert(3);

assert_eq!(set.remove_max(), Some(3));

pub fn max_entry(&mut self) -> Option<OccupiedEntry<'_, T>>

Returns the entry corresponding to the set’s maximum item.

Examples

let mut set = tree::Set::new();
assert!(set.max_entry().is_none());

set.insert(2);
set.insert(1);
set.insert(3);

{
    let mut e = set.max_entry().unwrap();
    assert_eq!(*e.get(), 3);
    assert_eq!(e.remove(), 3);
}

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

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

Returns a reference to the set’s minimum item, or None if the set is empty.

Examples

let mut set = tree::Set::new();
assert_eq!(set.min(), None);

set.insert(2);
set.insert(1);
set.insert(3);

assert_eq!(set.min(), Some(&1));

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

Removes and returns the set’s minimum item, or None if the set is empty.

Examples

let mut set = tree::Set::new();
assert_eq!(set.remove_min(), None);

set.insert(2);
set.insert(1);
set.insert(3);

assert_eq!(set.remove_min(), Some(1));

pub fn min_entry(&mut self) -> Option<OccupiedEntry<'_, T>>

Returns the entry corresponding to the set’s minimum item.

Examples

let mut set = tree::Set::new();
assert!(set.min_entry().is_none());

set.insert(2);
set.insert(1);
set.insert(3);

{
    let mut e = set.min_entry().unwrap();
    assert_eq!(*e.get(), 1);
    assert_eq!(e.remove(), 1);
}

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

pub fn pred<Q: ?Sized>(&self, item: &Q, inclusive: bool) -> Option<&T>

where C: Compare<Q, T>,

Returns a reference to the predecessor of the given item, or None if no such item is present in the set.

If inclusive is false, this method finds the greatest item that is strictly less than the given item. If inclusive is true, this method finds the greatest item that is less than or equal to the given item.

The given item need not itself be present in the set.

Examples

let mut set = tree::Set::new();

set.insert(2);
set.insert(1);
set.insert(3);

assert_eq!(set.pred(&0, false), None);
assert_eq!(set.pred(&1, false), None);
assert_eq!(set.pred(&2, false), Some(&1));
assert_eq!(set.pred(&3, false), Some(&2));
assert_eq!(set.pred(&4, false), Some(&3));

assert_eq!(set.pred(&0, true), None);
assert_eq!(set.pred(&1, true), Some(&1));
assert_eq!(set.pred(&2, true), Some(&2));
assert_eq!(set.pred(&3, true), Some(&3));
assert_eq!(set.pred(&4, true), Some(&3));

pub fn remove_pred<Q: ?Sized>(&mut self, item: &Q, inclusive: bool) -> Option<T>

where C: Compare<Q, T>,

Removes the predecessor of the given item from the set and returns it, or None if no such item present in the set.

If inclusive is false, this method removes the greatest item that is strictly less than the given item. If inclusive is true, this method removes the greatest item that is less than or equal to the given item.

The given item need not itself be present in the set.

Examples

let mut set = tree::Set::new();

set.insert(2);
set.insert(1);
set.insert(3);

assert_eq!(set.remove_pred(&1, false), None);
assert!(set.contains(&1));

assert_eq!(set.remove_pred(&2, false), Some(1));
assert!(!set.contains(&1));

assert_eq!(set.remove_pred(&2, true), Some(2));
assert!(!set.contains(&2));

pub fn pred_entry<Q: ?Sized>( &mut self, item: &Q, inclusive: bool, ) -> Option<OccupiedEntry<'_, T>>

where C: Compare<Q, T>,

Returns the entry corresponding to the predecessor of the given item.

If inclusive is false, this method returns the entry corresponding to the greatest item that is strictly less than the given item. If inclusive is true, this method returns the entry corresponding to the greatest item that is less than or equal to the given item.

The given item need not itself be present in the set.

Examples

let mut set = tree::Set::new();

set.insert(2);
set.insert(1);
set.insert(3);

assert!(set.pred_entry(&1, false).is_none());

{
    let mut e = set.pred_entry(&4, true).unwrap();
    assert_eq!(*e.get(), 3);
}

{
    let e = set.pred_entry(&3, false).unwrap();
    assert_eq!(e.remove(), 2);
}

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

pub fn succ<Q: ?Sized>(&self, item: &Q, inclusive: bool) -> Option<&T>

where C: Compare<Q, T>,

Returns a reference to the successor of the given item, or None if no such item is present in the set.

If inclusive is false, this method finds the smallest item that is strictly greater than the given item. If inclusive is true, this method finds the smallest item that is greater than or equal to the given item.

The given item need not itself be present in the set.

Examples

let mut set = tree::Set::new();

set.insert(2);
set.insert(1);
set.insert(3);

assert_eq!(set.succ(&0, false), Some(&1));
assert_eq!(set.succ(&1, false), Some(&2));
assert_eq!(set.succ(&2, false), Some(&3));
assert_eq!(set.succ(&3, false), None);
assert_eq!(set.succ(&4, false), None);

assert_eq!(set.succ(&0, true), Some(&1));
assert_eq!(set.succ(&1, true), Some(&1));
assert_eq!(set.succ(&2, true), Some(&2));
assert_eq!(set.succ(&3, true), Some(&3));
assert_eq!(set.succ(&4, true), None);

pub fn remove_succ<Q: ?Sized>(&mut self, item: &Q, inclusive: bool) -> Option<T>

where C: Compare<Q, T>,

Removes the successor of the given item from the set and returns it, or None if no such item present in the set.

If inclusive is false, this method removes the smallest item that is strictly greater than the given item. If inclusive is true, this method removes the smallest item that is greater than or equal to the given item.

The given item need not itself be present in the set.

Examples

let mut set = tree::Set::new();

set.insert(2);
set.insert(1);
set.insert(3);

assert_eq!(set.remove_succ(&3, false), None);
assert!(set.contains(&3));

assert_eq!(set.remove_succ(&2, false), Some(3));
assert!(!set.contains(&3));

assert_eq!(set.remove_succ(&2, true), Some(2));
assert!(!set.contains(&2));

pub fn succ_entry<Q: ?Sized>( &mut self, item: &Q, inclusive: bool, ) -> Option<OccupiedEntry<'_, T>>

where C: Compare<Q, T>,

Returns the entry corresponding to the successor of the given item.

If inclusive is false, this method returns the entry corresponding to the smallest item that is strictly greater than the given item. If inclusive is true, this method returns the entry corresponding to the smallest item that is greater than or equal to the given item.

The given item need not itself be present in the set.

Examples

let mut set = tree::Set::new();

set.insert(2);
set.insert(1);
set.insert(3);

assert!(set.succ_entry(&3, false).is_none());

{
    let mut e = set.succ_entry(&0, true).unwrap();
    assert_eq!(*e.get(), 1);
}

{
    let e = set.succ_entry(&1, false).unwrap();
    assert_eq!(e.remove(), 2);
}

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

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

Returns an iterator over the set.

The iterator yields the items in ascending order according to the set’s comparator.

Examples

let mut set = tree::Set::new();

set.insert(2);
set.insert(1);
set.insert(3);

let mut it = set.iter();
assert_eq!(it.next(), Some(&1));
assert_eq!(it.next(), Some(&2));
assert_eq!(it.next(), Some(&3));
assert_eq!(it.next(), None);

Trait Implementations

impl<T, C> Arbitrary for Set<T, C>

where T: Arbitrary, C: 'static + Clone + Compare<T> + Default + Send,

fn arbitrary<G: Gen>(gen: &mut G) -> Self

fn shrink(&self) -> Box<dyn Iterator<Item = Self>>

impl<T: Clone, C> Clone for Set<T, C>

where C: Compare<T> + Clone,

fn clone(&self) -> Set<T, C>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T, C> Debug for Set<T, C>

where T: Debug, C: Compare<T>,

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

Formats the value using the given formatter.

impl<T, C> Default for Set<T, C>

where C: Compare<T> + Default,

fn default() -> Self

Returns the “default value” for a type.

impl<T, C> Extend<T> for Set<T, C>

where C: Compare<T>,

fn extend<I: IntoIterator<Item = T>>(&mut self, it: 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, C> FromIterator<T> for Set<T, C>

where C: Compare<T> + Default,

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

Creates a value from an iterator.

impl<T, C> Hash for Set<T, C>

where T: Hash, C: Compare<T>,

fn hash<H: Hasher>(&self, h: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<'a, T, C> IntoIterator for &'a Set<T, C>

where C: Compare<T>,

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a, T>

Creates an iterator from a value.

impl<T, C> IntoIterator for Set<T, C>

where C: Compare<T>,

fn into_iter(self) -> IntoIter<T>

Returns an iterator that consumes the set.

The iterator yields the items in ascending order according to the set’s comparator.

Examples

let mut set = tree::Set::new();

set.insert(2);
set.insert(1);
set.insert(3);

let mut it = set.into_iter();
assert_eq!(it.next(), Some(1));
assert_eq!(it.next(), Some(2));
assert_eq!(it.next(), Some(3));
assert_eq!(it.next(), None);

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

impl<T, C> Ord for Set<T, C>

where C: Compare<T>,

fn cmp(&self, other: &Self) -> 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, C> PartialEq for Set<T, C>

where C: Compare<T>,

fn eq(&self, other: &Self) -> 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, C> PartialOrd for Set<T, C>

where C: Compare<T>,

fn partial_cmp(&self, other: &Self) -> 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, C> Eq for Set<T, C>

where C: Compare<T>,