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