]>
Commit | Line | Data |
---|---|---|
94b46f34 XL |
1 | //! A singly-linked list. |
2 | //! | |
3 | //! Using this data structure only makes sense under very specific | |
4 | //! circumstances: | |
5 | //! | |
6 | //! - If you have a list that rarely stores more than one element, then this | |
7 | //! data-structure can store the element without allocating and only uses as | |
8 | //! much space as a `Option<(T, usize)>`. If T can double as the `Option` | |
9 | //! discriminant, it will even only be as large as `T, usize`. | |
10 | //! | |
11 | //! If you expect to store more than 1 element in the common case, steer clear | |
12 | //! and use a `Vec<T>`, `Box<[T]>`, or a `SmallVec<T>`. | |
13 | ||
416331ca XL |
14 | #[cfg(test)] |
15 | mod tests; | |
16 | ||
e74abb32 | 17 | #[derive(Clone)] |
94b46f34 XL |
18 | pub struct TinyList<T: PartialEq> { |
19 | head: Option<Element<T>> | |
20 | } | |
21 | ||
22 | impl<T: PartialEq> TinyList<T> { | |
94b46f34 XL |
23 | #[inline] |
24 | pub fn new() -> TinyList<T> { | |
25 | TinyList { | |
26 | head: None | |
27 | } | |
28 | } | |
29 | ||
30 | #[inline] | |
31 | pub fn new_single(data: T) -> TinyList<T> { | |
32 | TinyList { | |
33 | head: Some(Element { | |
34 | data, | |
35 | next: None, | |
36 | }) | |
37 | } | |
38 | } | |
39 | ||
40 | #[inline] | |
41 | pub fn insert(&mut self, data: T) { | |
b7449926 XL |
42 | self.head = Some(Element { |
43 | data, | |
a1dfa0c6 | 44 | next: self.head.take().map(Box::new) |
b7449926 | 45 | }); |
94b46f34 XL |
46 | } |
47 | ||
48 | #[inline] | |
49 | pub fn remove(&mut self, data: &T) -> bool { | |
b7449926 XL |
50 | self.head = match self.head { |
51 | Some(ref mut head) if head.data == *data => { | |
a1dfa0c6 | 52 | head.next.take().map(|x| *x) |
94b46f34 | 53 | } |
b7449926 XL |
54 | Some(ref mut head) => return head.remove_next(data), |
55 | None => return false, | |
94b46f34 | 56 | }; |
b7449926 | 57 | true |
94b46f34 XL |
58 | } |
59 | ||
60 | #[inline] | |
61 | pub fn contains(&self, data: &T) -> bool { | |
e1599b0c XL |
62 | let mut elem = self.head.as_ref(); |
63 | while let Some(ref e) = elem { | |
64 | if &e.data == data { | |
65 | return true; | |
66 | } | |
67 | elem = e.next.as_ref().map(|e| &**e); | |
94b46f34 | 68 | } |
e1599b0c | 69 | false |
94b46f34 XL |
70 | } |
71 | ||
72 | #[inline] | |
73 | pub fn len(&self) -> usize { | |
e1599b0c XL |
74 | let (mut elem, mut count) = (self.head.as_ref(), 0); |
75 | while let Some(ref e) = elem { | |
76 | count += 1; | |
77 | elem = e.next.as_ref().map(|e| &**e); | |
94b46f34 | 78 | } |
e1599b0c | 79 | count |
94b46f34 XL |
80 | } |
81 | } | |
82 | ||
e74abb32 | 83 | #[derive(Clone)] |
94b46f34 XL |
84 | struct Element<T: PartialEq> { |
85 | data: T, | |
86 | next: Option<Box<Element<T>>>, | |
87 | } | |
88 | ||
89 | impl<T: PartialEq> Element<T> { | |
94b46f34 | 90 | fn remove_next(&mut self, data: &T) -> bool { |
e1599b0c XL |
91 | let new_next = match self.next { |
92 | Some(ref mut next) if next.data == *data => next.next.take(), | |
93 | Some(ref mut next) => return next.remove_next(data), | |
94 | None => return false, | |
94b46f34 | 95 | }; |
94b46f34 | 96 | self.next = new_next; |
b7449926 | 97 | true |
94b46f34 | 98 | } |
94b46f34 | 99 | } |