linked_list/
lib.rs

1//! # Description
2//!
3//! An alternative implementation of standard `LinkedList` featuring a prototype `Cursor`.
4
5#![no_std]
6
7extern crate alloc;
8
9#[cfg(any(test, feature = "std"))]
10#[cfg_attr(test, macro_use)]
11extern crate std;
12
13use core::cmp::Ordering;
14use core::fmt::{self, Debug};
15use core::hash::{Hash, Hasher};
16use core::iter::FromIterator;
17use core::marker::PhantomData;
18use core::mem;
19use core::ptr::NonNull;
20
21use allocator_api2::{
22    alloc::{Allocator, Global},
23    boxed::Box,
24};
25
26pub struct LinkedList<T, A: Allocator = Global> {
27    front: Link<T>,
28    back: Link<T>,
29    len: usize,
30    alloc: A,
31    _boo: PhantomData<T>,
32}
33
34type Link<T> = Option<NonNull<Node<T>>>;
35
36struct Node<T> {
37    front: Link<T>,
38    back: Link<T>,
39    elem: T,
40}
41
42pub struct Iter<'a, T> {
43    front: Link<T>,
44    back: Link<T>,
45    len: usize,
46    _boo: PhantomData<&'a T>,
47}
48
49pub struct IterMut<'a, T> {
50    front: Link<T>,
51    back: Link<T>,
52    len: usize,
53    _boo: PhantomData<&'a mut T>,
54}
55
56pub struct IntoIter<T, A: Allocator = Global> {
57    list: LinkedList<T, A>,
58}
59
60pub struct CursorMut<'a, T, A: Allocator = Global> {
61    list: &'a mut LinkedList<T, A>,
62    cur: Link<T>,
63    index: Option<usize>,
64}
65
66impl<T> LinkedList<T> {
67    pub fn new() -> Self {
68        Self::new_in(Default::default())
69    }
70}
71
72impl<T, A: Allocator> LinkedList<T, A> {
73    pub fn new_in(alloc: A) -> Self {
74        Self {
75            front: None,
76            back: None,
77            len: 0,
78            alloc,
79            _boo: PhantomData,
80        }
81    }
82
83    pub fn push_front(&mut self, elem: T) {
84        // SAFETY: it's a linked-list, what do you want?
85        unsafe {
86            let new = NonNull::new_unchecked(Box::into_raw(Box::new_in(
87                Node {
88                    front: None,
89                    back: None,
90                    elem,
91                },
92                &self.alloc,
93            )));
94            if let Some(old) = self.front {
95                // Put the new front before the old one
96                (*old.as_ptr()).front = Some(new);
97                (*new.as_ptr()).back = Some(old);
98            } else {
99                // If there's no front, then we're the empty list and need
100                // to set the back too.
101                self.back = Some(new);
102            }
103            // These things always happen!
104            self.front = Some(new);
105            self.len += 1;
106        }
107    }
108
109    pub fn push_back(&mut self, elem: T) {
110        // SAFETY: it's a linked-list, what do you want?
111        unsafe {
112            let new = NonNull::new_unchecked(Box::into_raw(Box::new_in(
113                Node {
114                    back: None,
115                    front: None,
116                    elem,
117                },
118                &self.alloc,
119            )));
120            if let Some(old) = self.back {
121                // Put the new back before the old one
122                (*old.as_ptr()).back = Some(new);
123                (*new.as_ptr()).front = Some(old);
124            } else {
125                // If there's no back, then we're the empty list and need
126                // to set the front too.
127                self.front = Some(new);
128            }
129            // These things always happen!
130            self.back = Some(new);
131            self.len += 1;
132        }
133    }
134
135    pub fn pop_front(&mut self) -> Option<T> {
136        // workaround for a bug in allocator-api2
137        fn into_inner<T, A: Allocator>(boxed: Box<T, A>) -> T {
138            use allocator_api2::alloc::Layout;
139            let (ptr, alloc) = Box::into_raw_with_allocator(boxed);
140            let unboxed = unsafe { ptr.read() };
141            unsafe { alloc.deallocate(NonNull::new(ptr).unwrap().cast(), Layout::new::<T>()) };
142            unboxed
143        }
144
145        unsafe {
146            // Only have to do stuff if there is a front node to pop.
147            self.front.map(|node| {
148                // Bring the Box back to life so we can move out its value and
149                // Drop it (Box continues to magically understand this for us).
150                let boxed_node = Box::from_raw_in(node.as_ptr(), &self.alloc);
151                let node = into_inner(boxed_node);
152                let result = node.elem;
153
154                // Make the next node into the new front.
155                self.front = node.back;
156                if let Some(new) = self.front {
157                    // Cleanup its reference to the removed node
158                    (*new.as_ptr()).front = None;
159                } else {
160                    // If the front is now null, then this list is now empty!
161                    self.back = None;
162                }
163
164                self.len -= 1;
165                result
166                // Box gets implicitly freed here, knows there is no T.
167            })
168        }
169    }
170
171    pub fn pop_back(&mut self) -> Option<T> {
172        // workaround for a bug in allocator-api2
173        fn into_inner<T, A: Allocator>(boxed: Box<T, A>) -> T {
174            use allocator_api2::alloc::Layout;
175            let (ptr, alloc) = Box::into_raw_with_allocator(boxed);
176            let unboxed = unsafe { ptr.read() };
177            unsafe { alloc.deallocate(NonNull::new(ptr).unwrap().cast(), Layout::new::<T>()) };
178            unboxed
179        }
180
181        unsafe {
182            // Only have to do stuff if there is a back node to pop.
183            self.back.map(|node| {
184                // Bring the Box front to life so we can move out its value and
185                // Drop it (Box continues to magically understand this for us).
186                let boxed_node = Box::from_raw(node.as_ptr());
187                let node = into_inner(boxed_node);
188                let result = node.elem;
189
190                // Make the next node into the new back.
191                self.back = node.front;
192                if let Some(new) = self.back {
193                    // Cleanup its reference to the removed node
194                    (*new.as_ptr()).back = None;
195                } else {
196                    // If the back is now null, then this list is now empty!
197                    self.front = None;
198                }
199
200                self.len -= 1;
201                result
202                // Box gets implicitly freed here, knows there is no T.
203            })
204        }
205    }
206
207    pub fn front(&self) -> Option<&T> {
208        unsafe { self.front.map(|node| &(*node.as_ptr()).elem) }
209    }
210
211    pub fn front_mut(&mut self) -> Option<&mut T> {
212        unsafe { self.front.map(|node| &mut (*node.as_ptr()).elem) }
213    }
214
215    pub fn back(&self) -> Option<&T> {
216        unsafe { self.back.map(|node| &(*node.as_ptr()).elem) }
217    }
218
219    pub fn back_mut(&mut self) -> Option<&mut T> {
220        unsafe { self.back.map(|node| &mut (*node.as_ptr()).elem) }
221    }
222
223    pub fn len(&self) -> usize {
224        self.len
225    }
226
227    pub fn is_empty(&self) -> bool {
228        self.len == 0
229    }
230
231    pub fn clear(&mut self) {
232        // Oh look it's drop again
233        while self.pop_front().is_some() {}
234    }
235
236    pub fn iter(&self) -> Iter<'_, T> {
237        Iter {
238            front: self.front,
239            back: self.back,
240            len: self.len,
241            _boo: PhantomData,
242        }
243    }
244
245    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
246        IterMut {
247            front: self.front,
248            back: self.back,
249            len: self.len,
250            _boo: PhantomData,
251        }
252    }
253
254    pub fn cursor_mut(&mut self) -> CursorMut<'_, T, A> {
255        CursorMut {
256            list: self,
257            cur: None,
258            index: None,
259        }
260    }
261}
262
263impl<T, A: Allocator> Drop for LinkedList<T, A> {
264    fn drop(&mut self) {
265        // Pop until we have to stop
266        while self.pop_front().is_some() {}
267    }
268}
269
270impl<T, A: Allocator + Default> Default for LinkedList<T, A> {
271    fn default() -> Self {
272        Self::new_in(Default::default())
273    }
274}
275
276impl<T: Clone, A: Allocator + Clone> Clone for LinkedList<T, A> {
277    fn clone(&self) -> Self {
278        let mut new_list = Self::new_in(self.alloc.clone());
279        for item in self {
280            new_list.push_back(item.clone());
281        }
282        new_list
283    }
284}
285
286impl<T, A: Allocator> Extend<T> for LinkedList<T, A> {
287    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
288        for item in iter {
289            self.push_back(item);
290        }
291    }
292}
293
294impl<T, A: Allocator + Default> FromIterator<T> for LinkedList<T, A> {
295    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
296        let mut list = Self::new_in(Default::default());
297        list.extend(iter);
298        list
299    }
300}
301
302impl<T: Debug, A: Allocator> Debug for LinkedList<T, A> {
303    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
304        f.debug_list().entries(self).finish()
305    }
306}
307
308impl<T, U, A1, A2> PartialEq<LinkedList<U, A2>> for LinkedList<T, A1>
309where
310    T: PartialEq<U>,
311    A1: Allocator,
312    A2: Allocator,
313{
314    fn eq(&self, other: &LinkedList<U, A2>) -> bool {
315        self.len() == other.len() && self.iter().eq(other.iter())
316    }
317}
318
319impl<T: Eq, A: Allocator> Eq for LinkedList<T, A> {}
320
321impl<T, A1, A2> PartialOrd<LinkedList<T, A2>> for LinkedList<T, A1>
322where
323    T: PartialOrd,
324    A1: Allocator,
325    A2: Allocator,
326{
327    fn partial_cmp(&self, other: &LinkedList<T, A2>) -> Option<Ordering> {
328        self.iter().partial_cmp(other)
329    }
330}
331
332impl<T: Ord, A: Allocator> Ord for LinkedList<T, A> {
333    fn cmp(&self, other: &Self) -> Ordering {
334        self.iter().cmp(other)
335    }
336}
337
338impl<T: Hash, A: Allocator> Hash for LinkedList<T, A> {
339    fn hash<H: Hasher>(&self, state: &mut H) {
340        self.len().hash(state);
341        for item in self {
342            item.hash(state);
343        }
344    }
345}
346
347impl<'a, T, A: Allocator> IntoIterator for &'a LinkedList<T, A> {
348    type IntoIter = Iter<'a, T>;
349    type Item = &'a T;
350
351    fn into_iter(self) -> Self::IntoIter {
352        self.iter()
353    }
354}
355
356impl<'a, T> Iterator for Iter<'a, T> {
357    type Item = &'a T;
358
359    fn next(&mut self) -> Option<Self::Item> {
360        // While self.front == self.back is a tempting condition to check here,
361        // it won't do the right for yielding the last element! That sort of
362        // thing only works for arrays because of "one-past-the-end" pointers.
363        if self.len > 0 {
364            // We could unwrap front, but this is safer and easier
365            self.front.map(|node| unsafe {
366                self.len -= 1;
367                self.front = (*node.as_ptr()).back;
368                &(*node.as_ptr()).elem
369            })
370        } else {
371            None
372        }
373    }
374
375    fn size_hint(&self) -> (usize, Option<usize>) {
376        (self.len, Some(self.len))
377    }
378}
379
380impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
381    fn next_back(&mut self) -> Option<Self::Item> {
382        if self.len > 0 {
383            self.back.map(|node| unsafe {
384                self.len -= 1;
385                self.back = (*node.as_ptr()).front;
386                &(*node.as_ptr()).elem
387            })
388        } else {
389            None
390        }
391    }
392}
393
394impl<'a, T> ExactSizeIterator for Iter<'a, T> {
395    fn len(&self) -> usize {
396        self.len
397    }
398}
399
400impl<'a, T, A: Allocator> IntoIterator for &'a mut LinkedList<T, A> {
401    type IntoIter = IterMut<'a, T>;
402    type Item = &'a mut T;
403
404    fn into_iter(self) -> Self::IntoIter {
405        self.iter_mut()
406    }
407}
408
409impl<'a, T> Iterator for IterMut<'a, T> {
410    type Item = &'a mut T;
411
412    fn next(&mut self) -> Option<Self::Item> {
413        // While self.front == self.back is a tempting condition to check here,
414        // it won't do the right for yielding the last element! That sort of
415        // thing only works for arrays because of "one-past-the-end" pointers.
416        if self.len > 0 {
417            // We could unwrap front, but this is safer and easier
418            self.front.map(|node| unsafe {
419                self.len -= 1;
420                self.front = (*node.as_ptr()).back;
421                &mut (*node.as_ptr()).elem
422            })
423        } else {
424            None
425        }
426    }
427
428    fn size_hint(&self) -> (usize, Option<usize>) {
429        (self.len, Some(self.len))
430    }
431}
432
433impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
434    fn next_back(&mut self) -> Option<Self::Item> {
435        if self.len > 0 {
436            self.back.map(|node| unsafe {
437                self.len -= 1;
438                self.back = (*node.as_ptr()).front;
439                &mut (*node.as_ptr()).elem
440            })
441        } else {
442            None
443        }
444    }
445}
446
447impl<'a, T> ExactSizeIterator for IterMut<'a, T> {
448    fn len(&self) -> usize {
449        self.len
450    }
451}
452
453impl<T, A: Allocator> IntoIterator for LinkedList<T, A> {
454    type IntoIter = IntoIter<T, A>;
455    type Item = T;
456
457    fn into_iter(self) -> Self::IntoIter {
458        IntoIter { list: self }
459    }
460}
461
462impl<T, A: Allocator> Iterator for IntoIter<T, A> {
463    type Item = T;
464
465    fn next(&mut self) -> Option<Self::Item> {
466        self.list.pop_front()
467    }
468
469    fn size_hint(&self) -> (usize, Option<usize>) {
470        (self.list.len, Some(self.list.len))
471    }
472}
473
474impl<T> DoubleEndedIterator for IntoIter<T> {
475    fn next_back(&mut self) -> Option<Self::Item> {
476        self.list.pop_back()
477    }
478}
479
480impl<T> ExactSizeIterator for IntoIter<T> {
481    fn len(&self) -> usize {
482        self.list.len
483    }
484}
485
486impl<'a, T, A: Allocator> CursorMut<'a, T, A> {
487    pub fn index(&self) -> Option<usize> {
488        self.index
489    }
490
491    pub fn move_next(&mut self) {
492        if let Some(cur) = self.cur {
493            unsafe {
494                // We're on a real element, go to its next (back)
495                self.cur = (*cur.as_ptr()).back;
496                if self.cur.is_some() {
497                    *self.index.as_mut().unwrap() += 1;
498                } else {
499                    // We just walked to the ghost, no more index
500                    self.index = None;
501                }
502            }
503        } else if !self.list.is_empty() {
504            // We're at the ghost, and there is a real front, so move to it!
505            self.cur = self.list.front;
506            self.index = Some(0)
507        } else {
508            // We're at the ghost, but that's the only element... do nothing.
509        }
510    }
511
512    pub fn move_prev(&mut self) {
513        if let Some(cur) = self.cur {
514            unsafe {
515                // We're on a real element, go to its previous (front)
516                self.cur = (*cur.as_ptr()).front;
517                if self.cur.is_some() {
518                    *self.index.as_mut().unwrap() -= 1;
519                } else {
520                    // We just walked to the ghost, no more index
521                    self.index = None;
522                }
523            }
524        } else if !self.list.is_empty() {
525            // We're at the ghost, and there is a real back, so move to it!
526            self.cur = self.list.back;
527            self.index = Some(self.list.len - 1)
528        } else {
529            // We're at the ghost, but that's the only element... do nothing.
530        }
531    }
532
533    pub fn current(&mut self) -> Option<&mut T> {
534        unsafe { self.cur.map(|node| &mut (*node.as_ptr()).elem) }
535    }
536
537    pub fn peek_next(&mut self) -> Option<&mut T> {
538        unsafe {
539            let next = if let Some(cur) = self.cur {
540                // Normal case, try to follow the cur node's back pointer
541                (*cur.as_ptr()).back
542            } else {
543                // Ghost case, try to use the list's front pointer
544                self.list.front
545            };
546
547            // Yield the element if the next node exists
548            next.map(|node| &mut (*node.as_ptr()).elem)
549        }
550    }
551
552    pub fn peek_prev(&mut self) -> Option<&mut T> {
553        unsafe {
554            let prev = if let Some(cur) = self.cur {
555                // Normal case, try to follow the cur node's front pointer
556                (*cur.as_ptr()).front
557            } else {
558                // Ghost case, try to use the list's back pointer
559                self.list.back
560            };
561
562            // Yield the element if the prev node exists
563            prev.map(|node| &mut (*node.as_ptr()).elem)
564        }
565    }
566
567    pub fn split_before(&mut self) -> LinkedList<T, A>
568    where
569        A: Copy,
570    {
571        // We have this:
572        //
573        //     list.front -> A <-> B <-> C <-> D <- list.back
574        //                               ^
575        //                              cur
576        //
577        //
578        // And we want to produce this:
579        //
580        //     list.front -> C <-> D <- list.back
581        //                   ^
582        //                  cur
583        //
584        //
585        //    return.front -> A <-> B <- return.back
586        //
587        if let Some(cur) = self.cur {
588            // We are pointing at a real element, so the list is non-empty.
589            unsafe {
590                // Current state
591                let old_len = self.list.len;
592                let old_idx = self.index.unwrap();
593                let prev = (*cur.as_ptr()).front;
594
595                // What self will become
596                let new_len = old_len - old_idx;
597                let new_front = self.cur;
598                let new_back = self.list.back;
599                let new_idx = Some(0);
600
601                // What the output will become
602                let output_len = old_len - new_len;
603                // We might be at the first node, in which case we don't want to set a new list.front but return an empty list.
604                let mut output_front = None;
605                let output_back = prev;
606
607                // Break the links between cur and prev
608                if let Some(prev) = prev {
609                    (*cur.as_ptr()).front = None;
610                    (*prev.as_ptr()).back = None;
611                    output_front = self.list.front;
612                }
613
614                // Produce the result:
615                self.list.len = new_len;
616                self.list.front = new_front;
617                self.list.back = new_back;
618                self.index = new_idx;
619
620                LinkedList {
621                    front: output_front,
622                    back: output_back,
623                    len: output_len,
624                    alloc: self.list.alloc,
625                    _boo: PhantomData,
626                }
627            }
628        } else {
629            // We're at the ghost, just replace our list with an empty one.
630            // No other state needs to be changed.
631            mem::replace(self.list, LinkedList::new_in(self.list.alloc))
632        }
633    }
634
635    pub fn split_after(&mut self) -> LinkedList<T, A>
636    where
637        A: Copy,
638    {
639        // We have this:
640        //
641        //     list.front -> A <-> B <-> C <-> D <- list.back
642        //                         ^
643        //                        cur
644        //
645        //
646        // And we want to produce this:
647        //
648        //     list.front -> A <-> B <- list.back
649        //                         ^
650        //                        cur
651        //
652        //
653        //    return.front -> C <-> D <- return.back
654        //
655        if let Some(cur) = self.cur {
656            // We are pointing at a real element, so the list is non-empty.
657            unsafe {
658                // Current state
659                let old_len = self.list.len;
660                let old_idx = self.index.unwrap();
661                let next = (*cur.as_ptr()).back;
662
663                // What self will become
664                let new_len = old_idx + 1;
665                let new_back = self.cur;
666                let new_front = self.list.front;
667                let new_idx = Some(old_idx);
668
669                // What the output will become
670                let output_len = old_len - new_len;
671                let output_front = next;
672                // We might be at the last node, in which case we don't want to set a new list.back but return an empty list.
673                let mut output_back = None;
674
675                // Break the links between cur and next
676                if let Some(next) = next {
677                    (*cur.as_ptr()).back = None;
678                    (*next.as_ptr()).front = None;
679                    output_back = self.list.back;
680                }
681
682                // Produce the result:
683                self.list.len = new_len;
684                self.list.front = new_front;
685                self.list.back = new_back;
686                self.index = new_idx;
687
688                LinkedList {
689                    front: output_front,
690                    back: output_back,
691                    len: output_len,
692                    alloc: self.list.alloc,
693                    _boo: PhantomData,
694                }
695            }
696        } else {
697            // We're at the ghost, just replace our list with an empty one.
698            // No other state needs to be changed.
699            mem::replace(self.list, LinkedList::new_in(self.list.alloc))
700        }
701    }
702
703    pub fn splice_before(&mut self, mut input: LinkedList<T, A>) {
704        // We have this:
705        //
706        // input.front -> 1 <-> 2 <- input.back
707        //
708        // list.front -> A <-> B <-> C <- list.back
709        //                     ^
710        //                    cur
711        //
712        //
713        // Becoming this:
714        //
715        // list.front -> A <-> 1 <-> 2 <-> B <-> C <- list.back
716        //                                 ^
717        //                                cur
718        //
719        unsafe {
720            // We can either `take` the input's pointers or `mem::forget`
721            // it. Using `take` is more responsible in case we ever do custom
722            // allocators or something that also needs to be cleaned up!
723            if input.is_empty() {
724                // Input is empty, do nothing.
725            } else if let Some(cur) = self.cur {
726                // Both lists are non-empty
727                let in_front = input.front.take().unwrap();
728                let in_back = input.back.take().unwrap();
729
730                if let Some(prev) = (*cur.as_ptr()).front {
731                    // General Case, no boundaries, just internal fixups
732                    (*prev.as_ptr()).back = Some(in_front);
733                    (*in_front.as_ptr()).front = Some(prev);
734                    (*cur.as_ptr()).front = Some(in_back);
735                    (*in_back.as_ptr()).back = Some(cur);
736                } else {
737                    // No prev, we're appending to the front
738                    (*cur.as_ptr()).front = Some(in_back);
739                    (*in_back.as_ptr()).back = Some(cur);
740                    self.list.front = Some(in_front);
741                }
742                // Index moves forward by input length
743                *self.index.as_mut().unwrap() += input.len;
744            } else if let Some(back) = self.list.back {
745                // We're on the ghost but non-empty, append to the back
746                let in_front = input.front.take().unwrap();
747                let in_back = input.back.take().unwrap();
748
749                (*back.as_ptr()).back = Some(in_front);
750                (*in_front.as_ptr()).front = Some(back);
751                self.list.back = Some(in_back);
752            } else {
753                // We're empty, become the input, remain on the ghost
754                mem::swap(self.list, &mut input);
755            }
756
757            self.list.len += input.len;
758            // Not necessary but Polite To Do
759            input.len = 0;
760
761            // Input dropped here
762        }
763    }
764
765    pub fn splice_after(&mut self, mut input: LinkedList<T, A>) {
766        // We have this:
767        //
768        // input.front -> 1 <-> 2 <- input.back
769        //
770        // list.front -> A <-> B <-> C <- list.back
771        //                     ^
772        //                    cur
773        //
774        //
775        // Becoming this:
776        //
777        // list.front -> A <-> B <-> 1 <-> 2 <-> C <- list.back
778        //                     ^
779        //                    cur
780        //
781        unsafe {
782            // We can either `take` the input's pointers or `mem::forget`
783            // it. Using `take` is more responsible in case we ever do custom
784            // allocators or something that also needs to be cleaned up!
785            if input.is_empty() {
786                // Input is empty, do nothing.
787            } else if let Some(cur) = self.cur {
788                // Both lists are non-empty
789                let in_front = input.front.take().unwrap();
790                let in_back = input.back.take().unwrap();
791
792                if let Some(next) = (*cur.as_ptr()).back {
793                    // General Case, no boundaries, just internal fixups
794                    (*next.as_ptr()).front = Some(in_back);
795                    (*in_back.as_ptr()).back = Some(next);
796                    (*cur.as_ptr()).back = Some(in_front);
797                    (*in_front.as_ptr()).front = Some(cur);
798                } else {
799                    // No next, we're appending to the back
800                    (*cur.as_ptr()).back = Some(in_front);
801                    (*in_front.as_ptr()).front = Some(cur);
802                    self.list.back = Some(in_back);
803                }
804                // Index doesn't change
805            } else if let Some(front) = self.list.front {
806                // We're on the ghost but non-empty, append to the front
807                let in_front = input.front.take().unwrap();
808                let in_back = input.back.take().unwrap();
809
810                (*front.as_ptr()).front = Some(in_back);
811                (*in_back.as_ptr()).back = Some(front);
812                self.list.front = Some(in_front);
813            } else {
814                // We're empty, become the input, remain on the ghost
815                mem::swap(self.list, &mut input);
816            }
817
818            self.list.len += input.len;
819            // Not necessary but Polite To Do
820            input.len = 0;
821
822            // Input dropped here
823        }
824    }
825}
826
827unsafe impl<T: Send> Send for LinkedList<T> {}
828unsafe impl<T: Sync> Sync for LinkedList<T> {}
829
830unsafe impl<'a, T: Send> Send for Iter<'a, T> {}
831unsafe impl<'a, T: Sync> Sync for Iter<'a, T> {}
832
833unsafe impl<'a, T: Send> Send for IterMut<'a, T> {}
834unsafe impl<'a, T: Sync> Sync for IterMut<'a, T> {}
835
836#[allow(dead_code)]
837fn assert_properties() {
838    fn is_send<T: Send>() {}
839    fn is_sync<T: Sync>() {}
840
841    is_send::<LinkedList<i32>>();
842    is_sync::<LinkedList<i32>>();
843
844    is_send::<IntoIter<i32>>();
845    is_sync::<IntoIter<i32>>();
846
847    is_send::<Iter<i32>>();
848    is_sync::<Iter<i32>>();
849
850    is_send::<IterMut<i32>>();
851    is_sync::<IterMut<i32>>();
852
853    fn linked_list_covariant<'a, T>(x: LinkedList<&'static T>) -> LinkedList<&'a T> {
854        x
855    }
856    fn iter_covariant<'i, 'a, T>(x: Iter<'i, &'static T>) -> Iter<'i, &'a T> {
857        x
858    }
859    fn into_iter_covariant<'a, T>(x: IntoIter<&'static T>) -> IntoIter<&'a T> {
860        x
861    }
862
863    /// ```compile_fail
864    /// use linked_list::IterMut;
865    ///
866    /// fn iter_mut_covariant<'i, 'a, T>(x: IterMut<'i, &'static T>) -> IterMut<'i, &'a T> { x }
867    /// ```
868    fn iter_mut_invariant() {}
869}
870
871#[cfg(feature = "serde")]
872impl<T, A> serde::Serialize for LinkedList<T, A>
873where
874    T: serde::Serialize,
875    A: Allocator,
876{
877    #[inline]
878    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
879    where
880        S: serde::Serializer,
881    {
882        serializer.collect_seq(self)
883    }
884}
885
886#[cfg(feature = "serde")]
887impl<'de, T, A> serde::Deserialize<'de> for LinkedList<T, A>
888where
889    T: serde::Deserialize<'de>,
890    A: Allocator + Default,
891{
892    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
893    where
894        D: serde::Deserializer<'de>,
895    {
896        struct SeqVisitor<T, A: Allocator> {
897            marker: PhantomData<LinkedList<T, A>>,
898        }
899
900        impl<'de, T, A> serde::de::Visitor<'de> for SeqVisitor<T, A>
901        where
902            T: serde::Deserialize<'de>,
903            A: Allocator + Default,
904        {
905            type Value = LinkedList<T, A>;
906
907            fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
908                formatter.write_str("a sequence")
909            }
910
911            #[inline]
912            fn visit_seq<B>(self, mut seq: B) -> Result<Self::Value, B::Error>
913            where
914                B: serde::de::SeqAccess<'de>,
915            {
916                let mut values = LinkedList::new_in(Default::default());
917
918                while let Some(value) = seq.next_element()? {
919                    LinkedList::push_back(&mut values, value);
920                }
921
922                Ok(values)
923            }
924        }
925
926        let visitor = SeqVisitor {
927            marker: PhantomData,
928        };
929        deserializer.deserialize_seq(visitor)
930    }
931
932    fn deserialize_in_place<D>(deserializer: D, place: &mut Self) -> Result<(), D::Error>
933    where
934        D: serde::Deserializer<'de>,
935    {
936        struct SeqInPlaceVisitor<'a, T: 'a, A: Allocator + 'a>(&'a mut LinkedList<T, A>);
937
938        impl<'a, 'de, T, A> serde::de::Visitor<'de> for SeqInPlaceVisitor<'a, T, A>
939        where
940            T: serde::Deserialize<'de>,
941            A: Allocator,
942        {
943            type Value = ();
944
945            fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
946                formatter.write_str("a sequence")
947            }
948
949            #[inline]
950            fn visit_seq<B>(mut self, mut seq: B) -> Result<Self::Value, B::Error>
951            where
952                B: serde::de::SeqAccess<'de>,
953            {
954                LinkedList::clear(&mut self.0);
955
956                // FIXME: try to overwrite old values here? (Vec, VecDeque, LinkedList)
957                while let Some(value) = seq.next_element()? {
958                    LinkedList::push_back(&mut self.0, value);
959                }
960
961                Ok(())
962            }
963        }
964
965        deserializer.deserialize_seq(SeqInPlaceVisitor(place))
966    }
967}
968
969#[cfg(feature = "miniserde")]
970impl<T: miniserde::Serialize, A: Allocator> miniserde::Serialize for LinkedList<T, A> {
971    fn begin(&self) -> miniserde::ser::Fragment<'_> {
972        struct Stream<'a, T: 'a>(Iter<'a, T>);
973
974        impl<'a, T: miniserde::Serialize> miniserde::ser::Seq for Stream<'a, T> {
975            fn next(&mut self) -> Option<&dyn miniserde::Serialize> {
976                let element = self.0.next()?;
977                Some(element)
978            }
979        }
980
981        miniserde::ser::Fragment::Seq(std::boxed::Box::new(Stream(self.iter())))
982    }
983}
984
985#[cfg(feature = "miniserde")]
986impl<T: miniserde::Deserialize, A: Allocator + Default> miniserde::Deserialize
987    for LinkedList<T, A>
988{
989    fn begin(out: &mut Option<Self>) -> &mut dyn miniserde::de::Visitor {
990        miniserde::make_place!(Place);
991
992        impl<T: miniserde::Deserialize, A: Allocator + Default> miniserde::de::Visitor
993            for Place<LinkedList<T, A>>
994        {
995            fn seq(&mut self) -> miniserde::Result<std::boxed::Box<dyn miniserde::de::Seq + '_>> {
996                Ok(std::boxed::Box::new(VecBuilder {
997                    out: &mut self.out,
998                    list: LinkedList::new_in(Default::default()),
999                    element: None,
1000                }))
1001            }
1002        }
1003
1004        struct VecBuilder<'a, T: 'a, A: Allocator + 'a> {
1005            out: &'a mut Option<LinkedList<T, A>>,
1006            list: LinkedList<T, A>,
1007            element: Option<T>,
1008        }
1009
1010        impl<'a, T, A: Allocator> VecBuilder<'a, T, A> {
1011            fn shift(&mut self) {
1012                if let Some(e) = self.element.take() {
1013                    self.list.push_back(e);
1014                }
1015            }
1016        }
1017
1018        impl<'a, T: miniserde::Deserialize, A: Allocator + Default> miniserde::de::Seq
1019            for VecBuilder<'a, T, A>
1020        {
1021            fn element(&mut self) -> miniserde::Result<&mut dyn miniserde::de::Visitor> {
1022                self.shift();
1023                Ok(miniserde::Deserialize::begin(&mut self.element))
1024            }
1025
1026            fn finish(&mut self) -> miniserde::Result<()> {
1027                self.shift();
1028                *self.out = Some(mem::take(&mut self.list));
1029                Ok(())
1030            }
1031        }
1032
1033        Place::new(out)
1034    }
1035}
1036
1037#[cfg(feature = "nanoserde")]
1038mod nanoserde_impls {
1039    use super::*;
1040
1041    impl<T> nanoserde::SerBin for LinkedList<T>
1042    where
1043        T: nanoserde::SerBin,
1044    {
1045        fn ser_bin(&self, s: &mut std::vec::Vec<u8>) {
1046            let len = self.len();
1047            len.ser_bin(s);
1048            for item in self.iter() {
1049                item.ser_bin(s);
1050            }
1051        }
1052    }
1053
1054    impl<T> nanoserde::DeBin for LinkedList<T>
1055    where
1056        T: nanoserde::DeBin,
1057    {
1058        fn de_bin(o: &mut usize, d: &[u8]) -> Result<LinkedList<T>, nanoserde::DeBinErr> {
1059            let len: usize = nanoserde::DeBin::de_bin(o, d)?;
1060            let mut out = LinkedList::new();
1061            for _ in 0..len {
1062                out.push_back(nanoserde::DeBin::de_bin(o, d)?)
1063            }
1064            Ok(out)
1065        }
1066    }
1067
1068    impl<T> nanoserde::SerJson for LinkedList<T>
1069    where
1070        T: nanoserde::SerJson,
1071    {
1072        fn ser_json(&self, d: usize, s: &mut nanoserde::SerJsonState) {
1073            s.out.push('[');
1074            if self.len() > 0 {
1075                let last = self.len() - 1;
1076                for (index, item) in self.iter().enumerate() {
1077                    s.indent(d + 1);
1078                    item.ser_json(d + 1, s);
1079                    if index != last {
1080                        s.out.push(',');
1081                    }
1082                }
1083            }
1084            s.out.push(']');
1085        }
1086    }
1087
1088    impl<T> nanoserde::DeJson for LinkedList<T>
1089    where
1090        T: nanoserde::DeJson,
1091    {
1092        fn de_json(
1093            s: &mut nanoserde::DeJsonState,
1094            i: &mut std::str::Chars,
1095        ) -> Result<LinkedList<T>, nanoserde::DeJsonErr> {
1096            let mut out = LinkedList::new();
1097            s.block_open(i)?;
1098
1099            while s.tok != nanoserde::DeJsonTok::BlockClose {
1100                out.push_back(nanoserde::DeJson::de_json(s, i)?);
1101                s.eat_comma_block(i)?;
1102            }
1103            s.block_close(i)?;
1104            Ok(out)
1105        }
1106    }
1107
1108    impl<T> nanoserde::SerRon for LinkedList<T>
1109    where
1110        T: nanoserde::SerRon,
1111    {
1112        fn ser_ron(&self, d: usize, s: &mut nanoserde::SerRonState) {
1113            s.out.push('[');
1114            if self.len() > 0 {
1115                let last = self.len() - 1;
1116                for (index, item) in self.iter().enumerate() {
1117                    s.indent(d + 1);
1118                    item.ser_ron(d + 1, s);
1119                    if index != last {
1120                        s.out.push(',');
1121                    }
1122                }
1123            }
1124            s.out.push(']');
1125        }
1126    }
1127
1128    impl<T> nanoserde::DeRon for LinkedList<T>
1129    where
1130        T: nanoserde::DeRon,
1131    {
1132        fn de_ron(
1133            s: &mut nanoserde::DeRonState,
1134            i: &mut std::str::Chars,
1135        ) -> Result<LinkedList<T>, nanoserde::DeRonErr> {
1136            let mut out = LinkedList::new();
1137            s.block_open(i)?;
1138
1139            while s.tok != nanoserde::DeRonTok::BlockClose {
1140                out.push_back(nanoserde::DeRon::de_ron(s, i)?);
1141                s.eat_comma_block(i)?;
1142            }
1143            s.block_close(i)?;
1144            Ok(out)
1145        }
1146    }
1147}
1148
1149#[cfg(feature = "borsh")]
1150impl<T, A: Allocator + Default> borsh::BorshDeserialize for LinkedList<T, A>
1151where
1152    T: borsh::BorshDeserialize,
1153{
1154    #[inline]
1155    fn deserialize_reader<R: borsh::io::Read>(reader: &mut R) -> borsh::io::Result<Self> {
1156        let vec = <alloc::vec::Vec<T>>::deserialize_reader(reader)?;
1157        Ok(vec.into_iter().collect::<LinkedList<T, A>>())
1158    }
1159}
1160
1161#[cfg(feature = "borsh")]
1162impl<T, A: Allocator> borsh::BorshSerialize for LinkedList<T, A>
1163where
1164    T: borsh::BorshSerialize,
1165{
1166    #[inline]
1167    fn serialize<W: borsh::io::Write>(&self, writer: &mut W) -> borsh::io::Result<()> {
1168        fn check_zst<T>() -> borsh::io::Result<()> {
1169            if core::mem::size_of::<T>() == 0 {
1170                return Err(borsh::io::Error::new(
1171                    borsh::io::ErrorKind::InvalidData,
1172                    borsh::error::ERROR_ZST_FORBIDDEN,
1173                ));
1174            }
1175            Ok(())
1176        }
1177
1178        check_zst::<T>()?;
1179
1180        writer.write_all(
1181            &(u32::try_from(self.len()).map_err(|_| borsh::io::ErrorKind::InvalidData)?)
1182                .to_le_bytes(),
1183        )?;
1184        for item in self {
1185            item.serialize(writer)?;
1186        }
1187        Ok(())
1188    }
1189}
1190
1191#[cfg(test)]
1192mod test {
1193    use super::LinkedList;
1194
1195    use std::vec::Vec;
1196
1197    fn generate_test() -> LinkedList<i32> {
1198        list_from(&[0, 1, 2, 3, 4, 5, 6])
1199    }
1200
1201    fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> {
1202        v.iter().map(|x| (*x).clone()).collect()
1203    }
1204
1205    #[test]
1206    fn test_basic_front() {
1207        let mut list = LinkedList::new();
1208
1209        // Try to break an empty list
1210        assert_eq!(list.len(), 0);
1211        assert_eq!(list.pop_front(), None);
1212        assert_eq!(list.len(), 0);
1213
1214        // Try to break a one item list
1215        list.push_front(10);
1216        assert_eq!(list.len(), 1);
1217        assert_eq!(list.pop_front(), Some(10));
1218        assert_eq!(list.len(), 0);
1219        assert_eq!(list.pop_front(), None);
1220        assert_eq!(list.len(), 0);
1221
1222        // Mess around
1223        list.push_front(10);
1224        assert_eq!(list.len(), 1);
1225        list.push_front(20);
1226        assert_eq!(list.len(), 2);
1227        list.push_front(30);
1228        assert_eq!(list.len(), 3);
1229        assert_eq!(list.pop_front(), Some(30));
1230        assert_eq!(list.len(), 2);
1231        list.push_front(40);
1232        assert_eq!(list.len(), 3);
1233        assert_eq!(list.pop_front(), Some(40));
1234        assert_eq!(list.len(), 2);
1235        assert_eq!(list.pop_front(), Some(20));
1236        assert_eq!(list.len(), 1);
1237        assert_eq!(list.pop_front(), Some(10));
1238        assert_eq!(list.len(), 0);
1239        assert_eq!(list.pop_front(), None);
1240        assert_eq!(list.len(), 0);
1241        assert_eq!(list.pop_front(), None);
1242        assert_eq!(list.len(), 0);
1243    }
1244
1245    #[test]
1246    fn test_basic() {
1247        let mut m = LinkedList::new();
1248        assert_eq!(m.pop_front(), None);
1249        assert_eq!(m.pop_back(), None);
1250        assert_eq!(m.pop_front(), None);
1251        m.push_front(1);
1252        assert_eq!(m.pop_front(), Some(1));
1253        m.push_back(2);
1254        m.push_back(3);
1255        assert_eq!(m.len(), 2);
1256        assert_eq!(m.pop_front(), Some(2));
1257        assert_eq!(m.pop_front(), Some(3));
1258        assert_eq!(m.len(), 0);
1259        assert_eq!(m.pop_front(), None);
1260        m.push_back(1);
1261        m.push_back(3);
1262        m.push_back(5);
1263        m.push_back(7);
1264        assert_eq!(m.pop_front(), Some(1));
1265
1266        let mut n = LinkedList::new();
1267        n.push_front(2);
1268        n.push_front(3);
1269        {
1270            assert_eq!(n.front().unwrap(), &3);
1271            let x = n.front_mut().unwrap();
1272            assert_eq!(*x, 3);
1273            *x = 0;
1274        }
1275        {
1276            assert_eq!(n.back().unwrap(), &2);
1277            let y = n.back_mut().unwrap();
1278            assert_eq!(*y, 2);
1279            *y = 1;
1280        }
1281        assert_eq!(n.pop_front(), Some(0));
1282        assert_eq!(n.pop_front(), Some(1));
1283    }
1284
1285    #[test]
1286    fn test_iterator() {
1287        let m = generate_test();
1288        for (i, elt) in m.iter().enumerate() {
1289            assert_eq!(i as i32, *elt);
1290        }
1291        let mut n = LinkedList::new();
1292        assert_eq!(n.iter().next(), None);
1293        n.push_front(4);
1294        let mut it = n.iter();
1295        assert_eq!(it.size_hint(), (1, Some(1)));
1296        assert_eq!(it.next().unwrap(), &4);
1297        assert_eq!(it.size_hint(), (0, Some(0)));
1298        assert_eq!(it.next(), None);
1299    }
1300
1301    #[test]
1302    fn test_iterator_double_end() {
1303        let mut n = LinkedList::new();
1304        assert_eq!(n.iter().next(), None);
1305        n.push_front(4);
1306        n.push_front(5);
1307        n.push_front(6);
1308        let mut it = n.iter();
1309        assert_eq!(it.size_hint(), (3, Some(3)));
1310        assert_eq!(it.next().unwrap(), &6);
1311        assert_eq!(it.size_hint(), (2, Some(2)));
1312        assert_eq!(it.next_back().unwrap(), &4);
1313        assert_eq!(it.size_hint(), (1, Some(1)));
1314        assert_eq!(it.next_back().unwrap(), &5);
1315        assert_eq!(it.next_back(), None);
1316        assert_eq!(it.next(), None);
1317    }
1318
1319    #[test]
1320    fn test_rev_iter() {
1321        let m = generate_test();
1322        for (i, elt) in m.iter().rev().enumerate() {
1323            assert_eq!(6 - i as i32, *elt);
1324        }
1325        let mut n = LinkedList::new();
1326        assert_eq!(n.iter().rev().next(), None);
1327        n.push_front(4);
1328        let mut it = n.iter().rev();
1329        assert_eq!(it.size_hint(), (1, Some(1)));
1330        assert_eq!(it.next().unwrap(), &4);
1331        assert_eq!(it.size_hint(), (0, Some(0)));
1332        assert_eq!(it.next(), None);
1333    }
1334
1335    #[test]
1336    fn test_mut_iter() {
1337        let mut m = generate_test();
1338        let mut len = m.len();
1339        for (i, elt) in m.iter_mut().enumerate() {
1340            assert_eq!(i as i32, *elt);
1341            len -= 1;
1342        }
1343        assert_eq!(len, 0);
1344        let mut n = LinkedList::new();
1345        assert!(n.iter_mut().next().is_none());
1346        n.push_front(4);
1347        n.push_back(5);
1348        let mut it = n.iter_mut();
1349        assert_eq!(it.size_hint(), (2, Some(2)));
1350        assert!(it.next().is_some());
1351        assert!(it.next().is_some());
1352        assert_eq!(it.size_hint(), (0, Some(0)));
1353        assert!(it.next().is_none());
1354    }
1355
1356    #[test]
1357    fn test_iterator_mut_double_end() {
1358        let mut n = LinkedList::new();
1359        assert!(n.iter_mut().next_back().is_none());
1360        n.push_front(4);
1361        n.push_front(5);
1362        n.push_front(6);
1363        let mut it = n.iter_mut();
1364        assert_eq!(it.size_hint(), (3, Some(3)));
1365        assert_eq!(*it.next().unwrap(), 6);
1366        assert_eq!(it.size_hint(), (2, Some(2)));
1367        assert_eq!(*it.next_back().unwrap(), 4);
1368        assert_eq!(it.size_hint(), (1, Some(1)));
1369        assert_eq!(*it.next_back().unwrap(), 5);
1370        assert!(it.next_back().is_none());
1371        assert!(it.next().is_none());
1372    }
1373
1374    #[test]
1375    fn test_eq() {
1376        let mut n: LinkedList<u8> = list_from(&[]);
1377        let mut m = list_from(&[]);
1378        assert!(n == m);
1379        n.push_front(1);
1380        assert!(n != m);
1381        m.push_back(1);
1382        assert!(n == m);
1383
1384        let n = list_from(&[2, 3, 4]);
1385        let m = list_from(&[1, 2, 3]);
1386        assert!(n != m);
1387    }
1388
1389    #[test]
1390    fn test_ord() {
1391        let n = list_from(&[]);
1392        let m = list_from(&[1, 2, 3]);
1393        assert!(n < m);
1394        assert!(m > n);
1395        assert!(n <= n);
1396        assert!(n >= n);
1397    }
1398
1399    #[test]
1400    fn test_ord_nan() {
1401        let nan = 0.0f64 / 0.0;
1402        let n = list_from(&[nan]);
1403        let m = list_from(&[nan]);
1404        assert!(!(n < m));
1405        assert!(!(n > m));
1406        assert!(!(n <= m));
1407        assert!(!(n >= m));
1408
1409        let n = list_from(&[nan]);
1410        let one = list_from(&[1.0f64]);
1411        assert!(!(n < one));
1412        assert!(!(n > one));
1413        assert!(!(n <= one));
1414        assert!(!(n >= one));
1415
1416        let u = list_from(&[1.0f64, 2.0, nan]);
1417        let v = list_from(&[1.0f64, 2.0, 3.0]);
1418        assert!(!(u < v));
1419        assert!(!(u > v));
1420        assert!(!(u <= v));
1421        assert!(!(u >= v));
1422
1423        let s = list_from(&[1.0f64, 2.0, 4.0, 2.0]);
1424        let t = list_from(&[1.0f64, 2.0, 3.0, 2.0]);
1425        assert!(!(s < t));
1426        assert!(s > one);
1427        assert!(!(s <= one));
1428        assert!(s >= one);
1429    }
1430
1431    #[test]
1432    fn test_debug() {
1433        let list: LinkedList<i32> = (0..10).collect();
1434        assert_eq!(format!("{:?}", list), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
1435
1436        let list: LinkedList<&str> = vec!["just", "one", "test", "more"]
1437            .iter()
1438            .copied()
1439            .collect();
1440        assert_eq!(format!("{:?}", list), r#"["just", "one", "test", "more"]"#);
1441    }
1442
1443    #[test]
1444    fn test_hashmap() {
1445        // Check that HashMap works with this as a key
1446
1447        let list1: LinkedList<i32> = (0..10).collect();
1448        let list2: LinkedList<i32> = (1..11).collect();
1449        let mut map = std::collections::HashMap::new();
1450
1451        assert_eq!(map.insert(list1.clone(), "list1"), None);
1452        assert_eq!(map.insert(list2.clone(), "list2"), None);
1453
1454        assert_eq!(map.len(), 2);
1455
1456        assert_eq!(map.get(&list1), Some(&"list1"));
1457        assert_eq!(map.get(&list2), Some(&"list2"));
1458
1459        assert_eq!(map.remove(&list1), Some("list1"));
1460        assert_eq!(map.remove(&list2), Some("list2"));
1461
1462        assert!(map.is_empty());
1463    }
1464
1465    #[test]
1466    fn test_cursor_move_peek() {
1467        let mut m: LinkedList<u32> = LinkedList::new();
1468        m.extend([1, 2, 3, 4, 5, 6]);
1469        let mut cursor = m.cursor_mut();
1470        cursor.move_next();
1471        assert_eq!(cursor.current(), Some(&mut 1));
1472        assert_eq!(cursor.peek_next(), Some(&mut 2));
1473        assert_eq!(cursor.peek_prev(), None);
1474        assert_eq!(cursor.index(), Some(0));
1475        cursor.move_prev();
1476        assert_eq!(cursor.current(), None);
1477        assert_eq!(cursor.peek_next(), Some(&mut 1));
1478        assert_eq!(cursor.peek_prev(), Some(&mut 6));
1479        assert_eq!(cursor.index(), None);
1480        cursor.move_next();
1481        cursor.move_next();
1482        assert_eq!(cursor.current(), Some(&mut 2));
1483        assert_eq!(cursor.peek_next(), Some(&mut 3));
1484        assert_eq!(cursor.peek_prev(), Some(&mut 1));
1485        assert_eq!(cursor.index(), Some(1));
1486
1487        let mut cursor = m.cursor_mut();
1488        cursor.move_prev();
1489        assert_eq!(cursor.current(), Some(&mut 6));
1490        assert_eq!(cursor.peek_next(), None);
1491        assert_eq!(cursor.peek_prev(), Some(&mut 5));
1492        assert_eq!(cursor.index(), Some(5));
1493        cursor.move_next();
1494        assert_eq!(cursor.current(), None);
1495        assert_eq!(cursor.peek_next(), Some(&mut 1));
1496        assert_eq!(cursor.peek_prev(), Some(&mut 6));
1497        assert_eq!(cursor.index(), None);
1498        cursor.move_prev();
1499        cursor.move_prev();
1500        assert_eq!(cursor.current(), Some(&mut 5));
1501        assert_eq!(cursor.peek_next(), Some(&mut 6));
1502        assert_eq!(cursor.peek_prev(), Some(&mut 4));
1503        assert_eq!(cursor.index(), Some(4));
1504    }
1505
1506    #[test]
1507    fn test_cursor_mut_insert() {
1508        let mut m: LinkedList<u32> = LinkedList::new();
1509        m.extend([1, 2, 3, 4, 5, 6]);
1510        let mut cursor = m.cursor_mut();
1511        cursor.move_next();
1512        cursor.splice_before(Some(7).into_iter().collect());
1513        cursor.splice_after(Some(8).into_iter().collect());
1514        // check_links(&m);
1515        assert_eq!(
1516            m.iter().cloned().collect::<Vec<_>>(),
1517            &[7, 1, 8, 2, 3, 4, 5, 6]
1518        );
1519        let mut cursor = m.cursor_mut();
1520        cursor.move_next();
1521        cursor.move_prev();
1522        cursor.splice_before(Some(9).into_iter().collect());
1523        cursor.splice_after(Some(10).into_iter().collect());
1524        check_links(&m);
1525        assert_eq!(
1526            m.iter().cloned().collect::<Vec<_>>(),
1527            &[10, 7, 1, 8, 2, 3, 4, 5, 6, 9]
1528        );
1529
1530        /* remove_current not impl'd
1531        let mut cursor = m.cursor_mut();
1532        cursor.move_next();
1533        cursor.move_prev();
1534        assert_eq!(cursor.remove_current(), None);
1535        cursor.move_next();
1536        cursor.move_next();
1537        assert_eq!(cursor.remove_current(), Some(7));
1538        cursor.move_prev();
1539        cursor.move_prev();
1540        cursor.move_prev();
1541        assert_eq!(cursor.remove_current(), Some(9));
1542        cursor.move_next();
1543        assert_eq!(cursor.remove_current(), Some(10));
1544        check_links(&m);
1545        assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[1, 8, 2, 3, 4, 5, 6]);
1546        */
1547
1548        let mut m: LinkedList<u32> = LinkedList::new();
1549        m.extend([1, 8, 2, 3, 4, 5, 6]);
1550        let mut cursor = m.cursor_mut();
1551        cursor.move_next();
1552        let mut p: LinkedList<u32> = LinkedList::new();
1553        p.extend([100, 101, 102, 103]);
1554        let mut q: LinkedList<u32> = LinkedList::new();
1555        q.extend([200, 201, 202, 203]);
1556        cursor.splice_after(p);
1557        cursor.splice_before(q);
1558        check_links(&m);
1559        assert_eq!(
1560            m.iter().cloned().collect::<Vec<_>>(),
1561            &[200, 201, 202, 203, 1, 100, 101, 102, 103, 8, 2, 3, 4, 5, 6]
1562        );
1563        let mut cursor = m.cursor_mut();
1564        cursor.move_next();
1565        cursor.move_prev();
1566        let tmp = cursor.split_before();
1567        let expected: &[u32] = &[];
1568        assert_eq!(m.into_iter().collect::<Vec<u32>>(), expected);
1569        m = tmp;
1570        let mut cursor = m.cursor_mut();
1571        cursor.move_next();
1572        cursor.move_next();
1573        cursor.move_next();
1574        cursor.move_next();
1575        cursor.move_next();
1576        cursor.move_next();
1577        cursor.move_next();
1578        let tmp = cursor.split_after();
1579        assert_eq!(
1580            tmp.into_iter().collect::<Vec<_>>(),
1581            &[102, 103, 8, 2, 3, 4, 5, 6]
1582        );
1583        check_links(&m);
1584        assert_eq!(
1585            m.iter().cloned().collect::<Vec<_>>(),
1586            &[200, 201, 202, 203, 1, 100, 101]
1587        );
1588    }
1589
1590    fn check_links<T: Eq + std::fmt::Debug>(list: &LinkedList<T>) {
1591        let from_front: Vec<_> = list.iter().collect();
1592        let from_back: Vec<_> = list.iter().rev().collect();
1593        let re_reved: Vec<_> = from_back.into_iter().rev().collect();
1594
1595        assert_eq!(from_front, re_reved);
1596    }
1597
1598    #[cfg(feature = "serde")]
1599    #[test]
1600    fn test_serialization() {
1601        let linked_list: LinkedList<bool> = LinkedList::new();
1602        let serialized = serde_json::to_string(&linked_list).unwrap();
1603        let unserialized: LinkedList<bool> = serde_json::from_str(&serialized).unwrap();
1604        assert_eq!(linked_list, unserialized);
1605
1606        let bools = vec![true, false, true, true];
1607        let linked_list: LinkedList<bool> = bools.iter().map(|n| *n).collect();
1608        let serialized = serde_json::to_string(&linked_list).unwrap();
1609        let unserialized: LinkedList<bool> = serde_json::from_str(&serialized).unwrap();
1610        assert_eq!(linked_list, unserialized);
1611    }
1612
1613    #[cfg(feature = "miniserde")]
1614    #[test]
1615    fn test_miniserde_serialization() {
1616        let linked_list: LinkedList<bool> = LinkedList::new();
1617        let serialized = miniserde::json::to_string(&linked_list);
1618        let unserialized: LinkedList<bool> = miniserde::json::from_str(&serialized[..]).unwrap();
1619        assert_eq!(linked_list, unserialized);
1620
1621        let bools = vec![true, false, true, true];
1622        let linked_list: LinkedList<bool> = bools.iter().map(|n| *n).collect();
1623        let serialized = miniserde::json::to_string(&linked_list);
1624        let unserialized: LinkedList<bool> = miniserde::json::from_str(&serialized[..]).unwrap();
1625        assert_eq!(linked_list, unserialized);
1626    }
1627
1628    #[cfg(feature = "nanoserde")]
1629    #[test]
1630    fn test_nanoserde_json_serialization() {
1631        use nanoserde::{DeJson, SerJson};
1632
1633        let linked_list: LinkedList<bool> = LinkedList::new();
1634        let serialized = linked_list.serialize_json();
1635        let unserialized: LinkedList<bool> = LinkedList::deserialize_json(&serialized[..]).unwrap();
1636        assert_eq!(linked_list, unserialized);
1637
1638        let bools = vec![true, false, true, true];
1639        let linked_list: LinkedList<bool> = bools.iter().map(|n| *n).collect();
1640        let serialized = linked_list.serialize_json();
1641        let unserialized: LinkedList<bool> = LinkedList::deserialize_json(&serialized[..]).unwrap();
1642        assert_eq!(linked_list, unserialized);
1643    }
1644
1645    #[cfg(feature = "borsh")]
1646    #[test]
1647    fn test_borsh_serialization() {
1648        let linked_list: LinkedList<bool> = LinkedList::new();
1649        let serialized = borsh::to_vec(&linked_list).unwrap();
1650        let unserialized: LinkedList<bool> = borsh::from_slice(&serialized[..]).unwrap();
1651        assert_eq!(linked_list, unserialized);
1652
1653        let bools = vec![true, false, true, true];
1654        let linked_list: LinkedList<bool> = bools.iter().map(|n| *n).collect();
1655        let serialized = borsh::to_vec(&linked_list).unwrap();
1656        let unserialized: LinkedList<bool> = borsh::from_slice(&serialized[..]).unwrap();
1657        assert_eq!(linked_list, unserialized);
1658    }
1659
1660    #[test]
1661    fn test_marker_split_before_first() {
1662        let mut m: LinkedList<u32> = LinkedList::new();
1663        m.extend([1, 2, 3, 4, 5, 6]);
1664        let mut cursor = m.cursor_mut();
1665        cursor.move_next();
1666        assert_eq!(cursor.current(), Some(&mut 1));
1667
1668        let left = cursor.split_before();
1669        assert!(left.is_empty());
1670        assert!(left.front.is_none() && left.back.is_none());
1671
1672        assert_eq!(cursor.current(), Some(&mut 1));
1673        assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[1, 2, 3, 4, 5, 6]);
1674        assert_eq!(m.len(), 6);
1675    }
1676
1677    #[test]
1678    fn test_split_after_last() {
1679        let mut m: LinkedList<u32> = LinkedList::new();
1680        m.extend([1, 2, 3, 4, 5, 6]);
1681        assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[1, 2, 3, 4, 5, 6]);
1682        let mut cursor = m.cursor_mut();
1683
1684        cursor.move_prev();
1685        assert_eq!(cursor.current(), Some(&mut 6));
1686
1687        let right = cursor.split_after();
1688        assert!(right.is_empty());
1689        assert!(right.front.is_none() && right.back.is_none());
1690
1691        assert_eq!(cursor.current(), Some(&mut 6));
1692        assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[1, 2, 3, 4, 5, 6]);
1693        assert_eq!(m.len(), 6);
1694    }
1695}
linked_list/lib.rs

linked_list/
lib.rs
