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> flatten(const sass::vector<T> & all)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> flattenInner(const sass::vector<T> & vec)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> hasAny(const T & cnt,U fn,Args...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> hasSubAny(const T & cnt,size_t len,U fn,Args...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> lcsIdentityCmp(const T & X,const T & Y,T & result)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> lcs(const sass::vector<T> & X,const sass::vector<T> & Y,bool (* select)(const T &,const T &,T &)=lcsIdentityCmp<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