<commit_before>#ifndef FREE_SEMIRING_H
#define FREE_SEMIRING_H

#include <memory>
#include <string>
#include <unordered_map>

#include "matrix.h"
#include "semiring.h"
#include "var.h"

#include "free-structure.h"


class FreeSemiring2 : public Semiring<FreeSemiring2> {
  public:
    FreeSemiring2(const VarPtr var) {
      assert(var);
      InitFactory();
      assert(factory_);
      node_ = factory_->NewElement(var);
      assert(node_);
    }

    static FreeSemiring2 null() {
      InitFactory();
      assert(factory_);
      return FreeSemiring2{factory_->GetEmpty()};
    }

    static FreeSemiring2 one() {
      InitFactory();
      assert(factory_);
      return FreeSemiring2{factory_->GetEpsilon()};
    }

    FreeSemiring2 star() const {
      assert(factory_);
      return FreeSemiring2{factory_->NewStar(node_)};
    }

    FreeSemiring2 operator+(const FreeSemiring2 &x) {
      assert(factory_);
      return FreeSemiring2{factory_->NewAddition(node_, x.node_)};
    }

    FreeSemiring2 operator*(const FreeSemiring2 &x) {
      assert(factory_);
      return FreeSemiring2{factory_->NewMultiplication(node_, x.node_)};
    }

    bool operator==(const FreeSemiring2 &x) const {
      return node_ == x.node_;
    }

    std::string string() const {
      std::stringstream ss;
      ss << *node_;
      return ss.str();
    }

    template <typename SR>
    SR Eval(const std::unordered_map<VarPtr, SR> &valuation) const;

    void PrintDot(std::ostream &out) {
      assert(factory_);
      factory_->PrintDot(out);
    }

    void GC() {
      assert(factory_);
      factory_->GC();
    }

  private:
    FreeSemiring2(NodePtr n) : node_(n) { assert(factory_); }

    static void InitFactory() {
      if (factory_ == nullptr) {
        factory_ = std::move(std::unique_ptr<NodeFactory>(new NodeFactory));
      }
    }

    NodePtr node_;
    static std::unique_ptr<NodeFactory> factory_;

    friend struct std::hash<FreeSemiring2>;
};

namespace std {

template <>
struct hash<FreeSemiring2> {
  inline std::size_t operator()(const FreeSemiring2 &fs) const {
    std::hash<NodePtr> h;
    return h(fs.node_);
  }
};

}  /* namespace std */


/*
 * Evaluator
 *
 * We want to memoize the result of evaluating every subgraph, since we can
 * reach the same node (and thus the same subgraph) many times.  So only the
 * first one we will actually perform the computation, in all subsequent visits
 * we will reuse the memoized reslt.  Note that this is ok, because we never
 * modify the actual semiring values.  We use shared_ptrs to avoid any
 * unnecessary copying of temporary values, etc.
 */
template <typename SR>
class Evaluator : public NodeVisitor {
  typedef std::shared_ptr<SR> SRPtr_;
  public:
    Evaluator(const std::unordered_map<VarPtr, SR> &v)
        : val_(v), evaled_(), result_() {}

    void Visit(const Addition &a) {
      LookupEval(a.GetLhs());
      auto temp = std::move(result_);
      LookupEval(a.GetRhs());
      result_ = std::make_shared<SR>(*temp + *result_);
    }

    void Visit(const Multiplication &m) {
      LookupEval(m.GetLhs());
      auto temp = std::move(result_);
      LookupEval(m.GetRhs());
      result_ = std::make_shared<SR>(*temp * *result_);
    }

    void Visit(const Star &s) {
      LookupEval(s.GetNode());
      result_ = std::make_shared<SR>(result_->star());
    }

    void Visit(const Element &e) {
      auto iter = val_.find(e.GetVar());
      assert(iter != val_.end());
      result_ = std::make_shared<SR>(iter->second);
    }

    void Visit(const Epsilon &e) {
      result_ = std::make_shared<SR>(SR::one());
    }

    void Visit(const Empty &e) {
      result_ = std::make_shared<SR>(SR::null());
    }

    std::shared_ptr<SR> GetResult() {
      return result_;
    }

  private:
    void LookupEval(const NodePtr &node) {
      auto iter = evaled_.find(node);
      if (iter != evaled_.end()) {
        result_ = iter->second;
      } else {
        node->Accept(*this);  /* Sets the result_ correctly */
        evaled_.emplace(node, result_);
      }
    }

