1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

/*
    Appellation: persistant <module>
    Contrib: FL03 <jo3mccain@icloud.com>
    Description: ... Summary ...
*/
use std::rc::Rc;

type Link<T> = Option<Rc<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

impl<T> Node<T> {
    pub fn new(elem: T, next: Link<T>) -> Self {
        Self { elem, next }
    }
    pub fn data(&self) -> &T {
        &self.elem
    }
    pub fn link(&self) -> &Link<T> {
        &self.next
    }
}

/// Singly-Linked, Persistant List
pub struct SLPList<T> {
    head: Link<T>,
}

impl<T> SLPList<T> {
    pub fn new() -> Self {
        Self::from(None)
    }
    pub fn prepend(&self, elem: T) -> Self {
        SLPList::from(Some(Rc::new(Node::new(elem, self.head.clone()))))
    }

    pub fn tail(&self) -> Self {
        SLPList::from(self.head.as_ref().and_then(|node| node.link().clone()))
    }

    pub fn head(&self) -> Option<&T> {
        self.head.as_ref().map(|node| node.data())
    }

    pub fn iter(&self) -> Iter<'_, T> {
        Iter {
            next: self.head.as_deref(),
        }
    }
}

impl<T> From<Link<T>> for SLPList<T> {
    fn from(head: Link<T>) -> SLPList<T> {
        SLPList { head }
    }
}

impl<T> Default for SLPList<T> {
    fn default() -> Self {
        Self::from(None)
    }
}

impl<T> Drop for SLPList<T> {
    fn drop(&mut self) {
        let mut head = self.head.take();
        while let Some(node) = head {
            if let Ok(mut node) = Rc::try_unwrap(node) {
                head = node.next.take();
            } else {
                break;
            }
        }
    }
}

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_deref();
            &node.elem
        })
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_linked_list() {
        let list = SLPList::default();
        assert_eq!(list.head(), None);

        let list = list.prepend(1).prepend(2).prepend(3);
        assert_eq!(list.head(), Some(&3));

        let list = list.tail();
        assert_eq!(list.head(), Some(&2));

        let list = list.tail();
        assert_eq!(list.head(), Some(&1));

        let list = list.tail();
        assert_eq!(list.head(), None);

        // Make sure empty tail works
        let list = list.tail();
        assert_eq!(list.head(), None);
    }

    #[test]
    fn test_linked_list_iter() {
        let list = SLPList::default().prepend(1).prepend(2).prepend(3);

        let mut iter = list.iter();
        assert_eq!(iter.next(), Some(&3));
        assert_eq!(iter.next(), Some(&2));
        assert_eq!(iter.next(), Some(&1));
    }
}