1.1 --- a/lemon/core.h Mon Jan 12 23:11:39 2009 +0100
1.2 +++ b/lemon/core.h Thu Nov 05 15:48:01 2009 +0100
1.3 @@ -22,10 +22,21 @@
1.4 #include <vector>
1.5 #include <algorithm>
1.6
1.7 +#include <lemon/config.h>
1.8 #include <lemon/bits/enable_if.h>
1.9 #include <lemon/bits/traits.h>
1.10 #include <lemon/assert.h>
1.11
1.12 +// Disable the following warnings when compiling with MSVC:
1.13 +// C4250: 'class1' : inherits 'class2::member' via dominance
1.14 +// C4355: 'this' : used in base member initializer list
1.15 +// C4503: 'function' : decorated name length exceeded, name was truncated
1.16 +// C4800: 'type' : forcing value to bool 'true' or 'false' (performance warning)
1.17 +// C4996: 'function': was declared deprecated
1.18 +#ifdef _MSC_VER
1.19 +#pragma warning( disable : 4250 4355 4503 4800 4996 )
1.20 +#endif
1.21 +
1.22 ///\file
1.23 ///\brief LEMON core utilities.
1.24 ///
1.25 @@ -1033,28 +1044,27 @@
1.26 ///
1.27 ///\sa findArc()
1.28 ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp
1.29 - template <typename _Graph>
1.30 - class ConArcIt : public _Graph::Arc {
1.31 + template <typename GR>
1.32 + class ConArcIt : public GR::Arc {
1.33 + typedef typename GR::Arc Parent;
1.34 +
1.35 public:
1.36
1.37 - typedef _Graph Graph;
1.38 - typedef typename Graph::Arc Parent;
1.39 -
1.40 - typedef typename Graph::Arc Arc;
1.41 - typedef typename Graph::Node Node;
1.42 + typedef typename GR::Arc Arc;
1.43 + typedef typename GR::Node Node;
1.44
1.45 /// \brief Constructor.
1.46 ///
1.47 /// Construct a new ConArcIt iterating on the arcs that
1.48 /// connects nodes \c u and \c v.
1.49 - ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {
1.50 + ConArcIt(const GR& g, Node u, Node v) : _graph(g) {
1.51 Parent::operator=(findArc(_graph, u, v));
1.52 }
1.53
1.54 /// \brief Constructor.
1.55 ///
1.56 /// Construct a new ConArcIt that continues the iterating from arc \c a.
1.57 - ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}
1.58 + ConArcIt(const GR& g, Arc a) : Parent(a), _graph(g) {}
1.59
1.60 /// \brief Increment operator.
1.61 ///
1.62 @@ -1065,7 +1075,7 @@
1.63 return *this;
1.64 }
1.65 private:
1.66 - const Graph& _graph;
1.67 + const GR& _graph;
1.68 };
1.69
1.70 namespace _core_bits {
1.71 @@ -1156,28 +1166,27 @@
1.72 ///\endcode
1.73 ///
1.74 ///\sa findEdge()
1.75 - template <typename _Graph>
1.76 - class ConEdgeIt : public _Graph::Edge {
1.77 + template <typename GR>
1.78 + class ConEdgeIt : public GR::Edge {
1.79 + typedef typename GR::Edge Parent;
1.80 +
1.81 public:
1.82
1.83 - typedef _Graph Graph;
1.84 - typedef typename Graph::Edge Parent;
1.85 -
1.86 - typedef typename Graph::Edge Edge;
1.87 - typedef typename Graph::Node Node;
1.88 + typedef typename GR::Edge Edge;
1.89 + typedef typename GR::Node Node;
1.90
1.91 /// \brief Constructor.
1.92 ///
1.93 /// Construct a new ConEdgeIt iterating on the edges that
1.94 /// connects nodes \c u and \c v.
1.95 - ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
1.96 + ConEdgeIt(const GR& g, Node u, Node v) : _graph(g), _u(u), _v(v) {
1.97 Parent::operator=(findEdge(_graph, _u, _v));
1.98 }
1.99
1.100 /// \brief Constructor.
1.101 ///
1.102 /// Construct a new ConEdgeIt that continues iterating from edge \c e.
1.103 - ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}
1.104 + ConEdgeIt(const GR& g, Edge e) : Parent(e), _graph(g) {}
1.105
1.106 /// \brief Increment operator.
1.107 ///
1.108 @@ -1187,7 +1196,7 @@
1.109 return *this;
1.110 }
1.111 private:
1.112 - const Graph& _graph;
1.113 + const GR& _graph;
1.114 Node _u, _v;
1.115 };
1.116
1.117 @@ -1210,29 +1219,32 @@
1.118 ///optimal time bound in a constant factor for any distribution of
1.119 ///queries.
1.120 ///
1.121 - ///\tparam G The type of the underlying digraph.
1.122 + ///\tparam GR The type of the underlying digraph.
1.123 ///
1.124 ///\sa ArcLookUp
1.125 ///\sa AllArcLookUp
1.126 - template<class G>
1.127 + template <typename GR>
1.128 class DynArcLookUp
1.129 - : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase
1.130 + : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase
1.131 {
1.132 - public:
1.133 - typedef typename ItemSetTraits<G, typename G::Arc>
1.134 + typedef typename ItemSetTraits<GR, typename GR::Arc>
1.135 ::ItemNotifier::ObserverBase Parent;
1.136
1.137 - TEMPLATE_DIGRAPH_TYPEDEFS(G);
1.138 - typedef G Digraph;
1.139 + TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1.140 +
1.141 + public:
1.142 +
1.143 + /// The Digraph type
1.144 + typedef GR Digraph;
1.145
1.146 protected:
1.147
1.148 - class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {
1.149 + class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type {
1.150 + typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent;
1.151 +
1.152 public:
1.153
1.154 - typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;
1.155 -
1.156 - AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}
1.157 + AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {}
1.158
1.159 virtual void add(const Node& node) {
1.160 Parent::add(node);
1.161 @@ -1256,12 +1268,6 @@
1.162 }
1.163 };
1.164
1.165 - const Digraph &_g;
1.166 - AutoNodeMap _head;
1.167 - typename Digraph::template ArcMap<Arc> _parent;
1.168 - typename Digraph::template ArcMap<Arc> _left;
1.169 - typename Digraph::template ArcMap<Arc> _right;
1.170 -
1.171 class ArcLess {
1.172 const Digraph &g;
1.173 public:
1.174 @@ -1272,6 +1278,14 @@
1.175 }
1.176 };
1.177
1.178 + protected:
1.179 +
1.180 + const Digraph &_g;
1.181 + AutoNodeMap _head;
1.182 + typename Digraph::template ArcMap<Arc> _parent;
1.183 + typename Digraph::template ArcMap<Arc> _left;
1.184 + typename Digraph::template ArcMap<Arc> _right;
1.185 +
1.186 public:
1.187
1.188 ///Constructor
1.189 @@ -1314,27 +1328,27 @@
1.190
1.191 virtual void clear() {
1.192 for(NodeIt n(_g);n!=INVALID;++n) {
1.193 - _head.set(n, INVALID);
1.194 + _head[n] = INVALID;
1.195 }
1.196 }
1.197
1.198 void insert(Arc arc) {
1.199 Node s = _g.source(arc);
1.200 Node t = _g.target(arc);
1.201 - _left.set(arc, INVALID);
1.202 - _right.set(arc, INVALID);
1.203 + _left[arc] = INVALID;
1.204 + _right[arc] = INVALID;
1.205
1.206 Arc e = _head[s];
1.207 if (e == INVALID) {
1.208 - _head.set(s, arc);
1.209 - _parent.set(arc, INVALID);
1.210 + _head[s] = arc;
1.211 + _parent[arc] = INVALID;
1.212 return;
1.213 }
1.214 while (true) {
1.215 if (t < _g.target(e)) {
1.216 if (_left[e] == INVALID) {
1.217 - _left.set(e, arc);
1.218 - _parent.set(arc, e);
1.219 + _left[e] = arc;
1.220 + _parent[arc] = e;
1.221 splay(arc);
1.222 return;
1.223 } else {
1.224 @@ -1342,8 +1356,8 @@
1.225 }
1.226 } else {
1.227 if (_right[e] == INVALID) {
1.228 - _right.set(e, arc);
1.229 - _parent.set(arc, e);
1.230 + _right[e] = arc;
1.231 + _parent[arc] = e;
1.232 splay(arc);
1.233 return;
1.234 } else {
1.235 @@ -1356,27 +1370,27 @@
1.236 void remove(Arc arc) {
1.237 if (_left[arc] == INVALID) {
1.238 if (_right[arc] != INVALID) {
1.239 - _parent.set(_right[arc], _parent[arc]);
1.240 + _parent[_right[arc]] = _parent[arc];
1.241 }
1.242 if (_parent[arc] != INVALID) {
1.243 if (_left[_parent[arc]] == arc) {
1.244 - _left.set(_parent[arc], _right[arc]);
1.245 + _left[_parent[arc]] = _right[arc];
1.246 } else {
1.247 - _right.set(_parent[arc], _right[arc]);
1.248 + _right[_parent[arc]] = _right[arc];
1.249 }
1.250 } else {
1.251 - _head.set(_g.source(arc), _right[arc]);
1.252 + _head[_g.source(arc)] = _right[arc];
1.253 }
1.254 } else if (_right[arc] == INVALID) {
1.255 - _parent.set(_left[arc], _parent[arc]);
1.256 + _parent[_left[arc]] = _parent[arc];
1.257 if (_parent[arc] != INVALID) {
1.258 if (_left[_parent[arc]] == arc) {
1.259 - _left.set(_parent[arc], _left[arc]);
1.260 + _left[_parent[arc]] = _left[arc];
1.261 } else {
1.262 - _right.set(_parent[arc], _left[arc]);
1.263 + _right[_parent[arc]] = _left[arc];
1.264 }
1.265 } else {
1.266 - _head.set(_g.source(arc), _left[arc]);
1.267 + _head[_g.source(arc)] = _left[arc];
1.268 }
1.269 } else {
1.270 Arc e = _left[arc];
1.271 @@ -1386,38 +1400,38 @@
1.272 e = _right[e];
1.273 }
1.274 Arc s = _parent[e];
1.275 - _right.set(_parent[e], _left[e]);
1.276 + _right[_parent[e]] = _left[e];
1.277 if (_left[e] != INVALID) {
1.278 - _parent.set(_left[e], _parent[e]);
1.279 + _parent[_left[e]] = _parent[e];
1.280 }
1.281
1.282 - _left.set(e, _left[arc]);
1.283 - _parent.set(_left[arc], e);
1.284 - _right.set(e, _right[arc]);
1.285 - _parent.set(_right[arc], e);
1.286 + _left[e] = _left[arc];
1.287 + _parent[_left[arc]] = e;
1.288 + _right[e] = _right[arc];
1.289 + _parent[_right[arc]] = e;
1.290
1.291 - _parent.set(e, _parent[arc]);
1.292 + _parent[e] = _parent[arc];
1.293 if (_parent[arc] != INVALID) {
1.294 if (_left[_parent[arc]] == arc) {
1.295 - _left.set(_parent[arc], e);
1.296 + _left[_parent[arc]] = e;
1.297 } else {
1.298 - _right.set(_parent[arc], e);
1.299 + _right[_parent[arc]] = e;
1.300 }
1.301 }
1.302 splay(s);
1.303 } else {
1.304 - _right.set(e, _right[arc]);
1.305 - _parent.set(_right[arc], e);
1.306 - _parent.set(e, _parent[arc]);
1.307 + _right[e] = _right[arc];
1.308 + _parent[_right[arc]] = e;
1.309 + _parent[e] = _parent[arc];
1.310
1.311 if (_parent[arc] != INVALID) {
1.312 if (_left[_parent[arc]] == arc) {
1.313 - _left.set(_parent[arc], e);
1.314 + _left[_parent[arc]] = e;
1.315 } else {
1.316 - _right.set(_parent[arc], e);
1.317 + _right[_parent[arc]] = e;
1.318 }
1.319 } else {
1.320 - _head.set(_g.source(arc), e);
1.321 + _head[_g.source(arc)] = e;
1.322 }
1.323 }
1.324 }
1.325 @@ -1429,17 +1443,17 @@
1.326 Arc me=v[m];
1.327 if (a < m) {
1.328 Arc left = refreshRec(v,a,m-1);
1.329 - _left.set(me, left);
1.330 - _parent.set(left, me);
1.331 + _left[me] = left;
1.332 + _parent[left] = me;
1.333 } else {
1.334 - _left.set(me, INVALID);
1.335 + _left[me] = INVALID;
1.336 }
1.337 if (m < b) {
1.338 Arc right = refreshRec(v,m+1,b);
1.339 - _right.set(me, right);
1.340 - _parent.set(right, me);
1.341 + _right[me] = right;
1.342 + _parent[right] = me;
1.343 } else {
1.344 - _right.set(me, INVALID);
1.345 + _right[me] = INVALID;
1.346 }
1.347 return me;
1.348 }
1.349 @@ -1451,46 +1465,46 @@
1.350 if (!v.empty()) {
1.351 std::sort(v.begin(),v.end(),ArcLess(_g));
1.352 Arc head = refreshRec(v,0,v.size()-1);
1.353 - _head.set(n, head);
1.354 - _parent.set(head, INVALID);
1.355 + _head[n] = head;
1.356 + _parent[head] = INVALID;
1.357 }
1.358 - else _head.set(n, INVALID);
1.359 + else _head[n] = INVALID;
1.360 }
1.361 }
1.362
1.363 void zig(Arc v) {
1.364 Arc w = _parent[v];
1.365 - _parent.set(v, _parent[w]);
1.366 - _parent.set(w, v);
1.367 - _left.set(w, _right[v]);
1.368 - _right.set(v, w);
1.369 + _parent[v] = _parent[w];
1.370 + _parent[w] = v;
1.371 + _left[w] = _right[v];
1.372 + _right[v] = w;
1.373 if (_parent[v] != INVALID) {
1.374 if (_right[_parent[v]] == w) {
1.375 - _right.set(_parent[v], v);
1.376 + _right[_parent[v]] = v;
1.377 } else {
1.378 - _left.set(_parent[v], v);
1.379 + _left[_parent[v]] = v;
1.380 }
1.381 }
1.382 if (_left[w] != INVALID){
1.383 - _parent.set(_left[w], w);
1.384 + _parent[_left[w]] = w;
1.385 }
1.386 }
1.387
1.388 void zag(Arc v) {
1.389 Arc w = _parent[v];
1.390 - _parent.set(v, _parent[w]);
1.391 - _parent.set(w, v);
1.392 - _right.set(w, _left[v]);
1.393 - _left.set(v, w);
1.394 + _parent[v] = _parent[w];
1.395 + _parent[w] = v;
1.396 + _right[w] = _left[v];
1.397 + _left[v] = w;
1.398 if (_parent[v] != INVALID){
1.399 if (_left[_parent[v]] == w) {
1.400 - _left.set(_parent[v], v);
1.401 + _left[_parent[v]] = v;
1.402 } else {
1.403 - _right.set(_parent[v], v);
1.404 + _right[_parent[v]] = v;
1.405 }
1.406 }
1.407 if (_right[w] != INVALID){
1.408 - _parent.set(_right[w], w);
1.409 + _parent[_right[w]] = w;
1.410 }
1.411 }
1.412
1.413 @@ -1622,16 +1636,19 @@
1.414 ///digraph changes. This is a time consuming (superlinearly proportional
1.415 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
1.416 ///
1.417 - ///\tparam G The type of the underlying digraph.
1.418 + ///\tparam GR The type of the underlying digraph.
1.419 ///
1.420 ///\sa DynArcLookUp
1.421 ///\sa AllArcLookUp
1.422 - template<class G>
1.423 + template<class GR>
1.424 class ArcLookUp
1.425 {
1.426 + TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1.427 +
1.428 public:
1.429 - TEMPLATE_DIGRAPH_TYPEDEFS(G);
1.430 - typedef G Digraph;
1.431 +
1.432 + /// The Digraph type
1.433 + typedef GR Digraph;
1.434
1.435 protected:
1.436 const Digraph &_g;
1.437 @@ -1732,22 +1749,21 @@
1.438 ///digraph changes. This is a time consuming (superlinearly proportional
1.439 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs).
1.440 ///
1.441 - ///\tparam G The type of the underlying digraph.
1.442 + ///\tparam GR The type of the underlying digraph.
1.443 ///
1.444 ///\sa DynArcLookUp
1.445 ///\sa ArcLookUp
1.446 - template<class G>
1.447 - class AllArcLookUp : public ArcLookUp<G>
1.448 + template<class GR>
1.449 + class AllArcLookUp : public ArcLookUp<GR>
1.450 {
1.451 - using ArcLookUp<G>::_g;
1.452 - using ArcLookUp<G>::_right;
1.453 - using ArcLookUp<G>::_left;
1.454 - using ArcLookUp<G>::_head;
1.455 + using ArcLookUp<GR>::_g;
1.456 + using ArcLookUp<GR>::_right;
1.457 + using ArcLookUp<GR>::_left;
1.458 + using ArcLookUp<GR>::_head;
1.459
1.460 - TEMPLATE_DIGRAPH_TYPEDEFS(G);
1.461 - typedef G Digraph;
1.462 + TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1.463
1.464 - typename Digraph::template ArcMap<Arc> _next;
1.465 + typename GR::template ArcMap<Arc> _next;
1.466
1.467 Arc refreshNext(Arc head,Arc next=INVALID)
1.468 {
1.469 @@ -1766,13 +1782,17 @@
1.470 }
1.471
1.472 public:
1.473 +
1.474 + /// The Digraph type
1.475 + typedef GR Digraph;
1.476 +
1.477 ///Constructor
1.478
1.479 ///Constructor.
1.480 ///
1.481 ///It builds up the search database, which remains valid until the digraph
1.482 ///changes.
1.483 - AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}
1.484 + AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();}
1.485
1.486 ///Refresh the data structure at a node.
1.487
1.488 @@ -1782,7 +1802,7 @@
1.489 ///the number of the outgoing arcs of \c n.
1.490 void refresh(Node n)
1.491 {
1.492 - ArcLookUp<G>::refresh(n);
1.493 + ArcLookUp<GR>::refresh(n);
1.494 refreshNext(_head[n]);
1.495 }
1.496
1.497 @@ -1829,7 +1849,7 @@
1.498 #ifdef DOXYGEN
1.499 Arc operator()(Node s, Node t, Arc prev=INVALID) const {}
1.500 #else
1.501 - using ArcLookUp<G>::operator() ;
1.502 + using ArcLookUp<GR>::operator() ;
1.503 Arc operator()(Node s, Node t, Arc prev) const
1.504 {
1.505 return prev==INVALID?(*this)(s,t):_next[prev];