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