1.1 --- a/src/work/klao/path.h Tue Jun 15 06:30:03 2004 +0000
1.2 +++ b/src/work/klao/path.h Wed Jun 16 09:44:30 2004 +0000
1.3 @@ -1,6 +1,20 @@
1.4 // -*- c++ -*- //
1.5
1.6 -///\ingroup datas
1.7 +/**
1.8 +@defgroup paths Path Structures
1.9 +@ingroup datas
1.10 +\brief Path structures implemented in Hugo.
1.11 +
1.12 +Hugolib provides flexible data structures
1.13 +to work with paths.
1.14 +
1.15 +All of them have the same interface, especially they can be built or extended
1.16 +using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
1.17 +algorithm to store its result in any kind of path structure.
1.18 +
1.19 +*/
1.20 +
1.21 +///\ingroup paths
1.22 ///\file
1.23 ///\brief Classes for representing paths in graphs.
1.24
1.25 @@ -17,7 +31,7 @@
1.26
1.27 namespace hugo {
1.28
1.29 - /// \addtogroup datas
1.30 + /// \addtogroup paths
1.31 /// @{
1.32
1.33
1.34 @@ -35,7 +49,9 @@
1.35 template<typename Graph, typename DM = DefaultDebugMode>
1.36 class DirPath {
1.37 public:
1.38 - typedef typename Graph::Edge GraphEdge;
1.39 + /// Edge type of the underlying graph.
1.40 + typedef typename Graph::Edge GraphEdge;
1.41 + /// Node type of the underlying graph.
1.42 typedef typename Graph::Node GraphNode;
1.43 class NodeIt;
1.44 class EdgeIt;
1.45 @@ -152,27 +168,49 @@
1.46 }
1.47
1.48
1.49 - /*** Iterator classes ***/
1.50 + /* Iterator classes */
1.51 +
1.52 + /**
1.53 + * \brief Iterator class to iterate on the edges of the paths
1.54 + *
1.55 + * \ingroup paths
1.56 + * This class is used to iterate on the edges of the paths
1.57 + *
1.58 + * Of course it converts to Graph::Edge
1.59 + *
1.60 + * \todo Its interface differs from the standard edge iterator.
1.61 + * Yes, it shouldn't.
1.62 + */
1.63 class EdgeIt {
1.64 friend class DirPath;
1.65
1.66 int idx;
1.67 const DirPath *p;
1.68 public:
1.69 + /// Default constructor
1.70 EdgeIt() {}
1.71 + /// Invalid constructor
1.72 EdgeIt(Invalid) : idx(-1), p(0) {}
1.73 + /// Constructor with starting point
1.74 EdgeIt(const DirPath &_p, int _idx = 0) :
1.75 idx(_idx), p(&_p) { validate(); }
1.76
1.77 + ///Validity check
1.78 bool valid() const { return idx!=-1; }
1.79
1.80 + ///Conversion to Graph::Edge
1.81 operator GraphEdge () const {
1.82 return valid() ? p->edges[idx] : INVALID;
1.83 }
1.84 +
1.85 + /// Next edge
1.86 EdgeIt& operator++() { ++idx; validate(); return *this; }
1.87
1.88 + /// Comparison operator
1.89 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
1.90 + /// Comparison operator
1.91 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
1.92 + /// Comparison operator
1.93 bool operator<(const EdgeIt& e) const { return idx<e.idx; }
1.94
1.95 private:
1.96 @@ -181,19 +219,35 @@
1.97 void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
1.98 };
1.99
1.100 + /**
1.101 + * \brief Iterator class to iterate on the nodes of the paths
1.102 + *
1.103 + * \ingroup paths
1.104 + * This class is used to iterate on the nodes of the paths
1.105 + *
1.106 + * Of course it converts to Graph::Node
1.107 + *
1.108 + * \todo Its interface differs from the standard node iterator.
1.109 + * Yes, it shouldn't.
1.110 + */
1.111 class NodeIt {
1.112 friend class DirPath;
1.113
1.114 int idx;
1.115 const DirPath *p;
1.116 public:
1.117 + /// Default constructor
1.118 NodeIt() {}
1.119 + /// Invalid constructor
1.120 NodeIt(Invalid) : idx(-1), p(0) {}
1.121 + /// Constructor with starting point
1.122 NodeIt(const DirPath &_p, int _idx = 0) :
1.123 idx(_idx), p(&_p) { validate(); }
1.124
1.125 + ///Validity check
1.126 bool valid() const { return idx!=-1; }
1.127
1.128 + ///Conversion to Graph::Node
1.129 operator const GraphNode& () const {
1.130 if(idx >= p->length())
1.131 return p->to();
1.132 @@ -202,10 +256,14 @@
1.133 else
1.134 return INVALID;
1.135 }
1.136 + /// Next node
1.137 NodeIt& operator++() { ++idx; validate(); return *this; }
1.138
1.139 + /// Comparison operator
1.140 bool operator==(const NodeIt& e) const { return idx==e.idx; }
1.141 + /// Comparison operator
1.142 bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
1.143 + /// Comparison operator
1.144 bool operator<(const NodeIt& e) const { return idx<e.idx; }
1.145
1.146 private:
1.147 @@ -217,7 +275,7 @@
1.148 /**
1.149 * \brief Class to build paths
1.150 *
1.151 - * \ingroup datas
1.152 + * \ingroup paths
1.153 * This class is used to fill a path with edges.
1.154 *
1.155 * You can push new edges to the front and to the back of the path in
1.156 @@ -285,6 +343,11 @@
1.157
1.158 // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
1.159 // Hogy kenyelmes egy ilyet hasznalni?
1.160 +
1.161 + ///Reserve storage in advance for the builder
1.162 +
1.163 + ///If you know an reasonable upper bound of the number of the edges
1.164 + ///to add, using this function you can speed up the building.
1.165 void reserve(size_t r) {
1.166 front.reserve(r);
1.167 back.reserve(r);
1.168 @@ -349,8 +412,10 @@
1.169 template<typename Graph, typename DM = DefaultDebugMode>
1.170 class UndirPath {
1.171 public:
1.172 + /// Edge type of the underlying graph.
1.173 typedef typename Graph::Edge GraphEdge;
1.174 - typedef typename Graph::Node GraphNode;
1.175 + /// Node type of the underlying graph.
1.176 + typedef typename Graph::Node GraphNode;
1.177 class NodeIt;
1.178 class EdgeIt;
1.179
1.180 @@ -466,27 +531,47 @@
1.181 }
1.182
1.183
1.184 - /*** Iterator classes ***/
1.185 +
1.186 + /**
1.187 + * \brief Iterator class to iterate on the edges of the paths
1.188 + *
1.189 + * \ingroup paths
1.190 + * This class is used to iterate on the edges of the paths
1.191 + *
1.192 + * Of course it converts to Graph::Edge
1.193 + *
1.194 + * \todo Its interface differs from the standard edge iterator.
1.195 + * Yes, it shouldn't.
1.196 + */
1.197 class EdgeIt {
1.198 friend class UndirPath;
1.199
1.200 int idx;
1.201 const UndirPath *p;
1.202 public:
1.203 + /// Default constructor
1.204 EdgeIt() {}
1.205 + /// Invalid constructor
1.206 EdgeIt(Invalid) : idx(-1), p(0) {}
1.207 + /// Constructor with starting point
1.208 EdgeIt(const UndirPath &_p, int _idx = 0) :
1.209 idx(_idx), p(&_p) { validate(); }
1.210
1.211 + ///Validity check
1.212 bool valid() const { return idx!=-1; }
1.213
1.214 + ///Conversion to Graph::Edge
1.215 operator GraphEdge () const {
1.216 return valid() ? p->edges[idx] : INVALID;
1.217 }
1.218 - EdgeIt& operator++() { ++idx; validate(); return *this; }
1.219 + /// Next edge
1.220 + EdgeIt& operator++() { ++idx; validate(); return *this; }
1.221
1.222 + /// Comparison operator
1.223 bool operator==(const EdgeIt& e) const { return idx==e.idx; }
1.224 + /// Comparison operator
1.225 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; }
1.226 + /// Comparison operator
1.227 bool operator<(const EdgeIt& e) const { return idx<e.idx; }
1.228
1.229 private:
1.230 @@ -495,19 +580,35 @@
1.231 void validate() { if( size_t(idx) >= p->length() ) idx=-1; }
1.232 };
1.233
1.234 + /**
1.235 + * \brief Iterator class to iterate on the nodes of the paths
1.236 + *
1.237 + * \ingroup paths
1.238 + * This class is used to iterate on the nodes of the paths
1.239 + *
1.240 + * Of course it converts to Graph::Node
1.241 + *
1.242 + * \todo Its interface differs from the standard node iterator.
1.243 + * Yes, it shouldn't.
1.244 + */
1.245 class NodeIt {
1.246 friend class UndirPath;
1.247
1.248 int idx;
1.249 const UndirPath *p;
1.250 public:
1.251 + /// Default constructor
1.252 NodeIt() {}
1.253 + /// Invalid constructor
1.254 NodeIt(Invalid) : idx(-1), p(0) {}
1.255 + /// Constructor with starting point
1.256 NodeIt(const UndirPath &_p, int _idx = 0) :
1.257 idx(_idx), p(&_p) { validate(); }
1.258
1.259 + ///Validity check
1.260 bool valid() const { return idx!=-1; }
1.261
1.262 + ///Conversion to Graph::Node
1.263 operator const GraphNode& () const {
1.264 if(idx >= p->length())
1.265 return p->to();
1.266 @@ -516,11 +617,15 @@
1.267 else
1.268 return INVALID;
1.269 }
1.270 + /// Next node
1.271 NodeIt& operator++() { ++idx; validate(); return *this; }
1.272
1.273 + /// Comparison operator
1.274 bool operator==(const NodeIt& e) const { return idx==e.idx; }
1.275 + /// Comparison operator
1.276 bool operator!=(const NodeIt& e) const { return idx!=e.idx; }
1.277 - bool operator<(const NodeIt& e) const { return idx<e.idx; }
1.278 + /// Comparison operator
1.279 + bool operator<(const NodeIt& e) const { return idx<e.idx; }
1.280
1.281 private:
1.282 void validate() { if( size_t(idx) > p->length() ) idx=-1; }
1.283 @@ -531,7 +636,7 @@
1.284 /**
1.285 * \brief Class to build paths
1.286 *
1.287 - * \ingroup datas
1.288 + * \ingroup paths
1.289 * This class is used to fill a path with edges.
1.290 *
1.291 * You can push new edges to the front and to the back of the path in
1.292 @@ -599,7 +704,12 @@
1.293
1.294 // FIXME: Hmm, pontosan hogy is kene ezt csinalni?
1.295 // Hogy kenyelmes egy ilyet hasznalni?
1.296 - void reserve(size_t r) {
1.297 +
1.298 + ///Reserve storage in advance for the builder
1.299 +
1.300 + ///If you know an reasonable upper bound of the number of the edges
1.301 + ///to add, using this function you can speed up the building.
1.302 + void reserve(size_t r) {
1.303 front.reserve(r);
1.304 back.reserve(r);
1.305 }