Initial commit. Basic Kleene iteration stuff.

11 files changed, 249 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..7fc71cc
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1 @@
+/a.out
diff --git a/Constant.h b/Constant.h
new file mode 100644
index 0000000..bab8cd9
--- /dev/null
+++ b/Constant.h
@@ -0,0 +1,22 @@
+#ifndef CONSTANT_H
+#define CONSTANT_H
+
+#include "Expression.h"
+
+template<class T>
+struct Constant : public Expression<T> {
+  Constant(const T& value) : _value(value) { }
+
+  T value() const {
+    return this->_value;
+  }
+
+  T eval(const std::map<std::string, T>&) const {
+    return _value;
+  }
+
+  private:
+  const T _value;
+};
+
+#endif
diff --git a/Equation.h b/Equation.h
new file mode 100644
index 0000000..b861768
--- /dev/null
+++ b/Equation.h
@@ -0,0 +1,47 @@
+#ifndef EQUATION_H
+#define EQUATION_H
+
+#include "Variable.h"
+#include "Expression.h"
+#include <map>
+#include <string>
+
+template<class T>
+struct Equation {
+  Equation(const Variable<T>& var, Expression<T>* value)
+    : _var(var), _value(value) { }
+
+  Variable<T> var() const {
+    return _var;
+  }
+  Variable<T> var(const Variable<T>& var) {
+    Variable<T> old_var = _var;
+    _var = var;
+    return _var;
+  }
+
+  Expression<T>* value() const {
+    return _value;
+  }
+  Expression<T>* value(const Expression<T>* value) {
+    Expression<T>* old_value = _value;
+    _value = value;
+    return old_value;
+  }
+
+  std::map<std::string, T> solve(const std::map<std::string, T>& curr) {
+    std::map<std::string, T> result = curr;
+    T last;
+    do {
+      last = result[_var.name()];
+      result[_var.name()] = _value->eval(result);
+    } while (last != result[_var.name()]);
+    return result;
+  }
+
+  private:
+  Variable<T> _var;
+  Expression<T>* _value;
+};
+
+#endif
diff --git a/EquationSystem.h b/EquationSystem.h
new file mode 100644
index 0000000..9a393c8
--- /dev/null
+++ b/EquationSystem.h
@@ -0,0 +1,40 @@
+#ifndef EQUATIONSYSTEM_H
+#define EQUATIONSYSTEM_H
+
+#include "Equation.h"
+#include <list>
+
+template<class T>
+struct EquationSystem {
+  bool add(Equation<T> e) {
+    for (iterator it = equations.begin();
+         it != equations.end();
+         ++it) {
+      if ((*it).var().name() == e.var().name()) {
+        return false;
+      }
+    }
+    this->equations.push_back(e);
+    return true;
+  }
+
+  std::map<std::string, T> solve(std::map<std::string, T> start) {
+    std::map<std::string, T> result = start;
+    std::map<std::string, T> comparison;
+    do {
+      comparison = result;
+      for (iterator it = equations.begin();
+           it != equations.end();
+           ++it) {
+        result = it->solve(result);
+      }
+    } while (comparison != result);
+    return result;
+  }
+
+  private:
+  typedef typename std::list< Equation<T> >::iterator iterator;
+  std::list< Equation<T> > equations;
+};
+
+#endif
diff --git a/Expression.h b/Expression.h
new file mode 100644
index 0000000..105ad28
--- /dev/null
+++ b/Expression.h
@@ -0,0 +1,12 @@
+#ifndef EXPRESSION_H
+#define EXPRESSION_H
+
+#include <string>
+#include <map>
+
+template<class T>
+struct Expression {
+  virtual T eval(const std::map<std::string, T>&) const = 0;
+};
+
+#endif
diff --git a/Max.h b/Max.h
new file mode 100644
index 0000000..b3b5d65
--- /dev/null
+++ b/Max.h
@@ -0,0 +1,22 @@
+#ifndef MAX_H
+#define MAX_H
+
+#include "Expression.h"
+
+template<class T>
+struct Max : public Expression<T> {
+  Max(Expression<T>* left, Expression<T>* right)
+    : _left(left), _right(right) { }
+
+  T eval(const std::map<std::string, T>& mappings) const {
+    T left = _left->eval(mappings);
+    T right = _right->eval(mappings);
+    return left < right ? right : left;
+  }
+  
+  private:
+  Expression<T>* _left;
+  Expression<T>* _right;
+};
+
+#endif
diff --git a/Min.h b/Min.h
new file mode 100644
index 0000000..9f17545
--- /dev/null
+++ b/Min.h
@@ -0,0 +1,22 @@
+#ifndef MIN_H
+#define MIN_H
+
+#include "Expression.h"
+
+template<class T>
+struct Min : public Expression<T> {
+  Min(Expression<T>* left, Expression<T>* right)
+    : _left(left), _right(right) { }
+
+  T eval(const std::map<std::string, T>& mappings) const {
+    T left = _left->eval(mappings);
+    T right = _right->eval(mappings);
+    return left < right ? left : right;
+  }
+  
+  private:
+  Expression<T>* _left;
+  Expression<T>* _right;
+};
+
+#endif
diff --git a/Sum.h b/Sum.h
new file mode 100644
index 0000000..bf04669
--- /dev/null
+++ b/Sum.h
@@ -0,0 +1,22 @@
+#ifndef SUM_H
+#define SUM_H
+
+#include "Expression.h"
+
+template<class T>
+struct Sum : public Expression<T> {
+  Sum(Expression<T>* left, Expression<T>* right)
+    : _left(left), _right(right) { }
+
+  T eval(const std::map<std::string, T>& mappings) const {
+    T left = _left->eval(mappings);
+    T right = _right->eval(mappings);
+    return left + right;
+  }
+  
+  private:
+  Expression<T>* _left;
+  Expression<T>* _right;
+};
+
+#endif
diff --git a/Term.h b/Term.h
new file mode 100644
index 0000000..8b13789
--- /dev/null
+++ b/Term.h
@@ -0,0 +1 @@
+
diff --git a/Variable.h b/Variable.h
new file mode 100644
index 0000000..7433426
--- /dev/null
+++ b/Variable.h
@@ -0,0 +1,24 @@
+#ifndef VARIABLE_H
+#define VARIABLE_H
+
+#include <string>
+#include "Expression.h"
+
+template<class T>
+struct Variable : public Expression<T> {
+  Variable(const std::string& name)
+    : _name(name) { }
+
+  std::string name() const {
+    return this->_name;
+  }
+
+  T eval(const std::map<std::string, T>& values) const {
+    return values.find(_name)->second;
+  }
+
+  private:
+  const std::string _name;
+};
+
+#endif
diff --git a/main.cpp b/main.cpp
new file mode 100644
index 0000000..814a3ee
--- /dev/null
+++ b/main.cpp
@@ -0,0 +1,36 @@
+#include "Constant.h"
+#include "Variable.h"
+#include "Min.h"
+#include "Max.h"
+#include "Sum.h"
+#include "Equation.h"
+#include "EquationSystem.h"
+
+#include <iostream>
+
+using namespace std;
+
+int main() {
+  std::map<std::string, int> mappings;
+  mappings["x"] = 10;
+
+  Equation<int> e(Variable<int>("x"),
+    new Max<int>(
+      new Min<int>(
+        new Constant<int>(100),
+        new Sum<int>(
+          new Variable<int>("x"),
+          new Constant<int>(100))),
+      new Constant<int>(20)));
+
+  Equation<int> e2(Variable<int>("x"),
+    new Constant<int>(200));
+
+  EquationSystem<int> es;
+  es.add(e);
+  es.add(e2);
+  std::map<std::string, int> result = es.solve(mappings);
+  cout << result["x"] << endl;
+
+  return 0;
+}