COIN-OR::LEMON - Graph Library

source: lemon/lemon/elevator.h @ 397:61fbd77f0f44

Last change on this file since 397:61fbd77f0f44 was 397:61fbd77f0f44, checked in by Alpar Juttner <alpar@…>, 16 years ago

Don't assume that the default maps are reference maps (in Elevator)

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