Changes in lemon/core.h [581:aa1804409f29:535:6a17a722b50e] in lemon-1.2
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/core.h
r581 r535 1035 1035 ///\sa findArc() 1036 1036 ///\sa ArcLookUp, AllArcLookUp, DynArcLookUp 1037 template <typename GR>1038 class ConArcIt : public GR::Arc {1037 template <typename _Graph> 1038 class ConArcIt : public _Graph::Arc { 1039 1039 public: 1040 1040 1041 typedef GRGraph;1041 typedef _Graph Graph; 1042 1042 typedef typename Graph::Arc Parent; 1043 1043 … … 1158 1158 /// 1159 1159 ///\sa findEdge() 1160 template <typename GR>1161 class ConEdgeIt : public GR::Edge {1160 template <typename _Graph> 1161 class ConEdgeIt : public _Graph::Edge { 1162 1162 public: 1163 1163 1164 typedef GRGraph;1164 typedef _Graph Graph; 1165 1165 typedef typename Graph::Edge Parent; 1166 1166 … … 1212 1212 ///queries. 1213 1213 /// 1214 ///\tparam G RThe type of the underlying digraph.1214 ///\tparam G The type of the underlying digraph. 1215 1215 /// 1216 1216 ///\sa ArcLookUp 1217 1217 ///\sa AllArcLookUp 1218 template <typename GR>1218 template<class G> 1219 1219 class DynArcLookUp 1220 : protected ItemSetTraits<G R, typename GR::Arc>::ItemNotifier::ObserverBase1220 : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase 1221 1221 { 1222 1222 public: 1223 typedef typename ItemSetTraits<G R, typename GR::Arc>1223 typedef typename ItemSetTraits<G, typename G::Arc> 1224 1224 ::ItemNotifier::ObserverBase Parent; 1225 1225 1226 TEMPLATE_DIGRAPH_TYPEDEFS(G R);1227 typedef G RDigraph;1226 TEMPLATE_DIGRAPH_TYPEDEFS(G); 1227 typedef G Digraph; 1228 1228 1229 1229 protected: 1230 1230 1231 class AutoNodeMap : public ItemSetTraits<G R, Node>::template Map<Arc>::Type {1231 class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type { 1232 1232 public: 1233 1233 1234 typedef typename ItemSetTraits<G R, Node>::template Map<Arc>::Type Parent;1235 1236 AutoNodeMap(const G R& digraph) : Parent(digraph, INVALID) {}1234 typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent; 1235 1236 AutoNodeMap(const G& 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 [n] = INVALID;1318 _head.set(n, INVALID); 1319 1319 } 1320 1320 } … … 1323 1323 Node s = _g.source(arc); 1324 1324 Node t = _g.target(arc); 1325 _left [arc] = INVALID;1326 _right [arc] = INVALID;1325 _left.set(arc, INVALID); 1326 _right.set(arc, INVALID); 1327 1327 1328 1328 Arc e = _head[s]; 1329 1329 if (e == INVALID) { 1330 _head [s] = arc;1331 _parent [arc] = INVALID;1330 _head.set(s, arc); 1331 _parent.set(arc, INVALID); 1332 1332 return; 1333 1333 } … … 1335 1335 if (t < _g.target(e)) { 1336 1336 if (_left[e] == INVALID) { 1337 _left [e] = arc;1338 _parent [arc] = e;1337 _left.set(e, arc); 1338 _parent.set(arc, e); 1339 1339 splay(arc); 1340 1340 return; … … 1344 1344 } else { 1345 1345 if (_right[e] == INVALID) { 1346 _right [e] = arc;1347 _parent [arc] = e;1346 _right.set(e, arc); 1347 _parent.set(arc, e); 1348 1348 splay(arc); 1349 1349 return; … … 1358 1358 if (_left[arc] == INVALID) { 1359 1359 if (_right[arc] != INVALID) { 1360 _parent [_right[arc]] = _parent[arc];1360 _parent.set(_right[arc], _parent[arc]); 1361 1361 } 1362 1362 if (_parent[arc] != INVALID) { 1363 1363 if (_left[_parent[arc]] == arc) { 1364 _left [_parent[arc]] = _right[arc];1364 _left.set(_parent[arc], _right[arc]); 1365 1365 } else { 1366 _right [_parent[arc]] = _right[arc];1366 _right.set(_parent[arc], _right[arc]); 1367 1367 } 1368 1368 } else { 1369 _head [_g.source(arc)] = _right[arc];1369 _head.set(_g.source(arc), _right[arc]); 1370 1370 } 1371 1371 } else if (_right[arc] == INVALID) { 1372 _parent [_left[arc]] = _parent[arc];1372 _parent.set(_left[arc], _parent[arc]); 1373 1373 if (_parent[arc] != INVALID) { 1374 1374 if (_left[_parent[arc]] == arc) { 1375 _left [_parent[arc]] = _left[arc];1375 _left.set(_parent[arc], _left[arc]); 1376 1376 } else { 1377 _right [_parent[arc]] = _left[arc];1377 _right.set(_parent[arc], _left[arc]); 1378 1378 } 1379 1379 } else { 1380 _head [_g.source(arc)] = _left[arc];1380 _head.set(_g.source(arc), _left[arc]); 1381 1381 } 1382 1382 } else { … … 1388 1388 } 1389 1389 Arc s = _parent[e]; 1390 _right [_parent[e]] = _left[e];1390 _right.set(_parent[e], _left[e]); 1391 1391 if (_left[e] != INVALID) { 1392 _parent [_left[e]] = _parent[e];1392 _parent.set(_left[e], _parent[e]); 1393 1393 } 1394 1394 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];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]); 1401 1401 if (_parent[arc] != INVALID) { 1402 1402 if (_left[_parent[arc]] == arc) { 1403 _left [_parent[arc]] = e;1403 _left.set(_parent[arc], e); 1404 1404 } else { 1405 _right [_parent[arc]] = e;1405 _right.set(_parent[arc], e); 1406 1406 } 1407 1407 } 1408 1408 splay(s); 1409 1409 } else { 1410 _right [e] = _right[arc];1411 _parent [_right[arc]] = e;1412 _parent [e] = _parent[arc];1410 _right.set(e, _right[arc]); 1411 _parent.set(_right[arc], e); 1412 _parent.set(e, _parent[arc]); 1413 1413 1414 1414 if (_parent[arc] != INVALID) { 1415 1415 if (_left[_parent[arc]] == arc) { 1416 _left [_parent[arc]] = e;1416 _left.set(_parent[arc], e); 1417 1417 } else { 1418 _right [_parent[arc]] = e;1418 _right.set(_parent[arc], e); 1419 1419 } 1420 1420 } else { 1421 _head [_g.source(arc)] = e;1421 _head.set(_g.source(arc), e); 1422 1422 } 1423 1423 } … … 1431 1431 if (a < m) { 1432 1432 Arc left = refreshRec(v,a,m-1); 1433 _left [me] = left;1434 _parent [left] = me;1433 _left.set(me, left); 1434 _parent.set(left, me); 1435 1435 } else { 1436 _left [me] = INVALID;1436 _left.set(me, INVALID); 1437 1437 } 1438 1438 if (m < b) { 1439 1439 Arc right = refreshRec(v,m+1,b); 1440 _right [me] = right;1441 _parent [right] = me;1440 _right.set(me, right); 1441 _parent.set(right, me); 1442 1442 } else { 1443 _right [me] = INVALID;1443 _right.set(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 [n] = head;1456 _parent [head] = INVALID;1457 } 1458 else _head [n] = INVALID;1455 _head.set(n, head); 1456 _parent.set(head, INVALID); 1457 } 1458 else _head.set(n, INVALID); 1459 1459 } 1460 1460 } … … 1462 1462 void zig(Arc v) { 1463 1463 Arc w = _parent[v]; 1464 _parent [v] = _parent[w];1465 _parent [w] = v;1466 _left [w] = _right[v];1467 _right [v] = w;1464 _parent.set(v, _parent[w]); 1465 _parent.set(w, v); 1466 _left.set(w, _right[v]); 1467 _right.set(v, w); 1468 1468 if (_parent[v] != INVALID) { 1469 1469 if (_right[_parent[v]] == w) { 1470 _right [_parent[v]] = v;1470 _right.set(_parent[v], v); 1471 1471 } else { 1472 _left [_parent[v]] = v;1472 _left.set(_parent[v], v); 1473 1473 } 1474 1474 } 1475 1475 if (_left[w] != INVALID){ 1476 _parent [_left[w]] = w;1476 _parent.set(_left[w], w); 1477 1477 } 1478 1478 } … … 1480 1480 void zag(Arc v) { 1481 1481 Arc w = _parent[v]; 1482 _parent [v] = _parent[w];1483 _parent [w] = v;1484 _right [w] = _left[v];1485 _left [v] = w;1482 _parent.set(v, _parent[w]); 1483 _parent.set(w, v); 1484 _right.set(w, _left[v]); 1485 _left.set(v, w); 1486 1486 if (_parent[v] != INVALID){ 1487 1487 if (_left[_parent[v]] == w) { 1488 _left [_parent[v]] = v;1488 _left.set(_parent[v], v); 1489 1489 } else { 1490 _right [_parent[v]] = v;1490 _right.set(_parent[v], v); 1491 1491 } 1492 1492 } 1493 1493 if (_right[w] != INVALID){ 1494 _parent [_right[w]] = w;1494 _parent.set(_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 RThe type of the underlying digraph.1626 ///\tparam G The type of the underlying digraph. 1627 1627 /// 1628 1628 ///\sa DynArcLookUp 1629 1629 ///\sa AllArcLookUp 1630 template<class G R>1630 template<class G> 1631 1631 class ArcLookUp 1632 1632 { 1633 1633 public: 1634 TEMPLATE_DIGRAPH_TYPEDEFS(G R);1635 typedef G RDigraph;1634 TEMPLATE_DIGRAPH_TYPEDEFS(G); 1635 typedef G 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 RThe type of the underlying digraph.1736 ///\tparam G The type of the underlying digraph. 1737 1737 /// 1738 1738 ///\sa DynArcLookUp 1739 1739 ///\sa ArcLookUp 1740 template<class G R>1741 class AllArcLookUp : public ArcLookUp<G R>1740 template<class G> 1741 class AllArcLookUp : public ArcLookUp<G> 1742 1742 { 1743 using ArcLookUp<G R>::_g;1744 using ArcLookUp<G R>::_right;1745 using ArcLookUp<G R>::_left;1746 using ArcLookUp<G R>::_head;1747 1748 TEMPLATE_DIGRAPH_TYPEDEFS(G R);1749 typedef G RDigraph;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; 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 R>(g), _next(g) {refreshNext();}1776 AllArcLookUp(const Digraph &g) : ArcLookUp<G>(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 R>::refresh(n);1786 ArcLookUp<G>::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 R>::operator() ;1833 using ArcLookUp<G>::operator() ; 1834 1834 Arc operator()(Node s, Node t, Arc prev) const 1835 1835 {
Note: See TracChangeset
for help on using the changeset viewer.