source: lemon-0.x/src/hugo/skeletons/path.h @ 804:6874a72dbdc5

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

/**
@defgroup paths Path Structures
@ingroup datas
\brief Path structures implemented in Hugo.

Hugolib provides flexible data structures
to work with paths.

All of them have the same interface, especially they can be built or extended
using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
algorithm to store its result in any kind of path structure.

*/

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

#ifndef HUGO_PATH_H
#define HUGO_PATH_H

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

#include <hugo/invalid.h>
#include <hugo/error.h>
#include <debug.h>

namespace hugo {
  namespace skeleton {
    /// \addtogroup skeletons
    /// @{
    
    
    //! \brief A structure for representing directed path in a graph.
    //!
    //! A structure for representing directed path 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