#![doc = include_str!("../README.md")]
#![no_std]
extern crate alloc;
use alloc::vec::Vec;
use core::{
borrow::Borrow,
hash::{Hash, Hasher},
ops::{Deref, Index, RangeBounds},
slice::SliceIndex,
};
use smallvec::SmallVec;
#[cfg(feature = "serde")]
use serde::{Deserialize, Deserializer, Serialize, Serializer};
#[derive(Clone, Eq, PartialOrd, Ord, Debug)]
pub struct SmallSortedSet<T, const N: usize> {
vec: SmallVec<[T; N]>,
}
impl<T, const N: usize> SmallSortedSet<T, N> {
#[must_use]
#[inline]
pub fn new() -> Self {
Self {
vec: SmallVec::new(),
}
}
#[must_use]
#[inline]
pub fn with_capacity(capacity: usize) -> Self {
Self {
vec: SmallVec::with_capacity(capacity),
}
}
#[inline]
pub const fn as_vec(&self) -> &SmallVec<[T; N]> {
&self.vec
}
#[must_use]
#[inline]
pub fn into_vec(self) -> SmallVec<[T; N]> {
self.vec
}
#[inline]
pub fn reserve(&mut self, additional: usize) {
self.vec.reserve(additional);
}
#[inline]
pub fn reserve_exact(&mut self, additional: usize) {
self.vec.reserve_exact(additional);
}
#[inline]
pub fn shrink_to_fit(&mut self) {
self.vec.shrink_to_fit();
}
#[inline]
pub fn capacity(&self) -> usize {
self.vec.capacity()
}
#[inline]
pub fn len(&self) -> usize {
self.vec.len()
}
#[inline]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
#[inline]
pub fn remove_at(&mut self, index: usize) -> T {
self.vec.remove(index)
}
#[inline]
pub fn try_remove_at(&mut self, index: usize) -> Option<T> {
if index >= self.vec.len() {
return None;
}
Some(self.vec.remove(index))
}
#[inline]
pub fn pop(&mut self) -> Option<T> {
self.vec.pop()
}
#[inline]
pub fn clear(&mut self) {
self.vec.clear();
}
#[inline]
pub fn truncate(&mut self, len: usize) {
self.vec.truncate(len);
}
#[inline]
pub fn drain(&mut self, range: impl RangeBounds<usize>) -> smallvec::Drain<'_, [T; N]> {
self.vec.drain(range)
}
#[inline]
pub fn retain(&mut self, mut f: impl FnMut(&T) -> bool) {
self.vec.retain(|t| f(t));
}
#[inline]
pub unsafe fn insert_at(&mut self, index: usize, element: T) {
self.vec.insert(index, element);
}
}
impl<T: Ord, const N: usize> SmallSortedSet<T, N> {
#[must_use]
pub fn from_unsorted(mut vec: SmallVec<[T; N]>) -> Self {
vec.sort_unstable();
vec.dedup();
Self { vec }
}
#[must_use]
#[inline]
pub fn from_unsorted_vec(vec: Vec<T>) -> Self {
Self::from_unsorted(vec.into())
}
#[must_use]
#[inline]
pub fn contains(&self, element: &T) -> bool {
self.vec.binary_search(element).is_ok()
}
pub fn insert(&mut self, element: T) -> Result<usize, usize> {
match self.vec.binary_search(&element) {
Ok(i) => Err(i),
Err(i) => {
self.vec.insert(i, element);
Ok(i)
}
}
}
pub fn remove(&mut self, element: &T) -> Result<usize, usize> {
let result = self.vec.binary_search(element);
if let Ok(i) = result {
self.vec.remove(i);
}
result
}
}
impl<T: Ord + Clone, const N: usize> SmallSortedSet<T, N> {
#[inline]
pub fn from_unsorted_slice(slice: &[T]) -> Self {
Self::from_unsorted(slice.into())
}
}
impl<T, const N: usize> Default for SmallSortedSet<T, N> {
#[inline]
fn default() -> Self {
Self::new()
}
}
impl<T: Ord, const N: usize> From<SmallVec<[T; N]>> for SmallSortedSet<T, N> {
#[inline]
fn from(unsorted: SmallVec<[T; N]>) -> Self {
Self::from_unsorted(unsorted)
}
}
impl<T: Ord, const N: usize> From<Vec<T>> for SmallSortedSet<T, N> {
#[inline]
fn from(unsorted: Vec<T>) -> Self {
Self::from_unsorted_vec(unsorted)
}
}
impl<T: Ord + Clone, const N: usize> From<&[T]> for SmallSortedSet<T, N> {
#[inline]
fn from(unsorted: &[T]) -> Self {
Self::from_unsorted_slice(unsorted)
}
}
impl<T, const N: usize> Deref for SmallSortedSet<T, N> {
type Target = [T];
#[inline]
fn deref(&self) -> &[T] {
&self.vec
}
}
impl<T, const N: usize> AsRef<[T]> for SmallSortedSet<T, N> {
#[inline]
fn as_ref(&self) -> &[T] {
&self.vec
}
}
impl<T, const N: usize> AsRef<SmallVec<[T; N]>> for SmallSortedSet<T, N> {
#[inline]
fn as_ref(&self) -> &SmallVec<[T; N]> {
&self.vec
}
}
impl<T, const N: usize> Borrow<[T]> for SmallSortedSet<T, N> {
#[inline]
fn borrow(&self) -> &[T] {
&self.vec
}
}
impl<T, I: SliceIndex<[T]>, const N: usize> Index<I> for SmallSortedSet<T, N> {
type Output = I::Output;
#[inline]
fn index(&self, index: I) -> &Self::Output {
self.vec.index(index)
}
}
impl<A: Ord, const N: usize> Extend<A> for SmallSortedSet<A, N> {
fn extend<T: IntoIterator<Item = A>>(&mut self, iter: T) {
self.vec.extend(iter);
self.vec.sort();
self.vec.dedup();
}
}
impl<A: Ord, const N: usize> FromIterator<A> for SmallSortedSet<A, N> {
fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self {
let vec = SmallVec::from_iter(iter);
Self::from_unsorted(vec)
}
}
impl<T, const N: usize> IntoIterator for SmallSortedSet<T, N> {
type Item = T;
type IntoIter = smallvec::IntoIter<[T; N]>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
self.vec.into_iter()
}
}
impl<'a, T, const N: usize> IntoIterator for &'a SmallSortedSet<T, N> {
type Item = &'a T;
type IntoIter = core::slice::Iter<'a, T>;
#[inline]
fn into_iter(self) -> Self::IntoIter {
self.vec.iter()
}
}
impl<T, U, const TN: usize, const UN: usize> PartialEq<SmallSortedSet<U, UN>>
for SmallSortedSet<T, TN>
where
T: PartialEq<U>,
{
#[inline]
fn eq(&self, other: &SmallSortedSet<U, UN>) -> bool {
self.vec == other.vec
}
}
impl<T: Hash, const N: usize> Hash for SmallSortedSet<T, N> {
#[inline]
fn hash<H: Hasher>(&self, state: &mut H) {
self.vec.hash(state);
}
}
#[cfg(feature = "serde")]
#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
impl<T, const N: usize> Serialize for SmallSortedSet<T, N>
where
T: Serialize,
{
fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
self.vec.serialize(serializer)
}
}
#[cfg(feature = "serde")]
#[cfg_attr(docsrs, doc(cfg(feature = "serde")))]
impl<'de, T, const N: usize> Deserialize<'de> for SmallSortedSet<T, N>
where
T: Deserialize<'de> + Ord,
{
fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
SmallVec::deserialize(deserializer).map(Self::from_unsorted)
}
}
#[cfg(test)]
mod tests {
use core::assert_matches;
use smallvec::smallvec;
const TEST_INLINE_SIZE: usize = 6;
type SmallVec = smallvec::SmallVec<[i32; TEST_INLINE_SIZE]>;
type SmallSortedSet = super::SmallSortedSet<i32, TEST_INLINE_SIZE>;
#[test]
fn from_unsorted() {
let unsorted = smallvec![5, 0, 2, 4, 3, 1, 5, 2, 0, 3, 4, 5, 1, 2, 4, 0, 3];
let sorted: SmallVec = smallvec![0, 1, 2, 3, 4, 5];
let a = SmallSortedSet::from_unsorted(unsorted);
let mut b = SmallSortedSet::new();
b.extend(sorted);
assert_eq!(a, b);
}
#[test]
fn insert() {
let mut vec = SmallSortedSet::new();
assert_matches!(vec.insert(5), Result::Ok(0));
assert_matches!(vec.insert(0), Result::Ok(0));
assert_matches!(vec.insert(2), Result::Ok(1));
assert_matches!(vec.insert(4), Result::Ok(2));
assert_matches!(vec.insert(3), Result::Ok(2));
assert_matches!(vec.insert(1), Result::Ok(1));
assert_matches!(vec.insert(5), Result::Err(5));
assert_matches!(vec.insert(2), Result::Err(2));
assert_matches!(vec.insert(0), Result::Err(0));
assert_matches!(vec.insert(3), Result::Err(3));
assert_matches!(vec.insert(4), Result::Err(4));
assert_matches!(vec.insert(5), Result::Err(5));
assert_matches!(vec.insert(1), Result::Err(1));
assert_matches!(vec.insert(2), Result::Err(2));
assert_matches!(vec.insert(4), Result::Err(4));
assert_matches!(vec.insert(0), Result::Err(0));
assert_matches!(vec.insert(3), Result::Err(3));
}
#[test]
fn remove() {
let mut vec = SmallSortedSet::new();
let sorted: SmallVec = smallvec![0, 1, 2, 3, 4, 5];
vec.extend(sorted);
assert_matches!(vec.remove(&5), Result::Ok(5));
assert_matches!(vec.remove(&5), Result::Err(5));
assert_matches!(vec.remove(&0), Result::Ok(0));
assert_matches!(vec.remove(&0), Result::Err(0));
assert_matches!(vec.remove(&2), Result::Ok(1));
assert_matches!(vec.remove(&2), Result::Err(1));
assert_matches!(vec.remove(&4), Result::Ok(2));
assert_matches!(vec.remove(&4), Result::Err(2));
assert_matches!(vec.remove(&3), Result::Ok(1));
assert_matches!(vec.remove(&3), Result::Err(1));
assert_matches!(vec.remove(&1), Result::Ok(0));
assert_matches!(vec.remove(&1), Result::Err(0));
assert_matches!(vec.remove(&0), Result::Err(0));
assert_matches!(vec.remove(&1), Result::Err(0));
assert_matches!(vec.remove(&2), Result::Err(0));
assert_matches!(vec.remove(&3), Result::Err(0));
assert_matches!(vec.remove(&4), Result::Err(0));
assert_matches!(vec.remove(&5), Result::Err(0));
}
#[test]
fn extend() {
let sorted: SmallVec = smallvec![1, 2, 4, 5, 8, 9];
let mut vec = SmallSortedSet::new();
vec.extend(sorted.iter().copied());
assert_eq!(vec.as_vec(), &sorted);
let duplicates: SmallVec = smallvec![
8, 1, 4, 2, 9, 5, 4, 9, 8, 2, 1, 5, 4, 8, 9, 1, 5, 2, 4, 2, 8, 5, 9
];
vec.extend(duplicates);
assert_eq!(vec.as_vec(), &sorted);
let new: SmallVec = smallvec![10, 3, 0, 6, 0, 7, 11, 3, 6];
vec.extend(new);
let expected: SmallVec = smallvec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11];
assert_eq!(vec.as_vec(), &expected);
}
}