heapless/binary_heap.rs
1//! A priority queue implemented with a binary heap.
2//!
3//! Insertion and popping the largest element have *O*(log n) time complexity.
4//! Checking the smallest/largest element is *O*(1).
5
6// TODO not yet implemented
7// Converting a vector to a binary heap can be done in-place, and has *O*(n) complexity. A binary
8// heap can also be converted to a sorted vector in-place, allowing it to be used for an
9// *O*(n log n) in-place heapsort.
10
11use core::{
12 cmp::Ordering,
13 fmt,
14 marker::PhantomData,
15 mem::{self, ManuallyDrop},
16 ops::{Deref, DerefMut},
17 ptr, slice,
18};
19
20use crate::vec::{OwnedVecStorage, Vec, VecInner, VecStorage, ViewVecStorage};
21
22/// Min-heap
23pub enum Min {}
24
25/// Max-heap
26pub enum Max {}
27
28/// The binary heap kind: min-heap or max-heap
29pub trait Kind: private::Sealed {
30 #[doc(hidden)]
31 fn ordering() -> Ordering;
32}
33
34impl Kind for Min {
35 fn ordering() -> Ordering {
36 Ordering::Less
37 }
38}
39
40impl Kind for Max {
41 fn ordering() -> Ordering {
42 Ordering::Greater
43 }
44}
45
46/// Sealed traits
47mod private {
48 pub trait Sealed {}
49}
50
51impl private::Sealed for Max {}
52impl private::Sealed for Min {}
53
54/// Base struct for [`BinaryHeap`] and [`BinaryHeapView`], generic over the [`VecStorage`].
55///
56/// In most cases you should use [`BinaryHeap`] or [`BinaryHeapView`] directly. Only use this
57/// struct if you want to write code that's generic over both.
58pub struct BinaryHeapInner<T, K, S: VecStorage<T> + ?Sized> {
59 pub(crate) _kind: PhantomData<K>,
60 pub(crate) data: VecInner<T, usize, S>,
61}
62
63/// A priority queue implemented with a binary heap.
64///
65/// This can be either a min-heap or a max-heap.
66///
67/// It is a logic error for an item to be modified in such a way that the item's ordering relative
68/// to any other item, as determined by the `Ord` trait, changes while it is in the heap. This is
69/// normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
70///
71/// ```
72/// use heapless::binary_heap::{BinaryHeap, Max};
73///
74/// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
75///
76/// // We can use peek to look at the next item in the heap. In this case,
77/// // there's no items in there yet so we get None.
78/// assert_eq!(heap.peek(), None);
79///
80/// // Let's add some scores...
81/// heap.push(1).unwrap();
82/// heap.push(5).unwrap();
83/// heap.push(2).unwrap();
84///
85/// // Now peek shows the most important item in the heap.
86/// assert_eq!(heap.peek(), Some(&5));
87///
88/// // We can check the length of a heap.
89/// assert_eq!(heap.len(), 3);
90///
91/// // We can iterate over the items in the heap, although they are returned in
92/// // a random order.
93/// for x in &heap {
94/// println!("{}", x);
95/// }
96///
97/// // If we instead pop these scores, they should come back in order.
98/// assert_eq!(heap.pop(), Some(5));
99/// assert_eq!(heap.pop(), Some(2));
100/// assert_eq!(heap.pop(), Some(1));
101/// assert_eq!(heap.pop(), None);
102///
103/// // We can clear the heap of any remaining items.
104/// heap.clear();
105///
106/// // The heap should now be empty.
107/// assert!(heap.is_empty())
108/// ```
109pub type BinaryHeap<T, K, const N: usize> = BinaryHeapInner<T, K, OwnedVecStorage<T, N>>;
110
111/// A priority queue implemented with a binary heap.
112///
113/// This can be either a min-heap or a max-heap.
114///
115/// It is a logic error for an item to be modified in such a way that the item's ordering relative
116/// to any other item, as determined by the `Ord` trait, changes while it is in the heap. This is
117/// normally only possible through `Cell`, `RefCell`, global state, I/O, or unsafe code.
118///
119/// ```
120/// use heapless::binary_heap::{BinaryHeap, BinaryHeapView, Max};
121///
122/// let mut heap_buffer: BinaryHeap<_, Max, 8> = BinaryHeap::new();
123/// let heap: &mut BinaryHeapView<_, Max> = &mut heap_buffer;
124///
125/// // We can use peek to look at the next item in the heap. In this case,
126/// // there's no items in there yet so we get None.
127/// assert_eq!(heap.peek(), None);
128///
129/// // Let's add some scores...
130/// heap.push(1).unwrap();
131/// heap.push(5).unwrap();
132/// heap.push(2).unwrap();
133///
134/// // Now peek shows the most important item in the heap.
135/// assert_eq!(heap.peek(), Some(&5));
136///
137/// // We can check the length of a heap.
138/// assert_eq!(heap.len(), 3);
139///
140/// // We can iterate over the items in the heap, although they are returned in
141/// // a random order.
142/// for x in &*heap {
143/// println!("{}", x);
144/// }
145///
146/// // If we instead pop these scores, they should come back in order.
147/// assert_eq!(heap.pop(), Some(5));
148/// assert_eq!(heap.pop(), Some(2));
149/// assert_eq!(heap.pop(), Some(1));
150/// assert_eq!(heap.pop(), None);
151///
152/// // We can clear the heap of any remaining items.
153/// heap.clear();
154///
155/// // The heap should now be empty.
156/// assert!(heap.is_empty())
157/// ```
158pub type BinaryHeapView<T, K> = BinaryHeapInner<T, K, ViewVecStorage<T>>;
159
160impl<T, K, const N: usize> BinaryHeap<T, K, N> {
161 /* Constructors */
162 /// Creates an empty `BinaryHeap` as a $K-heap.
163 ///
164 /// ```
165 /// use heapless::binary_heap::{BinaryHeap, Max};
166 ///
167 /// // allocate the binary heap on the stack
168 /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
169 /// heap.push(4).unwrap();
170 ///
171 /// // allocate the binary heap in a static variable
172 /// static mut HEAP: BinaryHeap<i32, Max, 8> = BinaryHeap::new();
173 /// ```
174 pub const fn new() -> Self {
175 Self {
176 _kind: PhantomData,
177 data: Vec::new(),
178 }
179 }
180}
181
182impl<T, K, const N: usize> BinaryHeap<T, K, N> {
183 /// Returns the underlying `Vec<T,N>`. Order is arbitrary and time is *O*(1).
184 pub fn into_vec(self) -> Vec<T, N, usize> {
185 self.data
186 }
187}
188
189impl<T, K, S: VecStorage<T>> BinaryHeapInner<T, K, S> {
190 /// Get a reference to the `BinaryHeap`, erasing the `N` const-generic.
191 pub fn as_view(&self) -> &BinaryHeapView<T, K> {
192 S::as_binary_heap_view(self)
193 }
194 /// Get a mutable reference to the `BinaryHeap`, erasing the `N` const-generic.
195 pub fn as_mut_view(&mut self) -> &mut BinaryHeapView<T, K> {
196 S::as_binary_heap_view_mut(self)
197 }
198}
199
200impl<T, K, S: VecStorage<T> + ?Sized> BinaryHeapInner<T, K, S>
201where
202 T: Ord,
203 K: Kind,
204{
205 /* Public API */
206 /// Returns the capacity of the binary heap.
207 pub fn capacity(&self) -> usize {
208 self.data.capacity()
209 }
210
211 /// Drops all items from the binary heap.
212 ///
213 /// ```
214 /// use heapless::binary_heap::{BinaryHeap, Max};
215 ///
216 /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
217 /// heap.push(1).unwrap();
218 /// heap.push(3).unwrap();
219 ///
220 /// assert!(!heap.is_empty());
221 ///
222 /// heap.clear();
223 ///
224 /// assert!(heap.is_empty());
225 /// ```
226 pub fn clear(&mut self) {
227 self.data.clear();
228 }
229
230 /// Returns the length of the binary heap.
231 ///
232 /// ```
233 /// use heapless::binary_heap::{BinaryHeap, Max};
234 ///
235 /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
236 /// heap.push(1).unwrap();
237 /// heap.push(3).unwrap();
238 ///
239 /// assert_eq!(heap.len(), 2);
240 /// ```
241 pub fn len(&self) -> usize {
242 self.data.len()
243 }
244
245 /// Checks if the binary heap is empty.
246 ///
247 /// ```
248 /// use heapless::binary_heap::{BinaryHeap, Max};
249 ///
250 /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
251 ///
252 /// assert!(heap.is_empty());
253 ///
254 /// heap.push(3).unwrap();
255 /// heap.push(5).unwrap();
256 /// heap.push(1).unwrap();
257 ///
258 /// assert!(!heap.is_empty());
259 /// ```
260 pub fn is_empty(&self) -> bool {
261 self.len() == 0
262 }
263
264 /// Checks if the binary heap is full.
265 ///
266 /// ```
267 /// use heapless::binary_heap::{BinaryHeap, Max};
268 ///
269 /// let mut heap: BinaryHeap<_, Max, 4> = BinaryHeap::new();
270 ///
271 /// assert!(!heap.is_full());
272 ///
273 /// heap.push(1).unwrap();
274 /// heap.push(2).unwrap();
275 /// heap.push(3).unwrap();
276 /// heap.push(4).unwrap();
277 ///
278 /// assert!(heap.is_full());
279 /// ```
280 pub fn is_full(&self) -> bool {
281 self.len() == self.capacity()
282 }
283
284 /// Returns an iterator visiting all values in the underlying vector, in arbitrary order.
285 ///
286 /// ```
287 /// use heapless::binary_heap::{BinaryHeap, Max};
288 ///
289 /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
290 /// heap.push(1).unwrap();
291 /// heap.push(2).unwrap();
292 /// heap.push(3).unwrap();
293 /// heap.push(4).unwrap();
294 ///
295 /// // Print 1, 2, 3, 4 in arbitrary order
296 /// for x in heap.iter() {
297 /// println!("{}", x);
298 /// }
299 /// ```
300 pub fn iter(&self) -> slice::Iter<'_, T> {
301 self.data.as_slice().iter()
302 }
303
304 /// Returns a mutable iterator visiting all values in the underlying vector, in arbitrary order.
305 ///
306 /// **WARNING** Mutating the items in the binary heap can leave the heap in an inconsistent
307 /// state.
308 pub fn iter_mut(&mut self) -> slice::IterMut<'_, T> {
309 self.data.as_mut_slice().iter_mut()
310 }
311
312 /// Returns the *top* (greatest if max-heap, smallest if min-heap) item in the binary heap, or
313 /// None if it is empty.
314 ///
315 /// ```
316 /// use heapless::binary_heap::{BinaryHeap, Max};
317 ///
318 /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
319 /// assert_eq!(heap.peek(), None);
320 ///
321 /// heap.push(1).unwrap();
322 /// heap.push(5).unwrap();
323 /// heap.push(2).unwrap();
324 /// assert_eq!(heap.peek(), Some(&5));
325 /// ```
326 pub fn peek(&self) -> Option<&T> {
327 self.data.as_slice().first()
328 }
329
330 /// Returns a mutable reference to the greatest item in the binary heap, or
331 /// `None` if it is empty.
332 ///
333 /// Note: If the `PeekMut` value is leaked, the heap may be in an
334 /// inconsistent state.
335 ///
336 /// # Examples
337 ///
338 /// Basic usage:
339 ///
340 /// ```
341 /// use heapless::binary_heap::{BinaryHeap, Max};
342 ///
343 /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
344 /// assert!(heap.peek_mut().is_none());
345 ///
346 /// heap.push(1);
347 /// heap.push(5);
348 /// heap.push(2);
349 /// {
350 /// let mut val = heap.peek_mut().unwrap();
351 /// *val = 0;
352 /// }
353 ///
354 /// assert_eq!(heap.peek(), Some(&2));
355 /// ```
356 pub fn peek_mut(&mut self) -> Option<PeekMutInner<'_, T, K, S>> {
357 if self.is_empty() {
358 None
359 } else {
360 Some(PeekMutInner {
361 heap: self,
362 sift: true,
363 })
364 }
365 }
366
367 /// Removes the *top* (greatest if max-heap, smallest if min-heap) item from the binary heap and
368 /// returns it, or None if it is empty.
369 ///
370 /// ```
371 /// use heapless::binary_heap::{BinaryHeap, Max};
372 ///
373 /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
374 /// heap.push(1).unwrap();
375 /// heap.push(3).unwrap();
376 ///
377 /// assert_eq!(heap.pop(), Some(3));
378 /// assert_eq!(heap.pop(), Some(1));
379 /// assert_eq!(heap.pop(), None);
380 /// ```
381 pub fn pop(&mut self) -> Option<T> {
382 if self.is_empty() {
383 None
384 } else {
385 Some(unsafe { self.pop_unchecked() })
386 }
387 }
388
389 /// Removes the *top* (greatest if max-heap, smallest if min-heap) item from the binary heap and
390 /// returns it, without checking if the binary heap is empty.
391 ///
392 /// # Safety
393 ///
394 /// The binary heap must not be empty.
395 ///
396 /// # Example
397 ///
398 /// ```
399 /// use heapless::binary_heap::{BinaryHeap, Max};
400 ///
401 /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
402 /// heap.push(42)?;
403 ///
404 /// // SAFETY: We just pushed a number onto the heap, so it cannot be empty.
405 /// let val = unsafe { heap.pop_unchecked() };
406 /// assert_eq!(val, 42);
407 /// # Ok::<(), u8>(())
408 /// ```
409 pub unsafe fn pop_unchecked(&mut self) -> T {
410 let mut item = self.data.pop_unchecked();
411
412 if !self.is_empty() {
413 mem::swap(&mut item, self.data.as_mut_slice().get_unchecked_mut(0));
414 self.sift_down_to_bottom(0);
415 }
416 item
417 }
418
419 /// Pushes an item onto the binary heap.
420 ///
421 /// ```
422 /// use heapless::binary_heap::{BinaryHeap, Max};
423 ///
424 /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
425 /// heap.push(3).unwrap();
426 /// heap.push(5).unwrap();
427 /// heap.push(1).unwrap();
428 ///
429 /// assert_eq!(heap.len(), 3);
430 /// assert_eq!(heap.peek(), Some(&5));
431 /// ```
432 pub fn push(&mut self, item: T) -> Result<(), T> {
433 if self.data.is_full() {
434 return Err(item);
435 }
436
437 unsafe { self.push_unchecked(item) }
438 Ok(())
439 }
440
441 /// Pushes an item onto the binary heap without first checking if it's full.
442 ///
443 /// # Safety
444 ///
445 /// The binary heap must not be full.
446 ///
447 /// # Example
448 ///
449 /// ```
450 /// use heapless::binary_heap::{BinaryHeap, Max};
451 ///
452 /// let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
453 ///
454 /// // SAFETY: We just created an empty heap of size 8, so it cannot be full.
455 /// unsafe { heap.push_unchecked(42) };
456 /// assert_eq!(heap.len(), 1);
457 /// assert_eq!(heap.peek(), Some(&42));
458 /// ```
459 pub unsafe fn push_unchecked(&mut self, item: T) {
460 let old_len = self.len();
461 self.data.push_unchecked(item);
462 self.sift_up(0, old_len);
463 }
464
465 /* Private API */
466 fn sift_down_to_bottom(&mut self, mut pos: usize) {
467 let end = self.len();
468 let start = pos;
469 unsafe {
470 let mut hole = Hole::new(self.data.as_mut_slice(), pos);
471 let mut child = 2 * pos + 1;
472 while child < end {
473 let right = child + 1;
474 // compare with the greater of the two children
475 if right < end && hole.get(child).cmp(hole.get(right)) != K::ordering() {
476 child = right;
477 }
478 hole.move_to(child);
479 child = 2 * hole.pos() + 1;
480 }
481 pos = hole.pos;
482 }
483 self.sift_up(start, pos);
484 }
485
486 fn sift_up(&mut self, start: usize, pos: usize) -> usize {
487 unsafe {
488 // Take out the value at `pos` and create a hole.
489 let mut hole = Hole::new(self.data.as_mut_slice(), pos);
490
491 while hole.pos() > start {
492 let parent = (hole.pos() - 1) / 2;
493 if hole.element().cmp(hole.get(parent)) != K::ordering() {
494 break;
495 }
496 hole.move_to(parent);
497 }
498 hole.pos()
499 }
500 }
501}
502
503/// Hole represents a hole in a slice i.e. an index without valid value
504/// (because it was moved from or duplicated).
505/// In drop, `Hole` will restore the slice by filling the hole
506/// position with the value that was originally removed.
507struct Hole<'a, T> {
508 data: &'a mut [T],
509 /// `elt` is always `Some` from new until drop.
510 elt: ManuallyDrop<T>,
511 pos: usize,
512}
513
514impl<'a, T> Hole<'a, T> {
515 /// Create a new Hole at index `pos`.
516 ///
517 /// Unsafe because pos must be within the data slice.
518 #[inline]
519 unsafe fn new(data: &'a mut [T], pos: usize) -> Self {
520 debug_assert!(pos < data.len());
521 let elt = ptr::read(data.get_unchecked(pos));
522 Hole {
523 data,
524 elt: ManuallyDrop::new(elt),
525 pos,
526 }
527 }
528
529 #[inline]
530 fn pos(&self) -> usize {
531 self.pos
532 }
533
534 /// Returns a reference to the element removed.
535 #[inline]
536 fn element(&self) -> &T {
537 &self.elt
538 }
539
540 /// Returns a reference to the element at `index`.
541 ///
542 /// Unsafe because index must be within the data slice and not equal to pos.
543 #[inline]
544 unsafe fn get(&self, index: usize) -> &T {
545 debug_assert!(index != self.pos);
546 debug_assert!(index < self.data.len());
547 self.data.get_unchecked(index)
548 }
549
550 /// Move hole to new location
551 ///
552 /// Unsafe because index must be within the data slice and not equal to pos.
553 #[inline]
554 unsafe fn move_to(&mut self, index: usize) {
555 debug_assert!(index != self.pos);
556 debug_assert!(index < self.data.len());
557 let ptr = self.data.as_mut_ptr();
558 let index_ptr: *const _ = ptr.add(index);
559 let hole_ptr = ptr.add(self.pos);
560 ptr::copy_nonoverlapping(index_ptr, hole_ptr, 1);
561 self.pos = index;
562 }
563}
564
565/// Structure wrapping a mutable reference to the greatest item on a
566/// `BinaryHeap`.
567///
568/// This `struct` is created by [`BinaryHeapInner::peek_mut`].
569/// See its documentation for more.
570pub struct PeekMutInner<'a, T, K, S>
571where
572 T: Ord,
573 K: Kind,
574 S: VecStorage<T> + ?Sized,
575{
576 heap: &'a mut BinaryHeapInner<T, K, S>,
577 sift: bool,
578}
579
580/// Structure wrapping a mutable reference to the greatest item on a
581/// `BinaryHeap`.
582///
583/// This `struct` is created by [`BinaryHeap::peek_mut`].
584/// See its documentation for more.
585pub type PeekMut<'a, T, K, const N: usize> = PeekMutInner<'a, T, K, OwnedVecStorage<T, N>>;
586
587/// Structure wrapping a mutable reference to the greatest item on a
588/// `BinaryHeap`.
589///
590/// This `struct` is created by [`BinaryHeapView::peek_mut`].
591/// See its documentation for more.
592pub type PeekMutView<'a, T, K> = PeekMutInner<'a, T, K, ViewVecStorage<T>>;
593
594impl<T, K, S> Drop for PeekMutInner<'_, T, K, S>
595where
596 T: Ord,
597 K: Kind,
598 S: VecStorage<T> + ?Sized,
599{
600 fn drop(&mut self) {
601 if self.sift {
602 self.heap.sift_down_to_bottom(0);
603 }
604 }
605}
606
607impl<T, K, S> Deref for PeekMutInner<'_, T, K, S>
608where
609 T: Ord,
610 K: Kind,
611 S: VecStorage<T> + ?Sized,
612{
613 type Target = T;
614 fn deref(&self) -> &T {
615 debug_assert!(!self.heap.is_empty());
616 // SAFE: PeekMut is only instantiated for non-empty heaps
617 unsafe { self.heap.data.as_slice().get_unchecked(0) }
618 }
619}
620
621impl<T, K, S> DerefMut for PeekMutInner<'_, T, K, S>
622where
623 T: Ord,
624 K: Kind,
625 S: VecStorage<T> + ?Sized,
626{
627 fn deref_mut(&mut self) -> &mut T {
628 debug_assert!(!self.heap.is_empty());
629 // SAFE: PeekMut is only instantiated for non-empty heaps
630 unsafe { self.heap.data.as_mut_slice().get_unchecked_mut(0) }
631 }
632}
633
634impl<T, K, S> PeekMutInner<'_, T, K, S>
635where
636 T: Ord,
637 K: Kind,
638 S: VecStorage<T> + ?Sized,
639{
640 /// Removes the peeked value from the heap and returns it.
641 pub fn pop(mut this: Self) -> T {
642 let value = this.heap.pop().unwrap();
643 this.sift = false;
644 value
645 }
646}
647
648impl<T> Drop for Hole<'_, T> {
649 #[inline]
650 fn drop(&mut self) {
651 // fill the hole again
652 unsafe {
653 let pos = self.pos;
654 ptr::write(self.data.get_unchecked_mut(pos), ptr::read(&*self.elt));
655 }
656 }
657}
658
659impl<T, K, const N: usize> Default for BinaryHeap<T, K, N>
660where
661 T: Ord,
662 K: Kind,
663{
664 fn default() -> Self {
665 Self::new()
666 }
667}
668
669impl<T, K, const N: usize> Clone for BinaryHeap<T, K, N>
670where
671 K: Kind,
672 T: Ord + Clone,
673{
674 fn clone(&self) -> Self {
675 Self {
676 _kind: self._kind,
677 data: self.data.clone(),
678 }
679 }
680}
681
682impl<T, K, S> fmt::Debug for BinaryHeapInner<T, K, S>
683where
684 K: Kind,
685 T: Ord + fmt::Debug,
686 S: VecStorage<T> + ?Sized,
687{
688 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
689 f.debug_list().entries(self.iter()).finish()
690 }
691}
692
693impl<'a, T, K, S> IntoIterator for &'a BinaryHeapInner<T, K, S>
694where
695 K: Kind,
696 T: Ord,
697 S: VecStorage<T> + ?Sized,
698{
699 type Item = &'a T;
700 type IntoIter = slice::Iter<'a, T>;
701
702 fn into_iter(self) -> Self::IntoIter {
703 self.iter()
704 }
705}
706
707#[cfg(test)]
708mod tests {
709 use static_assertions::assert_not_impl_any;
710
711 use super::{BinaryHeap, BinaryHeapView, Max, Min};
712
713 // Ensure a `BinaryHeap` containing `!Send` values stays `!Send` itself.
714 assert_not_impl_any!(BinaryHeap<*const (), Max, 4>: Send);
715 assert_not_impl_any!(BinaryHeap<*const (), Min, 4>: Send);
716
717 #[test]
718 fn static_new() {
719 static mut _B: BinaryHeap<i32, Min, 16> = BinaryHeap::new();
720 }
721
722 #[test]
723 fn drop() {
724 droppable!();
725
726 {
727 let mut v: BinaryHeap<Droppable, Max, 2> = BinaryHeap::new();
728 v.push(Droppable::new()).ok().unwrap();
729 v.push(Droppable::new()).ok().unwrap();
730 v.pop().unwrap();
731 }
732
733 assert_eq!(Droppable::count(), 0);
734
735 {
736 let mut v: BinaryHeap<Droppable, Max, 2> = BinaryHeap::new();
737 v.push(Droppable::new()).ok().unwrap();
738 v.push(Droppable::new()).ok().unwrap();
739 }
740
741 assert_eq!(Droppable::count(), 0);
742
743 {
744 let mut v: BinaryHeap<Droppable, Min, 2> = BinaryHeap::new();
745 v.push(Droppable::new()).ok().unwrap();
746 v.push(Droppable::new()).ok().unwrap();
747 v.pop().unwrap();
748 }
749
750 assert_eq!(Droppable::count(), 0);
751
752 {
753 let mut v: BinaryHeap<Droppable, Min, 2> = BinaryHeap::new();
754 v.push(Droppable::new()).ok().unwrap();
755 v.push(Droppable::new()).ok().unwrap();
756 }
757
758 assert_eq!(Droppable::count(), 0);
759 }
760
761 #[test]
762 fn into_vec() {
763 droppable!();
764
765 let mut h: BinaryHeap<Droppable, Max, 2> = BinaryHeap::new();
766 h.push(Droppable::new()).ok().unwrap();
767 h.push(Droppable::new()).ok().unwrap();
768 h.pop().unwrap();
769
770 assert_eq!(Droppable::count(), 1);
771
772 let v = h.into_vec();
773
774 assert_eq!(Droppable::count(), 1);
775
776 core::mem::drop(v);
777
778 assert_eq!(Droppable::count(), 0);
779 }
780
781 #[test]
782 fn min() {
783 let mut heap = BinaryHeap::<_, Min, 16>::new();
784 heap.push(1).unwrap();
785 heap.push(2).unwrap();
786 heap.push(3).unwrap();
787 heap.push(17).unwrap();
788 heap.push(19).unwrap();
789 heap.push(36).unwrap();
790 heap.push(7).unwrap();
791 heap.push(25).unwrap();
792 heap.push(100).unwrap();
793
794 assert_eq!(
795 heap.iter().cloned().collect::<Vec<_>>(),
796 [1, 2, 3, 17, 19, 36, 7, 25, 100]
797 );
798
799 assert_eq!(heap.pop(), Some(1));
800
801 assert_eq!(
802 heap.iter().cloned().collect::<Vec<_>>(),
803 [2, 17, 3, 25, 19, 36, 7, 100]
804 );
805
806 assert_eq!(heap.pop(), Some(2));
807 assert_eq!(heap.pop(), Some(3));
808 assert_eq!(heap.pop(), Some(7));
809 assert_eq!(heap.pop(), Some(17));
810 assert_eq!(heap.pop(), Some(19));
811 assert_eq!(heap.pop(), Some(25));
812 assert_eq!(heap.pop(), Some(36));
813 assert_eq!(heap.pop(), Some(100));
814 assert_eq!(heap.pop(), None);
815
816 assert!(heap.peek_mut().is_none());
817
818 heap.push(1).unwrap();
819 heap.push(2).unwrap();
820 heap.push(10).unwrap();
821
822 {
823 let mut val = heap.peek_mut().unwrap();
824 *val = 7;
825 }
826
827 assert_eq!(heap.pop(), Some(2));
828 assert_eq!(heap.pop(), Some(7));
829 assert_eq!(heap.pop(), Some(10));
830 assert_eq!(heap.pop(), None);
831 }
832
833 #[test]
834 fn max() {
835 let mut heap = BinaryHeap::<_, Max, 16>::new();
836 heap.push(1).unwrap();
837 heap.push(2).unwrap();
838 heap.push(3).unwrap();
839 heap.push(17).unwrap();
840 heap.push(19).unwrap();
841 heap.push(36).unwrap();
842 heap.push(7).unwrap();
843 heap.push(25).unwrap();
844 heap.push(100).unwrap();
845
846 assert_eq!(
847 heap.iter().cloned().collect::<Vec<_>>(),
848 [100, 36, 19, 25, 3, 2, 7, 1, 17]
849 );
850
851 assert_eq!(heap.pop(), Some(100));
852
853 assert_eq!(
854 heap.iter().cloned().collect::<Vec<_>>(),
855 [36, 25, 19, 17, 3, 2, 7, 1]
856 );
857
858 assert_eq!(heap.pop(), Some(36));
859 assert_eq!(heap.pop(), Some(25));
860 assert_eq!(heap.pop(), Some(19));
861 assert_eq!(heap.pop(), Some(17));
862 assert_eq!(heap.pop(), Some(7));
863 assert_eq!(heap.pop(), Some(3));
864 assert_eq!(heap.pop(), Some(2));
865 assert_eq!(heap.pop(), Some(1));
866 assert_eq!(heap.pop(), None);
867
868 assert!(heap.peek_mut().is_none());
869
870 heap.push(1).unwrap();
871 heap.push(9).unwrap();
872 heap.push(10).unwrap();
873
874 {
875 let mut val = heap.peek_mut().unwrap();
876 *val = 7;
877 }
878
879 assert_eq!(heap.pop(), Some(9));
880 assert_eq!(heap.pop(), Some(7));
881 assert_eq!(heap.pop(), Some(1));
882 assert_eq!(heap.pop(), None);
883 }
884
885 fn _test_variance<'a: 'b, 'b>(x: BinaryHeap<&'a (), Max, 42>) -> BinaryHeap<&'b (), Max, 42> {
886 x
887 }
888 fn _test_variance_view<'a: 'b, 'b, 'c>(
889 x: &'c BinaryHeapView<&'a (), Max>,
890 ) -> &'c BinaryHeapView<&'b (), Max> {
891 x
892 }
893}