COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/elevator.h @ 380:d916b8995e22

Last change on this file since 380:d916b8995e22 was 380:d916b8995e22, checked in by Alpar Juttner <alpar@…>, 15 years ago

Rename markToBottom() to dirtyTopButOne() + better doc (#174)

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