/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2006
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */


#ifndef LEMON_TABU_SEARCH_H
#define LEMON_TABU_SEARCH_H

/// \ingroup experimental
/// \file
/// \brief TabuSearch algorithm.
///
/// \author Szabadkai Mark

#include <lemon/bits/utility.h>
#include <lemon/error.h>
#include <lemon/time_measure.h>
#include <functional>
#include <deque>


namespace lemon {

  /// \brief Default Traits for TabuSearch class.
  /// 
  /// This template defines the needed types for the \ref TabuSearch class.
  /// Is main purpos is to simplify the main class's template interface,
  /// but it provides the EdgeIt type, passing to the concrete graph wheter
  /// it is directed or undirected.
#ifdef DOXYGEN
  template< typename GRAPH, typename VALUE, 
            typename HEIGHTMAP, typename BETTER, bool UNDIR >
#else
  template< typename GRAPH, typename VALUE,
            typename HEIGHTMAP = typename GRAPH::template NodeMap<VALUE>,
            typename BETTER = std::less<VALUE>,
            bool UNDIR = UndirectedTagIndicator<GRAPH>::value >
#endif
  struct TabuSearchDefaultTraits {
    typedef  VALUE  Value; 
    typedef  BETTER  Better;

    typedef  GRAPH  Graph;
    typedef  typename GRAPH::Node  Node;
    typedef  HEIGHTMAP  HeightMap;

    typedef  typename GRAPH::IncEdgeIt  EdgeIt;
  };

  template< typename GRAPH, typename VALUE, 
            typename HEIGHTMAP, typename BETTER >
  struct TabuSearchDefaultTraits< GRAPH, VALUE, HEIGHTMAP, BETTER, false > {
    typedef  VALUE  Value;
    typedef  BETTER  Better;

    typedef  GRAPH  Graph;
    typedef  typename GRAPH::Node  Node;
    typedef  HEIGHTMAP  HeightMap;

    typedef  typename GRAPH::OutEdgeIt  EdgeIt;
  };



  /// \brief Policy hierarchy to controll the search algorithm.
  ///
  /// The fallowing template hierarchy offers a clean interface to define own
  /// policies, and combine existing ones.
  template< typename TS >
  struct TabuSearchPolicyConcept {
    void  target( TS *ts ) {}

    void  reset()  {}
    bool  onStep() { return false; }
    bool  onStick() { return false; }
    bool  onImprove( const typename TS::Value &best ) { return false; }
  };

  template< typename TS >
  struct YesPolicy {
    void  target( TS *ts ) {}

    void  reset()  {}
    bool  onStep() { return true; }
    bool  onStick() { return true; }
    bool  onImprove( const typename TS::Value &best ) { return true; }
  };

  template< typename TS >
  struct NoPolicy : public TabuSearchPolicyConcept<TS> {};

  /// \brief Some basic methode, how tow Policies can be combined
  struct PolicyAndCombination {
    static bool  evaluate( const bool r1, const bool r2 ) {
      return r1 && r2;
    }
  };

  struct PolicyOrCombination {
    static bool  evaluate( const bool r1, const bool r2 ) {
      return r1 || r2;
    }
  };

  /// \brief CombinePolicies
  ///
  /// It combines tow policies using the given combination methode (mainly
  /// some of the basic logical methodes) to create a new one.
#ifdef DOXYGEN
  template< template<typename> class CP1, template<typename> class CP2, 
            typename COMBINATION >
#else
  template< template<typename> class CP1, template<typename> class CP2,
            typename COMBINATION = PolicyAndCombination >
#endif
  struct CombinePolicies {
    template< typename TS >
    struct Policy {
      typedef CP1<TS>  Policy1;
      typedef CP2<TS>  Policy2;
      
      Policy1  policy1;
      Policy2  policy2;

      inline Policy() : policy1(), policy2() {}
      inline Policy( const Policy1 &cp1, const Policy2 &cp2 ) 
        : policy1(cp1), policy2(cp2) {}

      void  target( TS *ts ) {
        policy1.target(ts), policy2.target(ts);
      };

      void  reset() {
        policy1.reset(), policy2.reset();
      }

      bool  onStep() {
        return cmb.evaluate( policy1.onStep(), policy2.onStep() );
      }

      bool  onStick() {
        return cmb.evaluate( policy1.onStick(), policy2.onStick() );
      }

      bool  onImprove( const typename TS::Value &best ) {
        return cmb.evaluate( policy1.onImprove(best), 
                             policy2.onImprove(best) );
      }

    private:
      COMBINATION cmb;
    };
  };


