<commit_before>#pragma once

#include <vector>
#include <algorithm>
#include <utility>
#include <functional>

namespace math {

template <typename Coefficient>
class polynomial : public std::vector<Coefficient> {
  /* return quotient and remainder */
  std::pair<polynomial, polynomial> division(const polynomial &lhs,
                                             const polynomial &rhs) const {
    if (!rhs)
      throw std::logic_error("Division by zero");

    if (lhs.degree() < rhs.degree())
      return std::make_tuple(polynomial(1, Coefficient(0)), lhs);

    const size_t quotient_degree =
        static_cast<size_t>(lhs.degree() - rhs.degree());
    polynomial q(quotient_degree + 1, Coefficient(0));
    polynomial r(lhs);

    auto r_lead = r.rlead();
    auto rhs_lead = rhs.crlead();
    auto q_it = std::rbegin(q);

    for (; r.degree() >= rhs.degree(); ++r_lead, ++q_it) {
      auto coefficient = *r_lead / *rhs_lead;

      // q = q + t;
      (*q_it) += coefficient;

      // r = r - (rhs * t);
      // leading zero coeffs in rhs possible, so use lead instead of crbegin()
      std::transform(r_lead, r_lead + rhs.degree() + 1, rhs_lead, r_lead,
                     [=](const Coefficient &lhs_, const Coefficient &rhs_) {
        return lhs_ - (rhs_ * coefficient);
      });
    }

    /* TODO remove leading zeroes */

    return std::make_tuple(q, r);
  }

  template <typename Op>
  polynomial &element_wise(const polynomial &rhs, Op &&op) {
    if (this->size() < rhs.size()) {
      this->reserve(rhs.size());
      std::fill_n(std::back_inserter(*this), rhs.size() - this->size(),
                  Coefficient(0));
    }

    std::transform(std::cbegin(rhs), std::cend(rhs), std::cbegin(*this),
                   std::begin(*this), std::forward<Op &&>(op));

    /* todo remove leading zeroes */

    return *this;
  }

  typename std::vector<Coefficient>::const_reverse_iterator crlead() const
      noexcept {
    return std::find_if(std::crbegin(*this), std::crend(*this),
                        [](const Coefficient &e) { return e; });
  }

  typename std::vector<Coefficient>::reverse_iterator rlead() {
    auto lead = std::find_if(std::rbegin(*this), std::rend(*this),
                             [](const Coefficient &e) { return e; });
    if (lead == std::rend(*this))
      return std::rend(*this) - 1;

    return lead;
  }

public:
  using std::vector<Coefficient>::vector;
  using coefficient_type = Coefficient;

  polynomial() = default;
  polynomial(const Coefficient &e) : std::vector<Coefficient>::vector(1, e) {}
  polynomial(const polynomial &) = default;
  polynomial(polynomial &&) = default;
  polynomial &operator=(const polynomial &rhs) = default;
  polynomial &operator=(polynomial &&) = default;

  explicit polynomial(
      std::vector<typename Coefficient::storage_type> coefficients) {
    for (const auto &element : coefficients) {
      this->push_back(Coefficient(element));
    }
  }
  explicit polynomial(const std::vector<Coefficient> &v)
      : std::vector<Coefficient>::vector(v) {}

  ssize_t degree() const noexcept {
    auto it = std::find_if(std::crbegin(*this), std::crend(*this),
                           [](const Coefficient &e) { return e; });
    return std::distance(it, std::crend(*this)) - 1;
  }

  typename std::vector<Coefficient>::size_type weight() const noexcept {
    return std::count_if(std::cbegin(*this), std::cend(*this),
                         [](const auto &e) { return e; });
  }

  Coefficient highest() const {
    if (!this->size())
      throw std::out_of_range("Polynomial has no terms.");

    return this->at(degree());
  }

  polynomial &reverse() {
    std::reverse(std::begin(*this), std::begin(*this) + degree() + 1);
    return *this;
  }

  polynomial simplified() const {
    polynomial copy;
    copy.reserve(this->size());
    std::copy(std::cbegin(*this), std::cbegin(*this) + this->degree() + 1,
              std::back_inserter(copy));

    return copy;
  }

  const Coefficient &operator[](const size_t &index) const {
    return this->at(index);
  }
  Coefficient &operator[](const size_t &index) { return this->at(index); }

  polynomial operator+(const polynomial &rhs) const {
    auto copy(*this);
    copy += rhs;
    return copy;
  }

  polynomial operator-(const polynomial &rhs) const {
    auto copy(*this);
    copy += rhs;
    return copy;
  }

