<commit_before>#ifndef MOGVW_H
#define MOGVW_H

#include <unordered_set>
#include <unordered_map>
#include <limits>
#include <vector>
#include <algorithm>
#include <memory>

#include "style.h"
#include "debug.h"
#include "integral.h"
#include "Polynomial.h"
#include "MM.h"

template<class P = Polynomial<Term<int, Monomial<char> > > >
struct moGVWRunner {
  typedef typename P::MonomialType MonomialType;
  typedef typename P::TermType TermType;
  typedef typename P::TermType T;
  typedef typename P::CoefficientType CoefficientType;
  typedef MM<P> MMType;
  typedef MonRl<P> MonRlType;
  typedef std::unordered_map<MonomialType, std::shared_ptr<MMType> > LMSet;
  typedef std::unordered_set<MMType> MMSet;
  typedef std::set<MonomialType> MSet;

  MMType signature(const MonomialType& m, const MMType& uf) const {
    MonomialType t = m / uf.f.lm();
    return MMType(uf.u, T(1, t));
  }

  MMType signature(const std::pair<MonomialType, std::shared_ptr<MMType> >& muf) const {
    return signature(muf.first, *(muf.second));
  }

  bool rejectedByLCMCriterion(const MonomialType& m, std::shared_ptr<MMType> uf, const LMSet& GG) {
    auto lmf = uf->f.lm();
    auto nvg = GG.find(m);
    if (nvg == GG.end()) return false;
    auto lmg = nvg->second->f.lm();
    if (m == lcm(lmf, lmg)) {
      return false;
    }
    if (signature(m, *uf) > signature(*nvg)) {
      D("rejecting (" << m << ", " << *uf << ") because " << *nvg << " has smaller signature");
      return true;
    }
    return false;
  }

  bool rejectedBySyzygyCriterion(const MonomialType& m, std::shared_ptr<MMType> uf, const LMSet& GG) {
    auto lmu = uf->u;
    auto t_f = m / uf->f.lm();
    auto nvg = GG.find(t_f*lmu.m);
    if (nvg == GG.end()) return false;
    auto lmv = nvg->second->u;
    if (lmu.index > lmv.index) {
      D("rejecting (" << m << ", " << *uf << ") because " << *nvg << " has smaller index");
      return true;
    }
    return false;
  }

  bool rejectedByRewrittenCriterion(const MonomialType& m, std::shared_ptr<MMType> uf, const LMSet& GG) {
    auto lmu = uf->u;
    auto lmf = uf->f.lm();
    for (auto nvg = GG.begin(); nvg != GG.end(); ++nvg) {
      auto lmv = nvg->second->u;
      if (!lmv.divides(lmu)) continue;
      auto t = lmu / lmv;
      if (t*nvg->second->f.lm() < lmf) {
        D("rejecting " << *uf);
        return true;
      }
    }
    return false;
  }

  MMSet lift(const LMSet& todo, LMSet& GG) {
    DD("todo = ", todo);

    MMSet HH;
    for (const auto& muf : todo) {
      D("chose " << muf << " to lift");
      for (uint i = 0; i < MonomialType::VAR_COUNT; ++i) {
        auto xim_m = muf.first;
        xim_m[i]++;
        auto uf = muf.second;
        auto nvg = GG.find(xim_m);
        if (nvg != GG.end()) {
          auto vg = nvg->second;
          MonomialType t_f = xim_m / uf->f.lm();
          MonomialType t_g = xim_m / vg->f.lm();
          auto tf_lmu = t_f * uf->u;
          auto tg_lmv = t_g * vg->u;
          if (tf_lmu > tg_lmv
              && !rejectedByLCMCriterion(xim_m, uf, GG)
              && !rejectedBySyzygyCriterion(xim_m, uf, GG)
              && !rejectedByRewrittenCriterion(xim_m, uf, GG)) {
            auto tf_uf = t_f * *uf;
            auto tg_vg = t_g * *vg;
            D("inserting " << tf_uf << " into HH");
            HH.insert(tf_uf);
            D("inserting " << tg_vg << " into HH");
            HH.insert(tg_vg);
          }
          if (tf_lmu < tg_lmv) {
            D("replacing GG[" << xim_m << "] = " << *vg << " by " << *uf);
            GG[xim_m] = uf;
            if (!rejectedByLCMCriterion(xim_m, vg, GG)
                && !rejectedBySyzygyCriterion(xim_m, vg, GG)
                && !rejectedByRewrittenCriterion(xim_m, vg, GG)) {
              auto tf_uf = t_f * *uf;
              auto tg_vg = t_g * *vg;
              D("inserting " << tf_uf << " into HH");
              HH.insert(tf_uf);
              D("inserting " << tg_vg << " into HH");
              HH.insert(tg_vg);
            }
          }
        } else {
          GG[xim_m] = uf;
        }
      }
      wasLifted[muf.first] = true;
    }
    DD("returning HH = ", HH);
    return HH;
  }

