embed_collections/
various.rs

1//! Various - A small-list optimization container for efficient parameter passing.
2//!
3//! `Various<T>` optimizing for the common case of a single element (use Option initially).
4//! It's storage can be seamless grow when more elements pushed, using [SegList](crate::seg_list),
5//! more efficient for CPU cache-line (compared to LinkedList), and produce less memory fragment (compared to `Vec`).
6//!
7//! # NOTE:
8//!
9//! It does not support random access, only sequential read and write.
10//!
11//! # Example
12//!
13//! ```rust
14//! use embed_collections::various::Various;
15//!
16//! // Create an empty Various
17//! let mut values = Various::new();
18//!
19//! // Push a single element (no allocation)
20//! values.push(42);
21//! assert_eq!(values.len(), 1);
22//! assert_eq!(values.first(), Some(&42));
23//!
24//! // Push more elements (transitions to SegList internally)
25//! values.push(100);
26//! values.push(200);
27//! assert_eq!(values.len(), 3);
28//!
29//! // Iterate over elements
30//! let sum: i32 = values.iter().sum();
31//! assert_eq!(sum, 342);
32//!
33//! // Pop elements from the back
34//! assert_eq!(values.pop(), Some(200));
35//! assert_eq!(values.pop(), Some(100));
36//! assert_eq!(values.pop(), Some(42));
37//! assert_eq!(values.pop(), None);
38//!
39//! // Create from a single value
40//! let single = Various::from("hello");
41//! assert_eq!(single.first(), Some(&"hello"));
42//!
43//! // Efficient for function parameter passing
44//! fn process_items(items: &Various<i32>) -> i32 {
45//!     items.iter().sum()
46//! }
47//!
48//! let items = Various::from(10);
49//! assert_eq!(process_items(&items), 10);
50//! ```
51
52use crate::seg_list::SegList;
53use core::fmt;
54
55pub struct Various<T> {
56    inner: VariousInner<T>,
57}
58
59enum VariousInner<T> {
60    One(Option<T>),
61    More(SegList<T>),
62}
63
64macro_rules! match_iter {
65    ($self: expr, $iter_type: tt, $f: tt $($m: tt)*) =>{
66        match $self.inner {
67            VariousInner::One($($m)* s)=>$iter_type::One(s.$f()),
68            VariousInner::More($($m)* s)=>$iter_type::More(s.$f()),
69        }
70    }
71}
72
73macro_rules! match_call {
74    ($self: expr, $cls: tt, $call: tt) => {
75        match $self {
76            $cls::One(i) => i.$call(),
77            $cls::More(i) => i.$call(),
78        }
79    };
80}
81
82impl<T> Default for Various<T> {
83    fn default() -> Self {
84        Self::new()
85    }
86}
87
88impl<T> Various<T> {
89    #[inline]
90    pub fn new() -> Self {
91        Self { inner: VariousInner::One(None) }
92    }
93
94    #[inline]
95    pub fn from(item: T) -> Self {
96        Self { inner: VariousInner::One(Some(item)) }
97    }
98
99    #[inline]
100    pub fn is_empty(&self) -> bool {
101        match &self.inner {
102            VariousInner::One(i) => i.is_none(),
103            VariousInner::More(i) => i.is_empty(),
104        }
105    }
106
107    #[inline]
108    pub fn len(&self) -> usize {
109        match &self.inner {
110            VariousInner::One(i) => {
111                if i.is_none() {
112                    0
113                } else {
114                    1
115                }
116            }
117            VariousInner::More(i) => i.len(),
118        }
119    }
120
121    /// push element to the tail
122    #[inline]
123    pub fn push(&mut self, new_item: T) {
124        match self.inner {
125            VariousInner::More(ref mut s) => {
126                s.push(new_item);
127            }
128            VariousInner::One(ref mut s) => {
129                if s.is_none() {
130                    s.replace(new_item);
131                } else {
132                    let mut l = SegList::new();
133                    l.push(s.take().unwrap());
134                    l.push(new_item);
135                    self.inner = VariousInner::More(l);
136                }
137            }
138        }
139    }
140
141    /// pop element from the tail
142    #[inline]
143    pub fn pop(&mut self) -> Option<T> {
144        match self.inner {
145            VariousInner::More(ref mut s) => s.pop(),
146            VariousInner::One(ref mut s) => s.take(),
147        }
148    }
149
150    #[inline]
151    pub fn iter<'a>(&'a self) -> VariousIter<'a, T> {
152        match_iter!(self, VariousIter, iter ref)
153    }
154
155    pub fn iter_mut<'a>(&'a mut self) -> VariousIterMut<'a, T> {
156        match_iter!(self, VariousIterMut, iter_mut ref mut)
157    }
158
159    #[inline]
160    pub fn first(&self) -> Option<&T> {
161        match self.inner {
162            VariousInner::One(ref s) => s.as_ref(),
163            VariousInner::More(ref s) => s.iter().next(),
164        }
165    }
166
167    #[inline]
168    pub fn last(&self) -> Option<&T> {
169        match self.inner {
170            VariousInner::More(ref s) => s.last(),
171            VariousInner::One(ref s) => s.as_ref(),
172        }
173    }
174
175    pub fn last_mut(&mut self) -> Option<&mut T> {
176        match self.inner {
177            VariousInner::More(ref mut s) => s.last_mut(),
178            VariousInner::One(ref mut s) => s.as_mut(),
179        }
180    }
181
182    #[inline]
183    pub fn take(&mut self) -> Self {
184        use core::mem;
185        Various { inner: mem::replace(&mut self.inner, VariousInner::One(None)) }
186    }
187}
188
189impl<T> IntoIterator for Various<T> {
190    type Item = T;
191
192    type IntoIter = VariousIntoIter<T>;
193
194    fn into_iter(self) -> VariousIntoIter<T> {
195        match_iter!(self, VariousIntoIter, into_iter)
196    }
197}
198
199impl<'a, T> IntoIterator for &'a Various<T> {
200    type Item = &'a T;
201
202    type IntoIter = VariousIter<'a, T>;
203
204    fn into_iter(self) -> VariousIter<'a, T> {
205        match_iter!(self, VariousIter, iter ref)
206    }
207}
208
209pub enum VariousIter<'a, T> {
210    One(core::option::Iter<'a, T>),
211    More(crate::seg_list::SegListIter<'a, T>),
212}
213
214impl<'a, T> core::iter::Iterator for VariousIter<'a, T> {
215    type Item = &'a T;
216
217    fn next(&mut self) -> Option<Self::Item> {
218        match_call!(self, VariousIter, next)
219    }
220}
221
222pub enum VariousIterMut<'a, T> {
223    One(core::option::IterMut<'a, T>),
224    More(crate::seg_list::SegListIterMut<'a, T>),
225}
226
227impl<'a, T> core::iter::Iterator for VariousIterMut<'a, T> {
228    type Item = &'a mut T;
229
230    fn next(&mut self) -> Option<Self::Item> {
231        match_call!(self, VariousIterMut, next)
232    }
233}
234
235pub enum VariousIntoIter<T> {
236    One(core::option::IntoIter<T>),
237    More(crate::seg_list::SegListDrain<T>),
238}
239
240impl<T> core::iter::Iterator for VariousIntoIter<T> {
241    type Item = T;
242
243    fn next(&mut self) -> Option<Self::Item> {
244        match_call!(self, VariousIntoIter, next)
245    }
246}
247
248impl<T: fmt::Debug> fmt::Debug for Various<T> {
249    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
250        match &self.inner {
251            VariousInner::One(s) => s.fmt(f),
252            VariousInner::More(s) => s.fmt(f),
253        }
254    }
255}
256
257#[cfg(test)]
258mod tests {
259
260    use super::*;
261
262    #[test]
263    fn test_one() {
264        let mut s = Various::new();
265        s.push(1);
266        assert_eq!(s.len(), 1);
267        for i in &s {
268            assert_eq!(*i, 1);
269        }
270        assert_eq!(Some(1), s.pop());
271        assert_eq!(s.len(), 0);
272        if (&s).into_iter().next().is_some() {
273            unreachable!();
274        }
275    }
276
277    #[test]
278    fn test_cap_0() {
279        let mut s = Various::new();
280        s.push(1);
281        assert_eq!(s.len(), 1);
282        for i in &s {
283            assert_eq!(*i, 1);
284        }
285        s.push(2);
286        s.push(3);
287        assert_eq!(s.len(), 3);
288        let mut total = 0;
289        for i in &s {
290            total += *i;
291        }
292        assert_eq!(total, 6);
293        for i in s.iter_mut() {
294            *i += 1;
295        }
296        let mut total = 0;
297        for i in &s {
298            total += *i;
299        }
300        assert_eq!(total, 9);
301        assert_eq!(s.pop(), Some(4));
302        let mut total = 0;
303        for i in s {
304            total += i;
305        }
306        assert_eq!(total, 5);
307    }
308
309    #[test]
310    fn test_more() {
311        let mut s = Various::new();
312        s.push(1);
313        s.push(2);
314        s.push(3);
315        assert_eq!(s.len(), 3);
316        let mut total = 0;
317        for i in &s {
318            total += *i;
319        }
320        assert_eq!(total, 6);
321        for i in s.iter_mut() {
322            *i += 1;
323        }
324        let mut total = 0;
325        for i in &s {
326            total += *i;
327        }
328        assert_eq!(total, 9);
329        assert_eq!(s.pop(), Some(4));
330        let mut total = 0;
331        for i in s {
332            total += i;
333        }
334        assert_eq!(total, 5);
335    }
336}
embed_collections/various.rs

embed_collections/
various.rs
