qfall_math/integer_mod_q/mat_zq/
sort.rs

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

qfall_math/integer_mod_q/mat_zq/
sort.rs
