linked_list/
lib.rs

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

linked_list/
lib.rs