  void append(MMSet& HH, const LMSet& GG) {
    MSet done;
    for (auto wh = HH.begin(); wh != HH.end(); ++wh) {
      done.insert(wh->f.lm());
    }
    DD("initialized done = ", done);
    MSet monomialsInHH;
    for (auto wh : HH) {
      std::forward_list<TermType> terms = wh.f.terms();
      for (const auto& term : terms) {
        monomialsInHH.insert(term.m());
      }
    }
    for (auto it = done.begin(); it != done.end(); ++it) {
      monomialsInHH.erase(*it);
    }
    DD("monomials in HH that are not done = ", monomialsInHH);
    while (!monomialsInHH.empty()) {
      MonomialType m = *(monomialsInHH.begin());
      done.insert(m);
      auto it = GG.find(m);
      if (it != GG.end()) {
        auto vg = it->second;
        MonomialType t = m / vg->f.lm();
        MMType newMM = t * *vg;
        HH.insert(newMM);
        std::forward_list<TermType> terms = newMM.f.terms();
        for (auto term : terms) {
          monomialsInHH.insert(term.m());
        }
      }
      for (auto it = done.begin(); it != done.end(); ++it) {
        auto found = monomialsInHH.find(*it);
        if (found != monomialsInHH.end()) {
          monomialsInHH.erase(found);
        }
      }
    }
    DD("returning HH = ", HH);
  }

  MMSet eliminate(MMSet& HH) {
    MMSet PP;
    MMSet todoInHH = HH;
    while (!todoInHH.empty()) {
      auto uf = *(todoInHH.begin());
      D("working on " << uf);
      HH.erase(uf);
      todoInHH.erase(uf);
      bool found = false;
      auto it = HH.begin();
      while (it != HH.end() && !found) {
        if (it->f.lm() == uf.f.lm()) {
          found = true;
        } else {
          ++it;
        }
      }
      if (!found) {
        it = PP.begin();
      }
      while (it != PP.end() && !found) {
        if (it->f.lm() == uf.f.lm()) {
          found = true;
        } else {
          ++it;
        }
      }
      if (found) {
        auto vg = *it;
        D("reducing " << uf << " with " << vg);
        auto u = uf.u;
        auto v = vg.u;
        auto f = uf.f;
        auto g = vg.f;
        auto lcg = g.lc();
        auto lcf = f.lc();

        if (u > v) {
          auto r = P::combine(f, lcg, g, -lcf);
          if (r.isZero()) {
            D("a row in HH reduced to zero!");
          } else {
            r.renormalize();
            MonRlType w(std::max(u.m, v.m), std::min(u.index, v.index));
            MMType wr = MMType(w, r);
            D("inserting " << wr << " into HH");
            HH.insert(wr);
            todoInHH.insert(wr);
          }
        }
        if (u < v) {
          D("removing " << vg << " from HH");
          HH.erase(vg);
          todoInHH.erase(vg);
          auto r = P::combine(f, -lcg, g, lcf);
          if (r.isZero()) {
            D("a row in HH reduced to zero!");
          } else {
            r.renormalize();
            MonRlType w(std::max(u.m, v.m), std::min(u.index, v.index));
            MMType wr = MMType(w, r);
            D("inserting " << wr << " into HH");
            HH.insert(wr);
            todoInHH.insert(wr);
          }
          D("inserting " << uf << " into HH");
          HH.insert(uf);
        }
      } else {
        D("no reduction found for " << uf);
        PP.insert(uf);
      }
    }
    DD("returning PP = ", PP);
    return PP;
  }

