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
|
use std::iter::FromIterator;
#[derive(Debug)]
struct Node<T> {
data: T,
next: Option<Box<Node<T>>>,
}
impl<T> Node<T> {
pub fn new(data: T, next: Option<Box<Node<T>>>) -> Self {
Node { data, next }
}
pub fn len(&self) -> usize {
1 + self.next.as_ref().map(|n| n.len()).unwrap_or(0)
}
}
#[derive(Debug)]
pub struct SimpleLinkedList<T> {
head: Option<Box<Node<T>>>,
}
impl<T> SimpleLinkedList<T> {
pub fn new() -> Self {
SimpleLinkedList { head: None }
}
// You may be wondering why it's necessary to have is_empty()
// when it can easily be determined from len().
// It's good custom to have both because len() can be expensive for some types,
// whereas is_empty() is almost always cheap.
// (Also ask yourself whether len() is expensive for SimpleLinkedList)
pub fn is_empty(&self) -> bool {
self.head.is_none()
}
pub fn len(&self) -> usize {
self.head.as_ref().map(|n| n.len()).unwrap_or(0)
}
pub fn push(&mut self, _element: T) {
// let node = Box::new(Node::new(_element, self.head.take()));
// self.head.replace(node);
self.head = Some(Box::new(Node::new(_element, self.head.take())));
}
pub fn pop(&mut self) -> Option<T> {
self.head.take().map(|n| {
// n.next.map(|n1| self.head.replace(n1));
self.head = n.next;
n.data
})
}
pub fn peek(&self) -> Option<&T> {
self.head.as_ref().map(|n| &n.data)
}
pub fn rev(self) -> SimpleLinkedList<T> {
self.rev_aux(SimpleLinkedList::new())
}
pub fn rev_aux(mut self, mut acc: SimpleLinkedList<T>) -> SimpleLinkedList<T> {
if let Some(e) = self.pop() {
acc.push(e);
self.rev_aux(acc)
} else {
acc
}
}
fn into_aux(mut self, mut acc: Vec<T>) -> Vec<T> {
if let Some(e) = self.pop() {
acc.push(e);
self.into_aux(acc)
} else {
acc
}
}
}
impl<T> FromIterator<T> for SimpleLinkedList<T> {
fn from_iter<I: IntoIterator<Item = T>>(_iter: I) -> Self {
_iter
.into_iter()
.fold(SimpleLinkedList::new(), |mut acc, n| {
acc.push(n);
acc
})
}
}
// In general, it would be preferable to implement IntoIterator for SimpleLinkedList<T>
// instead of implementing an explicit conversion to a vector. This is because, together,
// FromIterator and IntoIterator enable conversion between arbitrary collections.
// Given that implementation, converting to a vector is trivial:
//
// let vec: Vec<_> = simple_linked_list.into_iter().collect();
//
// The reason this exercise's API includes an explicit conversion to Vec<T> instead
// of IntoIterator is that implementing that interface is fairly complicated, and
// demands more of the student than we expect at this point in the track.
impl<T> Into<Vec<T>> for SimpleLinkedList<T> {
fn into(self) -> Vec<T> {
self.rev().into_aux(Vec::new())
}
}
|
