Expand description
Safe, fallible, embedded-friendly ordered set.
Fallible APIs
TryFrom
isn’t implemented because it would collide with the blanket implementation.
See this open GitHub issue from 2018,
this is a known Rust limitation that should be fixed via specialization in the future.
Attribution Note
The majority of API examples and descriptions are adapted or directly copied from the standard library’s BTreeSet
.
The goal is to offer embedded developers familiar, ergonomic APIs on resource constrained systems that otherwise don’t get the luxury of dynamic collections.
Implementations
sourceimpl<T: Ord + Default, const N: usize> SgSet<T, N>
impl<T: Ord + Default, const N: usize> SgSet<T, N>
sourcepub fn new() -> Self
pub fn new() -> Self
Makes a new, empty SgSet
.
Examples
use scapegoat::SgSet;
let mut set: SgSet<i32, 10> = SgSet::new();
sourcepub fn set_rebal_param(
&mut self,
alpha_num: f32,
alpha_denom: f32
) -> Result<(), SgError>
pub fn set_rebal_param(
&mut self,
alpha_num: f32,
alpha_denom: f32
) -> Result<(), SgError>
The original scapegoat tree paper’s alpha, a
, can be chosen in the range 0.5 <= a < 1.0
.
a
tunes how “aggressively” the data structure self-balances.
It controls the trade-off between total rebuild time and maximum height guarantees.
-
As
a
approaches0.5
, the tree will rebalance more often. Ths means slower insertions, but faster lookups and deletions.- An
a
equal to0.5
means a tree that always maintains a perfect balance (e.g.“complete” binary tree, at all times).
- An
-
As
a
approaches1.0
, the tree will rebalance less often. This means quicker insertions, but slower lookups and deletions.- If
a
reached1.0
, it’d mean a tree that never rebalances.
- If
Returns Err
if 0.5 <= alpha_num / alpha_denom < 1.0
isn’t true
(invalid a
, out of range).
Examples
use scapegoat::SgSet;
let mut set: SgSet<isize, 10> = SgSet::new();
// Set 2/3, e.g. `a = 0.666...` (it's default value).
assert!(set.set_rebal_param(2.0, 3.0).is_ok());
sourcepub fn rebal_param(&self) -> (f32, f32)
pub fn rebal_param(&self) -> (f32, f32)
Get the current rebalance parameter, alpha, as a tuple of (alpha_numerator, alpha_denominator)
.
See the corresponding setter method for more details.
Examples
use scapegoat::SgSet;
let mut set: SgSet<isize, 10> = SgSet::new();
// Set 2/3, e.g. `a = 0.666...` (it's default value).
assert!(set.set_rebal_param(2.0, 3.0).is_ok());
// Get the currently set value
assert_eq!(set.rebal_param(), (2.0, 3.0));
sourcepub fn capacity(&self) -> usize
pub fn capacity(&self) -> usize
Total capacity, e.g. maximum number of set elements.
Examples
use scapegoat::SgSet;
let mut set: SgSet<i32, 10> = SgSet::new();
assert!(set.capacity() == 10)
sourcepub fn append(&mut self, other: &mut SgSet<T, N>) where
T: Ord,
pub fn append(&mut self, other: &mut SgSet<T, N>) where
T: Ord,
Moves all elements from other
into self
, leaving other
empty.
Examples
use scapegoat::SgSet;
let mut a = SgSet::<_, 10>::new();
a.insert(1);
a.insert(2);
a.insert(3);
let mut b = SgSet::<_, 10>::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));
sourcepub fn try_append(&mut self, other: &mut SgSet<T, N>) -> Result<(), SgError>
pub fn try_append(&mut self, other: &mut SgSet<T, N>) -> Result<(), SgError>
Attempts to move all elements from other
into self
, leaving other
empty.
Examples
use core::iter::FromIterator;
use scapegoat::{SgSet, SgError};
let mut a = SgSet::<_, 10>::new();
assert!(a.try_insert(1).is_ok());
assert!(a.try_insert(2).is_ok());
assert!(a.try_insert(3).is_ok());
let mut b = SgSet::<_, 10>::new();
assert!(b.try_insert(3).is_ok()); // Overwrite previous
assert!(b.try_insert(4).is_ok());
assert!(b.try_insert(5).is_ok());
// Successful append
assert!(a.try_append(&mut b).is_ok());
// Elements moved
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));
// Fill remaining capacity
let mut key = 6;
while a.len() < a.capacity() {
assert!(a.try_insert(key).is_ok());
key += 1;
}
// Full
assert!(a.is_full());
// More data
let mut c = SgSet::<_, 10>::from_iter([11, 12]);
let mut d = SgSet::<_, 10>::from_iter([1, 2]);
// Cannot append new pairs
assert_eq!(a.try_append(&mut c), Err(SgError::StackCapacityExceeded));
// Can still replace existing pairs
assert!(a.try_append(&mut d).is_ok());
sourcepub fn insert(&mut self, value: T) -> bool where
T: Ord,
pub fn insert(&mut self, value: T) -> bool where
T: Ord,
Adds a value to the set.
If the set did not have this value present, true
is returned.
If the set did have this value present, false
is returned, and the entry is overwritten.
Examples
use scapegoat::SgSet;
let mut set = SgSet::<_, 10>::new();
assert_eq!(set.insert(2), true);
assert_eq!(set.insert(2), false);
assert_eq!(set.len(), 1);
sourcepub fn try_insert(&mut self, value: T) -> Result<bool, SgError> where
T: Ord,
pub fn try_insert(&mut self, value: T) -> Result<bool, SgError> where
T: Ord,
Adds a value to the set.
Returns Err
if the operation can’t be completed, else the Ok
contains:
true
if the set did not have this value present.false
if the set did have this value present (and that old entry is overwritten).
Examples
use scapegoat::{SgSet, SgError};
let mut set = SgSet::<_, 10>::new();
// Add a new element
assert_eq!(set.try_insert(2), Ok(true));
// Replace existing element
assert_eq!(set.try_insert(2), Ok(false));
assert_eq!(set.len(), 1);
// Fill remaining capacity
let mut elem = 3;
while set.len() < set.capacity() {
assert!(set.try_insert(elem).is_ok());
elem += 1;
}
// Full
assert!(set.is_full());
// Cannot insert new element
assert_eq!(set.try_insert(elem), Err(SgError::StackCapacityExceeded));
// Can still replace existing element
assert_eq!(set.try_insert(elem - 1), Ok(false));
sourcepub fn try_extend<I: ExactSizeIterator + IntoIterator<Item = T>>(
&mut self,
iter: I
) -> Result<(), SgError>
pub fn try_extend<I: ExactSizeIterator + IntoIterator<Item = T>>(
&mut self,
iter: I
) -> Result<(), SgError>
Attempt to extend a collection with the contents of an iterator.
Examples
use core::iter::FromIterator;
use scapegoat::{SgSet, SgError};
let mut a = SgSet::<_, 2>::new();
let mut b = SgSet::<_, 3>::from_iter([1, 2, 3]);
let mut c = SgSet::<_, 2>::from_iter([1, 2]);
// Too big
assert_eq!(a.try_extend(b.into_iter()), Err(SgError::StackCapacityExceeded));
// Fits
assert!(a.try_extend(c.into_iter()).is_ok());
Note
There is no TryExtend
trait in core
/std
.
sourcepub fn try_from_iter<I: ExactSizeIterator + IntoIterator<Item = T>>(
iter: I
) -> Result<Self, SgError>
pub fn try_from_iter<I: ExactSizeIterator + IntoIterator<Item = T>>(
iter: I
) -> Result<Self, SgError>
Attempt conversion from an iterator.
Will fail if iterator length exceeds u16::MAX
.
Examples
use scapegoat::{SgSet, SgError};
const CAPACITY_1: usize = 1_000;
assert!(SgSet::<_, CAPACITY_1>::try_from_iter((0..CAPACITY_1)).is_ok());
const CAPACITY_2: usize = (u16::MAX as usize) + 1;
assert_eq!(
SgSet::<_, CAPACITY_2>::try_from_iter((0..CAPACITY_2)),
Err(SgError::MaximumCapacityExceeded)
);
Note
There is no TryFromIterator
trait in core
/std
.
sourcepub fn iter(&self) -> Iter<'_, T, N>ⓘNotable traits for Iter<'a, T, N>impl<'a, T: Ord + Default, const N: usize> Iterator for Iter<'a, T, N> type Item = &'a T;
pub fn iter(&self) -> Iter<'_, T, N>ⓘNotable traits for Iter<'a, T, N>impl<'a, T: Ord + Default, const N: usize> Iterator for Iter<'a, T, N> type Item = &'a T;
Gets an iterator that visits the values in the SgSet
in ascending order.
Examples
use scapegoat::SgSet;
let set: SgSet<usize, 3> = [1, 2, 3].iter().cloned().collect();
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 scapegoat::SgSet;
let set: SgSet<usize, 3> = [3, 1, 2].iter().cloned().collect();
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);
sourcepub fn remove<Q>(&mut self, value: &Q) -> bool where
T: Borrow<Q> + Ord,
Q: Ord + ?Sized,
pub fn remove<Q>(&mut self, value: &Q) -> bool where
T: Borrow<Q> + Ord,
Q: Ord + ?Sized,
Removes a value from the set. Returns whether the value was present in the set.
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 scapegoat::SgSet;
let mut set = SgSet::<_, 10>::new();
set.insert(2);
assert_eq!(set.remove(&2), true);
assert_eq!(set.remove(&2), false);
sourcepub fn split_off<Q>(&mut self, value: &Q) -> SgSet<T, N> where
T: Borrow<Q> + Ord,
Q: Ord + ?Sized,
pub fn split_off<Q>(&mut self, value: &Q) -> SgSet<T, N> where
T: Borrow<Q> + Ord,
Q: Ord + ?Sized,
Splits the collection into two at the given value. Returns everything after the given value, including the value.
Examples
use scapegoat::SgSet;
let mut a = SgSet::<_, 5>::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));
sourcepub fn replace(&mut self, value: T) -> Option<T> where
T: Ord,
pub fn replace(&mut self, value: T) -> Option<T> where
T: Ord,
Adds a value to the set, replacing the existing value, if any, that is equal to the given one. Returns the replaced value.
Examples
use scapegoat::SgSet;
let mut set = SgSet::<_, 10>::new();
set.insert(Vec::<i32>::new());
assert_eq!(set.get(&[][..]).unwrap().capacity(), 0);
set.replace(Vec::with_capacity(10));
assert_eq!(set.get(&[][..]).unwrap().capacity(), 10);
sourcepub fn try_replace(&mut self, value: T) -> Result<Option<T>, SgError> where
T: Ord,
pub fn try_replace(&mut self, value: T) -> Result<Option<T>, SgError> where
T: Ord,
Attempts to add a value to the set, replacing the existing value, if any, that is equal to the given one. Returns the replaced value.
sourcepub fn take<Q>(&mut self, value: &Q) -> Option<T> where
T: Borrow<Q> + Ord,
Q: Ord + ?Sized,
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.
Examples
use scapegoat::SgSet;
let mut set: SgSet<_, 10> = [1, 2, 3].iter().cloned().collect();
assert_eq!(set.take(&2), Some(2));
assert_eq!(set.take(&2), None);
sourcepub fn retain<F>(&mut self, f: F) where
T: Ord,
F: FnMut(&T) -> bool,
pub fn retain<F>(&mut self, f: F) where
T: Ord,
F: FnMut(&T) -> bool,
Retains only the elements specified by the predicate.
In other words, remove all elements e
such that f(&e)
returns false
.
The elements are visited in ascending order.
Examples
use scapegoat::SgSet;
let xs = [1, 2, 3, 4, 5, 6];
let mut set: SgSet<i32, 10> = xs.iter().cloned().collect();
// Keep only the even numbers.
set.retain(|&k| k % 2 == 0);
assert!(set.iter().eq([2, 4, 6].iter()));
sourcepub fn get<Q>(&self, value: &Q) -> Option<&T> where
T: Borrow<Q> + Ord,
Q: Ord + ?Sized,
pub fn get<Q>(&self, value: &Q) -> Option<&T> where
T: Borrow<Q> + Ord,
Q: Ord + ?Sized,
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.
Examples
use scapegoat::SgSet;
let set: SgSet<_, 10> = [1, 2, 3].iter().cloned().collect();
assert_eq!(set.get(&2), Some(&2));
assert_eq!(set.get(&4), None);
sourcepub fn clear(&mut self)
pub fn clear(&mut self)
Clears the set, removing all values.
Examples
use scapegoat::SgSet;
let mut v = SgSet::<_, 10>::new();
v.insert(1);
v.clear();
assert!(v.is_empty());;
sourcepub fn contains<Q>(&self, value: &Q) -> bool where
T: Borrow<Q> + Ord,
Q: Ord + ?Sized,
pub fn contains<Q>(&self, value: &Q) -> bool where
T: Borrow<Q> + Ord,
Q: Ord + ?Sized,
Returns true
if the set contains a 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 scapegoat::SgSet;
let set: SgSet<_, 10> = [1, 2, 3].iter().cloned().collect();
assert_eq!(set.contains(&1), true);
assert_eq!(set.contains(&4), false);
sourcepub fn first(&self) -> Option<&T> where
T: Ord,
pub fn first(&self) -> Option<&T> where
T: Ord,
Returns a reference to the first/minium value in the set, if any.
Examples
use scapegoat::SgSet;
let mut set = SgSet::<_, 2>::new();
assert_eq!(set.first(), None);
set.insert(1);
assert_eq!(set.first(), Some(&1));
set.insert(2);
assert_eq!(set.first(), Some(&1));
sourcepub fn pop_first(&mut self) -> Option<T> where
T: Ord,
pub fn pop_first(&mut self) -> Option<T> where
T: Ord,
Removes the first value from the set and returns it, if any. The first value is the minimum value that was in the set.
Examples
use scapegoat::SgSet;
let mut set = SgSet::<_, 10>::new();
set.insert(1);
while let Some(n) = set.pop_first() {
assert_eq!(n, 1);
}
assert!(set.is_empty());
sourcepub fn last(&self) -> Option<&T> where
T: Ord,
pub fn last(&self) -> Option<&T> where
T: Ord,
Returns the last/maximum value in the set, if any.
Examples
use scapegoat::SgSet;
let mut set = SgSet::<_, 10>::new();
assert_eq!(set.first(), None);
set.insert(1);
assert_eq!(set.last(), Some(&1));
set.insert(2);
assert_eq!(set.last(), Some(&2));
sourcepub fn pop_last(&mut self) -> Option<T> where
T: Ord,
pub fn pop_last(&mut self) -> Option<T> where
T: Ord,
Removes the last value from the set and returns it, if any. The last value is the maximum value that was in the set.
Examples
use scapegoat::SgSet;
let mut set = SgSet::<_, 10>::new();
set.insert(1);
while let Some(n) = set.pop_last() {
assert_eq!(n, 1);
}
assert!(set.is_empty());
sourcepub fn len(&self) -> usize
pub fn len(&self) -> usize
Returns the number of elements in the set.
Examples
use scapegoat::SgSet;
let mut v = SgSet::<_, 10>::new();
assert_eq!(v.len(), 0);
v.insert(1);
assert_eq!(v.len(), 1);
sourcepub fn range<K, R>(&self, range: R) -> Range<'_, T, N>ⓘNotable traits for Range<'a, T, N>impl<'a, T: Ord + Default, const N: usize> Iterator for Range<'a, T, N> type Item = &'a T;
where
K: Ord + ?Sized,
T: Borrow<K> + Ord,
R: RangeBounds<K>,
pub fn range<K, R>(&self, range: R) -> Range<'_, T, N>ⓘNotable traits for Range<'a, T, N>impl<'a, T: Ord + Default, const N: usize> Iterator for Range<'a, T, N> type Item = &'a 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 scapegoat::SgSet;
use core::ops::Bound::Included;
let mut set = SgSet::<_, 5>::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());
sourcepub fn difference(&self, other: &SgSet<T, N>) -> Difference<'_, T, N>ⓘNotable traits for Difference<'a, T, N>impl<'a, T: Ord + Default, const N: usize> Iterator for Difference<'a, T, N> type Item = &'a T;
where
T: Ord,
pub fn difference(&self, other: &SgSet<T, N>) -> Difference<'_, T, N>ⓘNotable traits for Difference<'a, T, N>impl<'a, T: Ord + Default, const N: usize> Iterator for Difference<'a, T, N> type Item = &'a T;
where
T: Ord,
Returns an iterator over values representing set difference, e.g., values in self
but not in other
, in ascending order.
Examples
use scapegoat::SgSet;
let mut a = SgSet::<_, 10>::new();
a.insert(1);
a.insert(2);
let mut b = SgSet::<_, 10>::new();
b.insert(2);
b.insert(3);
let diff: Vec<_> = a.difference(&b).cloned().collect();
assert_eq!(diff, [1]);
sourcepub fn symmetric_difference<'a>(
&'a self,
other: &'a SgSet<T, N>
) -> SymmetricDifference<'_, T, N>ⓘNotable traits for SymmetricDifference<'a, T, N>impl<'a, T: Ord + Default, const N: usize> Iterator for SymmetricDifference<'a, T, N> type Item = &'a T;
where
T: Ord,
pub fn symmetric_difference<'a>(
&'a self,
other: &'a SgSet<T, N>
) -> SymmetricDifference<'_, T, N>ⓘNotable traits for SymmetricDifference<'a, T, N>impl<'a, T: Ord + Default, const N: usize> Iterator for SymmetricDifference<'a, T, N> type Item = &'a T;
where
T: Ord,
Returns an iterator over values representing symmetric set difference, e.g., values in self
or other
but not both, in ascending order.
Examples
use scapegoat::SgSet;
let mut a = SgSet::<_, 10>::new();
a.insert(1);
a.insert(2);
let mut b = SgSet::<_, 10>::new();
b.insert(2);
b.insert(3);
let sym_diff: Vec<_> = a.symmetric_difference(&b).cloned().collect();
assert_eq!(sym_diff, [1, 3]);
Warning
At present, this function may panic if set capacity N
exceeds 2048
.
The issue is that this function’s returned iterator needs to be 2 * N
long to support disjoint sets,
but without unstable feature(generic_const_exprs)
we can’t compute 2 * N
.
So we use 4096
instead of 2 * N
as a workaround, hence N
should be <= 2048
to ensure no panic.
An N > 2048
may or may not panic, depending on the size of sets’ intersection.
sourcepub fn intersection(&self, other: &SgSet<T, N>) -> Intersection<'_, T, N>ⓘNotable traits for Intersection<'a, T, N>impl<'a, T: Ord + Default, const N: usize> Iterator for Intersection<'a, T, N> type Item = &'a T;
where
T: Ord,
pub fn intersection(&self, other: &SgSet<T, N>) -> Intersection<'_, T, N>ⓘNotable traits for Intersection<'a, T, N>impl<'a, T: Ord + Default, const N: usize> Iterator for Intersection<'a, T, N> type Item = &'a T;
where
T: Ord,
Returns an iterator over values representing set intersection, e.g., values in both self
and other
, in ascending order.
Examples
use scapegoat::SgSet;
let mut a = SgSet::<_, 10>::new();
a.insert(1);
a.insert(2);
let mut b = SgSet::<_, 10>::new();
b.insert(2);
b.insert(3);
let intersection: Vec<_> = a.intersection(&b).cloned().collect();
assert_eq!(intersection, [2]);
sourcepub fn union<'a>(&'a self, other: &'a SgSet<T, N>) -> Union<'_, T, N>ⓘNotable traits for Union<'a, T, N>impl<'a, T: Ord + Default, const N: usize> Iterator for Union<'a, T, N> type Item = &'a T;
where
T: Ord,
pub fn union<'a>(&'a self, other: &'a SgSet<T, N>) -> Union<'_, T, N>ⓘNotable traits for Union<'a, T, N>impl<'a, T: Ord + Default, const N: usize> Iterator for Union<'a, T, N> type Item = &'a T;
where
T: Ord,
Returns an iterator over values representing set union, e.g., values in self
or other
, in ascending order.
Examples
use scapegoat::SgSet;
let mut a = SgSet::<_, 10>::new();
a.insert(1);
let mut b = SgSet::<_, 10>::new();
b.insert(2);
let union: Vec<_> = a.union(&b).cloned().collect();
assert_eq!(union, [1, 2]);
Warning
At present, this function may panic if set capacity N
exceeds 2048
.
The issue is that this function’s returned iterator needs to be 2 * N
long to support disjoint sets,
but without unstable feature(generic_const_exprs)
we can’t compute 2 * N
.
So we use 4096
instead of 2 * N
as a workaround, hence N
should be <= 2048
to ensure no panic.
An N > 2048
may or may not panic, depending on the size of sets’ intersection.
sourcepub fn is_empty(&self) -> bool
pub fn is_empty(&self) -> bool
Returns true
if the set contains no elements.
Examples
use scapegoat::SgSet;
let mut v = SgSet::<_, 10>::new();
assert!(v.is_empty());
v.insert(1);
assert!(!v.is_empty());
sourcepub fn is_full(&self) -> bool
pub fn is_full(&self) -> bool
Returns true
if the set’s capacity is filled.
Examples
use scapegoat::SgSet;
let mut a = SgSet::<_, 2>::new();
a.insert(1);
assert!(!a.is_full());
a.insert(2);
assert!(a.is_full());
sourcepub fn is_disjoint(&self, other: &SgSet<T, N>) -> bool where
T: Ord,
pub fn is_disjoint(&self, other: &SgSet<T, N>) -> bool where
T: Ord,
Returns true
if self
has no elements in common with other (empty intersection).
Examples
use scapegoat::SgSet;
let a: SgSet<_, 10> = [1, 2, 3].iter().cloned().collect();
let mut b = SgSet::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);
sourcepub fn is_subset(&self, other: &SgSet<T, N>) -> bool where
T: Ord,
pub fn is_subset(&self, other: &SgSet<T, N>) -> bool where
T: Ord,
Returns true
if self
is a subset of other
, e.g., other
contains at least all the values in self
.
Examples
use scapegoat::SgSet;
let sup: SgSet<_, 10> = [1, 2, 3].iter().cloned().collect();
let mut set = SgSet::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);
sourcepub fn is_superset(&self, other: &SgSet<T, N>) -> bool where
T: Ord,
pub fn is_superset(&self, other: &SgSet<T, N>) -> bool where
T: Ord,
Returns true
if self
is a superset of other
, e.g., self
contains at least all the values in other
.
Examples
use scapegoat::SgSet;
let sub: SgSet<_, 3> = [1, 2].iter().cloned().collect();
let mut set = SgSet::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);
Trait Implementations
sourceimpl<T: Ord + Default + Clone, const N: usize> BitAnd<&'_ SgSet<T, N>> for &SgSet<T, N>
impl<T: Ord + Default + Clone, const N: usize> BitAnd<&'_ SgSet<T, N>> for &SgSet<T, N>
sourcefn bitand(self, rhs: &SgSet<T, N>) -> SgSet<T, N>
fn bitand(self, rhs: &SgSet<T, N>) -> SgSet<T, N>
Returns the intersection of self
and rhs
as a new SgSet<T, N>
.
Examples
use scapegoat::SgSet;
let a: SgSet<_, 10> = vec![1, 2, 3].into_iter().collect();
let b: SgSet<_, 10> = vec![2, 3, 4].into_iter().collect();
let result = &a & &b;
let result_vec: Vec<_> = result.into_iter().collect();
assert_eq!(result_vec, [2, 3]);
sourceimpl<T: Ord + Default + Clone, const N: usize> BitOr<&'_ SgSet<T, N>> for &SgSet<T, N>
impl<T: Ord + Default + Clone, const N: usize> BitOr<&'_ SgSet<T, N>> for &SgSet<T, N>
sourcefn bitor(self, rhs: &SgSet<T, N>) -> SgSet<T, N>
fn bitor(self, rhs: &SgSet<T, N>) -> SgSet<T, N>
Returns the union of self
and rhs
as a new SgSet<T, N>
.
Examples
use scapegoat::SgSet;
let a: SgSet<_, 10> = vec![1, 2, 3].into_iter().collect();
let b: SgSet<_, 10> = vec![3, 4, 5].into_iter().collect();
let result = &a | &b;
let result_vec: Vec<_> = result.into_iter().collect();
assert_eq!(result_vec, [1, 2, 3, 4, 5]);
sourceimpl<T: Ord + Default + Clone, const N: usize> BitXor<&'_ SgSet<T, N>> for &SgSet<T, N>
impl<T: Ord + Default + Clone, const N: usize> BitXor<&'_ SgSet<T, N>> for &SgSet<T, N>
sourcefn bitxor(self, rhs: &SgSet<T, N>) -> SgSet<T, N>
fn bitxor(self, rhs: &SgSet<T, N>) -> SgSet<T, N>
Returns the symmetric difference of self
and rhs
as a new SgSet<T, N>
.
Examples
use scapegoat::SgSet;
let a: SgSet<_, 10> = vec![1, 2, 3].into_iter().collect();
let b: SgSet<_, 10> = vec![2, 3, 4].into_iter().collect();
let result = &a ^ &b;
let result_vec: Vec<_> = result.into_iter().collect();
assert_eq!(result_vec, [1, 4]);
sourceimpl<'a, T, const N: usize> Extend<&'a T> for SgSet<T, N> where
T: 'a + Ord + Default + Copy,
impl<'a, T, const N: usize> Extend<&'a T> for SgSet<T, N> where
T: 'a + Ord + Default + Copy,
sourcefn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I)
fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I)
Extends a collection with the contents of an iterator. Read more
sourcefn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)Extends a collection with exactly one element.
sourcefn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)Reserves capacity in a collection for the given number of additional elements. Read more
sourceimpl<T, const N: usize> Extend<T> for SgSet<T, N> where
T: Ord + Default,
impl<T, const N: usize> Extend<T> for SgSet<T, N> where
T: Ord + Default,
sourcefn extend<TreeIter: IntoIterator<Item = T>>(&mut self, iter: TreeIter)
fn extend<TreeIter: IntoIterator<Item = T>>(&mut self, iter: TreeIter)
Extends a collection with the contents of an iterator. Read more
sourcefn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one
)Extends a collection with exactly one element.
sourcefn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one
)Reserves capacity in a collection for the given number of additional elements. Read more
sourceimpl<T, const N: usize> From<[T; N]> for SgSet<T, N> where
T: Ord + Default,
impl<T, const N: usize> From<[T; N]> for SgSet<T, N> where
T: Ord + Default,
sourcefn from(arr: [T; N]) -> Self
fn from(arr: [T; N]) -> Self
use scapegoat::SgSet;
let set1 = SgSet::from([1, 2, 3, 4]);
let set2: SgSet<_, 4> = [1, 2, 3, 4].into();
assert_eq!(set1, set2);
Warning
TryFrom
isn’t implemented because it would collide with the blanket implementation.
See this open GitHub issue from 2018,
this is a known Rust limitation that should be fixed via specialization in the future.
sourceimpl<T, const N: usize> FromIterator<T> for SgSet<T, N> where
T: Ord + Default,
impl<T, const N: usize> FromIterator<T> for SgSet<T, N> where
T: Ord + Default,
sourcefn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self
Creates a value from an iterator. Read more
sourceimpl<T: Ord + Ord + Default, const N: usize> Ord for SgSet<T, N>
impl<T: Ord + Ord + Default, const N: usize> Ord for SgSet<T, N>
sourceimpl<T: PartialOrd + Ord + Default, const N: usize> PartialOrd<SgSet<T, N>> for SgSet<T, N>
impl<T: PartialOrd + Ord + Default, const N: usize> PartialOrd<SgSet<T, N>> for SgSet<T, N>
sourcefn partial_cmp(&self, other: &SgSet<T, N>) -> Option<Ordering>
fn partial_cmp(&self, other: &SgSet<T, N>) -> Option<Ordering>
This method returns an ordering between self
and other
values if one exists. Read more
1.0.0 · sourcefn lt(&self, other: &Rhs) -> bool
fn lt(&self, other: &Rhs) -> bool
This method tests less than (for self
and other
) and is used by the <
operator. Read more
1.0.0 · sourcefn le(&self, other: &Rhs) -> bool
fn le(&self, other: &Rhs) -> bool
This method tests less than or equal to (for self
and other
) and is used by the <=
operator. Read more
sourceimpl<T: Ord + Default + Clone, const N: usize> Sub<&'_ SgSet<T, N>> for &SgSet<T, N>
impl<T: Ord + Default + Clone, const N: usize> Sub<&'_ SgSet<T, N>> for &SgSet<T, N>
sourcefn sub(self, rhs: &SgSet<T, N>) -> SgSet<T, N>
fn sub(self, rhs: &SgSet<T, N>) -> SgSet<T, N>
Returns the difference of self
and rhs
as a new SgSet<T, N>
.
Examples
use scapegoat::SgSet;
let a: SgSet<_, 10> = vec![1, 2, 3].into_iter().collect();
let b: SgSet<_, 10> = vec![3, 4, 5].into_iter().collect();
let result = &a - &b;
let result_vec: Vec<_> = result.into_iter().collect();
assert_eq!(result_vec, [1, 2]);
impl<T: Eq + Ord + Default, const N: usize> Eq for SgSet<T, N>
impl<T: Ord + Default, const N: usize> StructuralEq for SgSet<T, N>
impl<T: Ord + Default, const N: usize> StructuralPartialEq for SgSet<T, N>
Auto Trait Implementations
impl<T, const N: usize> RefUnwindSafe for SgSet<T, N> where
T: RefUnwindSafe,
impl<T, const N: usize> Send for SgSet<T, N> where
T: Send,
impl<T, const N: usize> Sync for SgSet<T, N> where
T: Sync,
impl<T, const N: usize> Unpin for SgSet<T, N> where
T: Unpin,
impl<T, const N: usize> UnwindSafe for SgSet<T, N> where
T: UnwindSafe,
Blanket Implementations
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcepub fn borrow_mut(&mut self) -> &mut T
pub fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more