qfall_math/integer/mat_z/
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 [`MatZ`].
10
11use super::MatZ;
12use crate::{
13    error::MathError,
14    traits::{MatrixDimensions, MatrixGetSubmatrix, MatrixSetSubmatrix},
15};
16
17impl MatZ {
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::MatZ;
33    /// use std::str::FromStr;
34    /// let mat = MatZ::from_str("[[3, 2, 1]]").unwrap();
35    /// let cmp = MatZ::from_str("[[1, 2, 3]]").unwrap();
36    ///
37    /// let sorted = mat.sort_by_column(MatZ::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::{MatZ, Z}, error::MathError, traits::{MatrixDimensions, MatrixGetEntry}};
45    /// use std::str::FromStr;
46    /// let mat = MatZ::from_str("[[3, 2, 1]]").unwrap();
47    /// let cmp = MatZ::from_str("[[1, 2, 3]]").unwrap();
48    ///
49    /// fn custom_cond_func(matrix: &MatZ) -> Result<Z, MathError> {
50    ///     let mut sum = Z::ZERO;
51    ///     for entry in matrix.get_entries_rowwise() {
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());
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::MatZ;
100    /// use std::str::FromStr;
101    /// let mat = MatZ::from_str("[[3],[2],[1]]").unwrap();
102    /// let cmp = MatZ::from_str("[[1],[2],[3]]").unwrap();
103    ///
104    /// let sorted = mat.sort_by_row(MatZ::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::{MatZ, Z}, error::MathError, traits::{MatrixDimensions, MatrixGetEntry}};
112    /// use std::str::FromStr;
113    /// let mat = MatZ::from_str("[[3],[2],[1]]").unwrap();
114    /// let cmp = MatZ::from_str("[[1],[2],[3]]").unwrap();
115    ///
116    /// fn custom_cond_func(matrix: &MatZ) -> Result<Z, MathError> {
117    ///     let mut sum = Z::ZERO;
118    ///     for entry in matrix.get_entries_columnwise() {
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());
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::MatZ;
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: &MatZ) -> 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 = MatZ::from_str("[[3, 0, 2, -1],[2, 2, 2, 2]]").unwrap();
175        let cmp = MatZ::from_str("[[0, -1, 2, 3],[2, 2, 2, 2]]").unwrap();
176
177        let res = mat.sort_by_column(MatZ::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 = MatZ::from_str(&format!(
186            "[[{}, {}, 5],[1, 2, 5],[0, 0, 0]]",
187            i64::MIN,
188            i64::MAX
189        ))
190        .unwrap();
191        let cmp = MatZ::from_str(&format!(
192            "[[5, {}, {}],[5, 2, 1],[0, 0, 0]]",
193            i64::MAX,
194            i64::MIN
195        ))
196        .unwrap();
197
198        let res = mat.sort_by_column(MatZ::norm_eucl_sqrd).unwrap();
199
200        assert_eq!(cmp, res);
201    }
202
203    /// Checks whether sorting by column length acc. to infty norm works correct for large entries
204    #[test]
205    fn column_norm_infty_large_entries() {
206        let mat = MatZ::from_str(&format!(
207            "[[{}, {}, 5],[1, 2, 5],[0, 0, 0]]",
208            i64::MIN,
209            i64::MAX
210        ))
211        .unwrap();
212        let cmp = MatZ::from_str(&format!(
213            "[[5, {}, {}],[5, 2, 1],[0, 0, 0]]",
214            i64::MAX,
215            i64::MIN
216        ))
217        .unwrap();
218
219        let res = mat.sort_by_column(MatZ::norm_infty).unwrap();
220
221        assert_eq!(cmp, res);
222    }
223
224    /// Checks whether sorting by columns length acc. to eucl. norm works properly
225    /// for matrices with a few more entries
226    #[test]
227    fn many_columns() {
228        let mat = MatZ::from_str("[[3, 4, 1, 7, 2, 0, 9, -8, 6, 5]]").unwrap();
229        let cmp = MatZ::from_str("[[0, 1, 2, 3, 4, 5, 6, 7, -8, 9]]").unwrap();
230
231        let res = mat.sort_by_column(MatZ::norm_eucl_sqrd).unwrap();
232
233        assert_eq!(cmp, res);
234    }
235
236    /// Checks whether an error is returned for sorting by columns if the `cond_func` returns an error
237    #[test]
238    fn column_error_cond_func() {
239        let mat = MatZ::from_str("[[1, 2],[3, 4]]").unwrap();
240
241        let res = mat.sort_by_column(failing_func);
242
243        assert!(res.is_err());
244    }
245
246    /// Checks whether sorting by row length acc. to eucl. norm works correct for small entries
247    #[test]
248    fn row_norm_eucl_sqrd_small_entries() {
249        let mat = MatZ::from_str("[[3, 0, 2, -1],[2, 2, 2, 2]]").unwrap();
250        let cmp = MatZ::from_str("[[3, 0, 2, -1],[2, 2, 2, 2]]").unwrap();
251
252        let res = mat.sort_by_row(MatZ::norm_eucl_sqrd).unwrap();
253
254        assert_eq!(cmp, res);
255    }
256
257    /// Checks whether sorting by row length acc. to eucl. norm works correct for large entries
258    #[test]
259    fn row_norm_eucl_sqrd_large_entries() {
260        let mat = MatZ::from_str(&format!(
261            "[[{}, 0, 5],[{}, 2, 5],[0, 0, 0]]",
262            i64::MIN,
263            i64::MAX
264        ))
265        .unwrap();
266        let cmp = MatZ::from_str(&format!(
267            "[[0, 0, 0],[{}, 2, 5],[{}, 0, 5]]",
268            i64::MAX,
269            i64::MIN
270        ))
271        .unwrap();
272
273        let res = mat.sort_by_row(MatZ::norm_eucl_sqrd).unwrap();
274
275        assert_eq!(cmp, res);
276    }
277
278    /// Checks whether sorting by row length acc. to infty norm works correct for large entries
279    #[test]
280    fn row_norm_infty_large_entries() {
281        let mat = MatZ::from_str(&format!(
282            "[[{}, 0, 5],[{}, 2, 5],[0, 0, 0]]",
283            i64::MIN,
284            i64::MAX
285        ))
286        .unwrap();
287        let cmp = MatZ::from_str(&format!(
288            "[[0, 0, 0],[{}, 2, 5],[{}, 0, 5]]",
289            i64::MAX,
290            i64::MIN
291        ))
292        .unwrap();
293
294        let res = mat.sort_by_row(MatZ::norm_infty).unwrap();
295
296        assert_eq!(cmp, res);
297    }
298
299    /// Checks whether sorting by rows length acc. to eucl. norm works properly
300    /// for matrices with a few more entries
301    #[test]
302    fn many_rows() {
303        let mat = MatZ::from_str("[[3],[0],[-1],[-7],[2],[9],[4],[8],[6],[5]]").unwrap();
304        let cmp = MatZ::from_str("[[0],[-1],[2],[3],[4],[5],[6],[-7],[8],[9]]").unwrap();
305
306        let res = mat.sort_by_row(MatZ::norm_eucl_sqrd).unwrap();
307
308        assert_eq!(cmp, res);
309    }
310
311    /// Checks whether an error is returned for sorting by rows if the `cond_func` returns an error
312    #[test]
313    fn row_error_cond_func() {
314        let mat = MatZ::from_str("[[1, 2],[3, 4]]").unwrap();
315
316        let res = mat.sort_by_row(failing_func);
317
318        assert!(res.is_err());
319    }
320}
qfall_math/integer/mat_z/sort.rs

qfall_math/integer/mat_z/
sort.rs
