Struct immutable_map::set::TreeSet

pub struct TreeSet<V> { /* fields omitted */ }

An immutable set based on weight-balanced binary tree. See https://yoichihirai.com/bst.pdf for the balancing algorithm.

Examples

use immutable_map::TreeSet;

let set_0 = TreeSet::new();

// `insert` returns new copies with the given key and value inserted, and does not change
// the original map
let set_1 = set_0.insert(3);
let set_2 = set_1.insert(4);

assert!(!set_1.contains(&4));
assert!(set_2.contains(&4));

Methods

impl<V> TreeSet<V>

fn new() -> TreeSet<V>

Makes a new empty TreeSet

Examples

use immutable_map::TreeSet;

let set = TreeSet::new();
let new_set = set.insert(1);

fn len(&self) -> usize

Returns the number of elements in the set.

Examples

use immutable_map::TreeSet;

let set = TreeSet::new().insert(1).insert(2);
assert_eq!(2, set.len());

fn is_empty(&self) -> bool

Returns true if the set contains no elements.

Examples

use immutable_map::TreeSet;

let empty_set = TreeSet::new();
let new_set = empty_set.insert(1);

assert!(empty_set.is_empty());
assert!(!new_set.is_empty());

fn iter<'r>(&'r self) -> TreeSetIter<'r, V>

Gets an iterator over the entries of the set, in sorted order.

Examples

use immutable_map::TreeSet;

let set = TreeSet::new().insert(2).insert(3).insert(1);

for element in set.iter() {
    println!("{}", element);
}

let first_value = set.iter().next().unwrap();
assert_eq!(1, *first_value);

fn rev_iter<'r>(&'r self) -> TreeSetRevIter<'r, V>

Gets an iterator over the entries of the set, in decreasing order.

Examples

use immutable_map::TreeSet;

let set = TreeSet::new().insert(2).insert(3).insert(1);

for element in set.rev_iter() {
    println!("{}", element);
}

let first_value = set.rev_iter().next().unwrap();
assert_eq!(3, *first_value);

impl<V: Ord> TreeSet<V>

fn get<Q: Ord + ?Sized>(&self, key: &Q) -> Option<&V> where V: Borrow<Q>

Returns a reference to the value in the set, if any, that is equal to the given value.

The value may be any borrowed form of the set's value type, but the ordering on the borrowed form must match the ordering on the value type.

fn contains<Q: Ord + ?Sized>(&self, key: &Q) -> bool where V: Borrow<Q>

Returns true if the value is in the set, if any, that is equal to the given value.

The value may be any borrowed form of the set's value type, but the ordering on the borrowed form must match the ordering on the value type.

Examples

use immutable_map::TreeSet;

let set: TreeSet<String> = ["One".to_string(), "Two".to_string(), "Three".to_string()].iter().cloned().collect();

assert_eq!(true, set.contains("Two"));
assert_eq!(false, set.contains("Four"));

fn range<'r, Q: Ord>(&'r self,
                     min: Bound<&Q>,
                     max: Bound<&Q>)
                     -> TreeSetRange<'r, V> where V: Borrow<Q>

Constructs a double-ended iterator over a sub-range of elements in the set, starting at min, and ending at max. If min is Unbounded, then it will be treated as "negative infinity", and if max is Unbounded, then it will be treated as "positive infinity". Thus range(Unbounded, Unbounded) will yield the whole collection.

Examples

use immutable_map::TreeSet;
use immutable_map::Bound::*;

let set = TreeSet::new().insert(8).insert(3).insert(5);

for elem in set.range(Included(&4), Included(&8)) {
    println!("{}", elem);
}

let values: Vec<_> = set.range(Included(&4), Included(&8)).cloned().collect();

assert_eq!(values, [5, 8]);

fn intersection<'r>(&'r self, other: &'r TreeSet<V>) -> Intersection<'r, V>

Visits the values representing the intersection, in ascending order.

Examples

use immutable_map::TreeSet;

let a = TreeSet::new().insert(1).insert(2);
let b = TreeSet::new().insert(2).insert(3);

let intersection: Vec<_> = a.intersection(&b).cloned().collect();
assert_eq!(intersection, [2]);

fn union<'r>(&'r self, other: &'r TreeSet<V>) -> Union<'r, V>

Visits the values representing the union, in ascending order.

Examples

use immutable_map::TreeSet;

let a = TreeSet::new().insert(1).insert(2);
let b = TreeSet::new().insert(2).insert(3);

let union: Vec<_> = a.union(&b).cloned().collect();
assert_eq!(union, [1, 2, 3]);

fn difference<'r>(&'r self, other: &'r TreeSet<V>) -> Difference<'r, V>

Visits the values representing the difference of self and other, in ascending order.

Examples

use immutable_map::TreeSet;

let a = TreeSet::new().insert(1).insert(2);
let b = TreeSet::new().insert(2).insert(3);

let difference: Vec<_> = a.difference(&b).cloned().collect();
assert_eq!(difference, [1]);

fn symmetric_difference<'r>(&'r self,
                            other: &'r TreeSet<V>)
                            -> SymmetricDifference<'r, V>

Visits the values representing the symmetric difference, in ascending order.

Examples

use immutable_map::TreeSet;

let a = TreeSet::new().insert(1).insert(2);
let b = TreeSet::new().insert(2).insert(3);