  /// \brief IterationPolicy limits the number of iterations and the
  /// number of iterations without improvement
  template< typename TS >
  struct IterationPolicy {
    IterationPolicy() : _it_lim(100000), _noimpr_it_lim(5000) {}
    IterationPolicy( const long int itl, const long int noimpritl )
      : _it_lim(itl), _noimpr_it_lim(noimpritl)
    {}

    void  target( TS *ts ) {}

    void  reset() {
      _it = _noimpr_it = 0;
    }

    bool  onStep() {
      ++_it; ++_noimpr_it;
      return (_it <= _it_lim) && (_noimpr_it <= _noimpr_it_lim);
    }
		
    bool  onStick() {
      return false;
    }

    bool  onImprove( const typename TS::Value &best ) {
      _noimpr_it = 0;
      return true;
    }

    long int  iterationLimit() const {
      return _it_lim;
    }

    void  iterationLimit( const long int itl ) {
      _it_lim = itl;
    }

    long int  noImprovementIterationLimit() const {
      return _noimpr_it_lim;
    }

    void  noImprovementIterationLimit( const long int noimpritl ) {
      _noimpr_it_lim = noimpritl;
    }

  private:
    long int  _it_lim, _noimpr_it_lim;
    long int  _it, _noimpr_it;
  };

  /// \brief HeightPolicy stops the search when a given height is reached or
  /// exceeds
  template< typename TS >
  struct HeightPolicy {
    typedef typename TS::Value  Value;

    HeightPolicy() : _height_lim(), _found(false) {}
    HeightPolicy( const Value &hl ) : _height_lim(hl), _found(false) {}

    void  target( TS *ts ) {}

    void  reset() {
      _found = false;
    }

    bool  onStep() {
      return !_found;
    }

    bool  onStick() {
      return false;
    }

    bool  onImprove( const Value &best ) {
      typename TS::Better  better;
      _found = better(best, _height_lim) || (best == _height_lim);
      return !_found;
    }

    Value  heightLimi() const {
      return _height_lim;
    }

    void  heightLimi( const Value &hl ) {
      _height_lim = hl;
    }

  private:
    Value  _height_lim;
    bool  _found;
  };

  /// \brief TimePolicy limits the time for searching.
  template< typename TS >
  struct TimePolicy {
    TimePolicy() : _time_lim(60.0), _timeisup(false) {}
    TimePolicy( const double tl ) : _time_lim(tl), _timeisup(false) {}

    void  target( TS *ts ) {}

    void  reset() {
      _timeisup = false;
      _t.reset();
    }

    bool  onStep() {
      update();
      return !_timeisup;
    }

    bool  onStick() {
      return false;
    }

    bool  onImprove( const typename TS::Value &best ) {
      update();
      return !_timeisup;
    }

    double timeLimit() const {
      return _time_lim;
    }

    void  setTimeLimit( const double tl ) {
      _time_lim = tl;
      update();
    }

  private:
    lemon::Timer  _t;
    double  _time_lim;
    bool  _timeisup;

    inline void  update() {
      _timeisup = _t.realTime() > _time_lim;
    }
  };



  /// \brief TabuSearch main class
  ///
  /// This class offers the implementation of tabu-search algorithm. The
  /// tabu-serach is a local-search. It starts from a specified point of the
  /// problem's graph representation, and in every step it goes to the localy
  /// best next Node except those in tabu set. The maximum size of this tabu
  /// set defines how many Node will be remembered. The best Node ever found
  /// will also stored, so we wont lose it, even is the search continues.
  /// The class can be used on any kind of Graph and with any kind of Value
  /// with a total-settlement on it.
  ///
  /// \param _Graph The graph type the algorithm runs on.
  /// \param _Value The values' type associated to the nodes.
  /// \param _Policy Controlls the search. Determinates when to stop, or how
  /// manage stuck search. Default value is \ref IterationPolicy .
  /// \param _Traits Collection of needed types. Default value is
  /// \ref TabuSearchDefaultTraits .
  ///
  /// \author Szabadkai Mark
#ifdef DOXYGEN
  template< typename GRAPH, typename VALUE, template<typename> class POLICY, typename TRAITS >
#else
  template< typename GRAPH, typename VALUE,
            template<typename> class POLICY = IterationPolicy,
            typename TRAITS = TabuSearchDefaultTraits<GRAPH, VALUE> >
#endif
  class TabuSearch
  {
  public:

    /// \brief Thrown by setting the size of the tabu-set and the given size
    /// is less than 2.
    class BadParameterError : public lemon::LogicError {
    public:
      virtual const char* exceptionName() const {
        return "lemon::TabuSearch::BadParameterError";
      }
    };

