qfall_math/utils/
index.rs

1// Copyright © 2023 Marcel Luca Schmidt, Marvin Beckmann
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//! Implements methods to pre-process indices under certain conditions.
10
11use crate::error::MathError;
12use crate::traits::MatrixDimensions;
13use std::fmt::Display;
14
15/// Converts index into an [`i64`] that must be greater or equal than `0`
16/// and must fit into an [`i64`].
17///
18/// Parameters:
19/// - `index`: the index that has to be converted into an [`i64`].
20///
21/// Returns an [`i64`] representation of the index or an error if the
22/// index does not fulfill all conditions.
23///
24/// # Examples
25/// ```
26/// use qfall_math::utils::index::evaluate_index;
27///
28/// let index = evaluate_index(u32::MAX).unwrap();
29/// ```
30///
31/// # Errors and Failures
32/// - Returns a [`MathError`] of type [`OutOfBounds`](MathError::OutOfBounds) if
33///   either the index is negative or it does not fit into an [`i64`].
34pub fn evaluate_index(index: impl TryInto<i64> + Display) -> Result<i64, MathError> {
35    // the index must fit into an [`i64`]
36
37    let index: i64 = if cfg!(debug_assertions) {
38        // Only executed in debug mode
39        let index_str = index.to_string();
40        match index.try_into() {
41            Ok(index) => index,
42            _ => {
43                return Err(MathError::OutOfBounds(
44                    "fit into a i64".to_owned(),
45                    index_str,
46                ));
47            }
48        }
49    } else {
50        // Only executed when NOT in debug mode
51        match index.try_into() {
52            Ok(index) => index,
53            _ => {
54                return Err(MathError::OutOfBounds(
55                    "fit into a i64".to_owned(),
56                    "rerun in debug mode to obtain the incorrect index".to_owned(),
57                ));
58            }
59        }
60    };
61
62    // negative indices can not be addressed
63    if index < 0 {
64        return Err(MathError::OutOfBounds(
65            "be at least zero".to_owned(),
66            index.to_string(),
67        ));
68    }
69    Ok(index)
70}
71
72/// Converts index1 and index2 into [`i64`] that must be greater than `0` and must fit into
73/// an [`i64`].
74///
75/// Parameters:
76/// - `index1`: the first index that has to be converted into an [`i64`].
77/// - `index2`: the second index that has to be converted into an [`i64`].
78///
79/// Returns an [`i64`] representation of index1 and index2 or an error if the
80/// indices do not fulfill all conditions.
81///
82/// # Examples
83/// ```
84/// use qfall_math::utils::index::evaluate_indices;
85///
86/// let (index1, index2) = evaluate_indices(u32::MAX, 3).unwrap();
87/// ```
88///
89/// # Errors and Failures
90/// - Returns a [`MathError`] of type [`OutOfBounds`](MathError::OutOfBounds) if
91///   either the index is negative or it does not fit into an [`i64`].
92pub fn evaluate_indices(
93    index1: impl TryInto<i64> + Display,
94    index2: impl TryInto<i64> + Display,
95) -> Result<(i64, i64), MathError> {
96    let index1_i64 = evaluate_index(index1)?;
97    let index2_i64 = evaluate_index(index2)?;
98
99    Ok((index1_i64, index2_i64))
100}
101
102/// Evaluates whether the provided index is referencing an entry in a vector.
103/// Negative indices are allowed and reference entries form the end of the vector.
104///
105/// Parameters:
106/// - `index`: specifies the index in which the entry is located
107/// - `vector_length`: specifies the length of the vector
108///
109/// Returns the index as an [`i64`] if it references an entry and return
110/// an error otherwise.
111///
112/// # Errors and Failures
113/// - Returns a [`MathError`] of type [`MathError::OutOfBounds`]
114///   if the index is not within the bounds of the vector.
115pub fn evaluate_index_for_vector(
116    index: impl TryInto<i64> + Display,
117    vector_length: i64,
118) -> Result<i64, MathError> {
119    let mut index_i64: i64 = match index.try_into() {
120        Ok(index) => index,
121        _ => {
122            return Err(MathError::OutOfBounds(
123                "fit into a i64".to_owned(),
124                "unknown for performance reasons".to_owned(),
125            ));
126        }
127    };
128
129    if index_i64 < 0 {
130        index_i64 += vector_length;
131        if index_i64 < 0 {
132            return Err(MathError::OutOfBounds(
133                format!("be larger or equal to {}", -vector_length),
134                format!("{}", index_i64 - vector_length),
135            ));
136        }
137    }
138
139    if vector_length <= index_i64 {
140        return Err(MathError::OutOfBounds(
141            format!("be smaller than {vector_length}"),
142            format!("{index_i64}"),
143        ));
144    }
145    Ok(index_i64)
146}
147
148/// Evaluates whether the provided row and column are referencing an entry in a matrix.
149/// Negative indices are allowed and reference rows and columns form the end of the matrix.
150///
151/// Parameters:
152/// - `matrix`: specifies the matrix in which the entry is located
153/// - `row`: specifies the row in which the entry is located
154/// - `column`: specifies the column in which the entry is located
155///
156/// Returns the indices as a pair of [`i64`] if they reference an entry and return
157/// an error otherwise.
158///
159/// # Errors and Failures
160/// - Returns a [`MathError`] of type [`MathError::OutOfBounds`]
161///   if the number of rows or columns is greater than the matrix.
162pub fn evaluate_indices_for_matrix<S: MatrixDimensions + MatrixDimensions>(
163    matrix: &S,
164    row: impl TryInto<i64> + Display,
165    column: impl TryInto<i64> + Display,
166) -> Result<(i64, i64), MathError> {
167    let mut row_i64: i64 = match row.try_into() {
168        Ok(index) => index,
169        _ => {
170            return Err(MathError::OutOfBounds(
171                "fit into a i64".to_owned(),
172                "unknown for performance reasons".to_owned(),
173            ));
174        }
175    };
176
177    let mut column_i64: i64 = match column.try_into() {
178        Ok(index) => index,
179        _ => {
180            return Err(MathError::OutOfBounds(
181                "fit into a i64".to_owned(),
182                "unknown for performance reasons".to_owned(),
183            ));
184        }
185    };
186
187    if row_i64 < 0 {
188        row_i64 += matrix.get_num_rows();
189        if row_i64 < 0 {
190            return Err(MathError::OutOfBounds(
191                format!(
192                    "be larger or equal to ({}, {})",
193                    -matrix.get_num_rows(),
194                    -matrix.get_num_columns()
195                ),
196                format!("({}, {})", row_i64 - matrix.get_num_rows(), column_i64),
197            ));
198        }
199    }
200    if column_i64 < 0 {
201        column_i64 += matrix.get_num_columns();
202        if column_i64 < 0 {
203            return Err(MathError::OutOfBounds(
204                format!(
205                    "be larger or equal to ({}, {})",
206                    -matrix.get_num_rows(),
207                    -matrix.get_num_columns()
208                ),
209                format!("({}, {})", row_i64, column_i64 - matrix.get_num_columns()),
210            ));
211        }
212    }
213
214    if matrix.get_num_rows() <= row_i64 || matrix.get_num_columns() <= column_i64 {
215        return Err(MathError::OutOfBounds(
216            format!(
217                "be smaller than ({}, {})",
218                matrix.get_num_rows(),
219                matrix.get_num_columns()
220            ),
221            format!("({row_i64}, {column_i64})"),
222        ));
223    }
224    Ok((row_i64, column_i64))
225}
226
227/// Helper function to compute bit-reversed index
228fn bit_reverse(mut x: usize, log_n: usize) -> usize {
229    let mut res = 0;
230    for _ in 0..log_n {
231        res = (res << 1) | (x & 1);
232        x >>= 1;
233    }
234    res
235}
236
237/// Applies bit-reversed permutation to the input array
238/// Computes the Bit-Reversed order (BO) of an array.
239///
240/// Parameters:
241/// - `a`: the array whos order should be changed to bit-reversed order
242///
243/// Returns an array in BO order
244///
245/// # Examples
246/// ```
247/// use qfall_math::utils::index::bit_reverse_permutation;
248///
249/// let mut vec: Vec<usize> = (0..4).collect();
250/// bit_reverse_permutation(&mut vec);
251/// let cmp_vec = vec![0, 2, 1, 3];
252/// assert_eq!(cmp_vec, vec);
253/// ```
254pub fn bit_reverse_permutation<T>(a: &mut [T]) {
255    let n = a.len();
256    let log_n = n.trailing_zeros() as usize;
257
258    for i in 0..n {
259        let rev_i = bit_reverse(i, log_n);
260        if i < rev_i {
261            a.swap(i, rev_i);
262        }
263    }
264}
265
266#[cfg(test)]
267mod test_eval_index {
268    use super::evaluate_index;
269    use crate::integer::Z;
270
271    /// Tests that negative indices are not accepted
272    #[test]
273    fn is_err_negative() {
274        assert!(evaluate_index(i32::MIN).is_err());
275    }
276
277    /// Tests that the function can be called with several types
278    #[test]
279    fn is_ok_several_types() {
280        assert!(evaluate_index(i8::MAX).is_ok());
281        assert!(evaluate_index(i16::MAX).is_ok());
282        assert!(evaluate_index(i32::MAX).is_ok());
283        assert!(evaluate_index(i64::MAX).is_ok());
284        assert!(evaluate_index(u8::MAX).is_ok());
285        assert!(evaluate_index(u16::MAX).is_ok());
286        assert!(evaluate_index(u32::MAX).is_ok());
287
288        assert!(evaluate_index(Z::from(10)).is_ok());
289    }
290
291    /// Ensure that integers which can not be converted to an [`i64`]
292    /// are not accepted
293    #[test]
294    fn does_not_fit() {
295        assert!(evaluate_index(u64::MAX).is_err());
296    }
297}
298
299#[cfg(test)]
300mod test_eval_index_for_vector {
301    use super::evaluate_index_for_vector;
302
303    /// Test that negative addressing works.
304    #[test]
305    fn small_negative() {
306        let a = evaluate_index_for_vector(-1, 10).expect("No error with small negative index.");
307
308        assert_eq!(a, 9);
309    }
310
311    /// Assert that an error is returned if the index is just out of bounds.
312    #[test]
313    fn negative_out_of_bounds() {
314        assert!(evaluate_index_for_vector(-4, 3).is_err());
315        assert!(evaluate_index_for_vector(3, 3).is_err());
316    }
317
318    /// Tests that the function can be called with several types.
319    #[test]
320    fn is_ok_several_types() {
321        assert!(evaluate_index_for_vector(3i8, 4).is_ok());
322        assert!(evaluate_index_for_vector(3i16, 4).is_ok());
323        assert!(evaluate_index_for_vector(3i32, 4).is_ok());
324        assert!(evaluate_index_for_vector(3i64, 4).is_ok());
325        assert!(evaluate_index_for_vector(3u8, 4).is_ok());
326        assert!(evaluate_index_for_vector(3u16, 4).is_ok());
327        assert!(evaluate_index_for_vector(3u32, 4).is_ok());
328        assert!(evaluate_index_for_vector(3u64, 4).is_ok());
329    }
330
331    /// Ensure that integers which can not be converted to an [`i64`]
332    /// are not accepted
333    #[test]
334    fn does_not_fit() {
335        assert!(evaluate_index_for_vector(u64::MAX - 1, i64::MAX).is_err());
336    }
337}
338
339#[cfg(test)]
340mod test_eval_indices {
341    use super::evaluate_indices_for_matrix;
342    use crate::integer::MatZ;
343
344    /// Test that negative addressing works.
345    #[test]
346    fn small_negative() {
347        let matrix = MatZ::new(10, 10);
348
349        let (a, b) = evaluate_indices_for_matrix(&matrix, -1, -10)
350            .expect("No error with small negative index.");
351
352        assert_eq!(a, 9);
353        assert_eq!(b, 0);
354    }
355
356    /// Assert that an error is returned if either the row or column
357    /// are just out of bounds.
358    #[test]
359    fn negative_out_of_bounds() {
360        let matrix = MatZ::new(1, 1);
361
362        assert!(evaluate_indices_for_matrix(&matrix, 0, -2).is_err());
363        assert!(evaluate_indices_for_matrix(&matrix, -2, 0).is_err());
364        assert!(evaluate_indices_for_matrix(&matrix, -2, -2).is_err());
365    }
366
367    /// Tests that the function can be called with several types.
368    #[test]
369    fn is_ok_several_types() {
370        let matrix = MatZ::new(i16::MAX, u8::MAX);
371
372        assert!(evaluate_indices_for_matrix(&matrix, 3i8, 0).is_ok());
373        assert!(evaluate_indices_for_matrix(&matrix, 3i16, 0).is_ok());
374        assert!(evaluate_indices_for_matrix(&matrix, 3i32, 0).is_ok());
375        assert!(evaluate_indices_for_matrix(&matrix, 3i64, 0).is_ok());
376        assert!(evaluate_indices_for_matrix(&matrix, 3u8, 0).is_ok());
377        assert!(evaluate_indices_for_matrix(&matrix, 3u16, 0).is_ok());
378        assert!(evaluate_indices_for_matrix(&matrix, 3u32, 0).is_ok());
379        assert!(evaluate_indices_for_matrix(&matrix, 3u64, 0).is_ok());
380
381        assert!(evaluate_indices_for_matrix(&matrix, 0, 3i8).is_ok());
382        assert!(evaluate_indices_for_matrix(&matrix, 0, 3i16).is_ok());
383        assert!(evaluate_indices_for_matrix(&matrix, 0, 3i32).is_ok());
384        assert!(evaluate_indices_for_matrix(&matrix, 0, 3i64).is_ok());
385        assert!(evaluate_indices_for_matrix(&matrix, 0, 3u8).is_ok());
386        assert!(evaluate_indices_for_matrix(&matrix, 0, 3u16).is_ok());
387        assert!(evaluate_indices_for_matrix(&matrix, 0, 3u32).is_ok());
388        assert!(evaluate_indices_for_matrix(&matrix, 0, 3u64).is_ok());
389    }
390
391    /// Ensure that integers which can not be converted to an [`i64`]
392    /// are not accepted
393    #[test]
394    fn does_not_fit() {
395        let matrix = MatZ::new(3, 3);
396
397        assert!(evaluate_indices_for_matrix(&matrix, u64::MAX, 0).is_err());
398        assert!(evaluate_indices_for_matrix(&matrix, 0, u64::MAX).is_err());
399    }
400}
401
402#[cfg(test)]
403mod test_bit_reversed_order {
404    use super::bit_reverse_permutation;
405
406    /// ensure that the order is as expected in bit-reverse
407    #[test]
408    fn correct_new_order() {
409        let mut vec: Vec<i64> = (0..16).collect();
410        bit_reverse_permutation(&mut vec);
411        let cmp_vec = vec![0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15];
412        assert_eq!(cmp_vec, vec);
413    }
414
415    /// ensure that the function is self-inverse
416    #[test]
417    fn self_inverse() {
418        let vec: Vec<usize> = (0..12332).collect();
419        let mut vec_perm = vec.clone();
420        bit_reverse_permutation(&mut vec_perm);
421        bit_reverse_permutation(&mut vec_perm);
422        assert_eq!(vec, vec_perm);
423    }
424}
qfall_math/utils/index.rs

qfall_math/utils/
index.rs
