src/hugo/skeletons/path.h
author deba
Wed, 08 Sep 2004 12:06:45 +0000
changeset 822 88226d9fe821
parent 807 ce85435185c3
child 823 afba7fbbb239
permissions -rw-r--r--
The MapFactories have been removed from the code because
if we use macros then they increases only the complexity.

The pair iterators of the maps are separeted from the maps.

Some macros and comments has been changed.
     1 #define SKELETON
     2 // -*- c++ -*- //
     3 
     4 ///\ingroup skeletons
     5 ///\file
     6 ///\brief Classes for representing paths in graphs.
     7 
     8 #ifndef HUGO_PATH_H
     9 #define HUGO_PATH_H
    10 
    11 #include <hugo/invalid.h>
    12 
    13 namespace hugo {
    14   namespace skeleton {
    15     /// \addtogroup skeletons
    16     /// @{
    17     
    18     
    19     //! \brief A skeletom structure for representing directed paths in a graph.
    20     //!
    21     //! A skeleton structure for representing directed paths in a graph.
    22     //! \param GR The graph type in which the path is.
    23     //! 
    24     //! In a sense, the path can be treated as a graph, for is has \c NodeIt
    25     //! and \c EdgeIt with the same usage. These types converts to the \c Node
    26     //! and \c Edge of the original graph.
    27     template<typename GR>
    28     class Path {
    29     public:
    30       
    31       /// Type of the underlying graph.
    32       typedef /*typename*/ GR Graph;
    33       /// Edge type of the underlying graph.
    34       typedef typename Graph::Edge GraphEdge; 
    35       /// Node type of the underlying graph.
    36      typedef typename Graph::Node GraphNode;
    37       class NodeIt;
    38       class EdgeIt;
    39       
    40       /// \param _G The graph in which the path is.
    41       ///
    42       Path(const Graph &_G) {}
    43       
    44       /// Length of the path.
    45       size_t length() const {return 0;}
    46       /// Returns whether the path is empty.
    47       bool empty() const {}
    48       
    49       /// Resets the path to an empty path.
    50       void clear() {}
    51 
    52       /// \brief Starting point of the path.
    53       ///
    54       /// Starting point of the path.
    55       /// Returns INVALID if the path is empty.
    56       GraphNode/*It*/ head() const {return INVALID;}
    57       /// \brief End point of the path.
    58       ///
    59       /// End point of the path.
    60       /// Returns INVALID if the path is empty.
    61       GraphNode/*It*/ tail() const {return INVALID;}
    62 
    63       /// \brief First NodeIt/EdgeIt.
    64       ///
    65       /// Initializes node or edge iterator to point to the first
    66       /// node or edge.
    67       template<typename It>
    68       It& first(It &i) const { return i=It(*this); }
    69 
    70       /// \brief The head of an edge.
    71       ///
    72       /// Returns node iterator pointing to the head node of the
    73       /// given edge iterator.
    74       NodeIt head(const EdgeIt& e) const {}
    75 
    76       /// \brief The tail of an edge.
    77       ///
    78       /// Returns node iterator pointing to the tail node of the
    79       /// given edge iterator.
    80       NodeIt tail(const EdgeIt& e) const {}
    81 
    82 
    83       /* Iterator classes */
    84 
    85       /**
    86        * \brief Iterator class to iterate on the edges of the paths
    87        * 
    88        * \ingroup skeletons
    89        * This class is used to iterate on the edges of the paths
    90        *
    91        * Of course it converts to Graph::Edge
    92        * 
    93        */
    94       class EdgeIt {
    95       public:
    96 	/// Default constructor
    97 	EdgeIt() {}
    98 	/// Invalid constructor
    99 	EdgeIt(Invalid) {}
   100 	/// Constructor with starting point
   101 	EdgeIt(const Path &_p) {}
   102 
   103 	operator GraphEdge () const {}
   104 
   105 	/// Next edge
   106 	EdgeIt& operator++() {}
   107 
   108 	/// Comparison operator
   109 	bool operator==(const EdgeIt& e) const {}
   110 	/// Comparison operator
   111 	bool operator!=(const EdgeIt& e) const {}
   112 // 	/// Comparison operator
   113 //      /// \todo It is not clear what is the "natural" ordering.
   114 // 	bool operator<(const EdgeIt& e) const {}
   115 
   116       };
   117 
   118       /**
   119        * \brief Iterator class to iterate on the nodes of the paths
   120        * 
   121        * \ingroup skeletons
   122        * This class is used to iterate on the nodes of the paths
   123        *
   124        * Of course it converts to Graph::Node.
   125        * 
   126        */
   127       class NodeIt {
   128       public:
   129 	/// Default constructor
   130 	NodeIt() {}
   131 	/// Invalid constructor
   132 	NodeIt(Invalid) {}
   133 	/// Constructor with starting point
   134 	NodeIt(const Path &_p) {}
   135 
   136 	///Conversion to Graph::Node
   137 	operator const GraphNode& () const {}
   138 	/// Next node
   139 	NodeIt& operator++() {}
   140 
   141 	/// Comparison operator
   142 	bool operator==(const NodeIt& e) const {}
   143 	/// Comparison operator
   144 	bool operator!=(const NodeIt& e) const {}
   145 // 	/// Comparison operator
   146 //      /// \todo It is not clear what is the "natural" ordering.
   147 // 	bool operator<(const NodeIt& e) const {}
   148 
   149       };
   150 
   151       friend class Builder;    
   152 
   153       /**
   154        * \brief Class to build paths
   155        * 
   156        * \ingroup skeletons
   157        * This class is used to fill a path with edges.
   158        *
   159        * You can push new edges to the front and to the back of the path in
   160        * arbitrary order then you should commit these changes to the graph.
   161        *
   162        * While the builder is active (after the first modifying
   163        * operation and until the call of \ref commit())
   164        * the underlining Path is in a
   165        * "transitional" state (operations on it have undefined result).
   166        */
   167       class Builder {
   168       public:
   169 
   170         Path &P;
   171 
   172 	///\param _P the path you want to fill in.
   173 	///
   174 	Builder(Path &_P) : P(_P) {}
   175 
   176 	/// Sets the starting node of the path.
   177       
   178 	/// Sets the starting node of the path. Edge added to the path
   179 	/// afterwards have to be incident to this node.
   180 	/// You \em must start building an empry path with this functions.
   181 	/// (And you \em must \em not use it later).
   182 	/// \sa pushFront()
   183 	/// \sa pushBack()
   184 	void setStartNode(const GraphNode &) {}
   185 
   186 	///Push a new edge to the front of the path
   187 
   188 	///Push a new edge to the front of the path.
   189 	///If the path is empty, you \em must call \ref setStartNode() before
   190 	///the first use of \ref pushFront().
   191 	void pushFront(const GraphEdge& e) {}
   192 
   193 	///Push a new edge to the back of the path
   194 
   195 	///Push a new edge to the back of the path.
   196 	///If the path is empty, you \em must call \ref setStartNode() before
   197 	///the first use of \ref pushBack().
   198 	void pushBack(const GraphEdge& e) {}
   199 
   200 	///Commit the changes to the path.
   201 	void commit() {}
   202 
   203 	///Reserve (front) storage for the builder in advance.
   204 
   205 	///If you know an reasonable upper bound of the number of the edges
   206 	///to add to the front of the path,
   207 	///using this function you may speed up the building.
   208 	void reserveFront(size_t r) {}
   209 	///Reserve (back) storage for the builder in advance.
   210 
   211 	///If you know an reasonable upper bound of the number of the edges
   212 	///to add to the back of the path,
   213 	///using this function you may speed up the building.
   214 	void reserveBack(size_t r) {}
   215       };
   216     };
   217 
   218   ///@}
   219   }
   220   
   221 } // namespace hugo
   222 
   223 #endif // HUGO_PATH_H