Struct BTreeSet 

pub struct BTreeSet<T>
where
    T: Ord,
{ /* private fields */ }

An ordered set based on a B-Tree.

See BTreeMap’s documentation for a detailed discussion of this collection’s performance benefits and drawbacks.

It is a logic error for an item to be modified in such a way that the item’s ordering relative to any other item, as determined by the Ord trait, changes while it is in the set. This is normally only possible through Cell, RefCell, global state, I/O, or unsafe code. The behavior resulting from such a logic error is not specified, but will be encapsulated to the BTreeSet that observed the logic error and not result in undefined behavior. This could include panics, incorrect results, aborts, memory leaks, and non-termination.

Iterators returned by BTreeSet::iter produce their items in order, and take worst-case logarithmic and amortized constant time per item returned.

Examples

use wt_indexset::BTreeSet;

// Type inference lets us omit an explicit type signature (which
// would be `BTreeSet<&str>` in this example).
let mut books = BTreeSet::new();

// Add some books.
books.insert("A Dance With Dragons");
books.insert("To Kill a Mockingbird");
books.insert("The Odyssey");
books.insert("The Great Gatsby");

// Check for a specific one.
if !books.contains("The Winds of Winter") {
    println!("We have {} books, but The Winds of Winter ain't one.",
             books.len());
}

// Remove a book.
books.remove("The Odyssey");

// Iterate over everything.
for book in &books {
    println!("{book}");
}

A BTreeSet with a known list of items can be initialized from an array:

use wt_indexset::BTreeSet;

let set = BTreeSet::from_iter([1, 2, 3]);

Implementations

impl<T: Ord> BTreeSet<T>

pub fn new() -> Self

Makes a new, empty BTreeSet with maximum node size 1024. Allocates one vec of capacity 1024.

Note that this does not mean that the maximum number of items is 1024.

In case you would like to make a tree with a different maximum node size, use the with_maximum_node_size method.

Examples

use wt_indexset::BTreeSet;

let mut set: BTreeSet<i32> = BTreeSet::new();

pub fn with_maximum_node_size(maximum_node_size: usize) -> Self

Makes a new, empty BTreeSet with the given maximum node size. Allocates one vec with the capacity set to be the specified node size.

Examples

use wt_indexset::BTreeSet;

let mut set: BTreeSet<i32> = BTreeSet::with_maximum_node_size(128);

pub fn clear(&mut self)

Clears the set, removing all elements.

Examples

use wt_indexset::BTreeSet;

let mut v = BTreeSet::new();
v.insert(1);
v.clear();
assert!(v.is_empty());

pub fn get_index(&self, idx: usize) -> Option<&T>

Returns a reference to the element in the i-th position of the set, if any.

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

Examples

use wt_indexset::BTreeSet;

let set = BTreeSet::from_iter([1, 2, 3]);
assert_eq!(set.get_index(0), Some(&1));
assert_eq!(set.get_index(2), Some(&3));
assert_eq!(set.get_index(4), None);

pub fn get<Q>(&self, value: &Q) -> Option<&T>

where T: Borrow<Q> + Ord, Q: Ord + ?Sized,

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

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

Examples

use wt_indexset::BTreeSet;

let set = BTreeSet::from([1, 2, 3]);
assert_eq!(set.get(&2), Some(&2));
assert_eq!(set.get(&4), None);

pub fn lower_bound<Q>(&self, value: &Q) -> Option<&T>

where T: Borrow<Q>, Q: Ord + ?Sized,

Returns a reference to the first element in the set, if any, that is not less than the input.

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

Examples

use wt_indexset::BTreeSet;

let set = BTreeSet::from_iter([1, 2, 3, 5]);
assert_eq!(set.lower_bound(&2), Some(&2));
assert_eq!(set.lower_bound(&4), Some(&5));

pub fn len(&self) -> usize

Returns the number of elements in the set.

Examples

use wt_indexset::BTreeSet;

let mut v = BTreeSet::new();
assert_eq!(v.len(), 0);
v.insert(1);
assert_eq!(v.len(), 1);

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

Adds a value to the set.

Returns whether the value was newly inserted. That is:

