statemanager.hh

Go to the documentation of this file.

#if !defined(_STATE_MANAGER_HH_)
#define _STATE_MANAGER_HH_

#include <iostream>
#include <vector>
#include <cmath>
#include <stdexcept>

#include "easylocal/helpers/costcomponent.hh"
#include "easylocal/utils/types.hh"

namespace EasyLocal {
  
  namespace Core {
    
    template <typename CFtype>
    struct CostStructure
    {
      CostStructure() : total(0), violations(0), objective(0), all_components(0), weighted(0.0), is_weighted(false) {}
      CostStructure(CFtype total, CFtype violations, CFtype objective, const std::vector<CFtype>& all_components) : total(total), violations(violations), objective(objective), all_components(all_components), weighted(total), is_weighted(false) {}
      CostStructure(CFtype total, double weighted, CFtype violations, CFtype objective, const std::vector<CFtype>& all_components) : total(total), violations(violations), objective(objective), all_components(all_components), weighted(weighted), is_weighted(true) {}
      
      
      CFtype total, violations, objective;
      std::vector<CFtype> all_components;
      double weighted;
      
      bool is_weighted;
      
      CostStructure& operator+=(const CostStructure& other)
      {
        this->total += other.total;
        this->violations += other.violations;
        this->objective += other.objective;
        if (this->all_components.size() < other.all_components.size())
          this->all_components.resize(other.all_components.size(), 0);
        for (size_t i = 0; i < other.all_components.size(); i++)
          this->all_components[i] += other.all_components[i];
        return *this;
      }
      
      CostStructure& operator-=(const CostStructure& other)
      {
        this->total -= other.total;
        this->violations -= other.violations;
        this->objective -= other.objective;
        if (this->all_components.size() < other.all_components.size())
          this->all_components.resize(other.all_components.size(), 0);
        for (size_t i = 0; i < other.all_components.size(); i++)
          this->all_components[i] -= other.all_components[i];
        return *this;
      }
      
      explicit operator double() const
      {
        if (is_weighted)
          return weighted;
        else
          return (double)total;
      }      
    };
    
    template <typename CFtype>
    CostStructure<CFtype> operator+(const CostStructure<CFtype>& cs1, const CostStructure<CFtype>& cs2)
    {
      CostStructure<CFtype> res = cs1;
      res += cs2;
      return res;
    }
    
    template <typename CFtype>
    CostStructure<CFtype> operator-(const CostStructure<CFtype>& cs1, const CostStructure<CFtype>& cs2)
    {
      CostStructure<CFtype> res = cs1;
      res -= cs2;
      return res;
    }
    
    template <class CFtype>
    bool operator<(const CostStructure<CFtype>& cs1, const CostStructure<CFtype>& cs2)
    {
      if (cs1.is_weighted && cs2.is_weighted)
        return LessThan(cs1.weighted, cs2.weighted);
      return LessThan(cs1.total, cs2.total);
    }
    
    template <class CFtype>
    bool operator<(CFtype c1, const CostStructure<CFtype>& cs2)
    {
      if (cs2.is_weighted)
        return LessThan((double)c1, cs2.weighted);
      return LessThan(c1, cs2.total);
    }
    
    template <class CFtype>
    bool operator<(const CostStructure<CFtype>& cs1, CFtype c2)
    {
      if (cs1.is_weighted)
        return LessThan(cs1.weighted, (double)c2);
      return LessThan(cs1.total, c2);
    }
    
    template <class CFtype, typename OtherType>
    bool operator<(OtherType c1, const CostStructure<CFtype>& cs2)
    {
      if (cs2.is_weighted)
        return LessThan((double)c1, cs2.weighted);
      return LessThan((CFtype)c1, cs2.total);
    }
    
    template <class CFtype, typename OtherType>
    bool operator<(const CostStructure<CFtype>& cs1, OtherType c2)
    {
      if (cs1.is_weighted)
        return LessThan(cs1.weighted, (double)c2);
      return LessThan(cs1.total, (CFtype)c2);
    }
    
    template <class CFtype>
    bool operator<=(const CostStructure<CFtype>& cs1, const CostStructure<CFtype>& cs2)
    {
      if (cs1.is_weighted && cs2.is_weighted)
        return LessThanOrEqualTo(cs1.weighted, cs2.weighted);
      return LessThanOrEqualTo(cs1.total, cs2.total);
    }
    
