bendns' repos / btree_multiset
[no description]
Diffstat
-rw-r--r--Cargo.toml2
-rw-r--r--src/lib.rs80
2 files changed, 45 insertions, 37 deletions
diff --git a/Cargo.toml b/Cargo.toml
index 479068b..d7e3eeb 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -10,4 +10,4 @@ keywords = ["btree", "multiset"]
rust-version = "1.95.0"
[dependencies]
-smolvec = "1.0.0"
+smallvec = { version = "1.15.1", features = ["const_generics", "specialization"] }
diff --git a/src/lib.rs b/src/lib.rs
index 18fa5e3..e6bda7e 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -6,13 +6,17 @@ use std::collections::btree_map::{self, Entry};
use std::fmt::Debug;
use std::iter::FlatMap;
-use smolvec::SmolVec;
+use smallvec::SmallVec;
#[derive(Clone)]
/// Like a btree set, but with duplicates.
/// Currently immutable cause i havent thought about it yet.
-pub struct BTreeMultiset<T: ToK, A: Allocator + Clone = Global> {
- inner: BTreeMap<T::K, SmolVec<T>, A>,
+pub struct BTreeMultiset<
+ T: ToK,
+ const N: usize = 4,
+ A: Allocator + Clone = Global,
+> {
+ inner: BTreeMap<T::K, SmallVec<[T; N]>, A>,
}
pub trait ToK {
type K;
@@ -36,37 +40,39 @@ impl<T: Clone> ToK for Vec<T> {
self.clone()
}
}
-impl<T: Debug + ToK<K: Ord>, A: Allocator + Clone> Debug
- for BTreeMultiset<T, A>
+impl<const N: usize, T: Debug + ToK<K: Ord>, A: Allocator + Clone> Debug
+ for BTreeMultiset<T, N, A>
{
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_set().entries(self.iter()).finish()
}
}
-impl<T: ToK<K: Ord>, A: Allocator + Clone> IntoIterator
- for BTreeMultiset<T, A>
+impl<const N: usize, T: ToK<K: Ord>, A: Allocator + Clone> IntoIterator
+ for BTreeMultiset<T, N, A>
{
type Item = T;
type IntoIter = FlatMap<
- btree_map::IntoIter<T::K, SmolVec<T>, A>,
- SmolVec<T>,
- fn((T::K, SmolVec<T>)) -> SmolVec<T>,
+ btree_map::IntoIter<<T as ToK>::K, SmallVec<[T; N]>, A>,
+ SmallVec<[T; N]>,
+ fn((<T as ToK>::K, SmallVec<[T; N]>)) -> SmallVec<[T; N]>,
>;
fn into_iter(self) -> Self::IntoIter {
self.inner.into_iter().flat_map(|x| x.1)
}
}
-impl<T: ToK<K: Ord>> FromIterator<T> for BTreeMultiset<T> {
+impl<const N: usize, T: ToK<K: Ord>> FromIterator<T>
+ for BTreeMultiset<T, N>
+{
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
let mut x = Self::default();
x.extend(iter);
x
}
}
-impl<T: ToK<K: Ord>, A: Allocator + Clone> Extend<T>
- for BTreeMultiset<T, A>
+impl<const N: usize, T: ToK<K: Ord>, A: Allocator + Clone> Extend<T>
+ for BTreeMultiset<T, N, A>
{
#[inline]
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
@@ -80,45 +86,47 @@ impl<T: ToK<K: Ord>, A: Allocator + Clone> Extend<T>
self.insert(x);
}
}
-impl<T: ToK<K: Ord>> BTreeMultiset<T, Global> {
+impl<const N: usize, T: ToK<K: Ord>> BTreeMultiset<T, N> {
pub fn new() -> Self {
- Self { inner: BTreeMap::new_in(Global) }
+ Self { inner: BTreeMap::new() }
}
}
-impl<T: ToK<K: Ord>> Default for BTreeMultiset<T, Global> {
+impl<const N: usize, T: ToK<K: Ord>> Default for BTreeMultiset<T, N> {
fn default() -> Self {
Self::new()
}
}
-type Iter<'a, K, T> = FlatMap<
- btree_map::Iter<'a, K, SmolVec<T>>,
- &'a SmolVec<T>,
- fn((&'a K, &'a SmolVec<T>)) -> &'a SmolVec<T>,
+type Iter<'a, const N: usize, T> = FlatMap<
+ btree_map::Iter<'a, <T as ToK>::K, SmallVec<[T; N]>>,
+ &'a SmallVec<[T; N]>,
+ fn((&'a <T as ToK>::K, &'a SmallVec<[T; N]>)) -> &'a SmallVec<[T; N]>,
>;
-type Range<'a, K, T> = FlatMap<
- btree_map::Range<'a, K, SmolVec<T>>,
- &'a SmolVec<T>,
- fn((&'a K, &'a SmolVec<T>)) -> &'a SmolVec<T>,
+type Range<'a, const N: usize, T> = FlatMap<
+ btree_map::Range<'a, <T as ToK>::K, SmallVec<[T; N]>>,
+ &'a SmallVec<[T; N]>,
+ fn((&'a <T as ToK>::K, &'a SmallVec<[T; N]>)) -> &'a SmallVec<[T; N]>,
>;
-impl<T: ToK, A: Allocator + Clone> BTreeMultiset<T, A> {
- pub fn into_inner(self) -> BTreeMap<T::K, SmolVec<T>, A> {
+impl<const N: usize, T: ToK, A: Allocator + Clone> BTreeMultiset<T, N, A> {
+ pub fn into_inner(self) -> BTreeMap<T::K, SmallVec<[T; N]>, A> {
self.inner
}
}
-impl<T: ToK<K: Ord>, A: Allocator + Clone> BTreeMultiset<T, A> {
+impl<const N: usize, T: ToK<K: Ord>, A: Allocator + Clone>
+ BTreeMultiset<T, N, A>
+{
pub fn new_in(a: A) -> Self {
Self { inner: BTreeMap::new_in(a) }
}
/// Gets an iterator that visits the elements in the [`BTreeMultiset`] in ascending order.
/// Similar to `range(..)`.
- pub fn iter<'a>(&'a self) -> Iter<'a, T::K, T> {
+ pub fn iter(&'_ self) -> Iter<'_, N, T> {
self.inner.iter().flat_map(|x| x.1)
}
/// Adds a value to the multi set.
pub fn insert(&mut self, t: T) -> bool {
match self.inner.entry(t.to_key()) {
Entry::Vacant(vacant_entry) => {
- vacant_entry.insert(SmolVec::from_iter([t]));
+ vacant_entry.insert(SmallVec::from_iter([t]));
false
}
Entry::Occupied(occupied_entry) => {
@@ -139,10 +147,10 @@ impl<T: ToK<K: Ord>, A: Allocator + Clone> BTreeMultiset<T, A> {
///
/// Panics if range `start > end`.
/// Panics if range `start == end` and both bounds are `Excluded`.
- pub fn range<'a>(
- &'a self,
+ pub fn range(
+ &'_ self,
r: impl std::ops::RangeBounds<T::K>,
- ) -> Range<'a, T::K, T> {
+ ) -> Range<'_, N, T> {
self.inner.range(r).flat_map(|x| x.1)
}
@@ -150,16 +158,16 @@ impl<T: ToK<K: Ord>, A: Allocator + Clone> BTreeMultiset<T, A> {
// &'a mut self,
// r: impl std::ops::RangeBounds<K>,
// ) -> FlatMap<
- // RangeMut<'a, K, SmolVec<T>>,
- // &'a mut SmolVec<T>,
- // fn((&'a K, &'a mut SmolVec<T>)) -> &'a mut SmolVec<T>,
+ // RangeMut<'a, K, SmallVec<T>>,
+ // &'a mut SmallVec<T>,
+ // fn((&'a K, &'a mut SmallVec<T>)) -> &'a mut SmallVec<T>,
// > {
// self.inner.range_mut(r).flat_map(|x| x.1)
// }
}
#[test]
fn works() {
- let mut x = BTreeMultiset::new();
+ let mut x: BTreeMultiset<i32> = BTreeMultiset::new();
x.insert(4);
x.insert(3);