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 | |
9 | namespace 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 | |