// codesnip-guard: QuotientIndex
#[cfg_attr(any(),rustfmt::skip)]pub use self::quotient_index::{CeilQuotientIndex,FloorQuotientIndex};#[cfg_attr(any(),rustfmt::skip)]mod quotient_index{use std::{iter::{ExactSizeIterator,FusedIterator},ops::RangeInclusive};#[doc=" sorted({ floor(n/k) | k in \\[1, n\\] })"]pub struct FloorQuotientIndex{num:usize,sqrt:usize,pivot:usize}impl FloorQuotientIndex{pub fn new(num:usize)->Self{assert!(num>0,"num must be positive");let sqrt=num.isqrt();let pivot=num/sqrt;Self{num,sqrt,pivot}}pub fn values(&self)->impl ExactSizeIterator<Item=usize>+FusedIterator+'_{let len=self.len();(0..len).map(move|index|unsafe{self.index_to_value_unchecked(index)})}pub fn key_values(&self)->impl ExactSizeIterator<Item=(RangeInclusive<usize>,usize)>+FusedIterator+'_{let len=self.len();(0..len).map(move|index|unsafe{(self.index_to_key_unchecked(index),self.index_to_value_unchecked(index))})}#[allow(clippy::len_without_is_empty)]pub fn len(&self)->usize{2*self.sqrt-(self.pivot==self.sqrt)as usize}pub fn contains_key(&self,key:usize)->bool{(1..=self.num).contains(&key)}pub fn contains_value(&self,value:usize)->bool{if value==0||value>self.num{return false;}if value==usize::MAX{return self.num==usize::MAX;}self.num/value>self.num/(value+1)}pub fn index_to_key(&self,index:usize)->RangeInclusive<usize>{assert!(index<self.len(),"index out of bounds");unsafe{self.index_to_key_unchecked(index)}}pub fn index_to_value(&self,index:usize)->usize{assert!(index<self.len(),"index out of bounds");unsafe{self.index_to_value_unchecked(index)}}pub fn value_to_index(&self,value:usize)->usize{assert!(self.contains_value(value),"value is not present");unsafe{self.value_to_index_unchecked(value)}}pub fn value_to_key(&self,value:usize)->RangeInclusive<usize>{assert!(self.contains_value(value),"value is not present");unsafe{self.value_to_key_unchecked(value)}}pub fn key_to_index(&self,key:usize)->usize{assert!(self.contains_key(key),"key out of bounds");let value=self.key_to_value(key);unsafe{self.value_to_index_unchecked(value)}}pub fn key_to_value(&self,key:usize)->usize{assert!(self.contains_key(key),"key out of bounds");unsafe{self.key_to_value_unchecked(key)}}#[doc=" # Safety"]#[doc=" `index` must satisfy `index < self.len()`."]pub unsafe fn index_to_key_unchecked(&self,index:usize)->RangeInclusive<usize>{if index<self.sqrt{self.num/(index+2)+1..=self.num/(index+1)}else{let key=self.len()-index;key..=key}}#[doc=" # Safety"]#[doc=" `index` must satisfy `index < self.len()`."]pub unsafe fn index_to_value_unchecked(&self,index:usize)->usize{if index<self.sqrt{index+1}else{self.num/(self.len()-index)}}#[doc=" # Safety"]#[doc=" `value` must satisfy `self.contains_value(value)`."]pub unsafe fn value_to_index_unchecked(&self,value:usize)->usize{if value<=self.sqrt{value-1}else{self.len()-self.num/value}}#[doc=" # Safety"]#[doc=" `value` must satisfy `self.contains_value(value)`."]pub unsafe fn value_to_key_unchecked(&self,value:usize)->RangeInclusive<usize>{if value==usize::MAX{return 1..=1;}let start=(self.num/(value+1))+1;let end=self.num/value;start..=end}#[doc=" # Safety"]#[doc=" `key` must satisfy `1 <= key && key <= self.num`."]pub unsafe fn key_to_index_unchecked(&self,key:usize)->usize{let len=self.len();if key<=len-self.sqrt{len-key}else{self.num/key-1}}#[doc=" # Safety"]#[doc=" `key` must satisfy `1 <= key && key <= self.num`."]pub unsafe fn key_to_value_unchecked(&self,key:usize)->usize{self.num/key}}#[doc=" sorted({ ceil(n/k) | k in \\[1, n\\] })"]pub struct CeilQuotientIndex{num:usize,sqrt:usize,pivot:usize}impl CeilQuotientIndex{pub fn new(num:usize)->Self{assert!(num>0,"num must be positive");let sqrt=num.isqrt();let pivot=num.div_ceil(sqrt);Self{num,sqrt,pivot}}pub fn values(&self)->impl ExactSizeIterator<Item=usize>+FusedIterator+'_{let len=self.len();(0..len).map(move|index|unsafe{self.index_to_value_unchecked(index)})}pub fn key_values(&self)->impl ExactSizeIterator<Item=(RangeInclusive<usize>,usize)>+FusedIterator+'_{let len=self.len();(0..len).map(move|index|unsafe{(self.index_to_key_unchecked(index),self.index_to_value_unchecked(index))})}#[allow(clippy::len_without_is_empty)]pub fn len(&self)->usize{self.sqrt+self.pivot-1}pub fn contains_key(&self,key:usize)->bool{(1..=self.num).contains(&key)}pub fn contains_value(&self,value:usize)->bool{if value==0||value>self.num{return false;}if value==1{return true;}let start=self.num.div_ceil(value);let end=(self.num-1)/(value-1);start<=end}pub fn index_to_key(&self,index:usize)->RangeInclusive<usize>{assert!(index<self.len(),"index out of bounds");unsafe{self.index_to_key_unchecked(index)}}pub fn index_to_value(&self,index:usize)->usize{assert!(index<self.len(),"index out of bounds");unsafe{self.index_to_value_unchecked(index)}}pub fn value_to_index(&self,value:usize)->usize{assert!(self.contains_value(value),"value is not present");unsafe{self.value_to_index_unchecked(value)}}pub fn value_to_key(&self,value:usize)->RangeInclusive<usize>{assert!(self.contains_value(value),"value is not present");unsafe{self.value_to_key_unchecked(value)}}pub fn key_to_index(&self,key:usize)->usize{assert!(self.contains_key(key),"key out of bounds");let value=self.key_to_value(key);unsafe{self.value_to_index_unchecked(value)}}pub fn key_to_value(&self,key:usize)->usize{assert!(self.contains_key(key),"key out of bounds");unsafe{self.key_to_value_unchecked(key)}}#[doc=" # Safety"]#[doc=" `index` must satisfy `index < self.len()`."]pub unsafe fn index_to_key_unchecked(&self,index:usize)->RangeInclusive<usize>{if index<self.pivot{if index==0{return self.num..=self.num;}let start=self.num.div_ceil(index+1);let end=(self.num-1)/index;start..=end}else{let key=self.len()-index;key..=key}}#[doc=" # Safety"]#[doc=" `index` must satisfy `index < self.len()`."]pub unsafe fn index_to_value_unchecked(&self,index:usize)->usize{if index<self.pivot{index+1}else{self.num.div_ceil(self.len()-index)}}#[doc=" # Safety"]#[doc=" `value` must satisfy `self.contains_value(value)`."]pub unsafe fn value_to_index_unchecked(&self,value:usize)->usize{if value<=self.pivot{value-1}else{self.len()-(self.num-1)/(value-1)}}#[doc=" # Safety"]#[doc=" `value` must satisfy `self.contains_value(value)`."]pub unsafe fn value_to_key_unchecked(&self,value:usize)->RangeInclusive<usize>{if value==1{return self.num..=self.num;}let start=self.num.div_ceil(value);let end=(self.num-1)/(value-1);start..=end}#[doc=" # Safety"]#[doc=" `key` must satisfy `1 <= key && key <= self.num`."]pub unsafe fn key_to_index_unchecked(&self,key:usize)->usize{if key<self.sqrt{self.len()-key}else{self.num.div_ceil(key)-1}}#[doc=" # Safety"]#[doc=" `key` must satisfy `1 <= key && key <= self.num`."]pub unsafe fn key_to_value_unchecked(&self,key:usize)->usize{self.num.div_ceil(key)}}}