let symm_diff: Vec<_> = a.symmetric_difference(&b).cloned().collect();
assert_eq!(symm_diff, [1, 3]);

fn is_disjoint(&self, other: &TreeSet<V>) -> bool

Returns true if the set has no elements in common with other. This is equivalent to checking for an empty intersection.

Examples

use immutable_map::TreeSet;

let a = TreeSet::new().insert(1).insert(2);
let b = TreeSet::new().insert(2).insert(3);
let c = TreeSet::new().insert(3).insert(4);

assert_eq!(false, a.is_disjoint(&b));
assert_eq!(true, a.is_disjoint(&c));

fn is_subset(&self, other: &TreeSet<V>) -> bool

Returns true if self is a subset of other.

Examples

use immutable_map::TreeSet;

let sup = TreeSet::new().insert(1).insert(2).insert(3);
let a = TreeSet::new().insert(2);
let b = TreeSet::new().insert(3).insert(4);

assert_eq!(true, a.is_subset(&sup));
assert_eq!(false, b.is_subset(&sup));

fn is_superset(&self, other: &TreeSet<V>) -> bool

Returns true if self is a superset of other.

Examples

use immutable_map::TreeSet;

let sub = TreeSet::new().insert(1).insert(2);
let a = TreeSet::new().insert(1).insert(2).insert(3);
let b = TreeSet::new().insert(2).insert(3);

assert_eq!(true, a.is_superset(&sub));
assert_eq!(false, b.is_superset(&sub));

impl<V: Ord> TreeSet<V> where V: Clone

fn insert(&self, value: V) -> TreeSet<V>

Returns a new set with the value added to the set, replacing the existing value, if any.

Examples

use immutable_map::TreeSet;

let empty_set = TreeSet::new();
let new_set = empty_set.insert(3);

assert_eq!(false, empty_set.contains(&3));
assert_eq!(true, new_set.contains(&3));

fn insert_if_absent(&self, value: V) -> Option<TreeSet<V>>

Return a new copy of TreeSet with the value inserted.

Returns None if the set already has the value

Examples

use immutable_map::TreeSet;

let set = TreeSet::new().insert(2).insert(3);

assert_eq!(None, set.insert_if_absent(2));

let new_set = set.insert_if_absent(1).unwrap();

assert_eq!(true, new_set.contains(&1));

fn delete_min(&self) -> Option<(TreeSet<V>, &V)>

Returns a new set with the smallest element removed from the set, and the smallest element. Returns None if the set was empty

Examples

use immutable_map::TreeSet;

let empty_set = TreeSet::new();
assert_eq!(None, empty_set.delete_min());

let new_set = empty_set.insert(2).insert(3).insert(1);
let (set, removed) = new_set.delete_min().unwrap();

assert_eq!(false, set.contains(&1));
assert_eq!(&1, removed);

fn delete_max(&self) -> Option<(TreeSet<V>, &V)>

Returns a new set with the largest element removed from the set, and the largest element. Returns None if the set was empty

Examples

use immutable_map::TreeSet;

let empty_set = TreeSet::new();
assert_eq!(None, empty_set.delete_max());

let new_set = empty_set.insert(2).insert(3).insert(1);
let (set, removed) = new_set.delete_max().unwrap();

assert_eq!(false, set.contains(&3));
assert_eq!(&3, removed);

fn remove<Q: Ord + ?Sized>(&self, key: &Q) -> Option<(TreeSet<V>, &V)> where V: Borrow<Q>

Returns the new set with the value removed, and the removed value

Returns None if the original set did not contain the value

The value may be any borrowed form of the set's value type, but the ordering on the borrowed form must match the ordering on the value type.

Examples

use immutable_map::TreeSet;

let empty_set = TreeSet::new();
assert_eq!(None, empty_set.remove(&2));

let set = empty_set.insert(2).insert(3).insert(1);

let (new_set, removed) = set.remove(&2).unwrap();

assert_eq!(false, new_set.contains(&2));
assert_eq!(&2, removed);

Trait Implementations

impl<V: Clone> Clone for TreeSet<V>

fn clone(&self) -> TreeSet<V>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<V: Default> Default for TreeSet<V>

fn default() -> TreeSet<V>

Returns the "default value" for a type.

impl<V: Debug + Ord> Debug for TreeSet<V>

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

Formats the value using the given formatter.

impl<'r, V: Ord> IntoIterator for &'r TreeSet<V>

type Item = &'r V

The type of the elements being iterated over.

type IntoIter = Keys<Iter<'r, V, ()>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Keys<Iter<'r, V, ()>>

Creates an iterator from a value.

impl<V: PartialEq> PartialEq for TreeSet<V>

fn eq(&self, other: &TreeSet<V>) -> 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<V: Eq> Eq for TreeSet<V>

impl<V: PartialOrd> PartialOrd for TreeSet<V>

fn partial_cmp(&self, other: &TreeSet<V>) -> Option<Ordering>

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

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

This method tests less than (for self and other) and is used by the < operator.

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

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

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

This method tests greater than (for self and other) and is used by the > operator.

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

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

impl<V: Ord> Ord for TreeSet<V>

fn cmp(&self, other: &TreeSet<V>) -> Ordering

This method returns an Ordering between self and other.

impl<V: Ord + Clone> FromIterator<V> for TreeSet<V>

fn from_iter<T>(iter: T) -> TreeSet<V> where T: IntoIterator<Item=V>

Creates a value from an iterator.