cl_structures/
list.rs

1//! A stack or arena-allocable append-only linked list.
2//!
3//! This is pretty good for expressing recursive algorithms which
4//! follow a stack discipline but are expressed easier with context
5//! further up the stack.
6//!
7//! ```rust
8//! # use cl_structures::list::List;
9//! let l1 = List::new("which borrows the rest");
10//! let l2 = l1.enter("I must construct a new node");
11//! let l3 = l2.enter("For each new item");
12//!
13//! // You can iterate over the items from head to tail
14//! let mut list = Vec::from_iter(l3.iter().copied());
15//!
16//! assert_eq!(list[..], [
17//!     "For each new item",
18//!     "I must construct a new node",
19//!     "which borrows the rest",
20//! ])
21//! ```
22
23/// A stack or arena-allocable append-only linked list.
24#[derive(Clone, Copy, Debug, Default)]
25pub enum List<'parent, T> {
26    /// A list with one more element than its parent
27    Cons(&'parent List<'parent, T>, T),
28    /// The base case: an empty list
29    #[default]
30    Nil,
31}
32
33impl<'parent, T> List<'parent, T> {
34    /// Creates a new single-element [List]
35    pub fn new(value: T) -> List<'static, T> {
36        List::Cons(&List::Nil, value)
37    }
38
39    /// Creates a [List] with one more element than `self`
40    pub fn enter<'a>(&'a self, value: T) -> List<'a, T>
41    where T: 'a {
42        List::Cons(self, value)
43    }
44
45    /// Gets the value contained in this [List] (the `car`)
46    pub fn value(&self) -> Option<&T> {
47        match self {
48            Self::Cons(_, value) => Some(value),
49            Self::Nil => None,
50        }
51    }
52
53    /// Gets the parent element of this [List] (the `cdr`)
54    pub fn parent(&self) -> Option<&List<'parent, T>> {
55        match self {
56            Self::Cons(parent, _) => Some(parent),
57            Self::Nil => None,
58        }
59    }
60
61    /// Gets an [Iterator] over the elements of this [List].
62    ///
63    /// Elements are yielded in reverse insertion order (most to least recent)
64    pub fn iter(&self) -> ListIter<'_, T> {
65        ListIter(self)
66    }
67
68    pub fn get_reverse(&self) -> Vec<&T> {
69        fn inner<'i, T>(parent: &'i List<'i, T>, mut vec: Vec<&'i T>) -> Vec<&'i T> {
70            if let List::Cons(parent, value) = parent {
71                vec = inner(parent, vec);
72                vec.push(value)
73            }
74            vec
75        }
76        inner(self, vec![])
77    }
78}
79
80/// Iterates over the items of a List from most recent to least
81pub struct ListIter<'p, T>(&'p List<'p, T>);
82impl<'p, T> Iterator for ListIter<'p, T> {
83    type Item = &'p T;
84
85    fn next(&mut self) -> Option<Self::Item> {
86        let List::Cons(list, value) = self.0 else {
87            return None;
88        };
89        self.0 = *list;
90        Some(value)
91    }
92}
cl_structures/list.rs

cl_structures/
list.rs
