// codesnip-guard: RelaxedConvolution
#[cfg_attr(any(),rustfmt::skip)]pub use self::relaxed_convolution::RelaxedConvolution;#[cfg_attr(any(),rustfmt::skip)]mod relaxed_convolution{use super::{ConvolveSteps,Zero};use std::{fmt::Debug,iter::zip,marker::PhantomData,ops::{AddAssign,Index},slice::SliceIndex};pub struct RelaxedConvolution<T,C>where C:ConvolveSteps<T=Vec<T>>{a:Vec<T>,b:Vec<T>,c:Vec<T>,_marker:PhantomData<fn()->C>}impl<T:Debug,C>Debug for RelaxedConvolution<T,C>where C:ConvolveSteps<T=Vec<T>>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{f.debug_struct("RelaxedConvolution").field("a",&self.a).field("b",&self.b).field("c",&self.c).finish()}}impl<T,C>Default for RelaxedConvolution<T,C>where C:ConvolveSteps<T=Vec<T>>{fn default()->Self{Self{a:Default::default(),b:Default::default(),c:Default::default(),_marker:PhantomData}}}impl<T,C>RelaxedConvolution<T,C>where T:Clone+Zero+AddAssign<T>,C:ConvolveSteps<T=Vec<T>>{pub fn push(&mut self,x:T,y:T){let q=self.a.len();self.a.push(x);self.b.push(y);self.c.push(T::zero());if q!=0{self.c.push(T::zero());}let k=(q+2).trailing_zeros();let mut s=0;for k in 0..k+1-(1<<k==q+2)as u32{let size=1<<k;self.calc_block(s,q+1-size,size);if q+1-size!=s{self.calc_block(q+1-size,s,size);}s+=size;}}fn calc_block(&mut self,la:usize,lb:usize,size:usize){let a=self.a[la..la+size].to_vec();let b=self.b[lb..lb+size].to_vec();let c=C::convolve(a,b);for(c,d)in zip(c,&mut self.c[la+lb..]){*d+=c;}}}impl<T,C,I>Index<I>for RelaxedConvolution<T,C>where C:ConvolveSteps<T=Vec<T>>,I:SliceIndex<[T]>{type Output=<I as SliceIndex<[T]>>::Output;fn index(&self,index:I)->&Self::Output{self.c.index(index)}}}
// codesnip-guard: ConvolveSteps
#[cfg_attr(any(),rustfmt::skip)]pub use self::convolve_steps::ConvolveSteps;#[cfg_attr(any(),rustfmt::skip)]mod convolve_steps{pub trait ConvolveSteps{#[doc=" Whether transform multiplication computes modulo x^n - 1 in the coefficient ring."]const CYCLIC:bool=false;type T;type F;fn length(t:&Self::T)->usize;fn transform(t:Self::T,len:usize)->Self::F;fn inverse_transform(f:Self::F,len:usize)->Self::T;fn multiply(f:&mut Self::F,g:&Self::F);fn square(t:Self::T,len:usize)->Self::T where Self::T:Clone{let mut f=Self::transform(t.clone(),len);let g=Self::transform(t,len);Self::multiply(&mut f,&g);Self::inverse_transform(f,len)}fn convolve(a:Self::T,b:Self::T)->Self::T{let len=(Self::length(&a)+Self::length(&b)).saturating_sub(1);let mut a=Self::transform(a,len);let b=Self::transform(b,len);Self::multiply(&mut a,&b);Self::inverse_transform(a,len)}}}
// codesnip-guard: zero_one
#[cfg_attr(any(),rustfmt::skip)]pub use self::zero_one::{One,Zero};#[cfg_attr(any(),rustfmt::skip)]mod zero_one{pub trait Zero:Sized{fn zero()->Self;#[inline]fn is_zero(&self)->bool where Self:PartialEq{self==&Self::zero()}#[inline]fn set_zero(&mut self){*self=Self::zero();}}pub trait One:Sized{fn one()->Self;#[inline]fn is_one(&self)->bool where Self:PartialEq{self==&Self::one()}#[inline]fn set_one(&mut self){*self=Self::one();}}macro_rules!impl_zero_one{($({$(<$T:ident:$Bound:ident>)?$Trait:ident$method:ident$($t:ty)*,$e:expr})*)=>{$(impl_zero_one!(@impl[$(<$T:$Bound>)?]$Trait$method[$($t)*],$e);)*};(@impl[<$T:ident:$Bound:ident>]$Trait:ident$method:ident[$($t:ty)*],$e:expr)=>{$(impl<$T:$Bound>$Trait for$t{fn$method()->Self{$e}})*};(@impl[]$Trait:ident$method:ident[$($t:ty)*],$e:expr)=>{$(impl$Trait for$t{fn$method()->Self{$e}})*};}impl_zero_one!({Zero zero u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128,0}{Zero zero f32 f64,0.}{One one u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128,1}{One one f32 f64,1.}{<T:Zero>Zero zero std::num::Wrapping<T>,Self(T::zero())}{<T:One>One one std::num::Wrapping<T>,Self(T::one())});}