heapless/
sorted_linked_list.rs

1//! A fixed sorted priority linked list, similar to [`BinaryHeap`] but with different properties
2//! on `push`, `pop`, etc.
3//! For example, the sorting of the list will never `memcpy` the underlying value, so having large
4//! objects in the list will not cause a performance hit.
5//!
6//! # Examples
7//!
8//! ```
9//! use heapless::sorted_linked_list::{SortedLinkedList, Max};
10//! let mut ll: SortedLinkedList<_, _, Max, 3> = SortedLinkedList::new_usize();
11//!
12//! // The largest value will always be first
13//! ll.push(1).unwrap();
14//! assert_eq!(ll.peek(), Some(&1));
15//!
16//! ll.push(2).unwrap();
17//! assert_eq!(ll.peek(), Some(&2));
18//!
19//! ll.push(3).unwrap();
20//! assert_eq!(ll.peek(), Some(&3));
21//!
22//! // This will not fit in the queue.
23//! assert_eq!(ll.push(4), Err(4));
24//! ```
25//!
26//! [`BinaryHeap`]: `crate::binary_heap::BinaryHeap`
27
28use core::cmp::Ordering;
29use core::fmt;
30use core::marker::PhantomData;
31use core::mem::MaybeUninit;
32use core::ops::{Deref, DerefMut};
33use core::ptr;
34
35/// Trait for defining an index for the linked list, never implemented by users.
36pub trait SortedLinkedListIndex: Copy {
37    #[doc(hidden)]
38    unsafe fn new_unchecked(val: usize) -> Self;
39    #[doc(hidden)]
40    unsafe fn get_unchecked(self) -> usize;
41    #[doc(hidden)]
42    fn option(self) -> Option<usize>;
43    #[doc(hidden)]
44    fn none() -> Self;
45}
46
47/// Marker for Min sorted [`SortedLinkedList`].
48pub struct Min;
49
50/// Marker for Max sorted [`SortedLinkedList`].
51pub struct Max;
52
53/// The linked list kind: min-list or max-list
54pub trait Kind: private::Sealed {
55    #[doc(hidden)]
56    fn ordering() -> Ordering;
57}
58
59impl Kind for Min {
60    fn ordering() -> Ordering {
61        Ordering::Less
62    }
63}
64
65impl Kind for Max {
66    fn ordering() -> Ordering {
67        Ordering::Greater
68    }
69}
70
71/// Sealed traits
72mod private {
73    pub trait Sealed {}
74}
75
76impl private::Sealed for Max {}
77impl private::Sealed for Min {}
78
79/// A node in the [`SortedLinkedList`].
80pub struct Node<T, Idx> {
81    val: MaybeUninit<T>,
82    next: Idx,
83}
84
85/// The linked list.
86pub struct SortedLinkedList<T, Idx, K, const N: usize>
87where
88    Idx: SortedLinkedListIndex,
89{
90    list: [Node<T, Idx>; N],
91    head: Idx,
92    free: Idx,
93    _kind: PhantomData<K>,
94}
95
96// Internal macro for generating indexes for the linkedlist and const new for the linked list
97macro_rules! impl_index_and_const_new {
98    ($name:ident, $ty:ty, $new_name:ident, $max_val:expr) => {
99        /// Index for the [`SortedLinkedList`] with specific backing storage.
100        #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
101        pub struct $name($ty);
102
103        impl SortedLinkedListIndex for $name {
104            #[inline(always)]
105            unsafe fn new_unchecked(val: usize) -> Self {
106                Self::new_unchecked(val as $ty)
107            }
108
109            /// This is only valid if `self.option()` is not `None`.
110            #[inline(always)]
111            unsafe fn get_unchecked(self) -> usize {
112                self.0 as usize
113            }
114
115            #[inline(always)]
116            fn option(self) -> Option<usize> {
117                if self.0 == <$ty>::MAX {
118                    None
119                } else {
120                    Some(self.0 as usize)
121                }
122            }
123
124            #[inline(always)]
125            fn none() -> Self {
126                Self::none()
127            }
128        }
129
130        impl $name {
131            /// Needed for a `const fn new()`.
132            #[inline]
133            const unsafe fn new_unchecked(value: $ty) -> Self {
134                $name(value)
135            }
136
137            /// Needed for a `const fn new()`.
138            #[inline]
139            const fn none() -> Self {
140                $name(<$ty>::MAX)
141            }
142        }
143
144        impl<T, K, const N: usize> SortedLinkedList<T, $name, K, N> {
145            const UNINIT: Node<T, $name> = Node {
146                val: MaybeUninit::uninit(),
147                next: $name::none(),
148            };
149
150            /// Create a new linked list.
151            pub const fn $new_name() -> Self {
152                // Const assert N < MAX
153                crate::sealed::smaller_than::<N, $max_val>();
154
155                let mut list = SortedLinkedList {
156                    list: [Self::UNINIT; N],
157                    head: $name::none(),
158                    free: unsafe { $name::new_unchecked(0) },
159                    _kind: PhantomData,
160                };
161
162                if N == 0 {
163                    list.free = $name::none();
164                    return list;
165                }
166
167                let mut free = 0;
168
169                // Initialize indexes
170                while free < N - 1 {
171                    list.list[free].next = unsafe { $name::new_unchecked(free as $ty + 1) };
172                    free += 1;
173                }
174
175                list
176            }
177        }
178    };
179}
180
181impl_index_and_const_new!(LinkedIndexU8, u8, new_u8, { u8::MAX as usize - 1 });
182impl_index_and_const_new!(LinkedIndexU16, u16, new_u16, { u16::MAX as usize - 1 });
183impl_index_and_const_new!(LinkedIndexUsize, usize, new_usize, { usize::MAX - 1 });
184
185impl<T, Idx, K, const N: usize> SortedLinkedList<T, Idx, K, N>
186where
187    Idx: SortedLinkedListIndex,
188{
189    /// Internal access helper
190    #[inline(always)]
191    fn node_at(&self, index: usize) -> &Node<T, Idx> {
192        // Safety: The entire `self.list` is initialized in `new`, which makes this safe.
193        unsafe { self.list.get_unchecked(index) }
194    }
195
196    /// Internal access helper
197    #[inline(always)]
198    fn node_at_mut(&mut self, index: usize) -> &mut Node<T, Idx> {
199        // Safety: The entire `self.list` is initialized in `new`, which makes this safe.
200        unsafe { self.list.get_unchecked_mut(index) }
201    }
202
203    /// Internal access helper
204    #[inline(always)]
205    fn write_data_in_node_at(&mut self, index: usize, data: T) {
206        // Safety: The entire `self.list` is initialized in `new`, which makes this safe.
207        unsafe {
208            self.node_at_mut(index).val.as_mut_ptr().write(data);
209        }
210    }
211
212    /// Internal access helper
213    #[inline(always)]
214    fn read_data_in_node_at(&self, index: usize) -> &T {
215        // Safety: The entire `self.list` is initialized in `new`, which makes this safe.
216        unsafe { &*self.node_at(index).val.as_ptr() }
217    }
218
219    /// Internal access helper
220    #[inline(always)]
221    fn read_mut_data_in_node_at(&mut self, index: usize) -> &mut T {
222        // Safety: The entire `self.list` is initialized in `new`, which makes this safe.
223        unsafe { &mut *self.node_at_mut(index).val.as_mut_ptr() }
224    }
225
226    /// Internal access helper
227    #[inline(always)]
228    fn extract_data_in_node_at(&mut self, index: usize) -> T {
229        // Safety: The entire `self.list` is initialized in `new`, which makes this safe.
230        unsafe { self.node_at(index).val.as_ptr().read() }
231    }
232}
233
234impl<T, Idx, K, const N: usize> SortedLinkedList<T, Idx, K, N>
235where
236    T: Ord,
237    Idx: SortedLinkedListIndex,
238    K: Kind,
239{
240    /// Pushes a value onto the list without checking if the list is full.
241    ///
242    /// Complexity is worst-case `O(N)`.
243    ///
244    /// # Safety
245    ///
246    /// Assumes that the list is not full.
247    pub unsafe fn push_unchecked(&mut self, value: T) {
248        let new = self.free.get_unchecked();
249
250        // Store the data and update the next free spot
251        self.write_data_in_node_at(new, value);
252        self.free = self.node_at(new).next;
253
254        if let Some(head) = self.head.option() {
255            // Check if we need to replace head
256            if self
257                .read_data_in_node_at(head)
258                .cmp(self.read_data_in_node_at(new))
259                != K::ordering()
260            {
261                self.node_at_mut(new).next = self.head;
262                self.head = Idx::new_unchecked(new);
263            } else {
264                // It's not head, search the list for the correct placement
265                let mut current = head;
266
267                while let Some(next) = self.node_at(current).next.option() {
268                    if self
269                        .read_data_in_node_at(next)
270                        .cmp(self.read_data_in_node_at(new))
271                        != K::ordering()
272                    {
273                        break;
274                    }
275
276                    current = next;
277                }
278
279                self.node_at_mut(new).next = self.node_at(current).next;
280                self.node_at_mut(current).next = Idx::new_unchecked(new);
281            }
282        } else {
283            self.node_at_mut(new).next = self.head;
284            self.head = Idx::new_unchecked(new);
285        }
286    }
287
288    /// Pushes an element to the linked list and sorts it into place.
289    ///
290    /// Complexity is worst-case `O(N)`.
291    ///
292    /// # Example
293    ///
294    /// ```
295    /// use heapless::sorted_linked_list::{SortedLinkedList, Max};
296    /// let mut ll: SortedLinkedList<_, _, Max, 3> = SortedLinkedList::new_usize();
297    ///
298    /// // The largest value will always be first
299    /// ll.push(1).unwrap();
300    /// assert_eq!(ll.peek(), Some(&1));
301    ///
302    /// ll.push(2).unwrap();
303    /// assert_eq!(ll.peek(), Some(&2));
304    ///
305    /// ll.push(3).unwrap();
306    /// assert_eq!(ll.peek(), Some(&3));
307    ///
308    /// // This will not fit in the queue.
309    /// assert_eq!(ll.push(4), Err(4));
310    /// ```
311    pub fn push(&mut self, value: T) -> Result<(), T> {
312        if !self.is_full() {
313            Ok(unsafe { self.push_unchecked(value) })
314        } else {
315            Err(value)
316        }
317    }
318
319    /// Get an iterator over the sorted list.
320    ///
321    /// # Example
322    ///
323    /// ```
324    /// use heapless::sorted_linked_list::{SortedLinkedList, Max};
325    /// let mut ll: SortedLinkedList<_, _, Max, 3> = SortedLinkedList::new_usize();
326    ///
327    /// ll.push(1).unwrap();
328    /// ll.push(2).unwrap();
329    ///
330    /// let mut iter = ll.iter();
331    ///
332    /// assert_eq!(iter.next(), Some(&2));
333    /// assert_eq!(iter.next(), Some(&1));
334    /// assert_eq!(iter.next(), None);
335    /// ```
336    pub fn iter(&self) -> Iter<'_, T, Idx, K, N> {
337        Iter {
338            list: self,
339            index: self.head,
340        }
341    }
342
343    /// Find an element in the list that can be changed and resorted.
344    ///
345    /// # Example
346    ///
347    /// ```
348    /// use heapless::sorted_linked_list::{SortedLinkedList, Max};
349    /// let mut ll: SortedLinkedList<_, _, Max, 3> = SortedLinkedList::new_usize();
350    ///
351    /// ll.push(1).unwrap();
352    /// ll.push(2).unwrap();
353    /// ll.push(3).unwrap();
354    ///
355    /// // Find a value and update it
356    /// let mut find = ll.find_mut(|v| *v == 2).unwrap();
357    /// *find += 1000;
358    /// find.finish();
359    ///
360    /// assert_eq!(ll.pop(), Ok(1002));
361    /// assert_eq!(ll.pop(), Ok(3));
362    /// assert_eq!(ll.pop(), Ok(1));
363    /// assert_eq!(ll.pop(), Err(()));
364    /// ```
365    pub fn find_mut<F>(&mut self, mut f: F) -> Option<FindMut<'_, T, Idx, K, N>>
366    where
367        F: FnMut(&T) -> bool,
368    {
369        let head = self.head.option()?;
370
371        // Special-case, first element
372        if f(self.read_data_in_node_at(head)) {
373            return Some(FindMut {
374                is_head: true,
375                prev_index: Idx::none(),
376                index: self.head,
377                list: self,
378                maybe_changed: false,
379            });
380        }
381
382        let mut current = head;
383
384        while let Some(next) = self.node_at(current).next.option() {
385            if f(self.read_data_in_node_at(next)) {
386                return Some(FindMut {
387                    is_head: false,
388                    prev_index: unsafe { Idx::new_unchecked(current) },
389                    index: unsafe { Idx::new_unchecked(next) },
390                    list: self,
391                    maybe_changed: false,
392                });
393            }
394
395            current = next;
396        }
397
398        None
399    }
400
401    /// Peek at the first element.
402    ///
403    /// # Example
404    ///
405    /// ```
406    /// use heapless::sorted_linked_list::{SortedLinkedList, Max, Min};
407    /// let mut ll_max: SortedLinkedList<_, _, Max, 3> = SortedLinkedList::new_usize();
408    ///
409    /// // The largest value will always be first
410    /// ll_max.push(1).unwrap();
411    /// assert_eq!(ll_max.peek(), Some(&1));
412    /// ll_max.push(2).unwrap();
413    /// assert_eq!(ll_max.peek(), Some(&2));
414    /// ll_max.push(3).unwrap();
415    /// assert_eq!(ll_max.peek(), Some(&3));
416    ///
417    /// let mut ll_min: SortedLinkedList<_, _, Min, 3> = SortedLinkedList::new_usize();
418    ///
419    /// // The Smallest value will always be first
420    /// ll_min.push(3).unwrap();
421    /// assert_eq!(ll_min.peek(), Some(&3));
422    /// ll_min.push(2).unwrap();
423    /// assert_eq!(ll_min.peek(), Some(&2));
424    /// ll_min.push(1).unwrap();
425    /// assert_eq!(ll_min.peek(), Some(&1));
426    /// ```
427    pub fn peek(&self) -> Option<&T> {
428        self.head
429            .option()
430            .map(|head| self.read_data_in_node_at(head))
431    }
432
433    /// Pop an element from the list without checking so the list is not empty.
434    ///
435    /// # Safety
436    ///
437    /// Assumes that the list is not empty.
438    pub unsafe fn pop_unchecked(&mut self) -> T {
439        let head = self.head.get_unchecked();
440        let current = head;
441        self.head = self.node_at(head).next;
442        self.node_at_mut(current).next = self.free;
443        self.free = Idx::new_unchecked(current);
444
445        self.extract_data_in_node_at(current)
446    }
447
448    /// Pops the first element in the list.
449    ///
450    /// Complexity is worst-case `O(1)`.
451    ///
452    /// # Example
453    ///
454    /// ```
455    /// use heapless::sorted_linked_list::{SortedLinkedList, Max};
456    /// let mut ll: SortedLinkedList<_, _, Max, 3> = SortedLinkedList::new_usize();
457    ///
458    /// ll.push(1).unwrap();
459    /// ll.push(2).unwrap();
460    ///
461    /// assert_eq!(ll.pop(), Ok(2));
462    /// assert_eq!(ll.pop(), Ok(1));
463    /// assert_eq!(ll.pop(), Err(()));
464    /// ```
465    pub fn pop(&mut self) -> Result<T, ()> {
466        if !self.is_empty() {
467            Ok(unsafe { self.pop_unchecked() })
468        } else {
469            Err(())
470        }
471    }
472
473    /// Checks if the linked list is full.
474    ///
475    /// # Example
476    ///
477    /// ```
478    /// use heapless::sorted_linked_list::{SortedLinkedList, Max};
479    /// let mut ll: SortedLinkedList<_, _, Max, 3> = SortedLinkedList::new_usize();
480    ///
481    /// assert_eq!(ll.is_full(), false);
482    ///
483    /// ll.push(1).unwrap();
484    /// assert_eq!(ll.is_full(), false);
485    /// ll.push(2).unwrap();
486    /// assert_eq!(ll.is_full(), false);
487    /// ll.push(3).unwrap();
488    /// assert_eq!(ll.is_full(), true);
489    /// ```
490    #[inline]
491    pub fn is_full(&self) -> bool {
492        self.free.option().is_none()
493    }
494
495    /// Checks if the linked list is empty.
496    ///
497    /// # Example
498    ///
499    /// ```
500    /// use heapless::sorted_linked_list::{SortedLinkedList, Max};
501    /// let mut ll: SortedLinkedList<_, _, Max, 3> = SortedLinkedList::new_usize();
502    ///
503    /// assert_eq!(ll.is_empty(), true);
504    ///
505    /// ll.push(1).unwrap();
506    /// assert_eq!(ll.is_empty(), false);
507    /// ```
508    #[inline]
509    pub fn is_empty(&self) -> bool {
510        self.head.option().is_none()
511    }
512}
513
514/// Iterator for the linked list.
515pub struct Iter<'a, T, Idx, K, const N: usize>
516where
517    T: Ord,
518    Idx: SortedLinkedListIndex,
519    K: Kind,
520{
521    list: &'a SortedLinkedList<T, Idx, K, N>,
522    index: Idx,
523}
524
525impl<'a, T, Idx, K, const N: usize> Iterator for Iter<'a, T, Idx, K, N>
526where
527    T: Ord,
528    Idx: SortedLinkedListIndex,
529    K: Kind,
530{
531    type Item = &'a T;
532
533    fn next(&mut self) -> Option<Self::Item> {
534        let index = self.index.option()?;
535
536        let node = self.list.node_at(index);
537        self.index = node.next;
538
539        Some(self.list.read_data_in_node_at(index))
540    }
541}
542
543/// Comes from [`SortedLinkedList::find_mut`].
544pub struct FindMut<'a, T, Idx, K, const N: usize>
545where
546    T: Ord,
547    Idx: SortedLinkedListIndex,
548    K: Kind,
549{
550    list: &'a mut SortedLinkedList<T, Idx, K, N>,
551    is_head: bool,
552    prev_index: Idx,
553    index: Idx,
554    maybe_changed: bool,
555}
556
557impl<'a, T, Idx, K, const N: usize> FindMut<'a, T, Idx, K, N>
558where
559    T: Ord,
560    Idx: SortedLinkedListIndex,
561    K: Kind,
562{
563    fn pop_internal(&mut self) -> T {
564        if self.is_head {
565            // If it is the head element, we can do a normal pop
566            unsafe { self.list.pop_unchecked() }
567        } else {
568            // Somewhere in the list
569            let prev = unsafe { self.prev_index.get_unchecked() };
570            let curr = unsafe { self.index.get_unchecked() };
571
572            // Re-point the previous index
573            self.list.node_at_mut(prev).next = self.list.node_at_mut(curr).next;
574
575            // Release the index into the free queue
576            self.list.node_at_mut(curr).next = self.list.free;
577            self.list.free = self.index;
578
579            self.list.extract_data_in_node_at(curr)
580        }
581    }
582
583    /// This will pop the element from the list.
584    ///
585    /// Complexity is worst-case `O(1)`.
586    ///
587    /// # Example
588    ///
589    /// ```
590    /// use heapless::sorted_linked_list::{SortedLinkedList, Max};
591    /// let mut ll: SortedLinkedList<_, _, Max, 3> = SortedLinkedList::new_usize();
592    ///
593    /// ll.push(1).unwrap();
594    /// ll.push(2).unwrap();
595    /// ll.push(3).unwrap();
596    ///
597    /// // Find a value and update it
598    /// let mut find = ll.find_mut(|v| *v == 2).unwrap();
599    /// find.pop();
600    ///
601    /// assert_eq!(ll.pop(), Ok(3));
602    /// assert_eq!(ll.pop(), Ok(1));
603    /// assert_eq!(ll.pop(), Err(()));
604    /// ```
605    #[inline]
606    pub fn pop(mut self) -> T {
607        self.pop_internal()
608    }
609
610    /// This will resort the element into the correct position in the list if needed. The resorting
611    /// will only happen if the element has been accessed mutably.
612    ///
613    /// Same as calling `drop`.
614    ///
615    /// Complexity is worst-case `O(N)`.
616    ///
617    /// # Example
618    ///
619    /// ```
620    /// use heapless::sorted_linked_list::{SortedLinkedList, Max};
621    /// let mut ll: SortedLinkedList<_, _, Max, 3> = SortedLinkedList::new_usize();
622    ///
623    /// ll.push(1).unwrap();
624    /// ll.push(2).unwrap();
625    /// ll.push(3).unwrap();
626    ///
627    /// let mut find = ll.find_mut(|v| *v == 2).unwrap();
628    /// find.finish(); // No resort, we did not access the value.
629    ///
630    /// let mut find = ll.find_mut(|v| *v == 2).unwrap();
631    /// *find += 1000;
632    /// find.finish(); // Will resort, we accessed (and updated) the value.
633    ///
634    /// assert_eq!(ll.pop(), Ok(1002));
635    /// assert_eq!(ll.pop(), Ok(3));
636    /// assert_eq!(ll.pop(), Ok(1));
637    /// assert_eq!(ll.pop(), Err(()));
638    /// ```
639    #[inline]
640    pub fn finish(self) {
641        drop(self)
642    }
643}
644
645impl<T, Idx, K, const N: usize> Drop for FindMut<'_, T, Idx, K, N>
646where
647    T: Ord,
648    Idx: SortedLinkedListIndex,
649    K: Kind,
650{
651    fn drop(&mut self) {
652        // Only resort the list if the element has changed
653        if self.maybe_changed {
654            let val = self.pop_internal();
655            unsafe { self.list.push_unchecked(val) };
656        }
657    }
658}
659
660impl<T, Idx, K, const N: usize> Deref for FindMut<'_, T, Idx, K, N>
661where
662    T: Ord,
663    Idx: SortedLinkedListIndex,
664    K: Kind,
665{
666    type Target = T;
667
668    fn deref(&self) -> &Self::Target {
669        self.list
670            .read_data_in_node_at(unsafe { self.index.get_unchecked() })
671    }
672}
673
674impl<T, Idx, K, const N: usize> DerefMut for FindMut<'_, T, Idx, K, N>
675where
676    T: Ord,
677    Idx: SortedLinkedListIndex,
678    K: Kind,
679{
680    fn deref_mut(&mut self) -> &mut Self::Target {
681        self.maybe_changed = true;
682        self.list
683            .read_mut_data_in_node_at(unsafe { self.index.get_unchecked() })
684    }
685}
686
687// /// Useful for debug during development.
688// impl<T, Idx, K, const N: usize> fmt::Debug for FindMut<'_, T, Idx, K, N>
689// where
690//     T: Ord + core::fmt::Debug,
691//     Idx: SortedLinkedListIndex,
692//     K: Kind,
693// {
694//     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
695//         f.debug_struct("FindMut")
696//             .field("prev_index", &self.prev_index.option())
697//             .field("index", &self.index.option())
698//             .field(
699//                 "prev_value",
700//                 &self
701//                     .list
702//                     .read_data_in_node_at(self.prev_index.option().unwrap()),
703//             )
704//             .field(
705//                 "value",
706//                 &self.list.read_data_in_node_at(self.index.option().unwrap()),
707//             )
708//             .finish()
709//     }
710// }
711
712impl<T, Idx, K, const N: usize> fmt::Debug for SortedLinkedList<T, Idx, K, N>
713where
714    T: Ord + core::fmt::Debug,
715    Idx: SortedLinkedListIndex,
716    K: Kind,
717{
718    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
719        f.debug_list().entries(self.iter()).finish()
720    }
721}
722
723impl<T, Idx, K, const N: usize> Drop for SortedLinkedList<T, Idx, K, N>
724where
725    Idx: SortedLinkedListIndex,
726{
727    fn drop(&mut self) {
728        let mut index = self.head;
729
730        while let Some(i) = index.option() {
731            let node = self.node_at_mut(i);
732            index = node.next;
733
734            unsafe {
735                ptr::drop_in_place(node.val.as_mut_ptr());
736            }
737        }
738    }
739}
740
741#[cfg(test)]
742mod tests {
743    use super::*;
744
745    #[test]
746    fn const_new() {
747        static mut _V1: SortedLinkedList<u32, LinkedIndexU8, Max, 100> = SortedLinkedList::new_u8();
748        static mut _V2: SortedLinkedList<u32, LinkedIndexU16, Max, 10_000> =
749            SortedLinkedList::new_u16();
750        static mut _V3: SortedLinkedList<u32, LinkedIndexUsize, Max, 100_000> =
751            SortedLinkedList::new_usize();
752    }
753
754    #[test]
755    fn test_peek() {
756        let mut ll: SortedLinkedList<u32, LinkedIndexUsize, Max, 3> = SortedLinkedList::new_usize();
757
758        ll.push(1).unwrap();
759        assert_eq!(ll.peek().unwrap(), &1);
760
761        ll.push(2).unwrap();
762        assert_eq!(ll.peek().unwrap(), &2);
763
764        ll.push(3).unwrap();
765        assert_eq!(ll.peek().unwrap(), &3);
766
767        let mut ll: SortedLinkedList<u32, LinkedIndexUsize, Min, 3> = SortedLinkedList::new_usize();
768
769        ll.push(2).unwrap();
770        assert_eq!(ll.peek().unwrap(), &2);
771
772        ll.push(1).unwrap();
773        assert_eq!(ll.peek().unwrap(), &1);
774
775        ll.push(3).unwrap();
776        assert_eq!(ll.peek().unwrap(), &1);
777    }
778
779    #[test]
780    fn test_full() {
781        let mut ll: SortedLinkedList<u32, LinkedIndexUsize, Max, 3> = SortedLinkedList::new_usize();
782        ll.push(1).unwrap();
783        ll.push(2).unwrap();
784        ll.push(3).unwrap();
785
786        assert!(ll.is_full())
787    }
788
789    #[test]
790    fn test_empty() {
791        let ll: SortedLinkedList<u32, LinkedIndexUsize, Max, 3> = SortedLinkedList::new_usize();
792
793        assert!(ll.is_empty())
794    }
795
796    #[test]
797    fn test_zero_size() {
798        let ll: SortedLinkedList<u32, LinkedIndexUsize, Max, 0> = SortedLinkedList::new_usize();
799
800        assert!(ll.is_empty());
801        assert!(ll.is_full());
802    }
803
804    #[test]
805    fn test_rejected_push() {
806        let mut ll: SortedLinkedList<u32, LinkedIndexUsize, Max, 3> = SortedLinkedList::new_usize();
807        ll.push(1).unwrap();
808        ll.push(2).unwrap();
809        ll.push(3).unwrap();
810
811        // This won't fit
812        let r = ll.push(4);
813
814        assert_eq!(r, Err(4));
815    }
816
817    #[test]
818    fn test_updating() {
819        let mut ll: SortedLinkedList<u32, LinkedIndexUsize, Max, 3> = SortedLinkedList::new_usize();
820        ll.push(1).unwrap();
821        ll.push(2).unwrap();
822        ll.push(3).unwrap();
823
824        let mut find = ll.find_mut(|v| *v == 2).unwrap();
825
826        *find += 1000;
827        find.finish();
828
829        assert_eq!(ll.peek().unwrap(), &1002);
830
831        let mut find = ll.find_mut(|v| *v == 3).unwrap();
832
833        *find += 1000;
834        find.finish();
835
836        assert_eq!(ll.peek().unwrap(), &1003);
837
838        // Remove largest element
839        ll.find_mut(|v| *v == 1003).unwrap().pop();
840
841        assert_eq!(ll.peek().unwrap(), &1002);
842    }
843
844    #[test]
845    fn test_updating_1() {
846        let mut ll: SortedLinkedList<u32, LinkedIndexUsize, Max, 3> = SortedLinkedList::new_usize();
847        ll.push(1).unwrap();
848
849        let v = ll.pop().unwrap();
850
851        assert_eq!(v, 1);
852    }
853
854    #[test]
855    fn test_updating_2() {
856        let mut ll: SortedLinkedList<u32, LinkedIndexUsize, Max, 3> = SortedLinkedList::new_usize();
857        ll.push(1).unwrap();
858
859        let mut find = ll.find_mut(|v| *v == 1).unwrap();
860
861        *find += 1000;
862        find.finish();
863
864        assert_eq!(ll.peek().unwrap(), &1001);
865    }
866}