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