nalgebra/linalg/
permutation_sequence.rs

1#[cfg(feature = "serde-serialize-no-std")]
2use serde::{Deserialize, Serialize};
3
4use num::One;
5use simba::scalar::ClosedNeg;
6
7use crate::allocator::Allocator;
8use crate::base::{DefaultAllocator, Matrix, OVector, Scalar};
9#[cfg(any(feature = "std", feature = "alloc"))]
10use crate::dimension::Dyn;
11use crate::dimension::{Const, Dim, DimName};
12use crate::storage::StorageMut;
13
14/// A sequence of row or column permutations.
15#[cfg_attr(feature = "serde-serialize-no-std", derive(Serialize, Deserialize))]
16#[cfg_attr(
17    feature = "serde-serialize-no-std",
18    serde(bound(serialize = "DefaultAllocator: Allocator<D>,
19         OVector<(usize, usize), D>: Serialize"))
20)]
21#[cfg_attr(
22    feature = "serde-serialize-no-std",
23    serde(bound(deserialize = "DefaultAllocator: Allocator<D>,
24         OVector<(usize, usize), D>: Deserialize<'de>"))
25)]
26#[cfg_attr(feature = "defmt", derive(defmt::Format))]
27#[derive(Clone, Debug)]
28pub struct PermutationSequence<D: Dim>
29where
30    DefaultAllocator: Allocator<D>,
31{
32    len: usize,
33    ipiv: OVector<(usize, usize), D>,
34}
35
36impl<D: Dim> Copy for PermutationSequence<D>
37where
38    DefaultAllocator: Allocator<D>,
39    OVector<(usize, usize), D>: Copy,
40{
41}
42
43impl<D: DimName> PermutationSequence<D>
44where
45    DefaultAllocator: Allocator<D>,
46{
47    /// Creates a new statically-allocated sequence of `D` identity permutations.
48    #[inline]
49    pub fn identity() -> Self {
50        Self::identity_generic(D::name())
51    }
52}
53
54#[cfg(any(feature = "std", feature = "alloc"))]
55impl PermutationSequence<Dyn>
56where
57    DefaultAllocator: Allocator<Dyn>,
58{
59    /// Creates a new dynamically-allocated sequence of `n` identity permutations.
60    #[inline]
61    pub fn identity(n: usize) -> Self {
62        Self::identity_generic(Dyn(n))
63    }
64}
65
66impl<D: Dim> PermutationSequence<D>
67where
68    DefaultAllocator: Allocator<D>,
69{
70    /// Creates a new sequence of D identity permutations.
71    #[inline]
72    pub fn identity_generic(dim: D) -> Self {
73        Self {
74            len: 0,
75            // TODO: using a uninitialized matrix would save some computation, but
76            //       that loos difficult to setup with MaybeUninit.
77            ipiv: Matrix::repeat_generic(dim, Const::<1>, (0, 0)),
78        }
79    }
80
81    /// Adds the interchange of the row (or column) `i` with the row (or column) `i2` to this
82    /// sequence of permutations.
83    #[inline]
84    pub fn append_permutation(&mut self, i: usize, i2: usize) {
85        if i != i2 {
86            assert!(
87                self.len < self.ipiv.len(),
88                "Maximum number of permutations exceeded."
89            );
90            self.ipiv[self.len] = (i, i2);
91            self.len += 1;
92        }
93    }
94
95    /// Applies this sequence of permutations to the rows of `rhs`.
96    #[inline]
97    pub fn permute_rows<T: Scalar, R2: Dim, C2: Dim, S2>(&self, rhs: &mut Matrix<T, R2, C2, S2>)
98    where
99        S2: StorageMut<T, R2, C2>,
100    {
101        for i in self.ipiv.rows_range(..self.len).iter() {
102            rhs.swap_rows(i.0, i.1)
103        }
104    }
105
106    /// Applies this sequence of permutations in reverse to the rows of `rhs`.
107    #[inline]
108    pub fn inv_permute_rows<T: Scalar, R2: Dim, C2: Dim, S2>(&self, rhs: &mut Matrix<T, R2, C2, S2>)
109    where
110        S2: StorageMut<T, R2, C2>,
111    {
112        for i in 0..self.len {
113            let (i1, i2) = self.ipiv[self.len - i - 1];
114            rhs.swap_rows(i1, i2)
115        }
116    }
117
118    /// Applies this sequence of permutations to the columns of `rhs`.
119    #[inline]
120    pub fn permute_columns<T: Scalar, R2: Dim, C2: Dim, S2>(&self, rhs: &mut Matrix<T, R2, C2, S2>)
121    where
122        S2: StorageMut<T, R2, C2>,
123    {
124        for i in self.ipiv.rows_range(..self.len).iter() {
125            rhs.swap_columns(i.0, i.1)
126        }
127    }
128
129    /// Applies this sequence of permutations in reverse to the columns of `rhs`.
130    #[inline]
131    pub fn inv_permute_columns<T: Scalar, R2: Dim, C2: Dim, S2>(
132        &self,
133        rhs: &mut Matrix<T, R2, C2, S2>,
134    ) where
135        S2: StorageMut<T, R2, C2>,
136    {
137        for i in 0..self.len {
138            let (i1, i2) = self.ipiv[self.len - i - 1];
139            rhs.swap_columns(i1, i2)
140        }
141    }
142
143    /// The number of non-identity permutations applied by this sequence.
144    #[must_use]
145    pub const fn len(&self) -> usize {
146        self.len
147    }
148
149    /// Returns true if the permutation sequence contains no elements.
150    #[must_use]
151    pub const fn is_empty(&self) -> bool {
152        self.len() == 0
153    }
154
155    /// The determinant of the matrix corresponding to this permutation.
156    #[inline]
157    #[must_use]
158    pub fn determinant<T: One + ClosedNeg>(&self) -> T {
159        if self.len % 2 == 0 {
160            T::one()
161        } else {
162            -T::one()
163        }
164    }
165}
nalgebra/linalg/permutation_sequence.rs

nalgebra/linalg/
permutation_sequence.rs
