11#ifndef EIGEN_SPARSE_PERMUTATION_H
12#define EIGEN_SPARSE_PERMUTATION_H
17#include "./InternalHeaderCheck.h"
23template <
typename ExpressionType,
typename PlainObjectType,
24 bool NeedEval = !std::is_same<ExpressionType, PlainObjectType>::value>
26 XprHelper(
const ExpressionType& xpr) : m_xpr(xpr) {}
27 inline const PlainObjectType& xpr()
const {
return m_xpr; }
29 const PlainObjectType m_xpr;
31template <
typename ExpressionType,
typename PlainObjectType>
32struct XprHelper<ExpressionType, PlainObjectType, false> {
33 XprHelper(
const ExpressionType& xpr) : m_xpr(xpr) {}
34 inline const PlainObjectType& xpr()
const {
return m_xpr; }
36 const PlainObjectType& m_xpr;
39template <
typename PermDerived,
bool NeedInverseEval>
41 using IndicesType =
typename PermDerived::IndicesType;
42 using PermutationIndex =
typename IndicesType::Scalar;
43 using type = PermutationMatrix<IndicesType::SizeAtCompileTime, IndicesType::MaxSizeAtCompileTime, PermutationIndex>;
44 PermHelper(
const PermDerived& perm) : m_perm(perm.inverse()) {}
45 inline const type& perm()
const {
return m_perm; }
49template <
typename PermDerived>
50struct PermHelper<PermDerived, false> {
51 using type = PermDerived;
52 PermHelper(
const PermDerived& perm) : m_perm(perm) {}
53 inline const type& perm()
const {
return m_perm; }
58template <
typename ExpressionType,
int S
ide,
bool Transposed>
59struct permutation_matrix_product<ExpressionType, Side, Transposed, SparseShape> {
60 using MatrixType =
typename nested_eval<ExpressionType, 1>::type;
61 using MatrixTypeCleaned = remove_all_t<MatrixType>;
63 using Scalar =
typename MatrixTypeCleaned::Scalar;
64 using StorageIndex =
typename MatrixTypeCleaned::StorageIndex;
67 using ReturnType = SparseMatrix<Scalar, MatrixTypeCleaned::IsRowMajor ? RowMajor : ColMajor, StorageIndex>;
68 using TmpHelper = XprHelper<ExpressionType, ReturnType>;
72 static constexpr bool NeedOuterPermutation = ReturnType::IsRowMajor ? Side ==
OnTheLeft : Side ==
OnTheRight;
73 static constexpr bool NeedInversePermutation = Transposed ? Side ==
OnTheLeft : Side ==
OnTheRight;
75 template <
typename Dest,
typename PermutationType>
76 static inline void permute_outer(Dest& dst,
const PermutationType& perm,
const ExpressionType& xpr) {
80 const TmpHelper tmpHelper(xpr);
81 const ReturnType& tmp = tmpHelper.xpr();
83 ReturnType result(tmp.rows(), tmp.cols());
85 for (Index j = 0; j < tmp.outerSize(); j++) {
86 Index jp = perm.indices().coeff(j);
87 Index jsrc = NeedInversePermutation ? jp : j;
88 Index jdst = NeedInversePermutation ? j : jp;
89 Index begin = tmp.outerIndexPtr()[jsrc];
90 Index end = tmp.isCompressed() ? tmp.outerIndexPtr()[jsrc + 1] : begin + tmp.innerNonZeroPtr()[jsrc];
91 result.outerIndexPtr()[jdst + 1] += end - begin;
94 std::partial_sum(result.outerIndexPtr(), result.outerIndexPtr() + result.outerSize() + 1, result.outerIndexPtr());
95 result.resizeNonZeros(result.nonZeros());
97 for (Index j = 0; j < tmp.outerSize(); j++) {
98 Index jp = perm.indices().coeff(j);
99 Index jsrc = NeedInversePermutation ? jp : j;
100 Index jdst = NeedInversePermutation ? j : jp;
101 Index begin = tmp.outerIndexPtr()[jsrc];
102 Index end = tmp.isCompressed() ? tmp.outerIndexPtr()[jsrc + 1] : begin + tmp.innerNonZeroPtr()[jsrc];
103 Index target = result.outerIndexPtr()[jdst];
104 smart_copy(tmp.innerIndexPtr() + begin, tmp.innerIndexPtr() + end, result.innerIndexPtr() + target);
105 smart_copy(tmp.valuePtr() + begin, tmp.valuePtr() + end, result.valuePtr() + target);
107 dst = std::move(result);
110 template <
typename Dest,
typename PermutationType>
111 static inline void permute_inner(Dest& dst,
const PermutationType& perm,
const ExpressionType& xpr) {
112 using InnerPermHelper = PermHelper<PermutationType, NeedInversePermutation>;
113 using InnerPermType =
typename InnerPermHelper::type;
118 const TmpHelper tmpHelper(xpr);
119 const ReturnType& tmp = tmpHelper.xpr();
123 const InnerPermHelper permHelper(perm);
124 const InnerPermType& innerPerm = permHelper.perm();
126 ReturnType result(tmp.rows(), tmp.cols());
128 for (Index j = 0; j < tmp.outerSize(); j++) {
129 Index begin = tmp.outerIndexPtr()[j];
130 Index end = tmp.isCompressed() ? tmp.outerIndexPtr()[j + 1] : begin + tmp.innerNonZeroPtr()[j];
131 result.outerIndexPtr()[j + 1] += end - begin;
134 std::partial_sum(result.outerIndexPtr(), result.outerIndexPtr() + result.outerSize() + 1, result.outerIndexPtr());
135 result.resizeNonZeros(result.nonZeros());
137 for (Index j = 0; j < tmp.outerSize(); j++) {
138 Index begin = tmp.outerIndexPtr()[j];
139 Index end = tmp.isCompressed() ? tmp.outerIndexPtr()[j + 1] : begin + tmp.innerNonZeroPtr()[j];
140 Index target = result.outerIndexPtr()[j];
141 std::transform(tmp.innerIndexPtr() + begin, tmp.innerIndexPtr() + end, result.innerIndexPtr() + target,
142 [&innerPerm](StorageIndex i) { return innerPerm.indices().coeff(i); });
143 smart_copy(tmp.valuePtr() + begin, tmp.valuePtr() + end, result.valuePtr() + target);
146 result.sortInnerIndices();
147 dst = std::move(result);
150 template <
typename Dest,
typename PermutationType,
bool DoOuter = NeedOuterPermutation,
151 std::enable_if_t<DoOuter, int> = 0>
152 static inline void run(Dest& dst,
const PermutationType& perm,
const ExpressionType& xpr) {
153 permute_outer(dst, perm, xpr);
156 template <
typename Dest,
typename PermutationType,
bool DoOuter = NeedOuterPermutation,
157 std::enable_if_t<!DoOuter, int> = 0>
158 static inline void run(Dest& dst,
const PermutationType& perm,
const ExpressionType& xpr) {
159 permute_inner(dst, perm, xpr);
167template <
int ProductTag>
168struct product_promote_storage_type<Sparse, PermutationStorage, ProductTag> {
171template <
int ProductTag>
172struct product_promote_storage_type<PermutationStorage, Sparse, ProductTag> {
180template <
typename Lhs,
typename Rhs,
int ProductTag>
181struct product_evaluator<Product<Lhs, Rhs, AliasFreeProduct>, ProductTag, PermutationShape, SparseShape>
182 :
public evaluator<typename permutation_matrix_product<Rhs, OnTheLeft, false, SparseShape>::ReturnType> {
183 using XprType = Product<Lhs, Rhs, AliasFreeProduct>;
184 using PlainObject =
typename permutation_matrix_product<Rhs, OnTheLeft, false, SparseShape>::ReturnType;
185 using Base = evaluator<PlainObject>;
189 explicit product_evaluator(
const XprType& xpr) : m_result(xpr.rows(), xpr.cols()) {
190 internal::construct_at<Base>(
this, m_result);
191 generic_product_impl<Lhs, Rhs, PermutationShape, SparseShape, ProductTag>::evalTo(m_result, xpr.lhs(), xpr.rhs());
195 PlainObject m_result;
198template <
typename Lhs,
typename Rhs,
int ProductTag>
199struct product_evaluator<Product<Lhs, Rhs, AliasFreeProduct>, ProductTag, SparseShape, PermutationShape>
200 :
public evaluator<typename permutation_matrix_product<Lhs, OnTheRight, false, SparseShape>::ReturnType> {
201 using XprType = Product<Lhs, Rhs, AliasFreeProduct>;
202 using PlainObject =
typename permutation_matrix_product<Lhs, OnTheRight, false, SparseShape>::ReturnType;
203 using Base = evaluator<PlainObject>;
207 explicit product_evaluator(
const XprType& xpr) : m_result(xpr.rows(), xpr.cols()) {
208 ::new (
static_cast<Base*
>(
this)) Base(m_result);
209 generic_product_impl<Lhs, Rhs, SparseShape, PermutationShape, ProductTag>::evalTo(m_result, xpr.lhs(), xpr.rhs());
213 PlainObject m_result;
220template <typename SparseDerived, typename PermDerived>
221inline const Product<SparseDerived, PermDerived, AliasFreeProduct> operator*(
222 const SparseMatrixBase<SparseDerived>& matrix, const PermutationBase<PermDerived>& perm) {
223 return Product<SparseDerived, PermDerived, AliasFreeProduct>(matrix.derived(), perm.derived());
228template <
typename SparseDerived,
typename PermDerived>
229inline const Product<PermDerived, SparseDerived, AliasFreeProduct> operator*(
230 const PermutationBase<PermDerived>& perm,
const SparseMatrixBase<SparseDerived>& matrix) {
231 return Product<PermDerived, SparseDerived, AliasFreeProduct>(perm.derived(), matrix.derived());
236template <
typename SparseDerived,
typename PermutationType>
237inline const Product<SparseDerived, Inverse<PermutationType>, AliasFreeProduct> operator*(
238 const SparseMatrixBase<SparseDerived>& matrix,
const InverseImpl<PermutationType, PermutationStorage>& tperm) {
239 return Product<SparseDerived, Inverse<PermutationType>, AliasFreeProduct>(matrix.derived(), tperm.derived());
244template <
typename SparseDerived,
typename PermutationType>
245inline const Product<Inverse<PermutationType>, SparseDerived, AliasFreeProduct> operator*(
246 const InverseImpl<PermutationType, PermutationStorage>& tperm,
const SparseMatrixBase<SparseDerived>& matrix) {
247 return Product<Inverse<PermutationType>, SparseDerived, AliasFreeProduct>(tperm.derived(), matrix.derived());
@ OnTheLeft
Definition Constants.h:332
@ OnTheRight
Definition Constants.h:334
constexpr unsigned int EvalBeforeNestingBit
Definition Constants.h:75