| changeset 382 | f177fc597abd |
| parent 227 | cea88d0854a9 |
| child 434 | 1ce1b4cd8dd5 |
| 2:5ef48abed30a | 3:74fd68a5773d |
|---|---|
8 |
8 |
9 #ifndef HUGO_PATH_H |
9 #ifndef HUGO_PATH_H |
10 #define HUGO_PATH_H |
10 #define HUGO_PATH_H |
11 |
11 |
12 #include <deque> |
12 #include <deque> |
13 #include <vector> |
|
13 #include <algorithm> |
14 #include <algorithm> |
14 |
15 |
15 #include <invalid.h> |
16 #include <invalid.h> |
16 |
17 |
17 namespace hugo { |
18 namespace hugo { |
19 |
|
20 template<typename Graph> |
|
21 class DirPath { |
|
22 public: |
|
23 typedef typename Graph::Edge GraphEdge; |
|
24 typedef typename Graph::Node GraphNode; |
|
25 class NodeIt; |
|
26 class EdgeIt; |
|
27 |
|
28 protected: |
|
29 const Graph *gr; |
|
30 typedef std::vector<GraphEdge> Container; |
|
31 Container edges; |
|
32 |
|
33 public: |
|
34 |
|
35 DirPath(const Graph &_G) : gr(&_G) {} |
|
36 |
|
37 /// Subpath defined by two nodes. |
|
38 /// It is an error if the two edges are not in order! |
|
39 DirPath(const DirPath &P, const NodeIt &a, const NodeIt &b); |
|
40 /// Subpath defined by two edges. Contains edges in [a,b) |
|
41 /// It is an error if the two edges are not in order! |
|
42 DirPath(const DirPath &P, const EdgeIt &a, const EdgeIt &b); |
|
43 |
|
44 size_t length() const { return edges.size(); } |
|
45 bool empty() const { return edges.empty(); } |
|
46 GraphNode from() const { |
|
47 return empty() ? INVALID : gr->tail(edges[0]); |
|
48 } |
|
49 GraphNode to() const { |
|
50 return empty() ? INVALID : gr->head(edges[length()-1]); |
|
51 } |
|
52 |
|
53 template<typename It> |
|
54 It& first(It &i) const { return i=It(*this); } |
|
55 |
|
56 template<typename It> |
|
57 It& nth(It &i, int n) const { return i=It(*this, n); } |
|
58 |
|
59 template<typename It> |
|
60 bool valid(const It &i) const { return i.valid(); } |
|
61 |
|
62 template<typename It> |
|
63 It& next(It &e) const { return ++e; } |
|
64 |
|
65 /// \todo ! |
|
66 NodeIt head(const EdgeIt& e) const; |
|
67 NodeIt tail(const EdgeIt& e) const; |
|
68 |
|
69 |
|
70 /*** Iterator classes ***/ |
|
71 class EdgeIt { |
|
72 friend class DirPath; |
|
73 |
|
74 int idx; |
|
75 const DirPath *p; |
|
76 public: |
|
77 EdgeIt() {} |
|
78 EdgeIt(Invalid) : idx(-1), p(0) {} |
|
79 EdgeIt(const DirPath &_p, int _idx = 0) : |
|
80 idx(_idx), p(&_p) { validate(); } |
|
81 |
|
82 bool valid() const { return idx!=-1; } |
|
83 |
|
84 operator GraphEdge () const { |
|
85 return valid() ? p->edges[idx] : INVALID; |
|
86 } |
|
87 EdgeIt& operator++() { ++idx; validate(); return *this; } |
|
88 |
|
89 bool operator==(const EdgeIt& e) const { return idx==e.idx; } |
|
90 bool operator!=(const EdgeIt& e) const { return idx!=e.idx; } |
|
91 bool operator<(const EdgeIt& e) const { return idx<e.idx; } |
|
92 |
|
93 private: |
|
94 // FIXME: comparison between signed and unsigned... |
|
95 // Jo ez igy? Vagy esetleg legyen a length() int? |
|
96 void validate() { if( size_t(idx) >= p->length() ) idx=-1; } |
|
97 }; |
|
98 |
|
99 class NodeIt { |
|
100 friend class DirPath; |
|
101 |
|
102 int idx; |
|
103 const DirPath *p; |
|
104 public: |
|
105 NodeIt() {} |
|
106 NodeIt(Invalid) : idx(-1), p(0) {} |
|
107 NodeIt(const DirPath &_p, int _idx = 0) : |
|
108 idx(_idx), p(&_p) { validate(); } |
|
109 |
|
110 bool valid() const { return idx!=-1; } |
|
111 |
|
112 operator const GraphEdge& () const { |
|
113 if(idx >= p->length()) |
|
114 return p->to(); |
|
115 else if(idx >= 0) |
|
116 return p->gr->tail(p->edges[idx]); |
|
117 else |
|
118 return INVALID; |
|
119 } |
|
120 NodeIt& operator++() { ++idx; validate(); return *this; } |
|
121 |
|
122 bool operator==(const NodeIt& e) const { return idx==e.idx; } |
|
123 bool operator!=(const NodeIt& e) const { return idx!=e.idx; } |
|
124 bool operator<(const NodeIt& e) const { return idx<e.idx; } |
|
125 |
|
126 private: |
|
127 void validate() { if( size_t(idx) > p->length() ) idx=-1; } |
|
128 }; |
|
129 |
|
130 friend class Builder; |
|
131 class Builder { |
|
132 DirPath &P; |
|
133 Container d; |
|
134 |
|
135 public: |
|
136 Builder(DirPath &_P) : P(_P) {} |
|
137 |
|
138 bool pushFront(const GraphEdge& e) { |
|
139 if( empty() || P.gr->head(e)==from() ) { |
|
140 d.push_back(e); |
|
141 return true; |
|
142 } |
|
143 return false; |
|
144 } |
|
145 bool pushBack(const GraphEdge& e) { |
|
146 if( empty() || P.gr->tail(e)==to() ) { |
|
147 P.edges.push_back(e); |
|
148 return true; |
|
149 } |
|
150 return false; |
|
151 } |
|
152 |
|
153 void commit() { |
|
154 if( !d.empty() ) { |
|
155 P.edges.insert(P.edges.begin(), d.rbegin(), d.rend()); |
|
156 d.clear(); |
|
157 } |
|
158 } |
|
159 |
|
160 ~Builder() { commit(); } |
|
161 |
|
162 // FIXME: Hmm, pontosan hogy is kene ezt csinalni? |
|
163 // Hogy kenyelmes egy ilyet hasznalni? |
|
164 void reserve(size_t r) { |
|
165 d.reserve(r); |
|
166 P.edges.reserve(P.length()+r); |
|
167 } |
|
168 |
|
169 private: |
|
170 bool empty() { return d.empty() && P.empty(); } |
|
171 |
|
172 GraphNode from() const { |
|
173 if( ! d.empty() ) |
|
174 return P.gr->tail(d[d.size()-1]); |
|
175 else if( ! P.empty() ) |
|
176 return P.gr->tail(P.edges[0]); |
|
177 else |
|
178 return INVALID; |
|
179 } |
|
180 GraphNode to() const { |
|
181 if( ! P.empty() ) |
|
182 return P.gr->head(P.edges[P.length()-1]); |
|
183 else if( ! d.empty() ) |
|
184 return P.gr->head(d[0]); |
|
185 else |
|
186 return INVALID; |
|
187 } |
|
188 |
|
189 }; |
|
190 |
|
191 }; |
|
192 |
|
193 |
|
194 |
|
195 |
|
196 |
|
197 |
|
198 |
|
199 |
|
200 |
|
201 |
|
202 |
|
203 /**********************************************************************/ |
|
204 |
|
18 |
205 |
19 /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata |
206 /* Ennek az allocatorosdinak sokkal jobban utana kene nezni a hasznalata |
20 elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */ |
207 elott. Eleg bonyinak nez ki, ahogyan azokat az STL-ben hasznaljak. */ |
21 |
208 |
22 template<typename Graph> |
209 template<typename Graph> |
23 class Path { |
210 class DynamicPath { |
24 |
211 |
25 public: |
212 public: |
26 typedef typename Graph::Edge GraphEdge; |
213 typedef typename Graph::Edge GraphEdge; |
27 typedef typename Graph::Node GraphNode; |
214 typedef typename Graph::Node GraphNode; |
28 class NodeIt; |
215 class NodeIt; |
36 typedef std::deque<GraphEdge> Container; |
223 typedef std::deque<GraphEdge> Container; |
37 Container edges; |
224 Container edges; |
38 |
225 |
39 public: |
226 public: |
40 |
227 |
41 Path(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {} |
228 DynamicPath(Graph &_G) : G(_G), _first(INVALID), _last(INVALID) {} |
42 |
229 |
43 /// Subpath defined by two nodes. |
230 /// Subpath defined by two nodes. |
44 /// Nodes may be in reversed order, then |
231 /// Nodes may be in reversed order, then |
45 /// we contstruct the reversed path. |
232 /// we contstruct the reversed path. |
46 Path(const Path &P, const NodeIt &a, const NodeIt &b); |
233 DynamicPath(const DynamicPath &P, const NodeIt &a, const NodeIt &b); |
47 /// Subpath defined by two edges. Contains edges in [a,b) |
234 /// Subpath defined by two edges. Contains edges in [a,b) |
48 /// It is an error if the two edges are not in order! |
235 /// It is an error if the two edges are not in order! |
49 Path(const Path &P, const EdgeIt &a, const EdgeIt &b); |
236 DynamicPath(const DynamicPath &P, const EdgeIt &a, const EdgeIt &b); |
50 |
237 |
51 size_t length() const { return edges.size(); } |
238 size_t length() const { return edges.size(); } |
52 GraphNode from() const { return _first; } |
239 GraphNode from() const { return _first; } |
53 GraphNode to() const { return _last; } |
240 GraphNode to() const { return _last; } |
54 |
241 |
110 GraphNode graphNode(const NodeIt& n) const; |
297 GraphNode graphNode(const NodeIt& n) const; |
111 |
298 |
112 |
299 |
113 /*** Iterator classes ***/ |
300 /*** Iterator classes ***/ |
114 class EdgeIt { |
301 class EdgeIt { |
115 friend class Path; |
302 friend class DynamicPath; |
116 |
303 |
117 typename Container::const_iterator it; |
304 typename Container::const_iterator it; |
118 bool forw; |
305 bool forw; |
119 public: |
306 public: |
120 // FIXME: jarna neki ilyen is... |
307 // FIXME: jarna neki ilyen is... |
126 bool operator!=(const EdgeIt& e) const { return it!=e.it; } |
313 bool operator!=(const EdgeIt& e) const { return it!=e.it; } |
127 bool operator<(const EdgeIt& e) const { return it<e.it; } |
314 bool operator<(const EdgeIt& e) const { return it<e.it; } |
128 }; |
315 }; |
129 |
316 |
130 class NodeIt { |
317 class NodeIt { |
131 friend class Path; |
318 friend class DynamicPath; |
132 friend class EdgeIt; |
|
133 |
319 |
134 size_t idx; |
320 size_t idx; |
135 bool tail; // Is this node the tail of the edge with same idx? |
321 bool tail; // Is this node the tail of the edge with same idx? |
136 |
322 |
137 public: |
323 public: |
148 GraphNode &b); |
334 GraphNode &b); |
149 bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f); |
335 bool connectTwoEdges(const GraphEdge &e, const GraphEdge &f); |
150 }; |
336 }; |
151 |
337 |
152 template<typename Gr> |
338 template<typename Gr> |
153 typename Path<Gr>::EdgeIt& |
339 typename DynamicPath<Gr>::EdgeIt& |
154 Path<Gr>::next(Path::EdgeIt &e) const { |
340 DynamicPath<Gr>::next(DynamicPath::EdgeIt &e) const { |
155 if( e.it == edges.end() ) |
341 if( e.it == edges.end() ) |
156 return e; |
342 return e; |
157 |
343 |
158 GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) ); |
344 GraphNode common_node = ( e.forw ? G.head(*e.it) : G.tail(*e.it) ); |
159 ++e.it; |
345 ++e.it; |
167 e.forw = ( G.tail(*e.it) == common_node ); |
353 e.forw = ( G.tail(*e.it) == common_node ); |
168 return e; |
354 return e; |
169 } |
355 } |
170 |
356 |
171 template<typename Gr> |
357 template<typename Gr> |
172 typename Path<Gr>::NodeIt& Path<Gr>::next(NodeIt &n) const { |
358 typename DynamicPath<Gr>::NodeIt& DynamicPath<Gr>::next(NodeIt &n) const { |
173 if( n.idx >= length() ) { |
359 if( n.idx >= length() ) { |
174 // FIXME: invalid |
360 // FIXME: invalid |
175 n.idx = length()+1; |
361 n.idx = length()+1; |
176 return n; |
362 return n; |
177 } |
363 } |
189 |
375 |
190 return n; |
376 return n; |
191 } |
377 } |
192 |
378 |
193 template<typename Gr> |
379 template<typename Gr> |
194 bool Path<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a, |
380 bool DynamicPath<Gr>::edgeIncident(const GraphEdge &e, const GraphNode &a, |
195 GraphNode &b) { |
381 GraphNode &b) { |
196 if( G.tail(e) == a ) { |
382 if( G.tail(e) == a ) { |
197 b=G.head(e); |
383 b=G.head(e); |
198 return true; |
384 return true; |
199 } |
385 } |
203 } |
389 } |
204 return false; |
390 return false; |
205 } |
391 } |
206 |
392 |
207 template<typename Gr> |
393 template<typename Gr> |
208 bool Path<Gr>::connectTwoEdges(const GraphEdge &e, |
394 bool DynamicPath<Gr>::connectTwoEdges(const GraphEdge &e, |
209 const GraphEdge &f) { |
395 const GraphEdge &f) { |
210 if( edgeIncident(f, G.tail(e), _last) ) { |
396 if( edgeIncident(f, G.tail(e), _last) ) { |
211 _first = G.head(e); |
397 _first = G.head(e); |
212 return true; |
398 return true; |
213 } |
399 } |
217 } |
403 } |
218 return false; |
404 return false; |
219 } |
405 } |
220 |
406 |
221 template<typename Gr> |
407 template<typename Gr> |
222 bool Path<Gr>::pushFront(const GraphEdge &e) { |
408 bool DynamicPath<Gr>::pushFront(const GraphEdge &e) { |
223 if( G.valid(_first) ) { |
409 if( G.valid(_first) ) { |
224 if( edgeIncident(e, _first, _first) ) { |
410 if( edgeIncident(e, _first, _first) ) { |
225 edges.push_front(e); |
411 edges.push_front(e); |
226 return true; |
412 return true; |
227 } |
413 } |
235 else |
421 else |
236 return false; |
422 return false; |
237 } |
423 } |
238 |
424 |
239 template<typename Gr> |
425 template<typename Gr> |
240 bool Path<Gr>::pushBack(const GraphEdge &e) { |
426 bool DynamicPath<Gr>::pushBack(const GraphEdge &e) { |
241 if( G.valid(_last) ) { |
427 if( G.valid(_last) ) { |
242 if( edgeIncident(e, _last, _last) ) { |
428 if( edgeIncident(e, _last, _last) ) { |
243 edges.push_back(e); |
429 edges.push_back(e); |
244 return true; |
430 return true; |
245 } |
431 } |
254 return false; |
440 return false; |
255 } |
441 } |
256 |
442 |
257 |
443 |
258 template<typename Gr> |
444 template<typename Gr> |
259 bool Path<Gr>::setFrom(const GraphNode &n) { |
445 bool DynamicPath<Gr>::setFrom(const GraphNode &n) { |
260 if( G.valid(_first) ) { |
446 if( G.valid(_first) ) { |
261 return _first == n; |
447 return _first == n; |
262 } |
448 } |
263 else { |
449 else { |
264 if( length() > 0) { |
450 if( length() > 0) { |
274 } |
460 } |
275 } |
461 } |
276 } |
462 } |
277 |
463 |
278 template<typename Gr> |
464 template<typename Gr> |
279 bool Path<Gr>::setTo(const GraphNode &n) { |
465 bool DynamicPath<Gr>::setTo(const GraphNode &n) { |
280 if( G.valid(_last) ) { |
466 if( G.valid(_last) ) { |
281 return _last == n; |
467 return _last == n; |
282 } |
468 } |
283 else { |
469 else { |
284 if( length() > 0) { |
470 if( length() > 0) { |
295 } |
481 } |
296 } |
482 } |
297 |
483 |
298 |
484 |
299 template<typename Gr> |
485 template<typename Gr> |
300 typename Path<Gr>::NodeIt |
486 typename DynamicPath<Gr>::NodeIt |
301 Path<Gr>::tail(const EdgeIt& e) const { |
487 DynamicPath<Gr>::tail(const EdgeIt& e) const { |
302 NodeIt n; |
488 NodeIt n; |
303 |
489 |
304 if( e.it == edges.end() ) { |
490 if( e.it == edges.end() ) { |
305 // FIXME: invalid-> invalid |
491 // FIXME: invalid-> invalid |
306 n.idx = length() + 1; |
492 n.idx = length() + 1; |
312 n.tail = e.forw; |
498 n.tail = e.forw; |
313 return n; |
499 return n; |
314 } |
500 } |
315 |
501 |
316 template<typename Gr> |
502 template<typename Gr> |
317 typename Path<Gr>::NodeIt |
503 typename DynamicPath<Gr>::NodeIt |
318 Path<Gr>::head(const EdgeIt& e) const { |
504 DynamicPath<Gr>::head(const EdgeIt& e) const { |
319 if( e.it == edges.end()-1 ) { |
505 if( e.it == edges.end()-1 ) { |
320 return _last; |
506 return _last; |
321 } |
507 } |
322 |
508 |
323 EdgeIt next_edge = e; |
509 EdgeIt next_edge = e; |
324 next(next_edge); |
510 next(next_edge); |
325 return tail(next_edge); |
511 return tail(next_edge); |
326 } |
512 } |
327 |
513 |
328 template<typename Gr> |
514 template<typename Gr> |
329 typename Path<Gr>::GraphEdge |
515 typename DynamicPath<Gr>::GraphEdge |
330 Path<Gr>::graphEdge(const EdgeIt& e) const { |
516 DynamicPath<Gr>::graphEdge(const EdgeIt& e) const { |
331 if( e.it != edges.end() ) { |
517 if( e.it != edges.end() ) { |
332 return *e.it; |
518 return *e.it; |
333 } |
519 } |
334 else { |
520 else { |
335 return INVALID; |
521 return INVALID; |
336 } |
522 } |
337 } |
523 } |
338 |
524 |
339 template<typename Gr> |
525 template<typename Gr> |
340 typename Path<Gr>::GraphNode |
526 typename DynamicPath<Gr>::GraphNode |
341 Path<Gr>::graphNode(const NodeIt& n) const { |
527 DynamicPath<Gr>::graphNode(const NodeIt& n) const { |
342 if( n.idx < length() ) { |
528 if( n.idx < length() ) { |
343 return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]); |
529 return n.tail ? G.tail(edges[n.idx]) : G.head(edges[n.idx]); |
344 } |
530 } |
345 else if( n.idx == length() ) { |
531 else if( n.idx == length() ) { |
346 return _last; |
532 return _last; |
349 return INVALID; |
535 return INVALID; |
350 } |
536 } |
351 } |
537 } |
352 |
538 |
353 template<typename Gr> |
539 template<typename Gr> |
354 typename Path<Gr>::EdgeIt& Path<Gr>::nth(EdgeIt &e, size_t k) const { |
540 typename DynamicPath<Gr>::EdgeIt& |
541 DynamicPath<Gr>::nth(EdgeIt &e, size_t k) const { |
|
355 if( k<0 || k>=length() ) { |
542 if( k<0 || k>=length() ) { |
356 // FIXME: invalid EdgeIt |
543 // FIXME: invalid EdgeIt |
357 e.it = edges.end(); |
544 e.it = edges.end(); |
358 e.forw = true; |
545 e.forw = true; |
359 return e; |
546 return e; |
369 } |
556 } |
370 return e; |
557 return e; |
371 } |
558 } |
372 |
559 |
373 template<typename Gr> |
560 template<typename Gr> |
374 typename Path<Gr>::NodeIt& Path<Gr>::nth(NodeIt &n, size_t k) const { |
561 typename DynamicPath<Gr>::NodeIt& |
562 DynamicPath<Gr>::nth(NodeIt &n, size_t k) const { |
|
375 if( k<0 || k>length() ) { |
563 if( k<0 || k>length() ) { |
376 // FIXME: invalid NodeIt |
564 // FIXME: invalid NodeIt |
377 n.idx = length()+1; |
565 n.idx = length()+1; |
378 n.tail = true; |
566 n.tail = true; |
379 return n; |
567 return n; |
389 |
577 |
390 // Reszut konstruktorok: |
578 // Reszut konstruktorok: |
391 |
579 |
392 |
580 |
393 template<typename Gr> |
581 template<typename Gr> |
394 Path<Gr>::Path(const Path &P, const EdgeIt &a, const EdgeIt &b) : |
582 DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const EdgeIt &a, |
583 const EdgeIt &b) : |
|
395 G(P.G), edges(a.it, b.it) // WARNING: if b.it < a.it this will blow up! |
584 G(P.G), edges(a.it, b.it) // WARNING: if b.it < a.it this will blow up! |
396 { |
585 { |
397 if( G.valid(P._first) && a.it < P.edges.end() ) { |
586 if( G.valid(P._first) && a.it < P.edges.end() ) { |
398 _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) ); |
587 _first = ( a.forw ? G.tail(*a.it) : G.head(*a.it) ); |
399 if( b.it < P.edges.end() ) { |
588 if( b.it < P.edges.end() ) { |
404 } |
593 } |
405 } |
594 } |
406 } |
595 } |
407 |
596 |
408 template<typename Gr> |
597 template<typename Gr> |
409 Path<Gr>::Path(const Path &P, const NodeIt &a, const NodeIt &b) : |
598 DynamicPath<Gr>::DynamicPath(const DynamicPath &P, const NodeIt &a, |
410 G(P.G) |
599 const NodeIt &b) : G(P.G) |
411 { |
600 { |
412 if( !P.valid(a) || !P.valid(b) ) |
601 if( !P.valid(a) || !P.valid(b) ) |
413 return; |
602 return; |
414 |
603 |
415 int ai = a.idx, bi = b.idx; |
604 int ai = a.idx, bi = b.idx; |