lemon/core.h
changeset 584 33c6b6e755cd
parent 559 c5fd2d996909
child 617 4137ef9aacc6
equal deleted inserted replaced
13:0d1b228b5e4e 14:6bf3037a46c8
  1313       refresh();
  1313       refresh();
  1314     }
  1314     }
  1315 
  1315 
  1316     virtual void clear() {
  1316     virtual void clear() {
  1317       for(NodeIt n(_g);n!=INVALID;++n) {
  1317       for(NodeIt n(_g);n!=INVALID;++n) {
  1318         _head.set(n, INVALID);
  1318         _head[n] = INVALID;
  1319       }
  1319       }
  1320     }
  1320     }
  1321 
  1321 
  1322     void insert(Arc arc) {
  1322     void insert(Arc arc) {
  1323       Node s = _g.source(arc);
  1323       Node s = _g.source(arc);
  1324       Node t = _g.target(arc);
  1324       Node t = _g.target(arc);
  1325       _left.set(arc, INVALID);
  1325       _left[arc] = INVALID;
  1326       _right.set(arc, INVALID);
  1326       _right[arc] = INVALID;
  1327 
  1327 
  1328       Arc e = _head[s];
  1328       Arc e = _head[s];
  1329       if (e == INVALID) {
  1329       if (e == INVALID) {
  1330         _head.set(s, arc);
  1330         _head[s] = arc;
  1331         _parent.set(arc, INVALID);
  1331         _parent[arc] = INVALID;
  1332         return;
  1332         return;
  1333       }
  1333       }
  1334       while (true) {
  1334       while (true) {
  1335         if (t < _g.target(e)) {
  1335         if (t < _g.target(e)) {
  1336           if (_left[e] == INVALID) {
  1336           if (_left[e] == INVALID) {
  1337             _left.set(e, arc);
  1337             _left[e] = arc;
  1338             _parent.set(arc, e);
  1338             _parent[arc] = e;
  1339             splay(arc);
  1339             splay(arc);
  1340             return;
  1340             return;
  1341           } else {
  1341           } else {
  1342             e = _left[e];
  1342             e = _left[e];
  1343           }
  1343           }
  1344         } else {
  1344         } else {
  1345           if (_right[e] == INVALID) {
  1345           if (_right[e] == INVALID) {
  1346             _right.set(e, arc);
  1346             _right[e] = arc;
  1347             _parent.set(arc, e);
  1347             _parent[arc] = e;
  1348             splay(arc);
  1348             splay(arc);
  1349             return;
  1349             return;
  1350           } else {
  1350           } else {
  1351             e = _right[e];
  1351             e = _right[e];
  1352           }
  1352           }
  1355     }
  1355     }
  1356 
  1356 
  1357     void remove(Arc arc) {
  1357     void remove(Arc arc) {
  1358       if (_left[arc] == INVALID) {
  1358       if (_left[arc] == INVALID) {
  1359         if (_right[arc] != INVALID) {
  1359         if (_right[arc] != INVALID) {
  1360           _parent.set(_right[arc], _parent[arc]);
  1360           _parent[_right[arc]] = _parent[arc];
  1361         }
  1361         }
  1362         if (_parent[arc] != INVALID) {
  1362         if (_parent[arc] != INVALID) {
  1363           if (_left[_parent[arc]] == arc) {
  1363           if (_left[_parent[arc]] == arc) {
  1364             _left.set(_parent[arc], _right[arc]);
  1364             _left[_parent[arc]] = _right[arc];
  1365           } else {
  1365           } else {
  1366             _right.set(_parent[arc], _right[arc]);
  1366             _right[_parent[arc]] = _right[arc];
  1367           }
  1367           }
  1368         } else {
  1368         } else {
  1369           _head.set(_g.source(arc), _right[arc]);
  1369           _head[_g.source(arc)] = _right[arc];
  1370         }
  1370         }
  1371       } else if (_right[arc] == INVALID) {
  1371       } else if (_right[arc] == INVALID) {
  1372         _parent.set(_left[arc], _parent[arc]);
  1372         _parent[_left[arc]] = _parent[arc];
  1373         if (_parent[arc] != INVALID) {
  1373         if (_parent[arc] != INVALID) {
  1374           if (_left[_parent[arc]] == arc) {
  1374           if (_left[_parent[arc]] == arc) {
  1375             _left.set(_parent[arc], _left[arc]);
  1375             _left[_parent[arc]] = _left[arc];
  1376           } else {
  1376           } else {
  1377             _right.set(_parent[arc], _left[arc]);
  1377             _right[_parent[arc]] = _left[arc];
  1378           }
  1378           }
  1379         } else {
  1379         } else {
  1380           _head.set(_g.source(arc), _left[arc]);
  1380           _head[_g.source(arc)] = _left[arc];
  1381         }
  1381         }
  1382       } else {
  1382       } else {
  1383         Arc e = _left[arc];
  1383         Arc e = _left[arc];
  1384         if (_right[e] != INVALID) {
  1384         if (_right[e] != INVALID) {
  1385           e = _right[e];
  1385           e = _right[e];
  1386           while (_right[e] != INVALID) {
  1386           while (_right[e] != INVALID) {
  1387             e = _right[e];
  1387             e = _right[e];
  1388           }
  1388           }
  1389           Arc s = _parent[e];
  1389           Arc s = _parent[e];
  1390           _right.set(_parent[e], _left[e]);
  1390           _right[_parent[e]] = _left[e];
  1391           if (_left[e] != INVALID) {
  1391           if (_left[e] != INVALID) {
  1392             _parent.set(_left[e], _parent[e]);
  1392             _parent[_left[e]] = _parent[e];
  1393           }
  1393           }
  1394 
  1394 
  1395           _left.set(e, _left[arc]);
  1395           _left[e] = _left[arc];
  1396           _parent.set(_left[arc], e);
  1396           _parent[_left[arc]] = e;
  1397           _right.set(e, _right[arc]);
  1397           _right[e] = _right[arc];
  1398           _parent.set(_right[arc], e);
  1398           _parent[_right[arc]] = e;
  1399 
  1399 
  1400           _parent.set(e, _parent[arc]);
  1400           _parent[e] = _parent[arc];
  1401           if (_parent[arc] != INVALID) {
  1401           if (_parent[arc] != INVALID) {
  1402             if (_left[_parent[arc]] == arc) {
  1402             if (_left[_parent[arc]] == arc) {
  1403               _left.set(_parent[arc], e);
  1403               _left[_parent[arc]] = e;
  1404             } else {
  1404             } else {
  1405               _right.set(_parent[arc], e);
  1405               _right[_parent[arc]] = e;
  1406             }
  1406             }
  1407           }
  1407           }
  1408           splay(s);
  1408           splay(s);
  1409         } else {
  1409         } else {
  1410           _right.set(e, _right[arc]);
  1410           _right[e] = _right[arc];
  1411           _parent.set(_right[arc], e);
  1411           _parent[_right[arc]] = e;
  1412           _parent.set(e, _parent[arc]);
  1412           _parent[e] = _parent[arc];
  1413 
  1413 
  1414           if (_parent[arc] != INVALID) {
  1414           if (_parent[arc] != INVALID) {
  1415             if (_left[_parent[arc]] == arc) {
  1415             if (_left[_parent[arc]] == arc) {
  1416               _left.set(_parent[arc], e);
  1416               _left[_parent[arc]] = e;
  1417             } else {
  1417             } else {
  1418               _right.set(_parent[arc], e);
  1418               _right[_parent[arc]] = e;
  1419             }
  1419             }
  1420           } else {
  1420           } else {
  1421             _head.set(_g.source(arc), e);
  1421             _head[_g.source(arc)] = e;
  1422           }
  1422           }
  1423         }
  1423         }
  1424       }
  1424       }
  1425     }
  1425     }
  1426 
  1426 
  1428     {
  1428     {
  1429       int m=(a+b)/2;
  1429       int m=(a+b)/2;
  1430       Arc me=v[m];
  1430       Arc me=v[m];
  1431       if (a < m) {
  1431       if (a < m) {
  1432         Arc left = refreshRec(v,a,m-1);
  1432         Arc left = refreshRec(v,a,m-1);
  1433         _left.set(me, left);
  1433         _left[me] = left;
  1434         _parent.set(left, me);
  1434         _parent[left] = me;
  1435       } else {
  1435       } else {
  1436         _left.set(me, INVALID);
  1436         _left[me] = INVALID;
  1437       }
  1437       }
  1438       if (m < b) {
  1438       if (m < b) {
  1439         Arc right = refreshRec(v,m+1,b);
  1439         Arc right = refreshRec(v,m+1,b);
  1440         _right.set(me, right);
  1440         _right[me] = right;
  1441         _parent.set(right, me);
  1441         _parent[right] = me;
  1442       } else {
  1442       } else {
  1443         _right.set(me, INVALID);
  1443         _right[me] = INVALID;
  1444       }
  1444       }
  1445       return me;
  1445       return me;
  1446     }
  1446     }
  1447 
  1447 
  1448     void refresh() {
  1448     void refresh() {
  1450         std::vector<Arc> v;
  1450         std::vector<Arc> v;
  1451         for(OutArcIt a(_g,n);a!=INVALID;++a) v.push_back(a);
  1451         for(OutArcIt a(_g,n);a!=INVALID;++a) v.push_back(a);
  1452         if (!v.empty()) {
  1452         if (!v.empty()) {
  1453           std::sort(v.begin(),v.end(),ArcLess(_g));
  1453           std::sort(v.begin(),v.end(),ArcLess(_g));
  1454           Arc head = refreshRec(v,0,v.size()-1);
  1454           Arc head = refreshRec(v,0,v.size()-1);
  1455           _head.set(n, head);
  1455           _head[n] = head;
  1456           _parent.set(head, INVALID);
  1456           _parent[head] = INVALID;
  1457         }
  1457         }
  1458         else _head.set(n, INVALID);
  1458         else _head[n] = INVALID;
  1459       }
  1459       }
  1460     }
  1460     }
  1461 
  1461 
  1462     void zig(Arc v) {
  1462     void zig(Arc v) {
  1463       Arc w = _parent[v];
  1463       Arc w = _parent[v];
  1464       _parent.set(v, _parent[w]);
  1464       _parent[v] = _parent[w];
  1465       _parent.set(w, v);
  1465       _parent[w] = v;
  1466       _left.set(w, _right[v]);
  1466       _left[w] = _right[v];
  1467       _right.set(v, w);
  1467       _right[v] = w;
  1468       if (_parent[v] != INVALID) {
  1468       if (_parent[v] != INVALID) {
  1469         if (_right[_parent[v]] == w) {
  1469         if (_right[_parent[v]] == w) {
  1470           _right.set(_parent[v], v);
  1470           _right[_parent[v]] = v;
  1471         } else {
  1471         } else {
  1472           _left.set(_parent[v], v);
  1472           _left[_parent[v]] = v;
  1473         }
  1473         }
  1474       }
  1474       }
  1475       if (_left[w] != INVALID){
  1475       if (_left[w] != INVALID){
  1476         _parent.set(_left[w], w);
  1476         _parent[_left[w]] = w;
  1477       }
  1477       }
  1478     }
  1478     }
  1479 
  1479 
  1480     void zag(Arc v) {
  1480     void zag(Arc v) {
  1481       Arc w = _parent[v];
  1481       Arc w = _parent[v];
  1482       _parent.set(v, _parent[w]);
  1482       _parent[v] = _parent[w];
  1483       _parent.set(w, v);
  1483       _parent[w] = v;
  1484       _right.set(w, _left[v]);
  1484       _right[w] = _left[v];
  1485       _left.set(v, w);
  1485       _left[v] = w;
  1486       if (_parent[v] != INVALID){
  1486       if (_parent[v] != INVALID){
  1487         if (_left[_parent[v]] == w) {
  1487         if (_left[_parent[v]] == w) {
  1488           _left.set(_parent[v], v);
  1488           _left[_parent[v]] = v;
  1489         } else {
  1489         } else {
  1490           _right.set(_parent[v], v);
  1490           _right[_parent[v]] = v;
  1491         }
  1491         }
  1492       }
  1492       }
  1493       if (_right[w] != INVALID){
  1493       if (_right[w] != INVALID){
  1494         _parent.set(_right[w], w);
  1494         _parent[_right[w]] = w;
  1495       }
  1495       }
  1496     }
  1496     }
  1497 
  1497 
  1498     void splay(Arc v) {
  1498     void splay(Arc v) {
  1499       while (_parent[v] != INVALID) {
  1499       while (_parent[v] != INVALID) {