1.1 --- a/lemon/Makefile.am Tue Nov 11 10:25:57 2008 +0000
1.2 +++ b/lemon/Makefile.am Fri Nov 21 10:49:39 2008 +0000
1.3 @@ -27,6 +27,7 @@
1.4 lemon/dfs.h \
1.5 lemon/dijkstra.h \
1.6 lemon/dim2.h \
1.7 + lemon/elevator.h \
1.8 lemon/error.h \
1.9 lemon/full_graph.h \
1.10 lemon/graph_to_eps.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/elevator.h Fri Nov 21 10:49:39 2008 +0000
2.3 @@ -0,0 +1,981 @@
2.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library.
2.7 + *
2.8 + * Copyright (C) 2003-2008
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +#ifndef LEMON_ELEVATOR_H
2.23 +#define LEMON_ELEVATOR_H
2.24 +
2.25 +///\ingroup auxdat
2.26 +///\file
2.27 +///\brief Elevator class
2.28 +///
2.29 +///Elevator class implements an efficient data structure
2.30 +///for labeling items in push-relabel type algorithms.
2.31 +///
2.32 +
2.33 +#include <lemon/bits/traits.h>
2.34 +
2.35 +namespace lemon {
2.36 +
2.37 + ///Class for handling "labels" in push-relabel type algorithms.
2.38 +
2.39 + ///A class for handling "labels" in push-relabel type algorithms.
2.40 + ///
2.41 + ///\ingroup auxdat
2.42 + ///Using this class you can assign "labels" (nonnegative integer numbers)
2.43 + ///to the edges or nodes of a graph, manipulate and query them through
2.44 + ///operations typically arising in "push-relabel" type algorithms.
2.45 + ///
2.46 + ///Each item is either \em active or not, and you can also choose a
2.47 + ///highest level active item.
2.48 + ///
2.49 + ///\sa LinkedElevator
2.50 + ///
2.51 + ///\param Graph Type of the underlying graph.
2.52 + ///\param Item Type of the items the data is assigned to (Graph::Node,
2.53 + ///Graph::Arc, Graph::Edge).
2.54 + template<class Graph, class Item>
2.55 + class Elevator
2.56 + {
2.57 + public:
2.58 +
2.59 + typedef Item Key;
2.60 + typedef int Value;
2.61 +
2.62 + private:
2.63 +
2.64 + typedef Item *Vit;
2.65 + typedef typename ItemSetTraits<Graph,Item>::template Map<Vit>::Type VitMap;
2.66 + typedef typename ItemSetTraits<Graph,Item>::template Map<int>::Type IntMap;
2.67 +
2.68 + const Graph &_g;
2.69 + int _max_level;
2.70 + int _item_num;
2.71 + VitMap _where;
2.72 + IntMap _level;
2.73 + std::vector<Item> _items;
2.74 + std::vector<Vit> _first;
2.75 + std::vector<Vit> _last_active;
2.76 +
2.77 + int _highest_active;
2.78 +
2.79 + void copy(Item i, Vit p)
2.80 + {
2.81 + _where.set(*p=i,p);
2.82 + }
2.83 + void copy(Vit s, Vit p)
2.84 + {
2.85 + if(s!=p)
2.86 + {
2.87 + Item i=*s;
2.88 + *p=i;
2.89 + _where.set(i,p);
2.90 + }
2.91 + }
2.92 + void swap(Vit i, Vit j)
2.93 + {
2.94 + Item ti=*i;
2.95 + Vit ct = _where[ti];
2.96 + _where.set(ti,_where[*i=*j]);
2.97 + _where.set(*j,ct);
2.98 + *j=ti;
2.99 + }
2.100 +
2.101 + public:
2.102 +
2.103 + ///Constructor with given maximum level.
2.104 +
2.105 + ///Constructor with given maximum level.
2.106 + ///
2.107 + ///\param graph The underlying graph.
2.108 + ///\param max_level The maximum allowed level.
2.109 + ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
2.110 + Elevator(const Graph &graph,int max_level) :
2.111 + _g(graph),
2.112 + _max_level(max_level),
2.113 + _item_num(_max_level),
2.114 + _where(graph),
2.115 + _level(graph,0),
2.116 + _items(_max_level),
2.117 + _first(_max_level+2),
2.118 + _last_active(_max_level+2),
2.119 + _highest_active(-1) {}
2.120 + ///Constructor.
2.121 +
2.122 + ///Constructor.
2.123 + ///
2.124 + ///\param graph The underlying graph.
2.125 + ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
2.126 + ///where \c max_level is equal to the number of labeled items in the graph.
2.127 + Elevator(const Graph &graph) :
2.128 + _g(graph),
2.129 + _max_level(countItems<Graph, Item>(graph)),
2.130 + _item_num(_max_level),
2.131 + _where(graph),
2.132 + _level(graph,0),
2.133 + _items(_max_level),
2.134 + _first(_max_level+2),
2.135 + _last_active(_max_level+2),
2.136 + _highest_active(-1)
2.137 + {
2.138 + }
2.139 +
2.140 + ///Activate item \c i.
2.141 +
2.142 + ///Activate item \c i.
2.143 + ///\pre Item \c i shouldn't be active before.
2.144 + void activate(Item i)
2.145 + {
2.146 + const int l=_level[i];
2.147 + swap(_where[i],++_last_active[l]);
2.148 + if(l>_highest_active) _highest_active=l;
2.149 + }
2.150 +
2.151 + ///Deactivate item \c i.
2.152 +
2.153 + ///Deactivate item \c i.
2.154 + ///\pre Item \c i must be active before.
2.155 + void deactivate(Item i)
2.156 + {
2.157 + swap(_where[i],_last_active[_level[i]]--);
2.158 + while(_highest_active>=0 &&
2.159 + _last_active[_highest_active]<_first[_highest_active])
2.160 + _highest_active--;
2.161 + }
2.162 +
2.163 + ///Query whether item \c i is active
2.164 + bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
2.165 +
2.166 + ///Return the level of item \c i.
2.167 + int operator[](Item i) const { return _level[i]; }
2.168 +
2.169 + ///Return the number of items on level \c l.
2.170 + int onLevel(int l) const
2.171 + {
2.172 + return _first[l+1]-_first[l];
2.173 + }
2.174 + ///Return true if level \c l is empty.
2.175 + bool emptyLevel(int l) const
2.176 + {
2.177 + return _first[l+1]-_first[l]==0;
2.178 + }
2.179 + ///Return the number of items above level \c l.
2.180 + int aboveLevel(int l) const
2.181 + {
2.182 + return _first[_max_level+1]-_first[l+1];
2.183 + }
2.184 + ///Return the number of active items on level \c l.
2.185 + int activesOnLevel(int l) const
2.186 + {
2.187 + return _last_active[l]-_first[l]+1;
2.188 + }
2.189 + ///Return true if there is no active item on level \c l.
2.190 + bool activeFree(int l) const
2.191 + {
2.192 + return _last_active[l]<_first[l];
2.193 + }
2.194 + ///Return the maximum allowed level.
2.195 + int maxLevel() const
2.196 + {
2.197 + return _max_level;
2.198 + }
2.199 +
2.200 + ///\name Highest Active Item
2.201 + ///Functions for working with the highest level
2.202 + ///active item.
2.203 +
2.204 + ///@{
2.205 +
2.206 + ///Return a highest level active item.
2.207 +
2.208 + ///Return a highest level active item or INVALID if there is no active
2.209 + ///item.
2.210 + Item highestActive() const
2.211 + {
2.212 + return _highest_active>=0?*_last_active[_highest_active]:INVALID;
2.213 + }
2.214 +
2.215 + ///Return the highest active level.
2.216 +
2.217 + ///Return the level of the highest active item or -1 if there is no active
2.218 + ///item.
2.219 + int highestActiveLevel() const
2.220 + {
2.221 + return _highest_active;
2.222 + }
2.223 +
2.224 + ///Lift the highest active item by one.
2.225 +
2.226 + ///Lift the item returned by highestActive() by one.
2.227 + ///
2.228 + void liftHighestActive()
2.229 + {
2.230 + Item it = *_last_active[_highest_active];
2.231 + _level.set(it,_level[it]+1);
2.232 + swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
2.233 + --_first[++_highest_active];
2.234 + }
2.235 +
2.236 + ///Lift the highest active item to the given level.
2.237 +
2.238 + ///Lift the item returned by highestActive() to level \c new_level.
2.239 + ///
2.240 + ///\warning \c new_level must be strictly higher
2.241 + ///than the current level.
2.242 + ///
2.243 + void liftHighestActive(int new_level)
2.244 + {
2.245 + const Item li = *_last_active[_highest_active];
2.246 +
2.247 + copy(--_first[_highest_active+1],_last_active[_highest_active]--);
2.248 + for(int l=_highest_active+1;l<new_level;l++)
2.249 + {
2.250 + copy(--_first[l+1],_first[l]);
2.251 + --_last_active[l];
2.252 + }
2.253 + copy(li,_first[new_level]);
2.254 + _level.set(li,new_level);
2.255 + _highest_active=new_level;
2.256 + }
2.257 +
2.258 + ///Lift the highest active item to the top level.
2.259 +
2.260 + ///Lift the item returned by highestActive() to the top level and
2.261 + ///deactivate it.
2.262 + void liftHighestActiveToTop()
2.263 + {
2.264 + const Item li = *_last_active[_highest_active];
2.265 +
2.266 + copy(--_first[_highest_active+1],_last_active[_highest_active]--);
2.267 + for(int l=_highest_active+1;l<_max_level;l++)
2.268 + {
2.269 + copy(--_first[l+1],_first[l]);
2.270 + --_last_active[l];
2.271 + }
2.272 + copy(li,_first[_max_level]);
2.273 + --_last_active[_max_level];
2.274 + _level.set(li,_max_level);
2.275 +
2.276 + while(_highest_active>=0 &&
2.277 + _last_active[_highest_active]<_first[_highest_active])
2.278 + _highest_active--;
2.279 + }
2.280 +
2.281 + ///@}
2.282 +
2.283 + ///\name Active Item on Certain Level
2.284 + ///Functions for working with the active items.
2.285 +
2.286 + ///@{
2.287 +
2.288 + ///Return an active item on level \c l.
2.289 +
2.290 + ///Return an active item on level \c l or \ref INVALID if there is no such
2.291 + ///an item. (\c l must be from the range [0...\c max_level].
2.292 + Item activeOn(int l) const
2.293 + {
2.294 + return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
2.295 + }
2.296 +
2.297 + ///Lift the active item returned by \c activeOn(level) by one.
2.298 +
2.299 + ///Lift the active item returned by \ref activeOn() "activeOn(level)"
2.300 + ///by one.
2.301 + Item liftActiveOn(int level)
2.302 + {
2.303 + Item it =*_last_active[level];
2.304 + _level.set(it,_level[it]+1);
2.305 + swap(_last_active[level]--, --_first[level+1]);
2.306 + if (level+1>_highest_active) ++_highest_active;
2.307 + }
2.308 +
2.309 + ///Lift the active item returned by \c activeOn(level) to the given level.
2.310 +
2.311 + ///Lift the active item returned by \ref activeOn() "activeOn(level)"
2.312 + ///to the given level.
2.313 + void liftActiveOn(int level, int new_level)
2.314 + {
2.315 + const Item ai = *_last_active[level];
2.316 +
2.317 + copy(--_first[level+1], _last_active[level]--);
2.318 + for(int l=level+1;l<new_level;l++)
2.319 + {
2.320 + copy(_last_active[l],_first[l]);
2.321 + copy(--_first[l+1], _last_active[l]--);
2.322 + }
2.323 + copy(ai,_first[new_level]);
2.324 + _level.set(ai,new_level);
2.325 + if (new_level>_highest_active) _highest_active=new_level;
2.326 + }
2.327 +
2.328 + ///Lift the active item returned by \c activeOn(level) to the top level.
2.329 +
2.330 + ///Lift the active item returned by \ref activeOn() "activeOn(level)"
2.331 + ///to the top level and deactivate it.
2.332 + void liftActiveToTop(int level)
2.333 + {
2.334 + const Item ai = *_last_active[level];
2.335 +
2.336 + copy(--_first[level+1],_last_active[level]--);
2.337 + for(int l=level+1;l<_max_level;l++)
2.338 + {
2.339 + copy(_last_active[l],_first[l]);
2.340 + copy(--_first[l+1], _last_active[l]--);
2.341 + }
2.342 + copy(ai,_first[_max_level]);
2.343 + --_last_active[_max_level];
2.344 + _level.set(ai,_max_level);
2.345 +
2.346 + if (_highest_active==level) {
2.347 + while(_highest_active>=0 &&
2.348 + _last_active[_highest_active]<_first[_highest_active])
2.349 + _highest_active--;
2.350 + }
2.351 + }
2.352 +
2.353 + ///@}
2.354 +
2.355 + ///Lift an active item to a higher level.
2.356 +
2.357 + ///Lift an active item to a higher level.
2.358 + ///\param i The item to be lifted. It must be active.
2.359 + ///\param new_level The new level of \c i. It must be strictly higher
2.360 + ///than the current level.
2.361 + ///
2.362 + void lift(Item i, int new_level)
2.363 + {
2.364 + const int lo = _level[i];
2.365 + const Vit w = _where[i];
2.366 +
2.367 + copy(_last_active[lo],w);
2.368 + copy(--_first[lo+1],_last_active[lo]--);
2.369 + for(int l=lo+1;l<new_level;l++)
2.370 + {
2.371 + copy(_last_active[l],_first[l]);
2.372 + copy(--_first[l+1],_last_active[l]--);
2.373 + }
2.374 + copy(i,_first[new_level]);
2.375 + _level.set(i,new_level);
2.376 + if(new_level>_highest_active) _highest_active=new_level;
2.377 + }
2.378 +
2.379 + ///Move an inactive item to the top but one level (in a dirty way).
2.380 +
2.381 + ///This function moves an inactive item from the top level to the top
2.382 + ///but one level (in a dirty way).
2.383 + ///\warning It makes the underlying datastructure corrupt, so use it
2.384 + ///only if you really know what it is for.
2.385 + ///\pre The item is on the top level.
2.386 + void dirtyTopButOne(Item i) {
2.387 + _level.set(i,_max_level - 1);
2.388 + }
2.389 +
2.390 + ///Lift all items on and above the given level to the top level.
2.391 +
2.392 + ///This function lifts all items on and above level \c l to the top
2.393 + ///level and deactivates them.
2.394 + void liftToTop(int l)
2.395 + {
2.396 + const Vit f=_first[l];
2.397 + const Vit tl=_first[_max_level];
2.398 + for(Vit i=f;i!=tl;++i)
2.399 + _level.set(*i,_max_level);
2.400 + for(int i=l;i<=_max_level;i++)
2.401 + {
2.402 + _first[i]=f;
2.403 + _last_active[i]=f-1;
2.404 + }
2.405 + for(_highest_active=l-1;
2.406 + _highest_active>=0 &&
2.407 + _last_active[_highest_active]<_first[_highest_active];
2.408 + _highest_active--) ;
2.409 + }
2.410 +
2.411 + private:
2.412 + int _init_lev;
2.413 + Vit _init_num;
2.414 +
2.415 + public:
2.416 +
2.417 + ///\name Initialization
2.418 + ///Using these functions you can initialize the levels of the items.
2.419 + ///\n
2.420 + ///The initialization must be started with calling \c initStart().
2.421 + ///Then the items should be listed level by level starting with the
2.422 + ///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
2.423 + ///Finally \c initFinish() must be called.
2.424 + ///The items not listed are put on the highest level.
2.425 + ///@{
2.426 +
2.427 + ///Start the initialization process.
2.428 + void initStart()
2.429 + {
2.430 + _init_lev=0;
2.431 + _init_num=&_items[0];
2.432 + _first[0]=&_items[0];
2.433 + _last_active[0]=&_items[0]-1;
2.434 + Vit n=&_items[0];
2.435 + for(typename ItemSetTraits<Graph,Item>::ItemIt i(_g);i!=INVALID;++i)
2.436 + {
2.437 + *n=i;
2.438 + _where.set(i,n);
2.439 + _level.set(i,_max_level);
2.440 + ++n;
2.441 + }
2.442 + }
2.443 +
2.444 + ///Add an item to the current level.
2.445 + void initAddItem(Item i)
2.446 + {
2.447 + swap(_where[i],_init_num);
2.448 + _level.set(i,_init_lev);
2.449 + ++_init_num;
2.450 + }
2.451 +
2.452 + ///Start a new level.
2.453 +
2.454 + ///Start a new level.
2.455 + ///It shouldn't be used before the items on level 0 are listed.
2.456 + void initNewLevel()
2.457 + {
2.458 + _init_lev++;
2.459 + _first[_init_lev]=_init_num;
2.460 + _last_active[_init_lev]=_init_num-1;
2.461 + }
2.462 +
2.463 + ///Finalize the initialization process.
2.464 + void initFinish()
2.465 + {
2.466 + for(_init_lev++;_init_lev<=_max_level;_init_lev++)
2.467 + {
2.468 + _first[_init_lev]=_init_num;
2.469 + _last_active[_init_lev]=_init_num-1;
2.470 + }
2.471 + _first[_max_level+1]=&_items[0]+_item_num;
2.472 + _last_active[_max_level+1]=&_items[0]+_item_num-1;
2.473 + _highest_active = -1;
2.474 + }
2.475 +
2.476 + ///@}
2.477 +
2.478 + };
2.479 +
2.480 + ///Class for handling "labels" in push-relabel type algorithms.
2.481 +
2.482 + ///A class for handling "labels" in push-relabel type algorithms.
2.483 + ///
2.484 + ///\ingroup auxdat
2.485 + ///Using this class you can assign "labels" (nonnegative integer numbers)
2.486 + ///to the edges or nodes of a graph, manipulate and query them through
2.487 + ///operations typically arising in "push-relabel" type algorithms.
2.488 + ///
2.489 + ///Each item is either \em active or not, and you can also choose a
2.490 + ///highest level active item.
2.491 + ///
2.492 + ///\sa Elevator
2.493 + ///
2.494 + ///\param Graph Type of the underlying graph.
2.495 + ///\param Item Type of the items the data is assigned to (Graph::Node,
2.496 + ///Graph::Arc, Graph::Edge).
2.497 + template <class Graph, class Item>
2.498 + class LinkedElevator {
2.499 + public:
2.500 +
2.501 + typedef Item Key;
2.502 + typedef int Value;
2.503 +
2.504 + private:
2.505 +
2.506 + typedef typename ItemSetTraits<Graph,Item>::
2.507 + template Map<Item>::Type ItemMap;
2.508 + typedef typename ItemSetTraits<Graph,Item>::
2.509 + template Map<int>::Type IntMap;
2.510 + typedef typename ItemSetTraits<Graph,Item>::
2.511 + template Map<bool>::Type BoolMap;
2.512 +
2.513 + const Graph &_graph;
2.514 + int _max_level;
2.515 + int _item_num;
2.516 + std::vector<Item> _first, _last;
2.517 + ItemMap _prev, _next;
2.518 + int _highest_active;
2.519 + IntMap _level;
2.520 + BoolMap _active;
2.521 +
2.522 + public:
2.523 + ///Constructor with given maximum level.
2.524 +
2.525 + ///Constructor with given maximum level.
2.526 + ///
2.527 + ///\param graph The underlying graph.
2.528 + ///\param max_level The maximum allowed level.
2.529 + ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
2.530 + LinkedElevator(const Graph& graph, int max_level)
2.531 + : _graph(graph), _max_level(max_level), _item_num(_max_level),
2.532 + _first(_max_level + 1), _last(_max_level + 1),
2.533 + _prev(graph), _next(graph),
2.534 + _highest_active(-1), _level(graph), _active(graph) {}
2.535 +
2.536 + ///Constructor.
2.537 +
2.538 + ///Constructor.
2.539 + ///
2.540 + ///\param graph The underlying graph.
2.541 + ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
2.542 + ///where \c max_level is equal to the number of labeled items in the graph.
2.543 + LinkedElevator(const Graph& graph)
2.544 + : _graph(graph), _max_level(countItems<Graph, Item>(graph)),
2.545 + _item_num(_max_level),
2.546 + _first(_max_level + 1), _last(_max_level + 1),
2.547 + _prev(graph, INVALID), _next(graph, INVALID),
2.548 + _highest_active(-1), _level(graph), _active(graph) {}
2.549 +
2.550 +
2.551 + ///Activate item \c i.
2.552 +
2.553 + ///Activate item \c i.
2.554 + ///\pre Item \c i shouldn't be active before.
2.555 + void activate(Item i) {
2.556 + _active.set(i, true);
2.557 +
2.558 + int level = _level[i];
2.559 + if (level > _highest_active) {
2.560 + _highest_active = level;
2.561 + }
2.562 +
2.563 + if (_prev[i] == INVALID || _active[_prev[i]]) return;
2.564 + //unlace
2.565 + _next.set(_prev[i], _next[i]);
2.566 + if (_next[i] != INVALID) {
2.567 + _prev.set(_next[i], _prev[i]);
2.568 + } else {
2.569 + _last[level] = _prev[i];
2.570 + }
2.571 + //lace
2.572 + _next.set(i, _first[level]);
2.573 + _prev.set(_first[level], i);
2.574 + _prev.set(i, INVALID);
2.575 + _first[level] = i;
2.576 +
2.577 + }
2.578 +
2.579 + ///Deactivate item \c i.
2.580 +
2.581 + ///Deactivate item \c i.
2.582 + ///\pre Item \c i must be active before.
2.583 + void deactivate(Item i) {
2.584 + _active.set(i, false);
2.585 + int level = _level[i];
2.586 +
2.587 + if (_next[i] == INVALID || !_active[_next[i]])
2.588 + goto find_highest_level;
2.589 +
2.590 + //unlace
2.591 + _prev.set(_next[i], _prev[i]);
2.592 + if (_prev[i] != INVALID) {
2.593 + _next.set(_prev[i], _next[i]);
2.594 + } else {
2.595 + _first[_level[i]] = _next[i];
2.596 + }
2.597 + //lace
2.598 + _prev.set(i, _last[level]);
2.599 + _next.set(_last[level], i);
2.600 + _next.set(i, INVALID);
2.601 + _last[level] = i;
2.602 +
2.603 + find_highest_level:
2.604 + if (level == _highest_active) {
2.605 + while (_highest_active >= 0 && activeFree(_highest_active))
2.606 + --_highest_active;
2.607 + }
2.608 + }
2.609 +
2.610 + ///Query whether item \c i is active
2.611 + bool active(Item i) const { return _active[i]; }
2.612 +
2.613 + ///Return the level of item \c i.
2.614 + int operator[](Item i) const { return _level[i]; }
2.615 +
2.616 + ///Return the number of items on level \c l.
2.617 + int onLevel(int l) const {
2.618 + int num = 0;
2.619 + Item n = _first[l];
2.620 + while (n != INVALID) {
2.621 + ++num;
2.622 + n = _next[n];
2.623 + }
2.624 + return num;
2.625 + }
2.626 +
2.627 + ///Return true if the level is empty.
2.628 + bool emptyLevel(int l) const {
2.629 + return _first[l] == INVALID;
2.630 + }
2.631 +
2.632 + ///Return the number of items above level \c l.
2.633 + int aboveLevel(int l) const {
2.634 + int num = 0;
2.635 + for (int level = l + 1; level < _max_level; ++level)
2.636 + num += onLevel(level);
2.637 + return num;
2.638 + }
2.639 +
2.640 + ///Return the number of active items on level \c l.
2.641 + int activesOnLevel(int l) const {
2.642 + int num = 0;
2.643 + Item n = _first[l];
2.644 + while (n != INVALID && _active[n]) {
2.645 + ++num;
2.646 + n = _next[n];
2.647 + }
2.648 + return num;
2.649 + }
2.650 +
2.651 + ///Return true if there is no active item on level \c l.
2.652 + bool activeFree(int l) const {
2.653 + return _first[l] == INVALID || !_active[_first[l]];
2.654 + }
2.655 +
2.656 + ///Return the maximum allowed level.
2.657 + int maxLevel() const {
2.658 + return _max_level;
2.659 + }
2.660 +
2.661 + ///\name Highest Active Item
2.662 + ///Functions for working with the highest level
2.663 + ///active item.
2.664 +
2.665 + ///@{
2.666 +
2.667 + ///Return a highest level active item.
2.668 +
2.669 + ///Return a highest level active item or INVALID if there is no active
2.670 + ///item.
2.671 + Item highestActive() const {
2.672 + return _highest_active >= 0 ? _first[_highest_active] : INVALID;
2.673 + }
2.674 +
2.675 + ///Return the highest active level.
2.676 +
2.677 + ///Return the level of the highest active item or -1 if there is no active
2.678 + ///item.
2.679 + int highestActiveLevel() const {
2.680 + return _highest_active;
2.681 + }
2.682 +
2.683 + ///Lift the highest active item by one.
2.684 +
2.685 + ///Lift the item returned by highestActive() by one.
2.686 + ///
2.687 + void liftHighestActive() {
2.688 + Item i = _first[_highest_active];
2.689 + if (_next[i] != INVALID) {
2.690 + _prev.set(_next[i], INVALID);
2.691 + _first[_highest_active] = _next[i];
2.692 + } else {
2.693 + _first[_highest_active] = INVALID;
2.694 + _last[_highest_active] = INVALID;
2.695 + }
2.696 + _level.set(i, ++_highest_active);
2.697 + if (_first[_highest_active] == INVALID) {
2.698 + _first[_highest_active] = i;
2.699 + _last[_highest_active] = i;
2.700 + _prev.set(i, INVALID);
2.701 + _next.set(i, INVALID);
2.702 + } else {
2.703 + _prev.set(_first[_highest_active], i);
2.704 + _next.set(i, _first[_highest_active]);
2.705 + _first[_highest_active] = i;
2.706 + }
2.707 + }
2.708 +
2.709 + ///Lift the highest active item to the given level.
2.710 +
2.711 + ///Lift the item returned by highestActive() to level \c new_level.
2.712 + ///
2.713 + ///\warning \c new_level must be strictly higher
2.714 + ///than the current level.
2.715 + ///
2.716 + void liftHighestActive(int new_level) {
2.717 + Item i = _first[_highest_active];
2.718 + if (_next[i] != INVALID) {
2.719 + _prev.set(_next[i], INVALID);
2.720 + _first[_highest_active] = _next[i];
2.721 + } else {
2.722 + _first[_highest_active] = INVALID;
2.723 + _last[_highest_active] = INVALID;
2.724 + }
2.725 + _level.set(i, _highest_active = new_level);
2.726 + if (_first[_highest_active] == INVALID) {
2.727 + _first[_highest_active] = _last[_highest_active] = i;
2.728 + _prev.set(i, INVALID);
2.729 + _next.set(i, INVALID);
2.730 + } else {
2.731 + _prev.set(_first[_highest_active], i);
2.732 + _next.set(i, _first[_highest_active]);
2.733 + _first[_highest_active] = i;
2.734 + }
2.735 + }
2.736 +
2.737 + ///Lift the highest active item to the top level.
2.738 +
2.739 + ///Lift the item returned by highestActive() to the top level and
2.740 + ///deactivate it.
2.741 + void liftHighestActiveToTop() {
2.742 + Item i = _first[_highest_active];
2.743 + _level.set(i, _max_level);
2.744 + if (_next[i] != INVALID) {
2.745 + _prev.set(_next[i], INVALID);
2.746 + _first[_highest_active] = _next[i];
2.747 + } else {
2.748 + _first[_highest_active] = INVALID;
2.749 + _last[_highest_active] = INVALID;
2.750 + }
2.751 + while (_highest_active >= 0 && activeFree(_highest_active))
2.752 + --_highest_active;
2.753 + }
2.754 +
2.755 + ///@}
2.756 +
2.757 + ///\name Active Item on Certain Level
2.758 + ///Functions for working with the active items.
2.759 +
2.760 + ///@{
2.761 +
2.762 + ///Return an active item on level \c l.
2.763 +
2.764 + ///Return an active item on level \c l or \ref INVALID if there is no such
2.765 + ///an item. (\c l must be from the range [0...\c max_level].
2.766 + Item activeOn(int l) const
2.767 + {
2.768 + return _active[_first[l]] ? _first[l] : INVALID;
2.769 + }
2.770 +
2.771 + ///Lift the active item returned by \c activeOn(l) by one.
2.772 +
2.773 + ///Lift the active item returned by \ref activeOn() "activeOn(l)"
2.774 + ///by one.
2.775 + Item liftActiveOn(int l)
2.776 + {
2.777 + Item i = _first[l];
2.778 + if (_next[i] != INVALID) {
2.779 + _prev.set(_next[i], INVALID);
2.780 + _first[l] = _next[i];
2.781 + } else {
2.782 + _first[l] = INVALID;
2.783 + _last[l] = INVALID;
2.784 + }
2.785 + _level.set(i, ++l);
2.786 + if (_first[l] == INVALID) {
2.787 + _first[l] = _last[l] = i;
2.788 + _prev.set(i, INVALID);
2.789 + _next.set(i, INVALID);
2.790 + } else {
2.791 + _prev.set(_first[l], i);
2.792 + _next.set(i, _first[l]);
2.793 + _first[l] = i;
2.794 + }
2.795 + if (_highest_active < l) {
2.796 + _highest_active = l;
2.797 + }
2.798 + }
2.799 +
2.800 + ///Lift the active item returned by \c activeOn(l) to the given level.
2.801 +
2.802 + ///Lift the active item returned by \ref activeOn() "activeOn(l)"
2.803 + ///to the given level.
2.804 + void liftActiveOn(int l, int new_level)
2.805 + {
2.806 + Item i = _first[l];
2.807 + if (_next[i] != INVALID) {
2.808 + _prev.set(_next[i], INVALID);
2.809 + _first[l] = _next[i];
2.810 + } else {
2.811 + _first[l] = INVALID;
2.812 + _last[l] = INVALID;
2.813 + }
2.814 + _level.set(i, l = new_level);
2.815 + if (_first[l] == INVALID) {
2.816 + _first[l] = _last[l] = i;
2.817 + _prev.set(i, INVALID);
2.818 + _next.set(i, INVALID);
2.819 + } else {
2.820 + _prev.set(_first[l], i);
2.821 + _next.set(i, _first[l]);
2.822 + _first[l] = i;
2.823 + }
2.824 + if (_highest_active < l) {
2.825 + _highest_active = l;
2.826 + }
2.827 + }
2.828 +
2.829 + ///Lift the active item returned by \c activeOn(l) to the top level.
2.830 +
2.831 + ///Lift the active item returned by \ref activeOn() "activeOn(l)"
2.832 + ///to the top level and deactivate it.
2.833 + void liftActiveToTop(int l)
2.834 + {
2.835 + Item i = _first[l];
2.836 + if (_next[i] != INVALID) {
2.837 + _prev.set(_next[i], INVALID);
2.838 + _first[l] = _next[i];
2.839 + } else {
2.840 + _first[l] = INVALID;
2.841 + _last[l] = INVALID;
2.842 + }
2.843 + _level.set(i, _max_level);
2.844 + if (l == _highest_active) {
2.845 + while (_highest_active >= 0 && activeFree(_highest_active))
2.846 + --_highest_active;
2.847 + }
2.848 + }
2.849 +
2.850 + ///@}
2.851 +
2.852 + /// \brief Lift an active item to a higher level.
2.853 + ///
2.854 + /// Lift an active item to a higher level.
2.855 + /// \param i The item to be lifted. It must be active.
2.856 + /// \param new_level The new level of \c i. It must be strictly higher
2.857 + /// than the current level.
2.858 + ///
2.859 + void lift(Item i, int new_level) {
2.860 + if (_next[i] != INVALID) {
2.861 + _prev.set(_next[i], _prev[i]);
2.862 + } else {
2.863 + _last[new_level] = _prev[i];
2.864 + }
2.865 + if (_prev[i] != INVALID) {
2.866 + _next.set(_prev[i], _next[i]);
2.867 + } else {
2.868 + _first[new_level] = _next[i];
2.869 + }
2.870 + _level.set(i, new_level);
2.871 + if (_first[new_level] == INVALID) {
2.872 + _first[new_level] = _last[new_level] = i;
2.873 + _prev.set(i, INVALID);
2.874 + _next.set(i, INVALID);
2.875 + } else {
2.876 + _prev.set(_first[new_level], i);
2.877 + _next.set(i, _first[new_level]);
2.878 + _first[new_level] = i;
2.879 + }
2.880 + if (_highest_active < new_level) {
2.881 + _highest_active = new_level;
2.882 + }
2.883 + }
2.884 +
2.885 + ///Move an inactive item to the top but one level (in a dirty way).
2.886 +
2.887 + ///This function moves an inactive item from the top level to the top
2.888 + ///but one level (in a dirty way).
2.889 + ///\warning It makes the underlying datastructure corrupt, so use it
2.890 + ///only if you really know what it is for.
2.891 + ///\pre The item is on the top level.
2.892 + void dirtyTopButOne(Item i) {
2.893 + _level.set(i, _max_level - 1);
2.894 + }
2.895 +
2.896 + ///Lift all items on and above the given level to the top level.
2.897 +
2.898 + ///This function lifts all items on and above level \c l to the top
2.899 + ///level and deactivates them.
2.900 + void liftToTop(int l) {
2.901 + for (int i = l + 1; _first[i] != INVALID; ++i) {
2.902 + Item n = _first[i];
2.903 + while (n != INVALID) {
2.904 + _level.set(n, _max_level);
2.905 + n = _next[n];
2.906 + }
2.907 + _first[i] = INVALID;
2.908 + _last[i] = INVALID;
2.909 + }
2.910 + if (_highest_active > l - 1) {
2.911 + _highest_active = l - 1;
2.912 + while (_highest_active >= 0 && activeFree(_highest_active))
2.913 + --_highest_active;
2.914 + }
2.915 + }
2.916 +
2.917 + private:
2.918 +
2.919 + int _init_level;
2.920 +
2.921 + public:
2.922 +
2.923 + ///\name Initialization
2.924 + ///Using these functions you can initialize the levels of the items.
2.925 + ///\n
2.926 + ///The initialization must be started with calling \c initStart().
2.927 + ///Then the items should be listed level by level starting with the
2.928 + ///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
2.929 + ///Finally \c initFinish() must be called.
2.930 + ///The items not listed are put on the highest level.
2.931 + ///@{
2.932 +
2.933 + ///Start the initialization process.
2.934 + void initStart() {
2.935 +
2.936 + for (int i = 0; i <= _max_level; ++i) {
2.937 + _first[i] = _last[i] = INVALID;
2.938 + }
2.939 + _init_level = 0;
2.940 + for(typename ItemSetTraits<Graph,Item>::ItemIt i(_graph);
2.941 + i != INVALID; ++i) {
2.942 + _level.set(i, _max_level);
2.943 + _active.set(i, false);
2.944 + }
2.945 + }
2.946 +
2.947 + ///Add an item to the current level.
2.948 + void initAddItem(Item i) {
2.949 + _level.set(i, _init_level);
2.950 + if (_last[_init_level] == INVALID) {
2.951 + _first[_init_level] = i;
2.952 + _last[_init_level] = i;
2.953 + _prev.set(i, INVALID);
2.954 + _next.set(i, INVALID);
2.955 + } else {
2.956 + _prev.set(i, _last[_init_level]);
2.957 + _next.set(i, INVALID);
2.958 + _next.set(_last[_init_level], i);
2.959 + _last[_init_level] = i;
2.960 + }
2.961 + }
2.962 +
2.963 + ///Start a new level.
2.964 +
2.965 + ///Start a new level.
2.966 + ///It shouldn't be used before the items on level 0 are listed.
2.967 + void initNewLevel() {
2.968 + ++_init_level;
2.969 + }
2.970 +
2.971 + ///Finalize the initialization process.
2.972 + void initFinish() {
2.973 + _highest_active = -1;
2.974 + }
2.975 +
2.976 + ///@}
2.977 +
2.978 + };
2.979 +
2.980 +
2.981 +} //END OF NAMESPACE LEMON
2.982 +
2.983 +#endif
2.984 +