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
|
//! A singly-linked list.
//!
//! Using this data structure only makes sense under very specific
//! circumstances:
//!
//! - If you have a list that rarely stores more than one element, then this
//! data-structure can store the element without allocating and only uses as
//! much space as a `Option<(T, usize)>`. If T can double as the `Option`
//! discriminant, it will even only be as large as `T, usize`.
//!
//! If you expect to store more than 1 element in the common case, steer clear
//! and use a `Vec<T>`, `Box<[T]>`, or a `SmallVec<T>`.
#[cfg(test)]
mod tests;
#[derive(Clone, Hash, Debug, PartialEq)]
pub struct TinyList<T: PartialEq> {
head: Option<Element<T>>
}
impl<T: PartialEq> TinyList<T> {
#[inline]
pub fn new() -> TinyList<T> {
TinyList {
head: None
}
}
#[inline]
pub fn new_single(data: T) -> TinyList<T> {
TinyList {
head: Some(Element {
data,
next: None,
})
}
}
#[inline]
pub fn insert(&mut self, data: T) {
self.head = Some(Element {
data,
next: self.head.take().map(Box::new)
});
}
#[inline]
pub fn remove(&mut self, data: &T) -> bool {
self.head = match self.head {
Some(ref mut head) if head.data == *data => {
head.next.take().map(|x| *x)
}
Some(ref mut head) => return head.remove_next(data),
None => return false,
};
true
}
#[inline]
pub fn contains(&self, data: &T) -> bool {
if let Some(ref head) = self.head {
head.contains(data)
} else {
false
}
}
#[inline]
pub fn len(&self) -> usize {
if let Some(ref head) = self.head {
head.len()
} else {
0
}
}
}
#[derive(Clone, Hash, Debug, PartialEq)]
struct Element<T: PartialEq> {
data: T,
next: Option<Box<Element<T>>>,
}
impl<T: PartialEq> Element<T> {
fn remove_next(&mut self, data: &T) -> bool {
let new_next = if let Some(ref mut next) = self.next {
if next.data != *data {
return next.remove_next(data)
} else {
next.next.take()
}
} else {
return false
};
self.next = new_next;
true
}
fn len(&self) -> usize {
if let Some(ref next) = self.next {
1 + next.len()
} else {
1
}
}
fn contains(&self, data: &T) -> bool {
if self.data == *data {
return true
}
if let Some(ref next) = self.next {
next.contains(data)
} else {
false
}
}
}
|
