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