Lines
88.55 %
Functions
61.16 %
Branches
100 %
use std::cmp::Ordering;
use std::fmt;
use std::marker::PhantomData;
use std::slice::Iter;
use itertools::Itertools;
#[macro_export]
macro_rules! vecset {
() => {
$crate::VecSet::new()
};
($elem:expr; $n:expr) => {{
let mut __set = $crate::VecSet::new();
let __count: usize = $n;
if __count > 0 {
__set.insert($elem);
}
__set
}};
($($x:expr),+ $(,)?) => {{
$( let _ = __set.insert($x); )*
///
/// A set that is internally represented by a sorted vector. Mostly useful for
/// a compact representation of sets that are not changed often.
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct VecSet<T> {
/// The internal storage with the invariant that the array is sorted.
sorted_array: Vec<T>,
impl<T: Ord> VecSet<T> {
/// Creates a new, empty VecSet.
pub fn new() -> Self {
Self {
sorted_array: Vec::new(),
/// Creates a VecSet from the given vector without assuming anything of the given vector.
pub fn from_vec(mut vec: Vec<T>) -> Self {
vec.sort_unstable();
vec.dedup();
Self { sorted_array: vec }
/// Returns the capacity of the set.
pub fn capacity(&self) -> usize {
self.sorted_array.capacity()
/// Returns true iff the set contains the given element.
pub fn contains(&self, element: &T) -> bool {
self.sorted_array.binary_search(element).is_ok()
/// Clears the set, removing all elements.
pub fn clear(&mut self) {
self.sorted_array.clear();
/// Retains only the elements specified by the predicate.
pub fn retain<F>(&mut self, mut f: F)
where
F: FnMut(&T) -> bool,
{
// Removing elements does not change the order.
self.sorted_array.retain(|e| f(e));
/// Returns true iff this set is a subset of the other set.
pub fn is_subset(&self, other: &VecSet<T>) -> bool {
let mut self_iter = self.sorted_array.iter();
let mut other_iter = other.sorted_array.iter();
// Traverse both sets in order, checking that all elements of self are in other.
let mut self_next = self_iter.next();
let mut other_next = other_iter.next();
while let Some(self_val) = self_next {
match other_next {
Some(other_val) => {
match self_val.cmp(other_val) {
Ordering::Equal => {
self_next = self_iter.next();
other_next = other_iter.next();
Ordering::Greater => other_next = other_iter.next(),
Ordering::Less => return false, // self_val is smaller, not in other
None => return false, // other is exhausted
true
/// Returns a new set only containing the given element.
pub fn singleton(element: T) -> Self {
sorted_array: vec![element],
/// Returns true iff the set is empty.
pub fn is_empty(&self) -> bool {
self.sorted_array.is_empty()
/// Returns the difference of this set and the other set.
pub fn difference<'a>(&'a self, other: &'a VecSet<T>) -> impl Iterator<Item = &'a T> {
Difference::<'a, T, _> {
self_iter: self.sorted_array.iter(),
other_iter: other.sorted_array.iter(),
other_next: None,
marker: PhantomData,
/// Inserts the given element into the set, returns true iff the element was
/// inserted.
pub fn insert(&mut self, element: T) -> bool {
// Finds the location where to insert the element to keep the array sorted.
if let Err(position) = self.sorted_array.binary_search(&element) {
self.sorted_array.insert(position, element);
return true;
false
/// Extends this set with the elements from the given iterator, returns true iff at least one element was inserted.
pub fn extend<'a, I: IntoIterator<Item = &'a T>>(&mut self, iter: I) -> bool
T: Clone + 'a,
let mut inserted = false;
for element in iter {
if self.insert(element.clone()) {
inserted = true;
inserted
/// Returns an iterator over the elements in the set, they are yielded in sorted order.
pub fn iter(&self) -> impl Iterator<Item = &T> {
self.sorted_array.iter()
/// Returns the number of elements in the set.
pub fn len(&self) -> usize {
self.sorted_array.len()
/// Consumes the set and returns a vector with the elements in sorted order.
pub fn to_vec(self) -> Vec<T> {
self.sorted_array
impl<T: Ord> FromIterator<T> for VecSet<T> {
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
Self::from_vec(iter.into_iter().collect())
/// A lazy iterator that yields the difference of two sets. The elements are yielded in sorted order.
struct Difference<'a, T, I> {
self_iter: I,
other_iter: I,
other_next: Option<&'a T>,
marker: PhantomData<&'a T>,
impl<'a, T, I> Iterator for Difference<'a, T, I>
I: Iterator<Item = &'a T>,
T: Ord + PartialEq,
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
if self.other_next.is_none() {
self.other_next = self.other_iter.next();
for self_val in self.self_iter.by_ref() {
loop {
match self.other_next {
break;
Ordering::Greater => self.other_next = self.other_iter.next(),
Ordering::Less => return Some(self_val), // self_val is smaller, yield it
None => return Some(self_val), // other is exhausted, yield remaining elements of self
None
impl<T: Ord> Default for VecSet<T> {
fn default() -> Self {
Self::new()
impl<'a, T> IntoIterator for &'a VecSet<T> {
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Self::IntoIter {
impl<T: fmt::Debug> fmt::Debug for VecSet<T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{{{:?}}}", self.sorted_array.iter().format(", "))
#[cfg(test)]
mod tests {
use rand::RngExt;
use merc_utilities::random_test;
use crate::VecSet;
#[test]
fn test_random_vecset_difference() {
random_test(100, |rng| {
let size = rng.random_range(0..20);
let size2 = rng.random_range(0..20);
let vec1: Vec<u32> = (0..size).map(|_| rng.random_range(0..100)).collect();
let vec2: Vec<u32> = (0..size2).map(|_| rng.random_range(0..100)).collect();
let set1 = VecSet::from_vec(vec1.clone());
let set2 = VecSet::from_vec(vec2.clone());
println!("left: {:?}", set1);
println!("right: {:?}", set2);
let difference: Vec<u32> = set1.difference(&set2).cloned().collect();
let expected_difference: Vec<u32> = vec1
.into_iter()
.filter(|x| !vec2.contains(x))
.sorted()
.dedup()
.collect();
assert_eq!(difference, expected_difference);
})