Struct sp_core::bounded::bounded_btree_set::BoundedBTreeSet

pub struct BoundedBTreeSet<T, S>(_, _);

A bounded set based on a B-Tree.

B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing the amount of work performed in a search. See BTreeSet for more details.

Unlike a standard BTreeSet, there is an enforced upper limit to the number of items in the set. All internal operations ensure this bound is respected.

Implementations

impl<T, S> BoundedBTreeSet<T, S>where
    S: Get<u32>,

pub fn bound() -> usize

Get the bound of the type in usize.

Examples found in repository

src/bounded/bounded_btree_set.rs (line 85)

	pub fn into_inner(self) -> BTreeSet<T> {
		debug_assert!(self.0.len() <= Self::bound());
		self.0
	}

	/// Consumes self and mutates self via the given `mutate` function.
	///
	/// If the outcome of mutation is within bounds, `Some(Self)` is returned. Else, `None` is
	/// returned.
	///
	/// This is essentially a *consuming* shorthand [`Self::into_inner`] -> `...` ->
	/// [`Self::try_from`].
	pub fn try_mutate(mut self, mut mutate: impl FnMut(&mut BTreeSet<T>)) -> Option<Self> {
		mutate(&mut self.0);
		(self.0.len() <= Self::bound()).then(move || self)
	}

	/// Clears the set, removing all elements.
	pub fn clear(&mut self) {
		self.0.clear()
	}

	/// Exactly the same semantics as [`BTreeSet::insert`], but returns an `Err` (and is a noop) if
	/// the new length of the set exceeds `S`.
	///
	/// In the `Err` case, returns the inserted item so it can be further used without cloning.
	pub fn try_insert(&mut self, item: T) -> Result<bool, T> {
		if self.len() < Self::bound() || self.0.contains(&item) {
			Ok(self.0.insert(item))
		} else {
			Err(item)
		}
	}

	/// Remove an item from the set, returning whether it was previously in the set.
	///
	/// The item may be any borrowed form of the set's item type, but the ordering on the borrowed
	/// form _must_ match the ordering on the item type.
	pub fn remove<Q>(&mut self, item: &Q) -> bool
	where
		T: Borrow<Q>,
		Q: Ord + ?Sized,
	{
		self.0.remove(item)
	}

	/// Removes and returns the value in the set, if any, that is equal to the given one.
	///
	/// 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 take<Q>(&mut self, value: &Q) -> Option<T>
	where
		T: Borrow<Q> + Ord,
		Q: Ord + ?Sized,
	{
		self.0.take(value)
	}
}

impl<T, S> Default for BoundedBTreeSet<T, S>
where
	T: Ord,
	S: Get<u32>,
{
	fn default() -> Self {
		Self::new()
	}
}

impl<T, S> Clone for BoundedBTreeSet<T, S>
where
	BTreeSet<T>: Clone,
{
	fn clone(&self) -> Self {
		BoundedBTreeSet(self.0.clone(), PhantomData)
	}
}

impl<T, S> sp_std::fmt::Debug for BoundedBTreeSet<T, S>
where
	BTreeSet<T>: sp_std::fmt::Debug,
	S: Get<u32>,
{
	fn fmt(&self, f: &mut sp_std::fmt::Formatter<'_>) -> sp_std::fmt::Result {
		f.debug_tuple("BoundedBTreeSet").field(&self.0).field(&Self::bound()).finish()
	}
}

impl<T, S1, S2> PartialEq<BoundedBTreeSet<T, S1>> for BoundedBTreeSet<T, S2>
where
	BTreeSet<T>: PartialEq,
	S1: Get<u32>,
	S2: Get<u32>,
{
	fn eq(&self, other: &BoundedBTreeSet<T, S1>) -> bool {
		S1::get() == S2::get() && self.0 == other.0
	}
}

impl<T, S> Eq for BoundedBTreeSet<T, S>
where
	BTreeSet<T>: Eq,
	S: Get<u32>,
{
}

