stacked_set/
cons.rs

1use core::{borrow::Borrow, fmt::Debug};
2
3use crate::StackedSet;
4
5/// `Cons list`-like implementation of [`StackedSet`]
6///
7/// On my machine, worst time to check for existence is about 2ns/item
8pub struct ConsSet<'tail, Item>(ConsRepr<'tail, Item>);
9
10// In case you are wondering why is this type private - intend is to hide enum variants from public interface
11enum ConsRepr<'tail, Item> {
12    Nil,
13    Con {
14        this: Option<Item>,
15        tail: &'tail ConsSet<'tail, Item>,
16    },
17}
18
19impl<Item: PartialEq + Debug> Debug for ConsSet<'_, Item> {
20    #[inline]
21    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
22        let mut list = f.debug_list();
23        for item in self.iter() {
24            list.entry(item);
25        }
26        list.finish()
27    }
28}
29
30impl<Item: PartialEq> StackedSet for ConsSet<'_, Item> {
31    type Item = Item;
32
33    #[inline]
34    fn empty() -> Self {
35        ConsSet(ConsRepr::Nil)
36    }
37
38    #[inline]
39    fn contains_ref(&self, item: &Self::Item) -> bool {
40        match &self.0 {
41            ConsRepr::Nil => false,
42            ConsRepr::Con { this, tail } => {
43                if this.as_ref().is_some_and(|this| this == item.borrow()) {
44                    true
45                } else {
46                    tail.contains(item)
47                }
48            }
49        }
50    }
51
52    type Shorten<'new>
53        = ConsSet<'new, Item>
54    where
55        Self: 'new;
56
57    #[inline]
58    fn extend(&mut self, new_item: Item) -> Self::Shorten<'_> {
59        if self.contains_ref(&new_item) {
60            ConsSet(ConsRepr::Con {
61                this: None,
62                tail: self,
63            })
64        } else {
65            ConsSet(ConsRepr::Con {
66                this: Some(new_item),
67                tail: self,
68            })
69        }
70    }
71
72    #[inline]
73    fn fork(&mut self) -> Self::Shorten<'_> {
74        ConsSet(ConsRepr::Con {
75            this: None,
76            tail: self,
77        })
78    }
79
80    type IntoIter<'i>
81        = ConsIter<'i, Item>
82    where
83        Self: 'i;
84
85    #[inline]
86    fn iter(&self) -> Self::IntoIter<'_> {
87        ConsIter(&self.0)
88    }
89}
90
91#[allow(missing_debug_implementations)]
92pub struct ConsIter<'l, Item>(&'l ConsRepr<'l, Item>);
93
94impl<'l, Item> Iterator for ConsIter<'l, Item> {
95    type Item = &'l Item;
96
97    #[inline]
98    fn next(&mut self) -> Option<Self::Item> {
99        loop {
100            match core::mem::replace(&mut self.0, &ConsRepr::Nil) {
101                ConsRepr::Nil => break None,
102                ConsRepr::Con {
103                    this: Some(item),
104                    tail,
105                } => {
106                    self.0 = &tail.0;
107                    break Some(item);
108                }
109                ConsRepr::Con { this: None, tail } => {
110                    self.0 = &tail.0;
111                }
112            }
113        }
114    }
115}
stacked_set/cons.rs

stacked_set/
cons.rs
