fn pieces<T>(values: &[T]) -> Vec<LinearPiece<T>>Examples found in repository?
crates/competitive/src/math/min_plus_convolution/piecewise_linear.rs (line 65)
58fn finite_pieces<T>(values: &[T]) -> Option<Vec<LinearPiece<T>>>
59where
60 T: Signed + TryFrom<usize>,
61{
62 if values.iter().any(T::is_maximum) {
63 None
64 } else {
65 Some(pieces(values))
66 }
67}
68
69fn convolve_piece<T>(arbitrary: &[T], piece: LinearPiece<T>, result: &mut [T])
70where
71 T: Signed + TryFrom<usize>,
72{
73 let mut deque = VecDeque::with_capacity(arbitrary.len());
74 let mut next_to_add = 0;
75 for (output, slot) in result.iter_mut().enumerate() {
76 if output < piece.start {
77 continue;
78 }
79 let upper = (output - piece.start).min(arbitrary.len() - 1);
80 while next_to_add <= upper {
81 if !arbitrary[next_to_add].is_maximum() {
82 let index = T::try_from(next_to_add)
83 .ok()
84 .expect("piecewise-linear index must fit the value type");
85 let transformed = arbitrary[next_to_add] - piece.slope * index;
86 while deque.back().is_some_and(|&(_, value)| value >= transformed) {
87 deque.pop_back();
88 }
89 deque.push_back((next_to_add, transformed));
90 }
91 next_to_add += 1;
92 }
93 let lower = output.saturating_sub(piece.end);
94 while deque.front().is_some_and(|&(index, _)| index < lower) {
95 deque.pop_front();
96 }
97 if let Some(&(_, minimum)) = deque.front() {
98 let output = T::try_from(output)
99 .ok()
100 .expect("piecewise-linear output index must fit the value type");
101 *slot = (*slot).min(piece.slope * output + piece.intercept + minimum);
102 }
103 }
104}
105
106fn convolve_pieces<T>(
107 arbitrary: &[T],
108 structured: impl IntoIterator<Item = LinearPiece<T>>,
109 len: usize,
110) -> Vec<T>
111where
112 T: Signed + TryFrom<usize>,
113{
114 let mut result = vec![T::maximum(); len];
115 for piece in structured {
116 convolve_piece(arbitrary, piece, &mut result);
117 }
118 result
119}
120
121/// Computes convolution when at least one input is finite and linear.
122///
123/// # Panics
124///
125/// Panics unless at least one input is finite and linear, or an index cannot
126/// be represented by `T`.
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}
184
185pub(super) fn piecewise_linear<T>(arbitrary: &[T], structured: &[T]) -> Vec<T>
186where
187 T: Signed + TryFrom<usize>,
188{
189 let len = output_len(arbitrary.len(), structured.len());
190 convolve_pieces(arbitrary, pieces(structured), len)
191}