    template <class CFtype>
    bool operator<=(CFtype c1, const CostStructure<CFtype>& cs2)
    {
      if (cs2.is_weighted)
        return LessThanOrEqualTo((double)c1, cs2.weighted);
      return LessThanOrEqualTo(c1, cs2.total);
    }
    
    template <class CFtype>
    bool operator<=(const CostStructure<CFtype>& cs1, CFtype c2)
    {
      if (cs1.is_weighted)
        return LessThanOrEqualTo(cs1.weighted, (double)c2);
      return LessThanOrEqualTo(cs1.total, c2);
    }
    
    template <class CFtype, typename OtherType>
    bool operator<=(OtherType c1, const CostStructure<CFtype>& cs2)
    {
      if (cs2.is_weighted)
        return LessThanOrEqualTo((double)c1, cs2.weighted);
      return LessThanOrEqualTo((CFtype)c1, cs2.total);
    }
    
    template <class CFtype, typename OtherType>
    bool operator<=(const CostStructure<CFtype>& cs1, OtherType c2)
    {
      if (cs1.is_weighted)
        return LessThanOrEqualTo(cs1.weighted, (double)c2);
      return LessThanOrEqualTo(cs1.total, (CFtype)c2);
    }
    
    template <class CFtype>
    bool operator==(const CostStructure<CFtype>& cs1, const CostStructure<CFtype>& cs2)
    {
      if (cs1.is_weighted && cs2.is_weighted)
        return EqualTo(cs1.weighted, cs2.weighted);
      return EqualTo(cs1.total, cs2.total);
    }
    
    template <class CFtype>
    bool operator==(CFtype c1, const CostStructure<CFtype>& cs2)
    {
      if (cs2.is_weighted)
        return EqualTo((double)c1, cs2.weighted);
      return EqualTo(c1, cs2.total);
    }
    
    template <class CFtype>
    bool operator==(const CostStructure<CFtype>& cs1, CFtype c2)
    {
      if (cs1.is_weighted)
        return EqualTo(cs1.weighted, (double)c2);
      return EqualTo(cs1.total, c2);
    }
    
    template <class CFtype, typename OtherType>
    bool operator==(OtherType c1, const CostStructure<CFtype>& cs2)
    {
      if (cs2.is_weighted)
        return EqualTo((double)c1, cs2.weighted);
      return EqualTo((CFtype)c1, cs2.total);
    }
    
    template <class CFtype, typename OtherType>
    bool operator==(const CostStructure<CFtype>& cs1, OtherType c2)
    {
      if (cs1.is_weighted)
        return EqualTo(cs1.weighted, (double)c2);
      return EqualTo(cs1.total, (CFtype)c2);
    }
    
    template <class CFtype>
    bool operator>=(const CostStructure<CFtype>& cs1, const CostStructure<CFtype>& cs2)
    {
      if (cs1.is_weighted && cs2.is_weighted)
        return GreaterThanOrEqualTo(cs1.weighted, cs2.weighted);
      return GreaterThanOrEqualTo(cs1.total, cs2.total);
    }
    
    template <class CFtype>
    bool operator>=(CFtype c1, const CostStructure<CFtype>& cs2)
    {
      if (cs2.is_weighted)
        return GreaterThanOrEqualTo((double)c1, cs2.weighted);
      return GreaterThanOrEqualTo(c1, cs2.total);
    }
    
    template <class CFtype>
    bool operator>=(const CostStructure<CFtype>& cs1, CFtype c2)
    {
      if (cs1.is_weighted)
        return GreaterThanOrEqualTo(cs1.weighted, (double)c2);
      return GreaterThanOrEqualTo(cs1.total, c2);
    }
    
    template <class CFtype, typename OtherType>
    bool operator>=(OtherType c1, const CostStructure<CFtype>& cs2)
    {
      if (cs2.is_weighted)
        return GreaterThanOrEqualTo((double)c1, cs2.weighted);
      return GreaterThanOrEqualTo((CFtype)c1, cs2.total);
    }
    
    template <class CFtype, typename OtherType>
    bool operator>=(const CostStructure<CFtype>& cs1, OtherType c2)
    {
      if (cs1.is_weighted)
        return GreaterThanOrEqualTo(cs1.weighted, (double)c2);
      return GreaterThanOrEqualTo(cs1.total, (CFtype)c2);
    }
    
