1#ifndef SASS_DART_HELPERS_H
2#define SASS_DART_HELPERS_H
3
4#include <vector>
5#include <utility>
6#include <iterator>
7#include <functional>
8
9namespace Sass {
10
11 // ##########################################################################
12 // Flatten `vector<vector<T>>` to `vector<T>`
13 // ##########################################################################
14 template <class T>
15 T flatten(const sass::vector<T>& all)
16 {
17 T flattened;
18 for (const auto& sub : all) {
19 std::copy(std::begin(sub), std::end(sub),
20 std::back_inserter(flattened));
21 }
22 return flattened;
23 }
24
25 // ##########################################################################
26 // Expands each element of this Iterable into zero or more elements.
27 // Calls a function on every element and ads all results to flat array
28 // ##########################################################################
29 // Equivalent to dart `cnt.any`
30 // Pass additional closure variables to `fn`
31 template <class T, class U, typename ...Args>
32 T expand(const T& cnt, U fn, Args... args) {
33 T flattened;
34 for (const auto& sub : cnt) {
35 auto rv = fn(sub, args...);
36 flattened.insert(flattened.end(),
37 rv.begin(), rv.end());
38 }
39 return flattened;
40 }
41
42 // ##########################################################################
43 // ##########################################################################
44 template <class T>
45 T flattenInner(const sass::vector<T>& vec)
46 {
47 T outer;
48 for (const auto& sub : vec) {
49 outer.emplace_back(std::move(flatten(sub)));
50 }
51 return outer;
52 }
53 // EO flattenInner
54
55 // ##########################################################################
56 // Equivalent to dart `cnt.any`
57 // Pass additional closure variables to `fn`
58 // ##########################################################################
59 template <class T, class U, typename ...Args>
60 bool hasAny(const T& cnt, U fn, Args... args) {
61 for (const auto& sub : cnt) {
62 if (fn(sub, args...)) {
63 return true;
64 }
65 }
66 return false;
67 }
68 // EO hasAny
69
70 // ##########################################################################
71 // Equivalent to dart `cnt.take(len).any`
72 // Pass additional closure variables to `fn`
73 // ##########################################################################
74 template <class T, class U, typename ...Args>
75 bool hasSubAny(const T& cnt, size_t len, U fn, Args... args) {
76 for (size_t i = 0; i < len; i++) {
77 if (fn(cnt[i], args...)) {
78 return true;
79 }
80 }
81 return false;
82 }
83
84 // ##########################################################################
85 // Default predicate for lcs algorithm
86 // ##########################################################################
87 template <class T>
88 inline bool lcsIdentityCmp(const T& X, const T& Y, T& result)
89 {
90 // Assert equality
91 if (!ObjEqualityFn(X, Y)) {
92 return false;
93 }
94 // Store in reference
95 result = X;
96 // Return success
97 return true;
98 }
99 // EO lcsIdentityCmp
100
101 // ##########################################################################
102 // Longest common subsequence with predicate
103 // ##########################################################################
104 template <class T>
105 sass::vector<T> lcs(
106 const sass::vector<T>& X, const sass::vector<T>& Y,
107 bool(*select)(const T&, const T&, T&) = lcsIdentityCmp<T>)
108 {
109
110 std::size_t m = X.size(), mm = X.size() + 1;
111 std::size_t n = Y.size(), nn = Y.size() + 1;
112
113 if (m == 0) return {};
114 if (n == 0) return {};
115
116 // MSVC does not support variable-length arrays
117 // To circumvent, allocate one array on the heap
118 // Then use a macro to access via double index
119 // e.g. `size_t L[m][n]` is supported by gcc
120 size_t* len = new size_t[mm * nn + 1];
121 bool* acc = new bool[mm * nn + 1];
122 T* res = new T[mm * nn + 1];
123
124 #define LEN(x, y) len[(x) * nn + (y)]
125 #define ACC(x, y) acc[(x) * nn + (y)]
126 #define RES(x, y) res[(x) * nn + (y)]
127
128 /* Following steps build L[m+1][n+1] in bottom up fashion. Note
129 that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
130 for (size_t i = 0; i <= m; i++) {
131 for (size_t j = 0; j <= n; j++) {
132 if (i == 0 || j == 0)
133 LEN(i, j) = 0;
134 else {
135 ACC(i - 1, j - 1) = select(X[i - 1], Y[j - 1], RES(i - 1, j - 1));
136 if (ACC(i - 1, j - 1))
137 LEN(i, j) = LEN(i - 1, j - 1) + 1;
138 else
139 LEN(i, j) = std::max(LEN(i - 1, j), LEN(i, j - 1));
140 }
141 }
142 }
143
144 // Following code is used to print LCS
145 sass::vector<T> lcs;
146 std::size_t index = LEN(m, n);
147 lcs.reserve(index);
148
149 // Start from the right-most-bottom-most corner
150 // and one by one store objects in lcs[]
151 std::size_t i = m, j = n;
152 while (i > 0 && j > 0) {
153
154 // If current objects in X[] and Y are same,
155 // then current object is part of LCS
156 if (ACC(i - 1, j - 1))
157 {
158 // Put the stored object in result
159 // Note: we push instead of unshift
160 // Note: reverse the vector later
161 // ToDo: is deque more performant?
162 lcs.push_back(RES(i - 1, j - 1));
163 // reduce values of i, j and index
164 i -= 1; j -= 1; index -= 1;
165 }
166
167 // If not same, then find the larger of two and
168 // go in the direction of larger value
169 else if (LEN(i - 1, j) > LEN(i, j - 1)) {
170 i--;
171 }
172 else {
173 j--;
174 }
175
176 }
177
178 // reverse now as we used push_back
179 std::reverse(lcs.begin(), lcs.end());
180
181 // Delete temp memory on heap
182 delete[] len;
183 delete[] acc;
184 delete[] res;
185
186 #undef LEN
187 #undef ACC
188 #undef RES
189
190 return lcs;
191 }
192 // EO lcs
193
194 // ##########################################################################
195 // ##########################################################################
196
197}
198
199#endif
200

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