// codesnip-guard: RadixHeap
#[cfg_attr(any(),rustfmt::skip)]pub use self::radix_heap::{RadixHeapU32,RadixHeapU64};#[cfg_attr(any(),rustfmt::skip)]mod radix_heap{macro_rules!define_radix_heap{($name:ident,$key:ty,$buckets:expr)=>{#[doc=" A min-priority queue whose removed keys are monotonically nondecreasing."]#[doc=""]#[doc=" Values with equal keys have no specified removal order."]#[derive(Clone,Debug)]pub struct$name<T>{buckets:[Vec<($key,T)>;$buckets],last:$key,len:usize,}impl<T>$name<T>{pub fn new()->Self{Self{buckets:std::array::from_fn(|_|Vec::new()),last:0,len:0,}}pub fn len(&self)->usize{self.len}pub fn is_empty(&self)->bool{self.len==0}#[doc=" Inserts a value whose key is not less than the key most recently removed."]#[doc=""]#[doc=" # Panics"]#[doc=""]#[doc=" Panics if `key` is less than the key most recently removed."]pub fn push(&mut self,key:$key,value:T){assert!(key>=self.last,"key is less than the last removed key");self.buckets[Self::bucket_index(key,self.last)].push((key,value));self.len+=1;}pub fn pop(&mut self)->Option<($key,T)>{if self.len==0{return None;}if self.buckets[0].is_empty(){let index=(1..self.buckets.len()).find(|&index|!self.buckets[index].is_empty()).unwrap();self.last=self.buckets[index].iter().map(|&(key,_)|key).min().unwrap();let mut values=std::mem::take(&mut self.buckets[index]);while let Some((key,value))=values.pop(){let next=Self::bucket_index(key,self.last);debug_assert!(next<index);self.buckets[next].push((key,value));}self.buckets[index]=values;}self.len-=1;self.buckets[0].pop()}pub fn clear(&mut self){for bucket in&mut self.buckets{bucket.clear();}self.last=0;self.len=0;}#[inline]fn bucket_index(key:$key,last:$key)->usize{(<$key>::BITS-(key^last).leading_zeros())as usize}}impl<T>Default for$name<T>{fn default()->Self{Self::new()}}};}define_radix_heap!(RadixHeapU32,u32,33);define_radix_heap!(RadixHeapU64,u64,65);}