    template <class CFtype>
    bool operator>(const CostStructure<CFtype>& cs1, const CostStructure<CFtype>& cs2)
    {
      if (cs1.is_weighted && cs2.is_weighted)
        return GreaterThan(cs1.weighted, cs2.weighted);
      return GreaterThan(cs1.total, cs2.total);
    }
    
    template <class CFtype>
    bool operator>(CFtype c1, const CostStructure<CFtype>& cs2)
    {
      if (cs2.is_weighted)
        return GreaterThan((double)c1, cs2.weighted);
      return GreaterThan(c1, cs2.total);
    }
    
    template <class CFtype>
    bool operator>(const CostStructure<CFtype>& cs1, CFtype c2)
    {
      if (cs1.is_weighted)
        return GreaterThan(cs1.weighted, (double)c2);
      return GreaterThan(cs1.total, c2);
    }
    
    template <class CFtype, typename OtherType>
    bool operator>(OtherType c1, const CostStructure<CFtype>& cs2)
    {
      if (cs2.is_weighted)
        return GreaterThan((double)c1, cs2.weighted);
      return GreaterThan((CFtype)c1, cs2.total);
    }
    
    template <class CFtype, typename OtherType>
    bool operator>(const CostStructure<CFtype>& cs1, OtherType c2)
    {
      if (cs1.is_weighted)
        return GreaterThan(cs1.weighted, (double)c2);
      return GreaterThan(cs1.total, (CFtype)c2);
    }
    
    template <class CFtype>
    bool operator!=(const CostStructure<CFtype>& cs1, const CostStructure<CFtype>& cs2)
    {
      if (cs1.is_weighted && cs2.is_weighted)
        return !EqualTo(cs1.weighted, cs2.weighted);
      return !EqualTo(cs1.total, cs2.total);
    }
    
    template <class CFtype>
    bool operator!=(CFtype c1, const CostStructure<CFtype>& cs2)
    {
      if (cs2.is_weighted)
        return !EqualTo((double)c1, cs2.weighted);
      return !EqualTo(c1, cs2.total);
    }
    
    template <class CFtype>
    bool operator!=(const CostStructure<CFtype>& cs1, CFtype c2)
    {
      if (cs1.is_weighted)
        return !EqualTo(cs1.weighted, (double)c2);
      return !EqualTo(cs1.total, c2);
    }
    
    template <class CFtype, typename OtherType>
    bool operator!=(OtherType c1, const CostStructure<CFtype>& cs2)
    {
      if (cs2.is_weighted)
        return !EqualTo((double)c1, cs2.weighted);
      return !EqualTo((CFtype)c1, cs2.total);
    }
    
    template <class CFtype, typename OtherType>
    bool operator!=(const CostStructure<CFtype>& cs1, OtherType c2)
    {
      if (cs1.is_weighted)
        return !EqualTo(cs1.weighted, (double)c2);
      return !EqualTo(cs1.total, (CFtype)c2);
    }
    
    template <typename CFtype>
    std::ostream& operator<<(std::ostream& os, const CostStructure<CFtype>& cc)
    {
      os << cc.total << " (viol: " << cc.violations << ", obj: " << cc.objective << ", comps: {";
      for (size_t i = 0; i < cc.all_components.size(); i++)
      {
        if (i > 0)
          os << ", ";
        os << cc.all_components[i];
      }
      os << "})";
      
      return os;
    }
    
    
#if !defined(HARD_WEIGHT_SET)
    const int HARD_WEIGHT = 1000;
#define HARD_WEIGHT_SET
#endif
    
    template <class Input, class State, typename CFtype = int>
    class StateManager : public Printable
    {
    public:
      
      void Print(std::ostream& os = std::cout) const;
      
      virtual void RandomState(State &st) = 0;
      
      virtual CostStructure<CFtype> SampleState(State &st, unsigned int samples);
      
      virtual void GreedyState(State &st, double alpha, unsigned int k);
      
      virtual void GreedyState(State &st);
      
      virtual CostStructure<CFtype> CostFunctionComponents(const State& st, const std::vector<double>& weights = std::vector<double>(0)) const;
      
      virtual bool LowerBoundReached(const CFtype& fvalue) const;
      
      virtual bool OptimalStateReached(const State& st) const;
      
      void AddCostComponent(CostComponent<Input, State, CFtype>& cc);
      
      
      void ClearCostStructure();
      
      virtual unsigned int StateDistance(const State& st1, const State& st2) const;
      
      
      virtual bool CheckConsistency(const State& st) const = 0;
      
      const std::string name;
      