impl<T, S> PartialEq<BTreeSet<T>> for BoundedBTreeSet<T, S>
where
	BTreeSet<T>: PartialEq,
	S: Get<u32>,
{
	fn eq(&self, other: &BTreeSet<T>) -> bool {
		self.0 == *other
	}
}

impl<T, S> PartialOrd for BoundedBTreeSet<T, S>
where
	BTreeSet<T>: PartialOrd,
	S: Get<u32>,
{
	fn partial_cmp(&self, other: &Self) -> Option<sp_std::cmp::Ordering> {
		self.0.partial_cmp(&other.0)
	}
}

impl<T, S> Ord for BoundedBTreeSet<T, S>
where
	BTreeSet<T>: Ord,
	S: Get<u32>,
{
	fn cmp(&self, other: &Self) -> sp_std::cmp::Ordering {
		self.0.cmp(&other.0)
	}
}

impl<T, S> IntoIterator for BoundedBTreeSet<T, S> {
	type Item = T;
	type IntoIter = sp_std::collections::btree_set::IntoIter<T>;

	fn into_iter(self) -> Self::IntoIter {
		self.0.into_iter()
	}
}

impl<'a, T, S> IntoIterator for &'a BoundedBTreeSet<T, S> {
	type Item = &'a T;
	type IntoIter = sp_std::collections::btree_set::Iter<'a, T>;

	fn into_iter(self) -> Self::IntoIter {
		self.0.iter()
	}
}

impl<T, S> MaxEncodedLen for BoundedBTreeSet<T, S>
where
	T: MaxEncodedLen,
	S: Get<u32>,
{
	fn max_encoded_len() -> usize {
		Self::bound()
			.saturating_mul(T::max_encoded_len())
			.saturating_add(codec::Compact(S::get()).encoded_size())
	}
}

impl<T, S> Deref for BoundedBTreeSet<T, S>
where
	T: Ord,
{
	type Target = BTreeSet<T>;

	fn deref(&self) -> &Self::Target {
		&self.0
	}
}

impl<T, S> AsRef<BTreeSet<T>> for BoundedBTreeSet<T, S>
where
	T: Ord,
{
	fn as_ref(&self) -> &BTreeSet<T> {
		&self.0
	}
}

impl<T, S> From<BoundedBTreeSet<T, S>> for BTreeSet<T>
where
	T: Ord,
{
	fn from(set: BoundedBTreeSet<T, S>) -> Self {
		set.0
	}
}

impl<T, S> TryFrom<BTreeSet<T>> for BoundedBTreeSet<T, S>
where
	T: Ord,
	S: Get<u32>,
{
	type Error = ();

	fn try_from(value: BTreeSet<T>) -> Result<Self, Self::Error> {
		(value.len() <= Self::bound())
			.then(move || BoundedBTreeSet(value, PhantomData))
			.ok_or(())
	}

impl<T, S> BoundedBTreeSet<T, S>where
    T: Ord,
    S: Get<u32>,

pub fn new() -> Self

Create a new BoundedBTreeSet.

Does not allocate.

Examples found in repository

src/bounded/bounded_btree_set.rs (line 149)

	fn default() -> Self {
		Self::new()
	}

pub fn into_inner(self) -> BTreeSet<T>

Consume self, and return the inner BTreeSet.

This is useful when a mutating API of the inner type is desired, and closure-based mutation such as provided by try_mutate is inconvenient.

pub fn try_mutate(self, mutate: impl FnMut(&mut BTreeSet<T>)) -> Option<Self>

Consumes self and mutates self via the given mutate function.

If the outcome of mutation is within bounds, Some(Self) is returned. Else, None is returned.

This is essentially a consuming shorthand Self::into_inner -> ... -> Self::try_from.

pub fn clear(&mut self)

Clears the set, removing all elements.

pub fn try_insert(&mut self, item: T) -> Result<bool, T>

Exactly the same semantics as BTreeSet::insert, but returns an Err (and is a noop) if the new length of the set exceeds S.

In the Err case, returns the inserted item so it can be further used without cloning.

pub fn remove<Q>(&mut self, item: &Q) -> boolwhere
    T: Borrow<Q>,
    Q: Ord + ?Sized,

Remove an item from the set, returning whether it was previously in the set.

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

pub fn take<Q>(&mut self, value: &Q) -> Option<T>where
    T: Borrow<Q> + Ord,
    Q: Ord + ?Sized,

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

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.

Methods from Deref<Target = BTreeSet<T>>

pub fn range<K, R>(&self, range: R) -> Range<'_, T>where
    K: Ord + ?Sized,
    T: Borrow<K> + Ord,
    R: RangeBounds<K>,

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 std::collections::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 difference<'a>(
    &'a self,
    other: &'a BTreeSet<T, A>
) -> Difference<'a, T, A>where
    T: Ord,

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

