COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 581:aa1804409f29 in lemon-main for lemon/elevator.h


Ignore:
Timestamp:
04/14/09 10:35:38 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

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

File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/elevator.h

    r559 r581  
    7777    void copy(Item i, Vit p)
    7878    {
    79       _where.set(*p=i,p);
     79      _where[*p=i] = p;
    8080    }
    8181    void copy(Vit s, Vit p)
    … …  
    8585          Item i=*s;
    8686          *p=i;
    87           _where.set(i,p);
     87          _where[i] = p;
    8888        }
    8989    }
    … …  
    9292      Item ti=*i;
    9393      Vit ct = _where[ti];
    94       _where.set(ti,_where[*i=*j]);
    95       _where.set(*j,ct);
     94      _where[ti] = _where[*i=*j];
     95      _where[*j] = ct;
    9696      *j=ti;
    9797    }
    … …  
    227227    {
    228228      Item it = *_last_active[_highest_active];
    229       _level.set(it,_level[it]+1);
     229      ++_level[it];
    230230      swap(_last_active[_highest_active]--,_last_active[_highest_active+1]);
    231231      --_first[++_highest_active];
    … …  
    250250        }
    251251      copy(li,_first[new_level]);
    252       _level.set(li,new_level);
     252      _level[li] = new_level;
    253253      _highest_active=new_level;
    254254    }
    … …  
    270270      copy(li,_first[_max_level]);
    271271      --_last_active[_max_level];
    272       _level.set(li,_max_level);
     272      _level[li] = _max_level;
    273273
    274274      while(_highest_active>=0 &&
    … …  
    300300    {
    301301      Item it =*_last_active[level];
    302       _level.set(it,_level[it]+1);
     302      ++_level[it];
    303303      swap(_last_active[level]--, --_first[level+1]);
    304304      if (level+1>_highest_active) ++_highest_active;
    … …  
    320320        }
    321321      copy(ai,_first[new_level]);
    322       _level.set(ai,new_level);
     322      _level[ai] = new_level;
    323323      if (new_level>_highest_active) _highest_active=new_level;
    324324    }
    … …  
    340340      copy(ai,_first[_max_level]);
    341341      --_last_active[_max_level];
    342       _level.set(ai,_max_level);
     342      _level[ai] = _max_level;
    343343
    344344      if (_highest_active==level) {
    … …  
    371371        }
    372372      copy(i,_first[new_level]);
    373       _level.set(i,new_level);
     373      _level[i] = new_level;
    374374      if(new_level>_highest_active) _highest_active=new_level;
    375375    }
    … …  
    383383    ///\pre The item is on the top level.
    384384    void dirtyTopButOne(Item i) {
    385       _level.set(i,_max_level - 1);
     385      _level[i] = _max_level - 1;
    386386    }
    387387
    … …  
    395395      const Vit tl=_first[_max_level];
    396396      for(Vit i=f;i!=tl;++i)
    397         _level.set(*i,_max_level);
     397        _level[*i] = _max_level;
    398398      for(int i=l;i<=_max_level;i++)
    399399        {
    … …  
    434434        {
    435435          *n=i;
    436           _where.set(i,n);
    437           _level.set(i,_max_level);
     436          _where[i] = n;
     437          _level[i] = _max_level;
    438438          ++n;
    439439        }
    … …  
    444444    {
    445445      swap(_where[i],_init_num);
    446       _level.set(i,_init_lev);
     446      _level[i] = _init_lev;
    447447      ++_init_num;
    448448    }
    … …  
    552552    ///\pre Item \c i shouldn't be active before.
    553553    void activate(Item i) {
    554       _active.set(i, true);
     554      _active[i] = true;
    555555
    556556      int level = _level[i];
    … …  
    561561      if (_prev[i] == INVALID || _active[_prev[i]]) return;
    562562      //unlace
    563       _next.set(_prev[i], _next[i]);
     563      _next[_prev[i]] = _next[i];
    564564      if (_next[i] != INVALID) {
    565         _prev.set(_next[i], _prev[i]);
     565        _prev[_next[i]] = _prev[i];
    566566      } else {
    567567        _last[level] = _prev[i];
    568568      }
    569569      //lace
    570       _next.set(i, _first[level]);
    571       _prev.set(_first[level], i);
    572       _prev.set(i, INVALID);
     570      _next[i] = _first[level];
     571      _prev[_first[level]] = i;
     572      _prev[i] = INVALID;
    573573      _first[level] = i;
    574574
    … …  
    580580    ///\pre Item \c i must be active before.
    581581    void deactivate(Item i) {
    582       _active.set(i, false);
     582      _active[i] = false;
    583583      int level = _level[i];
    584584
    … …  
    587587
    588588      //unlace
    589       _prev.set(_next[i], _prev[i]);
     589      _prev[_next[i]] = _prev[i];
    590590      if (_prev[i] != INVALID) {
    591         _next.set(_prev[i], _next[i]);
     591        _next[_prev[i]] = _next[i];
    592592      } else {
    593593        _first[_level[i]] = _next[i];
    594594      }
    595595      //lace
    596       _prev.set(i, _last[level]);
    597       _next.set(_last[level], i);
    598       _next.set(i, INVALID);
     596      _prev[i] = _last[level];
     597      _next[_last[level]] = i;
     598      _next[i] = INVALID;
    599599      _last[level] = i;
    600600
    … …  
    686686      Item i = _first[_highest_active];
    687687      if (_next[i] != INVALID) {
    688         _prev.set(_next[i], INVALID);
     688        _prev[_next[i]] = INVALID;
    689689        _first[_highest_active] = _next[i];
    690690      } else {
    … …  
    692692        _last[_highest_active] = INVALID;
    693693      }
    694       _level.set(i, ++_highest_active);
     694      _level[i] = ++_highest_active;
    695695      if (_first[_highest_active] == INVALID) {
    696696        _first[_highest_active] = i;
    697697        _last[_highest_active] = i;
    698         _prev.set(i, INVALID);
    699         _next.set(i, INVALID);
    700       } else {
    701         _prev.set(_first[_highest_active], i);
    702         _next.set(i, _first[_highest_active]);
     698        _prev[i] = INVALID;
     699        _next[i] = INVALID;
     700      } else {
     701        _prev[_first[_highest_active]] = i;
     702        _next[i] = _first[_highest_active];
    703703        _first[_highest_active] = i;
    704704      }
    … …  
    715715      Item i = _first[_highest_active];
    716716      if (_next[i] != INVALID) {
    717         _prev.set(_next[i], INVALID);
     717        _prev[_next[i]] = INVALID;
    718718        _first[_highest_active] = _next[i];
    719719      } else {
    … …  
    721721        _last[_highest_active] = INVALID;
    722722      }
    723       _level.set(i, _highest_active = new_level);
     723      _level[i] = _highest_active = new_level;
    724724      if (_first[_highest_active] == INVALID) {
    725725        _first[_highest_active] = _last[_highest_active] = i;
    726         _prev.set(i, INVALID);
    727         _next.set(i, INVALID);
    728       } else {
    729         _prev.set(_first[_highest_active], i);
    730         _next.set(i, _first[_highest_active]);
     726        _prev[i] = INVALID;
     727        _next[i] = INVALID;
     728      } else {
     729        _prev[_first[_highest_active]] = i;
     730        _next[i] = _first[_highest_active];
    731731        _first[_highest_active] = i;
    732732      }
    … …  
    739739    void liftHighestActiveToTop() {
    740740      Item i = _first[_highest_active];
    741       _level.set(i, _max_level);
     741      _level[i] = _max_level;
    742742      if (_next[i] != INVALID) {
    743         _prev.set(_next[i], INVALID);
     743        _prev[_next[i]] = INVALID;
    744744        _first[_highest_active] = _next[i];
    745745      } else {
    … …  
    775775      Item i = _first[l];
    776776      if (_next[i] != INVALID) {
    777         _prev.set(_next[i], INVALID);
     777        _prev[_next[i]] = INVALID;
    778778        _first[l] = _next[i];
    779779      } else {
    … …  
    781781        _last[l] = INVALID;
    782782      }
    783       _level.set(i, ++l);
     783      _level[i] = ++l;
    784784      if (_first[l] == INVALID) {
    785785        _first[l] = _last[l] = i;
    786         _prev.set(i, INVALID);
    787         _next.set(i, INVALID);
    788       } else {
    789         _prev.set(_first[l], i);
    790         _next.set(i, _first[l]);
     786        _prev[i] = INVALID;
     787        _next[i] = INVALID;
     788      } else {
     789        _prev[_first[l]] = i;
     790        _next[i] = _first[l];
    791791        _first[l] = i;
    792792      }
    … …  
    804804      Item i = _first[l];
    805805      if (_next[i] != INVALID) {
    806         _prev.set(_next[i], INVALID);
     806        _prev[_next[i]] = INVALID;
    807807        _first[l] = _next[i];
    808808      } else {
    … …  
    810810        _last[l] = INVALID;
    811811      }
    812       _level.set(i, l = new_level);
     812      _level[i] = l = new_level;
    813813      if (_first[l] == INVALID) {
    814814        _first[l] = _last[l] = i;
    815         _prev.set(i, INVALID);
    816         _next.set(i, INVALID);
    817       } else {
    818         _prev.set(_first[l], i);
    819         _next.set(i, _first[l]);
     815        _prev[i] = INVALID;
     816        _next[i] = INVALID;
     817      } else {
     818        _prev[_first[l]] = i;
     819        _next[i] = _first[l];
    820820        _first[l] = i;
    821821      }
    … …  
    833833      Item i = _first[l];
    834834      if (_next[i] != INVALID) {
    835         _prev.set(_next[i], INVALID);
     835        _prev[_next[i]] = INVALID;
    836836        _first[l] = _next[i];
    837837      } else {
    … …  
    839839        _last[l] = INVALID;
    840840      }
    841       _level.set(i, _max_level);
     841      _level[i] = _max_level;
    842842      if (l == _highest_active) {
    843843        while (_highest_active >= 0 && activeFree(_highest_active))
    … …  
    857857    void lift(Item i, int new_level) {
    858858      if (_next[i] != INVALID) {
    859         _prev.set(_next[i], _prev[i]);
     859        _prev[_next[i]] = _prev[i];
    860860      } else {
    861861        _last[new_level] = _prev[i];
    862862      }
    863863      if (_prev[i] != INVALID) {
    864         _next.set(_prev[i], _next[i]);
     864        _next[_prev[i]] = _next[i];
    865865      } else {
    866866        _first[new_level] = _next[i];
    867867      }
    868       _level.set(i, new_level);
     868      _level[i] = new_level;
    869869      if (_first[new_level] == INVALID) {
    870870        _first[new_level] = _last[new_level] = i;
    871         _prev.set(i, INVALID);
    872         _next.set(i, INVALID);
    873       } else {
    874         _prev.set(_first[new_level], i);
    875         _next.set(i, _first[new_level]);
     871        _prev[i] = INVALID;
     872        _next[i] = INVALID;
     873      } else {
     874        _prev[_first[new_level]] = i;
     875        _next[i] = _first[new_level];
    876876        _first[new_level] = i;
    877877      }
    … …  
    889889    ///\pre The item is on the top level.
    890890    void dirtyTopButOne(Item i) {
    891       _level.set(i, _max_level - 1);
     891      _level[i] = _max_level - 1;
    892892    }
    893893
    … …  
    900900        Item n = _first[i];
    901901        while (n != INVALID) {
    902           _level.set(n, _max_level);
     902          _level[n] = _max_level;
    903903          n = _next[n];
    904904        }
    … …  
    938938      for(typename ItemSetTraits<GR,Item>::ItemIt i(_graph);
    939939          i != INVALID; ++i) {
    940         _level.set(i, _max_level);
    941         _active.set(i, false);
     940        _level[i] = _max_level;
     941        _active[i] = false;
    942942      }
    943943    }
    … …  
    945945    ///Add an item to the current level.
    946946    void initAddItem(Item i) {
    947       _level.set(i, _init_level);
     947      _level[i] = _init_level;
    948948      if (_last[_init_level] == INVALID) {
    949949        _first[_init_level] = i;
    950950        _last[_init_level] = i;
    951         _prev.set(i, INVALID);
    952         _next.set(i, INVALID);
    953       } else {
    954         _prev.set(i, _last[_init_level]);
    955         _next.set(i, INVALID);
    956         _next.set(_last[_init_level], i);
     951        _prev[i] = INVALID;
     952        _next[i] = INVALID;
     953      } else {
     954        _prev[i] = _last[_init_level];
     955        _next[i] = INVALID;
     956        _next[_last[_init_level]] = i;
    957957        _last[_init_level] = i;
    958958      }
Note: See TracChangeset for help on using the changeset viewer.