Changeset 628:aa1804409f29 in lemon for lemon/core.h
 Timestamp:
 04/14/09 10:35:38 (12 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/core.h
r606 r628 1316 1316 virtual void clear() { 1317 1317 for(NodeIt n(_g);n!=INVALID;++n) { 1318 _head .set(n, INVALID);1318 _head[n] = INVALID; 1319 1319 } 1320 1320 } … … 1323 1323 Node s = _g.source(arc); 1324 1324 Node t = _g.target(arc); 1325 _left .set(arc, INVALID);1326 _right .set(arc, INVALID);1325 _left[arc] = INVALID; 1326 _right[arc] = INVALID; 1327 1327 1328 1328 Arc e = _head[s]; 1329 1329 if (e == INVALID) { 1330 _head .set(s, arc);1331 _parent .set(arc, INVALID);1330 _head[s] = arc; 1331 _parent[arc] = INVALID; 1332 1332 return; 1333 1333 } … … 1335 1335 if (t < _g.target(e)) { 1336 1336 if (_left[e] == INVALID) { 1337 _left .set(e, arc);1338 _parent .set(arc, e);1337 _left[e] = arc; 1338 _parent[arc] = e; 1339 1339 splay(arc); 1340 1340 return; … … 1344 1344 } else { 1345 1345 if (_right[e] == INVALID) { 1346 _right .set(e, arc);1347 _parent .set(arc, e);1346 _right[e] = arc; 1347 _parent[arc] = e; 1348 1348 splay(arc); 1349 1349 return; … … 1358 1358 if (_left[arc] == INVALID) { 1359 1359 if (_right[arc] != INVALID) { 1360 _parent .set(_right[arc], _parent[arc]);1360 _parent[_right[arc]] = _parent[arc]; 1361 1361 } 1362 1362 if (_parent[arc] != INVALID) { 1363 1363 if (_left[_parent[arc]] == arc) { 1364 _left .set(_parent[arc], _right[arc]);1364 _left[_parent[arc]] = _right[arc]; 1365 1365 } else { 1366 _right .set(_parent[arc], _right[arc]);1366 _right[_parent[arc]] = _right[arc]; 1367 1367 } 1368 1368 } else { 1369 _head .set(_g.source(arc), _right[arc]);1369 _head[_g.source(arc)] = _right[arc]; 1370 1370 } 1371 1371 } else if (_right[arc] == INVALID) { 1372 _parent .set(_left[arc], _parent[arc]);1372 _parent[_left[arc]] = _parent[arc]; 1373 1373 if (_parent[arc] != INVALID) { 1374 1374 if (_left[_parent[arc]] == arc) { 1375 _left .set(_parent[arc], _left[arc]);1375 _left[_parent[arc]] = _left[arc]; 1376 1376 } else { 1377 _right .set(_parent[arc], _left[arc]);1377 _right[_parent[arc]] = _left[arc]; 1378 1378 } 1379 1379 } else { 1380 _head .set(_g.source(arc), _left[arc]);1380 _head[_g.source(arc)] = _left[arc]; 1381 1381 } 1382 1382 } else { … … 1388 1388 } 1389 1389 Arc s = _parent[e]; 1390 _right .set(_parent[e], _left[e]);1390 _right[_parent[e]] = _left[e]; 1391 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]);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]; 1401 1401 if (_parent[arc] != INVALID) { 1402 1402 if (_left[_parent[arc]] == arc) { 1403 _left .set(_parent[arc], e);1403 _left[_parent[arc]] = e; 1404 1404 } else { 1405 _right .set(_parent[arc], e);1405 _right[_parent[arc]] = e; 1406 1406 } 1407 1407 } 1408 1408 splay(s); 1409 1409 } 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]; 1413 1413 1414 1414 if (_parent[arc] != INVALID) { 1415 1415 if (_left[_parent[arc]] == arc) { 1416 _left .set(_parent[arc], e);1416 _left[_parent[arc]] = e; 1417 1417 } else { 1418 _right .set(_parent[arc], e);1418 _right[_parent[arc]] = e; 1419 1419 } 1420 1420 } else { 1421 _head .set(_g.source(arc), e);1421 _head[_g.source(arc)] = e; 1422 1422 } 1423 1423 } … … 1431 1431 if (a < m) { 1432 1432 Arc left = refreshRec(v,a,m1); 1433 _left .set(me, left);1434 _parent .set(left, me);1433 _left[me] = left; 1434 _parent[left] = me; 1435 1435 } else { 1436 _left .set(me, INVALID);1436 _left[me] = INVALID; 1437 1437 } 1438 1438 if (m < b) { 1439 1439 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; 1442 1442 } else { 1443 _right .set(me, INVALID);1443 _right[me] = INVALID; 1444 1444 } 1445 1445 return me; … … 1453 1453 std::sort(v.begin(),v.end(),ArcLess(_g)); 1454 1454 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; 1459 1459 } 1460 1460 } … … 1462 1462 void zig(Arc v) { 1463 1463 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; 1468 1468 if (_parent[v] != INVALID) { 1469 1469 if (_right[_parent[v]] == w) { 1470 _right .set(_parent[v], v);1470 _right[_parent[v]] = v; 1471 1471 } else { 1472 _left .set(_parent[v], v);1472 _left[_parent[v]] = v; 1473 1473 } 1474 1474 } 1475 1475 if (_left[w] != INVALID){ 1476 _parent .set(_left[w], w);1476 _parent[_left[w]] = w; 1477 1477 } 1478 1478 } … … 1480 1480 void zag(Arc v) { 1481 1481 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; 1486 1486 if (_parent[v] != INVALID){ 1487 1487 if (_left[_parent[v]] == w) { 1488 _left .set(_parent[v], v);1488 _left[_parent[v]] = v; 1489 1489 } else { 1490 _right .set(_parent[v], v);1490 _right[_parent[v]] = v; 1491 1491 } 1492 1492 } 1493 1493 if (_right[w] != INVALID){ 1494 _parent .set(_right[w], w);1494 _parent[_right[w]] = w; 1495 1495 } 1496 1496 }
Note: See TracChangeset
for help on using the changeset viewer.