cons_rs/
lib.rs

1//! A crate that contains a singly linked list.
2//!
3//! Note:
4//! This is different from the standard [`LinkedList`],
5//! which is doubly linked.
6//!
7//! [`LinkedList`]: alloc::collections::LinkedList
8#![no_std]
9#![warn(missing_docs)]
10#![forbid(unsafe_code)]
11
12// clippy settings
13#![warn(
14    clippy::alloc_instead_of_core, 
15    clippy::std_instead_of_alloc, 
16    clippy::std_instead_of_core
17)]
18#![allow(
19    clippy::must_use_candidate, 
20    clippy::return_self_not_must_use
21)]
22
23extern crate alloc;
24use alloc::boxed::Box;
25
26use core::iter::FusedIterator;
27use core::fmt::{self, Debug};
28
29// Needs to be up here so it can be imported into immutable module.
30macro_rules! into_iter_impl {
31    ($type: ty, $item: ty, $iter: ty, $func: path) => {
32        impl<'a, T> IntoIterator for $type {
33            type Item = $item;
34            type IntoIter = $iter;
35
36            fn into_iter(self) -> Self::IntoIter {
37                $func(self)
38            }
39        }
40    };
41    (ref, $iter: ty, $func: path) => {
42        into_iter_impl!{&'a List<T>, &'a T, $iter, $func}
43    };
44    (ref mut, $iter: ty, $func: path) => {
45        into_iter_impl!{&'a mut List<T>, &'a mut T, $iter, $func}
46    }
47}
48
49#[cfg(feature = "immutable")]
50pub mod immutable;
51
52/// A singly linked list.
53/// See the [crate-level documentation](crate) for more.
54pub struct List<T> {
55    head: Link<T>,
56}
57
58struct Node<T> {
59    elem: T,
60    next: Link<T>,
61}
62
63type Link<T> = Option<Box<Node<T>>>;
64
65impl<T> List<T> {
66    /// Creates an empty `List`.
67    ///
68    /// # Examples
69    ///
70    /// ```
71    /// use cons_rs::List;
72    ///
73    /// let list: List<i32> = List::new();
74    /// ```
75    #[inline]
76    pub const fn new() -> Self {
77        List { head: None }
78    }
79
80    /// Prepends an element to the beginning of the `List`.
81    ///
82    /// # Examples
83    ///
84    /// ```
85    /// use cons_rs::List;
86    /// 
87    /// let mut list = List::new();
88    ///
89    /// list.push(1);
90    /// assert_eq!(list.peek(), Some(&1));
91    ///
92    /// list.push(2);
93    /// assert_eq!(list.peek(), Some(&2));
94    /// ```
95    pub fn push(&mut self, element: T) {
96        let new = Node {
97            elem: element,
98            next: self.head.take(),
99        };
100
101        self.head = Some(Box::new(new));
102    }
103
104    /// Removes the element at the front of the `List`,
105    /// and returns it.
106    ///
107    /// # Examples
108    ///
109    /// ```
110    /// use cons_rs::List;
111    /// 
112    /// let mut list = List::new();
113    /// assert_eq!(list.pop(), None);
114    ///
115    /// list.push(1);
116    ///
117    /// assert_eq!(list.pop(), Some(1));
118    /// assert_eq!(list.pop(), None);
119    /// ```
120    pub fn pop(&mut self) -> Option<T> {
121        self.head.take().map(|node| {
122            self.head = node.next;
123            node.elem
124        })
125    }
126
127    /// Checks if the `List` is empty.
128    ///
129    /// # Examples
130    ///
131    /// ```
132    /// use cons_rs::List;
133    /// 
134    /// let mut list = List::new();
135    /// assert!(list.is_empty());
136    ///
137    /// list.push(1);
138    /// assert!(!list.is_empty());
139    /// ```
140    #[inline]
141    pub fn is_empty(&self) -> bool {
142        self.head.is_none()
143    }
144
145    /// Removes all elements from the `List`.
146    ///
147    /// # Examples
148    ///
149    /// ```
150    /// use cons_rs::List;
151    ///
152    /// let mut list = List::new();
153    /// list.push(1);
154    /// list.push(2);
155    /// list.clear();
156    /// 
157    /// assert!(list.is_empty());
158    /// ```
159    pub fn clear(&mut self) {
160        let mut current = self.head.take();
161
162        while let Some(mut node) = current {
163            current = node.next.take();
164        }
165    }
166    
167    /// Returns the length of the `List`.
168    ///
169    /// # Examples
170    ///
171    /// ```
172    /// use cons_rs::List;
173    ///
174    /// let mut list = List::new();
175    /// assert_eq!(list.len(), 0);
176    ///
177    /// list.push(1);
178    /// assert_eq!(list.len(), 1);
179    /// ```
180    pub fn len(&self) -> usize {
181        self.iter().len()
182    }
183    
184    /// Returns an immutable reference to the value
185    /// at the head of the `List`, if it exists.
186    ///
187    /// # Examples
188    ///
189    /// ```
190    /// use cons_rs::List;
191    /// 
192    /// let mut list = List::new();
193    /// assert_eq!(list.peek(), None);
194    ///
195    /// list.push(1);
196    /// assert_eq!(list.peek(), Some(&1));
197    /// ```
198    pub fn peek(&self) -> Option<&T> {
199        self.head.as_ref().map(|node| &node.elem)
200    }
201
202    /// Returns a mutable reference to the value
203    /// at the head of the `List`, if it exists.
204    ///
205    /// # Examples
206    ///
207    /// ```
208    /// use cons_rs::List;
209    /// 
210    /// let mut list = List::new();
211    /// assert_eq!(list.peek_mut(), None);
212    ///
213    /// list.push(1);
214    /// assert_eq!(list.peek_mut(), Some(&mut 1));
215    ///
216    /// *list.peek_mut().unwrap() = 50;
217    /// assert_eq!(list.peek_mut(), Some(&mut 50));
218    /// ```
219    pub fn peek_mut(&mut self) -> Option<&mut T> {
220        self.head.as_mut().map(|node| &mut node.elem)
221    }
222
223    /// Creates an [iterator that yields shared references](Iter)
224    /// to all the elements in the `List`.
225    ///
226    /// To get mutable references, see [`iter_mut`](List::iter_mut).
227    ///
228    /// # Examples
229    ///
230    /// ```
231    /// use cons_rs::List;
232    /// 
233    /// let mut list = List::new();
234    ///
235    /// list.push(1);
236    /// list.push(2);
237    ///
238    /// let mut iter = list.iter();
239    /// assert_eq!(iter.next(), Some(&2));
240    /// assert_eq!(iter.next(), Some(&1));
241    /// assert_eq!(iter.next(), None);
242    /// ```
243    pub fn iter(&self) -> Iter<'_, T> {
244        Iter {
245            next: self.head.as_deref(),
246        }
247    }
248
249    /// Creates an [iterator that yields mutable references](IterMut)
250    /// to all the elements in the `List`.
251    ///
252    /// To get shared references, see [`iter`](List::iter).
253    ///
254    /// # Examples
255    ///
256    /// ```
257    /// use cons_rs::List;
258    /// 
259    /// let mut list = List::new();
260    /// 
261    /// list.push(1);
262    /// list.push(2);
263    ///
264    /// for elem in list.iter_mut() {
265    ///     *elem += 10;
266    /// }
267    ///
268    /// assert_eq!(list.pop(), Some(12));
269    /// assert_eq!(list.pop(), Some(11));
270    /// assert_eq!(list.pop(), None);
271    /// ```
272    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
273        IterMut {
274            next: self.head.as_deref_mut(),
275        }
276    }
277}
278
279impl<T: Clone> Clone for List<T> {
280    fn clone(&self) -> Self {
281        self.iter().cloned().collect()
282    }
283}
284
285impl<T: Debug> Debug for List<T> {
286    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
287        f.debug_list().entries(self.iter()).finish()
288    }
289}
290
291impl<T> Default for List<T> {
292    #[inline]
293    fn default() -> Self {
294        Self::new()
295    }
296}
297
298impl<T: PartialEq> PartialEq for List<T> {
299    fn eq(&self, other: &Self) -> bool {
300        self.len() == other.len() && self.iter().eq(other)
301    }
302}
303
304impl<T: Eq> Eq for List<T> {}
305
306impl<T> Drop for List<T> {
307    fn drop(&mut self) {
308        self.clear();
309    }
310}
311
312impl<T> FromIterator<T> for List<T> {
313    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
314        let mut list = List::new();
315        list.extend(iter);
316        list
317    }
318}
319
320impl<T> Extend<T> for List<T> {
321    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
322        use alloc::collections::VecDeque;
323        
324        let mut queue = VecDeque::new();
325        queue.extend(iter);
326        
327        while let Some(elem) = queue.pop_back() {
328            self.push(elem);
329        }
330    }
331}
332
333into_iter_impl!{List<T>, T, IntoIter<T>, IntoIter}
334into_iter_impl!{ref, Iter<'a, T>, List::iter}
335into_iter_impl!{ref mut, IterMut<'a, T>, List::iter_mut}
336
337/// An [iterator](Iterator) that yields shared references
338/// to all the elements in a `List`.
339///
340/// For mutable references, see [`IterMut`].
341pub struct Iter<'a, T> {
342    next: Option<&'a Node<T>>,
343}
344
345impl<'a, T> Iterator for Iter<'a, T> {
346    type Item = &'a T;
347    
348    fn next(&mut self) -> Option<Self::Item> {
349        self.next.take().map(|node| {
350            self.next = node.next.as_deref();
351            &node.elem
352        })
353    }
354
355    fn size_hint(&self) -> (usize, Option<usize>) {
356        let mut len = 0;
357        let mut current = self.next;
358        while let Some(node) = current {
359            current = node.next.as_deref();
360            len += 1;
361        }
362        (len, Some(len))
363    }
364}
365
366// No methods because they all have default impls
367// NOTE:
368// Once ExactSizeIterator::is_empty is stablized (github.com/rust-lang/rust/issues/35428)
369// forward List::is_empty to it.
370impl<'a, T> ExactSizeIterator for Iter<'a, T> {}
371
372impl<'a, T> FusedIterator for Iter<'a, T> {}
373
374/// An [iterator](Iterator) that yields mutable references
375/// to all the elements in a `List`.
376///
377/// For shared references, see [`Iter`].
378pub struct IterMut<'a, T> {
379    next: Option<&'a mut Node<T>>,
380}
381
382impl<'a, T> Iterator for IterMut<'a, T> {
383    type Item = &'a mut T;
384    
385    fn next(&mut self) -> Option<Self::Item> {
386        self.next.take().map(|node| {
387            self.next = node.next.as_deref_mut();
388            &mut node.elem
389        })
390    }
391
392    fn size_hint(&self) -> (usize, Option<usize>) {
393        Iter { next: self.next.as_deref() }.size_hint()
394    }
395}
396
397// No methods because they all have default impls
398// NOTE:
399// Once ExactSizeIterator::is_empty is stablized (github.com/rust-lang/rust/issues/35428)
400// forward List::is_empty to it.
401impl<'a, T> ExactSizeIterator for IterMut<'a, T> {}
402
403impl<'a, T> FusedIterator for IterMut<'a, T> {}
404
405/// An [iterator](Iterator) that yields all the elements in a `List` by value.
406pub struct IntoIter<T>(List<T>);
407
408impl<T> Iterator for IntoIter<T> {
409    type Item = T;
410
411    fn next(&mut self) -> Option<Self::Item> {
412        self.0.pop()
413    }
414
415    fn size_hint(&self) -> (usize, Option<usize>) {
416        self.0.iter().size_hint()
417    }
418}
419
420// No methods because they all have default impls
421// NOTE:
422// Once ExactSizeIterator::is_empty is stablized (github.com/rust-lang/rust/issues/35428)
423// forward List::is_empty to it.
424impl<T> ExactSizeIterator for IntoIter<T> {}
425
426impl<T> FusedIterator for IntoIter<T> {}
427
428#[cfg(test)]
429mod tests {
430    use super::List;
431    use alloc::format;
432
433    #[test]
434    fn push_and_pop() {
435        let mut list = List::new();
436
437        assert_eq!(list.pop(), None);
438
439        list.push(1);
440        list.push(2);
441        list.push(3);
442
443        assert_eq!(list.pop(), Some(3));
444        assert_eq!(list.pop(), Some(2));
445
446        list.push(4);
447        list.push(5);
448
449        assert_eq!(list.pop(), Some(5));
450        assert_eq!(list.pop(), Some(4));
451        assert_eq!(list.pop(), Some(1));
452        assert_eq!(list.pop(), None);
453    }
454
455    #[test]
456    fn peek() {
457        let mut list = List::new();
458        assert_eq!(list.peek(), None);
459        assert_eq!(list.peek_mut(), None);
460
461        list.push(1);
462        list.push(2);
463        list.push(3);
464
465        assert_eq!(list.peek(), Some(&3));
466        assert_eq!(list.peek_mut(), Some(&mut 3));
467        list.peek_mut().map(|val| *val = 42);
468
469        assert_eq!(list.peek(), Some(&42));
470        assert_eq!(list.peek_mut(), Some(&mut 42));
471        assert_eq!(list.pop(), Some(42));
472        assert_eq!(list.pop(), Some(2));
473    }
474
475    #[test]
476    fn is_empty() {
477        let mut list = List::new();
478        assert!(list.is_empty());
479
480        list.push(1);
481        assert!(!list.is_empty());
482
483        list.pop();
484        assert!(list.is_empty());
485    }
486
487    #[test]
488    fn len() {
489        let mut list = List::new();
490        assert_eq!(list.len(), 0);
491
492        list.push(1);
493        list.push(2);
494        assert_eq!(list.len(), 2);
495
496        list.pop();
497        assert_eq!(list.len(), 1);
498    }
499
500    #[test]
501    fn size_hints() {
502        let empty = (0, Some(0));
503        let one = (1, Some(1));
504        
505        let mut list: List<i32> = List::new();
506        assert_eq!(list.iter().size_hint(), empty);
507        assert_eq!(list.iter_mut().size_hint(), empty);
508        assert_eq!(list.into_iter().size_hint(), empty);
509
510        let mut list = List::new();
511        list.push(1);
512
513        assert_eq!(list.iter().size_hint(), one);
514        assert_eq!(list.iter_mut().size_hint(), one);
515        assert_eq!(list.into_iter().size_hint(), one);
516    }
517    
518    #[test]
519    fn default() {
520        let mut list = List::default();
521        assert!(list.is_empty());
522        list.push(1);
523        assert_eq!(list.pop(), Some(1));
524        assert_eq!(list.pop(), None);
525    }
526
527    #[test]
528    fn clone() {
529        let mut list = List::new();
530        
531        list.push(1);
532        list.push(2);
533
534        let mut new_list = list.clone();
535        
536        assert_eq!(list.pop(), new_list.pop());
537        assert_eq!(list.pop(), new_list.pop());
538        assert_eq!(list.pop(), new_list.pop());
539    }
540
541    #[test]
542    fn debug_fmt() {
543        let mut list = List::new();
544        assert_eq!(
545            "[]",
546            format!("{:?}", list)
547        );
548
549        list.push(1);
550        list.push(2);
551        list.push(-3);
552
553        assert_eq!(
554            "[-3, 2, 1]",
555            format!("{:?}", list)
556        );
557    }
558
559    #[test]
560    fn into_iters() {
561        let mut list = List::new();
562
563        list.push(1);
564        list.push(2);
565
566        let mut expected_val = 2;
567        
568        for elem in list.clone() {
569            assert_eq!(elem, expected_val);
570            expected_val -= 1;
571        }
572        expected_val = 2;
573        
574        for elem in &list {
575            assert_eq!(elem, &expected_val);
576            expected_val -= 1;
577        }
578        expected_val = 2;
579
580        for elem in &mut list {
581            assert_eq!(elem, &mut expected_val);
582            expected_val -= 1;
583        }
584    }
585
586    #[test]
587    fn for_loop() {
588        let mut list = List::new();
589
590        list.push(0);
591        list.push(1);
592
593        let mut i = 1;
594        for elem in list {
595            assert_eq!(elem, i);
596            i -= 1;
597        }
598    }
599
600    #[test]
601    fn extend() {
602        let mut list = List::new();
603
604        list.extend([1, 2]);
605
606        assert_eq!(list.pop(), Some(1));
607        assert_eq!(list.pop(), Some(2));
608        assert_eq!(list.pop(), None);
609    }
610
611    #[test]
612    fn iter() {
613        let mut list = List::new();
614
615        list.push(1);
616        list.push(2);
617
618        let mut iter = list.iter();
619
620        assert_eq!(iter.next(), Some(&2));
621        assert_eq!(iter.next(), Some(&1));
622        assert_eq!(iter.next(), None);
623    }
624
625    #[test]
626    fn iter_mut() {
627        let mut list = List::new();
628
629        list.push(1);
630        list.push(2);
631        list.push(3);
632
633        let mut iter = list.iter_mut();
634
635        assert_eq!(iter.next(), Some(&mut 3));
636        assert_eq!(iter.next(), Some(&mut 2));
637        iter.next().map(|val| *val = 10);
638        assert_eq!(iter.next(), None);
639
640        assert_eq!(list.pop(), Some(3));
641        assert_eq!(list.pop(), Some(2));
642        assert_eq!(list.pop(), Some(10));
643        assert_eq!(list.pop(), None);
644    }
645
646    #[test]
647    fn from_iter() {
648        let mut list: List<_> = [1, 2, 3].into_iter().collect();
649
650        assert_eq!(list.pop(), Some(1));
651        assert_eq!(list.pop(), Some(2));
652        assert_eq!(list.pop(), Some(3));
653        assert_eq!(list.pop(), None);
654    }
655}
cons_rs/lib.rs

cons_rs/
lib.rs
