#ifndef FIXPOINT_ALGORITHM_HPP
#define FIXPOINT_ALGORITHM_HPP

#include "VariableAssignment.hpp"

template<typename T>
struct EquationSystem;
template<typename T>
struct MaxStrategy;

template<typename T>
struct FixpointAlgorithm {
  virtual VariableAssignment<T> maxFixpoint(const MaxStrategy<T>&, const EquationSystem<T>&) const = 0;
};

#include "EquationSystem.hpp"
#include "MaxStrategy.hpp"

template<typename T>
struct NaiveFixpoint : public FixpointAlgorithm<T> {
  virtual VariableAssignment<T> maxFixpoint(const MaxStrategy<T>& strat, const EquationSystem<T>& system) const {
    unsigned int size = system.varCount();
    VariableAssignment<T> newResult(size, infinity<T>());
    VariableAssignment<T> result(0);
    do {
      result = newResult;
      newResult = strat(system, result);
    } while (newResult != result);
    return result;
  }
};


template<typename T>
struct RecursiveFixpoint : public FixpointAlgorithm<T> {
  // this is a "VariableAssignment" which actually performs a recursive
  // call to determine what value to return
  struct EvaluatingVariableAssignment : public VariableAssignment<T> {
    EvaluatingVariableAssignment(const MaxStrategy<T>& strategy, const EquationSystem<T>& system)
      : VariableAssignment<T>(system.varCount(), infinity<T>()),
        _strategy(strategy), _system(system),
        _evaluating(NULL),
        _influence(system.varCount(), IdSet<Variable<T> >(system.varCount())),
        _stable(system.varCount()) {
    }
    virtual T& operator[] (const Variable<T>& x) const {
      if (_evaluating == NULL) {
        solve(x);
        return VariableAssignment<T>::_assignment[x.id()];
      } else {
        solve(x);
        _influence[x].insert(*_evaluating);
        return VariableAssignment<T>::_assignment[x.id()];
      }
    }
    void solve(const Variable<T>& x) const {
      if (!_stable.contains(x)) {
        _stable.insert(x);

        const Variable<T>* oldEval = _evaluating;
        _evaluating = &x;
        T t = _strategy(*_system[x], *this);
        _evaluating = oldEval;

        if (t != VariableAssignment<T>::_assignment[x.id()]) {
          IdSet<Variable<T> > oldInfluence = _influence[x];
          _influence[x].clear(); // clear out our idea of what x influences
          VariableAssignment<T>::_assignment[x.id()] = t;

          _stable.filter(oldInfluence); // whatever x influences needs to be re-evaluated

          for (typename IdSet<Variable<T> >::iterator it = oldInfluence.begin();
               it != oldInfluence.end();
               ++it) {
            solve(*_system.getVar(*it));
          }
        }
      }
    }
    private:
    const MaxStrategy<T>& _strategy;
    const EquationSystem<T>& _system;
    mutable const Variable<T>* _evaluating;
    mutable IdMap<Variable<T>, IdSet<Variable<T> > > _influence;
    mutable IdSet<Variable<T> > _stable;
  };

  virtual VariableAssignment<T> maxFixpoint(const MaxStrategy<T>& strat, const EquationSystem<T>& system) const {
    EvaluatingVariableAssignment assignment(strat, system);
    VariableAssignment<T> result(system.varCount());
    for (unsigned int i = 0; i < system.varCount(); ++i) {
      result[*system.getVar(i)] = assignment[*system.getVar(i)];
    }
    return result;
  }
};

#endif