Struct BTreeIndexSet 

pub struct BTreeIndexSet<T> { /* private fields */ }

BTree-based index set.

This is a thin wrapper around BTreeIndexMap<T, ()> providing a set-like API: every value is stored at most once, values keep a stable index until they (or an earlier value) are removed, and values can be iterated either in insertion order or in sorted order.

Example

use btree_indexmap::BTreeIndexSet;

let mut set = BTreeIndexSet::new();

// Values are stored in insertion order and assigned a stable index.
assert!(set.insert("banana"));
assert!(set.insert("apple"));
assert!(!set.insert("banana")); // already present

// O(1) access by index (insertion order).
assert_eq!(set.as_slice(), ["banana", "apple"]);

// O(log n) lookup, returning the stable index alongside the value.
assert_eq!(set.get_full("apple"), Some((1, &"apple")));

// Iterate in sorted order.
let sorted: Vec<_> = set.iter_sorted().copied().collect();
assert_eq!(sorted, ["apple", "banana"]);

Implementations

impl<T> BTreeIndexSet<T>

pub fn new() -> Self

Creates a new, empty set.

pub fn singleton(value: T) -> Self

where T: Ord,

Creates a new set containing the single value.

pub fn clear(&mut self)

Removes all values from the set.

This keeps the capacity allocated for the values.

pub fn is_empty(&self) -> bool

Returns true if the set contains no values.

pub fn len(&self) -> usize

Returns the number of values in the set.

pub fn as_slice(&self) -> &[T]

Returns the values of the set as a slice, in insertion (index) order.

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

where Q: ?Sized + Comparable<T>,

Returns the index and a reference to the value equal to value, if any.

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

where Q: ?Sized + Comparable<T>,

Returns the index of value in the set, if any.

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

where Q: ?Sized + Comparable<T>,

Returns a reference to the value equal to value, if any.

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

where Q: ?Sized + Comparable<T>,

Returns true if the set contains value.

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

where T: Ord,

Inserts value in the set, returning its index and whether it was newly inserted (true) or already present (false).

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

where T: Ord,

Inserts value in the set, returning whether it was newly inserted.

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

where Q: ?Sized + Comparable<T>,

Removes value from the set, returning its former index and the value itself, if it was present.

Shifts every following value one index down.

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

where Q: ?Sized + Comparable<T>,

Removes value from the set, returning the removed value, if any.

Shifts every following value one index down.

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

where Q: ?Sized + Comparable<T>,

Removes value from the set, returning whether the value was present.

Shifts every following value one index down.

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

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

Removes value from the set, returning its former index and the value itself, if it was present.

Moves the last value into the removed slot.

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

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

Removes value from the set, returning the removed value, if any.

Moves the last value into its place.

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

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

Removes value from the set, returning whether the value was present.

Moves the last value into its place.

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

Returns an iterator over the values of the set, in insertion (index) order.

pub fn iter_sorted(&self) -> IterSorted<'_, T>

Returns an iterator over the values of the set, sorted according to T’s implementation of Ord.

pub fn into_iter_sorted(self) -> IntoIterSorted<T>

Turns this set into an iterator over its values, sorted according to T’s implementation of Ord.

Trait Implementations

impl<T: Clone> Clone for BTreeIndexSet<T>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for BTreeIndexSet<T>

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

Formats the value using the given formatter.

impl<T> Default for BTreeIndexSet<T>

fn default() -> Self

Returns the “default value” for a type.

impl<T: Eq> Eq for BTreeIndexSet<T>

impl<T: Ord> Extend<T> for BTreeIndexSet<T>

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: T)

🔬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: Ord> FromIterator<T> for BTreeIndexSet<T>

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

Creates a value from an iterator.

impl<T: Hash> Hash for BTreeIndexSet<T>

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 BTreeIndexSet<T>

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

Panics

Panics if index is out of bounds.

type Output = T

The returned type after indexing.

impl<T> IntoIterator for BTreeIndexSet<T>

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

type Item = T

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

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

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

type Item = &'a T

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T: Ord> Ord for BTreeIndexSet<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.

fn clamp_to<R>(self, range: R) -> Self

where Self: Sized, R: ClampBounds<Self>,

🔬This is a nightly-only experimental API. (clamp_to)

Restrict a value to a certain range.

impl<T: PartialEq> PartialEq for BTreeIndexSet<T>

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

Equality operator ==.

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

Inequality operator !=.

impl<T: PartialOrd> PartialOrd for BTreeIndexSet<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.