#![no_std]
#![cfg_attr(
feature = "unstable_nightly",
feature(
exact_size_is_empty,
extend_one,
inplace_iteration,
min_specialization,
trusted_len
)
)]
#![cfg_attr(docsrs, feature(doc_cfg))]
#![allow(clippy::needless_doctest_main)]
extern crate alloc;
use core::fmt;
use core::iter::{FromIterator, FusedIterator};
use core::mem::{size_of, swap, ManuallyDrop};
use core::ops::{Deref, DerefMut};
use core::ptr;
use core::slice;
#[cfg(feature = "extra")]
use alloc::collections::TryReserveError;
use alloc::{vec, vec::Vec};
pub type BinaryHeap<T> = DaryHeap<T, 2>;
pub type TernaryHeap<T> = DaryHeap<T, 3>;
pub type QuaternaryHeap<T> = DaryHeap<T, 4>;
pub type QuinaryHeap<T> = DaryHeap<T, 5>;
pub type SenaryHeap<T> = DaryHeap<T, 6>;
pub type SeptenaryHeap<T> = DaryHeap<T, 7>;
pub type OctonaryHeap<T> = DaryHeap<T, 8>;
pub struct DaryHeap<T, const D: usize> {
data: Vec<T>,
}
#[cfg(feature = "serde")]
mod serde_impl {
use super::{DaryHeap, Vec};
use serde::{Deserialize, Deserializer, Serialize, Serializer};
impl<T: Serialize, const D: usize> Serialize for DaryHeap<T, D> {
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: Serializer,
{
self.data.serialize(serializer)
}
}
impl<'de, T: Ord + Deserialize<'de>, const A: usize> Deserialize<'de> for DaryHeap<T, A> {
fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where
D: Deserializer<'de>,
{
Vec::deserialize(deserializer).map(Into::into)
}
fn deserialize_in_place<D>(deserializer: D, place: &mut Self) -> Result<(), D::Error>
where
D: Deserializer<'de>,
{
place.data.clear();
let result = Vec::deserialize_in_place(deserializer, &mut place.data);
place.rebuild();
result
}
}
}
pub struct PeekMut<'a, T: 'a + Ord, const D: usize> {
heap: &'a mut DaryHeap<T, D>,
sift: bool,
}
impl<T: Ord + fmt::Debug, const D: usize> fmt::Debug for PeekMut<'_, T, D> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_tuple("PeekMut").field(&self.heap.data[0]).finish()
}
}
impl<T: Ord, const D: usize> Drop for PeekMut<'_, T, D> {
fn drop(&mut self) {
if self.sift {
unsafe { self.heap.sift_down(0) };
}
}
}
impl<T: Ord, const D: usize> Deref for PeekMut<'_, T, D> {
type Target = T;
fn deref(&self) -> &T {
debug_assert!(!self.heap.is_empty());
unsafe { self.heap.data.get_unchecked(0) }
}
}
impl<T: Ord, const D: usize> DerefMut for PeekMut<'_, T, D> {
fn deref_mut(&mut self) -> &mut T {
debug_assert!(!self.heap.is_empty());
self.sift = true;
unsafe { self.heap.data.get_unchecked_mut(0) }
}
}
impl<'a, T: Ord, const D: usize> PeekMut<'a, T, D> {
pub fn pop(mut this: PeekMut<'a, T, D>) -> T {
let value = this.heap.pop().unwrap();
this.sift = false;
value
}
}
impl<T: Clone, const D: usize> Clone for DaryHeap<T, D> {
fn clone(&self) -> Self {
DaryHeap {
data: self.data.clone(),
}
}
fn clone_from(&mut self, source: &Self) {
self.data.clone_from(&source.data);
}
}
impl<T: Ord, const D: usize> Default for DaryHeap<T, D> {
#[inline]
fn default() -> DaryHeap<T, D> {
DaryHeap::new()
}
}
impl<T: fmt::Debug, const D: usize> fmt::Debug for DaryHeap<T, D> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_list().entries(self.iter()).finish()
}
}
impl<T: Ord, const D: usize> DaryHeap<T, D> {
#[must_use]
pub fn new() -> DaryHeap<T, D> {
DaryHeap { data: vec![] }
}
#[must_use]
pub fn with_capacity(capacity: usize) -> DaryHeap<T, D> {
DaryHeap {
data: Vec::with_capacity(capacity),
}
}
pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T, D>> {
if self.is_empty() {
None
} else {
Some(PeekMut {
heap: self,
sift: false,
})
}
}
pub fn pop(&mut self) -> Option<T> {
self.data.pop().map(|mut item| {
if !self.is_empty() {
swap(&mut item, &mut self.data[0]);
unsafe { self.sift_down_to_bottom(0) };
}
item
})
}
pub fn push(&mut self, item: T) {
let old_len = self.len();
self.data.push(item);
unsafe { self.sift_up(0, old_len) };
}
#[must_use = "`self` will be dropped if the result is not used"]
pub fn into_sorted_vec(mut self) -> Vec<T> {
let mut end = self.len();
while end > 1 {
end -= 1;
unsafe {
let ptr = self.data.as_mut_ptr();
ptr::swap(ptr, ptr.add(end));
}
unsafe { self.sift_down_range(0, end) };
}
self.into_vec()
}
unsafe fn sift_up(&mut self, start: usize, pos: usize) -> usize {
assert_ne!(D, 0, "Arity should be greater than zero");
let mut hole = Hole::new(&mut self.data, pos);
while hole.pos() > start {
let parent = (hole.pos() - 1) / D;
if hole.element() <= hole.get(parent) {
break;
}
hole.move_to(parent);
}
hole.pos()
}
unsafe fn sift_down_range(&mut self, pos: usize, end: usize) {
assert_ne!(D, 0, "Arity should be greater than zero");
let mut hole = Hole::new(&mut self.data, pos);
let mut child = D * hole.pos() + 1;
while child <= end.saturating_sub(D) {
child = hole.max_sibling::<D>(child);
if hole.element() >= hole.get(child) {
return;
}
hole.move_to(child);
child = D * hole.pos() + 1;
}
child = hole.max_sibling_to::<D>(child, end);
if child < end && hole.element() < hole.get(child) {
hole.move_to(child);
}
}
unsafe fn sift_down(&mut self, pos: usize) {
let len = self.len();
self.sift_down_range(pos, len);
}
unsafe fn sift_down_to_bottom(&mut self, mut pos: usize) {
assert_ne!(D, 0, "Arity should be greater than zero");
let end = self.len();
let start = pos;
let mut hole = Hole::new(&mut self.data, pos);
let mut child = D * hole.pos() + 1;
while child <= end.saturating_sub(D) {
child = hole.max_sibling::<D>(child);
hole.move_to(child);
child = D * hole.pos() + 1;
}
child = hole.max_sibling_to::<D>(child, end);
if child < end {
hole.move_to(child);
}
pos = hole.pos();
drop(hole);
self.sift_up(start, pos);
}
fn rebuild_tail(&mut self, start: usize) {
assert_ne!(D, 0, "Arity should be greater than zero");
if start == self.len() {
return;
}
let tail_len = self.len() - start;
#[allow(clippy::manual_bits)]
#[inline(always)]
fn log2_fast(x: usize) -> usize {
8 * size_of::<usize>() - (x.leading_zeros() as usize) - 1
}
let better_to_rebuild = if start < tail_len {
true
} else if self.len() <= 4096 / D {
D * self.len() < (D - 1) * tail_len * log2_fast(start)
} else {
D * self.len() < (D - 1) * tail_len * 13usize.saturating_sub(D)
};
if better_to_rebuild {
self.rebuild();
} else {
for i in start..self.len() {
unsafe { self.sift_up(0, i) };
}
}
}
fn rebuild(&mut self) {
assert_ne!(D, 0, "Arity should be greater than zero");
if self.len() < 2 {
return;
}
let mut n = (self.len() - 1) / D + 1;
while n > 0 {
n -= 1;
unsafe { self.sift_down(n) };
}
}
pub fn append(&mut self, other: &mut Self) {
if self.len() < other.len() {
swap(self, other);
}
let start = self.data.len();
self.data.append(&mut other.data);
self.rebuild_tail(start);
}
#[inline]
#[cfg(feature = "unstable")]
#[cfg_attr(docsrs, doc(cfg(feature = "unstable")))]
pub fn drain_sorted(&mut self) -> DrainSorted<'_, T, D> {
DrainSorted { inner: self }
}
#[cfg(feature = "unstable")]
#[cfg_attr(docsrs, doc(cfg(feature = "unstable")))]
pub fn retain<F>(&mut self, mut f: F)
where
F: FnMut(&T) -> bool,
{
let mut first_removed = self.len();
let mut i = 0;
self.data.retain(|e| {
let keep = f(e);
if !keep && i < first_removed {
first_removed = i;
}
i += 1;
keep
});
self.rebuild_tail(first_removed);
}
}
impl<T, const D: usize> DaryHeap<T, D> {
pub fn iter(&self) -> Iter<'_, T> {
Iter {
iter: self.data.iter(),
}
}
#[cfg(feature = "unstable")]
#[cfg_attr(docsrs, doc(cfg(feature = "unstable")))]
pub fn into_iter_sorted(self) -> IntoIterSorted<T, D> {
IntoIterSorted { inner: self }
}
#[must_use]
pub fn peek(&self) -> Option<&T> {
self.data.get(0)
}
#[must_use]
pub fn capacity(&self) -> usize {
self.data.capacity()
}
pub fn reserve_exact(&mut self, additional: usize) {
self.data.reserve_exact(additional);
}
pub fn reserve(&mut self, additional: usize) {
self.data.reserve(additional);
}
#[cfg(feature = "extra")]
#[cfg_attr(docsrs, doc(cfg(feature = "extra")))]
pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
self.data.try_reserve_exact(additional)
}
#[cfg(feature = "extra")]
#[cfg_attr(docsrs, doc(cfg(feature = "extra")))]
pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
self.data.try_reserve(additional)
}
pub fn shrink_to_fit(&mut self) {
self.data.shrink_to_fit();
}
#[inline]
#[cfg(feature = "extra")]
#[cfg_attr(docsrs, doc(cfg(feature = "extra")))]
pub fn shrink_to(&mut self, min_capacity: usize) {
self.data.shrink_to(min_capacity)
}
#[cfg(feature = "unstable")]
#[cfg_attr(docsrs, doc(cfg(feature = "unstable")))]
#[must_use]
pub fn as_slice(&self) -> &[T] {
self.data.as_slice()
}
#[must_use = "`self` will be dropped if the result is not used"]
pub fn into_vec(self) -> Vec<T> {
self.into()
}
#[must_use]
pub fn len(&self) -> usize {
self.data.len()
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
#[inline]
pub fn drain(&mut self) -> Drain<'_, T> {
Drain {
iter: self.data.drain(..),
}
}
pub fn clear(&mut self) {
self.drain();
}
}
struct Hole<'a, T: 'a> {
data: &'a mut [T],
elt: ManuallyDrop<T>,
pos: usize,
}
impl<'a, T> Hole<'a, T> {
#[inline]
unsafe fn new(data: &'a mut [T], pos: usize) -> Self {
debug_assert!(pos < data.len());
let elt = ptr::read(data.get_unchecked(pos));
Hole {
data,
elt: ManuallyDrop::new(elt),
pos,
}
}
#[inline]
fn pos(&self) -> usize {
self.pos
}
#[inline]
fn element(&self) -> &T {
&self.elt
}
#[inline]
unsafe fn get(&self, index: usize) -> &T {
debug_assert!(index != self.pos);
debug_assert!(index < self.data.len());
self.data.get_unchecked(index)
}
#[inline]
unsafe fn move_to(&mut self, index: usize) {
debug_assert!(index != self.pos);
debug_assert!(index < self.data.len());
let ptr = self.data.as_mut_ptr();
let index_ptr: *const _ = ptr.add(index);
let hole_ptr = ptr.add(self.pos);
ptr::copy_nonoverlapping(index_ptr, hole_ptr, 1);
self.pos = index;
}
}
impl<'a, T: Ord> Hole<'a, T> {
#[inline]
unsafe fn max(&self, elem1: usize, elem2: usize) -> usize {
if self.get(elem1) <= self.get(elem2) {
elem2
} else {
elem1
}
}
#[inline]
unsafe fn max_sibling<const D: usize>(&self, first_sibling: usize) -> usize {
let mut sibling = first_sibling;
match D {
2 => {
sibling += (self.get(sibling) <= self.get(sibling + 1)) as usize;
}
3 => {
let sibling_a = self.max_sibling::<2>(sibling);
let sibling_b = sibling + 2;
sibling = self.max(sibling_a, sibling_b);
}
4 => {
let sibling_a = self.max_sibling::<2>(sibling);
let sibling_b = self.max_sibling::<2>(sibling + 2);
sibling = self.max(sibling_a, sibling_b);
}
_ => {
for other_sibling in sibling + 1..sibling + D {
if self.get(sibling) <= self.get(other_sibling) {
sibling = other_sibling;
}
}
}
}
sibling
}
#[inline]
unsafe fn max_sibling_to<const D: usize>(&self, first_sibling: usize, end: usize) -> usize {
let mut sibling = first_sibling;
match D {
2 => {}
3 => {
if sibling + 1 < end {
sibling = self.max_sibling::<2>(sibling);
}
}
_ => {
for other_sibling in sibling + 1..end {
if self.get(sibling) <= self.get(other_sibling) {
sibling = other_sibling;
}
}
}
}
sibling
}
}
impl<T> Drop for Hole<'_, T> {
#[inline]
fn drop(&mut self) {
unsafe {
let pos = self.pos;
ptr::copy_nonoverlapping(&*self.elt, self.data.get_unchecked_mut(pos), 1);
}
}
}
#[must_use = "iterators are lazy and do nothing unless consumed"]
pub struct Iter<'a, T: 'a> {
iter: slice::Iter<'a, T>,
}
impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_tuple("Iter").field(&self.iter.as_slice()).finish()
}
}
impl<T> Clone for Iter<'_, T> {
fn clone(&self) -> Self {
Iter {
iter: self.iter.clone(),
}
}
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
#[inline]
fn next(&mut self) -> Option<&'a T> {
self.iter.next()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
#[inline]
fn last(self) -> Option<&'a T> {
self.iter.last()
}
}
impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
#[inline]
fn next_back(&mut self) -> Option<&'a T> {
self.iter.next_back()
}
}
impl<T> ExactSizeIterator for Iter<'_, T> {
#[cfg(feature = "unstable_nightly")]
fn is_empty(&self) -> bool {
self.iter.is_empty()
}
}
impl<T> FusedIterator for Iter<'_, T> {}
#[derive(Clone)]
pub struct IntoIter<T> {
iter: vec::IntoIter<T>,
}
impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_tuple("IntoIter")
.field(&self.iter.as_slice())
.finish()
}
}
impl<T> Iterator for IntoIter<T> {
type Item = T;
#[inline]
fn next(&mut self) -> Option<T> {
self.iter.next()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl<T> DoubleEndedIterator for IntoIter<T> {
#[inline]
fn next_back(&mut self) -> Option<T> {
self.iter.next_back()
}
}
impl<T> ExactSizeIterator for IntoIter<T> {
#[cfg(feature = "unstable_nightly")]
fn is_empty(&self) -> bool {
self.iter.is_empty()
}
}
impl<T> FusedIterator for IntoIter<T> {}
#[cfg(feature = "unstable_nightly")]
#[doc(hidden)]
unsafe impl<T> core::iter::SourceIter for IntoIter<T> {
type Source = IntoIter<T>;
#[inline]
unsafe fn as_inner(&mut self) -> &mut Self::Source {
self
}
}
#[cfg(feature = "unstable_nightly")]
#[doc(hidden)]
unsafe impl<I> core::iter::InPlaceIterable for IntoIter<I> {}
#[must_use = "iterators are lazy and do nothing unless consumed"]
#[cfg(feature = "unstable")]
#[derive(Clone, Debug)]
pub struct IntoIterSorted<T, const D: usize> {
inner: DaryHeap<T, D>,
}
#[cfg(feature = "unstable")]
impl<T: Ord, const D: usize> Iterator for IntoIterSorted<T, D> {
type Item = T;
#[inline]
fn next(&mut self) -> Option<T> {
self.inner.pop()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let exact = self.inner.len();
(exact, Some(exact))
}
}
#[cfg(feature = "unstable")]
impl<T: Ord, const D: usize> ExactSizeIterator for IntoIterSorted<T, D> {}
#[cfg(feature = "unstable")]
impl<T: Ord, const D: usize> FusedIterator for IntoIterSorted<T, D> {}
#[cfg(all(feature = "unstable", feature = "unstable_nightly"))]
unsafe impl<T: Ord, const D: usize> core::iter::TrustedLen for IntoIterSorted<T, D> {}
#[derive(Debug)]
pub struct Drain<'a, T: 'a> {
iter: vec::Drain<'a, T>,
}
impl<T> Iterator for Drain<'_, T> {
type Item = T;
#[inline]
fn next(&mut self) -> Option<T> {
self.iter.next()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
impl<T> DoubleEndedIterator for Drain<'_, T> {
#[inline]
fn next_back(&mut self) -> Option<T> {
self.iter.next_back()
}
}
impl<T> ExactSizeIterator for Drain<'_, T> {
#[cfg(feature = "unstable_nightly")]
fn is_empty(&self) -> bool {
self.iter.is_empty()
}
}
impl<T> FusedIterator for Drain<'_, T> {}
#[cfg(feature = "unstable")]
#[derive(Debug)]
pub struct DrainSorted<'a, T: Ord, const D: usize> {
inner: &'a mut DaryHeap<T, D>,
}
#[cfg(feature = "unstable")]
impl<'a, T: Ord, const D: usize> Drop for DrainSorted<'a, T, D> {
fn drop(&mut self) {
use core::mem::forget;
struct DropGuard<'r, 'a, T: Ord, const D: usize>(&'r mut DrainSorted<'a, T, D>);
impl<'r, 'a, T: Ord, const D: usize> Drop for DropGuard<'r, 'a, T, D> {
fn drop(&mut self) {
while self.0.inner.pop().is_some() {}
}
}
while let Some(item) = self.inner.pop() {
let guard = DropGuard(self);
drop(item);
forget(guard);
}
}
}
#[cfg(feature = "unstable")]
impl<T: Ord, const D: usize> Iterator for DrainSorted<'_, T, D> {
type Item = T;
#[inline]
fn next(&mut self) -> Option<T> {
self.inner.pop()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
let exact = self.inner.len();
(exact, Some(exact))
}
}
#[cfg(feature = "unstable")]
impl<T: Ord, const D: usize> ExactSizeIterator for DrainSorted<'_, T, D> {}
#[cfg(feature = "unstable")]
impl<T: Ord, const D: usize> FusedIterator for DrainSorted<'_, T, D> {}
#[cfg(all(feature = "unstable", feature = "unstable_nightly"))]
unsafe impl<T: Ord, const D: usize> core::iter::TrustedLen for DrainSorted<'_, T, D> {}
impl<T: Ord, const D: usize> From<Vec<T>> for DaryHeap<T, D> {
fn from(vec: Vec<T>) -> DaryHeap<T, D> {
let mut heap = DaryHeap { data: vec };
heap.rebuild();
heap
}
}
impl<T: Ord, const D: usize, const N: usize> From<[T; N]> for DaryHeap<T, D> {
fn from(arr: [T; N]) -> Self {
#[allow(deprecated)]
core::array::IntoIter::new(arr).collect()
}
}
impl<T, const D: usize> From<DaryHeap<T, D>> for Vec<T> {
fn from(heap: DaryHeap<T, D>) -> Vec<T> {
heap.data
}
}
impl<T: Ord, const D: usize> FromIterator<T> for DaryHeap<T, D> {
fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> DaryHeap<T, D> {
DaryHeap::from(iter.into_iter().collect::<Vec<_>>())
}
}
impl<T, const D: usize> IntoIterator for DaryHeap<T, D> {
type Item = T;
type IntoIter = IntoIter<T>;
fn into_iter(self) -> IntoIter<T> {
IntoIter {
iter: self.data.into_iter(),
}
}
}
impl<'a, T, const D: usize> IntoIterator for &'a DaryHeap<T, D> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Iter<'a, T> {
self.iter()
}
}
impl<T: Ord, const D: usize> Extend<T> for DaryHeap<T, D> {
#[inline]
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
self.extend_desugared(iter.into_iter());
}
#[inline]
#[cfg(feature = "unstable_nightly")]
fn extend_one(&mut self, item: T) {
self.push(item);
}
#[inline]
#[cfg(feature = "unstable_nightly")]
fn extend_reserve(&mut self, additional: usize) {
self.reserve(additional);
}
}
impl<T: Ord, const D: usize> DaryHeap<T, D> {
fn extend_desugared<I: IntoIterator<Item = T>>(&mut self, iter: I) {
let iterator = iter.into_iter();
let (lower, _) = iterator.size_hint();
self.reserve(lower);
iterator.for_each(move |elem| self.push(elem));
}
}
impl<'a, T: 'a + Ord + Copy, const D: usize> Extend<&'a T> for DaryHeap<T, D> {
fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
self.extend(iter.into_iter().cloned());
}
#[inline]
#[cfg(feature = "unstable_nightly")]
fn extend_one(&mut self, &item: &'a T) {
self.push(item);
}
#[inline]
#[cfg(feature = "unstable_nightly")]
fn extend_reserve(&mut self, additional: usize) {
self.reserve(additional);
}
}
#[cfg(any(test, fuzzing))]
impl<T: Ord + fmt::Debug, const D: usize> DaryHeap<T, D> {
#[track_caller]
pub fn assert_valid_state(&self) {
assert_ne!(D, 0, "Arity should be greater than zero");
for (i, v) in self.iter().enumerate() {
let children = D * i + 1..D * i + D;
if children.start > self.len() {
break;
}
for j in children {
if let Some(x) = self.data.get(j) {
assert!(v >= x);
}
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use rand::{seq::SliceRandom, thread_rng};
fn pop<const D: usize>() {
let mut rng = thread_rng();
let ntest = if cfg!(miri) { 1 } else { 10 };
let nelem = if cfg!(miri) { 100 } else { 1000 };
for _ in 0..ntest {
let mut data: Vec<_> = (0..nelem).collect();
data.shuffle(&mut rng);
let mut heap = DaryHeap::<_, D>::from(data);
heap.assert_valid_state();
for i in (0..nelem).rev() {
assert_eq!(heap.pop(), Some(i));
heap.assert_valid_state();
}
assert_eq!(heap.pop(), None);
}
}
#[test]
#[should_panic]
fn push_d0() {
let mut heap = DaryHeap::<_, 0>::new();
heap.push(42);
}
#[test]
#[should_panic]
fn from_vec_d0() {
let _heap = DaryHeap::<_, 0>::from(vec![42]);
}
#[test]
fn pop_d1() {
pop::<1>();
}
#[test]
fn pop_d2() {
pop::<2>();
}
#[test]
fn pop_d3() {
pop::<3>();
}
#[test]
fn pop_d4() {
pop::<4>();
}
#[test]
fn pop_d5() {
pop::<5>();
}
#[test]
fn pop_d6() {
pop::<6>();
}
#[test]
fn pop_d7() {
pop::<7>();
}
#[test]
fn pop_d8() {
pop::<8>();
}
#[test]
#[cfg(feature = "serde")]
fn serde() {
use serde_test::Token::{Seq, SeqEnd, I32};
impl<T: PartialEq, const D: usize> PartialEq for DaryHeap<T, D> {
fn eq(&self, other: &Self) -> bool {
self.iter().zip(other).all(|(a, b)| a == b)
}
}
let empty = [Seq { len: Some(0) }, SeqEnd];
let part = [Seq { len: Some(3) }, I32(3), I32(1), I32(2), SeqEnd];
let full = [Seq { len: Some(4) }, I32(4), I32(3), I32(2), I32(1), SeqEnd];
let mut dary = BinaryHeap::<i32>::new();
serde_test::assert_tokens(&dary, &empty);
dary.extend(&[1, 2, 3]);
serde_test::assert_tokens(&dary, &part);
dary.push(4);
serde_test::assert_tokens(&dary, &full);
let mut std = alloc::collections::BinaryHeap::<i32>::new();
serde_test::assert_ser_tokens(&std, &empty);
std.extend(&[1, 2, 3]);
serde_test::assert_ser_tokens(&std, &part);
std.push(4);
serde_test::assert_ser_tokens(&std, &full);
}
}