coca/collections/
binary_heap.rs

1//! A fixed-capacity priority queue implemented with a binary heap.
2//!
3//! Insertion and popping the largest element have O(log(n)) time complexity.
4//! Checking the largest element is O(1).
5//!
6//! [`BinaryHeap<T, S, I>`](BinaryHeap) wraps a [`Vec<T, S, I>`](Vec) and
7//! can therefore be converted into the underlying vector type at zero cost.
8//! Converting a vector to a binary heap can be done in-place, and has O(n)
9//! complexity. A binary heap can also be converted to a sorted vector in-place,
10//! allowing it to be used for an O(n log(n)) in-place heap sort.
11
12use crate::storage::{ArrayLayout, Capacity, Storage};
13use crate::collections::vec::{Drain, Vec};
14
15use core::fmt::{self, Debug, Formatter};
16use core::iter::{FromIterator, FusedIterator};
17#[allow(unused_imports)]
18use core::mem::MaybeUninit;
19use core::ops::{Deref, DerefMut};
20
21/// A fixed-capacity priority queue implemented with a binary heap.
22///
23/// This will be a max-heap, i.e. [`heap.pop()`](BinaryHeap::pop) will return
24/// the largest value in the queue. [`core::cmp::Reverse`] or a custom `Ord`
25/// implementation can be used to make a min-heap instead.
26///
27/// It is a logic error for an item to be modified in such a way that the
28/// item's ordering relative to any other item, as determined by the `Ord`
29/// trait, changes while it is in the heap. This is normally only possible
30/// through `Cell`, `RefCell`, global state, I/O, or unsafe code.
31pub struct BinaryHeap<T: Ord, S: Storage<ArrayLayout<T>>, I: Capacity = usize> {
32    a: Vec<T, S, I>,
33}
34
35/// Structure wrapping a mutable reference to the greatest item on a `BinaryHeap`.
36///
37/// This `struct` is created by the [`BinaryHeap::peek_mut()`] method. See its
38/// documentation for more.
39pub struct PeekMut<'a, T: 'a + Ord, S: Storage<ArrayLayout<T>>, I: Capacity = usize> {
40    heap: &'a mut BinaryHeap<T, S, I>,
41}
42
43impl<T: Ord + Debug, S: Storage<ArrayLayout<T>>, I: Capacity> Debug for PeekMut<'_, T, S, I> {
44    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
45        f.debug_tuple("PeekMut").field(&self.heap.peek()).finish()
46    }
47}
48
49impl<T: Ord, S: Storage<ArrayLayout<T>>, I: Capacity> Drop for PeekMut<'_, T, S, I> {
50    fn drop(&mut self) {
51        heapify(self.heap.a.as_mut_slice(), 0);
52    }
53}
54
55impl<T: Ord, S: Storage<ArrayLayout<T>>, I: Capacity> Deref for PeekMut<'_, T, S, I> {
56    type Target = T;
57
58    fn deref(&self) -> &Self::Target {
59        debug_assert!(!self.heap.is_empty());
60        unsafe { self.heap.a.get_unchecked(0) }
61    }
62}
63
64impl<T: Ord, S: Storage<ArrayLayout<T>>, I: Capacity> DerefMut for PeekMut<'_, T, S, I> {
65    fn deref_mut(&mut self) -> &mut Self::Target {
66        debug_assert!(!self.heap.is_empty());
67        unsafe { self.heap.a.get_unchecked_mut(0) }
68    }
69}
70
71impl<T: Ord, S: Storage<ArrayLayout<T>>, I: Capacity> PeekMut<'_, T, S, I> {
72    /// Removes the peeked value from the heap and returns it.
73    pub fn pop(this: PeekMut<'_, T, S, I>) -> T {
74        debug_assert!(!this.heap.is_empty());
75        if let Some(value) = this.heap.pop() {
76            core::mem::forget(this);
77            value
78        } else {
79            unreachable!()
80        }
81    }
82}
83
84impl<T: Ord, S: Storage<ArrayLayout<T>>, I: Capacity> From<S> for BinaryHeap<T, S, I> {
85    /// Converts a contiguous block of memory into an empty binary heap.
86    ///
87    /// # Panics
88    /// This may panic if the index type I cannot represent `buf.capacity()`.
89    fn from(buf: S) -> Self {
90        BinaryHeap { a: Vec::from(buf) }
91    }
92}
93
94// This implementatin is largely based on the pseudocode given in
95// CLRS - Introduction to Algorithms (third edition), Chapter 6
96
97// These utility functions for binary tree traversal differ from the reference
98// because we're using 0-based indexing, i.e. these are equivalent to
99// `PARENT(i + 1) - 1`, `LEFT(i + 1) - 1`, and `RIGHT(i + 1) - 1`, respectively.
100#[inline(always)]
101fn parent(i: usize) -> usize {
102    (i + 1) / 2 - 1
103}
104
105#[inline(always)]
106fn left(i: usize) -> usize {
107    2 * (i + 1) - 1
108}
109
110#[inline(always)]
111fn right(i: usize) -> usize {
112    2 * (i + 1)
113}
114
115fn heapify<T: Ord>(a: &mut [T], i: usize) {
116    let l = left(i);
117    let r = right(i);
118    let mut largest = if l < a.len() && a[l] > a[i] { l } else { i };
119    if r < a.len() && a[r] > a[largest] {
120        largest = r;
121    }
122    if largest != i {
123        a.swap(i, largest);
124        heapify(a, largest);
125    }
126}
127
128impl<T: Ord + Debug, S: Storage<ArrayLayout<T>>, I: Capacity> Debug for BinaryHeap<T, S, I> {
129    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
130        f.debug_list().entries(self.iter()).finish()
131    }
132}
133
134impl<T: Ord, S: Storage<ArrayLayout<T>>, I: Capacity> From<Vec<T, S, I>> for BinaryHeap<T, S, I> {
135    /// Converts a [`Vec`] into a binary heap.
136    ///
137    /// This conversion happens in-place, and has O(n) time complexity.
138    fn from(mut vec: Vec<T, S, I>) -> Self {
139        let a = vec.as_mut_slice();
140        for i in (0..(a.len() / 2)).rev() {
141            heapify(a, i);
142        }
143        BinaryHeap { a: vec }
144    }
145}
146
147impl<T: Ord, S: Storage<ArrayLayout<T>>, I: Capacity> BinaryHeap<T, S, I> {
148    /// Returns a reference to the greatest item in the binary heap, or [`None`] if it is empty.
149    #[inline]
150    pub fn peek(&self) -> Option<&T> {
151        self.a.first()
152    }
153
154    /// Returns a mutable reference to the greatest item in the binary heap, or
155    /// [`None`] if it is empty.
156    ///
157    /// Note: If the `PeekMut` value is leaked, the heap may be left in an
158    /// inconsistent state.
159    ///
160    /// # Examples
161    /// ```
162    /// let mut backing_region = [core::mem::MaybeUninit::<u32>::uninit(); 3];
163    /// let mut heap = coca::collections::SliceHeap::<_>::from(&mut backing_region[..]);
164    /// heap.try_push(3);
165    /// heap.try_push(5);
166    /// heap.try_push(1);
167    ///
168    /// {
169    ///     let mut val = heap.peek_mut().unwrap();
170    ///     *val = 0;
171    /// }
172    ///
173    /// assert_eq!(heap.pop(), Some(3));
174    /// assert_eq!(heap.pop(), Some(1));
175    /// assert_eq!(heap.pop(), Some(0));
176    /// ```
177    #[inline]
178    pub fn peek_mut(&mut self) -> Option<PeekMut<T, S, I>> {
179        if self.is_empty() {
180            None
181        } else {
182            Some(PeekMut { heap: self })
183        }
184    }
185
186    /// Removes the greatest element from the binary heap and returns it, or [`None`] if it is empty.
187    ///
188    /// # Examples
189    /// ```
190    /// use coca::collections::{SliceHeap, SliceVec};
191    /// let mut backing_region = [core::mem::MaybeUninit::<u32>::uninit(); 3];
192    /// let mut vec = SliceVec::<u32>::from(&mut backing_region[..]);
193    /// vec.push(1); vec.push(3);
194    ///
195    /// let mut heap = SliceHeap::from(vec);
196    ///
197    /// assert_eq!(heap.pop(), Some(3));
198    /// assert_eq!(heap.pop(), Some(1));
199    /// assert_eq!(heap.pop(), None);
200    /// ```
201    pub fn pop(&mut self) -> Option<T> {
202        if self.is_empty() {
203            return None;
204        }
205
206        let result = self.a.swap_remove(I::from_usize(0));
207        heapify(self.a.as_mut_slice(), 0);
208        Some(result)
209    }
210
211    /// Pushes an item onto the binary heap.
212    ///
213    /// # Panics
214    /// Panics if the heap is already at capacity. See [`try_push`](BinaryHeap::try_push)
215    /// for a checked version that never panics.
216    #[inline]
217    pub fn push(&mut self, item: T) {
218        #[cold]
219        #[inline(never)]
220        fn assert_failed() -> ! {
221            panic!("binary heap is already at capacity")
222        }
223
224        if self.try_push(item).is_err() {
225            assert_failed();
226        }
227    }
228
229    /// Pushes an item onto the binary heap, returning `Err(item)` if it is full.
230    ///
231    /// # Examples
232    /// ```
233    /// let mut backing_region = [core::mem::MaybeUninit::<u32>::uninit(); 3];
234    /// let mut heap = coca::collections::SliceHeap::<_>::from(&mut backing_region[..]);
235    /// heap.try_push(3);
236    /// heap.try_push(5);
237    /// heap.try_push(1);
238    ///
239    /// assert_eq!(heap.len(), 3);
240    /// assert_eq!(heap.peek(), Some(&5));
241    /// ```
242    pub fn try_push(&mut self, item: T) -> Result<(), T> {
243        self.a.try_push(item)?;
244        let a = self.a.as_mut_slice();
245        let mut i = a.len() - 1;
246        while i > 0 && a[parent(i)] < a[i] {
247            a.swap(i, parent(i));
248            i = parent(i);
249        }
250        Ok(())
251    }
252
253    /// Returns the number of elements the binary heap can hold.
254    #[inline]
255    pub fn capacity(&self) -> usize {
256        self.a.capacity()
257    }
258
259    /// Returns the number of elements in the binary heap, also referred to as its *length*.
260    #[inline]
261    pub fn len(&self) -> usize {
262        self.a.len()
263    }
264
265    /// Returns `true` if the binary heap contains no elements.
266    #[inline]
267    pub fn is_empty(&self) -> bool {
268        self.a.is_empty()
269    }
270
271    /// Returns `true` if the binary heap contains the maximum number of elements.
272    #[inline]
273    pub fn is_full(&self) -> bool {
274        self.a.is_full()
275    }
276
277    /// Returns an iterator visiting all values in the underlying vector in arbitrary order.
278    pub fn iter(&self) -> impl Iterator<Item = &T> {
279        self.a.iter()
280    }
281
282    /// Clears the binary heap, returning an iterator over the removed elements.
283    /// The elements are removed in arbitrary order.
284    ///
285    /// # Examples
286    /// ```
287    /// let mut backing_region = [core::mem::MaybeUninit::<u32>::uninit(); 3];
288    /// let mut heap = coca::collections::SliceHeap::<_>::from(&mut backing_region[..]);
289    /// heap.push(1); heap.push(3);
290    /// assert!(!heap.is_empty());
291    ///
292    /// let mut iter = heap.drain();
293    /// assert!(iter.next().is_some());
294    /// assert!(iter.next().is_some());
295    /// assert!(iter.next().is_none());
296    /// drop(iter);
297    ///
298    /// assert!(heap.is_empty());
299    /// ```
300    #[inline]
301    pub fn drain(&mut self) -> Drain<'_, T, S, I> {
302        self.a.drain(..)
303    }
304
305    /// Returns an iterator which retrieves elements in heap order. The retrieved
306    /// elements are removed from the original heap. The remaining elements will
307    /// be removed on drop in heap order.
308    ///
309    /// # Remarks
310    /// `.drain_sorted()` is O(n log(n)), much slower than [`.drain()`](BinaryHeap::drain).
311    /// The latter is preferable in most cases.
312    ///
313    /// # Examples
314    /// ```
315    /// let mut backing_region = [core::mem::MaybeUninit::<u32>::uninit(); 3];
316    /// let mut heap = coca::collections::SliceHeap::<_>::from(&mut backing_region[..]);
317    /// heap.push(1); heap.push(3); heap.push(5);
318    ///
319    /// let mut iter = heap.drain_sorted();
320    /// assert_eq!(iter.next(), Some(5));
321    /// drop(iter);
322    /// assert!(heap.is_empty());
323    /// ```
324    #[inline]
325    pub fn drain_sorted(&mut self) -> DrainSorted<'_, T, S, I> {
326        DrainSorted { heap: self }
327    }
328
329    /// Drops all items from the binary heap.
330    #[inline]
331    pub fn clear(&mut self) {
332        self.a.clear();
333    }
334
335    /// Consumes the `BinaryHeap` and returns the underlying vector in arbitrary order.
336    #[inline]
337    pub fn into_vec(self) -> Vec<T, S, I> {
338        self.a
339    }
340
341    /// Consumes the `BinaryHeap` and returns a vector in sorted (ascending) order.
342    ///
343    /// # Examples
344    /// ```
345    /// let mut backing_region = [core::mem::MaybeUninit::<u32>::uninit(); 5];
346    /// let mut heap = coca::collections::SliceHeap::<_>::from(&mut backing_region[..]);
347    /// heap.push(1); heap.push(5); heap.push(3); heap.push(2); heap.push(4);
348    /// let vec = heap.into_sorted_vec();
349    /// assert_eq!(vec, &[1, 2, 3, 4, 5][..]);
350    /// ```
351    pub fn into_sorted_vec(self) -> Vec<T, S, I> {
352        let mut result = self.into_vec();
353        let a = result.as_mut_slice();
354        for i in (1..a.len()).rev() {
355            a.swap(0, i);
356            heapify(&mut a[..i], 0);
357        }
358        result
359    }
360
361    /// Consumes the `BinaryHeap` and returns an iterator which yields elements
362    /// in heap order.
363    ///
364    /// When dropped, the remaining elements will be dropped in heap order.
365    ///
366    /// # Remarks
367    /// `.into_iter_sorted()` is O(n log(n)), much slower than [`.into_iter()`](BinaryHeap::into_iter).
368    /// The latter is preferable in most cases.
369    ///
370    /// # Examples
371    /// ```
372    /// let mut backing_region = [core::mem::MaybeUninit::<u32>::uninit(); 3];
373    /// let mut heap = coca::collections::SliceHeap::<_>::from(&mut backing_region[..]);
374    /// heap.push(1); heap.push(3); heap.push(5);
375    ///
376    /// let mut iter = heap.into_iter_sorted();
377    /// assert_eq!(iter.next(), Some(5));
378    /// assert_eq!(iter.next(), Some(3));
379    /// assert_eq!(iter.next(), Some(1));
380    /// ```
381    pub fn into_iter_sorted(self) -> IntoIterSorted<T, S, I> {
382        IntoIterSorted { heap: self }
383    }
384}
385
386impl<T: Ord, S: Storage<ArrayLayout<T>>, I: Capacity> IntoIterator for BinaryHeap<T, S, I> {
387    type Item = T;
388    type IntoIter = <Vec<T, S, I> as IntoIterator>::IntoIter;
389    fn into_iter(self) -> Self::IntoIter {
390        self.a.into_iter()
391    }
392}
393
394impl<T1, T2: Ord, S: Storage<ArrayLayout<T2>>, I: Capacity> Extend<T1> for BinaryHeap<T2, S, I>
395where
396    Vec<T2, S, I>: Extend<T1>,
397{
398    fn extend<T: IntoIterator<Item = T1>>(&mut self, iter: T) {
399        self.a.extend(iter);
400        for i in (0..(self.a.len() / 2)).rev() {
401            heapify(self.a.as_mut_slice(), i);
402        }
403    }
404}
405
406impl<T: Ord, S: Storage<ArrayLayout<T>>, I: Capacity> FromIterator<T> for BinaryHeap<T, S, I>
407where
408    Vec<T, S, I>: FromIterator<T>,
409{
410    /// Creates a binary heap from an iterator.
411    ///
412    /// # Panics
413    /// Panics if the iterator yields more elements than the binary heap can hold.
414    fn from_iter<It: IntoIterator<Item = T>>(iter: It) -> Self {
415        let a = Vec::<T, S, I>::from_iter(iter);
416        Self::from(a)
417    }
418}
419
420/// A draining iterator over the elements of a `BinaryHeap`.
421///
422/// This `struct` is created by [`BinaryHeap::drain_sorted()`].
423/// See its documentation for more.
424pub struct DrainSorted<'a, T: Ord, S: Storage<ArrayLayout<T>>, I: Capacity> {
425    heap: &'a mut BinaryHeap<T, S, I>,
426}
427
428impl<T: Ord, S: Storage<ArrayLayout<T>>, I: Capacity> Iterator for DrainSorted<'_, T, S, I> {
429    type Item = T;
430
431    fn size_hint(&self) -> (usize, Option<usize>) {
432        let size = self.len();
433        (size, Some(size))
434    }
435
436    fn next(&mut self) -> Option<Self::Item> {
437        self.heap.pop()
438    }
439}
440
441impl<T: Ord, S: Storage<ArrayLayout<T>>, I: Capacity> ExactSizeIterator for DrainSorted<'_, T, S, I> {}
442impl<T: Ord, S: Storage<ArrayLayout<T>>, I: Capacity> FusedIterator for DrainSorted<'_, T, S, I> {}
443
444impl<T: Ord, S: Storage<ArrayLayout<T>>, I: Capacity> Drop for DrainSorted<'_, T, S, I> {
445    fn drop(&mut self) {
446        self.for_each(drop);
447    }
448}
449
450/// A consuming iterator that moves out of a `BinaryHeap`.
451///
452/// This `struct` is created by [`BinaryHeap::into_iter_sorted()`].
453/// See its documentation for more.
454#[derive(Debug)]
455pub struct IntoIterSorted<T: Ord, S: Storage<ArrayLayout<T>>, I: Capacity> {
456    heap: BinaryHeap<T, S, I>,
457}
458
459impl<T: Ord, S: Storage<ArrayLayout<T>>, I: Capacity> Iterator for IntoIterSorted<T, S, I> {
460    type Item = T;
461
462    #[inline]
463    fn size_hint(&self) -> (usize, Option<usize>) {
464        let size = self.heap.len();
465        (size, Some(size))
466    }
467
468    #[inline]
469    fn next(&mut self) -> Option<T> {
470        self.heap.pop()
471    }
472}
473
474impl<T: Ord, S: Storage<ArrayLayout<T>>, I: Capacity> ExactSizeIterator for IntoIterSorted<T, S, I> {}
475impl<T: Ord, S: Storage<ArrayLayout<T>>, I: Capacity> FusedIterator for IntoIterSorted<T, S, I> {}
476
477impl<T: Clone + Ord, S: Storage<ArrayLayout<T>>, I: Capacity> Clone for IntoIterSorted<T, S, I>
478where
479    BinaryHeap<T, S, I>: Clone,
480{
481    fn clone(&self) -> Self {
482        self.heap.clone().into_iter_sorted()
483    }
484}
485
486impl<T: Ord, S: Storage<ArrayLayout<T>>, I: Capacity> Drop for IntoIterSorted<T, S, I> {
487    fn drop(&mut self) {
488        self.for_each(drop);
489    }
490}
491
492#[cfg(feature = "alloc")]
493#[cfg_attr(docs_rs, doc(cfg(feature = "alloc")))]
494impl<T: Copy + Ord, I: Capacity> crate::collections::AllocHeap<T, I> {
495    /// Constructs a new, empty `AllocHeap<T, I>` with the specified capacity.
496    ///
497    /// # Panics
498    /// Panics if the specified capacity cannot be represented by a `usize`.
499    pub fn with_capacity(capacity: I) -> Self {
500        BinaryHeap {
501            a: Vec::with_capacity(capacity),
502        }
503    }
504}
505
506#[cfg(feature = "alloc")]
507#[cfg_attr(docs_rs, doc(cfg(feature = "alloc")))]
508impl<T: Copy + Ord, I: Capacity> Clone for crate::collections::AllocHeap<T, I> {
509    fn clone(&self) -> Self {
510        BinaryHeap { a: self.a.clone() }
511    }
512}
513
514impl<T: Ord, I: Capacity, const C: usize> BinaryHeap<T, [MaybeUninit<T>; C], I> {
515    /// Constructs a new, empty `BinaryHeap` backed by an inline array.
516    ///
517    /// # Panics
518    /// Panics if `C` cannot be represented as a value of type `I`.
519    ///
520    /// # Examples
521    /// ```
522    /// let heap = coca::collections::InlineHeap::<char, 4>::new();
523    /// assert_eq!(heap.capacity(), 4);
524    /// assert!(heap.is_empty());
525    /// ```
526    pub fn new() -> Self {
527        let a = Vec::new();
528        BinaryHeap { a }
529    }
530}
531
532impl<T: Ord, I: Capacity, const C: usize> Default for BinaryHeap<T, [MaybeUninit<T>; C], I> {
533    fn default() -> Self {
534        Self::new()
535    }
536}
537
538impl<T: Clone + Ord, I: Capacity, const C: usize> Clone for BinaryHeap<T, [MaybeUninit<T>; C], I> {
539    fn clone(&self) -> Self {
540        BinaryHeap { a: self.a.clone() }
541    }
542}
543
544#[cfg(test)]
545mod tests {
546    use super::*;
547
548    #[test]
549    fn tree_traversal_utilities() {
550        assert_eq!(left(0), 1);
551        assert_eq!(right(0), 2);
552        assert_eq!(parent(1), 0);
553        assert_eq!(parent(2), 0);
554
555        for i in 1..=1000 {
556            let l = left(i);
557            let r = right(i);
558            assert_eq!(l + 1, r);
559            assert_eq!(parent(l), i);
560            assert_eq!(parent(r), i);
561
562            let ll = left(l);
563            let lr = right(l);
564            let rl = left(r);
565            let rr = right(r);
566
567            assert_eq!(ll + 1, lr);
568            assert_eq!(rl + 1, rr);
569            assert_eq!(parent(parent(ll)), i);
570            assert_eq!(parent(parent(lr)), i);
571            assert_eq!(parent(parent(rl)), i);
572            assert_eq!(parent(parent(rr)), i);
573        }
574    }
575
576    #[test]
577    fn push_and_pop_randomized_inputs() {
578        use rand::{rngs::SmallRng, RngCore, SeedableRng};
579
580        let mut backing_region = [core::mem::MaybeUninit::<u32>::uninit(); 32];
581        let mut heap = crate::collections::SliceHeap::<_>::from(&mut backing_region[..]);
582
583        let mut rng = SmallRng::from_seed(crate::test_utils::RNG_SEED);
584
585        let mut newest = 0;
586        for _ in 0..32 {
587            newest = rng.next_u32();
588            heap.push(newest);
589        }
590
591        let mut prev = u32::max_value();
592        for _ in 0..1000 {
593            let x = heap.pop().unwrap();
594            assert!(x <= prev || x == newest);
595            prev = x;
596
597            newest = rng.next_u32();
598            heap.push(newest);
599        }
600    }
601
602    #[test]
603    fn iterators_take_and_drop_correctly() {
604        use core::cell::RefCell;
605
606        #[derive(Clone)]
607        struct Droppable<'a, 'b> {
608            value: usize,
609            log: &'a RefCell<crate::collections::SliceVec<'b, usize>>,
610        }
611
612        impl PartialEq for Droppable<'_, '_> {
613            fn eq(&self, rhs: &Self) -> bool {
614                self.value == rhs.value
615            }
616        }
617
618        impl Eq for Droppable<'_, '_> {}
619
620        impl PartialOrd for Droppable<'_, '_> {
621            fn partial_cmp(&self, rhs: &Self) -> Option<core::cmp::Ordering> {
622                Some(self.cmp(rhs))
623            }
624        }
625
626        impl Ord for Droppable<'_, '_> {
627            fn cmp(&self, rhs: &Self) -> core::cmp::Ordering {
628                self.value.cmp(&rhs.value)
629            }
630        }
631
632        impl Drop for Droppable<'_, '_> {
633            fn drop(&mut self) {
634                self.log.borrow_mut().push(self.value);
635            }
636        }
637
638        let mut backing_array = [MaybeUninit::<usize>::uninit(); 16];
639        let drop_log = RefCell::new(crate::collections::SliceVec::<_>::from(&mut backing_array[..]));
640
641        let mut backing_region = [
642            core::mem::MaybeUninit::<Droppable>::uninit(),
643            core::mem::MaybeUninit::<Droppable>::uninit(),
644            core::mem::MaybeUninit::<Droppable>::uninit(),
645            core::mem::MaybeUninit::<Droppable>::uninit(),
646            core::mem::MaybeUninit::<Droppable>::uninit(),
647            core::mem::MaybeUninit::<Droppable>::uninit(),
648            core::mem::MaybeUninit::<Droppable>::uninit(),
649            core::mem::MaybeUninit::<Droppable>::uninit(),
650        ];
651
652        let mut heap = crate::collections::SliceHeap::<Droppable>::from(&mut backing_region[..]);
653        for i in 1..=8 {
654            heap.push(Droppable {
655                value: i,
656                log: &drop_log,
657            });
658        }
659
660        let mut drain_iter = heap.drain_sorted();
661        assert_eq!(drain_iter.next().unwrap().value, 8);
662        assert_eq!(drain_iter.next().unwrap().value, 7);
663        assert_eq!(drop_log.borrow().len(), 2);
664
665        drop(drain_iter);
666        assert_eq!(drop_log.borrow().len(), 8);
667        assert_eq!(heap.len(), 0);
668
669        for i in 1..=8 {
670            heap.push(Droppable {
671                value: i,
672                log: &drop_log,
673            });
674        }
675
676        let mut into_iter = heap.into_iter_sorted();
677        assert_eq!(into_iter.next().unwrap().value, 8);
678        assert_eq!(into_iter.next().unwrap().value, 7);
679        assert_eq!(into_iter.next().unwrap().value, 6);
680        assert_eq!(drop_log.borrow().len(), 11);
681
682        drop(into_iter);
683        assert_eq!(drop_log.borrow().len(), 16);
684
685        assert_eq!(
686            drop_log.borrow().as_slice(),
687            &[8, 7, 6, 5, 4, 3, 2, 1, 8, 7, 6, 5, 4, 3, 2, 1]
688        );
689    }
690}
coca/collections/binary_heap.rs

coca/collections/
binary_heap.rs
