// codesnip-guard: ternary_search
#[cfg_attr(any(),rustfmt::skip)]pub use self::ternary_search::{golden_ternary_search,piecewise_ternary_search,ternary_search};#[cfg_attr(any(),rustfmt::skip)]pub mod ternary_search{use std::ops::RangeInclusive;#[doc=" fibonacci search helper"]pub trait FibonacciSearch:Sized{fn fibonacci_search<T,F>(self,other:Self,f:F)->(Self,T)where T:PartialOrd,F:FnMut(Self)->T;}macro_rules!impl_fibonacci_search_unsigned{($($t:ty)*)=>{$(impl FibonacciSearch for$t{fn fibonacci_search<T,F>(self,other:Self,mut f:F)->(Self,T)where T:PartialOrd,F:FnMut(Self)->T,{let l=self;let r=other;assert!(l<=r);const W:usize=[12,23,46,92,185][<$t>::BITS.ilog2()as usize-3];const FIB:[$t;W]={let mut fib=[0;W];fib[0]=1;fib[1]=2;let mut i=2;while i<W{fib[i]=fib[i-1]+fib[i-2];i+=1;}fib};let mut s=l;let mut v0=None;let mut v1=None;let mut v2=None;let mut v3=None;for w in FIB[..FIB.partition_point(|&f|f<r-l)].windows(2).rev(){let(w0,w1)=(w[0],w[1]);if w1>r-s||v1.get_or_insert_with(||f(s+w0))<=v2.get_or_insert_with(||f(s+w1)){v3=v2;v2=v1;v1=None;}else{v0=v1;v1=v2;v2=None;s+=w0;}}let mut kv=(s,v0.unwrap_or_else(||f(s)));if s<r{let v=v1.or(v2).unwrap_or_else(||f(s+1));if v<kv.1{kv=(s+1,v);}if s+1<r{let v=v3.unwrap_or_else(||f(s+2));if v<kv.1{kv=(s+2,v);}}}kv}})*};}impl_fibonacci_search_unsigned!(u8 u16 u32 u64 u128 usize);#[doc=" ternary search helper"]pub trait Trisect:Clone{type Key:FibonacciSearch;fn trisect_key(self)->Self::Key;fn trisect_unkey(key:Self::Key)->Self;}macro_rules!impl_trisect_unsigned{($($t:ty)*)=>{$(impl Trisect for$t{type Key=$t;fn trisect_key(self)->Self::Key{self}fn trisect_unkey(key:Self::Key)->Self{key}})*};}macro_rules!impl_trisect_signed{($({$i:ident$u:ident})*)=>{$(impl Trisect for$i{type Key=$u;fn trisect_key(self)->Self::Key{(self as$u)^(1<< <$u>::BITS-1)}fn trisect_unkey(key:Self::Key)->Self{(key^(1<< <$u>::BITS-1))as$i}})*};}macro_rules!impl_trisect_float{($({$t:ident$u:ident$i:ident})*)=>{$(impl Trisect for$t{type Key=$u;fn trisect_key(self)->Self::Key{let a=self.to_bits()as$i;(a^(((a>><$u>::BITS-1)as$u)>>1)as$i)as$u^(1<< <$u>::BITS-1)}fn trisect_unkey(key:Self::Key)->Self{let key=(key^(1<< <$u>::BITS-1))as$i;$t::from_bits((key^(((key>><$u>::BITS-1)as$u)>>1)as$i)as _)}})*};}impl_trisect_unsigned!(u8 u16 u32 u64 u128 usize);impl_trisect_signed!({i8 u8}{i16 u16}{i32 u32}{i64 u64}{i128 u128}{isize usize});impl_trisect_float!({f32 u32 i32}{f64 u64 i64});#[doc=" Returns the element that gives the minimum value from the strictly concave up function and the minimum value."]pub fn ternary_search<K,V,F>(range:RangeInclusive<K>,mut f:F)->(K,V)where K:Trisect,V:PartialOrd,F:FnMut(K)->V{let(l,r)=range.into_inner();let(k,v)=<K::Key as FibonacciSearch>::fibonacci_search(l.trisect_key(),r.trisect_key(),|x|{f(Trisect::trisect_unkey(x))});(K::trisect_unkey(k),v)}pub fn piecewise_ternary_search<const N:usize,K,V,F>(piece:[K;N],mut f:F)->(K,V)where K:Trisect,V:PartialOrd,F:FnMut(K)->V{piece.windows(2).map(|w|ternary_search(w[0].clone()..=w[1].clone(),&mut f)).min_by(|a,b|a.1 .partial_cmp(&b.1).unwrap()).unwrap_or_else(| |(piece[0].clone(),f(piece[0].clone())))}pub fn golden_ternary_search<T>(range:RangeInclusive<f64>,count:usize,mut f:impl FnMut(f64)->T)->(f64,T)where T:PartialOrd{let(mut l,mut r)=range.into_inner();const GOLDEN_RATIO_INV:f64=1f64/1.618_033_988_749_895_f64;let mut v0=None;let mut v1=None;let mut v2=None;let mut v3=None;for _ in 0..count{let w=(r-l)*GOLDEN_RATIO_INV;if v1.get_or_insert_with(| |f(r-w))<=v2.get_or_insert_with(| |f(l+w)){v3=v2;v2=v1;v1=None;r=l+w;}else{v0=v1;v1=v2;v2=None;l=r-w;}}let kv=(l,v0.unwrap_or_else(| |f(l)));let kv2=(r,v3.unwrap_or_else(| |f(r)));if kv2.1<kv.1{kv2}else{kv}}}