• If the set did not previously contain an equal value, true is returned.
• If the set already contained an equal value, false is returned, and the entry is not updated.

See the module-level documentation for more.

Examples

use wt_indexset::BTreeSet;

let mut set = BTreeSet::new();

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

pub fn replace(&mut self, value: T) -> Option<T>

Adds a value to the set, replacing the existing element, if any, that is equal to the value. Returns the replaced element.

Examples

use wt_indexset::BTreeSet;

let mut set = BTreeSet::new();
set.insert(Vec::<i32>::new());

assert_eq!(set.get(&[][..]).unwrap().capacity(), 0);
println!("{}", set.replace(Vec::with_capacity(10)).unwrap().capacity());
println!("{}", set.get(&[][..]).unwrap().capacity());
assert_eq!(set.get(&[][..]).unwrap().capacity(), 10);

pub fn contains<Q>(&self, value: &Q) -> bool

where T: Borrow<Q>, Q: Ord + ?Sized,

Returns true if the set contains an element equal to the value.

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

Examples

use wt_indexset::BTreeSet;

let set = BTreeSet::from_iter([1, 2, 3]);
assert_eq!(set.contains(&1), true);
assert_eq!(set.contains(&4), false);

pub fn remove<Q>(&mut self, value: &Q) -> bool

where T: Borrow<Q>, Q: Ord + ?Sized,

If the set contains an element equal to the value, removes it from the set and drops it. Returns whether such an element was present.

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

Examples

use wt_indexset::BTreeSet;

let mut set = BTreeSet::new();

set.insert(2);
assert_eq!(set.remove(&2), true);
assert_eq!(set.remove(&2), false);

pub fn take<Q>(&mut self, value: &Q) -> Option<T>

where T: Borrow<Q>, Q: Ord + ?Sized,

Removes and returns the element in the set, if any, that is equal to the value.

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

Examples

use wt_indexset::BTreeSet;

let mut set = BTreeSet::from_iter([1, 2, 3]);
assert_eq!(set.take(&2), Some(2));
assert_eq!(set.take(&2), None);

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

Returns a reference to the first element in the set, if any. This element is always the minimum of all elements in the set.

Examples

Basic usage:

use wt_indexset::BTreeSet;

let mut set = BTreeSet::new();
assert_eq!(set.first(), None);
set.insert(1);
assert_eq!(set.first(), Some(&1));
set.insert(2);
assert_eq!(set.first(), Some(&1));

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

Returns a reference to the last element in the set, if any. This element is always the maximum of all elements in the set.

Examples

Basic usage:

use wt_indexset::BTreeSet;

let mut set = BTreeSet::new();
assert_eq!(set.last(), None);
set.insert(1);
assert_eq!(set.last(), Some(&1));
set.insert(2);
assert_eq!(set.last(), Some(&2));

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

Removes the first element from the set and returns it, if any. The first element is always the minimum element in the set.

Examples

use wt_indexset::BTreeSet;

let mut set = BTreeSet::new();

set.insert(1);
while let Some(n) = set.pop_first() {
    assert_eq!(n, 1);
}
assert!(set.is_empty());

pub fn pop_index(&mut self, idx: usize) -> T

Removes the i-th element from the set and returns it, if any.

Examples

use wt_indexset::BTreeSet;

let mut set = BTreeSet::new();

set.insert(1);
set.insert(2);
assert_eq!(set.pop_index(0), 1);
assert_eq!(set.pop_index(0), 2);
assert!(set.is_empty());

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

Removes the last element from the set and returns it, if any. The last element is always the maximum element in the set.

Examples

use wt_indexset::BTreeSet;

let mut set = BTreeSet::new();

set.insert(1);
while let Some(n) = set.pop_last() {
    assert_eq!(n, 1);
}
assert!(set.is_empty());

pub fn is_empty(&self) -> bool

Returns true if the set contains no elements.

Examples

use wt_indexset::BTreeSet;

let mut v = BTreeSet::new();
assert!(v.is_empty());
v.insert(1);
assert!(!v.is_empty());

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

Returns true if the set is a subset of another, i.e., other contains at least all the elements in self.

Examples

