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) { |