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: usize = self.index.option()?;
535
536 let node: &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: T = 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(index: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(index: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: Idx = self.head;
729
730 while let Some(i: usize) = index.option() {
731 let node: &mut Node = self.node_at_mut(index:i);
732 index = node.next;
733
734 unsafe {
735 ptr::drop_in_place(to_drop: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}
867