im_lists/
list.rs

1//! A persistent list.
2//!
3//! This is a sequence of elements, akin to a cons list. The most common operation is to
4//! [`cons`](crate::list::List::cons) to the front (or [`cons_mut`](crate::list::List::cons_mut))
5//! The API is designed to be a drop in replacement for an immutable linked list implementation, with instead the backing
6//! being an unrolled linked list or VList, depending on your configuration.
7//!
8//! # Performance Notes
9//!
10//! Using the mutable functions when possible enables in place mutation. Much of the internal structure is shared,
11//! so even immutable functions can be fast, but the mutable functions will be faster.
12
13use std::{cmp::Ordering, iter::FromIterator, marker::PhantomData};
14
15use crate::{
16    handler::{DefaultDropHandler, DropHandler},
17    shared::{ArcPointer, PointerFamily, RcPointer},
18    unrolled::{ConsumingWrapper, IterWrapper, UnrolledCell, UnrolledList},
19};
20
21/// A persistent list.
22///
23/// This list is suitable for either a single threaded or multi threaded environment. The list accepts the smart pointer
24/// that you would like to use as a type parameter. There are sensible type aliases for implementations that you can use:
25///
26/// [`SharedList`] is simply a type alias for `GenericList<T, ArcPointer, 256, 1>`, which is both [`Send`] + [`Sync`]
27/// Similarly, [`List`] is just a type alias for `GenericList<T, RcPointer, 256, 1>`. [`SharedVList`] and
28/// [`VList`] are type aliases, as well, using the same backing of `GenericList`, however they have a growth factor of 2 - meaning
29/// bucket sizes will grow exponentially.
30///
31/// It's implemented as an unrolled linked list, which is a single linked list which stores a variable
32/// amount of elements in each node. The capacity of any individual node for now is set to to be `N` elements, which means that until more than `N` elements
33/// are cons'd onto a list, it will remain a vector under the hood. By default, N is sset to 256. There is also a growth rate, `G`, which describes how
34/// each successive node will grow in size. With `N = 2`, and `G = 2`, the list will look something like this:
35///
36/// ```text
37/// [0, 1, 2, 3, 4, 5, 6, 7] -> [8, 9, 10, 11] -> [12, 13]
38///
39/// ```
40///
41/// The list is also designed to leverage in place mutations whenever possible - if the number of references pointing to either a cell containing a vector
42/// or the shared vector is one, then that mutation is done in place. Otherwise, it is copy-on-write, maintaining our persistent invariant.
43///
44/// ## Performance Notes
45///
46/// The algorithmic complexity of an unrolled linked list matches that of a normal linked list - however in practice
47/// we have a decrease by the factor of the capacity of a node that gives us practical
48/// performance wins. For a list that is fully filled, iteration over nodes becomes O(n / N), rather than the typical O(n). If the growth rate is set to 2 (or more),
49/// over individual nodes becomes O(log(n)) - which means indexing or finding the last element is O(log(n)) as well.
50/// In addition, the unrolled linked list is able to avoid the costly cache misses that a typical linked list
51/// suffers from, seeing very realistic performance gains.
52///
53/// Let *n* be the number of elements in the list, and *m* is the capacity of a node.
54/// In the worst case, a node will be on average half filled. In the best case, all nodes are completely full.
55/// This means for operations that for a normal linked list may take linear time *Θ(n)*, we get a constant factor
56/// decrease of either a factor of *m* or *m / 2*. Similarly, we will see O(log(n)) performance characteristics if the growth rate is set to be larger than 1.
57pub struct GenericList<
58    T: Clone + 'static,
59    P: PointerFamily = RcPointer,
60    const N: usize = 256,
61    const G: usize = 1,
62    D: DropHandler<Self> = DefaultDropHandler,
63>(UnrolledList<T, P, N, G>, PhantomData<D>);
64
65pub type SharedList<T> = GenericList<T, ArcPointer, 256>;
66pub type List<T> = GenericList<T, RcPointer, 256>;
67
68pub type SharedVList<T> = GenericList<T, ArcPointer, 2, 2>;
69pub type VList<T> = GenericList<T, RcPointer, 2, 2>;
70
71#[doc(hidden)]
72#[derive(Copy, Clone)]
73pub struct RawCell<
74    T: Clone + 'static,
75    P: PointerFamily,
76    const N: usize,
77    const G: usize,
78    D: DropHandler<GenericList<T, P, N, G, D>>,
79>(*const UnrolledCell<T, P, N, G>, PhantomData<D>);
80
81impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> Clone
82    for GenericList<T, P, N, G, D>
83{
84    fn clone(&self) -> Self {
85        Self(self.0.clone(), PhantomData)
86    }
87}
88
89impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>>
90    GenericList<T, P, N, G, D>
91{
92    /// Construct an empty list.
93    pub fn new() -> Self {
94        GenericList(UnrolledList::new(), PhantomData)
95    }
96
97    /// Constructs an empty list with capacity `N`
98    pub fn new_with_capacity() -> Self {
99        GenericList(UnrolledList::new_with_capacity(), PhantomData)
100    }
101
102    /// Get the number of strong references pointing to this list
103    ///
104    /// Time: O(1)
105    pub fn strong_count(&self) -> usize {
106        self.0.strong_count()
107    }
108
109    /// Compare this list to another for pointer equality
110    pub fn ptr_eq(&self, other: &Self) -> bool {
111        self.0.ptr_eq(&other.0)
112    }
113
114    #[doc(hidden)]
115    pub fn storage_ptr_eq(&self, other: &Self) -> bool {
116        self.0.shared_ptr_eq(&other.0)
117    }
118
119    #[doc(hidden)]
120    pub fn as_ptr_usize(&self) -> usize {
121        self.0.as_ptr_usize()
122    }
123
124    #[doc(hidden)]
125    pub fn elements_as_ptr_usize(&self) -> usize {
126        // Overflow is fine - this should give us a unique value?
127        self.0.elements_as_ptr_usize() + self.0.index()
128    }
129
130    #[doc(hidden)]
131    pub fn identity_tuple(&self) -> (usize, usize) {
132        (self.0.elements_as_ptr_usize(), self.0.index())
133    }
134
135    // Check the next pointer. If the next pointer is the same,
136    // then we otherwise need to check the values of the current node of the list.
137    #[doc(hidden)]
138    pub fn next_ptr_as_usize(&self) -> Option<usize> {
139        self.0.next_ptr_as_usize()
140    }
141
142    #[doc(hidden)]
143    pub fn current_node_iter(&self) -> impl Iterator<Item = &T> {
144        self.0.current_node_iter()
145    }
146
147    #[doc(hidden)]
148    pub fn node_count(&self) -> usize {
149        self.0.cell_count()
150    }
151
152    #[doc(hidden)]
153    pub fn draining_iterator(
154        mut self,
155        // default: UnrolledList<T, P, N, G>,
156    ) -> impl Iterator<Item = T> {
157        std::mem::take(&mut self.0).draining_iterator()
158        // std::mem::replace(&mut self.0, default).draining_iterator()
159        // todo!()
160        // let x = MaybeUninit::new(self);
161        // let x = x.as_ptr();
162
163        // unsafe { std::ptr::read(&(*x).0).draining_iterator() }
164
165        // self.0.draining_iterator()
166        // ManuallyDrop::take(slot)
167        // todo!()
168    }
169
170    #[doc(hidden)]
171    pub fn nodes(&self) -> Vec<Self> {
172        self.0
173            .node_iter()
174            .map(|x| {
175                let mut x = x.clone();
176                P::make_mut(&mut x.0).next = None;
177                Self(x, PhantomData)
178            })
179            .collect()
180    }
181
182    #[doc(hidden)]
183    pub fn as_ptr(&self) -> RawCell<T, P, N, G, D> {
184        RawCell(self.0.as_ptr(), PhantomData)
185    }
186
187    /// Call a function on a raw pointer
188    /// # Safety
189    /// This must be called with a valid pointer as returned from as_ptr
190    #[doc(hidden)]
191    pub unsafe fn call_from_raw<O, F: FnOnce(&Self) -> O>(
192        cell: RawCell<T, P, N, G, D>,
193        func: F,
194    ) -> O {
195        let value = unsafe { Self::from_raw(cell) };
196        let res = func(&value);
197        std::mem::forget(value);
198        res
199    }
200
201    /// # Safety
202    /// This must be called with a valid pointer as returned from as_ptr
203    #[doc(hidden)]
204    unsafe fn from_raw(cell: RawCell<T, P, N, G, D>) -> Self {
205        Self(UnrolledList(P::from_raw(cell.0)), PhantomData)
206    }
207
208    /// Get the length of the list
209    ///
210    /// # Examples
211    ///
212    /// ```
213    /// # #[macro_use] extern crate im_lists;
214    /// # use im_lists::list;
215    /// let list = list![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
216    /// assert_eq!(list.len(), 10);
217    /// ```
218    pub fn len(&self) -> usize {
219        self.0.len()
220    }
221
222    /// Reverses the input list and returns a new list
223    ///
224    /// # Examples
225    ///
226    /// ```
227    /// # #[macro_use] extern crate im_lists;
228    /// # use im_lists::list;
229    /// let list = list![1, 2, 3, 4, 5].reverse();
230    /// assert_eq!(list, list![5, 4, 3, 2, 1])
231    /// ```
232    pub fn reverse(mut self) -> Self {
233        self.0 = std::mem::take(&mut self.0).reverse();
234        self
235    }
236
237    /// Get the last element of the list.
238    /// Returns None if the list is empty.
239    ///
240    /// # Examples
241    ///
242    /// ```
243    /// # #[macro_use] extern crate im_lists;
244    /// # use im_lists::list;
245    /// let list = list![1, 2, 3, 4, 5];
246    /// assert_eq!(list.last().cloned(), Some(5));
247    /// ```
248    pub fn last(&self) -> Option<&T> {
249        self.0.last()
250    }
251
252    /// Get the first element of the list.
253    /// Returns None if the list is empty.
254    ///
255    /// # Examples
256    ///
257    /// ```
258    /// # #[macro_use] extern crate im_lists;
259    /// # use im_lists::list;
260    /// # use im_lists::list::List;
261    /// let list = list![1, 2, 3, 4, 5];
262    /// let car = list.car();
263    /// assert_eq!(car, Some(1));
264    ///
265    /// let list: List<usize> = list![];
266    /// let car = list.car();
267    /// assert!(car.is_none());
268    /// ```
269    pub fn car(&self) -> Option<T> {
270        self.0.car()
271    }
272
273    /// Returns a reference to the first element of the list.
274    /// Returns None if the list is empty.
275    ///
276    /// # Examples
277    ///
278    /// ```
279    /// # #[macro_use] extern crate im_lists;
280    /// # use im_lists::list;
281    /// # use im_lists::list::List;
282    /// let list = list![1, 2, 3, 4, 5];
283    /// let first = list.first().cloned();
284    /// assert_eq!(first, Some(1));
285    ///
286    /// let list: List<usize> = list![];
287    /// let first = list.first();
288    /// assert!(first.is_none());
289    /// ```
290    pub fn first(&self) -> Option<&T> {
291        self.get(0)
292    }
293
294    /// Get the "rest" of the elements as a list, excluding the first element
295    ///
296    /// # Examples
297    ///
298    /// ```
299    /// # #[macro_use] extern crate im_lists;
300    /// # use im_lists::list;
301    /// let list = list![1, 2, 3, 4, 5];
302    /// let cdr = list.cdr().unwrap();
303    /// assert_eq!(cdr, list![2, 3, 4, 5]);
304    ///
305    /// let list = list![5];
306    /// let cdr = list.cdr();
307    /// assert!(cdr.is_none());
308    /// ```
309    pub fn cdr(&self) -> Option<GenericList<T, P, N, G, D>> {
310        self.0.cdr().map(|x| GenericList(x, PhantomData))
311    }
312
313    /// Get the "rest" of the elements as a list.
314    /// Alias for [`cdr`](crate::list::List::cdr)
315    pub fn rest(&self) -> Option<GenericList<T, P, N, G, D>> {
316        self.cdr()
317    }
318
319    /// Gets the cdr of the list, mutably.
320    /// Returns None if the next is empty - otherwise updates self to be the rest
321    ///
322    /// # Examples
323    ///
324    /// ```
325    /// # #[macro_use] extern crate im_lists;
326    /// # use im_lists::list;
327    /// let mut list = list![1, 2, 3, 4, 5];
328    /// list.cdr_mut().expect("This list has a tail");
329    /// assert_eq!(list, list![2, 3, 4, 5]);
330    ///
331    ///
332    /// let mut list = list![1, 2, 3];
333    /// assert!(list.cdr_mut().is_some());
334    /// assert_eq!(list, list![2, 3]);
335    /// assert!(list.cdr_mut().is_some());
336    /// assert_eq!(list, list![3]);
337    /// assert!(list.cdr_mut().is_none());
338    /// assert_eq!(list, list![]);
339    /// ```
340    pub fn cdr_mut(&mut self) -> Option<&mut Self> {
341        match self.0.cdr_mut() {
342            Some(_) => Some(self),
343            None => None,
344        }
345    }
346
347    #[doc(hidden)]
348    pub fn cdr_exists(&self) -> bool {
349        self.0.cdr_exists()
350    }
351
352    /// Gets the rest of the list, mutably.
353    /// Alias for [`cdr_mut`](crate::list::List::cdr_mut)
354    pub fn rest_mut(&mut self) -> Option<&mut Self> {
355        self.cdr_mut()
356    }
357
358    /// Pushes an element onto the front of the list, returning a new list
359    ///
360    /// # Examples
361    ///
362    /// ```
363    /// # #[macro_use] extern crate im_lists;
364    /// # use im_lists::list::List;
365    /// let list = List::cons(1, List::cons(2, List::cons(3, List::cons(4, List::new()))));
366    /// assert_eq!(list, list![1, 2, 3, 4]);
367    /// ```
368    pub fn cons(value: T, mut other: GenericList<T, P, N, G, D>) -> GenericList<T, P, N, G, D> {
369        Self(
370            UnrolledList::cons(value, std::mem::take(&mut other.0)),
371            PhantomData,
372        )
373    }
374
375    /// Mutably pushes an element onto the front of the list, in place
376    ///
377    /// # Examples
378    ///
379    /// ```
380    /// # #[macro_use] extern crate im_lists;
381    /// # use im_lists::list;
382    /// let mut list = list![];
383    /// list.cons_mut(3);
384    /// list.cons_mut(2);
385    /// list.cons_mut(1);
386    /// list.cons_mut(0);
387    /// assert_eq!(list, list![0, 1, 2, 3])
388    /// ```
389    pub fn cons_mut(&mut self, value: T) {
390        self.0.cons_mut(value)
391    }
392
393    /// Alias for cons_mut
394    ///
395    /// # Examples
396    ///
397    /// ```
398    /// # #[macro_use] extern crate im_lists;
399    /// # use im_lists::list;
400    /// let mut list = list![];
401    /// list.push_front(3);
402    /// list.push_front(2);
403    /// list.push_front(1);
404    /// list.push_front(0);
405    /// assert_eq!(list, list![0, 1, 2, 3])
406    /// ```
407    pub fn push_front(&mut self, value: T) {
408        self.0.push_front(value)
409    }
410
411    /// Mutably pop the first value off of the list
412    ///
413    /// # Examples
414    ///
415    /// ```
416    /// # #[macro_use] extern crate im_lists;
417    /// # use im_lists::list;
418    /// let mut list = list![1, 2, 3];
419    /// assert_eq!(list.pop_front().unwrap(), 1);
420    /// assert_eq!(list.pop_front().unwrap(), 2);
421    /// assert_eq!(list.pop_front().unwrap(), 3);
422    /// assert!(list.pop_front().is_none())
423    /// ```
424    pub fn pop_front(&mut self) -> Option<T> {
425        self.0.pop_front()
426    }
427
428    /// Push one value to the back of the list
429    ///
430    /// Time: O(n)
431    ///
432    /// # Examples
433    /// ```
434    /// # #[macro_use] extern crate im_lists;
435    /// # use im_lists::list;
436    /// let mut list = list![];
437    /// list.push_back(0);
438    /// list.push_back(1);
439    /// list.push_back(2);
440    /// list.push_back(3);
441    /// assert_eq!(list, list![0, 1, 2, 3])
442    /// ```
443    pub fn push_back(&mut self, value: T) {
444        self.0.push_back(value)
445    }
446
447    /// Construct a new list from the first `count` elements from the current list
448    ///
449    /// # Examples
450    /// ```
451    /// # #[macro_use] extern crate im_lists;
452    /// # use im_lists::list;
453    /// let list = list![0, 1, 2, 3, 4, 5];
454    /// let new_list = list.take(3);
455    /// assert_eq!(new_list, list![0, 1, 2]);
456    /// ```
457    pub fn take(&self, count: usize) -> Self {
458        GenericList(self.0.take(count), PhantomData)
459    }
460
461    /// Returns the list after the first `len` elements of lst.
462    /// If the list has fewer then `len` elements, then this returns `None`.
463    ///
464    /// # Examples
465    /// ```
466    /// # #[macro_use] extern crate im_lists;
467    /// # use im_lists::list;
468    /// let list = list![0, 1, 2, 3, 4, 5];
469    /// let new_list = list.tail(2);
470    /// assert_eq!(new_list.unwrap(), list![2, 3, 4, 5]);
471    ///
472    /// let no_list = list.tail(100);
473    /// assert!(no_list.is_none())
474    /// ```
475    pub fn tail(&self, len: usize) -> Option<Self> {
476        self.0.tail(len).map(|x| GenericList(x, PhantomData))
477    }
478
479    /// Constructs an iterator over the list
480    pub fn iter(&self) -> impl Iterator<Item = &'_ T> {
481        self.0.iter()
482    }
483
484    /// Get a reference to the value at index `index` in a list.
485    /// Returns `None` if the index is out of bounds.
486    pub fn get(&self, index: usize) -> Option<&T> {
487        self.0.get(index)
488    }
489
490    /// Append the list `other` to the end of the current list. Returns a new list.
491    ///
492    /// # Examples
493    ///
494    /// ```
495    /// # #[macro_use] extern crate im_lists;
496    /// # use im_lists::list;
497    /// let left = list![1usize, 2, 3];
498    /// let right = list![4usize, 5, 6];
499    /// assert_eq!(left.append(right), list![1, 2, 3, 4, 5, 6])
500    /// ```
501    pub fn append(mut self, mut other: Self) -> Self {
502        GenericList(
503            std::mem::take(&mut self.0).append(std::mem::take(&mut other.0)),
504            PhantomData,
505        )
506    }
507
508    /// Append the list 'other' to the end of the current list in place.
509    ///
510    /// # Examples
511    ///
512    /// ```
513    /// # #[macro_use] extern crate im_lists;
514    /// # use im_lists::list;
515    /// let mut left = list![1usize, 2, 3];
516    /// let right = list![4usize, 5, 6];
517    /// left.append_mut(right);
518    /// assert_eq!(left, list![1, 2, 3, 4, 5, 6])
519    /// ```
520    pub fn append_mut(&mut self, mut other: Self) {
521        self.0.append_mut(std::mem::take(&mut other.0));
522    }
523
524    /// Checks whether a list is empty
525    ///
526    /// # Examples
527    /// ```
528    /// # #[macro_use] extern crate im_lists;
529    /// # use im_lists::list;
530    /// # use im_lists::list::List;
531    /// let mut list = List::new();
532    /// assert!(list.is_empty());
533    /// list.cons_mut("applesauce");
534    /// assert!(!list.is_empty());
535    /// ```
536    pub fn is_empty(&self) -> bool {
537        self.0.is_empty()
538    }
539
540    /// Sorts the list
541    ///
542    /// # Examples
543    /// ```
544    /// # #[macro_use] extern crate im_lists;
545    /// # use im_lists::list;
546    /// let mut list = list![4, 2, 6, 3, 1, 5];
547    /// list.sort();
548    /// assert_eq!(list, list![1, 2, 3, 4, 5, 6]);
549    /// ```
550    pub fn sort(&mut self)
551    where
552        T: Ord,
553    {
554        self.0.sort()
555    }
556
557    /// Sorts the list according to the ordering
558    ///
559    /// # Examples
560    /// ```
561    /// # #[macro_use] extern crate im_lists;
562    /// # use im_lists::list;
563    /// let mut list = list![4, 2, 6, 3, 1, 5];
564    /// list.sort_by(Ord::cmp);
565    /// assert_eq!(list, list![1, 2, 3, 4, 5, 6]);
566    /// ```
567    pub fn sort_by<F>(&mut self, cmp: F)
568    where
569        F: Fn(&T, &T) -> Ordering,
570    {
571        self.0.sort_by(cmp)
572    }
573}
574
575impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> Default
576    for GenericList<T, P, N, G, D>
577{
578    fn default() -> Self {
579        Self::new()
580    }
581}
582
583impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> Extend<T>
584    for GenericList<T, P, N, G, D>
585{
586    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
587        self.append_mut(iter.into_iter().collect())
588    }
589}
590
591// and we'll implement FromIterator
592impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>>
593    FromIterator<T> for GenericList<T, P, N, G, D>
594{
595    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
596        GenericList(iter.into_iter().collect(), PhantomData)
597    }
598}
599
600impl<'a, T: 'a + Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>>
601    FromIterator<&'a T> for GenericList<T, P, N, G, D>
602{
603    fn from_iter<I: IntoIterator<Item = &'a T>>(iter: I) -> Self {
604        GenericList(iter.into_iter().cloned().collect(), PhantomData)
605    }
606}
607
608impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>>
609    FromIterator<GenericList<T, P, N, G, D>> for GenericList<T, P, N, G, D>
610{
611    fn from_iter<I: IntoIterator<Item = GenericList<T, P, N, G, D>>>(iter: I) -> Self {
612        GenericList(
613            iter.into_iter()
614                .flat_map(|mut x| std::mem::take(&mut x.0).into_node_iter())
615                .collect(),
616            PhantomData,
617        )
618    }
619}
620
621impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> From<Vec<T>>
622    for GenericList<T, P, N, G, D>
623{
624    fn from(vec: Vec<T>) -> Self {
625        GenericList(vec.into_iter().collect(), PhantomData)
626    }
627}
628
629impl<
630        T: Clone + std::fmt::Debug,
631        P: PointerFamily,
632        const N: usize,
633        const G: usize,
634        D: DropHandler<Self>,
635    > std::fmt::Debug for GenericList<T, P, N, G, D>
636{
637    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
638        f.debug_list().entries(self).finish()
639    }
640}
641
642/// An iterator over lists with values of type `T`.
643pub struct Iter<
644    'a,
645    T: Clone + 'static,
646    P: PointerFamily,
647    const N: usize,
648    const G: usize,
649    D: DropHandler<GenericList<T, P, N, G, D>>,
650>(IterWrapper<'a, T, P, N, G>, PhantomData<D>);
651
652impl<
653        'a,
654        T: Clone + 'static,
655        P: PointerFamily,
656        const N: usize,
657        const G: usize,
658        D: DropHandler<GenericList<T, P, N, G, D>>,
659    > Iterator for Iter<'a, T, P, N, G, D>
660{
661    type Item = &'a T;
662
663    #[inline(always)]
664    fn next(&mut self) -> Option<Self::Item> {
665        self.0.next()
666    }
667
668    #[inline(always)]
669    fn size_hint(&self) -> (usize, Option<usize>) {
670        self.0.size_hint()
671    }
672
673    #[inline(always)]
674    fn fold<B, F>(self, init: B, f: F) -> B
675    where
676        Self: Sized,
677        F: FnMut(B, Self::Item) -> B,
678    {
679        self.0.fold(init, f)
680    }
681}
682
683impl<
684        'a,
685        T: Clone,
686        P: PointerFamily,
687        const N: usize,
688        const G: usize,
689        D: DropHandler<GenericList<T, P, N, G, D>>,
690    > IntoIterator for &'a GenericList<T, P, N, G, D>
691{
692    type Item = &'a T;
693    type IntoIter = Iter<'a, T, P, N, G, D>;
694
695    #[inline(always)]
696    fn into_iter(self) -> Self::IntoIter {
697        Iter((&self.0).into_iter(), PhantomData)
698    }
699}
700
701/// A consuming iterator over lists with values of type `T`.
702pub struct ConsumingIter<
703    T: Clone + 'static,
704    P: PointerFamily,
705    const N: usize,
706    const G: usize,
707    D: DropHandler<GenericList<T, P, N, G, D>>,
708>(ConsumingWrapper<T, P, N, G>, PhantomData<D>);
709
710impl<
711        T: Clone,
712        P: PointerFamily,
713        const N: usize,
714        const G: usize,
715        D: DropHandler<GenericList<T, P, N, G, D>>,
716    > Iterator for ConsumingIter<T, P, N, G, D>
717{
718    type Item = T;
719
720    #[inline(always)]
721    fn next(&mut self) -> Option<Self::Item> {
722        self.0.next()
723    }
724
725    #[inline(always)]
726    fn size_hint(&self) -> (usize, Option<usize>) {
727        self.0.size_hint()
728    }
729
730    #[inline(always)]
731    fn fold<B, F>(self, init: B, f: F) -> B
732    where
733        Self: Sized,
734        F: FnMut(B, Self::Item) -> B,
735    {
736        self.0.fold(init, f)
737    }
738}
739
740impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> IntoIterator
741    for GenericList<T, P, N, G, D>
742{
743    type Item = T;
744    type IntoIter = ConsumingIter<T, P, N, G, D>;
745
746    #[inline(always)]
747    fn into_iter(mut self) -> Self::IntoIter {
748        ConsumingIter(std::mem::take(&mut self.0).into_iter(), PhantomData)
749    }
750}
751
752impl<
753        'a,
754        T: 'a + Clone,
755        P: 'a + PointerFamily,
756        const N: usize,
757        const G: usize,
758        D: 'a + DropHandler<Self>,
759    > FromIterator<&'a GenericList<T, P, N, G, D>> for GenericList<T, P, N, G, D>
760{
761    fn from_iter<I: IntoIterator<Item = &'a GenericList<T, P, N, G, D>>>(iter: I) -> Self {
762        iter.into_iter().cloned().collect()
763    }
764}
765
766impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> From<&[T]>
767    for GenericList<T, P, N, G, D>
768{
769    fn from(vec: &[T]) -> Self {
770        vec.iter().cloned().collect()
771    }
772}
773
774impl<
775        T: Clone + PartialEq,
776        P: PointerFamily,
777        const N: usize,
778        const G: usize,
779        D: DropHandler<Self>,
780    > PartialEq for GenericList<T, P, N, G, D>
781{
782    fn eq(&self, other: &Self) -> bool {
783        self.iter().eq(other.iter())
784    }
785}
786
787impl<T: Clone + Eq, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> Eq
788    for GenericList<T, P, N, G, D>
789{
790}
791
792impl<
793        T: Clone + PartialOrd,
794        P: PointerFamily,
795        const N: usize,
796        const G: usize,
797        D: DropHandler<Self>,
798    > PartialOrd for GenericList<T, P, N, G, D>
799{
800    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
801        self.iter().partial_cmp(other.iter())
802    }
803}
804
805impl<T: Clone + Ord, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> Ord
806    for GenericList<T, P, N, G, D>
807{
808    fn cmp(&self, other: &Self) -> Ordering {
809        self.iter().cmp(other.iter())
810    }
811}
812
813impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> std::ops::Add
814    for GenericList<T, P, N, G, D>
815{
816    type Output = GenericList<T, P, N, G, D>;
817
818    /// Concatenate two lists
819    fn add(self, other: Self) -> Self::Output {
820        self.append(other)
821    }
822}
823
824impl<
825        T: Clone,
826        P: PointerFamily,
827        const N: usize,
828        const G: usize,
829        D: DropHandler<GenericList<T, P, N, G, D>>,
830    > std::ops::Add for &GenericList<T, P, N, G, D>
831{
832    type Output = GenericList<T, P, N, G, D>;
833
834    /// Concatenate two lists
835    fn add(self, other: Self) -> Self::Output {
836        self.clone().append(other.clone())
837    }
838}
839
840impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>>
841    std::iter::Sum for GenericList<T, P, N, G, D>
842{
843    fn sum<I>(it: I) -> Self
844    where
845        I: Iterator<Item = Self>,
846    {
847        it.fold(Self::new(), |a, b| a + b)
848    }
849}
850
851impl<
852        T: Clone + std::hash::Hash,
853        P: PointerFamily,
854        const N: usize,
855        const G: usize,
856        D: DropHandler<Self>,
857    > std::hash::Hash for GenericList<T, P, N, G, D>
858{
859    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
860        for i in self {
861            i.hash(state)
862        }
863    }
864}
865
866impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>>
867    std::ops::Index<usize> for GenericList<T, P, N, G, D>
868{
869    type Output = T;
870    /// Get a reference to the value at index `index` in the vector.
871    ///
872    /// Time: O(log n)
873    fn index(&self, index: usize) -> &Self::Output {
874        match self.get(index) {
875            Some(value) => value,
876            None => panic!(
877                "{}::index: index out of bounds: {} < {}",
878                stringify!($list),
879                index,
880                self.len()
881            ),
882        }
883    }
884}
885
886impl<T: Clone, P: PointerFamily, const N: usize, const G: usize, D: DropHandler<Self>> Drop
887    for GenericList<T, P, N, G, D>
888{
889    fn drop(&mut self) {
890        D::drop_handler(self)
891    }
892}
893
894#[cfg(test)]
895mod tests {
896
897    use std::ops::Add;
898
899    use super::*;
900    use crate::{list, vlist};
901
902    #[test]
903    fn strong_count_empty() {
904        let list: List<usize> = List::new();
905        assert!(list.strong_count() >= 1);
906    }
907
908    #[test]
909    fn strong_count() {
910        let mut list: List<usize> = List::new();
911        list.cons_mut(1);
912        assert_eq!(list.strong_count(), 1);
913    }
914
915    #[test]
916    fn ptr_eq() {
917        let left: List<usize> = list![1, 2, 3, 4, 5];
918        let right: List<usize> = list![1, 2, 3, 4, 5];
919
920        assert!(!left.ptr_eq(&right));
921
922        let left_clone: List<usize> = left.clone();
923        assert!(left.ptr_eq(&left_clone))
924    }
925
926    #[test]
927    fn cdr_ptr_eq() {
928        let left: List<usize> = list![1, 2, 3, 4, 5];
929
930        let new_right = left.cdr().unwrap();
931        let new_right2 = left.cdr().unwrap();
932
933        assert!(new_right.identity_tuple() == new_right2.identity_tuple());
934    }
935
936    #[test]
937    fn len() {
938        let list = list![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
939        assert_eq!(list.len(), 10);
940    }
941
942    #[test]
943    fn reverse() {
944        let list = list![1, 2, 3, 4, 5].reverse();
945        assert_eq!(list, list![5, 4, 3, 2, 1]);
946    }
947
948    #[test]
949    fn last() {
950        let list = list![1, 2, 3, 4, 5];
951        assert_eq!(list.last().cloned(), Some(5));
952    }
953
954    #[test]
955    fn car() {
956        let list = list![1, 2, 3, 4, 5];
957        let car = list.car();
958        assert_eq!(car, Some(1));
959
960        let list: List<usize> = list![];
961        let car = list.car();
962        assert!(car.is_none());
963    }
964
965    #[test]
966    fn first() {
967        let list = list![1, 2, 3, 4, 5];
968        let car = list.first();
969        assert_eq!(car.cloned(), Some(1));
970
971        let list: List<usize> = list![];
972        let car = list.first();
973        assert!(car.is_none());
974    }
975
976    #[test]
977    fn cdr() {
978        let list = list![1, 2, 3, 4, 5];
979        let cdr = list.cdr().unwrap();
980        assert_eq!(cdr, list![2, 3, 4, 5]);
981        let list = list![5];
982        let cdr = list.cdr();
983        assert!(cdr.is_none());
984    }
985
986    #[test]
987    fn cdr_mut() {
988        let mut list = list![1, 2, 3, 4, 5];
989        list.cdr_mut().expect("This list has a tail");
990        assert_eq!(list, list![2, 3, 4, 5]);
991
992        let mut list = list![1, 2, 3];
993        assert!(list.cdr_mut().is_some());
994        assert_eq!(list, list![2, 3]);
995        assert!(list.cdr_mut().is_some());
996        assert_eq!(list, list![3]);
997        assert!(list.cdr_mut().is_none());
998        assert_eq!(list, list![]);
999    }
1000
1001    #[test]
1002    fn rest_mut() {
1003        let mut list = list![1, 2, 3, 4, 5];
1004        list.rest_mut().expect("This list has a tail");
1005        assert_eq!(list, list![2, 3, 4, 5]);
1006
1007        let mut list = list![1, 2, 3];
1008        assert!(list.rest_mut().is_some());
1009        assert_eq!(list, list![2, 3]);
1010        assert!(list.rest_mut().is_some());
1011        assert_eq!(list, list![3]);
1012        assert!(list.rest_mut().is_none());
1013        assert_eq!(list, list![]);
1014    }
1015
1016    #[test]
1017    fn cons() {
1018        let list = List::cons(1, List::cons(2, List::cons(3, List::cons(4, List::new()))));
1019        assert_eq!(list, list![1, 2, 3, 4]);
1020    }
1021
1022    #[test]
1023    fn cons_mut() {
1024        let mut list = list![];
1025        list.cons_mut(3);
1026        list.cons_mut(2);
1027        list.cons_mut(1);
1028        list.cons_mut(0);
1029        assert_eq!(list, list![0, 1, 2, 3])
1030    }
1031
1032    #[test]
1033    fn push_front() {
1034        let mut list = list![];
1035        list.push_front(3);
1036        list.push_front(2);
1037        list.push_front(1);
1038        list.push_front(0);
1039        assert_eq!(list, list![0, 1, 2, 3])
1040    }
1041
1042    #[test]
1043    fn iter() {
1044        assert_eq!(list![1usize, 1, 1, 1, 1].iter().sum::<usize>(), 5);
1045    }
1046
1047    #[test]
1048    fn get() {
1049        let list = list![1, 2, 3, 4, 5];
1050        assert_eq!(list.get(3).cloned(), Some(4));
1051        assert!(list.get(1000).is_none());
1052    }
1053
1054    #[test]
1055    fn append() {
1056        let left = list![1usize, 2, 3];
1057        let right = list![4usize, 5, 6];
1058        assert_eq!(left.append(right), list![1, 2, 3, 4, 5, 6])
1059    }
1060
1061    #[test]
1062    fn append_mut() {
1063        let mut left = list![1usize, 2, 3];
1064        let right = list![4usize, 5, 6];
1065        left.append_mut(right);
1066        assert_eq!(left, list![1, 2, 3, 4, 5, 6])
1067    }
1068
1069    #[test]
1070    fn is_empty() {
1071        let mut list = List::new();
1072        assert!(list.is_empty());
1073        list.cons_mut("applesauce");
1074        assert!(!list.is_empty());
1075    }
1076
1077    #[test]
1078    fn extend() {
1079        let mut list = list![1usize, 2, 3];
1080        let vec = vec![4, 5, 6];
1081        list.extend(vec);
1082        assert_eq!(list, list![1, 2, 3, 4, 5, 6])
1083    }
1084
1085    #[test]
1086    fn sort() {
1087        let mut list = list![5, 4, 3, 2, 1];
1088        list.sort();
1089        assert_eq!(list, list![1, 2, 3, 4, 5]);
1090    }
1091
1092    #[test]
1093    fn sort_by() {
1094        let mut list = list![5, 4, 3, 2, 1];
1095        list.sort_by(Ord::cmp);
1096        assert_eq!(list, list![1, 2, 3, 4, 5]);
1097    }
1098
1099    #[test]
1100    fn push_back() {
1101        let mut list = list![];
1102        list.push_back(0);
1103        list.push_back(1);
1104        list.push_back(2);
1105        assert_eq!(list, list![0, 1, 2]);
1106    }
1107
1108    #[test]
1109    fn add() {
1110        let left = list![1, 2, 3, 4, 5];
1111        let right = list![6, 7, 8, 9, 10];
1112
1113        assert_eq!(left + right, list![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
1114    }
1115
1116    #[test]
1117    fn sum() {
1118        let list = vec![list![1, 2, 3], list![4, 5, 6], list![7, 8, 9]];
1119        assert_eq!(
1120            list.into_iter().sum::<List<_>>(),
1121            list![1, 2, 3, 4, 5, 6, 7, 8, 9]
1122        );
1123    }
1124
1125    #[test]
1126    fn take() {
1127        let list = list![0, 1, 2, 3, 4, 5];
1128        let new_list = list.take(3);
1129        assert_eq!(new_list, list![0, 1, 2]);
1130    }
1131
1132    #[test]
1133    fn tail() {
1134        let list = list![0, 1, 2, 3, 4, 5];
1135        let new_list = list.tail(2);
1136        assert_eq!(new_list.unwrap(), list![2, 3, 4, 5]);
1137
1138        let no_list = list.tail(100);
1139        assert!(no_list.is_none())
1140    }
1141
1142    #[test]
1143    fn take_after_cdr() {
1144        let list = list![0, 1, 2, 3, 4, 5];
1145        let rest = list.rest().unwrap();
1146
1147        assert_eq!(rest.take(3), list![1, 2, 3]);
1148    }
1149
1150    #[test]
1151    fn tail_after_cdr() {
1152        let list = list![0, 1, 2, 3, 4, 5];
1153        let rest = list.rest().unwrap();
1154
1155        assert_eq!(rest.tail(2).unwrap(), list![3, 4, 5]);
1156    }
1157
1158    #[test]
1159    fn indexing() {
1160        let list = vlist![0, 1, 2, 3, 4, 5];
1161
1162        assert_eq!(4, list[4]);
1163    }
1164
1165    #[test]
1166    fn hash() {
1167        let mut map = std::collections::HashMap::new();
1168
1169        map.insert(vlist![0, 1, 2, 3, 4, 5], "hello world!");
1170
1171        assert_eq!(
1172            map.get(&vlist![0, 1, 2, 3, 4, 5]).copied(),
1173            Some("hello world!")
1174        );
1175    }
1176
1177    #[test]
1178    fn addition() {
1179        let l = vlist![0, 1, 2, 3, 4, 5];
1180        let r = vlist![6, 7, 8, 9, 10];
1181
1182        let combined = l.clone() + r.clone();
1183
1184        assert_eq!(combined, vlist![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
1185
1186        let combined = l.add(r);
1187
1188        assert_eq!(combined, vlist![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
1189    }
1190
1191    #[test]
1192    fn from_slice() {
1193        let slice: &[usize] = &[0, 1, 2, 3, 4, 5];
1194        let list: VList<usize> = vlist![0, 1, 2, 3, 4, 5];
1195
1196        assert_eq!(list, slice.into());
1197    }
1198
1199    #[test]
1200    #[should_panic]
1201    fn index_out_of_bounds() {
1202        let list: VList<usize> = vlist![0, 1, 2, 3, 4];
1203
1204        list[5];
1205    }
1206
1207    #[test]
1208    fn ordering() {
1209        let l: VList<usize> = vlist![0, 1, 2, 3, 4];
1210        let r: VList<usize> = vlist![1, 2, 3, 4, 5];
1211
1212        assert!(l < r);
1213    }
1214
1215    #[test]
1216    fn from_iterator() {
1217        let iter = vec![
1218            vlist![0, 1, 2, 3, 4],
1219            vlist![0, 1, 2, 3, 4],
1220            vlist![0, 1, 2, 3, 4],
1221        ];
1222
1223        let combined = iter.iter().collect::<VList<usize>>();
1224
1225        assert_eq!(
1226            combined,
1227            vlist![0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4]
1228        );
1229    }
1230
1231    #[test]
1232    fn from_iterator_group_lists() {
1233        let iter = vec![
1234            vlist![0, 1, 2, 3, 4],
1235            vlist![0, 1, 2, 3, 4],
1236            vlist![0, 1, 2, 3, 4],
1237        ];
1238
1239        let combined = iter.iter().collect::<VList<VList<usize>>>();
1240
1241        assert_eq!(
1242            combined,
1243            vlist![
1244                vlist![0, 1, 2, 3, 4],
1245                vlist![0, 1, 2, 3, 4],
1246                vlist![0, 1, 2, 3, 4]
1247            ]
1248        );
1249    }
1250
1251    #[test]
1252    fn to_string_works_as_intended() {
1253        let list = vlist![1, 2, 3, 4, 5];
1254
1255        assert_eq!("[1, 2, 3, 4, 5]", format!("{:?}", list));
1256    }
1257
1258    #[test]
1259    fn cons_grows_as_expected() {
1260        let list = vlist![1, 2];
1261
1262        let list = VList::cons(0, list);
1263
1264        assert_eq!(vlist![0, 1, 2], list);
1265        assert_eq!(2, list.0.node_iter().count());
1266    }
1267}
1268
1269#[cfg(test)]
1270mod arc_tests {
1271
1272    use std::ops::Add;
1273
1274    use super::*;
1275    use crate::{shared_list, shared_vlist, vlist};
1276
1277    #[test]
1278    fn strong_count_empty() {
1279        let list: SharedList<usize> = SharedList::new();
1280        assert!(list.strong_count() >= 1);
1281    }
1282
1283    #[test]
1284    fn strong_count() {
1285        let mut list: SharedList<usize> = SharedList::new();
1286        list.cons_mut(1);
1287        assert_eq!(list.strong_count(), 1);
1288    }
1289
1290    #[test]
1291    fn ptr_eq() {
1292        let left: SharedList<usize> = shared_list![1, 2, 3, 4, 5];
1293        let right: SharedList<usize> = shared_list![1, 2, 3, 4, 5];
1294
1295        assert!(!left.ptr_eq(&right));
1296
1297        let left_clone: SharedList<usize> = left.clone();
1298        assert!(left.ptr_eq(&left_clone))
1299    }
1300
1301    #[test]
1302    fn len() {
1303        let list = shared_list![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1304        assert_eq!(list.len(), 10);
1305    }
1306
1307    #[test]
1308    fn reverse() {
1309        let list = shared_list![1, 2, 3, 4, 5].reverse();
1310        assert_eq!(list, shared_list![5, 4, 3, 2, 1]);
1311    }
1312
1313    #[test]
1314    fn last() {
1315        let list = shared_list![1, 2, 3, 4, 5];
1316        assert_eq!(list.last().cloned(), Some(5));
1317    }
1318
1319    #[test]
1320    fn car() {
1321        let list = shared_list![1, 2, 3, 4, 5];
1322        let car = list.car();
1323        assert_eq!(car, Some(1));
1324
1325        let list: SharedList<usize> = shared_list![];
1326        let car = list.car();
1327        assert!(car.is_none());
1328    }
1329
1330    #[test]
1331    fn first() {
1332        let list = shared_list![1, 2, 3, 4, 5];
1333        let car = list.first();
1334        assert_eq!(car.cloned(), Some(1));
1335
1336        let list: SharedList<usize> = shared_list![];
1337        let car = list.first();
1338        assert!(car.is_none());
1339    }
1340
1341    #[test]
1342    fn cdr() {
1343        let list = shared_list![1, 2, 3, 4, 5];
1344        let cdr = list.cdr().unwrap();
1345        assert_eq!(cdr, shared_list![2, 3, 4, 5]);
1346        let list = shared_list![5];
1347        let cdr = list.cdr();
1348        assert!(cdr.is_none());
1349    }
1350
1351    #[test]
1352    fn cdr_mut() {
1353        let mut list = shared_list![1, 2, 3, 4, 5];
1354        list.cdr_mut().expect("This list has a tail");
1355        assert_eq!(list, shared_list![2, 3, 4, 5]);
1356
1357        let mut list = shared_list![1, 2, 3];
1358        assert!(list.cdr_mut().is_some());
1359        assert_eq!(list, shared_list![2, 3]);
1360        assert!(list.cdr_mut().is_some());
1361        assert_eq!(list, shared_list![3]);
1362        assert!(list.cdr_mut().is_none());
1363        assert_eq!(list, shared_list![]);
1364    }
1365
1366    #[test]
1367    fn rest_mut() {
1368        let mut list = shared_list![1, 2, 3, 4, 5];
1369        list.rest_mut().expect("This list has a tail");
1370        assert_eq!(list, shared_list![2, 3, 4, 5]);
1371
1372        let mut list = shared_list![1, 2, 3];
1373        assert!(list.rest_mut().is_some());
1374        assert_eq!(list, shared_list![2, 3]);
1375        assert!(list.rest_mut().is_some());
1376        assert_eq!(list, shared_list![3]);
1377        assert!(list.rest_mut().is_none());
1378        assert_eq!(list, shared_list![]);
1379    }
1380
1381    #[test]
1382    fn cons() {
1383        let list = SharedList::cons(
1384            1,
1385            SharedList::cons(
1386                2,
1387                SharedList::cons(3, SharedList::cons(4, SharedList::new())),
1388            ),
1389        );
1390        assert_eq!(list, shared_list![1, 2, 3, 4]);
1391    }
1392
1393    #[test]
1394    fn cons_mut() {
1395        let mut list = shared_list![];
1396        list.cons_mut(3);
1397        list.cons_mut(2);
1398        list.cons_mut(1);
1399        list.cons_mut(0);
1400        assert_eq!(list, shared_list![0, 1, 2, 3])
1401    }
1402
1403    #[test]
1404    fn push_front() {
1405        let mut list = shared_list![];
1406        list.push_front(3);
1407        list.push_front(2);
1408        list.push_front(1);
1409        list.push_front(0);
1410        assert_eq!(list, shared_list![0, 1, 2, 3])
1411    }
1412
1413    #[test]
1414    fn iter() {
1415        assert_eq!(shared_list![1usize, 1, 1, 1, 1].iter().sum::<usize>(), 5);
1416    }
1417
1418    #[test]
1419    fn get() {
1420        let list = shared_list![1, 2, 3, 4, 5];
1421        assert_eq!(list.get(3).cloned(), Some(4));
1422        assert!(list.get(1000).is_none());
1423    }
1424
1425    #[test]
1426    fn append() {
1427        let left = shared_list![1usize, 2, 3];
1428        let right = shared_list![4usize, 5, 6];
1429        assert_eq!(left.append(right), shared_list![1, 2, 3, 4, 5, 6])
1430    }
1431
1432    #[test]
1433    fn append_mut() {
1434        let mut left = shared_list![1usize, 2, 3];
1435        let right = shared_list![4usize, 5, 6];
1436        left.append_mut(right);
1437        assert_eq!(left, shared_list![1, 2, 3, 4, 5, 6])
1438    }
1439
1440    #[test]
1441    fn is_empty() {
1442        let mut list = List::new();
1443        assert!(list.is_empty());
1444        list.cons_mut("applesauce");
1445        assert!(!list.is_empty());
1446    }
1447
1448    #[test]
1449    fn extend() {
1450        let mut list = shared_list![1usize, 2, 3];
1451        let vec = vec![4, 5, 6];
1452        list.extend(vec);
1453        assert_eq!(list, shared_list![1, 2, 3, 4, 5, 6])
1454    }
1455
1456    #[test]
1457    fn sort() {
1458        let mut list = shared_list![5, 4, 3, 2, 1];
1459        list.sort();
1460        assert_eq!(list, shared_list![1, 2, 3, 4, 5]);
1461    }
1462
1463    #[test]
1464    fn sort_by() {
1465        let mut list = shared_list![5, 4, 3, 2, 1];
1466        list.sort_by(Ord::cmp);
1467        assert_eq!(list, shared_list![1, 2, 3, 4, 5]);
1468    }
1469
1470    #[test]
1471    fn push_back() {
1472        let mut list = shared_list![];
1473        list.push_back(0);
1474        list.push_back(1);
1475        list.push_back(2);
1476        assert_eq!(list, shared_list![0, 1, 2]);
1477    }
1478
1479    #[test]
1480    fn add() {
1481        let left = shared_list![1, 2, 3, 4, 5];
1482        let right = shared_list![6, 7, 8, 9, 10];
1483
1484        assert_eq!(left + right, shared_list![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
1485    }
1486
1487    #[test]
1488    fn sum() {
1489        let list = vec![
1490            shared_list![1, 2, 3],
1491            shared_list![4, 5, 6],
1492            shared_list![7, 8, 9],
1493        ];
1494        assert_eq!(
1495            list.into_iter().sum::<SharedList<_>>(),
1496            shared_list![1, 2, 3, 4, 5, 6, 7, 8, 9]
1497        );
1498    }
1499
1500    #[test]
1501    fn take() {
1502        let list = shared_list![0, 1, 2, 3, 4, 5];
1503        let new_list = list.take(3);
1504        assert_eq!(new_list, shared_list![0, 1, 2]);
1505    }
1506
1507    #[test]
1508    fn tail() {
1509        let list = shared_list![0, 1, 2, 3, 4, 5];
1510        let new_list = list.tail(2);
1511        assert_eq!(new_list.unwrap(), shared_list![2, 3, 4, 5]);
1512
1513        let no_list = list.tail(100);
1514        assert!(no_list.is_none())
1515    }
1516
1517    #[test]
1518    fn indexing() {
1519        let list = shared_vlist![0, 1, 2, 3, 4, 5];
1520
1521        assert_eq!(4, list[4]);
1522    }
1523
1524    #[test]
1525    fn hash() {
1526        let mut map = std::collections::HashMap::new();
1527
1528        map.insert(shared_vlist![0, 1, 2, 3, 4, 5], "hello world!");
1529
1530        assert_eq!(
1531            map.get(&shared_vlist![0, 1, 2, 3, 4, 5]).copied(),
1532            Some("hello world!")
1533        );
1534    }
1535
1536    #[test]
1537    fn addition() {
1538        let l = shared_vlist![0, 1, 2, 3, 4, 5];
1539        let r = shared_vlist![6, 7, 8, 9, 10];
1540
1541        let combined = l.clone() + r.clone();
1542
1543        assert_eq!(combined, shared_vlist![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
1544
1545        let combined = l.add(r);
1546
1547        assert_eq!(combined, shared_vlist![0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
1548    }
1549
1550    #[test]
1551    fn from_slice() {
1552        let slice: &[usize] = &[0, 1, 2, 3, 4, 5];
1553        let list: SharedVList<usize> = shared_vlist![0, 1, 2, 3, 4, 5];
1554
1555        assert_eq!(list, slice.into());
1556    }
1557
1558    #[test]
1559    #[should_panic]
1560    fn index_out_of_bounds() {
1561        let list: SharedVList<usize> = shared_vlist![0, 1, 2, 3, 4];
1562
1563        list[5];
1564    }
1565
1566    #[test]
1567    fn ordering() {
1568        let l: SharedVList<usize> = shared_vlist![0, 1, 2, 3, 4];
1569        let r: SharedVList<usize> = shared_vlist![1, 2, 3, 4, 5];
1570
1571        assert!(l < r);
1572    }
1573
1574    #[test]
1575    fn from_iterator() {
1576        let iter = vec![
1577            shared_vlist![0, 1, 2, 3, 4],
1578            shared_vlist![0, 1, 2, 3, 4],
1579            shared_vlist![0, 1, 2, 3, 4],
1580        ];
1581
1582        let combined = iter.iter().collect::<SharedVList<usize>>();
1583
1584        assert_eq!(
1585            combined,
1586            shared_vlist![0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4]
1587        );
1588    }
1589
1590    #[test]
1591    fn from_iterator_group_lists() {
1592        let iter = vec![
1593            shared_vlist![0, 1, 2, 3, 4],
1594            shared_vlist![0, 1, 2, 3, 4],
1595            shared_vlist![0, 1, 2, 3, 4],
1596        ];
1597
1598        let combined = iter.iter().collect::<SharedVList<SharedVList<usize>>>();
1599
1600        assert_eq!(
1601            combined,
1602            shared_vlist![
1603                shared_vlist![0, 1, 2, 3, 4],
1604                shared_vlist![0, 1, 2, 3, 4],
1605                shared_vlist![0, 1, 2, 3, 4]
1606            ]
1607        );
1608    }
1609
1610    #[test]
1611    fn vlist_growth() {
1612        let list = vlist![1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20];
1613
1614        let counts: Vec<_> = list.0.node_iter().map(|x| x.elements().len()).collect();
1615        assert_eq!(vec![6, 8, 4, 2], counts);
1616    }
1617
1618    #[test]
1619    fn consuming_iter_with_no_references() {
1620        let list = vlist![0, 1, 2, 3, 4, 5, 6, 7, 8];
1621
1622        let result = list.draining_iterator().collect::<Vec<_>>();
1623
1624        assert_eq!(vec![0, 1, 2, 3, 4, 5, 6, 7, 8], result);
1625    }
1626
1627    #[test]
1628    fn consuming_iter() {
1629        let list = vlist![0, 1, 2, 3, 4, 5, 6, 7, 8];
1630        let _second_list = list.cdr();
1631
1632        let result = list.draining_iterator().collect::<Vec<_>>();
1633
1634        assert_eq!(Vec::<usize>::new(), result);
1635    }
1636
1637    #[test]
1638    fn list_empty_test() {
1639        let mut list = (0..10000usize).into_iter().collect::<SharedVList<_>>();
1640
1641        for _ in 0..10000 {
1642            list.cdr_mut();
1643
1644            if list.len() == 0 {
1645                assert!(list.is_empty())
1646            } else {
1647                assert!(!list.is_empty())
1648            }
1649        }
1650
1651        // assert!(list.is_empty())
1652    }
1653
1654    #[test]
1655    fn raw_test() {
1656        let list = (0..1000usize).into_iter().collect::<SharedVList<_>>();
1657
1658        // Get the inner pointer, and then otherwise
1659        // call the drop implementation as neatly as possible.
1660        let pointer = list.as_ptr();
1661
1662        // Create value from pointer
1663        let value = unsafe { SharedVList::from_raw(pointer) };
1664        std::mem::forget(value);
1665    }
1666}
im_lists/list.rs

im_lists/
list.rs
