MVE - Multi-View Environment mve-devel
Loading...
Searching...
No Matches
permute.h
Go to the documentation of this file.
1/*
2 * Copyright (C) 2015, Simon Fuhrmann
3 * TU Darmstadt - Graphics, Capture and Massively Parallel Computing
4 * All rights reserved.
5 *
6 * This software may be modified and distributed under the terms
7 * of the BSD 3-Clause license. See the LICENSE.txt file for details.
8 */
9
10#ifndef MATH_PERMUTE_HEADER
11#define MATH_PERMUTE_HEADER
12
13#include <vector>
14#include <stdexcept>
15
16#include "math/defines.h"
17
20
35template <class V, class P>
36void
37permute_reloc (std::vector<V>& v, std::vector<P> const& p);
38
51template <class V, class P>
52void
53permute_math (std::vector<V>& v, std::vector<P> const& p);
54
55/* --------------------------- Implementation --------------------- */
56
57template <class V, class P>
58void
59permute_reloc (std::vector<V>& v, std::vector<P> const& p)
60{
61 if (v.size() != p.size())
62 throw std::invalid_argument("Vector length does not match");
63
64 if (v.empty())
65 return;
66
67 std::vector<bool> visited(v.size(), false);
68 std::size_t i = 0;
69 std::size_t seek = 0;
70
71 do
72 {
73 /* Permute a cycle using index-based relocation permutation. */
74 V tmp[2];
75 bool idx = false;
76 tmp[idx] = v[i];
77 while (!visited[i])
78 {
79 tmp[!idx] = v[p[i]];
80 v[p[i]] = tmp[idx];
81 idx = !idx;
82 visited[i] = true;
83 i = p[i];
84 }
85
86 /* Seek for an unvisited element. */
88 for (; seek < visited.size(); ++seek)
89 if (!visited[seek])
90 {
91 i = seek;
92 break;
93 }
94 }
95 while (i != MATH_MAX_SIZE_T);
96}
97
98/* ---------------------------------------------------------------- */
99
100template <class V, class P>
101void
102permute_math (std::vector<V>& v, std::vector<P> const& p)
103{
104 if (v.size() != p.size())
105 throw std::invalid_argument("Vector length does not match");
106
107 if (v.empty())
108 return;
109
110 std::vector<bool> visited(v.size(), false);
111 std::size_t i = 0;
112 std::size_t seek = 0;
113 do
114 {
115 /* Permute a cycle using mathematical permutation. */
116 visited[i] = true;
117 if (i != p[i])
118 {
119 V tmp = v[i];
120 while (!visited[p[i]])
121 {
122 v[i] = v[p[i]];
123 visited[p[i]] = true;
124 i = p[i];
125 }
126 v[i] = tmp;
127 }
128
129 /* Seek for an unvisited element. */
130 i = MATH_MAX_SIZE_T;
131 for (; seek < visited.size(); ++seek)
132 if (!visited[seek])
133 {
134 i = seek;
135 break;
136 }
137 }
138 while (i != MATH_MAX_SIZE_T);
139}
140
143
144#endif /* MATH_PERMUTE_HEADER */
#define MATH_NAMESPACE_BEGIN
Definition defines.h:15
#define MATH_NAMESPACE_END
Definition defines.h:16
#define MATH_MAX_SIZE_T
Definition defines.h:110
#define MATH_ALGO_NAMESPACE_BEGIN
Definition defines.h:18
#define MATH_ALGO_NAMESPACE_END
Definition defines.h:19
void permute_reloc(std::vector< V > &v, std::vector< P > const &p)
This function permutes a vector of elements v using a permutation given by vector p,...
Definition permute.h:59
void permute_math(std::vector< V > &v, std::vector< P > const &p)
This function permutes a vector of elements v using a permutation given by vector p,...
Definition permute.h:102