COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/elevator.h @ 456:aff6888e71c9

Last change on this file since 456:aff6888e71c9 was 440:88ed40ad0d4f, checked in by Alpar Juttner <alpar@…>, 11 years ago

Happy New Year again

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