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
64impl<T> Default for Various<T> {
65    fn default() -> Self {
66        Self::new()
67    }
68}
69
70impl<T> Various<T> {
71    #[inline]
72    pub fn new() -> Self {
73        Self { inner: VariousInner::One(None) }
74    }
75
76    #[inline]
77    pub fn from(item: T) -> Self {
78        Self { inner: VariousInner::One(Some(item)) }
79    }
80
81    #[inline]
82    pub fn is_empty(&self) -> bool {
83        match &self.inner {
84            VariousInner::One(i) => i.is_none(),
85            VariousInner::More(i) => i.is_empty(),
86        }
87    }
88
89    #[inline]
90    pub fn len(&self) -> usize {
91        match &self.inner {
92            VariousInner::One(i) => {
93                if i.is_none() {
94                    0
95                } else {
96                    1
97                }
98            }
99            VariousInner::More(i) => i.len(),
100        }
101    }
102
103    /// push element to the tail
104    #[inline]
105    pub fn push(&mut self, new_item: T) {
106        match self.inner {
107            VariousInner::More(ref mut s) => {
108                s.push(new_item);
109            }
110            VariousInner::One(ref mut s) => {
111                if s.is_none() {
112                    s.replace(new_item);
113                } else {
114                    let mut l = SegList::new();
115                    l.push(s.take().unwrap());
116                    l.push(new_item);
117                    self.inner = VariousInner::More(l);
118                }
119            }
120        }
121    }
122
123    /// pop element from the tail
124    #[inline]
125    pub fn pop(&mut self) -> Option<T> {
126        match self.inner {
127            VariousInner::More(ref mut s) => s.pop(),
128            VariousInner::One(ref mut s) => s.take(),
129        }
130    }
131
132    #[inline]
133    pub fn iter(&self) -> VariousIter<'_, T> {
134        let inner = match &self.inner {
135            VariousInner::One(s) => VariousIterInner::One(s.iter()),
136            VariousInner::More(s) => VariousIterInner::More(s.iter()),
137        };
138        VariousIter { inner }
139    }
140
141    pub fn iter_mut(&mut self) -> VariousIterMut<'_, T> {
142        let inner = match &mut self.inner {
143            VariousInner::One(s) => VariousIterMutInner::One(s.iter_mut()),
144            VariousInner::More(s) => VariousIterMutInner::More(s.iter_mut()),
145        };
146        VariousIterMut { inner }
147    }
148
149    #[inline]
150    pub fn first(&self) -> Option<&T> {
151        match self.inner {
152            VariousInner::One(ref s) => s.as_ref(),
153            VariousInner::More(ref s) => s.iter().next(),
154        }
155    }
156
157    #[inline]
158    pub fn last(&self) -> Option<&T> {
159        match self.inner {
160            VariousInner::More(ref s) => s.last(),
161            VariousInner::One(ref s) => s.as_ref(),
162        }
163    }
164
165    pub fn last_mut(&mut self) -> Option<&mut T> {
166        match self.inner {
167            VariousInner::More(ref mut s) => s.last_mut(),
168            VariousInner::One(ref mut s) => s.as_mut(),
169        }
170    }
171
172    /// Returns a reverse iterator over the elements
173    #[inline]
174    pub fn iter_rev(&self) -> VariousIter<'_, T> {
175        let inner = match &self.inner {
176            VariousInner::One(s) => VariousIterInner::One(s.iter()),
177            VariousInner::More(s) => VariousIterInner::More(s.iter_rev()),
178        };
179        VariousIter { inner }
180    }
181
182    /// Returns a mutable reverse iterator over the elements
183    #[inline]
184    pub fn iter_mut_rev(&mut self) -> VariousIterMut<'_, T> {
185        let inner = match &mut self.inner {
186            VariousInner::One(s) => VariousIterMutInner::One(s.iter_mut()),
187            VariousInner::More(s) => VariousIterMutInner::More(s.iter_mut_rev()),
188        };
189        VariousIterMut { inner }
190    }
191
192    /// Take the content out and leave and empty option inside, freeing inner memory
193    #[inline]
194    pub fn take(&mut self) -> Self {
195        use core::mem;
196        Various { inner: mem::replace(&mut self.inner, VariousInner::One(None)) }
197    }
198
199    /// Clear the content without freeing inner memory
200    #[inline]
201    pub fn clear(&mut self) {
202        match &mut self.inner {
203            VariousInner::One(inner) => {
204                let _ = inner.take();
205            }
206            VariousInner::More(inner) => inner.clear(),
207        }
208    }
209}
210
211impl<T> IntoIterator for Various<T> {
212    type Item = T;
213
214    type IntoIter = VariousIntoIter<T>;
215
216    fn into_iter(self) -> VariousIntoIter<T> {
217        let inner = match self.inner {
218            VariousInner::One(s) => VariousIntoIterInner::One(s.into_iter()),
219            VariousInner::More(s) => VariousIntoIterInner::More(s.drain()),
220        };
221        VariousIntoIter { inner }
222    }
223}
224
225impl<T> Various<T> {
226    /// Returns a reverse consuming iterator
227    #[inline]
228    pub fn into_rev(self) -> VariousIntoIter<T> {
229        let inner = match self.inner {
230            VariousInner::One(s) => VariousIntoIterInner::One(s.into_iter()),
231            VariousInner::More(s) => VariousIntoIterInner::More(s.into_rev()),
232        };
233        VariousIntoIter { inner }
234    }
235}
236
237impl<'a, T> IntoIterator for &'a Various<T> {
238    type Item = &'a T;
239
240    type IntoIter = VariousIter<'a, T>;
241
242    fn into_iter(self) -> VariousIter<'a, T> {
243        self.iter()
244    }
245}
246
247pub struct VariousIter<'a, T> {
248    inner: VariousIterInner<'a, T>,
249}
250
251enum VariousIterInner<'a, T> {
252    One(core::option::Iter<'a, T>),
253    More(crate::seg_list::SegListIter<'a, T>),
254}
255
256impl<'a, T> core::iter::Iterator for VariousIter<'a, T> {
257    type Item = &'a T;
258
259    fn next(&mut self) -> Option<Self::Item> {
260        match &mut self.inner {
261            VariousIterInner::One(i) => i.next(),
262            VariousIterInner::More(i) => i.next(),
263        }
264    }
265}
266
267pub struct VariousIterMut<'a, T> {
268    inner: VariousIterMutInner<'a, T>,
269}
270
271enum VariousIterMutInner<'a, T> {
272    One(core::option::IterMut<'a, T>),
273    More(crate::seg_list::SegListIterMut<'a, T>),
274}
275
276impl<'a, T> core::iter::Iterator for VariousIterMut<'a, T> {
277    type Item = &'a mut T;
278
279    fn next(&mut self) -> Option<Self::Item> {
280        match &mut self.inner {
281            VariousIterMutInner::One(i) => i.next(),
282            VariousIterMutInner::More(i) => i.next(),
283        }
284    }
285}
286
287pub struct VariousIntoIter<T> {
288    inner: VariousIntoIterInner<T>,
289}
290
291enum VariousIntoIterInner<T> {
292    One(core::option::IntoIter<T>),
293    More(crate::seg_list::SegListDrain<T>),
294}
295
296impl<T> core::iter::Iterator for VariousIntoIter<T> {
297    type Item = T;
298
299    fn next(&mut self) -> Option<Self::Item> {
300        match &mut self.inner {
301            VariousIntoIterInner::One(i) => i.next(),
302            VariousIntoIterInner::More(i) => i.next(),
303        }
304    }
305}
306
307impl<T: fmt::Debug> fmt::Debug for Various<T> {
308    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
309        match &self.inner {
310            VariousInner::One(s) => s.fmt(f),
311            VariousInner::More(s) => s.fmt(f),
312        }
313    }
314}
315
316#[cfg(test)]
317mod tests {
318
319    use super::*;
320
321    #[test]
322    fn test_one() {
323        let mut s = Various::new();
324        s.push(1);
325        assert_eq!(s.len(), 1);
326        for i in &s {
327            assert_eq!(*i, 1);
328        }
329        assert_eq!(Some(1), s.pop());
330        assert_eq!(s.len(), 0);
331        if (&s).into_iter().next().is_some() {
332            unreachable!();
333        }
334    }
335
336    #[test]
337    fn test_cap_0() {
338        let mut s = Various::new();
339        s.push(1);
340        assert_eq!(s.len(), 1);
341        for i in &s {
342            assert_eq!(*i, 1);
343        }
344        s.push(2);
345        s.push(3);
346        assert_eq!(s.len(), 3);
347        let mut total = 0;
348        for i in &s {
349            total += *i;
350        }
351        assert_eq!(total, 6);
352        for i in s.iter_mut() {
353            *i += 1;
354        }
355        let mut total = 0;
356        for i in &s {
357            total += *i;
358        }
359        assert_eq!(total, 9);
360        assert_eq!(s.pop(), Some(4));
361        let mut total = 0;
362        for i in s {
363            total += i;
364        }
365        assert_eq!(total, 5);
366    }
367
368    #[test]
369    fn test_more() {
370        let mut s = Various::new();
371        s.push(1);
372        s.push(2);
373        s.push(3);
374        assert_eq!(s.len(), 3);
375        let mut total = 0;
376        for i in &s {
377            total += *i;
378        }
379        assert_eq!(total, 6);
380        for i in s.iter_mut() {
381            *i += 1;
382        }
383        let mut total = 0;
384        for i in &s {
385            total += *i;
386        }
387        assert_eq!(total, 9);
388        assert_eq!(s.pop(), Some(4));
389        let mut total = 0;
390        for i in s {
391            total += i;
392        }
393        assert_eq!(total, 5);
394    }
395
396    #[test]
397    fn test_iter_rev_one() {
398        // Test reverse iterator with single element
399        let mut s = Various::new();
400        s.push(42);
401
402        let collected: Vec<i32> = s.iter_rev().copied().collect();
403        assert_eq!(collected, vec![42]);
404
405        // Test mutable reverse iterator
406        for i in s.iter_mut_rev() {
407            *i *= 10;
408        }
409        assert_eq!(s.first(), Some(&420));
410    }
411
412    #[test]
413    fn test_iter_rev_more() {
414        // Test reverse iterator with multiple elements
415        let mut s = Various::new();
416        s.push(1);
417        s.push(2);
418        s.push(3);
419
420        let collected: Vec<i32> = s.iter_rev().copied().collect();
421        assert_eq!(collected, vec![3, 2, 1]);
422
423        // Test mutable reverse iterator
424        for i in s.iter_mut_rev() {
425            *i *= 10;
426        }
427        let collected: Vec<i32> = s.iter().copied().collect();
428        assert_eq!(collected, vec![10, 20, 30]);
429    }
430
431    #[test]
432    fn test_iter_rev_empty() {
433        // Test reverse iterator with empty Various
434        let s: Various<i32> = Various::new();
435        let collected: Vec<i32> = s.iter_rev().copied().collect();
436        assert!(collected.is_empty());
437
438        let mut s_mut: Various<i32> = Various::new();
439        let count = s_mut.iter_mut_rev().count();
440        assert_eq!(count, 0);
441    }
442
443    #[test]
444    fn test_into_rev_one() {
445        // Test reverse consuming iterator with single element
446        let mut s = Various::new();
447        s.push(42);
448
449        let collected: Vec<i32> = s.into_rev().collect();
450        assert_eq!(collected, vec![42]);
451    }
452
453    #[test]
454    fn test_into_rev_more() {
455        // Test reverse consuming iterator with multiple elements
456        let mut s = Various::new();
457        s.push(1);
458        s.push(2);
459        s.push(3);
460
461        let collected: Vec<i32> = s.into_rev().collect();
462        assert_eq!(collected, vec![3, 2, 1]);
463    }
464
465    #[test]
466    fn test_into_rev_empty() {
467        // Test reverse consuming iterator with empty Various
468        let s: Various<i32> = Various::new();
469        let collected: Vec<i32> = s.into_rev().collect();
470        assert!(collected.is_empty());
471    }
472}
embed_collections/various.rs

embed_collections/
various.rs
