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
|
//! A linked list whose nodes can be stack-allocated.
use core::fmt;
/// A linked list whose nodes can be stack-allocated.
#[derive(Clone, Copy, Eq, Ord, PartialEq, PartialOrd)]
pub struct StackLinkedList<'list, T>(Option<(T, &'list StackLinkedList<'list, T>)>);
impl<'list, T> StackLinkedList<'list, T> {
/// An empty linked list.
pub const NIL: StackLinkedList<'list, T> = StackLinkedList(None);
/// Prepends an element to the linked list, returning the new head node.
pub fn cons(&'list self, head: T) -> StackLinkedList<'list, T> {
StackLinkedList(Some((head, self)))
}
/// Attempts to return the head and tail of the list.
pub fn uncons(&self) -> Option<(&T, &'list StackLinkedList<'list, T>)> {
let (hd, tl) = self.0.as_ref()?;
Some((hd, tl))
}
/// Returns an iterator over the elements in the list.
pub fn iter<'iter: 'list>(&'iter self) -> impl 'iter + Iterator<Item = &'list T> {
struct Iter<'iter, 'list, T>(&'iter StackLinkedList<'list, T>);
impl<'iter: 'list, 'list, T> Iterator for Iter<'iter, 'list, T> {
type Item = &'list T;
fn next(&mut self) -> Option<&'list T> {
match &(self.0).0 {
Some((hd, tl)) => {
self.0 = tl;
Some(hd)
}
None => None,
}
}
}
Iter(self)
}
}
impl<'list, T: fmt::Debug> fmt::Debug for StackLinkedList<'list, T> {
fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
fmt.debug_list().entries(self.iter()).finish()
}
}
impl<'list, T: Copy> IntoIterator for StackLinkedList<'list, T> {
type Item = T;
type IntoIter = OwnedIter<'list, T>;
fn into_iter(self) -> OwnedIter<'list, T> {
OwnedIter(self)
}
}
/// An (owned) iterator over a `StackLinkedList`.
#[derive(Clone)]
pub struct OwnedIter<'list, T>(StackLinkedList<'list, T>);
impl<'list, T: Copy> Iterator for OwnedIter<'list, T> {
type Item = T;
fn next(&mut self) -> Option<T> {
match (self.0).0 {
Some((hd, tl)) => {
self.0 = *tl;
Some(hd)
}
None => None,
}
}
}
|
