1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/elevator.h Thu Nov 05 15:50:01 2009 +0100
1.3 @@ -0,0 +1,982 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
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 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_ELEVATOR_H
1.23 +#define LEMON_ELEVATOR_H
1.24 +
1.25 +///\ingroup auxdat
1.26 +///\file
1.27 +///\brief Elevator class
1.28 +///
1.29 +///Elevator class implements an efficient data structure
1.30 +///for labeling items in push-relabel type algorithms.
1.31 +///
1.32 +
1.33 +#include <lemon/core.h>
1.34 +#include <lemon/bits/traits.h>
1.35 +
1.36 +namespace lemon {
1.37 +
1.38 + ///Class for handling "labels" in push-relabel type algorithms.
1.39 +
1.40 + ///A class for handling "labels" in push-relabel type algorithms.
1.41 + ///
1.42 + ///\ingroup auxdat
1.43 + ///Using this class you can assign "labels" (nonnegative integer numbers)
1.44 + ///to the edges or nodes of a graph, manipulate and query them through
1.45 + ///operations typically arising in "push-relabel" type algorithms.
1.46 + ///
1.47 + ///Each item is either \em active or not, and you can also choose a
1.48 + ///highest level active item.
1.49 + ///
1.50 + ///\sa LinkedElevator
1.51 + ///
1.52 + ///\param GR Type of the underlying graph.
1.53 + ///\param Item Type of the items the data is assigned to (\c GR::Node,
1.54 + ///\c GR::Arc or \c GR::Edge).
1.55 + template<class GR, class Item>
1.56 + class Elevator
1.57 + {
1.58 + public:
1.59 +
1.60 + typedef Item Key;
1.61 + typedef int Value;
1.62 +
1.63 + private:
1.64 +
1.65 + typedef Item *Vit;
1.66 + typedef typename ItemSetTraits<GR,Item>::template Map<Vit>::Type VitMap;
1.67 + typedef typename ItemSetTraits<GR,Item>::template Map<int>::Type IntMap;
1.68 +
1.69 + const GR &_g;
1.70 + int _max_level;
1.71 + int _item_num;
1.72 + VitMap _where;
1.73 + IntMap _level;
1.74 + std::vector<Item> _items;
1.75 + std::vector<Vit> _first;
1.76 + std::vector<Vit> _last_active;
1.77 +
1.78 + int _highest_active;
1.79 +
1.80 + void copy(Item i, Vit p)
1.81 + {
1.82 + _where[*p=i] = p;
1.83 + }
1.84 + void copy(Vit s, Vit p)
1.85 + {
1.86 + if(s!=p)
1.87 + {
1.88 + Item i=*s;
1.89 + *p=i;
1.90 + _where[i] = p;
1.91 + }
1.92 + }
1.93 + void swap(Vit i, Vit j)
1.94 + {
1.95 + Item ti=*i;
1.96 + Vit ct = _where[ti];
1.97 + _where[ti] = _where[*i=*j];
1.98 + _where[*j] = ct;
1.99 + *j=ti;
1.100 + }
1.101 +
1.102 + public:
1.103 +
1.104 + ///Constructor with given maximum level.
1.105 +
1.106 + ///Constructor with given maximum level.
1.107 + ///
1.108 + ///\param graph The underlying graph.
1.109 + ///\param max_level The maximum allowed level.
1.110 + ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
1.111 + Elevator(const GR &graph,int max_level) :
1.112 + _g(graph),
1.113 + _max_level(max_level),
1.114 + _item_num(_max_level),
1.115 + _where(graph),
1.116 + _level(graph,0),
1.117 + _items(_max_level),
1.118 + _first(_max_level+2),
1.119 + _last_active(_max_level+2),
1.120 + _highest_active(-1) {}
1.121 + ///Constructor.
1.122 +
1.123 + ///Constructor.
1.124 + ///
1.125 + ///\param graph The underlying graph.
1.126 + ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
1.127 + ///where \c max_level is equal to the number of labeled items in the graph.
1.128 + Elevator(const GR &graph) :
1.129 + _g(graph),
1.130 + _max_level(countItems<GR, Item>(graph)),
1.131 + _item_num(_max_level),
1.132 + _where(graph),
1.133 + _level(graph,0),
1.134 + _items(_max_level),
1.135 + _first(_max_level+2),
1.136 + _last_active(_max_level+2),
1.137 + _highest_active(-1)
1.138 + {
1.139 + }
1.140 +
1.141 + ///Activate item \c i.
1.142 +
1.143 + ///Activate item \c i.
1.144 + ///\pre Item \c i shouldn't be active before.
1.145 + void activate(Item i)
1.146 + {
1.147 + const int l=_level[i];
1.148 + swap(_where[i],++_last_active[l]);
1.149 + if(l>_highest_active) _highest_active=l;
1.150 + }
1.151 +
1.152 + ///Deactivate item \c i.
1.153 +
1.154 + ///Deactivate item \c i.
1.155 + ///\pre Item \c i must be active before.
1.156 + void deactivate(Item i)
1.157 + {
1.158 + swap(_where[i],_last_active[_level[i]]--);
1.159 + while(_highest_active>=0 &&
1.160 + _last_active[_highest_active]<_first[_highest_active])
1.161 + _highest_active--;
1.162 + }
1.163 +
1.164 + ///Query whether item \c i is active
1.165 + bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
1.166 +
1.167 + ///Return the level of item \c i.
1.168 + int operator[](Item i) const { return _level[i]; }
1.169 +
1.170 + ///Return the number of items on level \c l.
1.171 + int onLevel(int l) const
1.172 + {
1.173 + return _first[l+1]-_first[l];
1.174 + }
1.175 + ///Return true if level \c l is empty.
1.176 + bool emptyLevel(int l) const
1.177 + {
1.178 + return _first[l+1]-_first[l]==0;
1.179 + }
1.180 + ///Return the number of items above level \c l.
1.181 + int aboveLevel(int l) const
1.182 + {
1.183 + return _first[_max_level+1]-_first[l+1];
1.184 + }
1.185 + ///Return the number of active items on level \c l.
1.186 + int activesOnLevel(int l) const
1.187 + {
1.188 + return _last_active[l]-_first[l]+1;
1.189 + }
1.190 + ///Return true if there is no active item on level \c l.
1.191 + bool activeFree(int l) const
1.192 + {
1.193 + return _last_active[l]<_first[l];
1.194 + }
1.195 + ///Return the maximum allowed level.
1.196 + int maxLevel() const
1.197 + {
1.198 + return _max_level;
1.199 + }
1.200 +
1.201 + ///\name Highest Active Item
1.202 + ///Functions for working with the highest level
1.203 + ///active item.
1.204 +
1.205 + ///@{
1.206 +
1.207 + ///Return a highest level active item.
1.208 +
1.209 + ///Return a highest level active item or INVALID if there is no active
1.210 + ///item.
1.211 + Item highestActive() const
1.212 + {
1.213 + return _highest_active>=0?*_last_active[_highest_active]:INVALID;
1.214 + }
1.215 +
1.216 + ///Return the highest active level.
1.217 +
1.218 + ///Return the level of the highest active item or -1 if there is no active
1.219 + ///item.
1.220 + int highestActiveLevel() const
1.221 + {
1.222 + return _highest_active;
1.223 + }
1.224 +
1.225 + ///Lift the highest active item by one.
1.226 +
1.227 + ///Lift the item returned by highestActive() by one.
1.228 + ///
1.229 + void liftHighestActive()
1.230 + {
1.231 + Item it = *_last_active[_highest_active];
1.232 + ++_level[it];
1.233 + swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
1.234 + --_first[++_highest_active];
1.235 + }
1.236 +
1.237 + ///Lift the highest active item to the given level.
1.238 +
1.239 + ///Lift the item returned by highestActive() to level \c new_level.
1.240 + ///
1.241 + ///\warning \c new_level must be strictly higher
1.242 + ///than the current level.
1.243 + ///
1.244 + void liftHighestActive(int new_level)
1.245 + {
1.246 + const Item li = *_last_active[_highest_active];
1.247 +
1.248 + copy(--_first[_highest_active+1],_last_active[_highest_active]--);
1.249 + for(int l=_highest_active+1;l<new_level;l++)
1.250 + {
1.251 + copy(--_first[l+1],_first[l]);
1.252 + --_last_active[l];
1.253 + }
1.254 + copy(li,_first[new_level]);
1.255 + _level[li] = new_level;
1.256 + _highest_active=new_level;
1.257 + }
1.258 +
1.259 + ///Lift the highest active item to the top level.
1.260 +
1.261 + ///Lift the item returned by highestActive() to the top level and
1.262 + ///deactivate it.
1.263 + void liftHighestActiveToTop()
1.264 + {
1.265 + const Item li = *_last_active[_highest_active];
1.266 +
1.267 + copy(--_first[_highest_active+1],_last_active[_highest_active]--);
1.268 + for(int l=_highest_active+1;l<_max_level;l++)
1.269 + {
1.270 + copy(--_first[l+1],_first[l]);
1.271 + --_last_active[l];
1.272 + }
1.273 + copy(li,_first[_max_level]);
1.274 + --_last_active[_max_level];
1.275 + _level[li] = _max_level;
1.276 +
1.277 + while(_highest_active>=0 &&
1.278 + _last_active[_highest_active]<_first[_highest_active])
1.279 + _highest_active--;
1.280 + }
1.281 +
1.282 + ///@}
1.283 +
1.284 + ///\name Active Item on Certain Level
1.285 + ///Functions for working with the active items.
1.286 +
1.287 + ///@{
1.288 +
1.289 + ///Return an active item on level \c l.
1.290 +
1.291 + ///Return an active item on level \c l or \ref INVALID if there is no such
1.292 + ///an item. (\c l must be from the range [0...\c max_level].
1.293 + Item activeOn(int l) const
1.294 + {
1.295 + return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
1.296 + }
1.297 +
1.298 + ///Lift the active item returned by \c activeOn(level) by one.
1.299 +
1.300 + ///Lift the active item returned by \ref activeOn() "activeOn(level)"
1.301 + ///by one.
1.302 + Item liftActiveOn(int level)
1.303 + {
1.304 + Item it =*_last_active[level];
1.305 + ++_level[it];
1.306 + swap(_last_active[level]--, --_first[level+1]);
1.307 + if (level+1>_highest_active) ++_highest_active;
1.308 + }
1.309 +
1.310 + ///Lift the active item returned by \c activeOn(level) to the given level.
1.311 +
1.312 + ///Lift the active item returned by \ref activeOn() "activeOn(level)"
1.313 + ///to the given level.
1.314 + void liftActiveOn(int level, int new_level)
1.315 + {
1.316 + const Item ai = *_last_active[level];
1.317 +
1.318 + copy(--_first[level+1], _last_active[level]--);
1.319 + for(int l=level+1;l<new_level;l++)
1.320 + {
1.321 + copy(_last_active[l],_first[l]);
1.322 + copy(--_first[l+1], _last_active[l]--);
1.323 + }
1.324 + copy(ai,_first[new_level]);
1.325 + _level[ai] = new_level;
1.326 + if (new_level>_highest_active) _highest_active=new_level;
1.327 + }
1.328 +
1.329 + ///Lift the active item returned by \c activeOn(level) to the top level.
1.330 +
1.331 + ///Lift the active item returned by \ref activeOn() "activeOn(level)"
1.332 + ///to the top level and deactivate it.
1.333 + void liftActiveToTop(int level)
1.334 + {
1.335 + const Item ai = *_last_active[level];
1.336 +
1.337 + copy(--_first[level+1],_last_active[level]--);
1.338 + for(int l=level+1;l<_max_level;l++)
1.339 + {
1.340 + copy(_last_active[l],_first[l]);
1.341 + copy(--_first[l+1], _last_active[l]--);
1.342 + }
1.343 + copy(ai,_first[_max_level]);
1.344 + --_last_active[_max_level];
1.345 + _level[ai] = _max_level;
1.346 +
1.347 + if (_highest_active==level) {
1.348 + while(_highest_active>=0 &&
1.349 + _last_active[_highest_active]<_first[_highest_active])
1.350 + _highest_active--;
1.351 + }
1.352 + }
1.353 +
1.354 + ///@}
1.355 +
1.356 + ///Lift an active item to a higher level.
1.357 +
1.358 + ///Lift an active item to a higher level.
1.359 + ///\param i The item to be lifted. It must be active.
1.360 + ///\param new_level The new level of \c i. It must be strictly higher
1.361 + ///than the current level.
1.362 + ///
1.363 + void lift(Item i, int new_level)
1.364 + {
1.365 + const int lo = _level[i];
1.366 + const Vit w = _where[i];
1.367 +
1.368 + copy(_last_active[lo],w);
1.369 + copy(--_first[lo+1],_last_active[lo]--);
1.370 + for(int l=lo+1;l<new_level;l++)
1.371 + {
1.372 + copy(_last_active[l],_first[l]);
1.373 + copy(--_first[l+1],_last_active[l]--);
1.374 + }
1.375 + copy(i,_first[new_level]);
1.376 + _level[i] = new_level;
1.377 + if(new_level>_highest_active) _highest_active=new_level;
1.378 + }
1.379 +
1.380 + ///Move an inactive item to the top but one level (in a dirty way).
1.381 +
1.382 + ///This function moves an inactive item from the top level to the top
1.383 + ///but one level (in a dirty way).
1.384 + ///\warning It makes the underlying datastructure corrupt, so use it
1.385 + ///only if you really know what it is for.
1.386 + ///\pre The item is on the top level.
1.387 + void dirtyTopButOne(Item i) {
1.388 + _level[i] = _max_level - 1;
1.389 + }
1.390 +
1.391 + ///Lift all items on and above the given level to the top level.
1.392 +
1.393 + ///This function lifts all items on and above level \c l to the top
1.394 + ///level and deactivates them.
1.395 + void liftToTop(int l)
1.396 + {
1.397 + const Vit f=_first[l];
1.398 + const Vit tl=_first[_max_level];
1.399 + for(Vit i=f;i!=tl;++i)
1.400 + _level[*i] = _max_level;
1.401 + for(int i=l;i<=_max_level;i++)
1.402 + {
1.403 + _first[i]=f;
1.404 + _last_active[i]=f-1;
1.405 + }
1.406 + for(_highest_active=l-1;
1.407 + _highest_active>=0 &&
1.408 + _last_active[_highest_active]<_first[_highest_active];
1.409 + _highest_active--) ;
1.410 + }
1.411 +
1.412 + private:
1.413 + int _init_lev;
1.414 + Vit _init_num;
1.415 +
1.416 + public:
1.417 +
1.418 + ///\name Initialization
1.419 + ///Using these functions you can initialize the levels of the items.
1.420 + ///\n
1.421 + ///The initialization must be started with calling \c initStart().
1.422 + ///Then the items should be listed level by level starting with the
1.423 + ///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
1.424 + ///Finally \c initFinish() must be called.
1.425 + ///The items not listed are put on the highest level.
1.426 + ///@{
1.427 +
1.428 + ///Start the initialization process.
1.429 + void initStart()
1.430 + {
1.431 + _init_lev=0;
1.432 + _init_num=&_items[0];
1.433 + _first[0]=&_items[0];
1.434 + _last_active[0]=&_items[0]-1;
1.435 + Vit n=&_items[0];
1.436 + for(typename ItemSetTraits<GR,Item>::ItemIt i(_g);i!=INVALID;++i)
1.437 + {
1.438 + *n=i;
1.439 + _where[i] = n;
1.440 + _level[i] = _max_level;
1.441 + ++n;
1.442 + }
1.443 + }
1.444 +
1.445 + ///Add an item to the current level.
1.446 + void initAddItem(Item i)
1.447 + {
1.448 + swap(_where[i],_init_num);
1.449 + _level[i] = _init_lev;
1.450 + ++_init_num;
1.451 + }
1.452 +
1.453 + ///Start a new level.
1.454 +
1.455 + ///Start a new level.
1.456 + ///It shouldn't be used before the items on level 0 are listed.
1.457 + void initNewLevel()
1.458 + {
1.459 + _init_lev++;
1.460 + _first[_init_lev]=_init_num;
1.461 + _last_active[_init_lev]=_init_num-1;
1.462 + }
1.463 +
1.464 + ///Finalize the initialization process.
1.465 + void initFinish()
1.466 + {
1.467 + for(_init_lev++;_init_lev<=_max_level;_init_lev++)
1.468 + {
1.469 + _first[_init_lev]=_init_num;
1.470 + _last_active[_init_lev]=_init_num-1;
1.471 + }
1.472 + _first[_max_level+1]=&_items[0]+_item_num;
1.473 + _last_active[_max_level+1]=&_items[0]+_item_num-1;
1.474 + _highest_active = -1;
1.475 + }
1.476 +
1.477 + ///@}
1.478 +
1.479 + };
1.480 +
1.481 + ///Class for handling "labels" in push-relabel type algorithms.
1.482 +
1.483 + ///A class for handling "labels" in push-relabel type algorithms.
1.484 + ///
1.485 + ///\ingroup auxdat
1.486 + ///Using this class you can assign "labels" (nonnegative integer numbers)
1.487 + ///to the edges or nodes of a graph, manipulate and query them through
1.488 + ///operations typically arising in "push-relabel" type algorithms.
1.489 + ///
1.490 + ///Each item is either \em active or not, and you can also choose a
1.491 + ///highest level active item.
1.492 + ///
1.493 + ///\sa Elevator
1.494 + ///
1.495 + ///\param GR Type of the underlying graph.
1.496 + ///\param Item Type of the items the data is assigned to (\c GR::Node,
1.497 + ///\c GR::Arc or \c GR::Edge).
1.498 + template <class GR, class Item>
1.499 + class LinkedElevator {
1.500 + public:
1.501 +
1.502 + typedef Item Key;
1.503 + typedef int Value;
1.504 +
1.505 + private:
1.506 +
1.507 + typedef typename ItemSetTraits<GR,Item>::
1.508 + template Map<Item>::Type ItemMap;
1.509 + typedef typename ItemSetTraits<GR,Item>::
1.510 + template Map<int>::Type IntMap;
1.511 + typedef typename ItemSetTraits<GR,Item>::
1.512 + template Map<bool>::Type BoolMap;
1.513 +
1.514 + const GR &_graph;
1.515 + int _max_level;
1.516 + int _item_num;
1.517 + std::vector<Item> _first, _last;
1.518 + ItemMap _prev, _next;
1.519 + int _highest_active;
1.520 + IntMap _level;
1.521 + BoolMap _active;
1.522 +
1.523 + public:
1.524 + ///Constructor with given maximum level.
1.525 +
1.526 + ///Constructor with given maximum level.
1.527 + ///
1.528 + ///\param graph The underlying graph.
1.529 + ///\param max_level The maximum allowed level.
1.530 + ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
1.531 + LinkedElevator(const GR& graph, int max_level)
1.532 + : _graph(graph), _max_level(max_level), _item_num(_max_level),
1.533 + _first(_max_level + 1), _last(_max_level + 1),
1.534 + _prev(graph), _next(graph),
1.535 + _highest_active(-1), _level(graph), _active(graph) {}
1.536 +
1.537 + ///Constructor.
1.538 +
1.539 + ///Constructor.
1.540 + ///
1.541 + ///\param graph The underlying graph.
1.542 + ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
1.543 + ///where \c max_level is equal to the number of labeled items in the graph.
1.544 + LinkedElevator(const GR& graph)
1.545 + : _graph(graph), _max_level(countItems<GR, Item>(graph)),
1.546 + _item_num(_max_level),
1.547 + _first(_max_level + 1), _last(_max_level + 1),
1.548 + _prev(graph, INVALID), _next(graph, INVALID),
1.549 + _highest_active(-1), _level(graph), _active(graph) {}
1.550 +
1.551 +
1.552 + ///Activate item \c i.
1.553 +
1.554 + ///Activate item \c i.
1.555 + ///\pre Item \c i shouldn't be active before.
1.556 + void activate(Item i) {
1.557 + _active[i] = true;
1.558 +
1.559 + int level = _level[i];
1.560 + if (level > _highest_active) {
1.561 + _highest_active = level;
1.562 + }
1.563 +
1.564 + if (_prev[i] == INVALID || _active[_prev[i]]) return;
1.565 + //unlace
1.566 + _next[_prev[i]] = _next[i];
1.567 + if (_next[i] != INVALID) {
1.568 + _prev[_next[i]] = _prev[i];
1.569 + } else {
1.570 + _last[level] = _prev[i];
1.571 + }
1.572 + //lace
1.573 + _next[i] = _first[level];
1.574 + _prev[_first[level]] = i;
1.575 + _prev[i] = INVALID;
1.576 + _first[level] = i;
1.577 +
1.578 + }
1.579 +
1.580 + ///Deactivate item \c i.
1.581 +
1.582 + ///Deactivate item \c i.
1.583 + ///\pre Item \c i must be active before.
1.584 + void deactivate(Item i) {
1.585 + _active[i] = false;
1.586 + int level = _level[i];
1.587 +
1.588 + if (_next[i] == INVALID || !_active[_next[i]])
1.589 + goto find_highest_level;
1.590 +
1.591 + //unlace
1.592 + _prev[_next[i]] = _prev[i];
1.593 + if (_prev[i] != INVALID) {
1.594 + _next[_prev[i]] = _next[i];
1.595 + } else {
1.596 + _first[_level[i]] = _next[i];
1.597 + }
1.598 + //lace
1.599 + _prev[i] = _last[level];
1.600 + _next[_last[level]] = i;
1.601 + _next[i] = INVALID;
1.602 + _last[level] = i;
1.603 +
1.604 + find_highest_level:
1.605 + if (level == _highest_active) {
1.606 + while (_highest_active >= 0 && activeFree(_highest_active))
1.607 + --_highest_active;
1.608 + }
1.609 + }
1.610 +
1.611 + ///Query whether item \c i is active
1.612 + bool active(Item i) const { return _active[i]; }
1.613 +
1.614 + ///Return the level of item \c i.
1.615 + int operator[](Item i) const { return _level[i]; }
1.616 +
1.617 + ///Return the number of items on level \c l.
1.618 + int onLevel(int l) const {
1.619 + int num = 0;
1.620 + Item n = _first[l];
1.621 + while (n != INVALID) {
1.622 + ++num;
1.623 + n = _next[n];
1.624 + }
1.625 + return num;
1.626 + }
1.627 +
1.628 + ///Return true if the level is empty.
1.629 + bool emptyLevel(int l) const {
1.630 + return _first[l] == INVALID;
1.631 + }
1.632 +
1.633 + ///Return the number of items above level \c l.
1.634 + int aboveLevel(int l) const {
1.635 + int num = 0;
1.636 + for (int level = l + 1; level < _max_level; ++level)
1.637 + num += onLevel(level);
1.638 + return num;
1.639 + }
1.640 +
1.641 + ///Return the number of active items on level \c l.
1.642 + int activesOnLevel(int l) const {
1.643 + int num = 0;
1.644 + Item n = _first[l];
1.645 + while (n != INVALID && _active[n]) {
1.646 + ++num;
1.647 + n = _next[n];
1.648 + }
1.649 + return num;
1.650 + }
1.651 +
1.652 + ///Return true if there is no active item on level \c l.
1.653 + bool activeFree(int l) const {
1.654 + return _first[l] == INVALID || !_active[_first[l]];
1.655 + }
1.656 +
1.657 + ///Return the maximum allowed level.
1.658 + int maxLevel() const {
1.659 + return _max_level;
1.660 + }
1.661 +
1.662 + ///\name Highest Active Item
1.663 + ///Functions for working with the highest level
1.664 + ///active item.
1.665 +
1.666 + ///@{
1.667 +
1.668 + ///Return a highest level active item.
1.669 +
1.670 + ///Return a highest level active item or INVALID if there is no active
1.671 + ///item.
1.672 + Item highestActive() const {
1.673 + return _highest_active >= 0 ? _first[_highest_active] : INVALID;
1.674 + }
1.675 +
1.676 + ///Return the highest active level.
1.677 +
1.678 + ///Return the level of the highest active item or -1 if there is no active
1.679 + ///item.
1.680 + int highestActiveLevel() const {
1.681 + return _highest_active;
1.682 + }
1.683 +
1.684 + ///Lift the highest active item by one.
1.685 +
1.686 + ///Lift the item returned by highestActive() by one.
1.687 + ///
1.688 + void liftHighestActive() {
1.689 + Item i = _first[_highest_active];
1.690 + if (_next[i] != INVALID) {
1.691 + _prev[_next[i]] = INVALID;
1.692 + _first[_highest_active] = _next[i];
1.693 + } else {
1.694 + _first[_highest_active] = INVALID;
1.695 + _last[_highest_active] = INVALID;
1.696 + }
1.697 + _level[i] = ++_highest_active;
1.698 + if (_first[_highest_active] == INVALID) {
1.699 + _first[_highest_active] = i;
1.700 + _last[_highest_active] = i;
1.701 + _prev[i] = INVALID;
1.702 + _next[i] = INVALID;
1.703 + } else {
1.704 + _prev[_first[_highest_active]] = i;
1.705 + _next[i] = _first[_highest_active];
1.706 + _first[_highest_active] = i;
1.707 + }
1.708 + }
1.709 +
1.710 + ///Lift the highest active item to the given level.
1.711 +
1.712 + ///Lift the item returned by highestActive() to level \c new_level.
1.713 + ///
1.714 + ///\warning \c new_level must be strictly higher
1.715 + ///than the current level.
1.716 + ///
1.717 + void liftHighestActive(int new_level) {
1.718 + Item i = _first[_highest_active];
1.719 + if (_next[i] != INVALID) {
1.720 + _prev[_next[i]] = INVALID;
1.721 + _first[_highest_active] = _next[i];
1.722 + } else {
1.723 + _first[_highest_active] = INVALID;
1.724 + _last[_highest_active] = INVALID;
1.725 + }
1.726 + _level[i] = _highest_active = new_level;
1.727 + if (_first[_highest_active] == INVALID) {
1.728 + _first[_highest_active] = _last[_highest_active] = i;
1.729 + _prev[i] = INVALID;
1.730 + _next[i] = INVALID;
1.731 + } else {
1.732 + _prev[_first[_highest_active]] = i;
1.733 + _next[i] = _first[_highest_active];
1.734 + _first[_highest_active] = i;
1.735 + }
1.736 + }
1.737 +
1.738 + ///Lift the highest active item to the top level.
1.739 +
1.740 + ///Lift the item returned by highestActive() to the top level and
1.741 + ///deactivate it.
1.742 + void liftHighestActiveToTop() {
1.743 + Item i = _first[_highest_active];
1.744 + _level[i] = _max_level;
1.745 + if (_next[i] != INVALID) {
1.746 + _prev[_next[i]] = INVALID;
1.747 + _first[_highest_active] = _next[i];
1.748 + } else {
1.749 + _first[_highest_active] = INVALID;
1.750 + _last[_highest_active] = INVALID;
1.751 + }
1.752 + while (_highest_active >= 0 && activeFree(_highest_active))
1.753 + --_highest_active;
1.754 + }
1.755 +
1.756 + ///@}
1.757 +
1.758 + ///\name Active Item on Certain Level
1.759 + ///Functions for working with the active items.
1.760 +
1.761 + ///@{
1.762 +
1.763 + ///Return an active item on level \c l.
1.764 +
1.765 + ///Return an active item on level \c l or \ref INVALID if there is no such
1.766 + ///an item. (\c l must be from the range [0...\c max_level].
1.767 + Item activeOn(int l) const
1.768 + {
1.769 + return _active[_first[l]] ? _first[l] : INVALID;
1.770 + }
1.771 +
1.772 + ///Lift the active item returned by \c activeOn(l) by one.
1.773 +
1.774 + ///Lift the active item returned by \ref activeOn() "activeOn(l)"
1.775 + ///by one.
1.776 + Item liftActiveOn(int l)
1.777 + {
1.778 + Item i = _first[l];
1.779 + if (_next[i] != INVALID) {
1.780 + _prev[_next[i]] = INVALID;
1.781 + _first[l] = _next[i];
1.782 + } else {
1.783 + _first[l] = INVALID;
1.784 + _last[l] = INVALID;
1.785 + }
1.786 + _level[i] = ++l;
1.787 + if (_first[l] == INVALID) {
1.788 + _first[l] = _last[l] = i;
1.789 + _prev[i] = INVALID;
1.790 + _next[i] = INVALID;
1.791 + } else {
1.792 + _prev[_first[l]] = i;
1.793 + _next[i] = _first[l];
1.794 + _first[l] = i;
1.795 + }
1.796 + if (_highest_active < l) {
1.797 + _highest_active = l;
1.798 + }
1.799 + }
1.800 +
1.801 + ///Lift the active item returned by \c activeOn(l) to the given level.
1.802 +
1.803 + ///Lift the active item returned by \ref activeOn() "activeOn(l)"
1.804 + ///to the given level.
1.805 + void liftActiveOn(int l, int new_level)
1.806 + {
1.807 + Item i = _first[l];
1.808 + if (_next[i] != INVALID) {
1.809 + _prev[_next[i]] = INVALID;
1.810 + _first[l] = _next[i];
1.811 + } else {
1.812 + _first[l] = INVALID;
1.813 + _last[l] = INVALID;
1.814 + }
1.815 + _level[i] = l = new_level;
1.816 + if (_first[l] == INVALID) {
1.817 + _first[l] = _last[l] = i;
1.818 + _prev[i] = INVALID;
1.819 + _next[i] = INVALID;
1.820 + } else {
1.821 + _prev[_first[l]] = i;
1.822 + _next[i] = _first[l];
1.823 + _first[l] = i;
1.824 + }
1.825 + if (_highest_active < l) {
1.826 + _highest_active = l;
1.827 + }
1.828 + }
1.829 +
1.830 + ///Lift the active item returned by \c activeOn(l) to the top level.
1.831 +
1.832 + ///Lift the active item returned by \ref activeOn() "activeOn(l)"
1.833 + ///to the top level and deactivate it.
1.834 + void liftActiveToTop(int l)
1.835 + {
1.836 + Item i = _first[l];
1.837 + if (_next[i] != INVALID) {
1.838 + _prev[_next[i]] = INVALID;
1.839 + _first[l] = _next[i];
1.840 + } else {
1.841 + _first[l] = INVALID;
1.842 + _last[l] = INVALID;
1.843 + }
1.844 + _level[i] = _max_level;
1.845 + if (l == _highest_active) {
1.846 + while (_highest_active >= 0 && activeFree(_highest_active))
1.847 + --_highest_active;
1.848 + }
1.849 + }
1.850 +
1.851 + ///@}
1.852 +
1.853 + /// \brief Lift an active item to a higher level.
1.854 + ///
1.855 + /// Lift an active item to a higher level.
1.856 + /// \param i The item to be lifted. It must be active.
1.857 + /// \param new_level The new level of \c i. It must be strictly higher
1.858 + /// than the current level.
1.859 + ///
1.860 + void lift(Item i, int new_level) {
1.861 + if (_next[i] != INVALID) {
1.862 + _prev[_next[i]] = _prev[i];
1.863 + } else {
1.864 + _last[new_level] = _prev[i];
1.865 + }
1.866 + if (_prev[i] != INVALID) {
1.867 + _next[_prev[i]] = _next[i];
1.868 + } else {
1.869 + _first[new_level] = _next[i];
1.870 + }
1.871 + _level[i] = new_level;
1.872 + if (_first[new_level] == INVALID) {
1.873 + _first[new_level] = _last[new_level] = i;
1.874 + _prev[i] = INVALID;
1.875 + _next[i] = INVALID;
1.876 + } else {
1.877 + _prev[_first[new_level]] = i;
1.878 + _next[i] = _first[new_level];
1.879 + _first[new_level] = i;
1.880 + }
1.881 + if (_highest_active < new_level) {
1.882 + _highest_active = new_level;
1.883 + }
1.884 + }
1.885 +
1.886 + ///Move an inactive item to the top but one level (in a dirty way).
1.887 +
1.888 + ///This function moves an inactive item from the top level to the top
1.889 + ///but one level (in a dirty way).
1.890 + ///\warning It makes the underlying datastructure corrupt, so use it
1.891 + ///only if you really know what it is for.
1.892 + ///\pre The item is on the top level.
1.893 + void dirtyTopButOne(Item i) {
1.894 + _level[i] = _max_level - 1;
1.895 + }
1.896 +
1.897 + ///Lift all items on and above the given level to the top level.
1.898 +
1.899 + ///This function lifts all items on and above level \c l to the top
1.900 + ///level and deactivates them.
1.901 + void liftToTop(int l) {
1.902 + for (int i = l + 1; _first[i] != INVALID; ++i) {
1.903 + Item n = _first[i];
1.904 + while (n != INVALID) {
1.905 + _level[n] = _max_level;
1.906 + n = _next[n];
1.907 + }
1.908 + _first[i] = INVALID;
1.909 + _last[i] = INVALID;
1.910 + }
1.911 + if (_highest_active > l - 1) {
1.912 + _highest_active = l - 1;
1.913 + while (_highest_active >= 0 && activeFree(_highest_active))
1.914 + --_highest_active;
1.915 + }
1.916 + }
1.917 +
1.918 + private:
1.919 +
1.920 + int _init_level;
1.921 +
1.922 + public:
1.923 +
1.924 + ///\name Initialization
1.925 + ///Using these functions you can initialize the levels of the items.
1.926 + ///\n
1.927 + ///The initialization must be started with calling \c initStart().
1.928 + ///Then the items should be listed level by level starting with the
1.929 + ///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
1.930 + ///Finally \c initFinish() must be called.
1.931 + ///The items not listed are put on the highest level.
1.932 + ///@{
1.933 +
1.934 + ///Start the initialization process.
1.935 + void initStart() {
1.936 +
1.937 + for (int i = 0; i <= _max_level; ++i) {
1.938 + _first[i] = _last[i] = INVALID;
1.939 + }
1.940 + _init_level = 0;
1.941 + for(typename ItemSetTraits<GR,Item>::ItemIt i(_graph);
1.942 + i != INVALID; ++i) {
1.943 + _level[i] = _max_level;
1.944 + _active[i] = false;
1.945 + }
1.946 + }
1.947 +
1.948 + ///Add an item to the current level.
1.949 + void initAddItem(Item i) {
1.950 + _level[i] = _init_level;
1.951 + if (_last[_init_level] == INVALID) {
1.952 + _first[_init_level] = i;
1.953 + _last[_init_level] = i;
1.954 + _prev[i] = INVALID;
1.955 + _next[i] = INVALID;
1.956 + } else {
1.957 + _prev[i] = _last[_init_level];
1.958 + _next[i] = INVALID;
1.959 + _next[_last[_init_level]] = i;
1.960 + _last[_init_level] = i;
1.961 + }
1.962 + }
1.963 +
1.964 + ///Start a new level.
1.965 +
1.966 + ///Start a new level.
1.967 + ///It shouldn't be used before the items on level 0 are listed.
1.968 + void initNewLevel() {
1.969 + ++_init_level;
1.970 + }
1.971 +
1.972 + ///Finalize the initialization process.
1.973 + void initFinish() {
1.974 + _highest_active = -1;
1.975 + }
1.976 +
1.977 + ///@}
1.978 +
1.979 + };
1.980 +
1.981 +
1.982 +} //END OF NAMESPACE LEMON
1.983 +
1.984 +#endif
1.985 +