/* -*- 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 metah

/// \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;

    }

  };

  /// \ingroup metah

  ///

  /// \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* what() const throw() {

        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