1.1 --- a/lemon/elevator.h Wed Nov 14 17:42:48 2007 +0000
1.2 +++ b/lemon/elevator.h Wed Nov 14 17:44:42 2007 +0000
1.3 @@ -42,16 +42,22 @@
1.4 ///Each item is either \em active or not, and you can also choose a
1.5 ///highest level active item.
1.6 ///
1.7 + ///\sa LinkedElevator
1.8 + ///
1.9 ///\param Graph the underlying graph type
1.10 ///\param Item Type of the items the data is assigned to (Graph::Node,
1.11 ///Graph::Edge, Graph::UEdge)
1.12 template<class Graph, class Item>
1.13 class Elevator
1.14 {
1.15 - public:
1.16 + private:
1.17 +
1.18 + typedef Item Key;
1.19 + typedef int Value;
1.20 +
1.21 typedef typename std::vector<Item>::iterator Vit;
1.22 - typedef DefaultMap<Graph,Item,Vit> VitMap;
1.23 - typedef DefaultMap<Graph,Item,int> IntMap;
1.24 + typedef typename ItemSetTraits<Graph,Item>::template Map<Vit>::Type VitMap;
1.25 + typedef typename ItemSetTraits<Graph,Item>::template Map<int>::Type IntMap;
1.26
1.27 const Graph &_g;
1.28 int _max_level;
1.29 @@ -86,28 +92,8 @@
1.30 *j=ti;
1.31 }
1.32
1.33 - void checkDs() const
1.34 - {
1.35 - for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
1.36 - {
1.37 - Vit w=_where[i];
1.38 - int l=_level[i];
1.39 - check(*w==i,"GEBASZ: CORRUPT DS");
1.40 - check(_first[l]<=w,"GEBASZ: CORRUPT DS");
1.41 - check(_first[l+1]>w,"GEBASZ: CORRUPT DS");
1.42 - }
1.43 - for(int l=0;l<=_max_level;++l)
1.44 - {
1.45 - check(_first[l]<=_last_active[l]+1,"GEBASZ: CORRUPT DS");
1.46 - check(_last_active[l]<_first[l+1],"GEBASZ: CORRUPT DS");
1.47 - check(_first[l]<=_first[l+1],"GEBASZ: CORRUPT DS");
1.48 - }
1.49 - check(_highest_active<0 ||
1.50 - _first[_highest_active]<=_last_active[_highest_active],
1.51 - "GEBASZ: CORRUPT DS");
1.52 - }
1.53 -
1.54 public:
1.55 +
1.56 ///Constructor with given maximum level.
1.57
1.58 ///Constructor with given maximum level.
1.59 @@ -144,7 +130,7 @@
1.60 _highest_active(-1)
1.61 {
1.62 }
1.63 -
1.64 +
1.65 ///Activate item \c i.
1.66
1.67 ///Activate item \c i.
1.68 @@ -174,22 +160,16 @@
1.69 ///Return the level of item \c i.
1.70 int operator[](Item i) const { return _level[i]; }
1.71
1.72 - ///Returns an active item on level \c l.
1.73 -
1.74 - ///Returns an active item on level \c l.
1.75 - ///
1.76 - ///Returns an active item on level \c l or \ref INVALID if there is no such
1.77 - ///an item. (\c l must be from the range [0...\c max_level].
1.78 - Item operator[](int l) const
1.79 - {
1.80 - return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
1.81 - }
1.82 -
1.83 ///Return the number of items on level \c l.
1.84 int onLevel(int l) const
1.85 {
1.86 return _first[l+1]-_first[l];
1.87 }
1.88 + ///Return true if the level is empty.
1.89 + bool emptyLevel(int l) const
1.90 + {
1.91 + return _first[l+1]-_first[l]==0;
1.92 + }
1.93 ///Return the number of items above level \c l.
1.94 int aboveLevel(int l) const
1.95 {
1.96 @@ -200,6 +180,11 @@
1.97 {
1.98 return _last_active[l]-_first[l]+1;
1.99 }
1.100 + ///Return true if there is not active item on level \c l.
1.101 + bool activeFree(int l) const
1.102 + {
1.103 + return _last_active[l]<_first[l];
1.104 + }
1.105 ///Return the maximum allowed level.
1.106 int maxLevel() const
1.107 {
1.108 @@ -252,7 +237,7 @@
1.109 ///\warning \c new_level must be strictly higher
1.110 ///than the current level.
1.111 ///
1.112 - void liftHighestActiveTo(int new_level)
1.113 + void liftHighestActive(int new_level)
1.114 {
1.115 const Item li = *_last_active[_highest_active];
1.116
1.117 @@ -266,9 +251,109 @@
1.118 _level[li]=new_level;
1.119 _highest_active=new_level;
1.120 }
1.121 +
1.122 + ///Lift the highest active item.
1.123 +
1.124 + ///Lift the item returned by highestActive() to the top level and
1.125 + ///deactivates it.
1.126 + ///
1.127 + ///\warning \c new_level must be strictly higher
1.128 + ///than the current level.
1.129 + ///
1.130 + void liftHighestActiveToTop()
1.131 + {
1.132 + const Item li = *_last_active[_highest_active];
1.133 +
1.134 + copy(--_first[_highest_active+1],_last_active[_highest_active]--);
1.135 + for(int l=_highest_active+1;l<_max_level;l++)
1.136 + {
1.137 + copy(--_first[l+1],_first[l]);
1.138 + --_last_active[l];
1.139 + }
1.140 + copy(li,_first[_max_level]);
1.141 + --_last_active[_max_level];
1.142 + _level[li]=_max_level;
1.143 +
1.144 + while(_highest_active>=0 &&
1.145 + _last_active[_highest_active]<_first[_highest_active])
1.146 + _highest_active--;
1.147 + }
1.148
1.149 ///@}
1.150
1.151 + ///\name Active Item on Certain Level
1.152 + ///Functions for working with the active items.
1.153 +
1.154 + ///@{
1.155 +
1.156 + ///Returns an active item on level \c l.
1.157 +
1.158 + ///Returns an active item on level \c l.
1.159 + ///
1.160 + ///Returns an active item on level \c l or \ref INVALID if there is no such
1.161 + ///an item. (\c l must be from the range [0...\c max_level].
1.162 + Item activeOn(int l) const
1.163 + {
1.164 + return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
1.165 + }
1.166 +
1.167 + ///Lifts the active item returned by \c activeOn() member function.
1.168 +
1.169 + ///Lifts the active item returned by \c activeOn() member function
1.170 + ///by one.
1.171 + Item liftActiveOn(int level)
1.172 + {
1.173 + ++_level[*_last_active[level]];
1.174 + swap(_last_active[level]--, --_first[level+1]);
1.175 + if (level+1>_highest_active) ++_highest_active;
1.176 + }
1.177 +
1.178 + ///Lifts the active item returned by \c activeOn() member function.
1.179 +
1.180 + ///Lifts the active item returned by \c activeOn() member function
1.181 + ///to the given level.
1.182 + void liftActiveOn(int level, int new_level)
1.183 + {
1.184 + const Item ai = *_last_active[level];
1.185 +
1.186 + copy(--_first[level+1], _last_active[level]--);
1.187 + for(int l=level+1;l<new_level;l++)
1.188 + {
1.189 + copy(_last_active[l],_first[l]);
1.190 + copy(--_first[l+1], _last_active[l]--);
1.191 + }
1.192 + copy(ai,_first[new_level]);
1.193 + _level[ai]=new_level;
1.194 + if (new_level>_highest_active) _highest_active=new_level;
1.195 + }
1.196 +
1.197 + ///Lifts the active item returned by \c activeOn() member function.
1.198 +
1.199 + ///Lifts the active item returned by \c activeOn() member function
1.200 + ///to the top level.
1.201 + void liftActiveToTop(int level)
1.202 + {
1.203 + const Item ai = *_last_active[level];
1.204 +
1.205 + copy(--_first[level+1],_last_active[level]--);
1.206 + for(int l=level+1;l<_max_level;l++)
1.207 + {
1.208 + copy(_last_active[l],_first[l]);
1.209 + copy(--_first[l+1], _last_active[l]--);
1.210 + }
1.211 + copy(ai,_first[_max_level]);
1.212 + --_last_active[_max_level];
1.213 + _level[ai]=_max_level;
1.214 +
1.215 + if (_highest_active==level) {
1.216 + while(_highest_active>=0 &&
1.217 + _last_active[_highest_active]<_first[_highest_active])
1.218 + _highest_active--;
1.219 + }
1.220 + }
1.221 +
1.222 + ///@}
1.223 +
1.224 ///Lift an active item to a higher level.
1.225
1.226 ///Lift an active item to a higher level.
1.227 @@ -276,7 +361,7 @@
1.228 ///\param new_level The new level of \c i. It must be strictly higher
1.229 ///than the current level.
1.230 ///
1.231 - void liftTo(Item i, int new_level)
1.232 + void lift(Item i, int new_level)
1.233 {
1.234 const int lo = _level[i];
1.235 const Vit w = _where[i];
1.236 @@ -292,28 +377,11 @@
1.237 _level[i]=new_level;
1.238 if(new_level>_highest_active) _highest_active=new_level;
1.239 }
1.240 -
1.241 -// void liftToTop(int l)
1.242 -// {
1.243 -// const Vit f=_first[l];
1.244 -// for(int i=l;i<=_max_level;i++)
1.245 -// {
1.246 -// _first[i]=f;
1.247 -// _last_active[i]=f-1;
1.248 -// }
1.249 -// for(Vit i=f;i!=_items.end();++i)
1.250 -// _level[*i]=_max_level;
1.251 -// for(_highest_active=l-1;
1.252 -// _highest_active>=0 &&
1.253 -// _last_active[_highest_active]<_first[_highest_active];
1.254 -// _highest_active--) ;
1.255 -// }
1.256
1.257 ///Lift all nodes on and above a level to the top (and deactivate them).
1.258
1.259 - ///This function lifts all nodes on and above level \c l to \c maxLevel(),
1.260 - ///and
1.261 - ///also deactivates them.
1.262 + ///This function lifts all nodes on and above level \c l to \c
1.263 + ///maxLevel(), and also deactivates them.
1.264 void liftToTop(int l)
1.265 {
1.266 const Vit f=_first[l];
1.267 @@ -397,12 +465,511 @@
1.268 }
1.269 _first[_max_level+1]=_items.begin()+_item_num;
1.270 _last_active[_max_level+1]=_items.begin()+_item_num-1;
1.271 + _highest_active = -1;
1.272 }
1.273
1.274 ///@}
1.275
1.276 };
1.277
1.278 + ///Class for handling "labels" in push-relabel type algorithms.
1.279 +
1.280 + ///A class for handling "labels" in push-relabel type algorithms.
1.281 + ///
1.282 + ///\ingroup auxdat
1.283 + ///Using this class you can assign "labels" (nonnegative integer numbers)
1.284 + ///to the edges or nodes of a graph, manipulate and query them through
1.285 + ///operations typically arising in "push-relabel" type algorithms.
1.286 + ///
1.287 + ///Each item is either \em active or not, and you can also choose a
1.288 + ///highest level active item.
1.289 + ///
1.290 + ///\sa Elevator
1.291 + ///
1.292 + ///\param Graph the underlying graph type
1.293 + ///\param Item Type of the items the data is assigned to (Graph::Node,
1.294 + ///Graph::Edge, Graph::UEdge)
1.295 + template <class Graph, class Item>
1.296 + class LinkedElevator {
1.297 + private:
1.298 +
1.299 + typedef Item Key;
1.300 + typedef int Value;
1.301 +
1.302 + typedef typename ItemSetTraits<Graph,Item>::
1.303 + template Map<Item>::Type ItemMap;
1.304 + typedef typename ItemSetTraits<Graph,Item>::
1.305 + template Map<int>::Type IntMap;
1.306 + typedef typename ItemSetTraits<Graph,Item>::
1.307 + template Map<bool>::Type BoolMap;
1.308 +
1.309 + const Graph &_graph;
1.310 + int _max_level;
1.311 + int _item_num;
1.312 + std::vector<Item> _first, _last;
1.313 + ItemMap _prev, _next;
1.314 + int _highest_active;
1.315 + IntMap _level;
1.316 + BoolMap _active;
1.317 +
1.318 + public:
1.319 + ///Constructor with given maximum level.
1.320 +
1.321 + ///Constructor with given maximum level.
1.322 + ///
1.323 + ///\param g The underlying graph
1.324 + ///\param max_level Set the range of the possible labels to
1.325 + ///[0...\c max_level]
1.326 + LinkedElevator(const Graph& graph, int max_level)
1.327 + : _graph(graph), _max_level(max_level), _item_num(_max_level),
1.328 + _first(_max_level + 1), _last(_max_level + 1),
1.329 + _prev(graph), _next(graph),
1.330 + _highest_active(-1), _level(graph), _active(graph) {}
1.331 +
1.332 + ///Constructor.
1.333 +
1.334 + ///Constructor.
1.335 + ///
1.336 + ///\param g The underlying graph
1.337 + ///The range of the possible labels is [0...\c max_level],
1.338 + ///where \c max_level is equal to the number of labeled items in the graph.
1.339 + LinkedElevator(const Graph& graph)
1.340 + : _graph(graph), _max_level(countItems<Graph, Item>(graph)),
1.341 + _item_num(_max_level),
1.342 + _first(_max_level + 1), _last(_max_level + 1),
1.343 + _prev(graph, INVALID), _next(graph, INVALID),
1.344 + _highest_active(-1), _level(graph), _active(graph) {}
1.345 +
1.346 +
1.347 + ///Activate item \c i.
1.348 +
1.349 + ///Activate item \c i.
1.350 + ///\pre Item \c i shouldn't be active before.
1.351 + void activate(Item i) {
1.352 + _active.set(i, true);
1.353 +
1.354 + int level = _level[i];
1.355 + if (level > _highest_active) {
1.356 + _highest_active = level;
1.357 + }
1.358 +
1.359 + if (_prev[i] == INVALID || _active[_prev[i]]) return;
1.360 + //unlace
1.361 + _next.set(_prev[i], _next[i]);
1.362 + if (_next[i] != INVALID) {
1.363 + _prev.set(_next[i], _prev[i]);
1.364 + } else {
1.365 + _last[level] = _prev[i];
1.366 + }
1.367 + //lace
1.368 + _next.set(i, _first[level]);
1.369 + _prev.set(_first[level], i);
1.370 + _prev.set(i, INVALID);
1.371 + _first[level] = i;
1.372 +
1.373 + }
1.374 +
1.375 + ///Deactivate item \c i.
1.376 +
1.377 + ///Deactivate item \c i.
1.378 + ///\pre Item \c i must be active before.
1.379 + void deactivate(Item i) {
1.380 + _active.set(i, false);
1.381 + int level = _level[i];
1.382 +
1.383 + if (_next[i] == INVALID || !_active[_next[i]])
1.384 + goto find_highest_level;
1.385 +
1.386 + //unlace
1.387 + _prev.set(_next[i], _prev[i]);
1.388 + if (_prev[i] != INVALID) {
1.389 + _next.set(_prev[i], _next[i]);
1.390 + } else {
1.391 + _first[_level[i]] = _next[i];
1.392 + }
1.393 + //lace
1.394 + _prev.set(i, _last[level]);
1.395 + _next.set(_last[level], i);
1.396 + _next.set(i, INVALID);
1.397 + _last[level] = i;
1.398 +
1.399 + find_highest_level:
1.400 + if (level == _highest_active) {
1.401 + while (_highest_active >= 0 && activeFree(_highest_active))
1.402 + --_highest_active;
1.403 + }
1.404 + }
1.405 +
1.406 + ///Query whether item \c i is active
1.407 + bool active(Item i) const { return _active[i]; }
1.408 +
1.409 + ///Return the level of item \c i.
1.410 + int operator[](Item i) const { return _level[i]; }
1.411 +
1.412 + ///Return the number of items on level \c l.
1.413 + int onLevel(int l) const {
1.414 + int num = 0;
1.415 + Item n = _first[l];
1.416 + while (n != INVALID) {
1.417 + ++num;
1.418 + n = _next[n];
1.419 + }
1.420 + return num;
1.421 + }
1.422 +
1.423 + ///Return true if the level is empty.
1.424 + bool emptyLevel(int l) const {
1.425 + return _first[l] == INVALID;
1.426 + }
1.427 +
1.428 + ///Return the number of items above level \c l.
1.429 + int aboveLevel(int l) const {
1.430 + int num = 0;
1.431 + for (int level = l + 1; level < _max_level; ++level)
1.432 + num += onLevel(level);
1.433 + return num;
1.434 + }
1.435 +
1.436 + ///Return the number of active items on level \c l.
1.437 + int activesOnLevel(int l) const {
1.438 + int num = 0;
1.439 + Item n = _first[l];
1.440 + while (n != INVALID && _active[n]) {
1.441 + ++num;
1.442 + n = _next[n];
1.443 + }
1.444 + return num;
1.445 + }
1.446 +
1.447 + ///Return true if there is not active item on level \c l.
1.448 + bool activeFree(int l) const {
1.449 + return _first[l] == INVALID || !_active[_first[l]];
1.450 + }
1.451 +
1.452 + ///Return the maximum allowed level.
1.453 + int maxLevel() const {
1.454 + return _max_level;
1.455 + }
1.456 +
1.457 + ///\name Highest Active Item
1.458 + ///Functions for working with the highest level
1.459 + ///active item.
1.460 +
1.461 + ///@{
1.462 +
1.463 + ///Return a highest level active item.
1.464 +
1.465 + ///Return a highest level active item.
1.466 + ///
1.467 + ///\return the highest level active item or INVALID if there is no
1.468 + ///active item.
1.469 + Item highestActive() const {
1.470 + return _highest_active >= 0 ? _first[_highest_active] : INVALID;
1.471 + }
1.472 +
1.473 + ///Return a highest active level.
1.474 +
1.475 + ///Return a highest active level.
1.476 + ///
1.477 + ///\return the level of the highest active item or -1 if there is
1.478 + ///no active item.
1.479 + int highestActiveLevel() const {
1.480 + return _highest_active;
1.481 + }
1.482 +
1.483 + ///Lift the highest active item by one.
1.484 +
1.485 + ///Lift the item returned by highestActive() by one.
1.486 + ///
1.487 + void liftHighestActive() {
1.488 + Item i = _first[_highest_active];
1.489 + if (_next[i] != INVALID) {
1.490 + _prev.set(_next[i], INVALID);
1.491 + _first[_highest_active] = _next[i];
1.492 + } else {
1.493 + _first[_highest_active] = INVALID;
1.494 + _last[_highest_active] = INVALID;
1.495 + }
1.496 + _level.set(i, ++_highest_active);
1.497 + if (_first[_highest_active] == INVALID) {
1.498 + _first[_highest_active] = i;
1.499 + _last[_highest_active] = i;
1.500 + _prev.set(i, INVALID);
1.501 + _next.set(i, INVALID);
1.502 + } else {
1.503 + _prev.set(_first[_highest_active], i);
1.504 + _next.set(i, _first[_highest_active]);
1.505 + _first[_highest_active] = i;
1.506 + }
1.507 + }
1.508 +
1.509 + ///Lift the highest active item.
1.510 +
1.511 + ///Lift the item returned by highestActive() to level \c new_level.
1.512 + ///
1.513 + ///\warning \c new_level must be strictly higher
1.514 + ///than the current level.
1.515 + ///
1.516 + void liftHighestActive(int new_level) {
1.517 + Item i = _first[_highest_active];
1.518 + if (_next[i] != INVALID) {
1.519 + _prev.set(_next[i], INVALID);
1.520 + _first[_highest_active] = _next[i];
1.521 + } else {
1.522 + _first[_highest_active] = INVALID;
1.523 + _last[_highest_active] = INVALID;
1.524 + }
1.525 + _level.set(i, _highest_active = new_level);
1.526 + if (_first[_highest_active] == INVALID) {
1.527 + _first[_highest_active] = _last[_highest_active] = i;
1.528 + _prev.set(i, INVALID);
1.529 + _next.set(i, INVALID);
1.530 + } else {
1.531 + _prev.set(_first[_highest_active], i);
1.532 + _next.set(i, _first[_highest_active]);
1.533 + _first[_highest_active] = i;
1.534 + }
1.535 + }
1.536 +
1.537 + ///Lift the highest active to top.
1.538 +
1.539 + ///Lift the item returned by highestActive() to the top level and
1.540 + ///deactivates the node.
1.541 + ///
1.542 + void liftHighestActiveToTop() {
1.543 + Item i = _first[_highest_active];
1.544 + _level.set(i, _max_level);
1.545 + if (_next[i] != INVALID) {
1.546 + _prev.set(_next[i], INVALID);
1.547 + _first[_highest_active] = _next[i];
1.548 + } else {
1.549 + _first[_highest_active] = INVALID;
1.550 + _last[_highest_active] = INVALID;
1.551 + }
1.552 + while (_highest_active >= 0 && activeFree(_highest_active))
1.553 + --_highest_active;
1.554 + }
1.555 +
1.556 + ///@}
1.557 +
1.558 + ///\name Active Item on Certain Level
1.559 + ///Functions for working with the active items.
1.560 +
1.561 + ///@{
1.562 +
1.563 + ///Returns an active item on level \c l.
1.564 +
1.565 + ///Returns an active item on level \c l.
1.566 + ///
1.567 + ///Returns an active item on level \c l or \ref INVALID if there is no such
1.568 + ///an item. (\c l must be from the range [0...\c max_level].
1.569 + Item activeOn(int l) const
1.570 + {
1.571 + return _active[_first[l]] ? _first[l] : INVALID;
1.572 + }
1.573 +
1.574 + ///Lifts the active item returned by \c activeOn() member function.
1.575 +
1.576 + ///Lifts the active item returned by \c activeOn() member function
1.577 + ///by one.
1.578 + Item liftActiveOn(int l)
1.579 + {
1.580 + Item i = _first[l];
1.581 + if (_next[i] != INVALID) {
1.582 + _prev.set(_next[i], INVALID);
1.583 + _first[l] = _next[i];
1.584 + } else {
1.585 + _first[l] = INVALID;
1.586 + _last[l] = INVALID;
1.587 + }
1.588 + _level.set(i, ++l);
1.589 + if (_first[l] == INVALID) {
1.590 + _first[l] = _last[l] = i;
1.591 + _prev.set(i, INVALID);
1.592 + _next.set(i, INVALID);
1.593 + } else {
1.594 + _prev.set(_first[l], i);
1.595 + _next.set(i, _first[l]);
1.596 + _first[l] = i;
1.597 + }
1.598 + if (_highest_active < l) {
1.599 + _highest_active = l;
1.600 + }
1.601 + }
1.602 +
1.603 + /// \brief Lifts the active item returned by \c activeOn() member function.
1.604 + ///
1.605 + /// Lifts the active item returned by \c activeOn() member function
1.606 + /// to the given level.
1.607 + void liftActiveOn(int l, int new_level)
1.608 + {
1.609 + Item i = _first[l];
1.610 + if (_next[i] != INVALID) {
1.611 + _prev.set(_next[i], INVALID);
1.612 + _first[l] = _next[i];
1.613 + } else {
1.614 + _first[l] = INVALID;
1.615 + _last[l] = INVALID;
1.616 + }
1.617 + _level.set(i, l = new_level);
1.618 + if (_first[l] == INVALID) {
1.619 + _first[l] = _last[l] = i;
1.620 + _prev.set(i, INVALID);
1.621 + _next.set(i, INVALID);
1.622 + } else {
1.623 + _prev.set(_first[l], i);
1.624 + _next.set(i, _first[l]);
1.625 + _first[l] = i;
1.626 + }
1.627 + if (_highest_active < l) {
1.628 + _highest_active = l;
1.629 + }
1.630 + }
1.631 +
1.632 + ///Lifts the active item returned by \c activeOn() member function.
1.633 +
1.634 + ///Lifts the active item returned by \c activeOn() member function
1.635 + ///to the top level.
1.636 + void liftActiveToTop(int l)
1.637 + {
1.638 + Item i = _first[l];
1.639 + if (_next[i] != INVALID) {
1.640 + _prev.set(_next[i], INVALID);
1.641 + _first[l] = _next[i];
1.642 + } else {
1.643 + _first[l] = INVALID;
1.644 + _last[l] = INVALID;
1.645 + }
1.646 + _level.set(i, _max_level);
1.647 + if (l == _highest_active) {
1.648 + while (_highest_active >= 0 && activeFree(_highest_active))
1.649 + --_highest_active;
1.650 + }
1.651 + }
1.652 +
1.653 + ///@}
1.654 +
1.655 + /// \brief Lift an active item to a higher level.
1.656 + ///
1.657 + /// Lift an active item to a higher level.
1.658 + /// \param i The item to be lifted. It must be active.
1.659 + /// \param new_level The new level of \c i. It must be strictly higher
1.660 + /// than the current level.
1.661 + ///
1.662 + void lift(Item i, int new_level) {
1.663 + if (_next[i] != INVALID) {
1.664 + _prev.set(_next[i], _prev[i]);
1.665 + } else {
1.666 + _last[new_level] = _prev[i];
1.667 + }
1.668 + if (_prev[i] != INVALID) {
1.669 + _next.set(_prev[i], _next[i]);
1.670 + } else {
1.671 + _first[new_level] = _next[i];
1.672 + }
1.673 + _level.set(i, new_level);
1.674 + if (_first[new_level] == INVALID) {
1.675 + _first[new_level] = _last[new_level] = i;
1.676 + _prev.set(i, INVALID);
1.677 + _next.set(i, INVALID);
1.678 + } else {
1.679 + _prev.set(_first[new_level], i);
1.680 + _next.set(i, _first[new_level]);
1.681 + _first[new_level] = i;
1.682 + }
1.683 + if (_highest_active < new_level) {
1.684 + _highest_active = new_level;
1.685 + }
1.686 + }
1.687 +
1.688 + ///Lift all nodes on and above a level to the top (and deactivate them).
1.689 +
1.690 + ///This function lifts all nodes on and above level \c l to \c
1.691 + ///maxLevel(), and also deactivates them.
1.692 + void liftToTop(int l) {
1.693 + for (int i = l + 1; _first[i] != INVALID; ++i) {
1.694 + Item n = _first[i];
1.695 + while (n != INVALID) {
1.696 + _level.set(n, _max_level);
1.697 + n = _next[n];
1.698 + }
1.699 + _first[i] = INVALID;
1.700 + _last[i] = INVALID;
1.701 + }
1.702 + if (_highest_active > l - 1) {
1.703 + _highest_active = l - 1;
1.704 + while (_highest_active >= 0 && activeFree(_highest_active))
1.705 + --_highest_active;
1.706 + }
1.707 + }
1.708 +
1.709 + private:
1.710 +
1.711 + int _init_level;
1.712 +
1.713 + public:
1.714 +
1.715 + ///\name Initialization
1.716 + ///Using this function you can initialize the levels of the item.
1.717 + ///\n
1.718 + ///This initializatios is started with calling \c initStart().
1.719 + ///Then the
1.720 + ///items should be listed levels by levels statring with the lowest one
1.721 + ///(with level 0). This is done by using \c initAddItem()
1.722 + ///and \c initNewLevel(). Finally \c initFinish() must be called.
1.723 + ///The items not listed will be put on the highest level.
1.724 + ///@{
1.725 +
1.726 + ///Start the initialization process.
1.727 +
1.728 + void initStart() {
1.729 +
1.730 + for (int i = 0; i <= _max_level; ++i) {
1.731 + _first[i] = _last[i] = INVALID;
1.732 + }
1.733 + _init_level = 0;
1.734 + for(typename ItemSetTraits<Graph,Item>::ItemIt i(_graph);
1.735 + i != INVALID; ++i) {
1.736 + _level.set(i, _max_level);
1.737 + }
1.738 + }
1.739 +
1.740 + ///Add an item to the current level.
1.741 +
1.742 + void initAddItem(Item i) {
1.743 + _level.set(i, _init_level);
1.744 + if (_last[_init_level] == INVALID) {
1.745 + _first[_init_level] = i;
1.746 + _last[_init_level] = i;
1.747 + _prev.set(i, INVALID);
1.748 + _next.set(i, INVALID);
1.749 + } else {
1.750 + _prev.set(i, _last[_init_level]);
1.751 + _next.set(i, INVALID);
1.752 + _next.set(_last[_init_level], i);
1.753 + _last[_init_level] = i;
1.754 + }
1.755 + }
1.756 +
1.757 + ///Start a new level.
1.758 +
1.759 + ///Start a new level.
1.760 + ///It shouldn't be used before the items on level 0 are listed.
1.761 + void initNewLevel() {
1.762 + ++_init_level;
1.763 + }
1.764 +
1.765 + ///Finalize the initialization process.
1.766 +
1.767 + void initFinish() {
1.768 + _highest_active = -1;
1.769 + }
1.770 +
1.771 + ///@}
1.772 +
1.773 + };
1.774 +
1.775 +
1.776 } //END OF NAMESPACE LEMON
1.777
1.778 #endif