Struct BTreeSet 

pub struct BTreeSet<T, Node = Vec<T>>
where
    T: Ord + Clone + 'static,
    Node: NodeLike<T>,
{ /* private fields */ }

A persistent concurrent 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 crate::BTreeSet::iter produce their items in order, and take worst-case logarithmic and amortized constant time per item returned.

Examples

use indexset::concurrent::set::BTreeSet;

// Type inference lets us omit an explicit type signature (which
// would be `BTreeSet<&str>` in this example).
let mut books = BTreeSet::<&str>::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 indexset::concurrent::set::BTreeSet;

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

Implementations

impl<T, Node> BTreeSet<T, Node>

where T: Debug + Ord + Clone + Send, Node: NodeLike<T> + Send + 'static,

pub fn new() -> Self

pub fn with_maximum_node_size(node_capacity: 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 indexset::concurrent::set::BTreeSet;

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

pub fn attach_node(&self, node: Node)

pub fn attach_nodes(&self, nodes: impl IntoIterator<Item = Node>)

Attaches a persisted topology in one structural publication.

Nodes must be non-empty and internally sorted. Their values, together with any nodes already attached to this set, must form mutually ordered non-overlapping ranges. The same preconditions as Self::attach_node apply to every item.

pub fn insert(&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.

Examples

use indexset::concurrent::set::BTreeSet;

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

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

pub fn remove_cdc<Q>(&self, value: &Q) -> (Option<T>, Vec<ChangeEvent<T>>)

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

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

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 indexset::concurrent::set::BTreeSet;

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

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

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 indexset::concurrent::set::BTreeSet;

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

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

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

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn capacity(&self) -> usize

pub fn node_count(&self) -> usize

impl<'a, T, Node> BTreeSet<T, Node>

where T: Debug + Ord + Clone + Send + 'static, Node: NodeLike<T> + Send + 'static,

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

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

The iterator yields owned clones of the stored elements (see Iter): collected values remain valid under arbitrary concurrent mutation of the set.

Examples

use indexset::concurrent::set::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 indexset::concurrent::set::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 range<Q, R>(&'a self, range: R) -> Range<'a, T, Node>

where T: Borrow<Q>, Q: Ord + ?Sized, 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 indexset::concurrent::set::BTreeSet;
use std::ops::Bound::Included;

let mut set = BTreeSet::<usize>::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());

impl<T> BTreeSet<T>

where T: Debug + Ord + Clone + Send + 'static,

pub fn remove_range<R, Q>(&self, range: R)

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

Trait Implementations

impl<T, Node> Debug for BTreeSet<T, Node>

where T: Ord + Clone + 'static + Debug, Node: NodeLike<T> + Debug,

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

Formats the value using the given formatter.

impl<T: Ord + Clone + 'static, Node: NodeLike<T>> Default for BTreeSet<T, Node>

fn default() -> Self

Returns the “default value” for a type.

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

where T: Debug + Ord + Clone + Send,

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

Converts to this type from the input type.

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

where T: Debug + Ord + Clone + Send,

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

Creates a value from an iterator.

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

where T: Debug + Ord + Send + Clone, Node: NodeLike<T> + Send + 'static,

type Item = T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T, Node>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.