Examples

use std::collections::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 BTreeSet<T, A>
) -> SymmetricDifference<'a, T>where
    T: Ord,

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 std::collections::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 BTreeSet<T, A>
) -> Intersection<'a, T, A>where
    T: Ord,

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

Examples

use std::collections::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 union<'a>(&'a self, other: &'a BTreeSet<T, A>) -> Union<'a, T>where
    T: Ord,

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

Examples

use std::collections::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 contains<Q>(&self, value: &Q) -> boolwhere
    T: Borrow<Q> + Ord,
    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 std::collections::BTreeSet;

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

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 std::collections::BTreeSet;

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

pub fn is_disjoint(&self, other: &BTreeSet<T, A>) -> boolwhere
    T: Ord,

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

Examples

use std::collections::BTreeSet;

let a = BTreeSet::from([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 is_subset(&self, other: &BTreeSet<T, A>) -> boolwhere
    T: Ord,

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

Examples

use std::collections::BTreeSet;

let sup = BTreeSet::from([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: &BTreeSet<T, A>) -> boolwhere
    T: Ord,

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

Examples

use std::collections::BTreeSet;

let sub = BTreeSet::from([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 first(&self) -> Option<&T>where
    T: Ord,

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 std::collections::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>where
    T: Ord,

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 std::collections::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 iter(&self) -> Iter<'_, T>

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

Examples

use std::collections::BTreeSet;

let set = BTreeSet::from([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 std::collections::BTreeSet;

let set = BTreeSet::from([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 len(&self) -> usize

Returns the number of elements in the set.

Examples

use std::collections::BTreeSet;

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

pub fn is_empty(&self) -> bool

Returns true if the set contains no elements.

Examples

use std::collections::BTreeSet;

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

Trait Implementations

impl<T, S> AsRef<BTreeSet<T, Global>> for BoundedBTreeSet<T, S>where
    T: Ord,

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

Converts this type into a shared reference of the (usually inferred) input type.

impl<T, S> Clone for BoundedBTreeSet<T, S>where
    BTreeSet<T>: Clone,

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T, S> Debug for BoundedBTreeSet<T, S>where
    BTreeSet<T>: Debug,
    S: Get<u32>,

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

Formats the value using the given formatter.

impl<T, S> Decode for BoundedBTreeSet<T, S>where
    T: Decode + Ord,
    S: Get<u32>,

fn decode<I: Input>(input: &mut I) -> Result<Self, Error>

Attempt to deserialise the value from input.

fn skip<I: Input>(input: &mut I) -> Result<(), Error>

Attempt to skip the encoded value from input.

fn encoded_fixed_size() -> Option<usize>

Returns the fixed encoded size of the type.

impl<T, S> DecodeLength for BoundedBTreeSet<T, S>

fn len(self_encoded: &[u8]) -> Result<usize, Error>

Return the number of elements in self_encoded.

impl<T, S> Default for BoundedBTreeSet<T, S>where
    T: Ord,
    S: Get<u32>,

fn default() -> Self

Returns the “default value” for a type.

impl<T, S> Deref for BoundedBTreeSet<T, S>where
    T: Ord,

type Target = BTreeSet<T, Global>

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl<T, S> Encode for BoundedBTreeSet<T, S>where
    BTreeSet<T>: Encode,
    PhantomData<S>: Encode,

fn encode_to<__CodecOutputEdqy: Output + ?Sized>(
    &self,
    __codec_dest_edqy: &mut __CodecOutputEdqy
)

Convert self to a slice and append it to the destination.

fn size_hint(&self) -> usize

If possible give a hint of expected size of the encoding.

fn encode(&self) -> Vec<u8, Global>

Convert self to an owned vector.

fn using_encoded<R, F>(&self, f: F) -> Rwhere
    F: FnOnce(&[u8]) -> R,

Convert self to a slice and then invoke the given closure with it.

fn encoded_size(&self) -> usize

Calculates the encoded size.

impl<T, S> From<BoundedBTreeSet<T, S>> for BTreeSet<T>where
    T: Ord,

fn from(set: BoundedBTreeSet<T, S>) -> Self

Converts to this type from the input type.

impl<'a, T, S> IntoIterator for &'a BoundedBTreeSet<T, S>

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, S> IntoIterator for BoundedBTreeSet<T, S>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T, Global>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T, S> MaxEncodedLen for BoundedBTreeSet<T, S>where
    T: MaxEncodedLen,
    S: Get<u32>,

fn max_encoded_len() -> usize

Upper bound, in bytes, of the maximum encoded size of this item.

impl<T, S> Ord for BoundedBTreeSet<T, S>where
    BTreeSet<T>: Ord,
    S: Get<u32>,

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Selfwhere
    Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Selfwhere
    Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Selfwhere
    Self: Sized + PartialOrd<Self>,

Restrict a value to a certain interval.

impl<T, S> PartialEq<BTreeSet<T, Global>> for BoundedBTreeSet<T, S>where
    BTreeSet<T>: PartialEq,
    S: Get<u32>,

fn eq(&self, other: &BTreeSet<T>) -> 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 !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T, S1, S2> PartialEq<BoundedBTreeSet<T, S1>> for BoundedBTreeSet<T, S2>where
    BTreeSet<T>: PartialEq,
    S1: Get<u32>,
    S2: Get<u32>,

fn eq(&self, other: &BoundedBTreeSet<T, S1>) -> 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 !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T, S> PartialOrd<BoundedBTreeSet<T, S>> for BoundedBTreeSet<T, S>where
    BTreeSet<T>: PartialOrd,
    S: Get<u32>,

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

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<I, T, Bound> TryCollect<BoundedBTreeSet<T, Bound>> for Iwhere
    T: Ord,
    I: ExactSizeIterator + Iterator<Item = T>,
    Bound: Get<u32>,

type Error = &'static str

The error type that gets returned when a collection can’t be made from self.

fn try_collect(self) -> Result<BoundedBTreeSet<T, Bound>, Self::Error>

Consume self and try to collect the results into C.

impl<T, S> TryFrom<BTreeSet<T, Global>> for BoundedBTreeSet<T, S>where
    T: Ord,
    S: Get<u32>,

type Error = ()

The type returned in the event of a conversion error.

fn try_from(value: BTreeSet<T>) -> Result<Self, Self::Error>

Performs the conversion.

impl<T, S> TypeInfo for BoundedBTreeSet<T, S>where
    BTreeSet<T>: TypeInfo + 'static,
    PhantomData<S>: TypeInfo + 'static,
    T: TypeInfo + 'static,
    S: 'static,

type Identity = BoundedBTreeSet<T, S>

The type identifying for which type info is provided.

fn type_info() -> Type

Returns the static type identifier for Self.

impl<T, S> EncodeLike<BTreeSet<T, Global>> for BoundedBTreeSet<T, S>where
    BTreeSet<T>: Encode,

impl<T, S> EncodeLike<BoundedBTreeSet<T, S>> for BoundedBTreeSet<T, S>where
    BTreeSet<T>: Encode,
    PhantomData<S>: Encode,

impl<T, S> Eq for BoundedBTreeSet<T, S>where
    BTreeSet<T>: Eq,
    S: Get<u32>,