#ifndef LEMON_SIMANN_H

 #define LEMON_SIMANN_H

 #include <cstdlib>

 #include <cmath>

 #include <sys/time.h>

 namespace lemon {

   const double INFTY = 1e24;

   class SimAnnBase {

   public:

     class Controller;

   private:

     Controller *controller;

   protected:

     double curr_cost;

     double prev_cost;

     double best_cost;

     virtual void mutate() = 0;

     virtual void revert() = 0;

     virtual void saveAsBest() = 0;

   public:

     SimAnnBase() {

       curr_cost = prev_cost = best_cost = INFTY;

     }

     void setController(Controller &_controller) {

       controller = &_controller;

       controller->setBase(this);

     }

     double getCurrCost() { return curr_cost; }

     double getPrevCost() { return prev_cost; }

     double getBestCost() { return best_cost; }

     void run() {

       controller->init();

       while (controller->next()) {

         mutate();

         if (controller->accept()) {

           controller->acceptEvent();

           if (curr_cost < best_cost) {

             saveAsBest();

             controller->improveEvent();

           }

         }

         else {

           revert();

           controller->rejectEvent();

         }

       }

     }

     class Controller {

     public:

       SimAnnBase *base;

       virtual void init() {}

       virtual void acceptEvent() {}

       virtual void improveEvent() {}

       virtual void rejectEvent() {}

       virtual void setBase(SimAnnBase *_base) { base = _base; }

       virtual bool next() = 0;

       virtual bool accept() = 0;

     };

   };

   template <typename E>

   class SimAnn : public SimAnnBase {

   private:

     E *curr_ent;

     E *best_ent;

   public:

     SimAnn() : SimAnnBase() {}

     void setEntity(E &ent) {

       curr_ent = new E(ent);

       best_ent = new E(ent);

     }

     E getBestEntity() { return *best_ent; }

     void mutate() {

       curr_ent->mutate();

     }

     void revert() {

       curr_ent->revert();

     }

     void saveAsBest() {

       *best_ent = *curr_ent;

       best_cost = curr_cost;

     }

   };

   class EntitySkeleton {

   public:

     /*! \brief Makes a minor change to the entity.

      *  \return the new cost

      */

     double mutate() { return 0.0; }

     /*! \brief Restores the entity to its previous state i.e. reverts the

      *  effects of the last mutate.

      */

     void revert() {}

   };

   /*! \brief A simple controller for the simulated annealing class.

    *  \todo Find a way to set the various parameters.

    */

   class SimpleController : public SimAnnBase::Controller {

   public:

     long iter, last_impr, max_iter, max_no_impr;

     double temp, annealing_factor;

     SimpleController() {

       iter = last_impr = 0;

       max_iter = 500000;

       max_no_impr = 20000;

       annealing_factor = 0.9999;

       temp = 1000;

     }

     void acceptEvent() {

       iter++;

     }

     void improveEvent() {

       last_impr = iter;

     }

     void rejectEvent() {

       iter++;

     }

     bool next() {

       temp *= annealing_factor;

       bool quit = (iter > max_iter) || (iter - last_impr > max_no_impr);

       return !quit;

     }

     bool accept() {

       return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() /

         temp));

     }

   };

   /*! \brief A controller with preset running time for the simulated annealing

    *  class.

    *  \todo Find a better name.

    */

   class AdvancedController : public SimAnnBase::Controller {

   private:

     double threshold() { return 0.0; }

   public:

     double alpha;

     double temp;

     double avg_cost;

     double start_time, end_time;

     void init() {

       timeval tv;

       gettimeofday(&tv, 0);

       start_time = tv.tv_sec + double(tv.tv_usec) / 1e6;

     }

     void acceptEvent() {

       avg_cost = alpha * base->getCurrCost() + (1.0 - alpha) * avg_cost;

     }

     void improveEvent() {

     }

     void rejectEvent() {

     }

     bool next() {

       // abs(avg_cost - base->getBestCost())

       // ha nagy: cooling factor novelese

       // ha kicsi: homerseklet novelese

       // de mennyivel?

       timeval tv;

       gettimeofday(&tv, 0);

       double elapsed_time = tv.tv_sec + double(tv.tv_usec) / 1e6 - start_time;

       return elapsed_time < end_time;

     }

     bool accept() {

       return (drand48() <= exp(base->getPrevCost() - base->getCurrCost() /

         temp));

     }

   };

 }

 #endif