LEMON/LEMON-official Changeset - r232:e39056157d24

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r232:e39056157d24

« 231:9ce7a0

233:282392 »

r232:e39056157d24

Wed, 23 Jul 2008 19:21:20

[Not Reviewed]

0 comments (0 inline)

deba@inf.elte.hu
deba@inf.elte.hu

Two bug fixes in DynArcLookUp

0 1 0

default

1 file changed with 3 insertions and 0 deletions:

lemon/core.h

↑ Collapse diff ↑

lemon/core.h

Show inline comments

@@ -1323,128 +1323,129 @@
            splay(arc);
            return;
          } else {
            e = _right[e];
          }
        }
      }
    }

    void remove(Arc arc) {
      if (_left[arc] == INVALID) {
        if (_right[arc] != INVALID) {
          _parent.set(_right[arc], _parent[arc]);
        }
        if (_parent[arc] != INVALID) {
          if (_left[_parent[arc]] == arc) {
            _left.set(_parent[arc], _right[arc]);
          } else {
            _right.set(_parent[arc], _right[arc]);
          }
        } else {
          _head.set(_g.source(arc), _right[arc]);
        }
      } else if (_right[arc] == INVALID) {
        _parent.set(_left[arc], _parent[arc]);
        if (_parent[arc] != INVALID) {
          if (_left[_parent[arc]] == arc) {
            _left.set(_parent[arc], _left[arc]);
          } else {
            _right.set(_parent[arc], _left[arc]);
          }
        } else {
          _head.set(_g.source(arc), _left[arc]);
        }
      } else {
        Arc e = _left[arc];
        if (_right[e] != INVALID) {
          e = _right[e];
          while (_right[e] != INVALID) {
            e = _right[e];
          }
          Arc s = _parent[e];
          _right.set(_parent[e], _left[e]);
          if (_left[e] != INVALID) {
            _parent.set(_left[e], _parent[e]);
          }

          _left.set(e, _left[arc]);
          _parent.set(_left[arc], e);
          _right.set(e, _right[arc]);
          _parent.set(_right[arc], e);

          _parent.set(e, _parent[arc]);
          if (_parent[arc] != INVALID) {
            if (_left[_parent[arc]] == arc) {
              _left.set(_parent[arc], e);
            } else {
              _right.set(_parent[arc], e);
            }
          }
          splay(s);
        } else {
          _right.set(e, _right[arc]);
          _parent.set(_right[arc], e);
          _parent.set(e, _parent[arc]);

          if (_parent[arc] != INVALID) {
            if (_left[_parent[arc]] == arc) {
              _left.set(_parent[arc], e);
            } else {
              _right.set(_parent[arc], e);
            }
          } else {
            _head.set(_g.source(arc), e);
          }
        }
      }
    }

    Arc refreshRec(std::vector<Arc> &v,int a,int b)
    {
      int m=(a+b)/2;
      Arc me=v[m];
      if (a < m) {
        Arc left = refreshRec(v,a,m-1);
        _left.set(me, left);
        _parent.set(left, me);
      } else {
        _left.set(me, INVALID);
      }
      if (m < b) {
        Arc right = refreshRec(v,m+1,b);
        _right.set(me, right);
        _parent.set(right, me);
      } else {
        _right.set(me, INVALID);
      }
      return me;
    }

    void refresh() {
      for(NodeIt n(_g);n!=INVALID;++n) {
        std::vector<Arc> v;
        for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
        if(v.size()) {
          std::sort(v.begin(),v.end(),ArcLess(_g));
          Arc head = refreshRec(v,0,v.size()-1);
          _head.set(n, head);
          _parent.set(head, INVALID);
        }
        else _head.set(n, INVALID);
      }
    }

    void zig(Arc v) {
      Arc w = _parent[v];
      _parent.set(v, _parent[w]);
      _parent.set(w, v);
      _left.set(w, _right[v]);
      _right.set(v, w);
      if (_parent[v] != INVALID) {
        if (_right[_parent[v]] == w) {
          _right.set(_parent[v], v);
        } else {
          _left.set(_parent[v], v);
        }
      }
      if (_left[w] != INVALID){
        _parent.set(_left[w], w);
@@ -1453,162 +1454,164 @@

    void zag(Arc v) {
      Arc w = _parent[v];
      _parent.set(v, _parent[w]);
      _parent.set(w, v);
      _right.set(w, _left[v]);
      _left.set(v, w);
      if (_parent[v] != INVALID){
        if (_left[_parent[v]] == w) {
          _left.set(_parent[v], v);
        } else {
          _right.set(_parent[v], v);
        }
      }
      if (_right[w] != INVALID){
        _parent.set(_right[w], w);
      }
    }

    void splay(Arc v) {
      while (_parent[v] != INVALID) {
        if (v == _left[_parent[v]]) {
          if (_parent[_parent[v]] == INVALID) {
            zig(v);
          } else {
            if (_parent[v] == _left[_parent[_parent[v]]]) {
              zig(_parent[v]);
              zig(v);
            } else {
              zig(v);
              zag(v);
            }
          }
        } else {
          if (_parent[_parent[v]] == INVALID) {
            zag(v);
          } else {
            if (_parent[v] == _left[_parent[_parent[v]]]) {
              zag(v);
              zig(v);
            } else {
              zag(_parent[v]);
              zag(v);
            }
          }
        }
      }
      _head[_g.source(v)] = v;
    }


  public:

    ///Find an arc between two nodes.

    ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where
    /// <em>d</em> is the number of outgoing arcs of \c s.
    ///\param s The source node
    ///\param t The target node
    ///\return An arc from \c s to \c t if there exists,
    ///\ref INVALID otherwise.
    Arc operator()(Node s, Node t) const
    {
      Arc a = _head[s];
      if (a == INVALID) return INVALID;
      while (true) {
        if (_g.target(a) == t) {
          const_cast<DynArcLookUp&>(*this).splay(a);
          return a;
        } else if (t < _g.target(a)) {
          if (_left[a] == INVALID) {
            const_cast<DynArcLookUp&>(*this).splay(a);
            return INVALID;
          } else {
            a = _left[a];
          }
        } else  {
          if (_right[a] == INVALID) {
            const_cast<DynArcLookUp&>(*this).splay(a);
            return INVALID;
          } else {
            a = _right[a];
          }
        }
      }
    }

    ///Find the first arc between two nodes.

    ///Find the first arc between two nodes in time
    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
    /// outgoing arcs of \c s.
    ///\param s The source node
    ///\param t The target node
    ///\return An arc from \c s to \c t if there exists, \ref INVALID
    /// otherwise.
    Arc findFirst(Node s, Node t) const
    {
      Arc a = _head[s];
      if (a == INVALID) return INVALID;
      Arc r = INVALID;
      while (true) {
        if (_g.target(a) < t) {
          if (_right[a] == INVALID) {
            const_cast<DynArcLookUp&>(*this).splay(a);
            return r;
          } else {
            a = _right[a];
          }
        } else {
          if (_g.target(a) == t) {
            r = a;
          }
          if (_left[a] == INVALID) {
            const_cast<DynArcLookUp&>(*this).splay(a);
            return r;
          } else {
            a = _left[a];
          }
        }
      }
    }

    ///Find the next arc between two nodes.

    ///Find the next arc between two nodes in time
    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
    /// outgoing arcs of \c s.
    ///\param s The source node
    ///\param t The target node
    ///\return An arc from \c s to \c t if there exists, \ref INVALID
    /// otherwise.

    ///\note If \c e is not the result of the previous \c findFirst()
    ///operation then the amorized time bound can not be guaranteed.
#ifdef DOXYGEN
    Arc findNext(Node s, Node t, Arc a) const
#else
    Arc findNext(Node, Node t, Arc a) const
#endif
    {
      if (_right[a] != INVALID) {
        a = _right[a];
        while (_left[a] != INVALID) {
          a = _left[a];
        }
        const_cast<DynArcLookUp&>(*this).splay(a);
      } else {
        while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {
          a = _parent[a];
        }
        if (_parent[a] == INVALID) {
          return INVALID;
        } else {
          a = _parent[a];
          const_cast<DynArcLookUp&>(*this).splay(a);
        }
      }
      if (_g.target(a) == t) return a;
      else return INVALID;
    }

  };


0 comments (0 inline)

RhodeCode

Login to your account

...	...	@@ -1323,128 +1323,129 @@
1323	1323	splay(arc);
1324	1324	return;
1325	1325	} else {
1326	1326	e = _right[e];
1327	1327	}
1328	1328	}
1329	1329	}
1330	1330	}
1331	1331
1332	1332	void remove(Arc arc) {
1333	1333	if (_left[arc] == INVALID) {
1334	1334	if (_right[arc] != INVALID) {
1335	1335	_parent.set(_right[arc], _parent[arc]);
1336	1336	}
1337	1337	if (_parent[arc] != INVALID) {
1338	1338	if (_left[_parent[arc]] == arc) {
1339	1339	_left.set(_parent[arc], _right[arc]);
1340	1340	} else {
1341	1341	_right.set(_parent[arc], _right[arc]);
1342	1342	}
1343	1343	} else {
1344	1344	_head.set(_g.source(arc), _right[arc]);
1345	1345	}
1346	1346	} else if (_right[arc] == INVALID) {
1347	1347	_parent.set(_left[arc], _parent[arc]);
1348	1348	if (_parent[arc] != INVALID) {
1349	1349	if (_left[_parent[arc]] == arc) {
1350	1350	_left.set(_parent[arc], _left[arc]);
1351	1351	} else {
1352	1352	_right.set(_parent[arc], _left[arc]);
1353	1353	}
1354	1354	} else {
1355	1355	_head.set(_g.source(arc), _left[arc]);
1356	1356	}
1357	1357	} else {
1358	1358	Arc e = _left[arc];
1359	1359	if (_right[e] != INVALID) {
1360	1360	e = _right[e];
1361	1361	while (_right[e] != INVALID) {
1362	1362	e = _right[e];
1363	1363	}
1364	1364	Arc s = _parent[e];
1365	1365	_right.set(_parent[e], _left[e]);
1366	1366	if (_left[e] != INVALID) {
1367	1367	_parent.set(_left[e], _parent[e]);
1368	1368	}
1369	1369
1370	1370	_left.set(e, _left[arc]);
1371	1371	_parent.set(_left[arc], e);
1372	1372	_right.set(e, _right[arc]);
1373	1373	_parent.set(_right[arc], e);
1374	1374
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	}
1399	1400	}
1400	1401
1401	1402	Arc refreshRec(std::vector<Arc> &v,int a,int b)
1402	1403	{
1403	1404	int m=(a+b)/2;
1404	1405	Arc me=v[m];
1405	1406	if (a < m) {
1406	1407	Arc left = refreshRec(v,a,m-1);
1407	1408	_left.set(me, left);
1408	1409	_parent.set(left, me);
1409	1410	} else {
1410	1411	_left.set(me, INVALID);
1411	1412	}
1412	1413	if (m < b) {
1413	1414	Arc right = refreshRec(v,m+1,b);
1414	1415	_right.set(me, right);
1415	1416	_parent.set(right, me);
1416	1417	} else {
1417	1418	_right.set(me, INVALID);
1418	1419	}
1419	1420	return me;
1420	1421	}
1421	1422
1422	1423	void refresh() {
1423	1424	for(NodeIt n(_g);n!=INVALID;++n) {
1424	1425	std::vector<Arc> v;
1425	1426	for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);
1426	1427	if(v.size()) {
1427	1428	std::sort(v.begin(),v.end(),ArcLess(_g));
1428	1429	Arc head = refreshRec(v,0,v.size()-1);
1429	1430	_head.set(n, head);
1430	1431	_parent.set(head, INVALID);
1431	1432	}
1432	1433	else _head.set(n, INVALID);
1433	1434	}
1434	1435	}
1435	1436
1436	1437	void zig(Arc v) {
1437	1438	Arc w = _parent[v];
1438	1439	_parent.set(v, _parent[w]);
1439	1440	_parent.set(w, v);
1440	1441	_left.set(w, _right[v]);
1441	1442	_right.set(v, w);
1442	1443	if (_parent[v] != INVALID) {
1443	1444	if (_right[_parent[v]] == w) {
1444	1445	_right.set(_parent[v], v);
1445	1446	} else {
1446	1447	_left.set(_parent[v], v);
1447	1448	}
1448	1449	}
1449	1450	if (_left[w] != INVALID){
1450	1451	_parent.set(_left[w], w);
...	...	@@ -1453,162 +1454,164 @@
1453	1454
1454	1455	void zag(Arc v) {
1455	1456	Arc w = _parent[v];
1456	1457	_parent.set(v, _parent[w]);
1457	1458	_parent.set(w, v);
1458	1459	_right.set(w, _left[v]);
1459	1460	_left.set(v, w);
1460	1461	if (_parent[v] != INVALID){
1461	1462	if (_left[_parent[v]] == w) {
1462	1463	_left.set(_parent[v], v);
1463	1464	} else {
1464	1465	_right.set(_parent[v], v);
1465	1466	}
1466	1467	}
1467	1468	if (_right[w] != INVALID){
1468	1469	_parent.set(_right[w], w);
1469	1470	}
1470	1471	}
1471	1472
1472	1473	void splay(Arc v) {
1473	1474	while (_parent[v] != INVALID) {
1474	1475	if (v == _left[_parent[v]]) {
1475	1476	if (_parent[_parent[v]] == INVALID) {
1476	1477	zig(v);
1477	1478	} else {
1478	1479	if (_parent[v] == _left[_parent[_parent[v]]]) {
1479	1480	zig(_parent[v]);
1480	1481	zig(v);
1481	1482	} else {
1482	1483	zig(v);
1483	1484	zag(v);
1484	1485	}
1485	1486	}
1486	1487	} else {
1487	1488	if (_parent[_parent[v]] == INVALID) {
1488	1489	zag(v);
1489	1490	} else {
1490	1491	if (_parent[v] == _left[_parent[_parent[v]]]) {
1491	1492	zag(v);
1492	1493	zig(v);
1493	1494	} else {
1494	1495	zag(_parent[v]);
1495	1496	zag(v);
1496	1497	}
1497	1498	}
1498	1499	}
1499	1500	}
1500	1501	_head[_g.source(v)] = v;
1501	1502	}
1502	1503
1503	1504
1504	1505	public:
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 {
1529	1531	if (_right[a] == INVALID) {
1530	1532	const_cast<DynArcLookUp&>(*this).splay(a);
1531	1533	return INVALID;
1532	1534	} else {
1533	1535	a = _right[a];
1534	1536	}
1535	1537	}
1536	1538	}
1537	1539	}
1538	1540
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;
1563	1566	}
1564	1567	if (_left[a] == INVALID) {
1565	1568	const_cast<DynArcLookUp&>(*this).splay(a);
1566	1569	return r;
1567	1570	} else {
1568	1571	a = _left[a];
1569	1572	}
1570	1573	}
1571	1574	}
1572	1575	}
1573	1576
1574	1577	///Find the next arc between two nodes.
1575	1578
1576	1579	///Find the next arc between two nodes in time
1577	1580	/// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of
1578	1581	/// outgoing arcs of \c s.
1579	1582	///\param s The source node
1580	1583	///\param t The target node
1581	1584	///\return An arc from \c s to \c t if there exists, \ref INVALID
1582	1585	/// otherwise.
1583	1586
1584	1587	///\note If \c e is not the result of the previous \c findFirst()
1585	1588	///operation then the amorized time bound can not be guaranteed.
1586	1589	#ifdef DOXYGEN
1587	1590	Arc findNext(Node s, Node t, Arc a) const
1588	1591	#else
1589	1592	Arc findNext(Node, Node t, Arc a) const
1590	1593	#endif
1591	1594	{
1592	1595	if (_right[a] != INVALID) {
1593	1596	a = _right[a];
1594	1597	while (_left[a] != INVALID) {
1595	1598	a = _left[a];
1596	1599	}
1597	1600	const_cast<DynArcLookUp&>(*this).splay(a);
1598	1601	} else {
1599	1602	while (_parent[a] != INVALID && _right[_parent[a]] == a) {
1600	1603	a = _parent[a];
1601	1604	}
1602	1605	if (_parent[a] == INVALID) {
1603	1606	return INVALID;
1604	1607	} else {
1605	1608	a = _parent[a];
1606	1609	const_cast<DynArcLookUp&>(*this).splay(a);
1607	1610	}
1608	1611	}
1609	1612	if (_g.target(a) == t) return a;
1610	1613	else return INVALID;
1611	1614	}
1612	1615
1613	1616	};
1614	1617