qfall_math/integer/mat_poly_over_z/sort.rs
1// Copyright © 2025 Marcel Luca Schmidt
2//
3// This file is part of qFALL-math.
4//
5// qFALL-math is free software: you can redistribute it and/or modify it under
6// the terms of the Mozilla Public License Version 2.0 as published by the
7// Mozilla Foundation. See <https://mozilla.org/en-US/MPL/2.0/>.
8
9//! Contains functions to sort [`MatPolyOverZ`].
10
11use super::MatPolyOverZ;
12use crate::{
13 error::MathError,
14 traits::{MatrixDimensions, MatrixGetSubmatrix, MatrixSetSubmatrix},
15};
16
17impl MatPolyOverZ {
18 /// Sorts the columns of the matrix based on some condition defined by `cond_func` in an ascending order.
19 ///
20 /// This condition is usually a norm with the described input-output behaviour.
21 ///
22 /// Parameters:
23 /// - `cond_func`: computes values implementing [`Ord`] over the columns of the specified matrix.
24 /// These values are then used to re-order / sort the rows of the matrix.
25 ///
26 /// Returns an empty `Ok` if the action could be performed successfully.
27 /// A [`MathError`] is returned if the execution of `cond_func` returned an error.
28 ///
29 /// # Examples
30 /// ## Use a build-in function as condition
31 /// ```
32 /// use qfall_math::integer::MatPolyOverZ;
33 /// use std::str::FromStr;
34 /// let mat = MatPolyOverZ::from_str("[[2 3 4, 1 2, 1 1]]").unwrap();
35 /// let cmp = MatPolyOverZ::from_str("[[1 1, 1 2, 2 3 4]]").unwrap();
36 ///
37 /// let sorted = mat.sort_by_column(MatPolyOverZ::norm_eucl_sqrd).unwrap();
38 ///
39 /// assert_eq!(cmp, sorted);
40 /// ```
41 /// ## Use a custom function as condition
42 /// This function needs to take a column vector as input and output a type implementing [`PartialOrd`]
43 /// ```
44 /// use qfall_math::{integer::{MatPolyOverZ, Z}, error::MathError, traits::{MatrixDimensions, MatrixGetEntry}};
45 /// use crate::qfall_math::traits::GetCoefficient;
46 /// use std::str::FromStr;
47 /// let mat = MatPolyOverZ::from_str("[[2 0 4, 1 2, 1 1]]").unwrap();
48 /// let cmp = MatPolyOverZ::from_str("[[2 0 4, 1 1, 1 2]]").unwrap();
49 ///
50 /// fn custom_cond_func(matrix: &MatPolyOverZ) -> Result<Z, MathError> {
51 /// let mut sum = Z::ZERO;
52 /// for entry in matrix.get_entries_rowwise() {
53 /// sum += entry.get_coeff(0)?;
54 /// }
55 /// Ok(sum)
56 /// }
57 ///
58 /// let sorted = mat.sort_by_column(custom_cond_func).unwrap();
59 ///
60 /// assert_eq!(cmp, sorted);
61 /// ```
62 ///
63 /// # Errors and Failures
64 /// - Returns a [`MathError`] of the same type as `cond_func` if the execution of `cond_func` fails.
65 pub fn sort_by_column<T: Ord>(
66 &self,
67 cond_func: fn(&Self) -> Result<T, MathError>,
68 ) -> Result<Self, MathError> {
69 let mut condition_values = Vec::with_capacity(self.get_num_columns() as usize);
70 for col in 0..self.get_num_columns() {
71 condition_values.push(cond_func(&unsafe { self.get_column_unchecked(col) })?);
72 }
73
74 let mut id_vec: Vec<usize> = (0..self.get_num_columns() as usize).collect();
75 id_vec.sort_by_key(|x| &condition_values[*x]);
76
77 let mut out = Self::new(self.get_num_rows(), self.get_num_columns());
78 for (col, item) in id_vec.iter().enumerate() {
79 let (col_0, col_1) = (col as i64, *item as i64);
80 unsafe { out.set_column_unchecked(col_0, self, col_1) };
81 }
82
83 Ok(out)
84 }
85
86 /// Sorts the rows of the matrix based on some condition defined by `cond_func` in an ascending order.
87 ///
88 /// This condition is usually a norm with the described input-output behaviour.
89 ///
90 /// Parameters:
91 /// - `cond_func`: computes values implementing [`Ord`] over the columns of the specified matrix.
92 /// These values are then used to re-order / sort the columns of the matrix.
93 ///
94 /// Returns an empty `Ok` if the action could be performed successfully.
95 /// A [`MathError`] is returned if the execution of `cond_func` returned an error.
96 ///
97 /// # Examples
98 /// ## Use a build-in function as condition
99 /// ```
100 /// use qfall_math::integer::MatPolyOverZ;
101 /// use std::str::FromStr;
102 /// let mat = MatPolyOverZ::from_str("[[2 3 4],[1 2],[1 1]]").unwrap();
103 /// let cmp = MatPolyOverZ::from_str("[[1 1],[1 2],[2 3 4]]").unwrap();
104 ///
105 /// let sorted = mat.sort_by_row(MatPolyOverZ::norm_infty).unwrap();
106 ///
107 /// assert_eq!(cmp, sorted);
108 /// ```
109 /// ## Use a custom function as condition
110 /// This function needs to take a row vector as input and output a type implementing [`PartialOrd`]
111 /// ```
112 /// use qfall_math::{integer::{MatPolyOverZ, Z}, error::MathError, traits::{MatrixDimensions, MatrixGetEntry}};
113 /// use crate::qfall_math::traits::GetCoefficient;
114 /// use std::str::FromStr;
115 /// let mat = MatPolyOverZ::from_str("[[2 0 4],[1 2],[1 1]]").unwrap();
116 /// let cmp = MatPolyOverZ::from_str("[[2 0 4],[1 1],[1 2]]").unwrap();
117 ///
118 /// fn custom_cond_func(matrix: &MatPolyOverZ) -> Result<Z, MathError> {
119 /// let mut sum = Z::ZERO;
120 /// for entry in matrix.get_entries_columnwise() {
121 /// sum += entry.get_coeff(0)?;
122 /// }
123 /// Ok(sum)
124 /// }
125 ///
126 /// let sorted = mat.sort_by_row(custom_cond_func).unwrap();
127 ///
128 /// assert_eq!(cmp, sorted);
129 /// ```
130 ///
131 /// # Errors and Failures
132 /// - Returns a [`MathError`] of the same type as `cond_func` if the execution of `cond_func` fails.
133 pub fn sort_by_row<T: Ord>(
134 &self,
135 cond_func: fn(&Self) -> Result<T, MathError>,
136 ) -> Result<Self, MathError> {
137 let mut condition_values = Vec::with_capacity(self.get_num_rows() as usize);
138 for row in 0..self.get_num_rows() {
139 condition_values.push(cond_func(&unsafe { self.get_row_unchecked(row) })?);
140 }
141 let mut id_vec: Vec<usize> = (0..self.get_num_rows() as usize).collect();
142 id_vec.sort_by_key(|x| &condition_values[*x]);
143
144 let mut out = Self::new(self.get_num_rows(), self.get_num_columns());
145 for (row, item) in id_vec.iter().enumerate() {
146 let (row_0, row_1) = (row as i64, *item as i64);
147 unsafe { out.set_row_unchecked(row_0, self, row_1) };
148 }
149
150 Ok(out)
151 }
152}
153
154#[cfg(test)]
155mod test_sort_by_length {
156 use super::MatPolyOverZ;
157 use crate::error::{MathError, StringConversionError};
158 use std::str::FromStr;
159
160 /// This function should fail in any case a vector is provided to it.
161 /// As `sort_by_column` and `sort_by_row` execute this function on the columns resp. rows of its matrix,
162 /// it should always return an error if used as `cond_func` for these two functions
163 fn failing_func(matrix: &MatPolyOverZ) -> Result<(), MathError> {
164 if matrix.is_vector() {
165 Err(StringConversionError::InvalidMatrix(String::from(
166 "Some silly mistake was made - on purpose",
167 )))?
168 } else {
169 Ok(())
170 }
171 }
172
173 /// Checks whether sorting by column length acc. to eucl. norm works correct for small entries
174 #[test]
175 fn column_norm_eucl_sqrd_small_entries() {
176 let mat =
177 MatPolyOverZ::from_str("[[1 3, 0, 1 2, 1 -1],[1 2, 1 2, 1 2, 1 2]]").unwrap();
178 let cmp =
179 MatPolyOverZ::from_str("[[0, 1 -1, 1 2, 1 3],[1 2, 1 2, 1 2, 1 2]]").unwrap();
180
181 let res = mat.sort_by_column(MatPolyOverZ::norm_eucl_sqrd).unwrap();
182
183 assert_eq!(cmp, res);
184 }
185
186 /// Checks whether sorting by column length acc. to eucl. norm works correct for large entries
187 #[test]
188 fn column_norm_eucl_sqrd_large_entries() {
189 let mat = MatPolyOverZ::from_str(&format!(
190 "[[1 {}, 1 {}, 1 5],[1 1, 1 2, 1 5],[0, 0, 0]]",
191 i64::MIN,
192 i64::MAX
193 ))
194 .unwrap();
195 let cmp = MatPolyOverZ::from_str(&format!(
196 "[[1 5, 1 {}, 1 {}],[1 5, 1 2, 1 1],[0, 0, 0]]",
197 i64::MAX,
198 i64::MIN
199 ))
200 .unwrap();
201
202 let res = mat.sort_by_column(MatPolyOverZ::norm_eucl_sqrd).unwrap();
203
204 assert_eq!(cmp, res);
205 }
206
207 /// Checks whether sorting by columns length acc. to eucl. norm works properly
208 /// for matrices with a few more entries
209 #[test]
210 fn many_columns() {
211 let mat =
212 MatPolyOverZ::from_str("[[1 3, 1 4, 1 1, 1 7, 1 2, 0, 1 9, 1 -8, 1 6, 1 5]]")
213 .unwrap();
214 let cmp =
215 MatPolyOverZ::from_str("[[0, 1 1, 1 2, 1 3, 1 4, 1 5, 1 6, 1 7, 1 -8, 1 9]]")
216 .unwrap();
217
218 let res = mat.sort_by_column(MatPolyOverZ::norm_eucl_sqrd).unwrap();
219
220 assert_eq!(cmp, res);
221 }
222
223 /// Checks whether an error is returned for sorting by columns if the `cond_func` returns an error
224 #[test]
225 fn column_error_cond_func() {
226 let mat = MatPolyOverZ::from_str("[[1 1, 1 2],[1 3, 1 4]]").unwrap();
227
228 let res = mat.sort_by_column(failing_func);
229
230 assert!(res.is_err());
231 }
232
233 /// Checks whether sorting by row length acc. to eucl. norm works correct for small entries
234 #[test]
235 fn row_norm_eucl_sqrd_small_entries() {
236 let mat =
237 MatPolyOverZ::from_str("[[1 3, 0, 1 2, 1 -1],[1 2, 1 2, 1 2, 1 2]]").unwrap();
238 let cmp =
239 MatPolyOverZ::from_str("[[1 3, 0, 1 2, 1 -1],[1 2, 1 2, 1 2, 1 2]]").unwrap();
240
241 let res = mat.sort_by_row(MatPolyOverZ::norm_eucl_sqrd).unwrap();
242
243 assert_eq!(cmp, res);
244 }
245
246 /// Checks whether sorting by row length acc. to eucl. norm works correct for large entries
247 #[test]
248 fn row_norm_eucl_sqrd_large_entries() {
249 let mat = MatPolyOverZ::from_str(&format!(
250 "[[1 {}, 0, 1 5],[1 {}, 1 2, 1 5],[0, 0, 0]]",
251 i64::MIN,
252 i64::MAX
253 ))
254 .unwrap();
255 let cmp = MatPolyOverZ::from_str(&format!(
256 "[[0, 0, 0],[1 {}, 1 2, 1 5],[1 {}, 0, 1 5]]",
257 i64::MAX,
258 i64::MIN
259 ))
260 .unwrap();
261
262 let res = mat.sort_by_row(MatPolyOverZ::norm_eucl_sqrd).unwrap();
263
264 assert_eq!(cmp, res);
265 }
266
267 /// Checks whether sorting by row length acc. to infty norm works correct for large entries
268 #[test]
269 fn row_norm_infty_large_entries() {
270 let mat = MatPolyOverZ::from_str(&format!(
271 "[[1 {}, 0, 1 5],[1 {}, 1 2, 1 5],[0, 0, 0]]",
272 i64::MIN,
273 i64::MAX
274 ))
275 .unwrap();
276 let cmp = MatPolyOverZ::from_str(&format!(
277 "[[0, 0, 0],[1 {}, 1 2, 1 5],[1 {}, 0, 1 5]]",
278 i64::MAX,
279 i64::MIN
280 ))
281 .unwrap();
282
283 let res = mat.sort_by_row(MatPolyOverZ::norm_infty).unwrap();
284
285 assert_eq!(cmp, res);
286 }
287
288 /// Checks whether sorting by rows length acc. to eucl. norm works properly
289 /// for matrices with a few more entries
290 #[test]
291 fn many_rows() {
292 let mat = MatPolyOverZ::from_str(
293 "[[1 3],[0],[1 -1],[1 -7],[1 2],[1 9],[1 4],[1 8],[1 6],[1 5]]",
294 )
295 .unwrap();
296 let cmp = MatPolyOverZ::from_str(
297 "[[0],[1 -1],[1 2],[1 3],[1 4],[1 5],[1 6],[1 -7],[1 8],[1 9]]",
298 )
299 .unwrap();
300
301 let res = mat.sort_by_row(MatPolyOverZ::norm_eucl_sqrd).unwrap();
302
303 assert_eq!(cmp, res);
304 }
305
306 /// Checks whether an error is returned for sorting by rows if the `cond_func` returns an error
307 #[test]
308 fn row_error_cond_func() {
309 let mat = MatPolyOverZ::from_str("[[1 1, 1 2],[1 3, 1 4]]").unwrap();
310
311 let res = mat.sort_by_row(failing_func);
312
313 assert!(res.is_err());
314 }
315}