1 | #ifndef SASS_PATHS_H |
2 | #define SASS_PATHS_H |
3 | |
4 | #include <vector> |
5 | |
6 | namespace 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 | |