use wt_indexset::BTreeSet;

let sup = BTreeSet::from_iter([1, 2, 3]);
let mut set = BTreeSet::new();

assert_eq!(set.is_subset(&sup), true);
set.insert(2);
assert_eq!(set.is_subset(&sup), true);
set.insert(4);
assert_eq!(set.is_subset(&sup), false);

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

Returns true if the set is a superset of another, i.e., self contains at least all the elements in other.

Examples

use wt_indexset::BTreeSet;

let sub = BTreeSet::from_iter([1, 2]);
let mut set = BTreeSet::new();

assert_eq!(set.is_superset(&sub), false);

set.insert(0);
set.insert(1);
assert_eq!(set.is_superset(&sub), false);

set.insert(2);
assert_eq!(set.is_superset(&sub), true);

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

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

Examples

use wt_indexset::BTreeSet;

let a = BTreeSet::from_iter([1, 2, 3]);
let mut b = BTreeSet::new();

assert_eq!(a.is_disjoint(&b), true);
b.insert(4);
assert_eq!(a.is_disjoint(&b), true);
b.insert(1);
assert_eq!(a.is_disjoint(&b), false);

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

Gets an iterator that visits the elements in the BTreeSet in ascending order.

Examples

use wt_indexset::BTreeSet;

let set = BTreeSet::from_iter([1, 2, 3]);
let mut set_iter = set.iter();
assert_eq!(set_iter.next(), Some(&1));
assert_eq!(set_iter.next(), Some(&2));
assert_eq!(set_iter.next(), Some(&3));
assert_eq!(set_iter.next(), None);

Values returned by the iterator are returned in ascending order:

use wt_indexset::BTreeSet;

let set = BTreeSet::from_iter([3, 1, 2]);
let mut set_iter = set.iter();
assert_eq!(set_iter.next(), Some(&1));
assert_eq!(set_iter.next(), Some(&2));
assert_eq!(set_iter.next(), Some(&3));
assert_eq!(set_iter.next(), None);

pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, T>

Visits the elements representing the union, i.e., all the elements in self or other, without duplicates, in ascending order.

Examples

use wt_indexset::BTreeSet;

let mut a = BTreeSet::new();
a.insert(1);

let mut b = BTreeSet::new();
b.insert(2);

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

pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, T>

Visits the elements representing the difference, i.e., the elements that are in self but not in other, in ascending order.

Examples

use wt_indexset::BTreeSet;

let mut a = BTreeSet::new();
a.insert(1);
a.insert(2);

let mut b = BTreeSet::new();
b.insert(2);
b.insert(3);

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

pub fn symmetric_difference<'a>( &'a self, other: &'a Self, ) -> SymmetricDifference<'a, T>

Visits the elements representing the symmetric difference, i.e., the elements that are in self or in other but not in both, in ascending order.

Examples

use wt_indexset::BTreeSet;

let mut a = BTreeSet::new();
a.insert(1);
a.insert(2);

let mut b = BTreeSet::new();
b.insert(2);
b.insert(3);

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

pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, T>

Visits the elements representing the intersection, i.e., the elements that are both in self and other, in ascending order.

Examples

use wt_indexset::BTreeSet;

let mut a = BTreeSet::new();
a.insert(1);
a.insert(2);

let mut b = BTreeSet::new();
b.insert(2);
b.insert(3);

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

pub fn retain<F, Q>(&mut self, f: F)

where T: Borrow<Q>, Q: Ord + ?Sized, F: FnMut(&Q) -> bool,

Retains only the elements specified by the predicate.

In other words, remove all elements e for which f(&e) returns false. The elements are visited in ascending order.

Examples

use wt_indexset::BTreeSet;

let mut set = BTreeSet::from_iter([1, 2, 3, 4, 5, 6]);
// Keep only the even numbers.
set.retain(|&k| k % 2 == 0);
assert!(set.iter().eq([2, 4, 6].iter()));

pub fn split_off<Q>(&mut self, value: &Q) -> Self

where T: Borrow<Q>, Q: Ord + ?Sized,

Splits the collection into two at the value. Returns a new collection with all elements greater than or equal to the value.

