chj_rustbin/
conslist.rs

1/// Cons list. Only works with normal references. That's because
2/// making it generic for the reference/container type appears
3/// unworkable, even though feasible in principle, due to requiring
4/// explicit type parameters on every single cons call. The solution
5/// will be to generate the code for versions using Rc, Arc or
6/// whatever when needed. (Or, use dyn?, or perhaps/probably rather,
7/// enum.)
8
9pub enum List<'t, T> {
10    Pair(T, &'t List<'t, T>),
11    Null,
12}
13
14pub fn cons<'l, T>(v: T, r: &'l List<T>) -> List<'l, T> {
15    List::Pair(v, r)
16}
17
18impl<'t, T> List<'t, T> {
19    pub fn len(&self) -> usize {
20        match self {
21            List::Pair(_, r) => r.len() + 1,
22            List::Null => 0,
23        }
24    }
25    pub fn first(&self) -> Option<&T> {
26        match self {
27            List::Pair(v, _) => Some(v),
28            List::Null => None,
29        }
30    }
31    pub fn rest(&self) -> Option<&List<'_, T>> {
32        match self {
33            List::Pair(_, r) => Some(r),
34            List::Null => None,
35        }
36    }
37    pub fn last(&self) -> Option<&T> {
38        match self {
39            List::Pair(v, List::Null) => Some(v),
40            List::Pair(_, r) => r.last(),
41            List::Null => None,
42        }
43    }
44    /// A Vec of all the values as references.
45    // For reverse simply reverse the Vec afterwards yourself? (Could
46    // also get length then fill in unsafely or require Default.)
47    pub fn as_ref_vec(&self) -> Vec<&T> {
48        let mut vs = Vec::new();
49        let mut r = self;
50        loop {
51            match r {
52                List::Pair(v, r2) => {
53                    vs.push(v);
54                    r = r2;
55                }
56                List::Null => break,
57            }
58        }
59        vs
60    }
61    pub fn to_vec(&self) -> Vec<T>
62    where
63        T: Clone,
64    {
65        let mut vs: Vec<T> = Vec::new();
66        let mut r = self;
67        loop {
68            match r {
69                List::Pair(v, r2) => {
70                    vs.push(v.clone());
71                    r = r2;
72                }
73                List::Null => break,
74            }
75        }
76        vs
77    }
78}
79
80impl<'t, T: PartialEq> List<'t, T> {
81    /// Report whether a List contains a particular value.
82    pub fn contains(&self, val: &T) -> bool {
83        let mut l = self;
84        loop {
85            match l {
86                List::Pair(v, rest) => {
87                    if v == val {
88                        return true;
89                    } else {
90                        l = rest;
91                    }
92                }
93                List::Null => return false,
94            }
95        }
96    }
97}
98
99impl<'t, K: PartialEq, V> List<'t, (K, V)> {
100    /// In a List of (K, V) pairs, get the first V for which the K ==
101    /// key.
102    pub fn alist_get(&self, key: &K) -> Option<&V> {
103        let mut l = self;
104        loop {
105            match l {
106                List::Pair((k, v), rest) => {
107                    if k == key {
108                        return Some(v);
109                    } else {
110                        l = rest;
111                    }
112                }
113                List::Null => return None,
114            }
115        }
116    }
117}
118
119#[cfg(test)]
120mod tests {
121    use super::*;
122
123    #[test]
124    fn t_general() {
125        let a = List::Pair(5, &List::Null);
126        let b = List::Pair(7, &a);
127        let c = List::Pair(9, &b);
128        let d = cons(13, &b);
129        let e = cons(14, &c);
130        assert_eq!(List::Null::<i8>.as_ref_vec(), Vec::<&i8>::new());
131        assert_eq!(a.to_vec(), vec![5]);
132        assert_eq!(b.as_ref_vec(), vec![&7, &5]);
133        assert_eq!(c.rest().unwrap().to_vec(), vec![7, 5]);
134        assert_eq!(c.to_vec(), vec![9, 7, 5]);
135        assert_eq!(d.to_vec(), vec![13, 7, 5]);
136        assert_eq!(e.to_vec(), vec![14, 9, 7, 5]);
137
138        assert_eq!(e.contains(&14), true);
139        assert_eq!(e.contains(&13), false);
140        assert_eq!(e.contains(&5), true);
141    }
142
143    #[test]
144    fn t_alist() {
145        let a = cons((5, "five"), &List::Null);
146        let b = cons((2, "two"), &a);
147        let c = cons((3, "three"), &b);
148        assert_eq!(c.alist_get(&5), Some(&"five"));
149        assert_eq!(c.alist_get(&3), Some(&"three"));
150        assert_eq!(c.alist_get(&4), None);
151    }
152}
chj_rustbin/conslist.rs

chj_rustbin/
conslist.rs