  void update(const MMSet& PP, LMSet& GG) {
    for (auto wh = PP.begin(); wh != PP.end(); ++wh) {
      if (wh->f.isZero()) continue;
      auto m = wh->f.lm();
      D("looking for lm(h) = " << m);
      auto mvg = GG.find(m);
      if (mvg != GG.end()) {
        auto v = mvg->second->u;
        auto w = wh->u;
        auto g = mvg->second->f;
        if (((m / g.lm()) * v) > w) {
          D("replacing " << mvg->second << " by " << *wh);
          GG[m] = std::shared_ptr<MMType>(new MMType(*wh));
        }
      } else {
        D("not found, adding (" << m << ", " << *wh << ") to GG");
        GG[m] = std::shared_ptr<MMType>(new MMType(*wh));
      }
    }
    DD("returning, GG = ", GG);
    D("GG has " << GG.size() << " elements in " << GG.bucket_count() << " buckets");
  }

  std::set<P> interreduce(const std::set<P>& input) {
    DD("input = ", input);
    std::vector<P> intermediate(input.begin(), input.end());
    bool stable;
    do {
      stable = true;
      for (auto p = intermediate.begin(); p != intermediate.end(); ++p) {
        auto terms = p->terms();
        auto term = terms.begin();
        while (term != terms.end()) {
          auto r = intermediate.begin();
          while (r != intermediate.end() && (r->isZero() || r == p || !r->lm().divides(term->m()))) {
            ++r;
          }
          if (r != intermediate.end()) {
            D("reducing " << *p << " with " << *r);
            stable = false;
            auto t = term->m() / r->lm();
            auto rt = *r * t;
            p->combine(r->lc(), rt, -term->c());
            p->renormalize();
            D("to " << *p);<commit_msg>Replacing some for loops with for in loops.<commit_after>#ifndef MOGVW_H
#define MOGVW_H

#include <unordered_set>
#include <unordered_map>
#include <limits>
#include <vector>
#include <algorithm>
#include <memory>

#include "style.h"
#include "debug.h"
#include "integral.h"
#include "Polynomial.h"
#include "MM.h"

template<class P = Polynomial<Term<int, Monomial<char> > > >
struct moGVWRunner {
  typedef typename P::MonomialType MonomialType;
  typedef typename P::TermType TermType;
  typedef typename P::TermType T;
  typedef typename P::CoefficientType CoefficientType;
  typedef MM<P> MMType;
  typedef MonRl<P> MonRlType;
  typedef std::unordered_map<MonomialType, std::shared_ptr<MMType> > LMSet;
  typedef std::unordered_set<MMType> MMSet;
  typedef std::set<MonomialType> MSet;

  MMType signature(const MonomialType& m, const MMType& uf) const {
    MonomialType t = m / uf.f.lm();
    return MMType(uf.u, T(1, t));
  }

  MMType signature(const std::pair<MonomialType, std::shared_ptr<MMType> >& muf) const {
    return signature(muf.first, *(muf.second));
  }

  bool rejectedByLCMCriterion(const MonomialType& m, std::shared_ptr<MMType> uf, const LMSet& GG) {
    auto lmf = uf->f.lm();
    auto nvg = GG.find(m);
    if (nvg == GG.end()) return false;
    auto lmg = nvg->second->f.lm();
    if (m == lcm(lmf, lmg)) {
      return false;
    }
    if (signature(m, *uf) > signature(*nvg)) {
      D("rejecting (" << m << ", " << *uf << ") because " << *nvg << " has smaller signature");
      return true;
    }
    return false;
  }

  bool rejectedBySyzygyCriterion(const MonomialType& m, std::shared_ptr<MMType> uf, const LMSet& GG) {
    auto lmu = uf->u;
    auto t_f = m / uf->f.lm();
    auto nvg = GG.find(t_f*lmu.m);
    if (nvg == GG.end()) return false;
    auto lmv = nvg->second->u;
    if (lmu.index > lmv.index) {
      D("rejecting (" << m << ", " << *uf << ") because " << *nvg << " has smaller index");
      return true;
    }
    return false;
  }

  bool rejectedByRewrittenCriterion(const MonomialType& m, std::shared_ptr<MMType> uf, const LMSet& GG) {
    auto lmu = uf->u;
    auto lmf = uf->f.lm();
    for (auto nvg = GG.begin(); nvg != GG.end(); ++nvg) {
      auto lmv = nvg->second->u;
      if (!lmv.divides(lmu)) continue;
      auto t = lmu / lmv;
      if (t*nvg->second->f.lm() < lmf) {
        D("rejecting " << *uf);
        return true;
      }
    }
    return false;
  }

  MMSet lift(const LMSet& todo, LMSet& GG) {
    DD("todo = ", todo);

    MMSet HH;
    for (const auto& muf : todo) {
      D("chose " << muf << " to lift");
      for (uint i = 0; i < MonomialType::VAR_COUNT; ++i) {
        auto xim_m = muf.first;
        xim_m[i]++;
        auto uf = muf.second;
        auto nvg = GG.find(xim_m);
        if (nvg != GG.end()) {
          auto vg = nvg->second;
          MonomialType t_f = xim_m / uf->f.lm();
          MonomialType t_g = xim_m / vg->f.lm();
          auto tf_lmu = t_f * uf->u;
          auto tg_lmv = t_g * vg->u;
          if (tf_lmu > tg_lmv
              && !rejectedByLCMCriterion(xim_m, uf, GG)
              && !rejectedBySyzygyCriterion(xim_m, uf, GG)
              && !rejectedByRewrittenCriterion(xim_m, uf, GG)) {
            auto tf_uf = t_f * *uf;
            auto tg_vg = t_g * *vg;
            D("inserting " << tf_uf << " into HH");
            HH.insert(tf_uf);
            D("inserting " << tg_vg << " into HH");
            HH.insert(tg_vg);
          }
          if (tf_lmu < tg_lmv) {
            D("replacing GG[" << xim_m << "] = " << *vg << " by " << *uf);
            GG[xim_m] = uf;
            if (!rejectedByLCMCriterion(xim_m, vg, GG)
                && !rejectedBySyzygyCriterion(xim_m, vg, GG)
                && !rejectedByRewrittenCriterion(xim_m, vg, GG)) {
              auto tf_uf = t_f * *uf;
              auto tg_vg = t_g * *vg;
              D("inserting " << tf_uf << " into HH");
              HH.insert(tf_uf);
              D("inserting " << tg_vg << " into HH");
              HH.insert(tg_vg);
            }
          }
        } else {
          GG[xim_m] = uf;
        }
      }
      wasLifted[muf.first] = true;
    }
    DD("returning HH = ", HH);
    return HH;
  }

  void append(MMSet& HH, const LMSet& GG) {
    MSet done;
    for (const auto& wh : HH) {
      done.insert(wh.f.lm());
    }
    DD("initialized done = ", done);
    MSet monomialsInHH;
    for (const auto& wh : HH) {
      auto terms = wh.f.terms();
      for (const auto& term : terms) {
        if (done.find(term.m()) == done.end())
          monomialsInHH.insert(term.m());
      }
    }
    DD("monomials in HH that are not done = ", monomialsInHH);
    while (!monomialsInHH.empty()) {
      MonomialType m = *(monomialsInHH.begin());
      done.insert(m);
      auto it = GG.find(m);
      if (it != GG.end()) {
        auto vg = it->second;
        MonomialType t = m / vg->f.lm();
        MMType newMM = t * *vg;
        HH.insert(newMM);
        for (const auto& term : newMM.f.terms()) {
          monomialsInHH.insert(term.m());
        }
      }
      for (const auto& it : done) {
        auto found = monomialsInHH.find(it);
        if (found != monomialsInHH.end()) {
          monomialsInHH.erase(found);
        }
      }
    }
    DD("returning HH = ", HH);
  }

  MMSet eliminate(MMSet& HH) {
    MMSet PP;
    MMSet todoInHH = HH;
    while (!todoInHH.empty()) {
      auto uf = *(todoInHH.begin());
      D("working on " << uf);
      HH.erase(uf);
      todoInHH.erase(uf);
      bool found = false;
      auto it = HH.begin();
      while (it != HH.end() && !found) {
        if (it->f.lm() == uf.f.lm()) {
          found = true;
        } else {
          ++it;
        }
      }
      if (!found) {
        it = PP.begin();
      }
      while (it != PP.end() && !found) {
        if (it->f.lm() == uf.f.lm()) {
          found = true;
        } else {
          ++it;
        }
      }
      if (found) {
        auto vg = *it;
        D("reducing " << uf << " with " << vg);
        auto u = uf.u;
        auto v = vg.u;
        auto f = uf.f;
        auto g = vg.f;
        auto lcg = g.lc();
        auto lcf = f.lc();

        if (u > v) {
          auto r = P::combine(f, lcg, g, -lcf);
          if (r.isZero()) {
            D("a row in HH reduced to zero!");
          } else {
            r.renormalize();
            MonRlType w(std::max(u.m, v.m), std::min(u.index, v.index));
            MMType wr = MMType(w, r);
            D("inserting " << wr << " into HH");
            HH.insert(wr);
            todoInHH.insert(wr);
          }
        }
        if (u < v) {
          D("removing " << vg << " from HH");
          HH.erase(vg);
          todoInHH.erase(vg);
          auto r = P::combine(f, -lcg, g, lcf);
          if (r.isZero()) {
            D("a row in HH reduced to zero!");
          } else {
            r.renormalize();
            MonRlType w(std::max(u.m, v.m), std::min(u.index, v.index));
            MMType wr = MMType(w, r);
            D("inserting " << wr << " into HH");
            HH.insert(wr);
            todoInHH.insert(wr);
          }
          D("inserting " << uf << " into HH");
          HH.insert(uf);
        }
      } else {
        D("no reduction found for " << uf);
        PP.insert(uf);
      }
    }
    DD("returning PP = ", PP);
    return PP;
  }

  void update(const MMSet& PP, LMSet& GG) {
    for (const auto& wh : PP) {
      if (wh.f.isZero()) continue;
      auto m = wh.f.lm();
      D("looking for lm(h) = " << m);
      auto mvg = GG.find(m);
      if (mvg != GG.end()) {
        auto v = mvg->second->u;
        auto w = wh.u;
        auto g = mvg->second->f;
        if (((m / g.lm()) * v) > w) {
          D("replacing " << mvg->second << " by " << wh);
          GG[m] = std::shared_ptr<MMType>(new MMType(wh));
        }
      } else {
        D("not found, adding (" << m << ", " << wh << ") to GG");
        GG[m] = std::shared_ptr<MMType>(new MMType(wh));
      }
    }
    DD("returning, GG = ", GG);
    D("GG has " << GG.size() << " elements in " << GG.bucket_count() << " buckets");
  }

  std::set<P> interreduce(const std::set<P>& input) {
    DD("input = ", input);
    std::vector<P> intermediate(input.begin(), input.end());
    bool stable;
    do {
      stable = true;
      for (auto p = intermediate.begin(); p != intermediate.end(); ++p) {
        auto terms = p->terms();
        auto term = terms.begin();
        while (term != terms.end()) {
          auto r = intermediate.begin();
          while (r != intermediate.end() && (r->isZero() || r == p || !r->lm().divides(term->m()))) {
            ++r;
          }
          if (r != intermediate.end()) {
            D("reducing " << *p << " with " << *r);
            stable = false;
            auto t = term->m() / r->lm();
            auto rt = *r * t;
            p->combine(r->lc(), rt, -term->c());
            p->renormalize();
            D("to " << *p);
{'fraction_non_alphanumeric': 0.17759805007755372, 'fraction_numerical': 0.00022158209616662973, 'mean_word_length': 1.82078125, 'pattern_counts': {'":': 0, '<': 293, '<?xml version=': 0, '>': 145, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6209676', 'n_tokens_mistral': 6836, 'n_tokens_neox': 6560, 'n_words': 1510}