1#ifndef SASS_PATHS_H
2#define SASS_PATHS_H
3
4#include <vector>
5
6namespace Sass {
7
8 // Returns a list of all possible paths through the given lists.
9 //
10 // For example, given `[[1, 2], [3, 4], [5, 6]]`, this returns:
11 //
12 // ```
13 // [[1, 3, 5],
14 // [2, 3, 5],
15 // [1, 4, 5],
16 // [2, 4, 5],
17 // [1, 3, 6],
18 // [2, 3, 6],
19 // [1, 4, 6],
20 // [2, 4, 6]]
21 // ```
22 //
23 // Note: called `paths` in dart-sass
24 template <class T>
25 sass::vector<sass::vector<T>> permutate(
26 const sass::vector<sass::vector<T>>& in)
27 {
28
29 size_t L = in.size(), n = 0;
30
31 if (L == 0) return {};
32 // Exit early if any entry is empty
33 for (size_t i = 0; i < L; i += 1) {
34 if (in[i].size() == 0) return {};
35 }
36
37 size_t* state = new size_t[L + 1];
38 sass::vector<sass::vector<T>> out;
39
40 // First initialize all states for every permutation group
41 for (size_t i = 0; i < L; i += 1) {
42 state[i] = in[i].size() - 1;
43 }
44 while (true) {
45 sass::vector<T> perm;
46 // Create one permutation for state
47 for (size_t i = 0; i < L; i += 1) {
48 perm.push_back(in.at(i).at(in[i].size() - state[i] - 1));
49 }
50 // Current group finished
51 if (state[n] == 0) {
52 // Find position of next decrement
53 while (n < L && state[++n] == 0) {}
54
55 if (n == L) {
56 out.push_back(perm);
57 break;
58 }
59
60 state[n] -= 1;
61
62 for (size_t p = 0; p < n; p += 1) {
63 state[p] = in[p].size() - 1;
64 }
65
66 // Restart from front
67 n = 0;
68
69 }
70 else {
71 state[n] -= 1;
72 }
73 out.push_back(perm);
74 }
75
76 delete[] state;
77 return out;
78 }
79 // EO permutate
80
81 // ToDo: this variant is used in resolveParentSelectors
82 // Returns a list of all possible paths through the given lists.
83 //
84 // For example, given `[[1, 2], [3, 4], [5, 6]]`, this returns:
85 //
86 // ```
87 // [[1, 3, 5],
88 // [1, 3, 6],
89 // [1, 4, 5],
90 // [1, 4, 6],
91 // [2, 3, 5],
92 // [2, 3, 6],
93 // [2, 4, 5],
94 // [2, 4, 6]]
95 // ```
96 //
97 template <class T>
98 sass::vector<sass::vector<T>>
99 permutateAlt(const sass::vector<sass::vector<T>>& in) {
100
101 size_t L = in.size();
102 size_t n = in.size() - 1;
103
104 if (L == 0) return {};
105 // Exit early if any entry is empty
106 for (size_t i = 0; i < L; i += 1) {
107 if (in[i].size() == 0) return {};
108 }
109
110 size_t* state = new size_t[L];
111 sass::vector<sass::vector<T>> out;
112
113 // First initialize all states for every permutation group
114 for (size_t i = 0; i < L; i += 1) {
115 state[i] = in[i].size() - 1;
116 }
117
118 while (true) {
119 /*
120 // std::cerr << "PERM: ";
121 for (size_t p = 0; p < L; p++)
122 { // std::cerr << state[p] << " "; }
123 // std::cerr << "\n";
124 */
125 sass::vector<T> perm;
126 // Create one permutation for state
127 for (size_t i = 0; i < L; i += 1) {
128 perm.push_back(in.at(i).at(in[i].size() - state[i] - 1));
129 }
130 // Current group finished
131 if (state[n] == 0) {
132 // Find position of next decrement
133 while (n > 0 && state[--n] == 0) {}
134
135 // Check for end condition
136 if (state[n] != 0) {
137 // Decrease next on the left side
138 state[n] -= 1;
139 // Reset all counters to the right
140 for (size_t p = n + 1; p < L; p += 1) {
141 state[p] = in[p].size() - 1;
142 }
143 // Restart from end
144 n = L - 1;
145 }
146 else {
147 out.push_back(perm);
148 break;
149 }
150 }
151 else {
152 state[n] -= 1;
153 }
154 out.push_back(perm);
155 }
156
157 delete[] state;
158 return out;
159 }
160 // EO permutateAlt
161
162}
163
164#endif
165

source code of gtk/subprojects/libsass/src/permutate.hpp