    protected:
      StateManager(const Input& in, std::string name);
      
      virtual ~StateManager() {}
      
      std::vector<CostComponent<Input, State, CFtype>*> cost_component;
      
      const Input& in;
    };
    
    /* **************************************************************************
     * Implementation
     * **************************************************************************/
    
    template <class Input, class State, typename CFtype>
    StateManager<Input, State, CFtype>::StateManager(const Input& in, std::string name)
    :  name(name), in(in)
    {}
    
    template <class Input, class State, typename CFtype>
    void StateManager<Input, State, CFtype>::Print(std::ostream& os) const
    {
      os  << "State Manager: " + name << std::endl;
      os  << "Violations:" << std::endl;
      for (unsigned int i = 0; i < cost_component.size(); i++)
        if (cost_component[i]->IsHard())
          cost_component[i]->Print(os);
      os  << "Objective:" << std::endl;
      for (unsigned int i = 0; i < cost_component.size(); i++)
        if (cost_component[i]->IsSoft())
          cost_component[i]->Print(os);
    }
    
    template <class Input, class State, typename CFtype>
    CostStructure<CFtype> StateManager<Input, State, CFtype>::SampleState(State &st,
                                                           unsigned int samples)
    {
      unsigned int s = 1;
      RandomState(st);
      CostStructure<CFtype> cost = CostFunctionComponents(st);
      State best_state(in);
      best_state = st;
      CostStructure<CFtype> best_cost = cost;
      while (s < samples)
      {
        RandomState(st);
        cost = CostFunctionComponents(st);
        if (cost < best_cost)
        {
          best_state = st;
          best_cost = cost;
        }
        s++;
      }
      st = best_state;
      return best_cost;
    }
    
    template <class Input, class State, typename CFtype>
    void StateManager<Input, State, CFtype>::GreedyState(State &st, double alpha,
                                                         unsigned int k)
    {
      GreedyState(st);
    }
    
    template <class Input, class State, typename CFtype>
    void StateManager<Input, State, CFtype>::GreedyState(State &st)
    {
      throw std::runtime_error("For using this feature GreedyState must be implemented in the concrete class!");
    }
    
    template <class Input, class State, typename CFtype>
    CostStructure<CFtype> StateManager<Input, State, CFtype>::CostFunctionComponents(const State& st, const std::vector<double>& weights) const
    {
      CFtype hard_cost = 0, soft_cost = 0;
      double weighted_cost = 0.0;
      std::vector<CFtype> cost_function(CostComponent<Input, State, CFtype>::CostComponents(), (CFtype)0);
      for (size_t i = 0; i < cost_component.size(); i++)
      {
        CFtype current_cost = cost_function[cost_component[i]->Index()] = cost_component[i]->Cost(st);
        if (cost_component[i]->IsHard())
        {
          hard_cost += current_cost;
          if (!weights.empty())
            weighted_cost += HARD_WEIGHT * weights[cost_component[i]->Index()] * current_cost;
        }
        else
        {
          soft_cost += current_cost;
          if (!weights.empty())
            weighted_cost += weights[cost_component[i]->Index()] * current_cost;
        }
      }
      
      if (!weights.empty())
        return CostStructure<CFtype>(HARD_WEIGHT * hard_cost + soft_cost, weighted_cost, hard_cost, soft_cost, cost_function);
      else
        return CostStructure<CFtype>(HARD_WEIGHT * hard_cost + soft_cost, hard_cost, soft_cost, cost_function);
    }
    
    template <class Input, class State, typename CFtype>
    bool StateManager<Input, State, CFtype>::LowerBoundReached(const CFtype& fvalue) const
    {
      return IsZero(fvalue);
    }
    
    template <class Input, class State, typename CFtype>
    bool StateManager<Input, State, CFtype>::OptimalStateReached(const State& st) const
    {
      return LowerBoundReached(CostFunctionComponents(st).total);
    }
    
    template <class Input, class State, typename CFtype>
    void StateManager<Input, State, CFtype>::AddCostComponent(CostComponent<Input, State, CFtype>& cc)
    {
      cost_component.push_back(&cc);
    }    
    
    template <class Input, class State, typename CFtype>
    unsigned int StateManager<Input, State, CFtype>::StateDistance(const State& st1,
                                                                   const State& st2) const
    {
      throw std::runtime_error("For using this feature StateDistance must be implemented in the concrete class!");
      return 0;
    }
  }
}

#endif // _STATE_MANAGER_HH_