#ifndef FIXPOINT_ALGORITHM_HPP
#define FIXPOINT_ALGORITHM_HPP

#include "IdSet.hpp"
#include "IdMap.hpp"
#include "VariableAssignment.hpp"
#include "EquationSystem.hpp"

template<typename Domain>
struct FixpointAlgorithm {
  virtual ~FixpointAlgorithm() { }
  virtual void maxFixpoint(
      const EquationSystem<Domain>& system,
      StableVariableAssignment<Domain>& rho,
      IdSet<Variable<Domain> >& changedIn,
      IdSet<Variable<Domain> >& changedOut
  ) = 0;
};

template<typename Domain>
struct NaiveFixpointAlgorithm : public FixpointAlgorithm<Domain> {
  NaiveFixpointAlgorithm(const EquationSystem<Domain>& system)
    : _system(system) { }
  virtual void maxFixpoint(
      const EquationSystem<Domain>& system,
      StableVariableAssignment<Domain>& rhoOut,
      IdSet<Variable<Domain> >& changedIn,
      IdSet<Variable<Domain> >& changedOut
  ) {
    VariableAssignment<Domain>* rho = NULL;
    VariableAssignment<Domain>* result = system.assignment(infinity<Domain>());
    do {
      if (rho) delete rho;
      rho = result;
      result = _system.eval(*rho);
    } while (!_system.equalAssignments(*rho, *result));
    if (rho) delete rho;

    for (unsigned int i = 0, length = system.variableCount(); i < length; ++i) {
      Variable<Domain> var = system.variable(i);
      rhoOut[var] = (*result)[var];
    }
  }
  private:
  const EquationSystem<Domain>& _system;
};

template<typename Domain>
struct SmartFixpointAlgorithm : public FixpointAlgorithm<Domain> {
  SmartFixpointAlgorithm(const EquationSystem<Domain>& system)
    : _system(system),
      _influence(system.variableCount(), IdSet<Variable<Domain> >(system.variableCount())){
  }

  struct DynamicVariableAssignment : public VariableAssignment<Domain> {
    DynamicVariableAssignment(
      const EquationSystem<Domain>& system,
      IdMap<Variable<Domain>,IdSet<Variable<Domain> > >& influence,
      StableVariableAssignment<Domain>& rho,
      IdSet<Variable<Domain> >& stable,
      IdSet<Variable<Domain> >& changed
    ) : _system(system),
        _values(rho),
        _stable(stable),
        _changed(changed),
        _influence(influence) { }

    const Domain& operator[](const Variable<Domain>& var) const {
      solve(var);
      return _values[var];
    }

    private:

    void solve(const Variable<Domain>& x) const {
      if (!_stable.contains(x)) {
        _stable.insert(x);

        Domain val = _system[x]->eval(DependencyAssignment(*this, x));

        if (val != _values[x]) {
          IdSet<Variable<Domain> > oldInfluence = _influence[x];
          _influence[x].clear();
          _values[x] = val;
          _changed.insert(x);

          _stable.filter(oldInfluence);

          for (typename IdSet<Variable<Domain> >::iterator it = oldInfluence.begin();
               it != oldInfluence.end();
               ++it) {
            solve(_system.variable(*it));
          }
          _influence[x] = oldInfluence;
        }
      }
    }

    struct DependencyAssignment : public VariableAssignment<Domain> {
      DependencyAssignment(const DynamicVariableAssignment& assignment, const Variable<Domain>& var)
        : _assignment(assignment), _var(var) { }
      const Domain& operator[](const Variable<Domain>& x) const {
        const Domain& result = _assignment[x];
        _assignment._influence[x].insert(_var);
        return result;
      }
      private:
      const DynamicVariableAssignment& _assignment;
      const Variable<Domain>& _var;
    };

    const EquationSystem<Domain>& _system;
    StableVariableAssignment<Domain>& _values;
    IdSet<Variable<Domain> >& _stable;
    IdSet<Variable<Domain> >& _changed;
    IdMap<Variable<Domain>,IdSet<Variable<Domain> > >& _influence;
  };

  void invalidate(const IdSet<Variable<Domain> >& set, IdSet<Variable<Domain> >& changed, StableVariableAssignment<Domain>& rho) const {
    for (typename IdSet<Variable<Domain> >::iterator it = set.begin(),
                                                     end = set.end();
         it != end;
         ++it) {
      Variable<Domain>& var = _system.variable(*it);
      if (!changed.contains(var)) {
        rho[var] = infinity<Domain>();
        changed.insert(var);
        invalidate(_influence[var], changed, rho);
      }
    }
  }

  virtual void maxFixpoint(
      const EquationSystem<Domain>& system,
      StableVariableAssignment<Domain>& rhoOut,
      IdSet<Variable<Domain> >& changedIn,
      IdSet<Variable<Domain> >& changedOut
  ) {
    for (typename IdSet<Variable<Domain> >::iterator it = changedIn.begin(),
                                                     end = changedIn.end();
         it != end;
         ++it) {
      //std::cout << *it << " ";
      Variable<Domain>& var = _system.variable(*it);
      rhoOut[var] = infinity<Domain>();
      invalidate(_influence[var], changedIn, rhoOut);
    }

    changedIn.invert();
    DynamicVariableAssignment rho(system, _influence, rhoOut, changedIn, changedOut);
    for (unsigned int i = 0, length = system.variableCount(); i < length; ++i) {
      rho[system.variable(i)];
    }
    /*std::cout << _influence << std::endl;
    std::cout << std::endl;*/
  }
  private:
  const EquationSystem<Domain>& _system;
  IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence;
};

#endif