Struct tree::set::Set [−] [src]

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

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.

Methods

`impl<T> Set<T> where T: Ord,`
[src]

`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>,`
[src]

`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);

`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());

`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);

`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));

`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);

`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));

`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));

`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));

`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));

`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));

`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));

`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));

`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));

`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));

`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));

`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.