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

  *

  */

 ///\ingroup paths

 ///\file

 ///\brief Classes for representing paths in graphs.

 ///

 #ifndef LEMON_PATH_H

 #define LEMON_PATH_H

 #include <vector>

 #include <algorithm>

 #include <lemon/error.h>

 #include <lemon/bits/invalid.h>

 namespace lemon {

   /// \addtogroup paths

   /// @{

   //! \brief A structure for representing directed paths in a graph.

   //!

   //! A structure for representing directed path in a graph.

   //! \param Graph The graph type in which the path is.

   //!

   //! In a sense, the path can be treated as a graph, for is has \c NodeIt

   //! and \c EdgeIt with the same usage. These types converts to the \c Node

   //! and \c Edge of the original graph.

   //!

   //! \todo Thoroughfully check all the range and consistency tests.

   template<typename Graph>

   class Path {

   public:

     /// Edge type of the underlying graph.

     typedef typename Graph::Edge Edge;

     /// Node type of the underlying graph.

     typedef typename Graph::Node Node;

     class NodeIt;

     class EdgeIt;

     struct PathError : public LogicError {

       virtual const char* what() const throw() {

         return "lemon::PathError";

       }      

     };

   public:

     /// \brief Constructor

     ///

     /// Constructor 

     /// \param _G The graph in which the path is.

     Path(const Graph &_graph) : graph(&_graph), start(INVALID) {}

     /// \brief Subpath constructor.

     ///

     /// Subpath defined by two nodes.

     /// \warning It is an error if the two edges are not in order!

     Path(const Path &other, const NodeIt &a, const NodeIt &b) {

       graph = other.graph; 

       start = a;

       edges.insert(edges.end(), 

                    other.edges.begin() + a.id, other.edges.begin() + b.id);

     }

     /// \brief Subpath constructor.

     ///

     /// Subpath defined by two edges. Contains edges in [a,b)

     /// \warning It is an error if the two edges are not in order!

     Path(const Path &other, const EdgeIt &a, const EdgeIt &b) {

       graph = other.graph;

       start = graph->source(a);

       edges.insert(edges.end(), 

                    other.edges.begin() + a.id, other.edges.begin() + b.id);

     }

     /// \brief Length of the path.

     ///

     /// The number of the edges in the path. It can be zero if the

     /// path has only one node or it is empty.

     int length() const { return edges.size(); }

     /// \brief Returns whether the path is empty.

     ///

     /// Returns true when the path does not contain neither edge nor

     /// node.

     bool empty() const { return start == INVALID; }

     /// \brief Resets the path to an empty path.

     ///

     /// Resets the path to an empty path.

     void clear() { edges.clear(); start = INVALID; }

     /// \brief Starting point of the path.

     ///

     /// Starting point of the path.

     /// Returns INVALID if the path is empty.

     Node source() const {

       return start;

     }

     /// \brief End point of the path.

     ///

     /// End point of the path.

     /// Returns INVALID if the path is empty.

     Node target() const {

       return length() == 0 ? start : graph->target(edges[length()-1]);

     }

     /// \brief Gives back a node iterator to point to the node of a

     /// given index.

     ///

     /// Gives back a node iterator to point to the node of a given

     /// index.

     /// \pre n should less or equal to \c length()

     NodeIt nthNode(int n) const {

       return NodeIt(*this, n);

     }

     /// \brief Gives back an edge iterator to point to the edge of a

     /// given index.

     ///

     /// Gives back an edge iterator to point to the node of a given

     /// index.  

     /// \pre n should less than \c length()

     EdgeIt nthEdge(int n) const {

       return EdgeIt(*this, n);

     }

     /// \brief Returns node iterator pointing to the source node of the

     /// given edge iterator.

     ///

     /// Returns node iterator pointing to the source node of the given

     /// edge iterator.

     NodeIt source(const EdgeIt& e) const {

       return NodeIt(*this, e.id);

     }

     /// \brief Returns node iterator pointing to the target node of the

     /// given edge iterator.

     ///

     /// Returns node iterator pointing to the target node of the given

     /// edge iterator.

     NodeIt target(const EdgeIt& e) const {

       return NodeIt(*this, e.id + 1);

     }

     /// \brief Iterator class to iterate on the nodes of the paths

     ///

     /// This class is used to iterate on the nodes of the paths

     ///

     /// Of course it converts to Graph::Node

     class NodeIt {

       friend class Path;

     public:

       /// \brief Default constructor

       ///

       /// Default constructor

       NodeIt() {}

       /// \brief Invalid constructor

       ///

       /// Invalid constructor

       NodeIt(Invalid) : id(-1), path(0) {}

       /// \brief Constructor with starting point

       /// 

       /// Constructor with starting point

       NodeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) { 

         if (id > path->length()) id = -1; 

       }

       /// \brief Conversion to Graph::Node

       ///

       /// Conversion to Graph::Node

       operator Node() const {

 	if (id > 0) {

 	  return path->graph->target(path->edges[id - 1]);

 	} else if (id == 0) {

 	  return path->start;

 	} else {

 	  return INVALID;

         }

       }

       /// \brief Steps to the next node

       ///

       /// Steps to the next node

       NodeIt& operator++() { 

         ++id; 

         if (id > path->length()) id = -1; 

         return *this; 

       }

       /// \brief Comparison operator

       ///

       /// Comparison operator

       bool operator==(const NodeIt& n) const { return id == n.id; }

       /// \brief Comparison operator

       ///

       /// Comparison operator

       bool operator!=(const NodeIt& n) const { return id != n.id; }

       /// \brief Comparison operator

       ///

       /// Comparison operator

       bool operator<(const NodeIt& n) const { return id < n.id; }

     private:

       int id;

       const Path *path;

     };

     /// \brief Iterator class to iterate on the edges of the paths

     ///

     /// This class is used to iterate on the edges of the paths

     /// Of course it converts to Graph::Edge

     class EdgeIt {

       friend class Path;

     public:

       /// \brief Default constructor

       ///

       /// Default constructor

       EdgeIt() {}

       /// \brief Invalid constructor

       ///

       /// Invalid constructor

       EdgeIt(Invalid) : id(-1), path(0) {}

       /// \brief Constructor with starting point

       ///

       /// Constructor with starting point

       EdgeIt(const Path &_path, int _id = 0) : id(_id), path(&_path) { 

         if (id >= path->length()) id = -1;

       }

       /// \brief Conversion to Graph::Edge

       ///

       /// Conversion to Graph::Edge

       operator Edge() const {

 	return id != -1 ? path->edges[id] : INVALID;

       }

       /// \brief Steps to the next edge

       ///

       /// Steps to the next edge

       EdgeIt& operator++() { 

         ++id; 

         if (id >= path->length()) id = -1;

         return *this; 

       }

       /// \brief Comparison operator

       ///

       /// Comparison operator

       bool operator==(const EdgeIt& e) const { return id == e.id; }

       /// \brief Comparison operator

       ///

       /// Comparison operator

       bool operator!=(const EdgeIt& e) const { return id != e.id; }

       /// \brief Comparison operator

       ///

       /// Comparison operator

       bool operator<(const EdgeIt& e) const { return id < e.id; }

     private:

       int id;

       const Path *path;

     };

   protected:

     const Graph *graph;

     typedef std::vector<Edge> Container;

     Container edges;

     Node start;

   public:

     friend class Builder;

     /// \brief Class to build paths

     ///

     /// This class is used to fill a path with edges.

     ///

     /// You can push new edges to the front and to the back of the

     /// path in arbitrary order then you should commit these changes

     /// to the graph.

     ///

     /// Fundamentally, for most "Paths" (classes fulfilling the

     /// PathConcept) while the builder is active (after the first

     /// modifying operation and until the commit()) the original Path

     /// is in a "transitional" state (operations on it have undefined

     /// result). But in the case of Path the original path remains

     /// unchanged until the commit. However we don't recomend that you

     /// use this feature.

     class Builder {

     public:

       /// \brief Constructor

       ///

       /// Constructor

       /// \param _path the path you want to fill in.

       Builder(Path &_path) : path(_path), start(INVALID) {}

       /// \brief Destructor

       ///

       /// Destructor

       ~Builder() {

         LEMON_ASSERT(front.empty() && back.empty() && start == INVALID, 

                      PathError());

       }

       /// \brief Sets the starting node of the path.

       ///

       /// Sets the starting node of the path. Edge added to the path

       /// afterwards have to be incident to this node.  It should be

       /// called if and only if the path is empty and before any call

       /// to \ref pushFront() or \ref pushBack()

       void setStartNode(const Node &_start) {

         LEMON_ASSERT(path.empty() && start == INVALID, PathError());

         start = _start;

       }

       /// \brief Push a new edge to the front of the path

       ///

       /// Push a new edge to the front of the path.  

       /// \sa setStartNode

       void pushFront(const Edge& e) {

         LEMON_ASSERT(front.empty() || 

                      (path.graph->source(front.back()) == 

                       path.graph->target(e)), PathError());

         LEMON_ASSERT(path.empty() || 

                      (path.source() == path.graph->target(e)), PathError());

         LEMON_ASSERT(!path.empty() || !front.empty() ||

                      (start == path.graph->target(e)), PathError());

 	front.push_back(e);

       }

       /// \brief Push a new edge to the back of the path

       ///

       /// Push a new edge to the back of the path.

       /// \sa setStartNode

       void pushBack(const Edge& e) {

         LEMON_ASSERT(back.empty() || 

                      (path.graph->target(back.back()) == 

                       path.graph->source(e)), PathError());

         LEMON_ASSERT(path.empty() || 

                      (path.target() == path.graph->source(e)), PathError());

         LEMON_ASSERT(!path.empty() || !back.empty() ||

                      (start == path.graph->source(e)), PathError());

 	back.push_back(e);

       }

       /// \brief Commit the changes to the path.

       ///

       /// Commit the changes to the path.

       void commit() {

 	if( !front.empty() || !back.empty() || start != INVALID) {

 	  Container tmp;

 	  tmp.reserve(front.size() + back.size() + path.length());

 	  tmp.insert(tmp.end(), front.rbegin(), front.rend());

 	  tmp.insert(tmp.end(), path.edges.begin(), path.edges.end());

 	  tmp.insert(tmp.end(), back.begin(), back.end());

 	  path.edges.swap(tmp);

           if (!front.empty()) {

             path.start = path.graph->source(front.back());

           } else {

             path.start = start;

           }

           start = INVALID;

 	  front.clear();

 	  back.clear();

 	}

       }

       /// \brief Reserve storage for the builder in advance.

       ///

       /// If you know a reasonable upper bound of the number of the

       /// edges to add to the front, using this function you can speed

       /// up the building.

       void reserveFront(size_t r) {front.reserve(r);}

       /// \brief Reserve storage for the builder in advance.

       ///

       /// If you know a reasonable upper bound of the number of the

       /// edges to add to the back, using this function you can speed

       /// up the building.

       void reserveBack(size_t r) {back.reserve(r);}

     private:

       Path &path;

       Container front, back;

       Node start;

     };

   };

   ///@}

 } // namespace lemon

 #endif // LEMON_PATH_H