Examples

Basic usage:

use wt_indexset::BTreeSet;

let mut a = BTreeSet::new();
a.insert(1);
a.insert(2);
a.insert(3);
a.insert(17);
a.insert(41);

let b = a.split_off(&3);

assert_eq!(a.len(), 2);
assert_eq!(b.len(), 3);

assert!(a.contains(&1));
assert!(a.contains(&2));

assert!(b.contains(&3));
assert!(b.contains(&17));
assert!(b.contains(&41));

pub fn append(&mut self, other: &mut Self)

Moves all elements from other into self, leaving other empty.

Examples

use wt_indexset::BTreeSet;

let mut a = BTreeSet::new();
a.insert(1);
a.insert(2);
a.insert(3);

let mut b = BTreeSet::new();
b.insert(3);
b.insert(4);
b.insert(5);

a.append(&mut b);

assert_eq!(a.len(), 5);
assert_eq!(b.len(), 0);

assert!(a.contains(&1));
assert!(a.contains(&2));
assert!(a.contains(&3));
assert!(a.contains(&4));
assert!(a.contains(&5));

pub fn range<R, Q>(&self, range: R) -> Range<'_, T>

where Q: Ord + ?Sized, T: Borrow<Q>, R: RangeBounds<Q>,

Constructs a double-ended iterator over a sub-range of elements in the set. The simplest way is to use the range syntax min..max, thus range(min..max) will yield elements from min (inclusive) to max (exclusive). The range may also be entered as (Bound<T>, Bound<T>), so for example range((Excluded(4), Included(10))) will yield a left-exclusive, right-inclusive range from 4 to 10.

Panics

Panics if range start > end. Panics if range start == end and both bounds are Excluded.

Examples

use wt_indexset::BTreeSet;
use std::ops::Bound::Included;

let mut set = BTreeSet::new();
set.insert(3);
set.insert(5);
set.insert(8);
for &elem in set.range((Included(&4), Included(&8))) {
    println!("{elem}");
}
assert_eq!(Some(&5), set.range(4..).next());

pub fn rank<Q>(&self, value: &Q) -> usize

where Q: Ord + ?Sized, T: Borrow<Q>,

Returns the position in which the given element would fall in the already-existing sorted order.

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

Examples

use wt_indexset::BTreeSet;

let set = BTreeSet::from_iter([1, 2, 3]);
assert_eq!(set.rank(&1), 0);
assert_eq!(set.rank(&3), 2);
assert_eq!(set.rank(&4), 3);
assert_eq!(set.rank(&100), 3);

pub fn range_idx<R>(&self, range: R) -> Range<'_, T>

where R: RangeBounds<usize>,

Trait Implementations

impl<T> Clone for BTreeSet<T>

where T: Ord + Clone,

fn clone(&self) -> BTreeSet<T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T> Debug for BTreeSet<T>

where T: Ord + Debug,

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

Formats the value using the given formatter.

impl<T> Default for BTreeSet<T>

where T: Ord,

fn default() -> Self

Returns the “default value” for a type.

impl<T, const N: usize> From<[T; N]> for BTreeSet<T>

where T: Ord,

fn from(value: [T; N]) -> Self

Converts to this type from the input type.

impl<T> FromIterator<T> for BTreeSet<T>

where T: Ord,

fn from_iter<K: IntoIterator<Item = T>>(iter: K) -> Self

Creates a value from an iterator.

impl<T> Hash for BTreeSet<T>

where T: Ord + Hash,

fn hash<__H: Hasher>(&self, state: &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<T> Index<usize> for BTreeSet<T>

where T: Ord,

type Output = T

The returned type after indexing.

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<'a, T> IntoIterator for &'a BTreeSet<T>

where T: Ord,

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) -> Self::IntoIter

Creates an iterator from a value.

impl<T> IntoIterator for BTreeSet<T>

where T: Ord,

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> Ord for BTreeSet<T>

where T: Ord + Ord,

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

where T: Ord + PartialEq,

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

where T: Ord + PartialOrd,

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

where T: Ord + Eq,

impl<T> StructuralPartialEq for BTreeSet<T>

where T: Ord,