    ///Public types
    typedef  TabuSearch<GRAPH,VALUE,POLICY,TRAITS>  SelfType;

    typedef  typename TRAITS::Graph  Graph;
    typedef  typename TRAITS::Node  Node;
    typedef  typename TRAITS::Value  Value;
    typedef  typename TRAITS::HeightMap  HeightMap;
    typedef  typename TRAITS::Better  Better;
    typedef  typename std::deque< Node >::const_iterator  TabuIterator;

    typedef  POLICY<SelfType>  Policy;

  protected:
    typedef  typename TRAITS::EdgeIt  EdgeIt;

    const Graph  &gr;
    const HeightMap  &height;
    /// The tabu set. Teh current node is the first
    std::deque< Node >  tabu;
    /// Maximal tabu size
    unsigned int  mts;
    /// The best Node found
    Node  b;

    Better  better;
    Policy  pol;

  public:
    /// \brief Constructor
    ///
    /// \param graph the graph the algorithm will run on.
    /// \param hm the height map used by the algorithm.
    /// \param tabusz the maximal size of the tabu set. Default value is 3
    /// \param p the Policy controlling the search.
    TabuSearch( const Graph &graph, const HeightMap &hm, 
                const int tabusz = 3, Policy p = Policy() )
      : gr(graph), height(hm), mts(tabusz), pol(p)
    {
      pol.target(this);
    }

    /// \brief Destructor
    ~TabuSearch() {
      pol.target(NULL);
    }

    /// Set/Get the size of the tabu set
    void  tabuSize( const unsigned int size )
    {
      if( size < 2 )
      throw BadParameterError( "Tabu size must be at least 2!" );
      mts = size;
      while( mts < tabu.size() )
      tabu.pop_back();
    }

    unsigned int  tabuSize() const {
      return mts;
    }

    /// Set/Get Policy
    void  policy( Policy p ) {
      pol.target(NULL);
      pol = p;
      pol.target(this);
    }
		
    Policy& policy()  {
      return pol;
    }

    /// \name Execution control
    /// The simplest way to execute the algorithm is to use the member
    /// functions called \c run( 'startnode' ).
    ///@{

    /// \brief Initializes the internal data.
    ///
    /// \param startn The start node where the search begins.
    void  init( const Node startn ) {
      tabu.clear();
      tabu.push_front( startn );
      b = startn;
      pol.reset();
    }

    /// \brief Does one iteration
    ///
    /// If the Policy allows it searches for the best next node, then steps
    /// onto it.
    /// \return %False if one Policy condition wants to stop the search.
    bool  step()
    {
      ///Request premmision from ControllPolicy
      if( !pol.onStep() )
      return false;
	
      ///Find the best next potential node
      Node n; bool found = false;
      for( EdgeIt e(gr,tabu[0]); e != INVALID; ++e )
      {
        Node m = (gr.source(e) == tabu[0]) ? gr.target(e) : gr.source(e);
        bool wrong = false;
        for( int i = 1; i != (signed int)tabu.size(); ++i )
          if( m == tabu[i] ) {
            wrong = true;
            break;
          }
        if( wrong )
          continue;

        if( !found ) {
          n = m;
          found = true;
        } else
          if( better(height[m], height[n]) ) {
            n = m;
          }
      }

      ///Handle stuck search
      if( !found ) {
        return pol.onStick();
      }

      ///Move on...
      tabu.push_front(n);
      while( mts < tabu.size() ) {
        tabu.pop_back();
      }
      if( better(height[n], height[b]) ) {
        b = n;
        if( !pol.onImprove(height[b]) )
        return false;
      }

      return true;
    }

    /// \brief Runs a search while the Policy stops it.
    ///
    /// \param startn The start node where the search begins.
    inline void  run( const Node startn ) {
      std::cin.unsetf( std::ios_base::skipws );
      char c;
      init( startn );
      while( step() )
      std::cin >> c;
      std::cin.setf( std::ios_base::skipws );
    }

    ///@}

    /// \name Query Functions
    /// The result of the TabuSearch algorithm can be obtained using these
    /// functions.\n
    ///@{

    /// \brief The node, the search is standing on.
    inline Node  current() const {
      return tabu[0];
    }

    /// \brief The best node found until now.
    inline Node  best() const {
      return b;
    }

    /// \brief Beginning to iterate on the current tabu set.
    inline TabuIterator  tabu_begin() const {
      return tabu.begin();
    }

    /// \brief Ending to iterate on the current tabu set.
    inline TabuIterator  tabu_end() const {
      return tabu.end();
    }

    ///@}
  };
}
#endif