COIN-OR::LEMON - Graph Library

Changeset 581:aa1804409f29 in lemon-1.2 for lemon/core.h


Ignore:
Timestamp:
04/14/09 10:35:38 (11 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/core.h

    r559 r581  
    13161316    virtual void clear() {
    13171317      for(NodeIt n(_g);n!=INVALID;++n) {
    1318         _head.set(n, INVALID);
     1318        _head[n] = INVALID;
    13191319      }
    13201320    }
     
    13231323      Node s = _g.source(arc);
    13241324      Node t = _g.target(arc);
    1325       _left.set(arc, INVALID);
    1326       _right.set(arc, INVALID);
     1325      _left[arc] = INVALID;
     1326      _right[arc] = INVALID;
    13271327
    13281328      Arc e = _head[s];
    13291329      if (e == INVALID) {
    1330         _head.set(s, arc);
    1331         _parent.set(arc, INVALID);
     1330        _head[s] = arc;
     1331        _parent[arc] = INVALID;
    13321332        return;
    13331333      }
     
    13351335        if (t < _g.target(e)) {
    13361336          if (_left[e] == INVALID) {
    1337             _left.set(e, arc);
    1338             _parent.set(arc, e);
     1337            _left[e] = arc;
     1338            _parent[arc] = e;
    13391339            splay(arc);
    13401340            return;
     
    13441344        } else {
    13451345          if (_right[e] == INVALID) {
    1346             _right.set(e, arc);
    1347             _parent.set(arc, e);
     1346            _right[e] = arc;
     1347            _parent[arc] = e;
    13481348            splay(arc);
    13491349            return;
     
    13581358      if (_left[arc] == INVALID) {
    13591359        if (_right[arc] != INVALID) {
    1360           _parent.set(_right[arc], _parent[arc]);
     1360          _parent[_right[arc]] = _parent[arc];
    13611361        }
    13621362        if (_parent[arc] != INVALID) {
    13631363          if (_left[_parent[arc]] == arc) {
    1364             _left.set(_parent[arc], _right[arc]);
     1364            _left[_parent[arc]] = _right[arc];
    13651365          } else {
    1366             _right.set(_parent[arc], _right[arc]);
     1366            _right[_parent[arc]] = _right[arc];
    13671367          }
    13681368        } else {
    1369           _head.set(_g.source(arc), _right[arc]);
     1369          _head[_g.source(arc)] = _right[arc];
    13701370        }
    13711371      } else if (_right[arc] == INVALID) {
    1372         _parent.set(_left[arc], _parent[arc]);
     1372        _parent[_left[arc]] = _parent[arc];
    13731373        if (_parent[arc] != INVALID) {
    13741374          if (_left[_parent[arc]] == arc) {
    1375             _left.set(_parent[arc], _left[arc]);
     1375            _left[_parent[arc]] = _left[arc];
    13761376          } else {
    1377             _right.set(_parent[arc], _left[arc]);
     1377            _right[_parent[arc]] = _left[arc];
    13781378          }
    13791379        } else {
    1380           _head.set(_g.source(arc), _left[arc]);
     1380          _head[_g.source(arc)] = _left[arc];
    13811381        }
    13821382      } else {
     
    13881388          }
    13891389          Arc s = _parent[e];
    1390           _right.set(_parent[e], _left[e]);
     1390          _right[_parent[e]] = _left[e];
    13911391          if (_left[e] != INVALID) {
    1392             _parent.set(_left[e], _parent[e]);
     1392            _parent[_left[e]] = _parent[e];
    13931393          }
    13941394
    1395           _left.set(e, _left[arc]);
    1396           _parent.set(_left[arc], e);
    1397           _right.set(e, _right[arc]);
    1398           _parent.set(_right[arc], e);
    1399 
    1400           _parent.set(e, _parent[arc]);
     1395          _left[e] = _left[arc];
     1396          _parent[_left[arc]] = e;
     1397          _right[e] = _right[arc];
     1398          _parent[_right[arc]] = e;
     1399
     1400          _parent[e] = _parent[arc];
    14011401          if (_parent[arc] != INVALID) {
    14021402            if (_left[_parent[arc]] == arc) {
    1403               _left.set(_parent[arc], e);
     1403              _left[_parent[arc]] = e;
    14041404            } else {
    1405               _right.set(_parent[arc], e);
     1405              _right[_parent[arc]] = e;
    14061406            }
    14071407          }
    14081408          splay(s);
    14091409        } else {
    1410           _right.set(e, _right[arc]);
    1411           _parent.set(_right[arc], e);
    1412           _parent.set(e, _parent[arc]);
     1410          _right[e] = _right[arc];
     1411          _parent[_right[arc]] = e;
     1412          _parent[e] = _parent[arc];
    14131413
    14141414          if (_parent[arc] != INVALID) {
    14151415            if (_left[_parent[arc]] == arc) {
    1416               _left.set(_parent[arc], e);
     1416              _left[_parent[arc]] = e;
    14171417            } else {
    1418               _right.set(_parent[arc], e);
     1418              _right[_parent[arc]] = e;
    14191419            }
    14201420          } else {
    1421             _head.set(_g.source(arc), e);
     1421            _head[_g.source(arc)] = e;
    14221422          }
    14231423        }
     
    14311431      if (a < m) {
    14321432        Arc left = refreshRec(v,a,m-1);
    1433         _left.set(me, left);
    1434         _parent.set(left, me);
     1433        _left[me] = left;
     1434        _parent[left] = me;
    14351435      } else {
    1436         _left.set(me, INVALID);
     1436        _left[me] = INVALID;
    14371437      }
    14381438      if (m < b) {
    14391439        Arc right = refreshRec(v,m+1,b);
    1440         _right.set(me, right);
    1441         _parent.set(right, me);
     1440        _right[me] = right;
     1441        _parent[right] = me;
    14421442      } else {
    1443         _right.set(me, INVALID);
     1443        _right[me] = INVALID;
    14441444      }
    14451445      return me;
     
    14531453          std::sort(v.begin(),v.end(),ArcLess(_g));
    14541454          Arc head = refreshRec(v,0,v.size()-1);
    1455           _head.set(n, head);
    1456           _parent.set(head, INVALID);
    1457         }
    1458         else _head.set(n, INVALID);
     1455          _head[n] = head;
     1456          _parent[head] = INVALID;
     1457        }
     1458        else _head[n] = INVALID;
    14591459      }
    14601460    }
     
    14621462    void zig(Arc v) {
    14631463      Arc w = _parent[v];
    1464       _parent.set(v, _parent[w]);
    1465       _parent.set(w, v);
    1466       _left.set(w, _right[v]);
    1467       _right.set(v, w);
     1464      _parent[v] = _parent[w];
     1465      _parent[w] = v;
     1466      _left[w] = _right[v];
     1467      _right[v] = w;
    14681468      if (_parent[v] != INVALID) {
    14691469        if (_right[_parent[v]] == w) {
    1470           _right.set(_parent[v], v);
     1470          _right[_parent[v]] = v;
    14711471        } else {
    1472           _left.set(_parent[v], v);
     1472          _left[_parent[v]] = v;
    14731473        }
    14741474      }
    14751475      if (_left[w] != INVALID){
    1476         _parent.set(_left[w], w);
     1476        _parent[_left[w]] = w;
    14771477      }
    14781478    }
     
    14801480    void zag(Arc v) {
    14811481      Arc w = _parent[v];
    1482       _parent.set(v, _parent[w]);
    1483       _parent.set(w, v);
    1484       _right.set(w, _left[v]);
    1485       _left.set(v, w);
     1482      _parent[v] = _parent[w];
     1483      _parent[w] = v;
     1484      _right[w] = _left[v];
     1485      _left[v] = w;
    14861486      if (_parent[v] != INVALID){
    14871487        if (_left[_parent[v]] == w) {
    1488           _left.set(_parent[v], v);
     1488          _left[_parent[v]] = v;
    14891489        } else {
    1490           _right.set(_parent[v], v);
     1490          _right[_parent[v]] = v;
    14911491        }
    14921492      }
    14931493      if (_right[w] != INVALID){
    1494         _parent.set(_right[w], w);
     1494        _parent[_right[w]] = w;
    14951495      }
    14961496    }
Note: See TracChangeset for help on using the changeset viewer.