1 // -*- c++ -*- |
|
2 #ifndef LEMON_ITERABLE_GRAPH_EXTENDER_H |
|
3 #define LEMON_ITERABLE_GRAPH_EXTENDER_H |
|
4 |
|
5 #include <lemon/invalid.h> |
|
6 |
|
7 namespace lemon { |
|
8 |
|
9 template <typename _Base> |
|
10 class IterableGraphExtender : public _Base { |
|
11 public: |
|
12 |
|
13 typedef _Base Parent; |
|
14 typedef IterableGraphExtender<_Base> Graph; |
|
15 |
|
16 typedef typename Parent::Node Node; |
|
17 typedef typename Parent::Edge Edge; |
|
18 |
|
19 |
|
20 class NodeIt : public Node { |
|
21 const Graph* graph; |
|
22 public: |
|
23 |
|
24 NodeIt() {} |
|
25 |
|
26 NodeIt(Invalid i) : Node(i) { } |
|
27 |
|
28 explicit NodeIt(const Graph& _graph) : graph(&_graph) { |
|
29 _graph.first(*static_cast<Node*>(this)); |
|
30 } |
|
31 |
|
32 NodeIt(const Graph& _graph, const Node& node) |
|
33 : Node(node), graph(&_graph) {} |
|
34 |
|
35 NodeIt& operator++() { |
|
36 graph->next(*this); |
|
37 return *this; |
|
38 } |
|
39 |
|
40 }; |
|
41 |
|
42 |
|
43 class EdgeIt : public Edge { |
|
44 const Graph* graph; |
|
45 public: |
|
46 |
|
47 EdgeIt() { } |
|
48 |
|
49 EdgeIt(Invalid i) : Edge(i) { } |
|
50 |
|
51 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { |
|
52 _graph.first(*static_cast<Edge*>(this)); |
|
53 } |
|
54 |
|
55 EdgeIt(const Graph& _graph, const Edge& e) : |
|
56 Edge(e), graph(&_graph) { } |
|
57 |
|
58 EdgeIt& operator++() { |
|
59 graph->next(*this); |
|
60 return *this; |
|
61 } |
|
62 |
|
63 }; |
|
64 |
|
65 |
|
66 class OutEdgeIt : public Edge { |
|
67 const Graph* graph; |
|
68 public: |
|
69 |
|
70 OutEdgeIt() { } |
|
71 |
|
72 OutEdgeIt(Invalid i) : Edge(i) { } |
|
73 |
|
74 OutEdgeIt(const Graph& _graph, const Node& node) |
|
75 : graph(&_graph) { |
|
76 _graph.firstOut(*this, node); |
|
77 } |
|
78 |
|
79 OutEdgeIt(const Graph& _graph, const Edge& edge) |
|
80 : Edge(edge), graph(&_graph) {} |
|
81 |
|
82 OutEdgeIt& operator++() { |
|
83 graph->nextOut(*this); |
|
84 return *this; |
|
85 } |
|
86 |
|
87 }; |
|
88 |
|
89 |
|
90 class InEdgeIt : public Edge { |
|
91 const Graph* graph; |
|
92 public: |
|
93 |
|
94 InEdgeIt() { } |
|
95 |
|
96 InEdgeIt(Invalid i) : Edge(i) { } |
|
97 |
|
98 InEdgeIt(const Graph& _graph, const Node& node) |
|
99 : graph(&_graph) { |
|
100 _graph.firstIn(*this, node); |
|
101 } |
|
102 |
|
103 InEdgeIt(const Graph& _graph, const Edge& edge) : |
|
104 Edge(edge), graph(&_graph) {} |
|
105 |
|
106 InEdgeIt& operator++() { |
|
107 graph->nextIn(*this); |
|
108 return *this; |
|
109 } |
|
110 |
|
111 }; |
|
112 |
|
113 /// Base node of the iterator |
|
114 /// |
|
115 /// Returns the base node (ie. the source in this case) of the iterator |
|
116 /// |
|
117 /// \todo Document in the concept! |
|
118 Node baseNode(const OutEdgeIt &e) const { |
|
119 return source(e); |
|
120 } |
|
121 /// Running node of the iterator |
|
122 /// |
|
123 /// Returns the running node (ie. the target in this case) of the |
|
124 /// iterator |
|
125 /// |
|
126 /// \todo Document in the concept! |
|
127 Node runningNode(const OutEdgeIt &e) const { |
|
128 return target(e); |
|
129 } |
|
130 |
|
131 /// Base node of the iterator |
|
132 /// |
|
133 /// Returns the base node (ie. the target in this case) of the iterator |
|
134 /// |
|
135 /// \todo Document in the concept! |
|
136 Node baseNode(const InEdgeIt &e) const { |
|
137 return target(e); |
|
138 } |
|
139 /// Running node of the iterator |
|
140 /// |
|
141 /// Returns the running node (ie. the source in this case) of the |
|
142 /// iterator |
|
143 /// |
|
144 /// \todo Document in the concept! |
|
145 Node runningNode(const InEdgeIt &e) const { |
|
146 return source(e); |
|
147 } |
|
148 |
|
149 using Parent::first; |
|
150 |
|
151 private: |
|
152 |
|
153 // /// \todo When (and if) we change the iterators concept to use operator*, |
|
154 // /// then the following shadowed methods will become superfluous. |
|
155 // /// But for now these are important safety measures. |
|
156 |
|
157 // void first(NodeIt &) const; |
|
158 // void first(EdgeIt &) const; |
|
159 // void first(OutEdgeIt &) const; |
|
160 // void first(InEdgeIt &) const; |
|
161 |
|
162 }; |
|
163 |
|
164 |
|
165 |
|
166 |
|
167 |
|
168 |
|
169 template <typename _Base> |
|
170 class IterableUndirGraphExtender : public IterableGraphExtender<_Base> { |
|
171 public: |
|
172 |
|
173 typedef IterableGraphExtender<_Base> Parent; |
|
174 typedef IterableUndirGraphExtender<_Base> Graph; |
|
175 typedef typename Parent::Node Node; |
|
176 |
|
177 typedef typename Parent::UndirEdge UndirEdge; |
|
178 |
|
179 class UndirEdgeIt : public Parent::UndirEdge { |
|
180 const Graph* graph; |
|
181 public: |
|
182 |
|
183 UndirEdgeIt() { } |
|
184 |
|
185 UndirEdgeIt(Invalid i) : UndirEdge(i) { } |
|
186 |
|
187 explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) { |
|
188 _graph.first(*static_cast<UndirEdge*>(this)); |
|
189 } |
|
190 |
|
191 UndirEdgeIt(const Graph& _graph, const UndirEdge& e) : |
|
192 UndirEdge(e), graph(&_graph) { } |
|
193 |
|
194 UndirEdgeIt& operator++() { |
|
195 graph->next(*this); |
|
196 return *this; |
|
197 } |
|
198 |
|
199 }; |
|
200 |
|
201 class IncEdgeIt : public Parent::UndirEdge { |
|
202 const Graph* graph; |
|
203 bool forward; |
|
204 friend class IterableUndirGraphExtender; |
|
205 template <typename G> |
|
206 friend class UndirGraphExtender; |
|
207 public: |
|
208 |
|
209 IncEdgeIt() { } |
|
210 |
|
211 IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { } |
|
212 |
|
213 IncEdgeIt(const Graph& _graph, const Node &n) |
|
214 : graph(&_graph) |
|
215 { |
|
216 _graph._dirFirstOut(*this, n); |
|
217 } |
|
218 |
|
219 IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n) |
|
220 : graph(&_graph), UndirEdge(ue) |
|
221 { |
|
222 forward = (_graph.source(ue) == n); |
|
223 } |
|
224 |
|
225 IncEdgeIt& operator++() { |
|
226 graph->_dirNextOut(*this); |
|
227 return *this; |
|
228 } |
|
229 }; |
|
230 |
|
231 using Parent::baseNode; |
|
232 using Parent::runningNode; |
|
233 |
|
234 /// Base node of the iterator |
|
235 /// |
|
236 /// Returns the base node of the iterator |
|
237 Node baseNode(const IncEdgeIt &e) const { |
|
238 return _dirSource(e); |
|
239 } |
|
240 /// Running node of the iterator |
|
241 /// |
|
242 /// Returns the running node of the iterator |
|
243 Node runningNode(const IncEdgeIt &e) const { |
|
244 return _dirTarget(e); |
|
245 } |
|
246 |
|
247 }; |
|
248 } |
|
249 |
|
250 #endif // LEMON_GRAPH_EXTENDER_H |
|