COIN-OR::LEMON - Graph Library

source: lemon/lemon/elevator.h @ 924:c67e235c832f

Last change on this file since 924:c67e235c832f was 628:aa1804409f29, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Exploit that the standard maps are reference maps (#190)

File size: 26.4 KB
RevLine 
[394]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
[463]5 * Copyright (C) 2003-2009
[394]6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_ELEVATOR_H
20#define LEMON_ELEVATOR_H
21
22///\ingroup auxdat
23///\file
24///\brief Elevator class
25///
26///Elevator class implements an efficient data structure
27///for labeling items in push-relabel type algorithms.
28///
29
[566]30#include <lemon/core.h>
[398]31#include <lemon/bits/traits.h>
32
[394]33namespace lemon {
34
35  ///Class for handling "labels" in push-relabel type algorithms.
36
37  ///A class for handling "labels" in push-relabel type algorithms.
38  ///
39  ///\ingroup auxdat
40  ///Using this class you can assign "labels" (nonnegative integer numbers)
41  ///to the edges or nodes of a graph, manipulate and query them through
42  ///operations typically arising in "push-relabel" type algorithms.
43  ///
44  ///Each item is either \em active or not, and you can also choose a
45  ///highest level active item.
46  ///
47  ///\sa LinkedElevator
48  ///
[606]49  ///\param GR Type of the underlying graph.
50  ///\param Item Type of the items the data is assigned to (\c GR::Node,
51  ///\c GR::Arc or \c GR::Edge).
52  template<class GR, class Item>
[394]53  class Elevator
54  {
55  public:
56
57    typedef Item Key;
58    typedef int Value;
59
60  private:
61
[396]62    typedef Item *Vit;
[606]63    typedef typename ItemSetTraits<GR,Item>::template Map<Vit>::Type VitMap;
64    typedef typename ItemSetTraits<GR,Item>::template Map<int>::Type IntMap;
[394]65
[606]66    const GR &_g;
[394]67    int _max_level;
68    int _item_num;
69    VitMap _where;
70    IntMap _level;
71    std::vector<Item> _items;
72    std::vector<Vit> _first;
73    std::vector<Vit> _last_active;
74
75    int _highest_active;
76
77    void copy(Item i, Vit p)
78    {
[628]79      _where[*p=i] = p;
[394]80    }
81    void copy(Vit s, Vit p)
82    {
83      if(s!=p)
84        {
85          Item i=*s;
86          *p=i;
[628]87          _where[i] = p;
[394]88        }
89    }
90    void swap(Vit i, Vit j)
91    {
92      Item ti=*i;
93      Vit ct = _where[ti];
[628]94      _where[ti] = _where[*i=*j];
95      _where[*j] = ct;
[394]96      *j=ti;
97    }
98
99  public:
100
101    ///Constructor with given maximum level.
102
103    ///Constructor with given maximum level.
104    ///
[398]105    ///\param graph The underlying graph.
106    ///\param max_level The maximum allowed level.
107    ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
[606]108    Elevator(const GR &graph,int max_level) :
[398]109      _g(graph),
[394]110      _max_level(max_level),
111      _item_num(_max_level),
[398]112      _where(graph),
113      _level(graph,0),
[394]114      _items(_max_level),
115      _first(_max_level+2),
116      _last_active(_max_level+2),
117      _highest_active(-1) {}
118    ///Constructor.
119
120    ///Constructor.
121    ///
[398]122    ///\param graph The underlying graph.
123    ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
[394]124    ///where \c max_level is equal to the number of labeled items in the graph.
[606]125    Elevator(const GR &graph) :
[398]126      _g(graph),
[606]127      _max_level(countItems<GR, Item>(graph)),
[394]128      _item_num(_max_level),
[398]129      _where(graph),
130      _level(graph,0),
[394]131      _items(_max_level),
132      _first(_max_level+2),
133      _last_active(_max_level+2),
134      _highest_active(-1)
135    {
136    }
137
138    ///Activate item \c i.
139
140    ///Activate item \c i.
141    ///\pre Item \c i shouldn't be active before.
142    void activate(Item i)
143    {
144      const int l=_level[i];
145      swap(_where[i],++_last_active[l]);
146      if(l>_highest_active) _highest_active=l;
147    }
148
149    ///Deactivate item \c i.
150
151    ///Deactivate item \c i.
152    ///\pre Item \c i must be active before.
153    void deactivate(Item i)
154    {
155      swap(_where[i],_last_active[_level[i]]--);
156      while(_highest_active>=0 &&
157            _last_active[_highest_active]<_first[_highest_active])
158        _highest_active--;
159    }
160
161    ///Query whether item \c i is active
162    bool active(Item i) const { return _where[i]<=_last_active[_level[i]]; }
163
164    ///Return the level of item \c i.
165    int operator[](Item i) const { return _level[i]; }
166
167    ///Return the number of items on level \c l.
168    int onLevel(int l) const
169    {
170      return _first[l+1]-_first[l];
171    }
[398]172    ///Return true if level \c l is empty.
[394]173    bool emptyLevel(int l) const
174    {
175      return _first[l+1]-_first[l]==0;
176    }
177    ///Return the number of items above level \c l.
178    int aboveLevel(int l) const
179    {
180      return _first[_max_level+1]-_first[l+1];
181    }
182    ///Return the number of active items on level \c l.
183    int activesOnLevel(int l) const
184    {
185      return _last_active[l]-_first[l]+1;
186    }
[398]187    ///Return true if there is no active item on level \c l.
[394]188    bool activeFree(int l) const
189    {
190      return _last_active[l]<_first[l];
191    }
192    ///Return the maximum allowed level.
193    int maxLevel() const
194    {
195      return _max_level;
196    }
197
198    ///\name Highest Active Item
199    ///Functions for working with the highest level
200    ///active item.
201
202    ///@{
203
204    ///Return a highest level active item.
205
[398]206    ///Return a highest level active item or INVALID if there is no active
[394]207    ///item.
208    Item highestActive() const
209    {
210      return _highest_active>=0?*_last_active[_highest_active]:INVALID;
211    }
212
[398]213    ///Return the highest active level.
[394]214
[398]215    ///Return the level of the highest active item or -1 if there is no active
[394]216    ///item.
217    int highestActiveLevel() const
218    {
219      return _highest_active;
220    }
221
222    ///Lift the highest active item by one.
223
224    ///Lift the item returned by highestActive() by one.
225    ///
226    void liftHighestActive()
227    {
[397]228      Item it = *_last_active[_highest_active];
[628]229      ++_level[it];
[394]230      swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
231      --_first[++_highest_active];
232    }
233
[398]234    ///Lift the highest active item to the given level.
[394]235
236    ///Lift the item returned by highestActive() to level \c new_level.
237    ///
238    ///\warning \c new_level must be strictly higher
239    ///than the current level.
240    ///
241    void liftHighestActive(int new_level)
242    {
243      const Item li = *_last_active[_highest_active];
244
245      copy(--_first[_highest_active+1],_last_active[_highest_active]--);
246      for(int l=_highest_active+1;l<new_level;l++)
247        {
248          copy(--_first[l+1],_first[l]);
249          --_last_active[l];
250        }
251      copy(li,_first[new_level]);
[628]252      _level[li] = new_level;
[394]253      _highest_active=new_level;
254    }
255
[398]256    ///Lift the highest active item to the top level.
[394]257
258    ///Lift the item returned by highestActive() to the top level and
[398]259    ///deactivate it.
[394]260    void liftHighestActiveToTop()
261    {
262      const Item li = *_last_active[_highest_active];
263
264      copy(--_first[_highest_active+1],_last_active[_highest_active]--);
265      for(int l=_highest_active+1;l<_max_level;l++)
266        {
267          copy(--_first[l+1],_first[l]);
268          --_last_active[l];
269        }
270      copy(li,_first[_max_level]);
271      --_last_active[_max_level];
[628]272      _level[li] = _max_level;
[394]273
274      while(_highest_active>=0 &&
275            _last_active[_highest_active]<_first[_highest_active])
276        _highest_active--;
277    }
278
279    ///@}
280
281    ///\name Active Item on Certain Level
282    ///Functions for working with the active items.
283
284    ///@{
285
[398]286    ///Return an active item on level \c l.
[394]287
[398]288    ///Return an active item on level \c l or \ref INVALID if there is no such
[394]289    ///an item. (\c l must be from the range [0...\c max_level].
290    Item activeOn(int l) const
291    {
292      return _last_active[l]>=_first[l]?*_last_active[l]:INVALID;
293    }
294
[398]295    ///Lift the active item returned by \c activeOn(level) by one.
[394]296
[398]297    ///Lift the active item returned by \ref activeOn() "activeOn(level)"
[394]298    ///by one.
299    Item liftActiveOn(int level)
300    {
[397]301      Item it =*_last_active[level];
[628]302      ++_level[it];
[394]303      swap(_last_active[level]--, --_first[level+1]);
304      if (level+1>_highest_active) ++_highest_active;
305    }
306
[398]307    ///Lift the active item returned by \c activeOn(level) to the given level.
[394]308
[398]309    ///Lift the active item returned by \ref activeOn() "activeOn(level)"
[394]310    ///to the given level.
311    void liftActiveOn(int level, int new_level)
312    {
313      const Item ai = *_last_active[level];
314
315      copy(--_first[level+1], _last_active[level]--);
316      for(int l=level+1;l<new_level;l++)
317        {
318          copy(_last_active[l],_first[l]);
319          copy(--_first[l+1], _last_active[l]--);
320        }
321      copy(ai,_first[new_level]);
[628]322      _level[ai] = new_level;
[394]323      if (new_level>_highest_active) _highest_active=new_level;
324    }
325
[398]326    ///Lift the active item returned by \c activeOn(level) to the top level.
[394]327
[398]328    ///Lift the active item returned by \ref activeOn() "activeOn(level)"
329    ///to the top level and deactivate it.
[394]330    void liftActiveToTop(int level)
331    {
332      const Item ai = *_last_active[level];
333
334      copy(--_first[level+1],_last_active[level]--);
335      for(int l=level+1;l<_max_level;l++)
336        {
337          copy(_last_active[l],_first[l]);
338          copy(--_first[l+1], _last_active[l]--);
339        }
340      copy(ai,_first[_max_level]);
341      --_last_active[_max_level];
[628]342      _level[ai] = _max_level;
[394]343
344      if (_highest_active==level) {
345        while(_highest_active>=0 &&
346              _last_active[_highest_active]<_first[_highest_active])
347          _highest_active--;
348      }
349    }
350
351    ///@}
352
353    ///Lift an active item to a higher level.
354
355    ///Lift an active item to a higher level.
356    ///\param i The item to be lifted. It must be active.
357    ///\param new_level The new level of \c i. It must be strictly higher
358    ///than the current level.
359    ///
360    void lift(Item i, int new_level)
361    {
362      const int lo = _level[i];
363      const Vit w = _where[i];
364
365      copy(_last_active[lo],w);
366      copy(--_first[lo+1],_last_active[lo]--);
367      for(int l=lo+1;l<new_level;l++)
368        {
369          copy(_last_active[l],_first[l]);
370          copy(--_first[l+1],_last_active[l]--);
371        }
372      copy(i,_first[new_level]);
[628]373      _level[i] = new_level;
[394]374      if(new_level>_highest_active) _highest_active=new_level;
375    }
376
[395]377    ///Move an inactive item to the top but one level (in a dirty way).
[394]378
[398]379    ///This function moves an inactive item from the top level to the top
380    ///but one level (in a dirty way).
381    ///\warning It makes the underlying datastructure corrupt, so use it
382    ///only if you really know what it is for.
[395]383    ///\pre The item is on the top level.
384    void dirtyTopButOne(Item i) {
[628]385      _level[i] = _max_level - 1;
[394]386    }
387
[398]388    ///Lift all items on and above the given level to the top level.
[394]389
[398]390    ///This function lifts all items on and above level \c l to the top
391    ///level and deactivates them.
[394]392    void liftToTop(int l)
393    {
394      const Vit f=_first[l];
395      const Vit tl=_first[_max_level];
396      for(Vit i=f;i!=tl;++i)
[628]397        _level[*i] = _max_level;
[394]398      for(int i=l;i<=_max_level;i++)
399        {
400          _first[i]=f;
401          _last_active[i]=f-1;
402        }
403      for(_highest_active=l-1;
404          _highest_active>=0 &&
405            _last_active[_highest_active]<_first[_highest_active];
406          _highest_active--) ;
407    }
408
409  private:
410    int _init_lev;
411    Vit _init_num;
412
413  public:
414
415    ///\name Initialization
[398]416    ///Using these functions you can initialize the levels of the items.
[394]417    ///\n
[398]418    ///The initialization must be started with calling \c initStart().
419    ///Then the items should be listed level by level starting with the
420    ///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
421    ///Finally \c initFinish() must be called.
422    ///The items not listed are put on the highest level.
[394]423    ///@{
424
425    ///Start the initialization process.
426    void initStart()
427    {
428      _init_lev=0;
[396]429      _init_num=&_items[0];
430      _first[0]=&_items[0];
431      _last_active[0]=&_items[0]-1;
432      Vit n=&_items[0];
[606]433      for(typename ItemSetTraits<GR,Item>::ItemIt i(_g);i!=INVALID;++i)
[394]434        {
435          *n=i;
[628]436          _where[i] = n;
437          _level[i] = _max_level;
[394]438          ++n;
439        }
440    }
441
442    ///Add an item to the current level.
443    void initAddItem(Item i)
444    {
[397]445      swap(_where[i],_init_num);
[628]446      _level[i] = _init_lev;
[394]447      ++_init_num;
448    }
449
450    ///Start a new level.
451
452    ///Start a new level.
453    ///It shouldn't be used before the items on level 0 are listed.
454    void initNewLevel()
455    {
456      _init_lev++;
457      _first[_init_lev]=_init_num;
458      _last_active[_init_lev]=_init_num-1;
459    }
460
461    ///Finalize the initialization process.
462    void initFinish()
463    {
464      for(_init_lev++;_init_lev<=_max_level;_init_lev++)
465        {
466          _first[_init_lev]=_init_num;
467          _last_active[_init_lev]=_init_num-1;
468        }
[396]469      _first[_max_level+1]=&_items[0]+_item_num;
470      _last_active[_max_level+1]=&_items[0]+_item_num-1;
[394]471      _highest_active = -1;
472    }
473
474    ///@}
475
476  };
477
478  ///Class for handling "labels" in push-relabel type algorithms.
479
480  ///A class for handling "labels" in push-relabel type algorithms.
481  ///
482  ///\ingroup auxdat
483  ///Using this class you can assign "labels" (nonnegative integer numbers)
484  ///to the edges or nodes of a graph, manipulate and query them through
485  ///operations typically arising in "push-relabel" type algorithms.
486  ///
487  ///Each item is either \em active or not, and you can also choose a
488  ///highest level active item.
489  ///
490  ///\sa Elevator
491  ///
[606]492  ///\param GR Type of the underlying graph.
493  ///\param Item Type of the items the data is assigned to (\c GR::Node,
494  ///\c GR::Arc or \c GR::Edge).
495  template <class GR, class Item>
[394]496  class LinkedElevator {
497  public:
498
499    typedef Item Key;
500    typedef int Value;
501
502  private:
503
[606]504    typedef typename ItemSetTraits<GR,Item>::
[394]505    template Map<Item>::Type ItemMap;
[606]506    typedef typename ItemSetTraits<GR,Item>::
[394]507    template Map<int>::Type IntMap;
[606]508    typedef typename ItemSetTraits<GR,Item>::
[394]509    template Map<bool>::Type BoolMap;
510
[606]511    const GR &_graph;
[394]512    int _max_level;
513    int _item_num;
514    std::vector<Item> _first, _last;
515    ItemMap _prev, _next;
516    int _highest_active;
517    IntMap _level;
518    BoolMap _active;
519
520  public:
521    ///Constructor with given maximum level.
522
523    ///Constructor with given maximum level.
524    ///
[398]525    ///\param graph The underlying graph.
526    ///\param max_level The maximum allowed level.
527    ///Set the range of the possible labels to <tt>[0..max_level]</tt>.
[606]528    LinkedElevator(const GR& graph, int max_level)
[394]529      : _graph(graph), _max_level(max_level), _item_num(_max_level),
530        _first(_max_level + 1), _last(_max_level + 1),
531        _prev(graph), _next(graph),
532        _highest_active(-1), _level(graph), _active(graph) {}
533
534    ///Constructor.
535
536    ///Constructor.
537    ///
[398]538    ///\param graph The underlying graph.
539    ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
[394]540    ///where \c max_level is equal to the number of labeled items in the graph.
[606]541    LinkedElevator(const GR& graph)
542      : _graph(graph), _max_level(countItems<GR, Item>(graph)),
[394]543        _item_num(_max_level),
544        _first(_max_level + 1), _last(_max_level + 1),
545        _prev(graph, INVALID), _next(graph, INVALID),
546        _highest_active(-1), _level(graph), _active(graph) {}
547
548
549    ///Activate item \c i.
550
551    ///Activate item \c i.
552    ///\pre Item \c i shouldn't be active before.
553    void activate(Item i) {
[628]554      _active[i] = true;
[394]555
556      int level = _level[i];
557      if (level > _highest_active) {
558        _highest_active = level;
559      }
560
561      if (_prev[i] == INVALID || _active[_prev[i]]) return;
562      //unlace
[628]563      _next[_prev[i]] = _next[i];
[394]564      if (_next[i] != INVALID) {
[628]565        _prev[_next[i]] = _prev[i];
[394]566      } else {
567        _last[level] = _prev[i];
568      }
569      //lace
[628]570      _next[i] = _first[level];
571      _prev[_first[level]] = i;
572      _prev[i] = INVALID;
[394]573      _first[level] = i;
574
575    }
576
577    ///Deactivate item \c i.
578
579    ///Deactivate item \c i.
580    ///\pre Item \c i must be active before.
581    void deactivate(Item i) {
[628]582      _active[i] = false;
[394]583      int level = _level[i];
584
585      if (_next[i] == INVALID || !_active[_next[i]])
586        goto find_highest_level;
587
588      //unlace
[628]589      _prev[_next[i]] = _prev[i];
[394]590      if (_prev[i] != INVALID) {
[628]591        _next[_prev[i]] = _next[i];
[394]592      } else {
593        _first[_level[i]] = _next[i];
594      }
595      //lace
[628]596      _prev[i] = _last[level];
597      _next[_last[level]] = i;
598      _next[i] = INVALID;
[394]599      _last[level] = i;
600
601    find_highest_level:
602      if (level == _highest_active) {
603        while (_highest_active >= 0 && activeFree(_highest_active))
604          --_highest_active;
605      }
606    }
607
608    ///Query whether item \c i is active
609    bool active(Item i) const { return _active[i]; }
610
611    ///Return the level of item \c i.
612    int operator[](Item i) const { return _level[i]; }
613
614    ///Return the number of items on level \c l.
615    int onLevel(int l) const {
616      int num = 0;
617      Item n = _first[l];
618      while (n != INVALID) {
619        ++num;
620        n = _next[n];
621      }
622      return num;
623    }
624
625    ///Return true if the level is empty.
626    bool emptyLevel(int l) const {
627      return _first[l] == INVALID;
628    }
629
630    ///Return the number of items above level \c l.
631    int aboveLevel(int l) const {
632      int num = 0;
633      for (int level = l + 1; level < _max_level; ++level)
634        num += onLevel(level);
635      return num;
636    }
637
638    ///Return the number of active items on level \c l.
639    int activesOnLevel(int l) const {
640      int num = 0;
641      Item n = _first[l];
642      while (n != INVALID && _active[n]) {
643        ++num;
644        n = _next[n];
645      }
646      return num;
647    }
648
[398]649    ///Return true if there is no active item on level \c l.
[394]650    bool activeFree(int l) const {
651      return _first[l] == INVALID || !_active[_first[l]];
652    }
653
654    ///Return the maximum allowed level.
655    int maxLevel() const {
656      return _max_level;
657    }
658
659    ///\name Highest Active Item
660    ///Functions for working with the highest level
661    ///active item.
662
663    ///@{
664
665    ///Return a highest level active item.
666
[398]667    ///Return a highest level active item or INVALID if there is no active
668    ///item.
[394]669    Item highestActive() const {
670      return _highest_active >= 0 ? _first[_highest_active] : INVALID;
671    }
672
[398]673    ///Return the highest active level.
[394]674
[398]675    ///Return the level of the highest active item or -1 if there is no active
676    ///item.
[394]677    int highestActiveLevel() const {
678      return _highest_active;
679    }
680
681    ///Lift the highest active item by one.
682
683    ///Lift the item returned by highestActive() by one.
684    ///
685    void liftHighestActive() {
686      Item i = _first[_highest_active];
687      if (_next[i] != INVALID) {
[628]688        _prev[_next[i]] = INVALID;
[394]689        _first[_highest_active] = _next[i];
690      } else {
691        _first[_highest_active] = INVALID;
692        _last[_highest_active] = INVALID;
693      }
[628]694      _level[i] = ++_highest_active;
[394]695      if (_first[_highest_active] == INVALID) {
696        _first[_highest_active] = i;
697        _last[_highest_active] = i;
[628]698        _prev[i] = INVALID;
699        _next[i] = INVALID;
[394]700      } else {
[628]701        _prev[_first[_highest_active]] = i;
702        _next[i] = _first[_highest_active];
[394]703        _first[_highest_active] = i;
704      }
705    }
706
[398]707    ///Lift the highest active item to the given level.
[394]708
709    ///Lift the item returned by highestActive() to level \c new_level.
710    ///
711    ///\warning \c new_level must be strictly higher
712    ///than the current level.
713    ///
714    void liftHighestActive(int new_level) {
715      Item i = _first[_highest_active];
716      if (_next[i] != INVALID) {
[628]717        _prev[_next[i]] = INVALID;
[394]718        _first[_highest_active] = _next[i];
719      } else {
720        _first[_highest_active] = INVALID;
721        _last[_highest_active] = INVALID;
722      }
[628]723      _level[i] = _highest_active = new_level;
[394]724      if (_first[_highest_active] == INVALID) {
725        _first[_highest_active] = _last[_highest_active] = i;
[628]726        _prev[i] = INVALID;
727        _next[i] = INVALID;
[394]728      } else {
[628]729        _prev[_first[_highest_active]] = i;
730        _next[i] = _first[_highest_active];
[394]731        _first[_highest_active] = i;
732      }
733    }
734
[398]735    ///Lift the highest active item to the top level.
[394]736
737    ///Lift the item returned by highestActive() to the top level and
[398]738    ///deactivate it.
[394]739    void liftHighestActiveToTop() {
740      Item i = _first[_highest_active];
[628]741      _level[i] = _max_level;
[394]742      if (_next[i] != INVALID) {
[628]743        _prev[_next[i]] = INVALID;
[394]744        _first[_highest_active] = _next[i];
745      } else {
746        _first[_highest_active] = INVALID;
747        _last[_highest_active] = INVALID;
748      }
749      while (_highest_active >= 0 && activeFree(_highest_active))
750        --_highest_active;
751    }
752
753    ///@}
754
755    ///\name Active Item on Certain Level
756    ///Functions for working with the active items.
757
758    ///@{
759
[398]760    ///Return an active item on level \c l.
[394]761
[398]762    ///Return an active item on level \c l or \ref INVALID if there is no such
[394]763    ///an item. (\c l must be from the range [0...\c max_level].
764    Item activeOn(int l) const
765    {
766      return _active[_first[l]] ? _first[l] : INVALID;
767    }
768
[398]769    ///Lift the active item returned by \c activeOn(l) by one.
[394]770
[398]771    ///Lift the active item returned by \ref activeOn() "activeOn(l)"
[394]772    ///by one.
773    Item liftActiveOn(int l)
774    {
775      Item i = _first[l];
776      if (_next[i] != INVALID) {
[628]777        _prev[_next[i]] = INVALID;
[394]778        _first[l] = _next[i];
779      } else {
780        _first[l] = INVALID;
781        _last[l] = INVALID;
782      }
[628]783      _level[i] = ++l;
[394]784      if (_first[l] == INVALID) {
785        _first[l] = _last[l] = i;
[628]786        _prev[i] = INVALID;
787        _next[i] = INVALID;
[394]788      } else {
[628]789        _prev[_first[l]] = i;
790        _next[i] = _first[l];
[394]791        _first[l] = i;
792      }
793      if (_highest_active < l) {
794        _highest_active = l;
795      }
796    }
797
[398]798    ///Lift the active item returned by \c activeOn(l) to the given level.
799
800    ///Lift the active item returned by \ref activeOn() "activeOn(l)"
801    ///to the given level.
[394]802    void liftActiveOn(int l, int new_level)
803    {
804      Item i = _first[l];
805      if (_next[i] != INVALID) {
[628]806        _prev[_next[i]] = INVALID;
[394]807        _first[l] = _next[i];
808      } else {
809        _first[l] = INVALID;
810        _last[l] = INVALID;
811      }
[628]812      _level[i] = l = new_level;
[394]813      if (_first[l] == INVALID) {
814        _first[l] = _last[l] = i;
[628]815        _prev[i] = INVALID;
816        _next[i] = INVALID;
[394]817      } else {
[628]818        _prev[_first[l]] = i;
819        _next[i] = _first[l];
[394]820        _first[l] = i;
821      }
822      if (_highest_active < l) {
823        _highest_active = l;
824      }
825    }
826
[398]827    ///Lift the active item returned by \c activeOn(l) to the top level.
[394]828
[398]829    ///Lift the active item returned by \ref activeOn() "activeOn(l)"
830    ///to the top level and deactivate it.
[394]831    void liftActiveToTop(int l)
832    {
833      Item i = _first[l];
834      if (_next[i] != INVALID) {
[628]835        _prev[_next[i]] = INVALID;
[394]836        _first[l] = _next[i];
837      } else {
838        _first[l] = INVALID;
839        _last[l] = INVALID;
840      }
[628]841      _level[i] = _max_level;
[394]842      if (l == _highest_active) {
843        while (_highest_active >= 0 && activeFree(_highest_active))
844          --_highest_active;
845      }
846    }
847
848    ///@}
849
850    /// \brief Lift an active item to a higher level.
851    ///
852    /// Lift an active item to a higher level.
853    /// \param i The item to be lifted. It must be active.
854    /// \param new_level The new level of \c i. It must be strictly higher
855    /// than the current level.
856    ///
857    void lift(Item i, int new_level) {
858      if (_next[i] != INVALID) {
[628]859        _prev[_next[i]] = _prev[i];
[394]860      } else {
861        _last[new_level] = _prev[i];
862      }
863      if (_prev[i] != INVALID) {
[628]864        _next[_prev[i]] = _next[i];
[394]865      } else {
866        _first[new_level] = _next[i];
867      }
[628]868      _level[i] = new_level;
[394]869      if (_first[new_level] == INVALID) {
870        _first[new_level] = _last[new_level] = i;
[628]871        _prev[i] = INVALID;
872        _next[i] = INVALID;
[394]873      } else {
[628]874        _prev[_first[new_level]] = i;
875        _next[i] = _first[new_level];
[394]876        _first[new_level] = i;
877      }
878      if (_highest_active < new_level) {
879        _highest_active = new_level;
880      }
881    }
882
[395]883    ///Move an inactive item to the top but one level (in a dirty way).
[394]884
[398]885    ///This function moves an inactive item from the top level to the top
886    ///but one level (in a dirty way).
887    ///\warning It makes the underlying datastructure corrupt, so use it
888    ///only if you really know what it is for.
[395]889    ///\pre The item is on the top level.
890    void dirtyTopButOne(Item i) {
[628]891      _level[i] = _max_level - 1;
[394]892    }
893
[398]894    ///Lift all items on and above the given level to the top level.
[394]895
[398]896    ///This function lifts all items on and above level \c l to the top
897    ///level and deactivates them.
[394]898    void liftToTop(int l)  {
899      for (int i = l + 1; _first[i] != INVALID; ++i) {
900        Item n = _first[i];
901        while (n != INVALID) {
[628]902          _level[n] = _max_level;
[394]903          n = _next[n];
904        }
905        _first[i] = INVALID;
906        _last[i] = INVALID;
907      }
908      if (_highest_active > l - 1) {
909        _highest_active = l - 1;
910        while (_highest_active >= 0 && activeFree(_highest_active))
911          --_highest_active;
912      }
913    }
914
915  private:
916
917    int _init_level;
918
919  public:
920
921    ///\name Initialization
[398]922    ///Using these functions you can initialize the levels of the items.
[394]923    ///\n
[398]924    ///The initialization must be started with calling \c initStart().
925    ///Then the items should be listed level by level starting with the
926    ///lowest one (level 0) using \c initAddItem() and \c initNewLevel().
927    ///Finally \c initFinish() must be called.
928    ///The items not listed are put on the highest level.
[394]929    ///@{
930
931    ///Start the initialization process.
932    void initStart() {
933
934      for (int i = 0; i <= _max_level; ++i) {
935        _first[i] = _last[i] = INVALID;
936      }
937      _init_level = 0;
[606]938      for(typename ItemSetTraits<GR,Item>::ItemIt i(_graph);
[394]939          i != INVALID; ++i) {
[628]940        _level[i] = _max_level;
941        _active[i] = false;
[394]942      }
943    }
944
945    ///Add an item to the current level.
946    void initAddItem(Item i) {
[628]947      _level[i] = _init_level;
[394]948      if (_last[_init_level] == INVALID) {
949        _first[_init_level] = i;
950        _last[_init_level] = i;
[628]951        _prev[i] = INVALID;
952        _next[i] = INVALID;
[394]953      } else {
[628]954        _prev[i] = _last[_init_level];
955        _next[i] = INVALID;
956        _next[_last[_init_level]] = i;
[394]957        _last[_init_level] = i;
958      }
959    }
960
961    ///Start a new level.
962
963    ///Start a new level.
964    ///It shouldn't be used before the items on level 0 are listed.
965    void initNewLevel() {
966      ++_init_level;
967    }
968
969    ///Finalize the initialization process.
970    void initFinish() {
971      _highest_active = -1;
972    }
973
974    ///@}
975
976  };
977
978
979} //END OF NAMESPACE LEMON
980
981#endif
982
Note: See TracBrowser for help on using the repository browser.