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

im_lists/
list.rs
