/* -*- 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.
///
///\todo Iterators have obsolete style

#ifndef LEMON_PATH_H
#define LEMON_PATH_H

#include <deque>
#include <vector>
#include <algorithm>

#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.
  //! \param DM DebugMode, defaults to DefaultDebugMode.
  //!
  //! 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 DirPath {
  public:
    /// Edge type of the underlying graph.
    typedef typename Graph::Edge GraphEdge;
    /// Node type of the underlying graph.
    typedef typename Graph::Node GraphNode;
    class NodeIt;
    class EdgeIt;

  protected:
    const Graph *gr;
    typedef std::vector<GraphEdge> Container;
    Container edges;

  public:

    /// \param _G The graph in which the path is.
    ///
    DirPath(const Graph &_G) : gr(&_G) {}

    /// \brief Subpath constructor.
    ///
    /// Subpath defined by two nodes.
    /// \warning It is an error if the two edges are not in order!
    DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b) {
      gr = P.gr;
      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
    }

    /// \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!
    DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b) {
      gr = P.gr;
      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
    }

    /// Length of the path.
    int length() const { return edges.size(); }
    /// Returns whether the path is empty.
    bool empty() const { return edges.empty(); }

    /// Resets the path to an empty path.
    void clear() { edges.clear(); }

    /// \brief Starting point of the path.
    ///
    /// Starting point of the path.
    /// Returns INVALID if the path is empty.
    GraphNode source() const {
      return empty() ? INVALID : gr->source(edges[0]);
    }
    /// \brief End point of the path.
    ///
    /// End point of the path.
    /// Returns INVALID if the path is empty.
    GraphNode target() const {
      return empty() ? INVALID : gr->target(edges[length()-1]);
    }

    /// \brief Initializes node or edge iterator to point to the first
    /// node or edge.
    ///
    /// \sa nth
    template<typename It>
    It& first(It &i) const { return i=It(*this); }

    /// \brief Initializes node iterator to point to the node of a given index.
    NodeIt& nth(NodeIt &i, int n) const {
      return i=NodeIt(*this, n);
    }

    /// \brief Initializes edge iterator to point to the edge of a given index.
    EdgeIt& nth(EdgeIt &i, int n) const {
      return i=EdgeIt(*this, n);
    }

    /// \brief Returns node iterator pointing to the target node of the
    /// given edge iterator.
    NodeIt target(const EdgeIt& e) const {
      return NodeIt(*this, e.idx+1);
    }

    /// \brief Returns node iterator pointing to the source node of the
    /// given edge iterator.
    NodeIt source(const EdgeIt& e) const {
      return NodeIt(*this, e.idx);
    }


    /* Iterator classes */

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

      int idx;
      const DirPath *p;
    public:
      /// Default constructor
      EdgeIt() {}
      /// Invalid constructor
      EdgeIt(Invalid) : idx(-1), p(0) {}
      /// Constructor with starting point
      EdgeIt(const DirPath &_p, int _idx = 0) :
	idx(_idx), p(&_p) { validate(); }

      ///Validity check
      bool valid() const { return idx!=-1; }

      ///Conversion to Graph::Edge
      operator GraphEdge () const {
	return valid() ? p->edges[idx] : INVALID;
      }

      /// Next edge
      EdgeIt& operator++() { ++idx; validate(); return *this; }

      /// Comparison operator
      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
      /// Comparison operator
      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
      /// Comparison operator
      bool operator<(const EdgeIt& e) const { return idx<e.idx; }

    private:
      void validate() { if(idx >= p->length() ) idx=-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 DirPath;

      int idx;
      const DirPath *p;
    public:
      /// Default constructor
      NodeIt() {}
      /// Invalid constructor
      NodeIt(Invalid) : idx(-1), p(0) {}
      /// Constructor with starting point
      NodeIt(const DirPath &_p, int _idx = 0) :
	idx(_idx), p(&_p) { validate(); }

      ///Validity check
      bool valid() const { return idx!=-1; }

      ///Conversion to Graph::Node
      operator GraphNode () const {
	if(idx >= p->length())
	  return p->target();
	else if(idx >= 0)
	  return p->gr->source(p->edges[idx]);
	else
	  return INVALID;
      }
      /// Next node
      NodeIt& operator++() { ++idx; validate(); return *this; }

      /// Comparison operator
      bool operator==(const NodeIt& e) const { return idx==e.idx; }
      /// Comparison operator
      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
      /// Comparison operator
      bool operator<(const NodeIt& e) const { return idx<e.idx; }

    private:
      void validate() { if(idx > p->length() ) idx=-1; }
    };

    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 DirPath the original path remains unchanged until the
     * commit. However we don't recomend that you use this feature.
     */
    class Builder {
      DirPath &P;
      Container front, back;

    public:
      ///\param _p the path you want to fill in.
      ///
      Builder(DirPath &_p) : P(_p) {}

      /// 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 GraphNode &) {}

      ///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 GraphEdge& e) {
	front.push_back(e);
      }

      ///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 GraphEdge& e) {
	back.push_back(e);
      }

      ///Commit the changes to the path.
      void commit() {
	if( !front.empty() || !back.empty() ) {
	  Container tmp;
	  tmp.reserve(front.size()+back.size()+P.length());
	  tmp.insert(tmp.end(), front.rbegin(), front.rend());
	  tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
	  tmp.insert(tmp.end(), back.begin(), back.end());
	  P.edges.swap(tmp);
	  front.clear();
	  back.clear();
	}
      }

      ///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);}

      ///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:
      bool empty() {
	return front.empty() && back.empty() && P.empty();
      }

      GraphNode source() const {
	if( ! front.empty() )
	  return P.gr->source(front[front.size()-1]);
	else if( ! P.empty() )
	  return P.gr->source(P.edges[0]);
	else if( ! back.empty() )
	  return P.gr->source(back[0]);
	else
	  return INVALID;
      }
      GraphNode target() const {
	if( ! back.empty() )
	  return P.gr->target(back[back.size()-1]);
	else if( ! P.empty() )
	  return P.gr->target(P.edges[P.length()-1]);
	else if( ! front.empty() )
	  return P.gr->target(front[0]);
	else
	  return INVALID;
      }

    };

  };










  /**********************************************************************/


  //! \brief A structure for representing undirected path in a graph.
  //!
  //! A structure for representing undirected path in a graph. Ie. this is
  //! a path in a \e directed graph but the edges should not be directed
  //! forward.
  //!
  //! \param Graph The graph type in which the path is.
  //! \param DM DebugMode, defaults to DefaultDebugMode.
  //!
  //! 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.
  /// \todo May we need just path for undirected graph instead of this.
  template<typename Graph>
  class UPath {
  public:
    /// Edge type of the underlying graph.
    typedef typename Graph::Edge GraphEdge;
     /// Node type of the underlying graph.
   typedef typename Graph::Node GraphNode;
    class NodeIt;
    class EdgeIt;

  protected:
    const Graph *gr;
    typedef std::vector<GraphEdge> Container;
    Container edges;

  public:

    /// \param _G The graph in which the path is.
    ///
    UPath(const Graph &_G) : gr(&_G) {}

    /// \brief Subpath constructor.
    ///
    /// Subpath defined by two nodes.
    /// \warning It is an error if the two edges are not in order!
    UPath(const UPath &P, const NodeIt &a, const NodeIt &b) {
      gr = P.gr;
      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
    }

    /// \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!
    UPath(const UPath &P, const EdgeIt &a, const EdgeIt &b) {
      gr = P.gr;
      edges.insert(edges.end(), P.edges.begin()+a.idx, P.edges.begin()+b.idx);
    }

    /// Length of the path.
    size_t length() const { return edges.size(); }
    /// Returns whether the path is empty.
    bool empty() const { return edges.empty(); }

    /// Resets the path to an empty path.
    void clear() { edges.clear(); }

    /// \brief Starting point of the path.
    ///
    /// Starting point of the path.
    /// Returns INVALID if the path is empty.
    GraphNode source() const {
      return empty() ? INVALID : gr->source(edges[0]);
    }
    /// \brief End point of the path.
    ///
    /// End point of the path.
    /// Returns INVALID if the path is empty.
    GraphNode target() const {
      return empty() ? INVALID : gr->target(edges[length()-1]);
    }

    /// \brief Initializes node or edge iterator to point to the first
    /// node or edge.
    ///
    /// \sa nth
    template<typename It>
    It& first(It &i) const { return i=It(*this); }

    /// \brief Initializes node iterator to point to the node of a given index.
    NodeIt& nth(NodeIt &i, int n) const {
      return i=NodeIt(*this, n);
    }

    /// \brief Initializes edge iterator to point to the edge of a given index.
    EdgeIt& nth(EdgeIt &i, int n) const {
      return i=EdgeIt(*this, n);
    }

    /// Checks validity of a node or edge iterator.
    template<typename It>
    static
    bool valid(const It &i) { return i.valid(); }

    /// Steps the given node or edge iterator.
    template<typename It>
    static
    It& next(It &e) {
      return ++e;
    }

    /// \brief Returns node iterator pointing to the target node of the
    /// given edge iterator.
    NodeIt target(const EdgeIt& e) const {
      return NodeIt(*this, e.idx+1);
    }

    /// \brief Returns node iterator pointing to the source node of the
    /// given edge iterator.
    NodeIt source(const EdgeIt& e) const {
      return NodeIt(*this, e.idx);
    }



    /**
     * \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
     *
     * \todo Its interface differs from the standard edge iterator.
     * Yes, it shouldn't.
     */
    class EdgeIt {
      friend class UPath;

      int idx;
      const UPath *p;
    public:
      /// Default constructor
      EdgeIt() {}
      /// Invalid constructor
      EdgeIt(Invalid) : idx(-1), p(0) {}
      /// Constructor with starting point
      EdgeIt(const UPath &_p, int _idx = 0) :
	idx(_idx), p(&_p) { validate(); }

      ///Validity check
      bool valid() const { return idx!=-1; }

      ///Conversion to Graph::Edge
      operator GraphEdge () const {
	return valid() ? p->edges[idx] : INVALID;
      }
      /// Next edge
     EdgeIt& operator++() { ++idx; validate(); return *this; }

      /// Comparison operator
      bool operator==(const EdgeIt& e) const { return idx==e.idx; }
      /// Comparison operator
      bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
      /// Comparison operator
      bool operator<(const EdgeIt& e) const { return idx<e.idx; }

    private:
      // FIXME: comparison between signed and unsigned...
      // Jo ez igy? Vagy esetleg legyen a length() int?
      void validate() { if( size_t(idx) >= p->length() ) idx=-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
     *
     * \todo Its interface differs from the standard node iterator.
     * Yes, it shouldn't.
     */
    class NodeIt {
      friend class UPath;

      int idx;
      const UPath *p;
    public:
      /// Default constructor
      NodeIt() {}
      /// Invalid constructor
      NodeIt(Invalid) : idx(-1), p(0) {}
      /// Constructor with starting point
      NodeIt(const UPath &_p, int _idx = 0) :
	idx(_idx), p(&_p) { validate(); }

      ///Validity check
      bool valid() const { return idx!=-1; }

      ///Conversion to Graph::Node
      operator const GraphNode& () const {
	if(idx >= p->length())
	  return p->target();
	else if(idx >= 0)
	  return p->gr->source(p->edges[idx]);
	else
	  return INVALID;
      }
      /// Next node
      NodeIt& operator++() { ++idx; validate(); return *this; }

      /// Comparison operator
      bool operator==(const NodeIt& e) const { return idx==e.idx; }
      /// Comparison operator
      bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
       /// Comparison operator
     bool operator<(const NodeIt& e) const { return idx<e.idx; }

    private:
      void validate() { if( size_t(idx) > p->length() ) idx=-1; }
    };

    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 ot it have undefined result). But
     * in the case of UPath the original path is unchanged until the
     * commit. However we don't recomend that you use this feature.
     */
    class Builder {
      UPath &P;
      Container front, back;

    public:
      ///\param _p the path you want to fill in.
      ///
      Builder(UPath &_p) : P(_p) {}

      /// 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 GraphNode &) {}

      ///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 GraphEdge& e) {
	front.push_back(e);
      }

      ///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 GraphEdge& e) {
	back.push_back(e);
      }

      ///Commit the changes to the path.
      void commit() {
	if( !(front.empty() && back.empty()) ) {
	  Container tmp;
	  tmp.reserve(front.size()+back.size()+P.length());
	  tmp.insert(tmp.end(), front.rbegin(), front.rend());
	  tmp.insert(tmp.end(), P.edges.begin(), P.edges.end());
	  tmp.insert(tmp.end(), back.begin(), back.end());
	  P.edges.swap(tmp);
	  front.clear();
	  back.clear();
	}
      }


      ///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);}

      ///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:
      bool empty() {
	return front.empty() && back.empty() && P.empty();
      }

      GraphNode source() const {
	if( ! front.empty() )
	  return P.gr->source(front[front.size()-1]);
	else if( ! P.empty() )
	  return P.gr->source(P.edges[0]);
	else if( ! back.empty() )
	  return P.gr->source(back[0]);
	else
	  return INVALID;
      }
      GraphNode target() const {
	if( ! back.empty() )
	  return P.gr->target(back[back.size()-1]);
	else if( ! P.empty() )
	  return P.gr->target(P.edges[P.length()-1]);
	else if( ! front.empty() )
	  return P.gr->target(front[0]);
	else
	  return INVALID;
      }

    };

  };


  ///@}

} // namespace lemon

#endif // LEMON_PATH_H