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

embed_seglist/
various.rs
