Changes in lemon/core.h [535:6a17a722b50e:581:aa1804409f29] in lemon-1.2
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/core.h
r535 r581 1035 1035 ///\sa findArc() 1036 1036 ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp 1037 template <typename _Graph>1038 class ConArcIt : public _Graph::Arc {1037 template <typename GR> 1038 class ConArcIt : public GR::Arc { 1039 1039 public: 1040 1040 1041 typedef _GraphGraph;1041 typedef GR Graph; 1042 1042 typedef typename Graph::Arc Parent; 1043 1043 … … 1158 1158 /// 1159 1159 ///\sa findEdge() 1160 template <typename _Graph>1161 class ConEdgeIt : public _Graph::Edge {1160 template <typename GR> 1161 class ConEdgeIt : public GR::Edge { 1162 1162 public: 1163 1163 1164 typedef _GraphGraph;1164 typedef GR Graph; 1165 1165 typedef typename Graph::Edge Parent; 1166 1166 … … 1212 1212 ///queries. 1213 1213 /// 1214 ///\tparam G The type of the underlying digraph.1214 ///\tparam GR The type of the underlying digraph. 1215 1215 /// 1216 1216 ///\sa ArcLookUp 1217 1217 ///\sa AllArcLookUp 1218 template <class G>1218 template <typename GR> 1219 1219 class DynArcLookUp 1220 : protected ItemSetTraits<G , typename G::Arc>::ItemNotifier::ObserverBase1220 : protected ItemSetTraits<GR, typename GR::Arc>::ItemNotifier::ObserverBase 1221 1221 { 1222 1222 public: 1223 typedef typename ItemSetTraits<G , typename G::Arc>1223 typedef typename ItemSetTraits<GR, typename GR::Arc> 1224 1224 ::ItemNotifier::ObserverBase Parent; 1225 1225 1226 TEMPLATE_DIGRAPH_TYPEDEFS(G );1227 typedef G Digraph;1226 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 1227 typedef GR Digraph; 1228 1228 1229 1229 protected: 1230 1230 1231 class AutoNodeMap : public ItemSetTraits<G , Node>::template Map<Arc>::Type {1231 class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type { 1232 1232 public: 1233 1233 1234 typedef typename ItemSetTraits<G , Node>::template Map<Arc>::Type Parent;1235 1236 AutoNodeMap(const G & digraph) : Parent(digraph, INVALID) {}1234 typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent; 1235 1236 AutoNodeMap(const GR& digraph) : Parent(digraph, INVALID) {} 1237 1237 1238 1238 virtual void add(const Node& node) { … … 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,m-1); 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 } … … 1624 1624 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs). 1625 1625 /// 1626 ///\tparam G The type of the underlying digraph.1626 ///\tparam GR The type of the underlying digraph. 1627 1627 /// 1628 1628 ///\sa DynArcLookUp 1629 1629 ///\sa AllArcLookUp 1630 template<class G >1630 template<class GR> 1631 1631 class ArcLookUp 1632 1632 { 1633 1633 public: 1634 TEMPLATE_DIGRAPH_TYPEDEFS(G );1635 typedef G Digraph;1634 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 1635 typedef GR Digraph; 1636 1636 1637 1637 protected: … … 1734 1734 ///(<em>O</em>(<em>m</em> log<em>m</em>)) to the number of arcs). 1735 1735 /// 1736 ///\tparam G The type of the underlying digraph.1736 ///\tparam GR The type of the underlying digraph. 1737 1737 /// 1738 1738 ///\sa DynArcLookUp 1739 1739 ///\sa ArcLookUp 1740 template<class G >1741 class AllArcLookUp : public ArcLookUp<G >1740 template<class GR> 1741 class AllArcLookUp : public ArcLookUp<GR> 1742 1742 { 1743 using ArcLookUp<G >::_g;1744 using ArcLookUp<G >::_right;1745 using ArcLookUp<G >::_left;1746 using ArcLookUp<G >::_head;1747 1748 TEMPLATE_DIGRAPH_TYPEDEFS(G );1749 typedef G Digraph;1743 using ArcLookUp<GR>::_g; 1744 using ArcLookUp<GR>::_right; 1745 using ArcLookUp<GR>::_left; 1746 using ArcLookUp<GR>::_head; 1747 1748 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 1749 typedef GR Digraph; 1750 1750 1751 1751 typename Digraph::template ArcMap<Arc> _next; … … 1774 1774 ///It builds up the search database, which remains valid until the digraph 1775 1775 ///changes. 1776 AllArcLookUp(const Digraph &g) : ArcLookUp<G >(g), _next(g) {refreshNext();}1776 AllArcLookUp(const Digraph &g) : ArcLookUp<GR>(g), _next(g) {refreshNext();} 1777 1777 1778 1778 ///Refresh the data structure at a node. … … 1784 1784 void refresh(Node n) 1785 1785 { 1786 ArcLookUp<G >::refresh(n);1786 ArcLookUp<GR>::refresh(n); 1787 1787 refreshNext(_head[n]); 1788 1788 } … … 1831 1831 Arc operator()(Node s, Node t, Arc prev=INVALID) const {} 1832 1832 #else 1833 using ArcLookUp<G >::operator() ;1833 using ArcLookUp<GR>::operator() ; 1834 1834 Arc operator()(Node s, Node t, Arc prev) const 1835 1835 {
Note: See TracChangeset
for help on using the changeset viewer.