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