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
        }
    }
}