1 #if !defined HAVE_PERMAPPLYFUNC_H__
2 #define HAVE_PERMAPPLYFUNC_H__
3 // This file is part of the FXT library.
4 // Copyright (C) 2010, 2018 Joerg Arndt
5 // License: GNU General Public License version 3 or later,
6 // see the file COPYING.txt in the main directory.
7
8
9 #include "fxttypes.h"
10 #include "ds/bitarray.h"
11 #include "restrict.h"
12
13
14
15 template <typename Type>
apply_permutation(ulong (* x)(ulong),const Type * f,Type * restrict g,ulong n)16 void apply_permutation(ulong (*x)(ulong), const Type *f, Type * restrict g, ulong n)
17 // Set g[x(k)] <-- f[k] for all k
18 // Must have: 0<=x(k)<n for all k
19 //
20 // Example: The following two lines result in identical g[]:
21 // apply_permutation(gray_code, f, g, n);
22 // gray_permute(f, g, n);
23 {
24 for (ulong k=0; k<n; ++k) g[x(k)] = f[k];
25 }
26 // -------------------------
27
28
29 template <typename Type>
30 void apply_permutation(ulong (*x)(ulong), Type * restrict f, ulong n, bitarray *bp=nullptr)
31 // Set f[x(k)] <-- f[k] for all k
32 // Must have: 0<=x(k)<n for all k
33 // In-place version.
34 {
35 bitarray *tp = bp;
36 if ( nullptr==bp ) tp = new bitarray(n); // tags
37 tp->clear_all();
38
39 for (ulong k=0; k<n; ++k)
40 {
41 if ( tp->test_clear(k) ) continue; // already processed
42 tp->set(k);
43
44 // --- do cycle: ---
45 ulong i = k; // start of cycle
46 Type t = f[i];
47 ulong g = x(i);
48 while ( 0==(tp->test_set(g)) ) // cf. gray_permute()
49 {
50 Type tt = f[g];
51 f[g] = t;
52 t = tt;
53 g = x(g);
54 }
55 f[g] = t;
56 // --- end (do cycle) ---
57 }
58
59 if ( nullptr==bp ) delete tp;
60 }
61 // -------------------------
62
63
64 template <typename Type>
apply_inverse_permutation(ulong (* x)(ulong),const Type * f,Type * restrict g,ulong n)65 void apply_inverse_permutation(ulong (*x)(ulong), const Type *f, Type * restrict g, ulong n)
66 // Set g[k] <-- f[x(k)] for all k
67 // Must have: 0<=x(k)<n for all k, and x(i)!=x(j) for all i!=j
68 {
69 for (ulong k=0; k<n; ++k) g[k] = f[x(k)];
70 }
71 // -------------------------
72
73
74 template <typename Type>
75 void apply_inverse_permutation(ulong (*x)(ulong), Type *f, ulong n, bitarray *bp=nullptr)
76 // Set f[k] <-- f[x(k)] for all k
77 // Must have: 0<=x(k)<n for all k, and x(i)!=x(j) for all i!=j
78 // In-place version.
79 {
80 bitarray *tp = bp;
81 if ( nullptr==bp ) tp = new bitarray(n); // tags
82 tp->clear_all();
83
84 for (ulong k=0; k<n; ++k)
85 {
86 if ( tp->test_clear(k) ) continue; // already processed
87 tp->set(k);
88
89 // --- do cycle: ---
90 ulong i = k; // start of cycle
91 Type t = f[i];
92 ulong g = x(i);
93 while ( 0==(tp->test_set(g)) ) // cf. inverse_gray_permute()
94 {
95 f[i] = f[g];
96 i = g;
97 g = x(i);
98 }
99 f[i] = t;
100 // --- end (do cycle) ---
101 }
102
103 if ( nullptr==bp ) delete tp;
104 }
105 // -------------------------
106
107
108
109
110 #endif // !defined HAVE_PERMAPPLYFUNC_H__
111