//  espprc.hpp header file

//  Copyright Michael Drexl 2005. All rights reserved.

#ifndef BOOST_ESPPRC_HPP
#define BOOST_ESPPRC_HPP

#include <time.h>
#include <map>
#include <queue>
#include <vector>

#include <boost/graph/graph_traits.hpp>

namespace boost {

//  espprc_label struct
template<class Graph, class Resource_Container>
struct espprc_label
{
  espprc_label( const unsigned long n, 
                const Resource_Container& rc = Resource_Container(), 
                const espprc_label* const pl = 0, 
                const typename graph_traits<Graph>::edge_descriptor& ed = 
                  graph_traits<Graph>::edge_descriptor(), 
                const typename graph_traits<Graph>::vertex_descriptor& vd = 
                  graph_traits<Graph>::vertex_descriptor() )
  : num( n ), 
    cumulated_resource_consumption( rc ), 
    p_pred_label( pl ), 
    pred_edge( ed ), 
    resident_vertex( vd ), 
    b_is_dominated( false )
  {}
  espprc_label& operator=( const espprc_label& other )
  {
    if( this == &other )
      return *this;
    this->~espprc_label();
    new( this ) espprc_label( other );
    return *this;
  }
  const unsigned long num;
  Resource_Container cumulated_resource_consumption;
  const espprc_label* const p_pred_label;
  const typename graph_traits<Graph>::edge_descriptor pred_edge;
  const typename graph_traits<Graph>::vertex_descriptor resident_vertex;
  bool b_is_dominated;
}; //  espprc_label

template<class Graph, class Resource_Container>
inline bool operator==( const espprc_label<Graph, Resource_Container>& l1, 
                        const espprc_label<Graph, Resource_Container>& l2 )
{
  return 
    l1.cumulated_resource_consumption == l2.cumulated_resource_consumption;
}

template<class Graph, class Resource_Container>
inline bool operator!=( const espprc_label<Graph, Resource_Container>& l1, 
                        const espprc_label<Graph, Resource_Container>& l2 )
{
  return 
    !( l1 == l2 );
}

template<class Graph, class Resource_Container>
inline bool operator<( const espprc_label<Graph, Resource_Container>& l1, 
                       const espprc_label<Graph, Resource_Container>& l2 )
{
  return 
    l1.cumulated_resource_consumption < l2.cumulated_resource_consumption;
}

template<class Graph, class Resource_Container>
inline bool operator>( const espprc_label<Graph, Resource_Container>& l1, 
                       const espprc_label<Graph, Resource_Container>& l2 )
{
  return 
    l2.cumulated_resource_consumption < l1.cumulated_resource_consumption;
}

template<class Graph, class Resource_Container>
inline bool operator<=( const espprc_label<Graph, Resource_Container>& l1, 
                        const espprc_label<Graph, Resource_Container>& l2 )
{
  return 
    l1 < l2 || l1 == l2;
}

template<class Graph, class Resource_Container>
inline bool operator>=( const espprc_label<Graph, Resource_Container>& l1, 
                        const espprc_label<Graph, Resource_Container>& l2 )
{
  return l2 < l1 || l1 == l2;
}

namespace detail {

//  ks_smart_pointer class
//  from:
//  Kuhlins, S.; Schader, M. (1999):
//  Die C++-Standardbibliothek
//  Springer, Berlin
//  p. 333 f.
template<class T>
class ks_smart_pointer
{
public:
  ks_smart_pointer( T* ptt = 0 ) : pt( ptt ) {}
  ks_smart_pointer( const ks_smart_pointer& other ) : pt( other.pt ) {}
  ks_smart_pointer& operator=( const ks_smart_pointer& other )
    { pt = other.pt; return *this; }
  ~ks_smart_pointer() {}
  T& operator*() const { return *pt; }
  T* operator->() const { return pt; }
  T* get() const { return pt; }
  operator T*() const { return pt; }
  friend bool operator==( const ks_smart_pointer& t, 
                          const ks_smart_pointer& u )
    { return *t.pt == *u.pt; }
  friend bool operator!=( const ks_smart_pointer& t, 
                          const ks_smart_pointer& u )
    { return *t.pt != *u.pt; }
  friend bool operator<( const ks_smart_pointer& t, 
                         const ks_smart_pointer& u )
    { return *t.pt < *u.pt; }
  friend bool operator>( const ks_smart_pointer& t, 
                         const ks_smart_pointer& u )
    { return *t.pt > *u.pt; }
  friend bool operator<=( const ks_smart_pointer& t, 
                          const ks_smart_pointer& u )
    { return *t.pt <= *u.pt; }
  friend bool operator>=( const ks_smart_pointer& t, 
                          const ks_smart_pointer& u )
    { return *t.pt >= *u.pt; }
private:
  T* pt;
}; // ks_smart_pointer


//  espprc_dispatch function (body/implementation)
template<class Graph, 
         class Vertex_Num_Map, 
         class Arc_Num_Map, 
         class Resource_Container, 
         class Resource_Extension_Function, 
         class Dominance_Function, 
         class Label_Allocator, 
         class Visitor>
void espprc_dispatch
( const Graph& g, 
  const Vertex_Num_Map& vert_num_map, 
  const Arc_Num_Map& arc_num_map, 
  typename graph_traits<Graph>::vertex_descriptor o, 
  typename graph_traits<Graph>::vertex_descriptor d, 
  // each inner vector corresponds to a pareto-optimal path
  std::vector
    <std::vector
      <typename graph_traits
        <Graph>::edge_descriptor> >& pareto_optimal_solutions, 
  std::vector
    <Resource_Container>& pareto_optimal_resource_containers, 
  bool b_all_pareto_optimal_solutions, 
  // to initialize the first label/resource container 
  // and to carry the type information
  const Resource_Container& rc, 
  Resource_Extension_Function& ref, 
  Dominance_Function& dominance, 
  // to specify the memory management strategy for the labels
  Label_Allocator& la = 
    std::allocator<espprc_label<Graph, Resource_Container> >(), 
  Visitor vis = Visitor() )
{
  clock_t start, finish;
  start = clock();
  pareto_optimal_solutions.clear();

  unsigned long i_label_num = 0;
  typedef 
    ks_smart_pointer<espprc_label<Graph, Resource_Container> > Splabel;
  std::priority_queue<Splabel, std::vector<Splabel>, std::greater<Splabel> > 
    unprocessed_labels;

  bool b_feasible = true;
  espprc_label<Graph, Resource_Container>* first_label = la.allocate( 1 );
  la.construct( first_label, 
                espprc_label<Graph, Resource_Container>( i_label_num++, 
                                                         rc, 
                                                         0, 
                                                         typename graph_traits<Graph>::
                                                           edge_descriptor(), 
                                                         o ) );

  Splabel splabel_first_label = Splabel( first_label );
  unprocessed_labels.push( splabel_first_label );
  std::vector<std::list<Splabel> > vec_vertex_labels( num_vertices( g ) );
  while( unprocessed_labels.size() )
  {
    Splabel cur_label = unprocessed_labels.top();
    unprocessed_labels.pop();
    vis.on_label_popped( *cur_label, g );
    if( !b_all_pareto_optimal_solutions && (*cur_label).resident_vertex == d )
    {
      while( unprocessed_labels.size() )
      {
        // the devil don't sleep
        if( (*cur_label).b_is_dominated )
        {
          la.destroy( cur_label.get() );
          la.deallocate( cur_label.get(), 1 );
        }
        Splabel l = unprocessed_labels.top();
        unprocessed_labels.pop();
        // delete only dominated labels, because nondominated labels are 
        // deleted at the end of the function
        if( (*l).b_is_dominated )
        {
          la.destroy( l.get() );
          la.deallocate( l.get(), 1 );
        }
      }
      break;
    }
    // an Splabel object in unprocessed_labels and the respective Splabel 
    // object in the respective list<Splabel> of vec_vertex_labels share their 
    // embedded espprc_label object
    // to avoid memory leaks, dominated espprc_label objects are marked and 
    // deleted when popped from unprocessed_labels, as they can no longer be 
    // deleted at the end of the function; only the Splabel object in 
    // unprocessed_labels still references the espprc_label object
    // this is also for efficiency, because the else branch is executed only 
    // if there is a chance that extending the 
    // label leads to new undominated labels, which in turn is possible only 
    // if the label to be extended is undominated
    if( (*cur_label).b_is_dominated )
    {
      vis.on_label_dominated( *cur_label, g );
      la.destroy( cur_label.get() );
      la.deallocate( cur_label.get(), 1 );
    }
    else
    {
      vis.on_label_not_dominated( *cur_label, g );
      typename graph_traits<Graph>::vertex_descriptor cur_vertex = 
        cur_label->resident_vertex;
      typename graph_traits<Graph>::out_edge_iterator oei, oei_end;
      for( tie( oei, oei_end ) = out_edges( cur_vertex, g ); 
           oei != oei_end; 
           ++oei )
      {
        b_feasible = true;
        espprc_label<Graph, Resource_Container>* new_label = la.allocate( 1 );
        la.construct( new_label, 
                      espprc_label<Graph, Resource_Container>
                        ( i_label_num++, 
                          cur_label->cumulated_resource_consumption, 
                          cur_label.get(), 
                          *oei, 
                          target( *oei, g ) ) );
        b_feasible = 
          ref( g, 
               new_label->cumulated_resource_consumption, 
               new_label->p_pred_label->cumulated_resource_consumption, 
               new_label->pred_edge );

        if( !b_feasible )
        {
          vis.on_label_not_feasible( *new_label, g );
          la.destroy( new_label );
          la.deallocate( new_label, 1 );
        }
        else
        {
          const espprc_label<Graph, Resource_Container>& ref_new_label = 
            *new_label;
          vis.on_label_feasible( ref_new_label, g );
          std::list<Splabel>& list_labels_cur_vertex = 
            vec_vertex_labels[vert_num_map[new_label->resident_vertex]];
          bool b_dominated = false;
          typename std::list<Splabel>::iterator si = list_labels_cur_vertex.begin();
          typename std::list<Splabel>::iterator si_end = list_labels_cur_vertex.end();
          while( si != si_end )
          {
            espprc_label<Graph, Resource_Container>& ref_cur_label = **si;
            if( dominance( ref_cur_label.cumulated_resource_consumption, 
                           ref_new_label.cumulated_resource_consumption ) )
            {
              b_dominated = true;
              // the following break makes sure that no two labels with 
              // identical resource consumption dominate each other and are 
              // both marked as dominated
              break;
            }
            if( dominance( ref_new_label.cumulated_resource_consumption, 
                           ref_cur_label.cumulated_resource_consumption ) )
            {
              ref_cur_label.b_is_dominated = true;
              typename std::list<Splabel>::iterator si_buf = si;
              ++si;
              list_labels_cur_vertex.erase( si_buf );
            }
            else
              ++si;
          }
          if( !b_dominated )
          {
            Splabel new_sp_label( new_label );
            list_labels_cur_vertex.push_back( new_sp_label );
            unprocessed_labels.push( new_sp_label );
          }
          else
          {
            la.destroy( new_label );
            la.deallocate( new_label, 1 );
          }
        }
      }
    }
  }
  finish = clock();
  std::list<Splabel> dsplabels = vec_vertex_labels[vert_num_map[d]];
  typename std::list<Splabel>::const_iterator csi = dsplabels.begin();
  typename std::list<Splabel>::const_iterator csi_end = dsplabels.end();
  // if d could be reached from o
  if( dsplabels.size() )
  {
    for( ; csi != csi_end; ++csi )
    {
      std::vector<typename graph_traits<Graph>::edge_descriptor> 
        cur_pareto_optimal_path;
      const espprc_label<Graph, Resource_Container>* p_cur_label = 
        (*csi).get();
      pareto_optimal_resource_containers.
        push_back( p_cur_label->cumulated_resource_consumption );
      while( p_cur_label->num != 0 )
      {
        cur_pareto_optimal_path.push_back( p_cur_label->pred_edge );
        p_cur_label = p_cur_label->p_pred_label;
      }
      pareto_optimal_solutions.push_back( cur_pareto_optimal_path );
      if( !b_all_pareto_optimal_solutions )
        break;
    }
  }

  la.destroy( splabel_first_label.get() );
  la.deallocate( splabel_first_label.get(), 1 );
  int i_size = static_cast<int>( vec_vertex_labels.size() );
  for( int i = 0; i < i_size; ++i )
  {
    const std::list<Splabel>& list_labels_cur_vertex = vec_vertex_labels[i];
    csi_end = list_labels_cur_vertex.end();
    for( csi = list_labels_cur_vertex.begin(); csi != csi_end; ++csi )
    {
      la.destroy( (*csi).get() );
      la.deallocate( (*csi).get(), 1 );
    }
  }
} // espprc_dispatch

} // detail

//  default_espprc_visitor struct
struct default_espprc_visitor
{
  template<class Label, class Graph>
  void on_label_popped( const Label& l, const Graph& g ) {}
  template<class Label, class Graph>
  void on_label_feasible( const Label& l, const Graph& g ) {}
  template<class Label, class Graph>
  void on_label_not_feasible( const Label& l, const Graph& g ) {}
  template<class Label, class Graph>
  void on_label_dominated( const Label& l, const Graph& g ) {}
  template<class Label, class Graph>
  void on_label_not_dominated( const Label& l, const Graph& g ) {}
}; //  default_espprc_visitor


//  espprc function (handle/interface)
template<class Graph, 
         class Vertex_Num_Map, 
         class Arc_Num_Map, 
         class Resource_Container, 
         class Resource_Extension_Function, 
         class Dominance_Function, 
         class Label_Allocator, 
         class Visitor>
void espprc( const Graph& g, 
             const Vertex_Num_Map& vert_num_map, 
             const Arc_Num_Map& arc_num_map, 
             typename graph_traits<Graph>::vertex_descriptor o, 
             typename graph_traits<Graph>::vertex_descriptor d, 
             // each inner vector corresponds to a pareto-optimal path
             std::vector
               <std::vector
                 <typename graph_traits
                   <Graph>::edge_descriptor> >& pareto_optimal_solutions, 
             std::vector
               <Resource_Container>& pareto_optimal_resource_containers, 
             bool b_all_pareto_optimal_solutions, 
             // to initialize the first label/resource container 
             // and to carry the type information
             const Resource_Container& rc, 
             const Resource_Extension_Function& ref, 
             const Dominance_Function& dominance, 
             // to specify the memory management strategy for the labels
             Label_Allocator la, 
             Visitor vis)
{
  espprc_dispatch( g, 
                   vert_num_map, 
                   arc_num_map, 
                   o, 
                   d, 
                   pareto_optimal_solutions, 
                   pareto_optimal_resource_containers, 
                   b_all_pareto_optimal_solutions, 
                   rc, 
                   ref, 
                   dominance, 
                   la, 
                   vis );
} //  espprc

//  check_path function
template<class Graph, 
         class Resource_Container, 
         class Resource_Extension_Function>
void check_path( const Graph& g, 
                 // ed_vec_path must contain the arcs of the path to be 
                 // checked in ascending order, i.e., the first element of 
                 // ed_vec_path must be the arc whose tail is the start vertex 
                 // of the path and so on
                 const std::vector
                   <typename graph_traits
                     <Graph>::edge_descriptor>& ed_vec_path, 
                 const Resource_Container& initial_resource_levels, 
                 const Resource_Container& desired_final_resource_levels, 
                 Resource_Extension_Function& ref, 
                 bool& b_feasible, 
                 bool& b_correctly_extended, 
                 typename graph_traits<Graph>::edge_descriptor& 
                   ed_last_extended_arc )
{
  b_feasible = true;
  b_correctly_extended = false;
  int i_path_length = static_cast<int>( ed_vec_path.size() );
  Resource_Container current_resource_levels = initial_resource_levels;
  Resource_Container final_resource_levels = current_resource_levels;
  for( int i = 0; i < i_path_length; ++i )
  {
    ed_last_extended_arc = ed_vec_path[i];
    b_feasible = 
      ref( g, final_resource_levels, current_resource_levels, ed_vec_path[i] );
    current_resource_levels = final_resource_levels;
    if( !b_feasible )
      return;
  }
  b_correctly_extended = 
    final_resource_levels == desired_final_resource_levels ? true : false;
} //  check_path

} //  namespace

#endif //  BOOST_ESPPRC_HPP