    const std::unordered_map<VarPtr, SR> &val_;
    std::unordered_map<NodePtr, SRPtr_> evaled_;
    SRPtr_ result_;
};

template <typename SR>
SR FreeSemiring2::Eval(const std::unordered_map<VarPtr, SR> &valuation) const {
  Evaluator<SR> evaluator{valuation};
  node_->Accept(evaluator);
  return std::move(*evaluator.GetResult());
}

// FIXME: Matrix eval should store the valuation of the subtrees of FreeSemiring
// across different FreeSemirings accessed in the matrix...


class FreeSemiring : public Semiring<FreeSemiring>
{
public:
	VarPtr elem;
	std::shared_ptr<FreeSemiring> left_ptr;
	std::shared_ptr<FreeSemiring> right_ptr;
	enum optype {Element, Addition, Multiplication, Star, Dummy};
	enum optype type;
	static std::shared_ptr<FreeSemiring> elem_null;
	static std::shared_ptr<FreeSemiring> elem_one;

	FreeSemiring();
	FreeSemiring(int zero);
	FreeSemiring(VarPtr var);
	FreeSemiring(const FreeSemiring& term);
	FreeSemiring(optype type, FreeSemiring left);
	FreeSemiring(optype type, FreeSemiring left, FreeSemiring right);
	virtual ~FreeSemiring();
	FreeSemiring operator += (const FreeSemiring& term);<commit_msg>free-semiring: implement evaluation for matrices<commit_after>#ifndef FREE_SEMIRING_H
#define FREE_SEMIRING_H

#include <memory>
#include <string>
#include <unordered_map>

#include "matrix.h"
#include "semiring.h"
#include "var.h"

#include "free-structure.h"

template <typename SR>
class Evaluator;

class FreeSemiring2 : public Semiring<FreeSemiring2> {
  public:
    FreeSemiring2(const VarPtr var) {
      assert(var);
      InitFactory();
      assert(factory_);
      node_ = factory_->NewElement(var);
      assert(node_);
    }

    static FreeSemiring2 null() {
      InitFactory();
      assert(factory_);
      return FreeSemiring2{factory_->GetEmpty()};
    }

    static FreeSemiring2 one() {
      InitFactory();
      assert(factory_);
      return FreeSemiring2{factory_->GetEpsilon()};
    }

    FreeSemiring2 star() const {
      assert(factory_);
      return FreeSemiring2{factory_->NewStar(node_)};
    }

    FreeSemiring2 operator+(const FreeSemiring2 &x) {
      assert(factory_);
      return FreeSemiring2{factory_->NewAddition(node_, x.node_)};
    }

    FreeSemiring2 operator*(const FreeSemiring2 &x) {
      assert(factory_);
      return FreeSemiring2{factory_->NewMultiplication(node_, x.node_)};
    }

    bool operator==(const FreeSemiring2 &x) const {
      return node_ == x.node_;
    }

    std::string string() const {
      std::stringstream ss;
      ss << *node_;
      return ss.str();
    }

    template <typename SR>
    SR Eval(const std::unordered_map<VarPtr, SR> &valuation) const;

    template <typename SR>
    SR Eval(Evaluator<SR> &evaluator) const;

    void PrintDot(std::ostream &out) {
      assert(factory_);
      factory_->PrintDot(out);
    }

    void GC() {
      assert(factory_);
      factory_->GC();
    }

  private:
    FreeSemiring2(NodePtr n) : node_(n) { assert(factory_); }

    static void InitFactory() {
      if (factory_ == nullptr) {
        factory_ = std::move(std::unique_ptr<NodeFactory>(new NodeFactory));
      }
    }

    NodePtr node_;
    static std::unique_ptr<NodeFactory> factory_;

    friend struct std::hash<FreeSemiring2>;
};

namespace std {

template <>
struct hash<FreeSemiring2> {
  inline std::size_t operator()(const FreeSemiring2 &fs) const {
    std::hash<NodePtr> h;
    return h(fs.node_);
  }
};

}  /* namespace std */


/*
 * Evaluator
 *
 * We want to memoize the result of evaluating every subgraph, since we can
 * reach the same node (and thus the same subgraph) many times.  So only the
 * first one we will actually perform the computation, in all subsequent visits
 * we will reuse the memoized reslt.  Note that this is ok, because we never
 * modify the actual semiring values.  We use shared_ptrs to avoid any
 * unnecessary copying of temporary values, etc.
 */
template <typename SR>
class Evaluator : public NodeVisitor {
  typedef std::shared_ptr<SR> SRPtr_;
  public:
    Evaluator(const std::unordered_map<VarPtr, SR> &v)
        : val_(v), evaled_(), result_() {}

