fn finite_pieces<T>(values: &[T]) -> Option<Vec<LinearPiece<T>>>Examples found in repository?
crates/competitive/src/math/min_plus_convolution/piecewise_linear.rs (line 135)
127pub fn min_plus_convolution_linear<T>(a: &[T], b: &[T]) -> Vec<T>
128where
129 T: Signed + TryFrom<usize>,
130{
131 let len = output_len(a.len(), b.len());
132 if len == 0 {
133 return Vec::new();
134 }
135 let a_piece = finite_pieces(a).filter(|pieces| pieces.len() == 1);
136 let b_piece = finite_pieces(b).filter(|pieces| pieces.len() == 1);
137 let (arbitrary, piece) = if let Some(pieces) = b_piece {
138 (a, pieces[0])
139 } else if let Some(pieces) = a_piece {
140 (b, pieces[0])
141 } else {
142 panic!("at least one min-plus convolution input must be finite and linear")
143 };
144 convolve_pieces(arbitrary, std::iter::once(piece), len)
145}
146
147pub(super) fn linear<T>(arbitrary: &[T], structured: &[T]) -> Vec<T>
148where
149 T: Signed + TryFrom<usize>,
150{
151 let len = output_len(arbitrary.len(), structured.len());
152 convolve_pieces(arbitrary, pieces(structured), len)
153}
154
155/// Computes convolution using the input with fewer maximal linear pieces.
156///
157/// If that input has `p` pieces, the running time is `O(p * (n + m))`.
158///
159/// # Panics
160///
161/// Panics unless at least one input is finite, or an index cannot be
162/// represented by `T`.
163pub fn min_plus_convolution_piecewise_linear<T>(a: &[T], b: &[T]) -> Vec<T>
164where
165 T: Signed + TryFrom<usize>,
166{
167 let len = output_len(a.len(), b.len());
168 if len == 0 {
169 return Vec::new();
170 }
171 let a_pieces = finite_pieces(a);
172 let b_pieces = finite_pieces(b);
173 let (arbitrary, structured) = match (a_pieces, b_pieces) {
174 (Some(a_pieces), Some(b_pieces)) if a_pieces.len() < b_pieces.len() => (b, a_pieces),
175 (Some(_), Some(b_pieces)) => (a, b_pieces),
176 (Some(a_pieces), None) => (b, a_pieces),
177 (None, Some(b_pieces)) => (a, b_pieces),
178 (None, None) => {
179 panic!("at least one min-plus convolution input must be finite")
180 }
181 };
182 convolve_pieces(arbitrary, structured, len)
183}