[no description]
| -rw-r--r-- | src/lib.rs | 65 |
1 files changed, 39 insertions, 26 deletions
@@ -11,34 +11,44 @@ use smolvec::SmolVec; #[derive(Clone)] /// Like a btree set, but with duplicates. /// Currently immutable cause i havent thought about it yet. -pub struct BTreeMultiset<K, T, F, A: Allocator + Clone> { - inner: BTreeMap<K, SmolVec<T>, A>, - f: F, +pub struct BTreeMultiset<T: ToK, A: Allocator + Clone = Global> { + inner: BTreeMap<T::K, SmolVec<T>, A>, } -impl<K: Ord, T: Debug, F: Fn(&T) -> K, A: Allocator + Clone> Debug - for BTreeMultiset<K, T, F, A> +pub trait ToK { + type K; + fn to_key(&self) -> Self::K; +} +impl<T: Clone> ToK for T { + type K = T; + + fn to_key(&self) -> Self::K { + self.clone() + } +} +impl<T: Debug + ToK<K: Ord>, A: Allocator + Clone> Debug + for BTreeMultiset<T, A> { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { f.debug_set().entries(self.iter()).finish() } } -impl<K, T, F: Fn(&T) -> K, A: Allocator + Clone> IntoIterator - for BTreeMultiset<K, T, F, A> +impl<T: ToK<K: Ord>, A: Allocator + Clone> IntoIterator + for BTreeMultiset<T, A> { type Item = T; type IntoIter = FlatMap< - btree_map::IntoIter<K, SmolVec<T>, A>, + btree_map::IntoIter<T::K, SmolVec<T>, A>, SmolVec<T>, - fn((K, SmolVec<T>)) -> SmolVec<T>, + fn((T::K, SmolVec<T>)) -> SmolVec<T>, >; fn into_iter(self) -> Self::IntoIter { self.inner.into_iter().flat_map(|x| x.1) } } -impl<K: Ord, T, F: Fn(&T) -> K, A: Allocator + Clone> Extend<T> - for BTreeMultiset<K, T, F, A> +impl<T: ToK<K: Ord>, A: Allocator + Clone> Extend<T> + for BTreeMultiset<T, A> { #[inline] fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { @@ -52,9 +62,14 @@ impl<K: Ord, T, F: Fn(&T) -> K, A: Allocator + Clone> Extend<T> self.insert(x); } } -impl<K: Ord, T, F: Fn(&T) -> K> BTreeMultiset<K, T, F, Global> { - pub fn new(f: F) -> Self { - Self { inner: BTreeMap::new_in(Global), f } +impl<T: ToK<K: Ord>> BTreeMultiset<T, Global> { + pub fn new() -> Self { + Self { inner: BTreeMap::new_in(Global) } + } +} +impl<T: ToK<K: Ord>> Default for BTreeMultiset<T, Global> { + fn default() -> Self { + Self::new() } } type Iter<'a, K, T> = FlatMap< @@ -67,25 +82,23 @@ type Range<'a, K, T> = FlatMap< &'a SmolVec<T>, fn((&'a K, &'a SmolVec<T>)) -> &'a SmolVec<T>, >; -impl<K, T, F, A: Allocator + Clone> BTreeMultiset<K, T, F, A> { - pub fn into_inner(self) -> BTreeMap<K, SmolVec<T>, A> { +impl<T: ToK, A: Allocator + Clone> BTreeMultiset<T, A> { + pub fn into_inner(self) -> BTreeMap<T::K, SmolVec<T>, A> { self.inner } } -impl<K: Ord, T, F: Fn(&T) -> K, A: Allocator + Clone> - BTreeMultiset<K, T, F, A> -{ - pub fn new_in(f: F, a: A) -> Self { - Self { inner: BTreeMap::new_in(a), f } +impl<T: ToK<K: Ord>, A: Allocator + Clone> BTreeMultiset<T, 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, K, T> { + pub fn iter<'a>(&'a self) -> Iter<'a, T::K, 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((self.f)(&t)) { + match self.inner.entry(t.to_key()) { Entry::Vacant(vacant_entry) => { vacant_entry.insert(SmolVec::from_iter([t])); false @@ -110,8 +123,8 @@ impl<K: Ord, T, F: Fn(&T) -> K, A: Allocator + Clone> /// Panics if range `start == end` and both bounds are `Excluded`. pub fn range<'a>( &'a self, - r: impl std::ops::RangeBounds<K>, - ) -> Range<'a, K, T> { + r: impl std::ops::RangeBounds<T::K>, + ) -> Range<'a, T::K, T> { self.inner.range(r).flat_map(|x| x.1) } @@ -128,7 +141,7 @@ impl<K: Ord, T, F: Fn(&T) -> K, A: Allocator + Clone> } #[test] fn works() { - let mut x = BTreeMultiset::new(|x: &u32| *x); + let mut x = BTreeMultiset::new(); x.insert(4); x.insert(3); |