]>
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 | |
94222f64 | 8 | //! much space as an `Option<(T, usize)>`. If T can double as the `Option` |
94b46f34 XL |
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)] |
6a06907d | 18 | pub struct TinyList<T> { |
60c5eb7d | 19 | head: Option<Element<T>>, |
94b46f34 XL |
20 | } |
21 | ||
22 | impl<T: PartialEq> TinyList<T> { | |
94b46f34 XL |
23 | #[inline] |
24 | pub fn new() -> TinyList<T> { | |
60c5eb7d | 25 | TinyList { head: None } |
94b46f34 XL |
26 | } |
27 | ||
28 | #[inline] | |
29 | pub fn new_single(data: T) -> TinyList<T> { | |
60c5eb7d | 30 | TinyList { head: Some(Element { data, next: None }) } |
94b46f34 XL |
31 | } |
32 | ||
33 | #[inline] | |
34 | pub fn insert(&mut self, data: T) { | |
60c5eb7d | 35 | self.head = Some(Element { data, next: self.head.take().map(Box::new) }); |
94b46f34 XL |
36 | } |
37 | ||
38 | #[inline] | |
39 | pub fn remove(&mut self, data: &T) -> bool { | |
6522a427 EL |
40 | self.head = match &mut self.head { |
41 | Some(head) if head.data == *data => head.next.take().map(|x| *x), | |
42 | Some(head) => return head.remove_next(data), | |
b7449926 | 43 | None => return false, |
94b46f34 | 44 | }; |
b7449926 | 45 | true |
94b46f34 XL |
46 | } |
47 | ||
48 | #[inline] | |
49 | pub fn contains(&self, data: &T) -> bool { | |
e1599b0c | 50 | let mut elem = self.head.as_ref(); |
6522a427 | 51 | while let Some(e) = elem { |
e1599b0c XL |
52 | if &e.data == data { |
53 | return true; | |
54 | } | |
f9f354fc | 55 | elem = e.next.as_deref(); |
94b46f34 | 56 | } |
e1599b0c | 57 | false |
94b46f34 | 58 | } |
94b46f34 XL |
59 | } |
60 | ||
e74abb32 | 61 | #[derive(Clone)] |
6a06907d | 62 | struct Element<T> { |
94b46f34 XL |
63 | data: T, |
64 | next: Option<Box<Element<T>>>, | |
65 | } | |
66 | ||
67 | impl<T: PartialEq> Element<T> { | |
6522a427 | 68 | fn remove_next(mut self: &mut Self, data: &T) -> bool { |
60c5eb7d | 69 | loop { |
6522a427 | 70 | match self.next { |
60c5eb7d | 71 | Some(ref mut next) if next.data == *data => { |
6522a427 | 72 | self.next = next.next.take(); |
60c5eb7d XL |
73 | return true; |
74 | } | |
6522a427 | 75 | Some(ref mut next) => self = next, |
60c5eb7d XL |
76 | None => return false, |
77 | } | |
78 | } | |
94b46f34 | 79 | } |
94b46f34 | 80 | } |