r232:e39056157d24
Wed, 23 Jul 2008 19:21:20
[Not Reviewed]
0 comments (0 inline)
0
1
0
| ... | ... |
@@ -1375,24 +1375,25 @@ |
| 1375 | 1375 |
_parent.set(e, _parent[arc]); |
| 1376 | 1376 |
if (_parent[arc] != INVALID) {
|
| 1377 | 1377 |
if (_left[_parent[arc]] == arc) {
|
| 1378 | 1378 |
_left.set(_parent[arc], e); |
| 1379 | 1379 |
} else {
|
| 1380 | 1380 |
_right.set(_parent[arc], e); |
| 1381 | 1381 |
} |
| 1382 | 1382 |
} |
| 1383 | 1383 |
splay(s); |
| 1384 | 1384 |
} else {
|
| 1385 | 1385 |
_right.set(e, _right[arc]); |
| 1386 | 1386 |
_parent.set(_right[arc], e); |
| 1387 |
_parent.set(e, _parent[arc]); |
|
| 1387 | 1388 |
|
| 1388 | 1389 |
if (_parent[arc] != INVALID) {
|
| 1389 | 1390 |
if (_left[_parent[arc]] == arc) {
|
| 1390 | 1391 |
_left.set(_parent[arc], e); |
| 1391 | 1392 |
} else {
|
| 1392 | 1393 |
_right.set(_parent[arc], e); |
| 1393 | 1394 |
} |
| 1394 | 1395 |
} else {
|
| 1395 | 1396 |
_head.set(_g.source(arc), e); |
| 1396 | 1397 |
} |
| 1397 | 1398 |
} |
| 1398 | 1399 |
} |
| ... | ... |
@@ -1505,24 +1506,25 @@ |
| 1505 | 1506 |
|
| 1506 | 1507 |
///Find an arc between two nodes. |
| 1507 | 1508 |
|
| 1508 | 1509 |
///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where |
| 1509 | 1510 |
/// <em>d</em> is the number of outgoing arcs of \c s. |
| 1510 | 1511 |
///\param s The source node |
| 1511 | 1512 |
///\param t The target node |
| 1512 | 1513 |
///\return An arc from \c s to \c t if there exists, |
| 1513 | 1514 |
///\ref INVALID otherwise. |
| 1514 | 1515 |
Arc operator()(Node s, Node t) const |
| 1515 | 1516 |
{
|
| 1516 | 1517 |
Arc a = _head[s]; |
| 1518 |
if (a == INVALID) return INVALID; |
|
| 1517 | 1519 |
while (true) {
|
| 1518 | 1520 |
if (_g.target(a) == t) {
|
| 1519 | 1521 |
const_cast<DynArcLookUp&>(*this).splay(a); |
| 1520 | 1522 |
return a; |
| 1521 | 1523 |
} else if (t < _g.target(a)) {
|
| 1522 | 1524 |
if (_left[a] == INVALID) {
|
| 1523 | 1525 |
const_cast<DynArcLookUp&>(*this).splay(a); |
| 1524 | 1526 |
return INVALID; |
| 1525 | 1527 |
} else {
|
| 1526 | 1528 |
a = _left[a]; |
| 1527 | 1529 |
} |
| 1528 | 1530 |
} else {
|
| ... | ... |
@@ -1539,24 +1541,25 @@ |
| 1539 | 1541 |
///Find the first arc between two nodes. |
| 1540 | 1542 |
|
| 1541 | 1543 |
///Find the first arc between two nodes in time |
| 1542 | 1544 |
/// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of |
| 1543 | 1545 |
/// outgoing arcs of \c s. |
| 1544 | 1546 |
///\param s The source node |
| 1545 | 1547 |
///\param t The target node |
| 1546 | 1548 |
///\return An arc from \c s to \c t if there exists, \ref INVALID |
| 1547 | 1549 |
/// otherwise. |
| 1548 | 1550 |
Arc findFirst(Node s, Node t) const |
| 1549 | 1551 |
{
|
| 1550 | 1552 |
Arc a = _head[s]; |
| 1553 |
if (a == INVALID) return INVALID; |
|
| 1551 | 1554 |
Arc r = INVALID; |
| 1552 | 1555 |
while (true) {
|
| 1553 | 1556 |
if (_g.target(a) < t) {
|
| 1554 | 1557 |
if (_right[a] == INVALID) {
|
| 1555 | 1558 |
const_cast<DynArcLookUp&>(*this).splay(a); |
| 1556 | 1559 |
return r; |
| 1557 | 1560 |
} else {
|
| 1558 | 1561 |
a = _right[a]; |
| 1559 | 1562 |
} |
| 1560 | 1563 |
} else {
|
| 1561 | 1564 |
if (_g.target(a) == t) {
|
| 1562 | 1565 |
r = a; |
0 comments (0 inline)