15 |
13 |
16 #include <invalid.h> |
14 #include <invalid.h> |
17 |
15 |
18 namespace hugo { |
16 namespace hugo { |
19 |
17 |
|
18 /// \addtogroup datas |
|
19 /// @{ |
|
20 |
|
21 ///A container for directed paths |
|
22 |
|
23 ///\param Graph The graph type in which the path is. |
|
24 /// |
|
25 ///In a sense, the path can be treated as a graph, for is has \c NodeIt |
|
26 ///and \c EdgeIt with the same usage. These types converts to the \c Node |
|
27 ///and \c Edge of the original graph. |
|
28 ///\todo How to clear a path? |
|
29 ///\todo Clarify the consistency checks to do. |
20 template<typename Graph> |
30 template<typename Graph> |
21 class DirPath { |
31 class DirPath { |
22 public: |
32 public: |
23 typedef typename Graph::Edge GraphEdge; |
33 typedef typename Graph::Edge GraphEdge; |
24 typedef typename Graph::Node GraphNode; |
34 typedef typename Graph::Node GraphNode; |
30 typedef std::vector<GraphEdge> Container; |
40 typedef std::vector<GraphEdge> Container; |
31 Container edges; |
41 Container edges; |
32 |
42 |
33 public: |
43 public: |
34 |
44 |
|
45 /// Constructor |
|
46 |
|
47 /// \param _G The graph in which the path is. |
|
48 /// |
35 DirPath(const Graph &_G) : gr(&_G) {} |
49 DirPath(const Graph &_G) : gr(&_G) {} |
36 |
50 |
37 /// Subpath defined by two nodes. |
51 /// Subpath defined by two nodes. |
38 /// It is an error if the two edges are not in order! |
52 /// \warning It is an error if the two edges are not in order! |
39 DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b); |
53 DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b); |
40 /// Subpath defined by two edges. Contains edges in [a,b) |
54 /// Subpath defined by two edges. Contains edges in [a,b) |
41 /// It is an error if the two edges are not in order! |
55 /// \warning It is an error if the two edges are not in order! |
42 DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b); |
56 DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b); |
43 |
57 |
44 size_t length() const { return edges.size(); } |
58 size_t length() const { return edges.size(); } |
45 bool empty() const { return edges.empty(); } |
59 bool empty() const { return edges.empty(); } |
46 GraphNode from() const { |
60 GraphNode from() const { |
126 private: |
140 private: |
127 void validate() { if( size_t(idx) > p->length() ) idx=-1; } |
141 void validate() { if( size_t(idx) > p->length() ) idx=-1; } |
128 }; |
142 }; |
129 |
143 |
130 friend class Builder; |
144 friend class Builder; |
|
145 |
|
146 ///Class to build paths |
|
147 |
|
148 ///\ingroup datas |
|
149 ///This class is used to build new paths. |
|
150 ///You can push new edges to the front and to the back of the path in |
|
151 ///arbitrary order the you can commit these changes to the graph. |
|
152 ///\todo We must clarify when the path will be in "transitional" state. |
131 class Builder { |
153 class Builder { |
132 DirPath &P; |
154 DirPath &P; |
133 Container d; |
155 Container d; |
134 |
156 |
135 public: |
157 public: |
|
158 ///Constructor |
|
159 |
|
160 ///\param _P the path you want to build. |
|
161 /// |
136 Builder(DirPath &_P) : P(_P) {} |
162 Builder(DirPath &_P) : P(_P) {} |
137 |
163 |
|
164 ///Set the first node of the path. |
|
165 |
|
166 ///Set the first node of the path. |
|
167 ///If the path is empty, this must be call before any call of |
|
168 ///\ref pushFront() or \ref pushBack() |
|
169 void setFirst(const GraphNode &) { } |
|
170 |
|
171 ///Push a new edge to the front of the path |
|
172 |
|
173 ///Push a new edge to the front of the path. |
|
174 ///\sa setFirst() |
138 bool pushFront(const GraphEdge& e) { |
175 bool pushFront(const GraphEdge& e) { |
139 if( empty() || P.gr->head(e)==from() ) { |
176 if( empty() || P.gr->head(e)==from() ) { |
140 d.push_back(e); |
177 d.push_back(e); |
141 return true; |
178 return true; |
142 } |
179 } |
143 return false; |
180 return false; |
144 } |
181 } |
|
182 ///Push a new edge to the back of the path |
|
183 |
|
184 ///Push a new edge to the back of the path. |
|
185 ///\sa setFirst() |
145 bool pushBack(const GraphEdge& e) { |
186 bool pushBack(const GraphEdge& e) { |
146 if( empty() || P.gr->tail(e)==to() ) { |
187 if( empty() || P.gr->tail(e)==to() ) { |
147 P.edges.push_back(e); |
188 P.edges.push_back(e); |
148 return true; |
189 return true; |
149 } |
190 } |
150 return false; |
191 return false; |
151 } |
192 } |
152 |
193 |
|
194 ///Commit the changes to the path. |
153 void commit() { |
195 void commit() { |
154 if( !d.empty() ) { |
196 if( !d.empty() ) { |
155 P.edges.insert(P.edges.begin(), d.rbegin(), d.rend()); |
197 P.edges.insert(P.edges.begin(), d.rbegin(), d.rend()); |
156 d.clear(); |
198 d.clear(); |
157 } |
199 } |
158 } |
200 } |
159 |
201 |
|
202 ///Desctuctor |
|
203 |
|
204 ///The desctuctor. |
|
205 ///It commit also commit the changes. |
|
206 ///\todo Is this what we want? |
160 ~Builder() { commit(); } |
207 ~Builder() { commit(); } |
161 |
208 |
162 // FIXME: Hmm, pontosan hogy is kene ezt csinalni? |
209 // FIXME: Hmm, pontosan hogy is kene ezt csinalni? |
163 // Hogy kenyelmes egy ilyet hasznalni? |
210 // Hogy kenyelmes egy ilyet hasznalni? |
164 void reserve(size_t r) { |
211 void reserve(size_t r) { |