Struct TreeSet

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

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

Implementations

impl<V> TreeSet<V>

pub fn new() -> TreeSet<V>

Makes a new empty TreeSet

Examples

use immutable_map::TreeSet;

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

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

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

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

pub 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>

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

pub 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"));

pub 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]);

pub 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]);

pub 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]);

pub 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]);

pub 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]);

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

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

pub 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> TreeSet<V>

where V: Clone + Ord,

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

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

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

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

pub 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: Debug + Ord> Debug for TreeSet<V>

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

Formats the value using the given formatter.

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

fn default() -> TreeSet<V>

Returns the “default value” for a type.

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.

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: Ord> Ord for TreeSet<V>

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

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

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<V: Eq> Eq for TreeSet<V>