1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/bits/iterable_graph_extender.h Mon May 23 04:48:14 2005 +0000
1.3 @@ -0,0 +1,250 @@
1.4 +// -*- c++ -*-
1.5 +#ifndef LEMON_ITERABLE_GRAPH_EXTENDER_H
1.6 +#define LEMON_ITERABLE_GRAPH_EXTENDER_H
1.7 +
1.8 +#include <lemon/invalid.h>
1.9 +
1.10 +namespace lemon {
1.11 +
1.12 + template <typename _Base>
1.13 + class IterableGraphExtender : public _Base {
1.14 + public:
1.15 +
1.16 + typedef _Base Parent;
1.17 + typedef IterableGraphExtender<_Base> Graph;
1.18 +
1.19 + typedef typename Parent::Node Node;
1.20 + typedef typename Parent::Edge Edge;
1.21 +
1.22 +
1.23 + class NodeIt : public Node {
1.24 + const Graph* graph;
1.25 + public:
1.26 +
1.27 + NodeIt() {}
1.28 +
1.29 + NodeIt(Invalid i) : Node(i) { }
1.30 +
1.31 + explicit NodeIt(const Graph& _graph) : graph(&_graph) {
1.32 + _graph.first(*static_cast<Node*>(this));
1.33 + }
1.34 +
1.35 + NodeIt(const Graph& _graph, const Node& node)
1.36 + : Node(node), graph(&_graph) {}
1.37 +
1.38 + NodeIt& operator++() {
1.39 + graph->next(*this);
1.40 + return *this;
1.41 + }
1.42 +
1.43 + };
1.44 +
1.45 +
1.46 + class EdgeIt : public Edge {
1.47 + const Graph* graph;
1.48 + public:
1.49 +
1.50 + EdgeIt() { }
1.51 +
1.52 + EdgeIt(Invalid i) : Edge(i) { }
1.53 +
1.54 + explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
1.55 + _graph.first(*static_cast<Edge*>(this));
1.56 + }
1.57 +
1.58 + EdgeIt(const Graph& _graph, const Edge& e) :
1.59 + Edge(e), graph(&_graph) { }
1.60 +
1.61 + EdgeIt& operator++() {
1.62 + graph->next(*this);
1.63 + return *this;
1.64 + }
1.65 +
1.66 + };
1.67 +
1.68 +
1.69 + class OutEdgeIt : public Edge {
1.70 + const Graph* graph;
1.71 + public:
1.72 +
1.73 + OutEdgeIt() { }
1.74 +
1.75 + OutEdgeIt(Invalid i) : Edge(i) { }
1.76 +
1.77 + OutEdgeIt(const Graph& _graph, const Node& node)
1.78 + : graph(&_graph) {
1.79 + _graph.firstOut(*this, node);
1.80 + }
1.81 +
1.82 + OutEdgeIt(const Graph& _graph, const Edge& edge)
1.83 + : Edge(edge), graph(&_graph) {}
1.84 +
1.85 + OutEdgeIt& operator++() {
1.86 + graph->nextOut(*this);
1.87 + return *this;
1.88 + }
1.89 +
1.90 + };
1.91 +
1.92 +
1.93 + class InEdgeIt : public Edge {
1.94 + const Graph* graph;
1.95 + public:
1.96 +
1.97 + InEdgeIt() { }
1.98 +
1.99 + InEdgeIt(Invalid i) : Edge(i) { }
1.100 +
1.101 + InEdgeIt(const Graph& _graph, const Node& node)
1.102 + : graph(&_graph) {
1.103 + _graph.firstIn(*this, node);
1.104 + }
1.105 +
1.106 + InEdgeIt(const Graph& _graph, const Edge& edge) :
1.107 + Edge(edge), graph(&_graph) {}
1.108 +
1.109 + InEdgeIt& operator++() {
1.110 + graph->nextIn(*this);
1.111 + return *this;
1.112 + }
1.113 +
1.114 + };
1.115 +
1.116 + /// Base node of the iterator
1.117 + ///
1.118 + /// Returns the base node (ie. the source in this case) of the iterator
1.119 + ///
1.120 + /// \todo Document in the concept!
1.121 + Node baseNode(const OutEdgeIt &e) const {
1.122 + return source(e);
1.123 + }
1.124 + /// Running node of the iterator
1.125 + ///
1.126 + /// Returns the running node (ie. the target in this case) of the
1.127 + /// iterator
1.128 + ///
1.129 + /// \todo Document in the concept!
1.130 + Node runningNode(const OutEdgeIt &e) const {
1.131 + return target(e);
1.132 + }
1.133 +
1.134 + /// Base node of the iterator
1.135 + ///
1.136 + /// Returns the base node (ie. the target in this case) of the iterator
1.137 + ///
1.138 + /// \todo Document in the concept!
1.139 + Node baseNode(const InEdgeIt &e) const {
1.140 + return target(e);
1.141 + }
1.142 + /// Running node of the iterator
1.143 + ///
1.144 + /// Returns the running node (ie. the source in this case) of the
1.145 + /// iterator
1.146 + ///
1.147 + /// \todo Document in the concept!
1.148 + Node runningNode(const InEdgeIt &e) const {
1.149 + return source(e);
1.150 + }
1.151 +
1.152 + using Parent::first;
1.153 +
1.154 + private:
1.155 +
1.156 + // /// \todo When (and if) we change the iterators concept to use operator*,
1.157 + // /// then the following shadowed methods will become superfluous.
1.158 + // /// But for now these are important safety measures.
1.159 +
1.160 + // void first(NodeIt &) const;
1.161 + // void first(EdgeIt &) const;
1.162 + // void first(OutEdgeIt &) const;
1.163 + // void first(InEdgeIt &) const;
1.164 +
1.165 + };
1.166 +
1.167 +
1.168 +
1.169 +
1.170 +
1.171 +
1.172 + template <typename _Base>
1.173 + class IterableUndirGraphExtender : public IterableGraphExtender<_Base> {
1.174 + public:
1.175 +
1.176 + typedef IterableGraphExtender<_Base> Parent;
1.177 + typedef IterableUndirGraphExtender<_Base> Graph;
1.178 + typedef typename Parent::Node Node;
1.179 +
1.180 + typedef typename Parent::UndirEdge UndirEdge;
1.181 +
1.182 + class UndirEdgeIt : public Parent::UndirEdge {
1.183 + const Graph* graph;
1.184 + public:
1.185 +
1.186 + UndirEdgeIt() { }
1.187 +
1.188 + UndirEdgeIt(Invalid i) : UndirEdge(i) { }
1.189 +
1.190 + explicit UndirEdgeIt(const Graph& _graph) : graph(&_graph) {
1.191 + _graph.first(*static_cast<UndirEdge*>(this));
1.192 + }
1.193 +
1.194 + UndirEdgeIt(const Graph& _graph, const UndirEdge& e) :
1.195 + UndirEdge(e), graph(&_graph) { }
1.196 +
1.197 + UndirEdgeIt& operator++() {
1.198 + graph->next(*this);
1.199 + return *this;
1.200 + }
1.201 +
1.202 + };
1.203 +
1.204 + class IncEdgeIt : public Parent::UndirEdge {
1.205 + const Graph* graph;
1.206 + bool forward;
1.207 + friend class IterableUndirGraphExtender;
1.208 + template <typename G>
1.209 + friend class UndirGraphExtender;
1.210 + public:
1.211 +
1.212 + IncEdgeIt() { }
1.213 +
1.214 + IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
1.215 +
1.216 + IncEdgeIt(const Graph& _graph, const Node &n)
1.217 + : graph(&_graph)
1.218 + {
1.219 + _graph._dirFirstOut(*this, n);
1.220 + }
1.221 +
1.222 + IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n)
1.223 + : graph(&_graph), UndirEdge(ue)
1.224 + {
1.225 + forward = (_graph.source(ue) == n);
1.226 + }
1.227 +
1.228 + IncEdgeIt& operator++() {
1.229 + graph->_dirNextOut(*this);
1.230 + return *this;
1.231 + }
1.232 + };
1.233 +
1.234 + using Parent::baseNode;
1.235 + using Parent::runningNode;
1.236 +
1.237 + /// Base node of the iterator
1.238 + ///
1.239 + /// Returns the base node of the iterator
1.240 + Node baseNode(const IncEdgeIt &e) const {
1.241 + return _dirSource(e);
1.242 + }
1.243 + /// Running node of the iterator
1.244 + ///
1.245 + /// Returns the running node of the iterator
1.246 + Node runningNode(const IncEdgeIt &e) const {
1.247 + return _dirTarget(e);
1.248 + }
1.249 +
1.250 + };
1.251 +}
1.252 +
1.253 +#endif // LEMON_GRAPH_EXTENDER_H