|
Packit Service |
7770af |
#ifndef SASS_SASS_UTIL_H
|
|
Packit Service |
7770af |
#define SASS_SASS_UTIL_H
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
#include "ast.hpp"
|
|
Packit Service |
7770af |
#include "node.hpp"
|
|
Packit Service |
7770af |
#include "debug.hpp"
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
namespace Sass {
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
/*
|
|
Packit Service |
7770af |
This is for ports of functions in the Sass:Util module.
|
|
Packit Service |
7770af |
*/
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
/*
|
|
Packit Service |
7770af |
# Return a Node collection of all possible paths through the given Node collection of Node collections.
|
|
Packit Service |
7770af |
#
|
|
Packit Service |
7770af |
# @param arrs [NodeCollection<NodeCollection<Node>>]
|
|
Packit Service |
7770af |
# @return [NodeCollection<NodeCollection<Node>>]
|
|
Packit Service |
7770af |
#
|
|
Packit Service |
7770af |
# @example
|
|
Packit Service |
7770af |
# paths([[1, 2], [3, 4], [5]]) #=>
|
|
Packit Service |
7770af |
# # [[1, 3, 5],
|
|
Packit Service |
7770af |
# # [2, 3, 5],
|
|
Packit Service |
7770af |
# # [1, 4, 5],
|
|
Packit Service |
7770af |
# # [2, 4, 5]]
|
|
Packit Service |
7770af |
*/
|
|
Packit Service |
7770af |
Node paths(const Node& arrs);
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
/*
|
|
Packit Service |
7770af |
This class is a default implementation of a Node comparator that can be passed to the lcs function below.
|
|
Packit Service |
7770af |
It uses operator== for equality comparision. It then returns one if the Nodes are equal.
|
|
Packit Service |
7770af |
*/
|
|
Packit Service |
7770af |
class DefaultLcsComparator {
|
|
Packit Service |
7770af |
public:
|
|
Packit Service |
7770af |
bool operator()(const Node& one, const Node& two, Node& out) const {
|
|
Packit Service |
7770af |
// TODO: Is this the correct C++ interpretation?
|
|
Packit Service |
7770af |
// block ||= proc {|a, b| a == b && a}
|
|
Packit Service |
7770af |
if (one == two) {
|
|
Packit Service |
7770af |
out = one;
|
|
Packit Service |
7770af |
return true;
|
|
Packit Service |
7770af |
}
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
return false;
|
|
Packit Service |
7770af |
}
|
|
Packit Service |
7770af |
};
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
typedef std::vector<std::vector<int> > LCSTable;
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
/*
|
|
Packit Service |
7770af |
This is the equivalent of ruby's Sass::Util.lcs_backtrace.
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
# Computes a single longest common subsequence for arrays x and y.
|
|
Packit Service |
7770af |
# Algorithm from http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Reading_out_an_LCS
|
|
Packit Service |
7770af |
*/
|
|
Packit Service |
7770af |
template<typename ComparatorType>
|
|
Packit Service |
7770af |
Node lcs_backtrace(const LCSTable& c, const Node& x, const Node& y, int i, int j, const ComparatorType& comparator) {
|
|
Packit Service |
7770af |
DEBUG_PRINTLN(LCS, "LCSBACK: X=" << x << " Y=" << y << " I=" << i << " J=" << j)
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
if (i == 0 || j == 0) {
|
|
Packit Service |
7770af |
DEBUG_PRINTLN(LCS, "RETURNING EMPTY")
|
|
Packit Service |
7770af |
return Node::createCollection();
|
|
Packit Service |
7770af |
}
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
NodeDeque& xChildren = *(x.collection());
|
|
Packit Service |
7770af |
NodeDeque& yChildren = *(y.collection());
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
Node compareOut = Node::createNil();
|
|
Packit Service |
7770af |
if (comparator(xChildren[i], yChildren[j], compareOut)) {
|
|
Packit Service |
7770af |
DEBUG_PRINTLN(LCS, "RETURNING AFTER ELEM COMPARE")
|
|
Packit Service |
7770af |
Node result = lcs_backtrace(c, x, y, i - 1, j - 1, comparator);
|
|
Packit Service |
7770af |
result.collection()->push_back(compareOut);
|
|
Packit Service |
7770af |
return result;
|
|
Packit Service |
7770af |
}
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
if (c[i][j - 1] > c[i - 1][j]) {
|
|
Packit Service |
7770af |
DEBUG_PRINTLN(LCS, "RETURNING AFTER TABLE COMPARE")
|
|
Packit Service |
7770af |
return lcs_backtrace(c, x, y, i, j - 1, comparator);
|
|
Packit Service |
7770af |
}
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
DEBUG_PRINTLN(LCS, "FINAL RETURN")
|
|
Packit Service |
7770af |
return lcs_backtrace(c, x, y, i - 1, j, comparator);
|
|
Packit Service |
7770af |
}
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
/*
|
|
Packit Service |
7770af |
This is the equivalent of ruby's Sass::Util.lcs_table.
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
# Calculates the memoization table for the Least Common Subsequence algorithm.
|
|
Packit Service |
7770af |
# Algorithm from http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Computing_the_length_of_the_LCS
|
|
Packit Service |
7770af |
*/
|
|
Packit Service |
7770af |
template<typename ComparatorType>
|
|
Packit Service |
7770af |
void lcs_table(const Node& x, const Node& y, const ComparatorType& comparator, LCSTable& out) {
|
|
Packit Service |
7770af |
DEBUG_PRINTLN(LCS, "LCSTABLE: X=" << x << " Y=" << y)
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
NodeDeque& xChildren = *(x.collection());
|
|
Packit Service |
7770af |
NodeDeque& yChildren = *(y.collection());
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
LCSTable c(xChildren.size(), std::vector<int>(yChildren.size()));
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
// These shouldn't be necessary since the vector will be initialized to 0 already.
|
|
Packit Service |
7770af |
// x.size.times {|i| c[i][0] = 0}
|
|
Packit Service |
7770af |
// y.size.times {|j| c[0][j] = 0}
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
for (size_t i = 1; i < xChildren.size(); i++) {
|
|
Packit Service |
7770af |
for (size_t j = 1; j < yChildren.size(); j++) {
|
|
Packit Service |
7770af |
Node compareOut = Node::createNil();
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
if (comparator(xChildren[i], yChildren[j], compareOut)) {
|
|
Packit Service |
7770af |
c[i][j] = c[i - 1][j - 1] + 1;
|
|
Packit Service |
7770af |
} else {
|
|
Packit Service |
7770af |
c[i][j] = std::max(c[i][j - 1], c[i - 1][j]);
|
|
Packit Service |
7770af |
}
|
|
Packit Service |
7770af |
}
|
|
Packit Service |
7770af |
}
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
out = c;
|
|
Packit Service |
7770af |
}
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
/*
|
|
Packit Service |
7770af |
This is the equivalent of ruby's Sass::Util.lcs.
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
# Computes a single longest common subsequence for `x` and `y`.
|
|
Packit Service |
7770af |
# If there are more than one longest common subsequences,
|
|
Packit Service |
7770af |
# the one returned is that which starts first in `x`.
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
# @param x [NodeCollection]
|
|
Packit Service |
7770af |
# @param y [NodeCollection]
|
|
Packit Service |
7770af |
# @comparator An equality check between elements of `x` and `y`.
|
|
Packit Service |
7770af |
# @return [NodeCollection] The LCS
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
|
|
Packit Service |
7770af |
*/
|
|
Packit Service |
7770af |
template<typename ComparatorType>
|
|
Packit Service |
7770af |
Node lcs(Node& x, Node& y, const ComparatorType& comparator) {
|
|
Packit Service |
7770af |
DEBUG_PRINTLN(LCS, "LCS: X=" << x << " Y=" << y)
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
Node newX = Node::createCollection();
|
|
Packit Service |
7770af |
newX.collection()->push_back(Node::createNil());
|
|
Packit Service |
7770af |
newX.plus(x);
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
Node newY = Node::createCollection();
|
|
Packit Service |
7770af |
newY.collection()->push_back(Node::createNil());
|
|
Packit Service |
7770af |
newY.plus(y);
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
LCSTable table;
|
|
Packit Service |
7770af |
lcs_table(newX, newY, comparator, table);
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
return lcs_backtrace(table, newX, newY, static_cast<int>(newX.collection()->size()) - 1, static_cast<int>(newY.collection()->size()) - 1, comparator);
|
|
Packit Service |
7770af |
}
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
/*
|
|
Packit Service |
7770af |
This is the equivalent of ruby sass' Sass::Util.flatten and [].flatten.
|
|
Packit Service |
7770af |
Sass::Util.flatten requires the number of levels to flatten, while
|
|
Packit Service |
7770af |
[].flatten doesn't and will flatten the entire array. This function
|
|
Packit Service |
7770af |
supports both.
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
# Flattens the first `n` nested arrays. If n == -1, all arrays will be flattened
|
|
Packit Service |
7770af |
#
|
|
Packit Service |
7770af |
# @param arr [NodeCollection] The array to flatten
|
|
Packit Service |
7770af |
# @param n [int] The number of levels to flatten
|
|
Packit Service |
7770af |
# @return [NodeCollection] The flattened array
|
|
Packit Service |
7770af |
*/
|
|
Packit Service |
7770af |
Node flatten(Node& arr, int n = -1);
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
/*
|
|
Packit Service |
7770af |
This is the equivalent of ruby's Sass::Util.group_by_to_a.
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
# Performs the equivalent of `enum.group_by.to_a`, but with a guaranteed
|
|
Packit Service |
7770af |
# order. Unlike [#hash_to_a], the resulting order isn't sorted key order;
|
|
Packit Service |
7770af |
# instead, it's the same order as `#group_by` has under Ruby 1.9 (key
|
|
Packit Service |
7770af |
# appearance order).
|
|
Packit Service |
7770af |
#
|
|
Packit Service |
7770af |
# @param enum [Enumerable]
|
|
Packit Service |
7770af |
# @return [Array<[Object, Array]>] An array of pairs.
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
TODO: update @param and @return once I know what those are.
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
The following is the modified version of the ruby code that was more portable to C++. You
|
|
Packit Service |
7770af |
should be able to drop it into ruby 3.2.19 and get the same results from ruby sass.
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
def group_by_to_a(enum, &block)
|
|
Packit Service |
7770af |
order = {}
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
arr = []
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
grouped = {}
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
for e in enum do
|
|
Packit Service |
7770af |
key = block[e]
|
|
Packit Service |
7770af |
unless order.include?(key)
|
|
Packit Service |
7770af |
order[key] = order.size
|
|
Packit Service |
7770af |
end
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
if not grouped.has_key?(key) then
|
|
Packit Service |
7770af |
grouped[key] = [e]
|
|
Packit Service |
7770af |
else
|
|
Packit Service |
7770af |
grouped[key].push(e)
|
|
Packit Service |
7770af |
end
|
|
Packit Service |
7770af |
end
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
grouped.each do |key, vals|
|
|
Packit Service |
7770af |
arr[order[key]] = [key, vals]
|
|
Packit Service |
7770af |
end
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
arr
|
|
Packit Service |
7770af |
end
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
*/
|
|
Packit Service |
7770af |
template<typename EnumType, typename KeyType, typename KeyFunctorType>
|
|
Packit Service |
7770af |
void group_by_to_a(std::vector<EnumType>& enumeration, KeyFunctorType& keyFunc, std::vector<std::pair<KeyType, std::vector<EnumType> > >& arr /*out*/) {
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
std::map<unsigned int, KeyType> order;
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
std::map<size_t, std::vector<EnumType> > grouped;
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
for (typename std::vector<EnumType>::iterator enumIter = enumeration.begin(), enumIterEnd = enumeration.end(); enumIter != enumIterEnd; enumIter++) {
|
|
Packit Service |
7770af |
EnumType& e = *enumIter;
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
KeyType key = keyFunc(e);
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
if (grouped.find(key->hash()) == grouped.end()) {
|
|
Packit Service |
7770af |
order.insert(std::make_pair((unsigned int)order.size(), key));
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
std::vector<EnumType> newCollection;
|
|
Packit Service |
7770af |
newCollection.push_back(e);
|
|
Packit Service |
7770af |
grouped.insert(std::make_pair(key->hash(), newCollection));
|
|
Packit Service |
7770af |
} else {
|
|
Packit Service |
7770af |
std::vector<EnumType>& collection = grouped.at(key->hash());
|
|
Packit Service |
7770af |
collection.push_back(e);
|
|
Packit Service |
7770af |
}
|
|
Packit Service |
7770af |
}
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
for (unsigned int index = 0; index < order.size(); index++) {
|
|
Packit Service |
7770af |
KeyType& key = order.at(index);
|
|
Packit Service |
7770af |
std::vector<EnumType>& values = grouped.at(key->hash());
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
std::pair<KeyType, std::vector<EnumType> > grouping = std::make_pair(key, values);
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
arr.push_back(grouping);
|
|
Packit Service |
7770af |
}
|
|
Packit Service |
7770af |
}
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
}
|
|
Packit Service |
7770af |
|
|
Packit Service |
7770af |
#endif
|