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

 ///\file

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

 ///

 ///\todo Iterators have obsolete style

 #ifndef LEMON_CONCEPT_PATH_H

 #define LEMON_CONCEPT_PATH_H

 #include <lemon/bits/invalid.h>

 #include <lemon/concept_check.h>

 namespace lemon {

   namespace concepts {

     /// \addtogroup concept

     /// @{

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

     //!

     //! A skeleton structure for representing directed paths 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 it has \c NodeIt

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

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

     template<typename _Graph>

     class Path {

     public:

       /// Type of the underlying graph.

       typedef _Graph Graph;

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

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

       ///

       Path(const Graph &_g) {

 	ignore_unused_variable_warning(_g);

       }

       /// Length of the path ie. the number of edges in the path.

       int length() const {return 0;}

       /// Returns whether the path is empty.

       bool empty() const { return true;}

       /// Resets the path to an empty path.

       void clear() {}

       /// \brief Starting point of the path.

       ///

       /// Starting point of the path.

       /// Returns INVALID if the path is empty.

       Node target() const {return INVALID;}

       /// \brief End point of the path.

       ///

       /// End point of the path.

       /// Returns INVALID if the path is empty.

       Node source() const {return INVALID;}

       /// \brief The target of an edge.

       ///

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

       /// given edge iterator.

       NodeIt target(const EdgeIt&) const {return INVALID;}

       /// \brief The source of an edge.

       ///

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

       /// given edge iterator.

       NodeIt source(const EdgeIt&) const {return INVALID;}

       /// \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 {

       public:

 	/// Default constructor

 	NodeIt() {}

 	/// Invalid constructor

 	NodeIt(Invalid) {}

 	/// Constructor with starting point

 	NodeIt(const Path &) {}

 	///Conversion to Graph::Node

 	operator Node() const { return INVALID; }

 	/// Next node

 	NodeIt& operator++() {return *this;}

 	/// Comparison operator

 	bool operator==(const NodeIt&) const {return true;}

 	/// Comparison operator

 	bool operator!=(const NodeIt&) const {return true;}

  	/// Comparison operator

  	bool operator<(const NodeIt&) const {return false;}

       };

       /// \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 {

       public:

 	/// Default constructor

 	EdgeIt() {}

 	/// Invalid constructor

 	EdgeIt(Invalid) {}

 	/// Constructor with starting point

 	EdgeIt(const Path &) {}

 	operator Edge() const { return INVALID; }

 	/// Next edge

 	EdgeIt& operator++() {return *this;}

 	/// Comparison operator

 	bool operator==(const EdgeIt&) const {return true;}

 	/// Comparison operator

 	bool operator!=(const EdgeIt&) const {return true;}

  	/// Comparison operator

  	bool operator<(const EdgeIt&) const {return false;}

       };

       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.

       ///

       /// While the builder is active (after the first modifying

       /// operation and until the call of \ref commit()) the

       /// underlining Path is in a "transitional" state (operations on

       /// it have undefined result).

       class Builder {

       public:

         /// Constructor

         /// Constructor

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

 	///

 	Builder(Path &_path) { ignore_unused_variable_warning(_path); }

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

 	/// You \em must start building an empty path with these functions.

 	/// (And you \em must \em not use it later).

 	/// \sa pushFront()

 	/// \sa pushBack()

 	void setStartNode(const Node &) {}

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

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

 	///If the path is empty, you \em must call \ref setStartNode() before

 	///the first use of \ref pushFront().

 	void pushFront(const Edge&) {}

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

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

 	///If the path is empty, you \em must call \ref setStartNode() before

 	///the first use of \ref pushBack().

 	void pushBack(const Edge&) {}

 	///Commit the changes to the path.

 	///Commit the changes to the path.

         ///

 	void commit() {}

 	///Reserve (front) storage for the builder in advance.

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

 	///to add to the front of the path,

 	///using this function you may speed up the building.

 	void reserveFront(size_t) {}

 	///Reserve (back) storage for the builder in advance.

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

 	///to add to the back of the path,

 	///using this function you may speed up the building.

 	void reserveBack(size_t) {}

       };

       template <typename _Path>

       struct Constraints {

 	void constraints() {

           typedef typename _Path::Node Node;

           typedef typename _Path::NodeIt NodeIt;

           typedef typename Graph::Node GraphNode;

           typedef typename _Path::Edge Edge;

           typedef typename _Path::EdgeIt EdgeIt;

           typedef typename Graph::Edge GraphEdge;

           typedef typename _Path::Builder Builder;

           path = _Path(graph);

           bool b = cpath.empty();

           int l = cpath.length();

           Node gn;

           Edge ge;

           gn = cpath.source();

           gn = cpath.target();

           NodeIt nit;

           EdgeIt eit(INVALID);

           nit = path.source(eit);

           nit = path.target(eit);

           nit = NodeIt();

           nit = NodeIt(cpath);

           nit = INVALID;

           gn = nit;

           ++nit;

           b = nit == nit;

           b = nit != nit;

           b = nit < nit;

           eit = EdgeIt();

           eit = EdgeIt(cpath);

           eit = INVALID;

           ge = eit;

           ++eit;

           b = eit == eit;

           b = eit != eit;

           b = eit < eit;

           size_t st = 0;

           Builder builder(path); 

           builder.setStartNode(gn);

           builder.pushFront(ge);

           builder.pushBack(ge);

           builder.commit();

           builder.reserveFront(st);

           builder.reserveBack(st);

           ignore_unused_variable_warning(l);

           ignore_unused_variable_warning(b);

 	}

         const Graph& graph;

         const _Path& cpath;

         _Path& path;

       };

     };

   ///@}

   }

 } // namespace lemon

 #endif // LEMON_CONCEPT_PATH_H