Geogram  Version 1.9.1
A programming library of geometric algorithms
permutation.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2000-2022 Inria
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  *
8  * * Redistributions of source code must retain the above copyright notice,
9  * this list of conditions and the following disclaimer.
10  * * Redistributions in binary form must reproduce the above copyright notice,
11  * this list of conditions and the following disclaimer in the documentation
12  * and/or other materials provided with the distribution.
13  * * Neither the name of the ALICE Project-Team nor the names of its
14  * contributors may be used to endorse or promote products derived from this
15  * software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
21  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27  * POSSIBILITY OF SUCH DAMAGE.
28  *
29  * Contact: Bruno Levy
30  *
31  * https://www.inria.fr/fr/bruno-levy
32  *
33  * Inria,
34  * Domaine de Voluceau,
35  * 78150 Le Chesnay - Rocquencourt
36  * FRANCE
37  *
38  */
39 
40 #ifndef GEOGRAM_BASIC_PERMUTATION
41 #define GEOGRAM_BASIC_PERMUTATION
42 
43 #include <geogram/basic/common.h>
44 #include <geogram/basic/numeric.h>
45 #include <geogram/basic/memory.h>
46 
52 namespace GEO {
53 
57  namespace Permutation {
58 
70  inline bool is_valid(const vector<index_t>& permutation) {
71  std::vector<bool> visited(permutation.size(), false);
72  for(index_t i = 0; i < permutation.size(); i++) {
73  if(permutation[i] >= permutation.size()) {
74  return false;
75  }
76  if(visited[permutation[i]]) {
77  return false;
78  }
79  visited[permutation[i]] = true;
80  }
81  return true;
82  }
83 
95  inline void mark(
96  vector<index_t>& permutation,
97  index_t i
98  ) {
99  geo_debug_assert(i < permutation.size());
100  geo_debug_assert(signed_index_t(permutation[i]) >= 0);
101  permutation[i] = index_t(-signed_index_t(permutation[i]) - 1);
102  }
103 
110  inline bool is_marked(
111  const vector<index_t>& permutation,
112  index_t i
113  ) {
114  geo_debug_assert(i < permutation.size());
115  return signed_index_t(permutation[i]) < 0;
116  }
117 
126  inline void unmark(
127  vector<index_t>& permutation,
128  index_t i
129  ) {
130  geo_debug_assert(is_marked(permutation, i));
131  permutation[i] = index_t(-signed_index_t(permutation[i]) - 1);
132  }
133 
157  inline void apply(
158  void* data, const vector<index_t>& permutation_in,
159  index_t elemsize
160  ) {
161  Memory::pointer pdata = (Memory::pointer) (data);
162  vector<index_t>& permutation =
163  const_cast<vector<index_t>&>(permutation_in);
164  geo_debug_assert(is_valid(permutation));
165  Memory::byte* temp = static_cast<Memory::byte*>(alloca(elemsize));
166  for(index_t k = 0; k < permutation.size(); k++) {
167  if(is_marked(permutation, k)) {
168  continue;
169  }
170  index_t i = k;
171  index_t j = permutation[k];
172  Memory::copy(temp, pdata + i * elemsize, elemsize);
173  mark(permutation, k);
174  while(j != k) {
175  Memory::copy(
176  pdata + i * elemsize, pdata + j * elemsize, elemsize
177  );
178  index_t nj = permutation[j];
179  mark(permutation, j);
180  i = j;
181  j = nj;
182  }
183  Memory::copy(pdata + i * elemsize, temp, elemsize);
184  }
185  for(index_t k = 0; k < permutation.size(); k++) {
186  unmark(permutation, k);
187  }
188  }
189 
210  template <class T>
211  inline void apply(
212  vector<T>& data, const vector<index_t>& permutation_in
213  ) {
214  vector<index_t>& permutation =
215  const_cast<vector<index_t>&>(permutation_in);
216  geo_debug_assert(is_valid(permutation));
217  T temp;
218  for(index_t k = 0; k < permutation.size(); k++) {
219  if(is_marked(permutation, k)) {
220  continue;
221  }
222  index_t i = k;
223  temp = data[i];
224  index_t j = permutation[k];
225  mark(permutation, k);
226  while(j != k) {
227  data[i] = data[j];
228  index_t nj = permutation[j];
229  mark(permutation, j);
230  i = j;
231  j = nj;
232  }
233  data[i] = temp;
234  }
235  for(index_t k = 0; k < permutation.size(); k++) {
236  unmark(permutation, k);
237  }
238  }
239 
253  inline void invert(vector<index_t>& permutation) {
254  geo_debug_assert(is_valid(permutation));
255  for(index_t k = 0; k < permutation.size(); k++) {
256  if(is_marked(permutation, k)) {
257  continue;
258  }
259  index_t i = k;
260  index_t j = permutation[i];
261  while(j != k) {
262  index_t temp = permutation[j];
263  permutation[j] = i;
264  mark(permutation, j);
265  i = j;
266  j = temp;
267  }
268  permutation[j] = i;
269  mark(permutation, j);
270  }
271  for(index_t k = 0; k < permutation.size(); k++) {
272  unmark(permutation, k);
273  }
274  }
275 
285  inline void invert(
286  const vector<index_t>& permutation, vector<index_t>& invert
287  ) {
288  geo_debug_assert(is_valid(permutation));
289  invert.resize(permutation.size());
290  for(index_t i=0; i<permutation.size(); ++i) {
291  invert[permutation[i]] = i;
292  }
293  }
294 
295  }
296 }
297 
298 #endif
#define geo_debug_assert(x)
Verifies that a condition is met.
Definition: assert.h:196
index_t size() const
Gets the number of elements.
Definition: memory.h:674
Common include file, providing basic definitions. Should be included before anything else by all head...
Types and functions for memory manipulation.
unsigned char byte
Unsigned byte type.
Definition: memory.h:92
byte * pointer
Pointer to unsigned byte(s)
Definition: memory.h:104
void copy(void *to, const void *from, size_t size)
Copies a memory block.
Definition: memory.h:129
bool is_marked(const vector< index_t > &permutation, index_t i)
Checks if a permutation element has been visited.
Definition: permutation.h:110
void unmark(vector< index_t > &permutation, index_t i)
Unmarks a permutation element.
Definition: permutation.h:126
void mark(vector< index_t > &permutation, index_t i)
Marks a permutation element as visited.
Definition: permutation.h:95
void invert(vector< index_t > &permutation)
Inverts a permutation in-place.
Definition: permutation.h:253
void apply(void *data, const vector< index_t > &permutation_in, index_t elemsize)
Applies a permutation in-place. Permutes the first N elements of size elemsize in array data using pe...
Definition: permutation.h:157
bool is_valid(const vector< index_t > &permutation)
Checks whether a vector is a valid permutation.
Definition: permutation.h:70
Global Vorpaline namespace.
Definition: basic.h:55
geo_signed_index_t signed_index_t
The type for storing and manipulating indices differences.
Definition: numeric.h:343
geo_index_t index_t
The type for storing and manipulating indices.
Definition: numeric.h:329
Types and functions for numbers manipulation.