    void Visit(const Addition &a) {
      LookupEval(a.GetLhs());
      auto temp = std::move(result_);
      LookupEval(a.GetRhs());
      result_ = std::make_shared<SR>(*temp + *result_);
    }

    void Visit(const Multiplication &m) {
      LookupEval(m.GetLhs());
      auto temp = std::move(result_);
      LookupEval(m.GetRhs());
      result_ = std::make_shared<SR>(*temp * *result_);
    }

    void Visit(const Star &s) {
      LookupEval(s.GetNode());
      result_ = std::make_shared<SR>(result_->star());
    }

    void Visit(const Element &e) {
      auto iter = val_.find(e.GetVar());
      assert(iter != val_.end());
      result_ = std::make_shared<SR>(iter->second);
    }

    void Visit(const Epsilon &e) {
      result_ = std::make_shared<SR>(SR::one());
    }

    void Visit(const Empty &e) {
      result_ = std::make_shared<SR>(SR::null());
    }

    std::shared_ptr<SR> GetResult() {
      return result_;
    }

  private:
    void LookupEval(const NodePtr &node) {
      auto iter = evaled_.find(node);
      if (iter != evaled_.end()) {
        result_ = iter->second;
      } else {
        node->Accept(*this);  /* Sets the result_ correctly */
        evaled_.emplace(node, result_);
      }
    }

    const std::unordered_map<VarPtr, SR> &val_;
    std::unordered_map<NodePtr, SRPtr_> evaled_;
    SRPtr_ result_;
};

template <typename SR>
SR FreeSemiring2::Eval(const std::unordered_map<VarPtr, SR> &valuation) const {
  Evaluator<SR> evaluator{valuation};
  node_->Accept(evaluator);
  return std::move(*evaluator.GetResult());
}

template <typename SR>
SR FreeSemiring2::Eval(Evaluator<SR> &evaluator) const {
  node_->Accept(evaluator);
  return std::move(*evaluator.GetResult());
}

template <typename SR>
Matrix<SR> FreeSemiringMatrixEval(const Matrix<FreeSemiring2> &matrix,
    const std::unordered_map<VarPtr, SR> &valuation) {

  std::vector<FreeSemiring2> elements = matrix.getElements();
  std::vector<SR> result;

  /* We have a single Evaluator that is used for all evaluations of the elements
   * of the original matrix.  This way if different elements refer to the same
   * FreeSemiring subexpression, we memoize the result and reuse it. */
  Evaluator<SR> evaluator{valuation};

  for(auto &elem : elements) {
    result.emplace_back(elem.Eval(evaluator));
  }

  return Matrix<SR>(matrix.getRows(), matrix.getColumns(), std::move(result));
}


class FreeSemiring : public Semiring<FreeSemiring>
{
public:
	VarPtr elem;
	std::shared_ptr<FreeSemiring> left_ptr;
	std::shared_ptr<FreeSemiring> right_ptr;
	enum optype {Element, Addition, Multiplication, Star, Dummy};
	enum optype type;
	static std::shared_ptr<FreeSemiring> elem_null;
	static std::shared_ptr<FreeSemiring> elem_one;

	FreeSemiring();
	FreeSemiring(int zero);
	FreeSemiring(VarPtr var);
	FreeSemiring(const FreeSemiring& term);
	FreeSemiring(optype type, FreeSemiring left);
	FreeSemiring(optype type, FreeSemiring left, FreeSemiring right);
	virtual ~FreeSemiring();
	FreeSemiring operator += (const FreeSemiring& term);
{'fraction_non_alphanumeric': 0.12771255780860905, 'fraction_numerical': 0.00400213447171825, 'mean_word_length': 3.560016220600162, 'pattern_counts': {'":': 0, '<': 84, '<?xml version=': 0, '>': 107, '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': '5133962', 'n_tokens_mistral': 3650, 'n_tokens_neox': 3571, 'n_words': 876}