cons_list/
lib.rs

1// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
2// file at the top-level directory of this distribution and at
3// http://rust-lang.org/COPYRIGHT.
4//
5// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8// option. This file may not be copied, modified, or distributed
9// except according to those terms.
10
11//! An immutable singly-linked list, as seen in basically every functional language.
12
13#![cfg_attr(test, feature(test))]
14#[cfg(test)]
15extern crate test;
16
17
18
19use std::cmp::Ordering;
20use std::iter;
21use std::rc::Rc;
22use std::hash::{Hash, Hasher};
23
24struct Node<T> {
25    elem: T,
26    next: Option<Rc<Node<T>>>,
27}
28
29impl<T> Node<T> {
30    fn new(elem: T) -> Node<T> {
31        Node {
32            elem: elem,
33            next: None,
34        }
35    }
36}
37
38/// An iterator over the items of an ConsList
39#[derive(Clone)]
40pub struct Iter<'a, T: 'a> {
41    head: Option<&'a Node<T>>,
42    nelem: usize,
43}
44
45/// An immutable singly-linked list, as seen in basically every functional language
46pub struct ConsList<T> {
47    front: Option<Rc<Node<T>>>,
48    length: usize,
49}
50
51impl<T> ConsList<T> {
52    /// Constructs a new, empty `ConsList`
53    pub fn new() -> ConsList<T> {
54        ConsList {
55            front: None,
56            length: 0,
57        }
58    }
59
60    /// Returns a copy of the list, with `elem` appended to the front
61    pub fn append(&self, elem: T) -> ConsList<T> {
62        let mut new_node = Node::new(elem);
63        new_node.next = self.front.clone();
64
65        ConsList {
66            front: Some(Rc::new(new_node)),
67            length: self.len() + 1,
68        }
69    }
70
71    /// Returns a reference to the first element in the list
72    pub fn head(&self) -> Option<&T> {
73        self.front.as_ref().map(|node| &node.elem)
74    }
75
76    /// Returns a copy of the list, with the first element removed
77    pub fn tail(&self) -> ConsList<T> {
78        self.tailn(1)
79    }
80
81    /// Returns a copy of the list, with the first `n` elements removed
82    pub fn tailn(&self, n: usize) -> ConsList<T> {
83        if self.len() <= n {
84            ConsList::new()
85        } else {
86            let len = self.len() - n;
87            let mut head = self.front.as_ref();
88            for _ in 0..n {
89                head = head.unwrap().next.as_ref();
90            }
91            ConsList {
92                front: Some(head.unwrap().clone()),
93                length: len,
94            }
95        }
96    }
97
98    /// Returns the last element in the list
99    pub fn last(&self) -> Option<&T> {
100        self.iter().last()
101    }
102
103    /// Returns a copy of the list, with only the last `n` elements remaining
104    pub fn lastn(&self, n: usize) -> ConsList<T> {
105        if n >= self.length {
106            self.clone()
107        } else {
108            self.tailn(self.length - n)
109        }
110
111    }
112
113    /// Returns an iterator over references to the elements of the list in order
114    pub fn iter<'a>(&'a self) -> Iter<'a, T> {
115        Iter {
116            head: self.front.as_ref().map(|x| &**x),
117            nelem: self.len(),
118        }
119    }
120
121    pub fn len(&self) -> usize {
122        self.length
123    }
124
125    pub fn is_empty(&self) -> bool {
126        return self.len() == 0;
127    }
128}
129
130impl<T> Drop for ConsList<T> {
131    fn drop(&mut self) {
132        // don't want to blow the stack with destructors,
133        // but also don't want to walk the whole list.
134        // So walk the list until we find a non-uniquely owned item
135        let mut head = self.front.take();
136        loop {
137            let temp = head;
138            match temp {
139                Some(node) => {
140                    match Rc::try_unwrap(node) {
141                        Ok(mut node) => {
142                            head = node.next.take();
143                        }
144                        _ => return,
145                    }
146                }
147                _ => return,
148            }
149        }
150    }
151}
152
153
154impl<'a, T> Iterator for Iter<'a, T> {
155    type Item = &'a T;
156    fn next(&mut self) -> Option<&'a T> {
157        match self.head.take() {
158            None => None,
159            Some(head) => {
160                self.nelem -= 1;
161                self.head = head.next.as_ref().map(|next| &**next);
162                Some(&head.elem)
163            }
164        }
165    }
166
167    fn size_hint(&self) -> (usize, Option<usize>) {
168        (self.nelem, Some(self.nelem))
169    }
170}
171
172impl<T> iter::FromIterator<T> for ConsList<T> {
173    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> ConsList<T> {
174        let mut list = ConsList::new();
175        for elem in iter {
176            list = list.append(elem);
177        }
178        list
179    }
180}
181
182impl<T: PartialEq> PartialEq for ConsList<T> {
183    fn eq(&self, other: &ConsList<T>) -> bool {
184        self.len() == other.len() && self.iter().zip(other.iter()).all(|(x, y)| x == y)
185    }
186
187    fn ne(&self, other: &ConsList<T>) -> bool {
188        self.len() != other.len() || self.iter().zip(other.iter()).all(|(x, y)| x != y)
189    }
190}
191
192impl<T: PartialOrd> PartialOrd for ConsList<T> {
193    fn partial_cmp(&self, other: &ConsList<T>) -> Option<Ordering> {
194        let mut a = self.iter();
195        let mut b = other.iter();
196        loop {
197            match (a.next(), b.next()) {
198                (None, None) => return Some(std::cmp::Ordering::Equal),
199                (None, _) => return Some(std::cmp::Ordering::Less),
200                (_, None) => return Some(std::cmp::Ordering::Greater),
201                (Some(x), Some(y)) => {
202                    match x.partial_cmp(&y) {
203                        Some(std::cmp::Ordering::Equal) => (),
204                        non_eq => return non_eq,
205                    }
206                }
207            }
208        }
209    }
210}
211
212impl<T> Clone for ConsList<T> {
213    fn clone(&self) -> ConsList<T> {
214        ConsList {
215            front: self.front.clone(),
216            length: self.length,
217        }
218    }
219}
220
221impl<T: std::fmt::Debug> std::fmt::Debug for ConsList<T> {
222    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
223        try!(write!(f, "["));
224
225        for (i, e) in self.iter().enumerate() {
226            if i != 0 {
227                try!(write!(f, ", "));
228            }
229            try!(write!(f, "{:?}", *e));
230        }
231
232        write!(f, "]")
233    }
234}
235
236impl<A: Hash> Hash for ConsList<A> {
237    fn hash<H: Hasher>(&self, state: &mut H) {
238        self.len().hash(state);
239        for elt in self.iter() {
240            elt.hash(state);
241        }
242    }
243}
244
245impl<'a, T> IntoIterator for &'a ConsList<T> {
246    type Item = &'a T;
247    type IntoIter = Iter<'a, T>;
248    fn into_iter(self) -> Iter<'a, T> {
249        self.iter()
250    }
251}
252
253#[cfg(test)]
254mod tests {
255    use std::hash;
256
257    use super::ConsList;
258
259    #[test]
260    fn test_basic() {
261        let mut m = ConsList::new();
262        assert_eq!(m.head(), None);
263        assert_eq!(m.tail().head(), None);
264        m = m.append(Box::new(1));
265        assert_eq!(**m.head().unwrap(), 1);
266        m = m.tail().append(Box::new(2)).append(Box::new(3));
267        assert_eq!(m.len(), 2);
268        assert_eq!(**m.head().unwrap(), 3);
269        m = m.tail();
270        assert_eq!(**m.head().unwrap(), 2);
271        m = m.tail();
272        assert_eq!(m.len(), 0);
273        assert_eq!(m.head(), None);
274        m = m.append(Box::new(7)).append(Box::new(5)).append(Box::new(3)).append(Box::new(1));
275        assert_eq!(**m.head().unwrap(), 1);
276    }
277
278    #[test]
279    fn test_tailn() {
280        let m = list_from(&[0, 1, 2, 3, 4, 5]);
281        assert_eq!(m.tailn(0), m);
282        assert_eq!(m.tailn(3), m.tail().tail().tail());
283    }
284
285    #[test]
286    fn test_last() {
287        let mut m = list_from(&[0, 1, 2, 3, 4, 5]);
288        assert_eq!(m.last().unwrap(), &5);
289
290        m = ConsList::new();
291        assert_eq!(m.last(), None);
292    }
293
294    #[test]
295    fn test_lastn() {
296        let m = list_from(&[0, 1, 2, 3, 4, 5]);
297        assert_eq!(m.lastn(0).head(), None);
298        assert_eq!(m.lastn(8), m);
299        assert_eq!(m.lastn(4), m.tail().tail());
300    }
301
302    #[cfg(test)]
303    fn generate_test() -> ConsList<i32> {
304        list_from(&[0, 1, 2, 3, 4, 5, 6])
305    }
306
307    #[cfg(test)]
308    fn list_from<T: Clone>(v: &[T]) -> ConsList<T> {
309        v.iter().rev().map(|x| (*x).clone()).collect()
310    }
311
312    #[test]
313    fn test_iterator() {
314        let m = generate_test();
315        for (i, elt) in m.iter().enumerate() {
316            assert_eq!(i as i32, *elt);
317        }
318        let mut n = ConsList::new();
319        assert_eq!(n.iter().next(), None);
320        n = n.append(4);
321        let mut it = n.iter();
322        assert_eq!(it.size_hint(), (1, Some(1)));
323        assert_eq!(it.next().unwrap(), &4);
324        assert_eq!(it.size_hint(), (0, Some(0)));
325        assert_eq!(it.next(), None);
326    }
327
328    #[test]
329    fn test_iterator_clone() {
330        let mut n = ConsList::new();
331        n = n.append(1).append(2).append(3);
332        let mut it = n.iter();
333        it.next();
334        let mut jt = it.clone();
335        assert_eq!(it.next(), jt.next());
336        assert_eq!(it.next(), jt.next());
337    }
338
339    #[test]
340    fn test_eq() {
341        let mut n: ConsList<u8> = list_from(&[]);
342        let mut m = list_from(&[]);
343        assert!(n == m);
344        n = n.append(1);
345        assert!(n != m);
346        m = m.append(1);
347        assert!(n == m);
348
349        let n = list_from(&[2, 3, 4]);
350        let m = list_from(&[1, 2, 3]);
351        assert!(n != m);
352    }
353
354    #[test]
355    fn test_hash() {
356        let mut x = ConsList::new();
357        let mut y = ConsList::new();
358
359        let mut h = hash::SipHasher::new();
360
361        assert!(hash::Hash::hash(&x, &mut h) == hash::Hash::hash(&y, &mut h));
362
363        x = x.append(1).append(2).append(3);
364        y = y.append(1).append(4).tail().append(2).append(3);
365
366        assert!(hash::Hash::hash(&x, &mut h) == hash::Hash::hash(&y, &mut h));
367    }
368
369    #[test]
370    fn test_ord() {
371        let n = list_from(&[]);
372        let m = list_from(&[1, 2, 3]);
373        assert!(n < m);
374        assert!(m > n);
375        assert!(n <= n);
376        assert!(n >= n);
377    }
378
379    #[test]
380    fn test_ord_nan() {
381        let nan = 0.0f64 / 0.0;
382        let n = list_from(&[nan]);
383        let m = list_from(&[nan]);
384        assert!(!(n < m));
385        assert!(!(n > m));
386        assert!(!(n <= m));
387        assert!(!(n >= m));
388
389        let n = list_from(&[nan]);
390        let one = list_from(&[1.0f64]);
391        assert!(!(n < one));
392        assert!(!(n > one));
393        assert!(!(n <= one));
394        assert!(!(n >= one));
395
396        let u = list_from(&[1.0f64, 2.0, nan]);
397        let v = list_from(&[1.0f64, 2.0, 3.0]);
398        assert!(!(u < v));
399        assert!(!(u > v));
400        assert!(!(u <= v));
401        assert!(!(u >= v));
402
403        let s = list_from(&[1.0f64, 2.0, 4.0, 2.0]);
404        let t = list_from(&[1.0f64, 2.0, 3.0, 2.0]);
405        assert!(!(s < t));
406        assert!(s > one);
407        assert!(!(s <= one));
408        assert!(s >= one);
409    }
410
411    #[test]
412    fn test_debug() {
413        let list: ConsList<i32> = (0..10).rev().collect();
414        assert_eq!(format!("{:?}", list), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
415
416        let list: ConsList<&str> = vec!["just", "one", "test", "more"]
417            .iter()
418            .rev()
419            .map(|&s| s)
420            .collect();
421        assert_eq!(format!("{:?}", list), r#"["just", "one", "test", "more"]"#);
422    }
423}
424
425#[cfg(test)]
426mod bench {
427    use test::Bencher;
428    use test;
429
430    use super::ConsList;
431
432    #[bench]
433    fn bench_collect_into(b: &mut test::Bencher) {
434        let v = &[0i32; 64];
435        b.iter(|| { let _: ConsList<i32> = v.iter().map(|x| *x).collect(); })
436    }
437
438    #[bench]
439    fn bench_append(b: &mut test::Bencher) {
440        let mut m: ConsList<i32> = ConsList::new();
441        b.iter(|| { m = m.append(0); })
442    }
443
444    #[bench]
445    fn bench_append_tail(b: &mut test::Bencher) {
446        let mut m: ConsList<i32> = ConsList::new();
447        b.iter(|| { m = m.append(0).tail(); })
448    }
449
450    #[bench]
451    fn bench_iter(b: &mut test::Bencher) {
452        let v = &[0; 128];
453        let m: ConsList<i32> = v.iter().map(|&x| x).collect();
454        b.iter(|| {
455                   assert!(m.iter().count() == 128);
456               })
457    }
458}
459
cons_list/lib.rs

cons_list/
lib.rs
