#define SKELETON
// -*- c++ -*- //

///\ingroup concept
///\file
///\brief Classes for representing paths in graphs.

#ifndef LEMON_PATH_H
#define LEMON_PATH_H

#include <lemon/invalid.h>

namespace lemon {
  namespace concept {
    /// \addtogroup concept
    /// @{
    
    
    //! \brief A skeleton 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.
      GraphNode head() const {}
      /// \brief End point of the path.
      ///
      /// End point of the path.
      /// Returns INVALID if the path is empty.
      GraphNode 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 concept
       * 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 concept
       * 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 concept
       * 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:

        Path &P;

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

#endif // LEMON_PATH_H