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

embed_collections/
various.rs
