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

nalgebra/linalg/
permutation_sequence.rs
