Skip to content

Instantly share code, notes, and snippets.

@deque-blog
Last active December 22, 2016 20:53
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save deque-blog/6ad6a3b943773fa944823cad4842cedc to your computer and use it in GitHub Desktop.
Save deque-blog/6ad6a3b943773fa944823cad4842cedc to your computer and use it in GitHub Desktop.
template<typename Iterator, typename Value, typename BinaryOp>
Value add_to_counter(Iterator first, Iterator last,
Value carry, Value const &zero,
BinaryOp op)
{
assert(carry != zero);
for (; first != last; ++first) {
if (*first == zero) {
*first = carry;
return zero;
}
carry = op(*first, carry);
*first = zero;
}
return carry;
}
template<typename Iterator, typename Value, typename BinaryOp>
Value reduce_counter(Iterator first, Iterator last,
Value const &zero, BinaryOp op)
{
first = std::find_if(first, last, [&zero](auto &v) { return v != zero; });
if (first == last)
return zero;
Value result = *first;
for (++first; first != last; ++first) {
if (*first != zero)
result = op(*first, result);
}
return result;
};
template<typename BinaryOp, typename Value>
class binary_counter {
public:
binary_counter(BinaryOp const &op, Value const &zero)
: m_bits(), m_zero(zero), m_op(op) {}
void add(Value carry) {
carry = add_to_counter(begin(m_bits), end(m_bits), carry, m_zero, m_op);
if (carry != m_zero)
m_bits.push_back(std::move(carry));
}
Value reduce() const {
return reduce_counter(begin(m_bits), end(m_bits), m_zero, m_op);
}
private:
std::vector<Value> m_bits;
Value m_zero;
BinaryOp m_op;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment