stacked_set/
collection.rs

1use core::{borrow::Borrow, fmt::Debug, ops::Deref};
2
3use crate::StackedSet;
4
5/// Kind of interface a "collection" should expose for [`StackedSet`] implementation to be built on top of it.
6///
7/// To get a [`StackedSet`] implementor, just wrap your collection into [`CollectionSet`]. Original collection will still be available via `Deref`/`Borrow`/`AsRef`.
8pub trait SetCollection {
9    /// Element type stored in the collection.
10    type Item;
11
12    /// A some sort of memory that can be used to remove the item back. Some implementations (like `Vec` may want to make this a unit type, if the item to remove is somehow known through collection structure).
13    type ExtendMemory;
14
15    /// Creates an empty collection.
16    fn new() -> Self;
17
18    /// Extends the collection, creating instance of `ExtendMemory` to later remove this element. Note that implementation should not care about item previously existing, as [`CollectionSet`] checks for `new_item` not being present in the collection prior to this call.
19    fn extend(&mut self, new_item: Self::Item) -> Self::ExtendMemory;
20
21    /// Checks if the collection contains a certain element. Only accepts in a core reference, check [`SetCollection::contains`] method if more flexibility is needed.
22    fn contains_ref(&self, item: &Self::Item) -> bool;
23
24    /// Checks if the collection contains a certain element.
25    #[inline]
26    fn contains(&self, item: impl Borrow<Self::Item>) -> bool {
27        self.contains_ref(item.borrow())
28    }
29
30    /// Removes an element from the collection represented by [`SetCollection::ExtendMemory`] instance.
31    fn remove(&mut self, present_item: Self::ExtendMemory);
32
33    /// Type of iterator over item references.
34    type IntoIter<'i>: Iterator<Item = &'i Self::Item>
35    where
36        Self: 'i;
37
38    /// Creates iterator over item references.
39    fn iter(&self) -> Self::IntoIter<'_>;
40}
41
42/// [`SetCollection`]-based implementation.
43///
44/// On my machine, worst time to check for existence is about 0.6ns/item.
45pub struct CollectionSet<'l, Collection: SetCollection>(CollectionRepr<'l, Collection>);
46
47// In case you are wondering why is this type private - intend is to hide enum variants from public interface
48enum CollectionRepr<'l, Collection: SetCollection> {
49    Nil(Collection),
50    Fork(&'l mut Collection),
51    Extend(&'l mut Collection, Collection::ExtendMemory),
52    Moved,
53}
54
55impl<Collection: SetCollection> CollectionSet<'_, Collection> {
56    /// A private method for convenient collection mutation
57    #[inline]
58    pub(self) fn c_mut(&mut self) -> &mut Collection {
59        match &mut self.0 {
60            CollectionRepr::Nil(c) => c,
61            CollectionRepr::Fork(c) | CollectionRepr::Extend(c, _) => c,
62            CollectionRepr::Moved => unreachable!("Cannot call instance method after drop"),
63        }
64    }
65}
66
67impl<Collection: SetCollection> Deref for CollectionSet<'_, Collection> {
68    type Target = Collection;
69
70    #[inline]
71    fn deref(&self) -> &Self::Target {
72        match &self.0 {
73            CollectionRepr::Nil(c) => c,
74            CollectionRepr::Fork(c) | CollectionRepr::Extend(c, _) => c,
75            CollectionRepr::Moved => unreachable!("Cannot call instance method after drop"),
76        }
77    }
78}
79
80impl<Collection: SetCollection> Borrow<Collection> for CollectionSet<'_, Collection> {
81    #[inline]
82    fn borrow(&self) -> &Collection {
83        self
84    }
85}
86
87impl<Collection: SetCollection> AsRef<Collection> for CollectionSet<'_, Collection> {
88    #[inline]
89    fn as_ref(&self) -> &Collection {
90        self
91    }
92}
93
94impl<Collection: SetCollection + Debug> Debug for CollectionSet<'_, Collection> {
95    #[inline]
96    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
97        <Collection as core::fmt::Debug>::fmt(&**self, f)
98    }
99}
100
101impl<Collection: SetCollection> Drop for CollectionSet<'_, Collection> {
102    #[inline]
103    fn drop(&mut self) {
104        let repr = core::mem::replace(&mut self.0, CollectionRepr::Moved);
105        if let CollectionRepr::Extend(c, m) = repr {
106            c.remove(m);
107        }
108    }
109}
110
111impl<Collection: SetCollection> StackedSet for CollectionSet<'_, Collection> {
112    type Item = Collection::Item;
113
114    #[inline]
115    fn empty() -> Self {
116        Self(CollectionRepr::Nil(Collection::new()))
117    }
118
119    #[inline]
120    fn contains_ref(&self, item: &Self::Item) -> bool {
121        Collection::contains_ref(self, item)
122    }
123
124    type Shorten<'new>
125        = CollectionSet<'new, Collection>
126    where
127        Self: 'new;
128
129    #[inline]
130    fn extend(&mut self, new_item: Self::Item) -> Self::Shorten<'_> {
131        if self.contains_ref(&new_item) {
132            CollectionSet(CollectionRepr::Fork(self.c_mut()))
133        } else {
134            let m = self.c_mut().extend(new_item);
135            CollectionSet(CollectionRepr::Extend(self.c_mut(), m))
136        }
137    }
138
139    #[inline]
140    fn fork(&mut self) -> Self::Shorten<'_> {
141        CollectionSet(CollectionRepr::Fork(self.c_mut()))
142    }
143
144    type IntoIter<'i>
145        = Collection::IntoIter<'i>
146    where
147        Self: 'i;
148
149    #[inline]
150    fn iter(&self) -> Self::IntoIter<'_> {
151        let c: &Collection = self;
152        c.iter()
153    }
154}
stacked_set/collection.rs

stacked_set/
collection.rs
