1.1 --- a/lemon/elevator.h Mon Jan 12 23:11:39 2009 +0100
1.2 +++ b/lemon/elevator.h Thu Nov 05 15:48:01 2009 +0100
1.3 @@ -27,6 +27,7 @@
1.4 ///for labeling items in push-relabel type algorithms.
1.5 ///
1.6
1.7 +#include <lemon/core.h>
1.8 #include <lemon/bits/traits.h>
1.9
1.10 namespace lemon {
1.11 @@ -45,10 +46,10 @@
1.12 ///
1.13 ///\sa LinkedElevator
1.14 ///
1.15 - ///\param Graph Type of the underlying graph.
1.16 - ///\param Item Type of the items the data is assigned to (Graph::Node,
1.17 - ///Graph::Arc, Graph::Edge).
1.18 - template<class Graph, class Item>
1.19 + ///\param GR Type of the underlying graph.
1.20 + ///\param Item Type of the items the data is assigned to (\c GR::Node,
1.21 + ///\c GR::Arc or \c GR::Edge).
1.22 + template<class GR, class Item>
1.23 class Elevator
1.24 {
1.25 public:
1.26 @@ -59,10 +60,10 @@
1.27 private:
1.28
1.29 typedef Item *Vit;
1.30 - typedef typename ItemSetTraits<Graph,Item>::template Map<Vit>::Type VitMap;
1.31 - typedef typename ItemSetTraits<Graph,Item>::template Map<int>::Type IntMap;
1.32 + typedef typename ItemSetTraits<GR,Item>::template Map<Vit>::Type VitMap;
1.33 + typedef typename ItemSetTraits<GR,Item>::template Map<int>::Type IntMap;
1.34
1.35 - const Graph &_g;
1.36 + const GR &_g;
1.37 int _max_level;
1.38 int _item_num;
1.39 VitMap _where;
1.40 @@ -75,7 +76,7 @@
1.41
1.42 void copy(Item i, Vit p)
1.43 {
1.44 - _where.set(*p=i,p);
1.45 + _where[*p=i] = p;
1.46 }
1.47 void copy(Vit s, Vit p)
1.48 {
1.49 @@ -83,15 +84,15 @@
1.50 {
1.51 Item i=*s;
1.52 *p=i;
1.53 - _where.set(i,p);
1.54 + _where[i] = p;
1.55 }
1.56 }
1.57 void swap(Vit i, Vit j)
1.58 {
1.59 Item ti=*i;
1.60 Vit ct = _where[ti];
1.61 - _where.set(ti,_where[*i=*j]);
1.62 - _where.set(*j,ct);
1.63 + _where[ti] = _where[*i=*j];
1.64 + _where[*j] = ct;
1.65 *j=ti;
1.66 }
1.67
1.68 @@ -104,7 +105,7 @@
1.69 ///\param graph The underlying graph.
1.70 ///\param max_level The maximum allowed level.
1.71 ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
1.72 - Elevator(const Graph &graph,int max_level) :
1.73 + Elevator(const GR &graph,int max_level) :
1.74 _g(graph),
1.75 _max_level(max_level),
1.76 _item_num(_max_level),
1.77 @@ -121,9 +122,9 @@
1.78 ///\param graph The underlying graph.
1.79 ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
1.80 ///where \c max_level is equal to the number of labeled items in the graph.
1.81 - Elevator(const Graph &graph) :
1.82 + Elevator(const GR &graph) :
1.83 _g(graph),
1.84 - _max_level(countItems<Graph, Item>(graph)),
1.85 + _max_level(countItems<GR, Item>(graph)),
1.86 _item_num(_max_level),
1.87 _where(graph),
1.88 _level(graph,0),
1.89 @@ -225,7 +226,7 @@
1.90 void liftHighestActive()
1.91 {
1.92 Item it = *_last_active[_highest_active];
1.93 - _level.set(it,_level[it]+1);
1.94 + ++_level[it];
1.95 swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
1.96 --_first[++_highest_active];
1.97 }
1.98 @@ -248,7 +249,7 @@
1.99 --_last_active[l];
1.100 }
1.101 copy(li,_first[new_level]);
1.102 - _level.set(li,new_level);
1.103 + _level[li] = new_level;
1.104 _highest_active=new_level;
1.105 }
1.106
1.107 @@ -268,7 +269,7 @@
1.108 }
1.109 copy(li,_first[_max_level]);
1.110 --_last_active[_max_level];
1.111 - _level.set(li,_max_level);
1.112 + _level[li] = _max_level;
1.113
1.114 while(_highest_active>=0 &&
1.115 _last_active[_highest_active]<_first[_highest_active])
1.116 @@ -298,7 +299,7 @@
1.117 Item liftActiveOn(int level)
1.118 {
1.119 Item it =*_last_active[level];
1.120 - _level.set(it,_level[it]+1);
1.121 + ++_level[it];
1.122 swap(_last_active[level]--, --_first[level+1]);
1.123 if (level+1>_highest_active) ++_highest_active;
1.124 }
1.125 @@ -318,7 +319,7 @@
1.126 copy(--_first[l+1], _last_active[l]--);
1.127 }
1.128 copy(ai,_first[new_level]);
1.129 - _level.set(ai,new_level);
1.130 + _level[ai] = new_level;
1.131 if (new_level>_highest_active) _highest_active=new_level;
1.132 }
1.133
1.134 @@ -338,7 +339,7 @@
1.135 }
1.136 copy(ai,_first[_max_level]);
1.137 --_last_active[_max_level];
1.138 - _level.set(ai,_max_level);
1.139 + _level[ai] = _max_level;
1.140
1.141 if (_highest_active==level) {
1.142 while(_highest_active>=0 &&
1.143 @@ -369,7 +370,7 @@
1.144 copy(--_first[l+1],_last_active[l]--);
1.145 }
1.146 copy(i,_first[new_level]);
1.147 - _level.set(i,new_level);
1.148 + _level[i] = new_level;
1.149 if(new_level>_highest_active) _highest_active=new_level;
1.150 }
1.151
1.152 @@ -381,7 +382,7 @@
1.153 ///only if you really know what it is for.
1.154 ///\pre The item is on the top level.
1.155 void dirtyTopButOne(Item i) {
1.156 - _level.set(i,_max_level - 1);
1.157 + _level[i] = _max_level - 1;
1.158 }
1.159
1.160 ///Lift all items on and above the given level to the top level.
1.161 @@ -393,7 +394,7 @@
1.162 const Vit f=_first[l];
1.163 const Vit tl=_first[_max_level];
1.164 for(Vit i=f;i!=tl;++i)
1.165 - _level.set(*i,_max_level);
1.166 + _level[*i] = _max_level;
1.167 for(int i=l;i<=_max_level;i++)
1.168 {
1.169 _first[i]=f;
1.170 @@ -429,11 +430,11 @@
1.171 _first[0]=&_items[0];
1.172 _last_active[0]=&_items[0]-1;
1.173 Vit n=&_items[0];
1.174 - for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
1.175 + for(typename ItemSetTraits<GR,Item>::ItemIt i(_g);i!=INVALID;++i)
1.176 {
1.177 *n=i;
1.178 - _where.set(i,n);
1.179 - _level.set(i,_max_level);
1.180 + _where[i] = n;
1.181 + _level[i] = _max_level;
1.182 ++n;
1.183 }
1.184 }
1.185 @@ -442,7 +443,7 @@
1.186 void initAddItem(Item i)
1.187 {
1.188 swap(_where[i],_init_num);
1.189 - _level.set(i,_init_lev);
1.190 + _level[i] = _init_lev;
1.191 ++_init_num;
1.192 }
1.193
1.194 @@ -488,10 +489,10 @@
1.195 ///
1.196 ///\sa Elevator
1.197 ///
1.198 - ///\param Graph Type of the underlying graph.
1.199 - ///\param Item Type of the items the data is assigned to (Graph::Node,
1.200 - ///Graph::Arc, Graph::Edge).
1.201 - template <class Graph, class Item>
1.202 + ///\param GR Type of the underlying graph.
1.203 + ///\param Item Type of the items the data is assigned to (\c GR::Node,
1.204 + ///\c GR::Arc or \c GR::Edge).
1.205 + template <class GR, class Item>
1.206 class LinkedElevator {
1.207 public:
1.208
1.209 @@ -500,14 +501,14 @@
1.210
1.211 private:
1.212
1.213 - typedef typename ItemSetTraits<Graph,Item>::
1.214 + typedef typename ItemSetTraits<GR,Item>::
1.215 template Map<Item>::Type ItemMap;
1.216 - typedef typename ItemSetTraits<Graph,Item>::
1.217 + typedef typename ItemSetTraits<GR,Item>::
1.218 template Map<int>::Type IntMap;
1.219 - typedef typename ItemSetTraits<Graph,Item>::
1.220 + typedef typename ItemSetTraits<GR,Item>::
1.221 template Map<bool>::Type BoolMap;
1.222
1.223 - const Graph &_graph;
1.224 + const GR &_graph;
1.225 int _max_level;
1.226 int _item_num;
1.227 std::vector<Item> _first, _last;
1.228 @@ -524,7 +525,7 @@
1.229 ///\param graph The underlying graph.
1.230 ///\param max_level The maximum allowed level.
1.231 ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
1.232 - LinkedElevator(const Graph& graph, int max_level)
1.233 + LinkedElevator(const GR& graph, int max_level)
1.234 : _graph(graph), _max_level(max_level), _item_num(_max_level),
1.235 _first(_max_level + 1), _last(_max_level + 1),
1.236 _prev(graph), _next(graph),
1.237 @@ -537,8 +538,8 @@
1.238 ///\param graph The underlying graph.
1.239 ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
1.240 ///where \c max_level is equal to the number of labeled items in the graph.
1.241 - LinkedElevator(const Graph& graph)
1.242 - : _graph(graph), _max_level(countItems<Graph, Item>(graph)),
1.243 + LinkedElevator(const GR& graph)
1.244 + : _graph(graph), _max_level(countItems<GR, Item>(graph)),
1.245 _item_num(_max_level),
1.246 _first(_max_level + 1), _last(_max_level + 1),
1.247 _prev(graph, INVALID), _next(graph, INVALID),
1.248 @@ -550,7 +551,7 @@
1.249 ///Activate item \c i.
1.250 ///\pre Item \c i shouldn't be active before.
1.251 void activate(Item i) {
1.252 - _active.set(i, true);
1.253 + _active[i] = true;
1.254
1.255 int level = _level[i];
1.256 if (level > _highest_active) {
1.257 @@ -559,16 +560,16 @@
1.258
1.259 if (_prev[i] == INVALID || _active[_prev[i]]) return;
1.260 //unlace
1.261 - _next.set(_prev[i], _next[i]);
1.262 + _next[_prev[i]] = _next[i];
1.263 if (_next[i] != INVALID) {
1.264 - _prev.set(_next[i], _prev[i]);
1.265 + _prev[_next[i]] = _prev[i];
1.266 } else {
1.267 _last[level] = _prev[i];
1.268 }
1.269 //lace
1.270 - _next.set(i, _first[level]);
1.271 - _prev.set(_first[level], i);
1.272 - _prev.set(i, INVALID);
1.273 + _next[i] = _first[level];
1.274 + _prev[_first[level]] = i;
1.275 + _prev[i] = INVALID;
1.276 _first[level] = i;
1.277
1.278 }
1.279 @@ -578,23 +579,23 @@
1.280 ///Deactivate item \c i.
1.281 ///\pre Item \c i must be active before.
1.282 void deactivate(Item i) {
1.283 - _active.set(i, false);
1.284 + _active[i] = false;
1.285 int level = _level[i];
1.286
1.287 if (_next[i] == INVALID || !_active[_next[i]])
1.288 goto find_highest_level;
1.289
1.290 //unlace
1.291 - _prev.set(_next[i], _prev[i]);
1.292 + _prev[_next[i]] = _prev[i];
1.293 if (_prev[i] != INVALID) {
1.294 - _next.set(_prev[i], _next[i]);
1.295 + _next[_prev[i]] = _next[i];
1.296 } else {
1.297 _first[_level[i]] = _next[i];
1.298 }
1.299 //lace
1.300 - _prev.set(i, _last[level]);
1.301 - _next.set(_last[level], i);
1.302 - _next.set(i, INVALID);
1.303 + _prev[i] = _last[level];
1.304 + _next[_last[level]] = i;
1.305 + _next[i] = INVALID;
1.306 _last[level] = i;
1.307
1.308 find_highest_level:
1.309 @@ -684,21 +685,21 @@
1.310 void liftHighestActive() {
1.311 Item i = _first[_highest_active];
1.312 if (_next[i] != INVALID) {
1.313 - _prev.set(_next[i], INVALID);
1.314 + _prev[_next[i]] = INVALID;
1.315 _first[_highest_active] = _next[i];
1.316 } else {
1.317 _first[_highest_active] = INVALID;
1.318 _last[_highest_active] = INVALID;
1.319 }
1.320 - _level.set(i, ++_highest_active);
1.321 + _level[i] = ++_highest_active;
1.322 if (_first[_highest_active] == INVALID) {
1.323 _first[_highest_active] = i;
1.324 _last[_highest_active] = i;
1.325 - _prev.set(i, INVALID);
1.326 - _next.set(i, INVALID);
1.327 + _prev[i] = INVALID;
1.328 + _next[i] = INVALID;
1.329 } else {
1.330 - _prev.set(_first[_highest_active], i);
1.331 - _next.set(i, _first[_highest_active]);
1.332 + _prev[_first[_highest_active]] = i;
1.333 + _next[i] = _first[_highest_active];
1.334 _first[_highest_active] = i;
1.335 }
1.336 }
1.337 @@ -713,20 +714,20 @@
1.338 void liftHighestActive(int new_level) {
1.339 Item i = _first[_highest_active];
1.340 if (_next[i] != INVALID) {
1.341 - _prev.set(_next[i], INVALID);
1.342 + _prev[_next[i]] = INVALID;
1.343 _first[_highest_active] = _next[i];
1.344 } else {
1.345 _first[_highest_active] = INVALID;
1.346 _last[_highest_active] = INVALID;
1.347 }
1.348 - _level.set(i, _highest_active = new_level);
1.349 + _level[i] = _highest_active = new_level;
1.350 if (_first[_highest_active] == INVALID) {
1.351 _first[_highest_active] = _last[_highest_active] = i;
1.352 - _prev.set(i, INVALID);
1.353 - _next.set(i, INVALID);
1.354 + _prev[i] = INVALID;
1.355 + _next[i] = INVALID;
1.356 } else {
1.357 - _prev.set(_first[_highest_active], i);
1.358 - _next.set(i, _first[_highest_active]);
1.359 + _prev[_first[_highest_active]] = i;
1.360 + _next[i] = _first[_highest_active];
1.361 _first[_highest_active] = i;
1.362 }
1.363 }
1.364 @@ -737,9 +738,9 @@
1.365 ///deactivate it.
1.366 void liftHighestActiveToTop() {
1.367 Item i = _first[_highest_active];
1.368 - _level.set(i, _max_level);
1.369 + _level[i] = _max_level;
1.370 if (_next[i] != INVALID) {
1.371 - _prev.set(_next[i], INVALID);
1.372 + _prev[_next[i]] = INVALID;
1.373 _first[_highest_active] = _next[i];
1.374 } else {
1.375 _first[_highest_active] = INVALID;
1.376 @@ -773,20 +774,20 @@
1.377 {
1.378 Item i = _first[l];
1.379 if (_next[i] != INVALID) {
1.380 - _prev.set(_next[i], INVALID);
1.381 + _prev[_next[i]] = INVALID;
1.382 _first[l] = _next[i];
1.383 } else {
1.384 _first[l] = INVALID;
1.385 _last[l] = INVALID;
1.386 }
1.387 - _level.set(i, ++l);
1.388 + _level[i] = ++l;
1.389 if (_first[l] == INVALID) {
1.390 _first[l] = _last[l] = i;
1.391 - _prev.set(i, INVALID);
1.392 - _next.set(i, INVALID);
1.393 + _prev[i] = INVALID;
1.394 + _next[i] = INVALID;
1.395 } else {
1.396 - _prev.set(_first[l], i);
1.397 - _next.set(i, _first[l]);
1.398 + _prev[_first[l]] = i;
1.399 + _next[i] = _first[l];
1.400 _first[l] = i;
1.401 }
1.402 if (_highest_active < l) {
1.403 @@ -802,20 +803,20 @@
1.404 {
1.405 Item i = _first[l];
1.406 if (_next[i] != INVALID) {
1.407 - _prev.set(_next[i], INVALID);
1.408 + _prev[_next[i]] = INVALID;
1.409 _first[l] = _next[i];
1.410 } else {
1.411 _first[l] = INVALID;
1.412 _last[l] = INVALID;
1.413 }
1.414 - _level.set(i, l = new_level);
1.415 + _level[i] = l = new_level;
1.416 if (_first[l] == INVALID) {
1.417 _first[l] = _last[l] = i;
1.418 - _prev.set(i, INVALID);
1.419 - _next.set(i, INVALID);
1.420 + _prev[i] = INVALID;
1.421 + _next[i] = INVALID;
1.422 } else {
1.423 - _prev.set(_first[l], i);
1.424 - _next.set(i, _first[l]);
1.425 + _prev[_first[l]] = i;
1.426 + _next[i] = _first[l];
1.427 _first[l] = i;
1.428 }
1.429 if (_highest_active < l) {
1.430 @@ -831,13 +832,13 @@
1.431 {
1.432 Item i = _first[l];
1.433 if (_next[i] != INVALID) {
1.434 - _prev.set(_next[i], INVALID);
1.435 + _prev[_next[i]] = INVALID;
1.436 _first[l] = _next[i];
1.437 } else {
1.438 _first[l] = INVALID;
1.439 _last[l] = INVALID;
1.440 }
1.441 - _level.set(i, _max_level);
1.442 + _level[i] = _max_level;
1.443 if (l == _highest_active) {
1.444 while (_highest_active >= 0 && activeFree(_highest_active))
1.445 --_highest_active;
1.446 @@ -855,23 +856,23 @@
1.447 ///
1.448 void lift(Item i, int new_level) {
1.449 if (_next[i] != INVALID) {
1.450 - _prev.set(_next[i], _prev[i]);
1.451 + _prev[_next[i]] = _prev[i];
1.452 } else {
1.453 _last[new_level] = _prev[i];
1.454 }
1.455 if (_prev[i] != INVALID) {
1.456 - _next.set(_prev[i], _next[i]);
1.457 + _next[_prev[i]] = _next[i];
1.458 } else {
1.459 _first[new_level] = _next[i];
1.460 }
1.461 - _level.set(i, new_level);
1.462 + _level[i] = new_level;
1.463 if (_first[new_level] == INVALID) {
1.464 _first[new_level] = _last[new_level] = i;
1.465 - _prev.set(i, INVALID);
1.466 - _next.set(i, INVALID);
1.467 + _prev[i] = INVALID;
1.468 + _next[i] = INVALID;
1.469 } else {
1.470 - _prev.set(_first[new_level], i);
1.471 - _next.set(i, _first[new_level]);
1.472 + _prev[_first[new_level]] = i;
1.473 + _next[i] = _first[new_level];
1.474 _first[new_level] = i;
1.475 }
1.476 if (_highest_active < new_level) {
1.477 @@ -887,7 +888,7 @@
1.478 ///only if you really know what it is for.
1.479 ///\pre The item is on the top level.
1.480 void dirtyTopButOne(Item i) {
1.481 - _level.set(i, _max_level - 1);
1.482 + _level[i] = _max_level - 1;
1.483 }
1.484
1.485 ///Lift all items on and above the given level to the top level.
1.486 @@ -898,7 +899,7 @@
1.487 for (int i = l + 1; _first[i] != INVALID; ++i) {
1.488 Item n = _first[i];
1.489 while (n != INVALID) {
1.490 - _level.set(n, _max_level);
1.491 + _level[n] = _max_level;
1.492 n = _next[n];
1.493 }
1.494 _first[i] = INVALID;
1.495 @@ -934,25 +935,25 @@
1.496 _first[i] = _last[i] = INVALID;
1.497 }
1.498 _init_level = 0;
1.499 - for(typename ItemSetTraits<Graph,Item>::ItemIt i(_graph);
1.500 + for(typename ItemSetTraits<GR,Item>::ItemIt i(_graph);
1.501 i != INVALID; ++i) {
1.502 - _level.set(i, _max_level);
1.503 - _active.set(i, false);
1.504 + _level[i] = _max_level;
1.505 + _active[i] = false;
1.506 }
1.507 }
1.508
1.509 ///Add an item to the current level.
1.510 void initAddItem(Item i) {
1.511 - _level.set(i, _init_level);
1.512 + _level[i] = _init_level;
1.513 if (_last[_init_level] == INVALID) {
1.514 _first[_init_level] = i;
1.515 _last[_init_level] = i;
1.516 - _prev.set(i, INVALID);
1.517 - _next.set(i, INVALID);
1.518 + _prev[i] = INVALID;
1.519 + _next[i] = INVALID;
1.520 } else {
1.521 - _prev.set(i, _last[_init_level]);
1.522 - _next.set(i, INVALID);
1.523 - _next.set(_last[_init_level], i);
1.524 + _prev[i] = _last[_init_level];
1.525 + _next[i] = INVALID;
1.526 + _next[_last[_init_level]] = i;
1.527 _last[_init_level] = i;
1.528 }
1.529 }