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