  polynomial operator*(const polynomial &rhs) const {
    if (!(*this && rhs))
      return polynomial({ Coefficient(0) });
    /* The range based for loop below also loops over leading zero coefficients,
     * so use size() instead of degree()
     */
    polynomial result(this->size() + rhs.size(), Coefficient(0));

    auto coffset = std::cbegin(result);
    auto offset = std::begin(result);
    for (const auto &term : *this) {
      auto copy = rhs * term;

      // std::cout << "  rhs * term = " << rhs << " * " << term << " = " << copy
      // << std::endl;
      std::transform(std::cbegin(copy), std::cend(copy), coffset, offset,
                     std::plus<Coefficient>{});
      ++coffset;
      ++offset;
    }
    return result;
  }
<commit_msg>Handle leading zeroes properly in polynomial multiplication<commit_after>#pragma once

#include <vector>
#include <algorithm>
#include <utility>
#include <functional>

namespace math {

template <typename Coefficient>
class polynomial : public std::vector<Coefficient> {
  /* return quotient and remainder */
  std::pair<polynomial, polynomial> division(const polynomial &lhs,
                                             const polynomial &rhs) const {
    if (!rhs)
      throw std::logic_error("Division by zero");

    if (lhs.degree() < rhs.degree())
      return std::make_tuple(polynomial(1, Coefficient(0)), lhs);

    const size_t quotient_degree =
        static_cast<size_t>(lhs.degree() - rhs.degree());
    polynomial q(quotient_degree + 1, Coefficient(0));
    polynomial r(lhs);

    auto r_lead = r.rlead();
    auto rhs_lead = rhs.crlead();
    auto q_it = std::rbegin(q);

    for (; r.degree() >= rhs.degree(); ++r_lead, ++q_it) {
      auto coefficient = *r_lead / *rhs_lead;

      // q = q + t;
      (*q_it) += coefficient;

      // r = r - (rhs * t);
      // leading zero coeffs in rhs possible, so use lead instead of crbegin()
      std::transform(r_lead, r_lead + rhs.degree() + 1, rhs_lead, r_lead,
                     [=](const Coefficient &lhs_, const Coefficient &rhs_) {
        return lhs_ - (rhs_ * coefficient);
      });
    }

    /* TODO remove leading zeroes */

    return std::make_tuple(q, r);
  }

  template <typename Op>
  polynomial &element_wise(const polynomial &rhs, Op &&op) {
    if (this->size() < rhs.size()) {
      this->reserve(rhs.size());
      std::fill_n(std::back_inserter(*this), rhs.size() - this->size(),
                  Coefficient(0));
    }

    std::transform(std::cbegin(rhs), std::cend(rhs), std::cbegin(*this),
                   std::begin(*this), std::forward<Op &&>(op));

    /* todo remove leading zeroes */

    return *this;
  }

  typename std::vector<Coefficient>::const_reverse_iterator crlead() const
      noexcept {
    return std::find_if(std::crbegin(*this), std::crend(*this),
                        [](const Coefficient &e) { return e; });
  }

  typename std::vector<Coefficient>::reverse_iterator rlead() {
    auto lead = std::find_if(std::rbegin(*this), std::rend(*this),
                             [](const Coefficient &e) { return e; });
    if (lead == std::rend(*this))
      return std::rend(*this) - 1;

    return lead;
  }

public:
  using std::vector<Coefficient>::vector;
  using coefficient_type = Coefficient;

  polynomial() = default;
  polynomial(const Coefficient &e) : std::vector<Coefficient>::vector(1, e) {}
  polynomial(const polynomial &) = default;
  polynomial(polynomial &&) = default;
  polynomial &operator=(const polynomial &rhs) = default;
  polynomial &operator=(polynomial &&) = default;

  explicit polynomial(
      std::vector<typename Coefficient::storage_type> coefficients) {
    for (const auto &element : coefficients) {
      this->push_back(Coefficient(element));
    }
  }
  explicit polynomial(const std::vector<Coefficient> &v)
      : std::vector<Coefficient>::vector(v) {}

  ssize_t degree() const noexcept {
    auto it = std::find_if(std::crbegin(*this), std::crend(*this),
                           [](const Coefficient &e) { return e; });
    return std::distance(it, std::crend(*this)) - 1;
  }

  typename std::vector<Coefficient>::size_type weight() const noexcept {
    return std::count_if(std::cbegin(*this), std::cend(*this),
                         [](const auto &e) { return e; });
  }

  Coefficient highest() const {
    if (!this->size())
      throw std::out_of_range("Polynomial has no terms.");

    return this->at(degree());
  }

  polynomial &reverse() {
    std::reverse(std::begin(*this), std::begin(*this) + degree() + 1);
    return *this;
  }

  polynomial simplified() const {
    polynomial copy;
    copy.reserve(this->size());
    std::copy(std::cbegin(*this), std::cbegin(*this) + this->degree() + 1,
              std::back_inserter(copy));

    return copy;
  }

  const Coefficient &operator[](const size_t &index) const {
    return this->at(index);
  }
  Coefficient &operator[](const size_t &index) { return this->at(index); }

  polynomial operator+(const polynomial &rhs) const {
    auto copy(*this);
    copy += rhs;
    return copy;
  }

  polynomial operator-(const polynomial &rhs) const {
    auto copy(*this);
    copy += rhs;
    return copy;
  }

  polynomial operator*(const polynomial &rhs) const {
    if (!(*this && rhs))
      return polynomial({ Coefficient(0) });

    auto rhs_ = rhs.simplified();
    const size_t size = static_cast<size_t>(this->degree()) + rhs_.size();
    polynomial result(size, Coefficient(0));

    auto coffset = std::cbegin(result);
    auto offset = std::begin(result);
    for (const auto &term : *this) {
      if (term) {
        auto copy = rhs_ * term;

        // std::cout << "  rhs * term = " << rhs << " * " << term << " = " <<
        // copy
        // << std::endl;
        std::transform(std::cbegin(copy), std::cend(copy), coffset, offset,
                       std::plus<Coefficient>{});
      }
      ++coffset;
      ++offset;
    }
    return result;
  }

{'fraction_non_alphanumeric': 0.1609228690027995, 'fraction_numerical': 0.0025098947774881745, 'mean_word_length': 2.948170731707317, 'pattern_counts': {'":': 0, '<': 74, '<?xml version=': 0, '>': 66, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7210254', 'n_tokens_mistral': 3312, 'n_tokens_neox': 3264, 'n_words': 767}