COIN-OR::LEMON - Graph Library

source: lemon/lemon/elevator.h @ 969:6dd226d3dcba

Last change on this file since 969:6dd226d3dcba was 628:aa1804409f29, checked in by Peter Kovacs <kpeter@…>, 16 years ago

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

File size: 26.4 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2009
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
30#include <lemon/core.h>
31#include <lemon/bits/traits.h>
32
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  ///
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>
53  class Elevator
54  {
55  public:
56
57    typedef Item Key;
58    typedef int Value;
59
60  private:
61
62    typedef Item *Vit;
63    typedef typename ItemSetTraits<GR,Item>::template Map<Vit>::Type VitMap;
64    typedef typename ItemSetTraits<GR,Item>::template Map<int>::Type IntMap;
65
66    const GR &_g;
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    {
79      _where[*p=i] = p;
80    }
81    void copy(Vit s, Vit p)
82    {
83      if(s!=p)
84        {
85          Item i=*s;
86          *p=i;
87          _where[i] = p;
88        }
89    }
90    void swap(Vit i, Vit j)
91    {
92      Item ti=*i;
93      Vit ct = _where[ti];
94      _where[ti] = _where[*i=*j];
95      _where[*j] = ct;
96      *j=ti;
97    }
98
99  public:
100
101    ///Constructor with given maximum level.
102
103    ///Constructor with given maximum level.
104    ///
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>.
108    Elevator(const GR &graph,int max_level) :
109      _g(graph),
110      _max_level(max_level),
111      _item_num(_max_level),
112      _where(graph),
113      _level(graph,0),
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    ///
122    ///\param graph The underlying graph.
123    ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
124    ///where \c max_level is equal to the number of labeled items in the graph.
125    Elevator(const GR &graph) :
126      _g(graph),
127      _max_level(countItems<GR, Item>(graph)),
128      _item_num(_max_level),
129      _where(graph),
130      _level(graph,0),
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    }
172    ///Return true if level \c l is empty.
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    }
187    ///Return true if there is no active item on level \c l.
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
206    ///Return a highest level active item or INVALID if there is no active
207    ///item.
208    Item highestActive() const
209    {
210      return _highest_active>=0?*_last_active[_highest_active]:INVALID;
211    }
212
213    ///Return the highest active level.
214
215    ///Return the level of the highest active item or -1 if there is no active
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    {
228      Item it = *_last_active[_highest_active];
229      ++_level[it];
230      swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
231      --_first[++_highest_active];
232    }
233
234    ///Lift the highest active item to the given level.
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]);
252      _level[li] = new_level;
253      _highest_active=new_level;
254    }
255
256    ///Lift the highest active item to the top level.
257
258    ///Lift the item returned by highestActive() to the top level and
259    ///deactivate it.
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];
272      _level[li] = _max_level;
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
286    ///Return an active item on level \c l.
287
288    ///Return an active item on level \c l or \ref INVALID if there is no such
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
295    ///Lift the active item returned by \c activeOn(level) by one.
296
297    ///Lift the active item returned by \ref activeOn() "activeOn(level)"
298    ///by one.
299    Item liftActiveOn(int level)
300    {
301      Item it =*_last_active[level];
302      ++_level[it];
303      swap(_last_active[level]--, --_first[level+1]);
304      if (level+1>_highest_active) ++_highest_active;
305    }
306
307    ///Lift the active item returned by \c activeOn(level) to the given level.
308
309    ///Lift the active item returned by \ref activeOn() "activeOn(level)"
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]);
322      _level[ai] = new_level;
323      if (new_level>_highest_active) _highest_active=new_level;
324    }
325
326    ///Lift the active item returned by \c activeOn(level) to the top level.
327
328    ///Lift the active item returned by \ref activeOn() "activeOn(level)"
329    ///to the top level and deactivate it.
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];
342      _level[ai] = _max_level;
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]);
373      _level[i] = new_level;
374      if(new_level>_highest_active) _highest_active=new_level;
375    }
376
377    ///Move an inactive item to the top but one level (in a dirty way).
378
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.
383    ///\pre The item is on the top level.
384    void dirtyTopButOne(Item i) {
385      _level[i] = _max_level - 1;
386    }
387
388    ///Lift all items on and above the given level to the top level.
389
390    ///This function lifts all items on and above level \c l to the top
391    ///level and deactivates them.
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)
397        _level[*i] = _max_level;
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
416    ///Using these functions you can initialize the levels of the items.
417    ///\n
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.
423    ///@{
424
425    ///Start the initialization process.
426    void initStart()
427    {
428      _init_lev=0;
429      _init_num=&_items[0];
430      _first[0]=&_items[0];
431      _last_active[0]=&_items[0]-1;
432      Vit n=&_items[0];
433      for(typename ItemSetTraits<GR,Item>::ItemIt i(_g);i!=INVALID;++i)
434        {
435          *n=i;
436          _where[i] = n;
437          _level[i] = _max_level;
438          ++n;
439        }
440    }
441
442    ///Add an item to the current level.
443    void initAddItem(Item i)
444    {
445      swap(_where[i],_init_num);
446      _level[i] = _init_lev;
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        }
469      _first[_max_level+1]=&_items[0]+_item_num;
470      _last_active[_max_level+1]=&_items[0]+_item_num-1;
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  ///
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>
496  class LinkedElevator {
497  public:
498
499    typedef Item Key;
500    typedef int Value;
501
502  private:
503
504    typedef typename ItemSetTraits<GR,Item>::
505    template Map<Item>::Type ItemMap;
506    typedef typename ItemSetTraits<GR,Item>::
507    template Map<int>::Type IntMap;
508    typedef typename ItemSetTraits<GR,Item>::
509    template Map<bool>::Type BoolMap;
510
511    const GR &_graph;
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    ///
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>.
528    LinkedElevator(const GR& graph, int max_level)
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    ///
538    ///\param graph The underlying graph.
539    ///Set the range of the possible labels to <tt>[0..max_level]</tt>,
540    ///where \c max_level is equal to the number of labeled items in the graph.
541    LinkedElevator(const GR& graph)
542      : _graph(graph), _max_level(countItems<GR, Item>(graph)),
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) {
554      _active[i] = true;
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
563      _next[_prev[i]] = _next[i];
564      if (_next[i] != INVALID) {
565        _prev[_next[i]] = _prev[i];
566      } else {
567        _last[level] = _prev[i];
568      }
569      //lace
570      _next[i] = _first[level];
571      _prev[_first[level]] = i;
572      _prev[i] = INVALID;
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) {
582      _active[i] = false;
583      int level = _level[i];
584
585      if (_next[i] == INVALID || !_active[_next[i]])
586        goto find_highest_level;
587
588      //unlace
589      _prev[_next[i]] = _prev[i];
590      if (_prev[i] != INVALID) {
591        _next[_prev[i]] = _next[i];
592      } else {
593        _first[_level[i]] = _next[i];
594      }
595      //lace
596      _prev[i] = _last[level];
597      _next[_last[level]] = i;
598      _next[i] = INVALID;
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
649    ///Return true if there is no active item on level \c l.
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
667    ///Return a highest level active item or INVALID if there is no active
668    ///item.
669    Item highestActive() const {
670      return _highest_active >= 0 ? _first[_highest_active] : INVALID;
671    }
672
673    ///Return the highest active level.
674
675    ///Return the level of the highest active item or -1 if there is no active
676    ///item.
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) {
688        _prev[_next[i]] = INVALID;
689        _first[_highest_active] = _next[i];
690      } else {
691        _first[_highest_active] = INVALID;
692        _last[_highest_active] = INVALID;
693      }
694      _level[i] = ++_highest_active;
695      if (_first[_highest_active] == INVALID) {
696        _first[_highest_active] = i;
697        _last[_highest_active] = i;
698        _prev[i] = INVALID;
699        _next[i] = INVALID;
700      } else {
701        _prev[_first[_highest_active]] = i;
702        _next[i] = _first[_highest_active];
703        _first[_highest_active] = i;
704      }
705    }
706
707    ///Lift the highest active item to the given level.
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) {
717        _prev[_next[i]] = INVALID;
718        _first[_highest_active] = _next[i];
719      } else {
720        _first[_highest_active] = INVALID;
721        _last[_highest_active] = INVALID;
722      }
723      _level[i] = _highest_active = new_level;
724      if (_first[_highest_active] == INVALID) {
725        _first[_highest_active] = _last[_highest_active] = i;
726        _prev[i] = INVALID;
727        _next[i] = INVALID;
728      } else {
729        _prev[_first[_highest_active]] = i;
730        _next[i] = _first[_highest_active];
731        _first[_highest_active] = i;
732      }
733    }
734
735    ///Lift the highest active item to the top level.
736
737    ///Lift the item returned by highestActive() to the top level and
738    ///deactivate it.
739    void liftHighestActiveToTop() {
740      Item i = _first[_highest_active];
741      _level[i] = _max_level;
742      if (_next[i] != INVALID) {
743        _prev[_next[i]] = INVALID;
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
760    ///Return an active item on level \c l.
761
762    ///Return an active item on level \c l or \ref INVALID if there is no such
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
769    ///Lift the active item returned by \c activeOn(l) by one.
770
771    ///Lift the active item returned by \ref activeOn() "activeOn(l)"
772    ///by one.
773    Item liftActiveOn(int l)
774    {
775      Item i = _first[l];
776      if (_next[i] != INVALID) {
777        _prev[_next[i]] = INVALID;
778        _first[l] = _next[i];
779      } else {
780        _first[l] = INVALID;
781        _last[l] = INVALID;
782      }
783      _level[i] = ++l;
784      if (_first[l] == INVALID) {
785        _first[l] = _last[l] = i;
786        _prev[i] = INVALID;
787        _next[i] = INVALID;
788      } else {
789        _prev[_first[l]] = i;
790        _next[i] = _first[l];
791        _first[l] = i;
792      }
793      if (_highest_active < l) {
794        _highest_active = l;
795      }
796    }
797
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.
802    void liftActiveOn(int l, int new_level)
803    {
804      Item i = _first[l];
805      if (_next[i] != INVALID) {
806        _prev[_next[i]] = INVALID;
807        _first[l] = _next[i];
808      } else {
809        _first[l] = INVALID;
810        _last[l] = INVALID;
811      }
812      _level[i] = l = new_level;
813      if (_first[l] == INVALID) {
814        _first[l] = _last[l] = i;
815        _prev[i] = INVALID;
816        _next[i] = INVALID;
817      } else {
818        _prev[_first[l]] = i;
819        _next[i] = _first[l];
820        _first[l] = i;
821      }
822      if (_highest_active < l) {
823        _highest_active = l;
824      }
825    }
826
827    ///Lift the active item returned by \c activeOn(l) to the top level.
828
829    ///Lift the active item returned by \ref activeOn() "activeOn(l)"
830    ///to the top level and deactivate it.
831    void liftActiveToTop(int l)
832    {
833      Item i = _first[l];
834      if (_next[i] != INVALID) {
835        _prev[_next[i]] = INVALID;
836        _first[l] = _next[i];
837      } else {
838        _first[l] = INVALID;
839        _last[l] = INVALID;
840      }
841      _level[i] = _max_level;
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) {
859        _prev[_next[i]] = _prev[i];
860      } else {
861        _last[new_level] = _prev[i];
862      }
863      if (_prev[i] != INVALID) {
864        _next[_prev[i]] = _next[i];
865      } else {
866        _first[new_level] = _next[i];
867      }
868      _level[i] = new_level;
869      if (_first[new_level] == INVALID) {
870        _first[new_level] = _last[new_level] = i;
871        _prev[i] = INVALID;
872        _next[i] = INVALID;
873      } else {
874        _prev[_first[new_level]] = i;
875        _next[i] = _first[new_level];
876        _first[new_level] = i;
877      }
878      if (_highest_active < new_level) {
879        _highest_active = new_level;
880      }
881    }
882
883    ///Move an inactive item to the top but one level (in a dirty way).
884
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.
889    ///\pre The item is on the top level.
890    void dirtyTopButOne(Item i) {
891      _level[i] = _max_level - 1;
892    }
893
894    ///Lift all items on and above the given level to the top level.
895
896    ///This function lifts all items on and above level \c l to the top
897    ///level and deactivates them.
898    void liftToTop(int l)  {
899      for (int i = l + 1; _first[i] != INVALID; ++i) {
900        Item n = _first[i];
901        while (n != INVALID) {
902          _level[n] = _max_level;
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
922    ///Using these functions you can initialize the levels of the items.
923    ///\n
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.
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;
938      for(typename ItemSetTraits<GR,Item>::ItemIt i(_graph);
939          i != INVALID; ++i) {
940        _level[i] = _max_level;
941        _active[i] = false;
942      }
943    }
944
945    ///Add an item to the current level.
946    void initAddItem(Item i) {
947      _level[i] = _init_level;
948      if (_last[_init_level] == INVALID) {
949        _first[_init_level] = i;
950        _last[_init_level] = i;
951        _prev[i] = INVALID;
952        _next[i] = INVALID;
953      } else {
954        _prev[i] = _last[_init_level];
955        _next[i] = INVALID;
956        _next[_last[_init_level]] = i;
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.