// -*- c++ -*- //

 ///\ingroup skeletons

 ///\file

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

 #ifndef HUGO_PATH_H

 #define HUGO_PATH_H

 #include <hugo/invalid.h>

 namespace hugo {

   namespace skeleton {

     /// \addtogroup skeletons

     /// @{

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

     //!

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

     //! \param GR 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.

     template<typename GR>

     class Path {

     public:

       /// Type of the underlying graph.

       typedef typename GR Graph;

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

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

       ///

       Path(const Graph &_G) {}

       /// Length of the path.

       size_t length() const {}

       /// Returns whether the path is empty.

       bool empty() const {}

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

       NodeIt head() const {}

       /// \brief End point of the path.

       ///

       /// End point of the path.

       /// Returns INVALID if the path is empty.

       NodeIt tail() const {}

       /// \brief First NodeIt/EdgeIt.

       ///

       /// Initializes node or edge iterator to point to the first

       /// node or edge.

       template<typename It>

       It& first(It &i) const { return i=It(*this); }

       /// \brief The head of an edge.

       ///

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

       /// given edge iterator.

       NodeIt head(const EdgeIt& e) const {}

       /// \brief The tail of an edge.

       ///

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

       /// given edge iterator.

       NodeIt tail(const EdgeIt& e) const {}

       /* Iterator classes */

       /**

        * \brief Iterator class to iterate on the edges of the paths

        * 

        * \ingroup skeletons

        * 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 &_p) {}

 	operator GraphEdge () const {}

 	/// Next edge

 	EdgeIt& operator++() {}

 	/// Comparison operator

 	bool operator==(const EdgeIt& e) const {}

 	/// Comparison operator

 	bool operator!=(const EdgeIt& e) const {}

 // 	/// Comparison operator

 //      /// \todo It is not clear what is the "natural" ordering.

 // 	bool operator<(const EdgeIt& e) const {}

       };

       /**

        * \brief Iterator class to iterate on the nodes of the paths

        * 

        * \ingroup skeletons

        * 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 &_p) {}

 	///Conversion to Graph::Node

 	operator const GraphNode& () const {}

 	/// Next node

 	NodeIt& operator++() {}

 	/// Comparison operator

 	bool operator==(const NodeIt& e) const {}

 	/// Comparison operator

 	bool operator!=(const NodeIt& e) const {}

 // 	/// Comparison operator

 //      /// \todo It is not clear what is the "natural" ordering.

 // 	bool operator<(const NodeIt& e) const {}

       };

       friend class Builder;    

       /**

        * \brief Class to build paths

        * 

        * \ingroup skeletons

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

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

 	///

 	Builder(Path &_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.

 	/// You \em must start building an empry path with this functions.

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

 	/// \sa pushFront()

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

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

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

 	void pushFront(const GraphEdge& e) {}

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

 	///Commit the changes to the path.

 	void commit() {}

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

 	///If you know an reasonable upper bound of 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 r) {}

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

 	///If you know an reasonable upper bound of 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 r) {}

       };

     };

   ///@}

   }

 } // namespace hugo

 #endif // HUGO_PATH_H