Changeset 1979:c2992fd74dad in lemon-0.x for lemon/bits
- Timestamp:
- 02/22/06 19:26:56 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2569
- Location:
- lemon/bits
- Files:
-
- 2 added
- 4 deleted
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bits/alteration_notifier.h
r1956 r1979 266 266 void add(const Item& item) { 267 267 typename Container::iterator it; 268 for (it = container.begin(); it != container.end(); ++it) { 269 (*it)->add(item); 268 try { 269 for (it = container.begin(); it != container.end(); ++it) { 270 (*it)->add(item); 271 } 272 } catch (...) { 273 typename Container::iterator jt; 274 for (jt = container.begin(); jt != it; ++it) { 275 (*it)->erase(item); 276 } 277 throw; 270 278 } 271 279 } … … 279 287 void add(const std::vector<Item>& items) { 280 288 typename Container::iterator it; 281 for (it = container.begin(); it != container.end(); ++it) { 282 (*it)->add(items); 289 try { 290 for (it = container.begin(); it != container.end(); ++it) { 291 (*it)->add(items); 292 } 293 } catch (...) { 294 typename Container::iterator jt; 295 for (jt = container.begin(); jt != it; ++it) { 296 (*it)->erase(items); 297 } 298 throw; 283 299 } 284 300 } … … 317 333 void build() { 318 334 typename Container::iterator it; 319 for (it = container.begin(); it != container.end(); ++it) { 320 (*it)->build(); 335 try { 336 for (it = container.begin(); it != container.end(); ++it) { 337 (*it)->build(); 338 } 339 } catch (...) { 340 typename Container::iterator jt; 341 for (jt = container.begin(); jt != it; ++it) { 342 (*it)->clear(); 343 } 344 throw; 321 345 } 322 346 } … … 336 360 }; 337 361 338 339 /// \brief Class to extend a graph with the functionality of alteration340 /// observing.341 ///342 /// AlterableGraphExtender extends the _Base graphs functionality with343 /// the possibility of alteration observing. It defines two observer344 /// registrys for the nodes and mapes.345 ///346 /// \todo Document what "alteration observing" is. And probably find a347 /// better (shorter) name.348 ///349 /// \param _Base is the base class to extend.350 ///351 /// \pre _Base is conform to the BaseGraphComponent concept.352 ///353 /// \post AlterableGraphExtender<_Base> is conform to the354 /// AlterableGraphComponent concept.355 ///356 /// \author Balazs Dezso357 358 template <typename _Base>359 class AlterableGraphExtender : public _Base {360 public:361 362 typedef AlterableGraphExtender Graph;363 typedef _Base Parent;364 365 typedef typename Parent::Node Node;366 typedef typename Parent::Edge Edge;367 368 /// The edge observer registry.369 typedef AlterationNotifier<Edge> EdgeNotifier;370 /// The node observer registry.371 typedef AlterationNotifier<Node> NodeNotifier;372 373 374 protected:375 376 mutable EdgeNotifier edge_notifier;377 378 mutable NodeNotifier node_notifier;379 380 public:381 382 /// \brief Gives back the edge alteration notifier.383 ///384 /// Gives back the edge alteration notifier.385 EdgeNotifier& getNotifier(Edge) const {386 return edge_notifier;387 }388 389 /// \brief Gives back the node alteration notifier.390 ///391 /// Gives back the node alteration notifier.392 NodeNotifier& getNotifier(Node) const {393 return node_notifier;394 }395 396 ~AlterableGraphExtender() {397 node_notifier.clear();398 edge_notifier.clear();399 }400 401 };402 403 404 template <typename _Base>405 class AlterableEdgeSetExtender : public _Base {406 public:407 408 typedef AlterableEdgeSetExtender Graph;409 typedef _Base Parent;410 411 typedef typename Parent::Edge Edge;412 413 /// The edge observer registry.414 typedef AlterationNotifier<Edge> EdgeNotifier;415 416 protected:417 418 mutable EdgeNotifier edge_notifier;419 420 public:421 422 /// \brief Gives back the edge alteration notifier.423 ///424 /// Gives back the edge alteration notifier.425 EdgeNotifier& getNotifier(Edge) const {426 return edge_notifier;427 }428 429 ~AlterableEdgeSetExtender() {430 edge_notifier.clear();431 }432 433 };434 435 /// \brief Class to extend an undirected graph with the functionality of436 /// alteration observing.437 ///438 /// \todo Document.439 ///440 /// \sa AlterableGraphExtender441 ///442 /// \bug This should be done some other way. Possibilities: template443 /// specialization (not very easy, if at all possible); some kind of444 /// enable_if boost technique?445 446 template <typename _Base>447 class AlterableUGraphExtender448 : public AlterableGraphExtender<_Base> {449 public:450 451 typedef AlterableUGraphExtender Graph;452 typedef AlterableGraphExtender<_Base> Parent;453 454 typedef typename Parent::UEdge UEdge;455 456 /// The edge observer registry.457 typedef AlterationNotifier<UEdge> UEdgeNotifier;458 459 protected:460 461 mutable UEdgeNotifier u_edge_notifier;462 463 public:464 465 using Parent::getNotifier;466 UEdgeNotifier& getNotifier(UEdge) const {467 return u_edge_notifier;468 }469 470 ~AlterableUGraphExtender() {471 u_edge_notifier.clear();472 }473 };474 475 template <typename _Base>476 class AlterableUEdgeSetExtender477 : public AlterableEdgeSetExtender<_Base> {478 public:479 480 typedef AlterableUEdgeSetExtender Graph;481 typedef AlterableEdgeSetExtender<_Base> Parent;482 483 typedef typename Parent::UEdge UEdge;484 485 typedef AlterationNotifier<UEdge> UEdgeNotifier;486 487 protected:488 489 mutable UEdgeNotifier u_edge_notifier;490 491 public:492 493 using Parent::getNotifier;494 UEdgeNotifier& getNotifier(UEdge) const {495 return u_edge_notifier;496 }497 498 ~AlterableUEdgeSetExtender() {499 u_edge_notifier.clear();500 }501 };502 503 504 505 template <typename _Base>506 class AlterableBpUGraphExtender : public _Base {507 public:508 509 typedef _Base Parent;510 typedef AlterableBpUGraphExtender Graph;511 512 typedef typename Parent::Node Node;513 typedef typename Parent::BNode BNode;514 typedef typename Parent::ANode ANode;515 typedef typename Parent::Edge Edge;516 typedef typename Parent::UEdge UEdge;517 518 519 typedef AlterationNotifier<Node> NodeNotifier;520 typedef AlterationNotifier<BNode> BNodeNotifier;521 typedef AlterationNotifier<ANode> ANodeNotifier;522 typedef AlterationNotifier<Edge> EdgeNotifier;523 typedef AlterationNotifier<UEdge> UEdgeNotifier;524 525 protected:526 527 mutable NodeNotifier nodeNotifier;528 mutable BNodeNotifier bNodeNotifier;529 mutable ANodeNotifier aNodeNotifier;530 mutable EdgeNotifier edgeNotifier;531 mutable UEdgeNotifier uEdgeNotifier;532 533 public:534 535 NodeNotifier& getNotifier(Node) const {536 return nodeNotifier;537 }538 539 BNodeNotifier& getNotifier(BNode) const {540 return bNodeNotifier;541 }542 543 ANodeNotifier& getNotifier(ANode) const {544 return aNodeNotifier;545 }546 547 EdgeNotifier& getNotifier(Edge) const {548 return edgeNotifier;549 }550 551 UEdgeNotifier& getNotifier(UEdge) const {552 return uEdgeNotifier;553 }554 555 ~AlterableBpUGraphExtender() {556 nodeNotifier.clear();557 bNodeNotifier.clear();558 aNodeNotifier.clear();559 edgeNotifier.clear();560 uEdgeNotifier.clear();561 }562 563 };564 362 565 363 /// @} -
lemon/bits/default_map.h
r1966 r1979 23 23 #include <lemon/bits/array_map.h> 24 24 #include <lemon/bits/vector_map.h> 25 #include <lemon/bits/static_map.h> 25 26 26 27 ///\ingroup graphmapfactory … … 31 32 namespace lemon { 32 33 33 #ifndef GLIBCXX_DEBUG 34 35 #ifndef _GLIBCXX_DEBUG 34 36 35 37 template <typename _Graph, typename _Item, typename _Value> … … 168 170 }; 169 171 170 171 /// \e172 template <typename _Base>173 class MappableGraphExtender : public _Base {174 public:175 176 typedef MappableGraphExtender<_Base> Graph;177 typedef _Base Parent;178 179 typedef typename Parent::Node Node;180 typedef typename Parent::NodeIt NodeIt;181 182 typedef typename Parent::Edge Edge;183 typedef typename Parent::EdgeIt EdgeIt;184 185 186 template <typename _Value>187 class NodeMap188 : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {189 public:190 typedef MappableGraphExtender Graph;191 typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;192 193 NodeMap(const Graph& _g)194 : Parent(_g) {}195 NodeMap(const Graph& _g, const _Value& _v)196 : Parent(_g, _v) {}197 198 NodeMap& operator=(const NodeMap& cmap) {199 return operator=<NodeMap>(cmap);200 }201 202 203 /// \brief Template assign operator.204 ///205 /// The given parameter should be conform to the ReadMap206 /// concecpt and could be indiced by the current item set of207 /// the NodeMap. In this case the value for each item208 /// is assigned by the value of the given ReadMap.209 template <typename CMap>210 NodeMap& operator=(const CMap& cmap) {211 checkConcept<concept::ReadMap<Node, _Value>, CMap>();212 const typename Parent::Graph* graph = Parent::getGraph();213 Node it;214 for (graph->first(it); it != INVALID; graph->next(it)) {215 Parent::set(it, cmap[it]);216 }217 return *this;218 }219 220 };221 222 template <typename _Value>223 class EdgeMap224 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {225 public:226 typedef MappableGraphExtender Graph;227 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;228 229 EdgeMap(const Graph& _g)230 : Parent(_g) {}231 EdgeMap(const Graph& _g, const _Value& _v)232 : Parent(_g, _v) {}233 234 EdgeMap& operator=(const EdgeMap& cmap) {235 return operator=<EdgeMap>(cmap);236 }237 238 template <typename CMap>239 EdgeMap& operator=(const CMap& cmap) {240 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();241 const typename Parent::Graph* graph = Parent::getGraph();242 Edge it;243 for (graph->first(it); it != INVALID; graph->next(it)) {244 Parent::set(it, cmap[it]);245 }246 return *this;247 }248 };249 250 };251 252 /// \e253 template <typename _Base>254 class MappableEdgeSetExtender : public _Base {255 public:256 257 typedef MappableEdgeSetExtender<_Base> Graph;258 typedef _Base Parent;259 260 typedef typename Parent::Edge Edge;261 typedef typename Parent::EdgeIt EdgeIt;262 263 template <typename _Value>264 class EdgeMap265 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {266 public:267 typedef MappableEdgeSetExtender Graph;268 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;269 270 EdgeMap(const Graph& _g)271 : Parent(_g) {}272 EdgeMap(const Graph& _g, const _Value& _v)273 : Parent(_g, _v) {}274 275 EdgeMap& operator=(const EdgeMap& cmap) {276 return operator=<EdgeMap>(cmap);277 }278 279 template <typename CMap>280 EdgeMap& operator=(const CMap& cmap) {281 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();282 const typename Parent::Graph* graph = Parent::getGraph();283 Edge it;284 for (graph->first(it); it != INVALID; graph->next(it)) {285 Parent::set(it, cmap[it]);286 }287 return *this;288 }289 };290 291 };292 293 /// \e294 template <typename _Base>295 class MappableUGraphExtender :296 public MappableGraphExtender<_Base> {297 public:298 299 typedef MappableUGraphExtender Graph;300 typedef MappableGraphExtender<_Base> Parent;301 302 typedef typename Parent::UEdge UEdge;303 304 template <typename _Value>305 class UEdgeMap306 : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {307 public:308 typedef MappableUGraphExtender Graph;309 typedef IterableMapExtender<310 DefaultMap<Graph, UEdge, _Value> > Parent;311 312 UEdgeMap(const Graph& _g)313 : Parent(_g) {}314 UEdgeMap(const Graph& _g, const _Value& _v)315 : Parent(_g, _v) {}316 317 UEdgeMap& operator=(const UEdgeMap& cmap) {318 return operator=<UEdgeMap>(cmap);319 }320 321 template <typename CMap>322 UEdgeMap& operator=(const CMap& cmap) {323 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();324 const typename Parent::Graph* graph = Parent::getGraph();325 UEdge it;326 for (graph->first(it); it != INVALID; graph->next(it)) {327 Parent::set(it, cmap[it]);328 }329 return *this;330 }331 };332 333 334 };335 336 /// \e337 template <typename _Base>338 class MappableUEdgeSetExtender :339 public MappableEdgeSetExtender<_Base> {340 public:341 342 typedef MappableUEdgeSetExtender Graph;343 typedef MappableEdgeSetExtender<_Base> Parent;344 345 typedef typename Parent::UEdge UEdge;346 347 template <typename _Value>348 class UEdgeMap349 : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {350 public:351 typedef MappableUEdgeSetExtender Graph;352 typedef IterableMapExtender<353 DefaultMap<Graph, UEdge, _Value> > Parent;354 355 UEdgeMap(const Graph& _g)356 : Parent(_g) {}357 UEdgeMap(const Graph& _g, const _Value& _v)358 : Parent(_g, _v) {}359 360 UEdgeMap& operator=(const UEdgeMap& cmap) {361 return operator=<UEdgeMap>(cmap);362 }363 364 template <typename CMap>365 UEdgeMap& operator=(const CMap& cmap) {366 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();367 const typename Parent::Graph* graph = Parent::getGraph();368 UEdge it;369 for (graph->first(it); it != INVALID; graph->next(it)) {370 Parent::set(it, cmap[it]);371 }372 return *this;373 }374 };375 376 377 };378 379 380 template <typename _Base>381 class MappableBpUGraphExtender : public _Base {382 public:383 384 typedef _Base Parent;385 typedef MappableBpUGraphExtender Graph;386 387 typedef typename Parent::Node Node;388 typedef typename Parent::ANode ANode;389 typedef typename Parent::BNode BNode;390 typedef typename Parent::Edge Edge;391 typedef typename Parent::UEdge UEdge;392 393 template <typename _Value>394 class ANodeMap395 : public IterableMapExtender<DefaultMap<Graph, ANode, _Value> > {396 public:397 typedef MappableBpUGraphExtender Graph;398 typedef IterableMapExtender<DefaultMap<Graph, ANode, _Value> >399 Parent;400 401 ANodeMap(const Graph& _g)402 : Parent(_g) {}403 ANodeMap(const Graph& _g, const _Value& _v)404 : Parent(_g, _v) {}405 406 ANodeMap& operator=(const ANodeMap& cmap) {407 return operator=<ANodeMap>(cmap);408 }409 410 411 /// \brief Template assign operator.412 ///413 /// The given parameter should be conform to the ReadMap414 /// concept and could be indiced by the current item set of415 /// the ANodeMap. In this case the value for each item416 /// is assigned by the value of the given ReadMap.417 template <typename CMap>418 ANodeMap& operator=(const CMap& cmap) {419 checkConcept<concept::ReadMap<ANode, _Value>, CMap>();420 const typename Parent::Graph* graph = Parent::getGraph();421 ANode it;422 for (graph->first(it); it != INVALID; graph->next(it)) {423 Parent::set(it, cmap[it]);424 }425 return *this;426 }427 428 };429 430 template <typename _Value>431 class BNodeMap432 : public IterableMapExtender<DefaultMap<Graph, BNode, _Value> > {433 public:434 typedef MappableBpUGraphExtender Graph;435 typedef IterableMapExtender<DefaultMap<Graph, BNode, _Value> >436 Parent;437 438 BNodeMap(const Graph& _g)439 : Parent(_g) {}440 BNodeMap(const Graph& _g, const _Value& _v)441 : Parent(_g, _v) {}442 443 BNodeMap& operator=(const BNodeMap& cmap) {444 return operator=<BNodeMap>(cmap);445 }446 447 448 /// \brief Template assign operator.449 ///450 /// The given parameter should be conform to the ReadMap451 /// concept and could be indiced by the current item set of452 /// the BNodeMap. In this case the value for each item453 /// is assigned by the value of the given ReadMap.454 template <typename CMap>455 BNodeMap& operator=(const CMap& cmap) {456 checkConcept<concept::ReadMap<BNode, _Value>, CMap>();457 const typename Parent::Graph* graph = Parent::getGraph();458 BNode it;459 for (graph->first(it); it != INVALID; graph->next(it)) {460 Parent::set(it, cmap[it]);461 }462 return *this;463 }464 465 };466 467 protected:468 469 template <typename _Value>470 class NodeMapBase : public Parent::NodeNotifier::ObserverBase {471 public:472 typedef MappableBpUGraphExtender Graph;473 474 typedef Node Key;475 typedef _Value Value;476 477 /// The reference type of the map;478 typedef typename BNodeMap<_Value>::Reference Reference;479 /// The pointer type of the map;480 typedef typename BNodeMap<_Value>::Pointer Pointer;481 482 /// The const value type of the map.483 typedef const Value ConstValue;484 /// The const reference type of the map;485 typedef typename BNodeMap<_Value>::ConstReference ConstReference;486 /// The pointer type of the map;487 typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;488 489 typedef True ReferenceMapTag;490 491 NodeMapBase(const Graph& _g)492 : graph(&_g), bNodeMap(_g), aNodeMap(_g) {493 Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));494 }495 NodeMapBase(const Graph& _g, const _Value& _v)496 : graph(&_g), bNodeMap(_g, _v),497 aNodeMap(_g, _v) {498 Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));499 }500 501 virtual ~NodeMapBase() {502 if (Parent::NodeNotifier::ObserverBase::attached()) {503 Parent::NodeNotifier::ObserverBase::detach();504 }505 }506 507 ConstReference operator[](const Key& node) const {508 if (Parent::aNode(node)) {509 return aNodeMap[node];510 } else {511 return bNodeMap[node];512 }513 }514 515 Reference operator[](const Key& node) {516 if (Parent::aNode(node)) {517 return aNodeMap[node];518 } else {519 return bNodeMap[node];520 }521 }522 523 void set(const Key& node, const Value& value) {524 if (Parent::aNode(node)) {525 aNodeMap.set(node, value);526 } else {527 bNodeMap.set(node, value);528 }529 }530 531 protected:532 533 virtual void add(const Node&) {}534 virtual void add(const std::vector<Node>&) {}535 virtual void erase(const Node&) {}536 virtual void erase(const std::vector<Node>&) {}537 virtual void clear() {}538 virtual void build() {}539 540 const Graph* getGraph() const { return graph; }541 542 private:543 const Graph* graph;544 BNodeMap<_Value> bNodeMap;545 ANodeMap<_Value> aNodeMap;546 };547 548 public:549 550 template <typename _Value>551 class NodeMap552 : public IterableMapExtender<NodeMapBase<_Value> > {553 public:554 typedef MappableBpUGraphExtender Graph;555 typedef IterableMapExtender< NodeMapBase<_Value> > Parent;556 557 NodeMap(const Graph& _g)558 : Parent(_g) {}559 NodeMap(const Graph& _g, const _Value& _v)560 : Parent(_g, _v) {}561 562 NodeMap& operator=(const NodeMap& cmap) {563 return operator=<NodeMap>(cmap);564 }565 566 567 /// \brief Template assign operator.568 ///569 /// The given parameter should be conform to the ReadMap570 /// concept and could be indiced by the current item set of571 /// the NodeMap. In this case the value for each item572 /// is assigned by the value of the given ReadMap.573 template <typename CMap>574 NodeMap& operator=(const CMap& cmap) {575 checkConcept<concept::ReadMap<Node, _Value>, CMap>();576 const typename Parent::Graph* graph = Parent::getGraph();577 Node it;578 for (graph->first(it); it != INVALID; graph->next(it)) {579 Parent::set(it, cmap[it]);580 }581 return *this;582 }583 584 };585 586 587 588 template <typename _Value>589 class EdgeMap590 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {591 public:592 typedef MappableBpUGraphExtender Graph;593 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;594 595 EdgeMap(const Graph& _g)596 : Parent(_g) {}597 EdgeMap(const Graph& _g, const _Value& _v)598 : Parent(_g, _v) {}599 600 EdgeMap& operator=(const EdgeMap& cmap) {601 return operator=<EdgeMap>(cmap);602 }603 604 template <typename CMap>605 EdgeMap& operator=(const CMap& cmap) {606 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();607 const typename Parent::Graph* graph = Parent::getGraph();608 Edge it;609 for (graph->first(it); it != INVALID; graph->next(it)) {610 Parent::set(it, cmap[it]);611 }612 return *this;613 }614 };615 616 template <typename _Value>617 class UEdgeMap618 : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {619 public:620 typedef MappableBpUGraphExtender Graph;621 typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> >622 Parent;623 624 UEdgeMap(const Graph& _g)625 : Parent(_g) {}626 UEdgeMap(const Graph& _g, const _Value& _v)627 : Parent(_g, _v) {}628 629 UEdgeMap& operator=(const UEdgeMap& cmap) {630 return operator=<UEdgeMap>(cmap);631 }632 633 template <typename CMap>634 UEdgeMap& operator=(const CMap& cmap) {635 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();636 const typename Parent::Graph* graph = Parent::getGraph();637 UEdge it;638 for (graph->first(it); it != INVALID; graph->next(it)) {639 Parent::set(it, cmap[it]);640 }641 return *this;642 }643 };644 645 };646 647 172 } 648 173 -
lemon/bits/graph_extender.h
r1956 r1979 23 23 #include <lemon/error.h> 24 24 25 #include <lemon/bits/default_map.h> 26 25 27 namespace lemon { 26 28 27 template <typename _Base>28 class GraphExtender : public _Base {29 template <typename Base> 30 class GraphExtender : public Base { 29 31 public: 30 32 31 typedef _Base Parent;33 typedef Base Parent; 32 34 typedef GraphExtender Graph; 35 36 // Base extensions 33 37 34 38 typedef typename Parent::Node Node; … … 60 64 } 61 65 66 // Alterable extension 67 68 typedef AlterationNotifier<Node> NodeNotifier; 69 typedef AlterationNotifier<Edge> EdgeNotifier; 70 71 72 protected: 73 74 mutable NodeNotifier node_notifier; 75 mutable EdgeNotifier edge_notifier; 76 77 public: 78 79 NodeNotifier& getNotifier(Node) const { 80 return node_notifier; 81 } 82 83 EdgeNotifier& getNotifier(Edge) const { 84 return edge_notifier; 85 } 86 87 class NodeIt : public Node { 88 const Graph* graph; 89 public: 90 91 NodeIt() {} 92 93 NodeIt(Invalid i) : Node(i) { } 94 95 explicit NodeIt(const Graph& _graph) : graph(&_graph) { 96 _graph.first(*static_cast<Node*>(this)); 97 } 98 99 NodeIt(const Graph& _graph, const Node& node) 100 : Node(node), graph(&_graph) {} 101 102 NodeIt& operator++() { 103 graph->next(*this); 104 return *this; 105 } 106 107 }; 108 109 110 class EdgeIt : public Edge { 111 const Graph* graph; 112 public: 113 114 EdgeIt() { } 115 116 EdgeIt(Invalid i) : Edge(i) { } 117 118 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { 119 _graph.first(*static_cast<Edge*>(this)); 120 } 121 122 EdgeIt(const Graph& _graph, const Edge& e) : 123 Edge(e), graph(&_graph) { } 124 125 EdgeIt& operator++() { 126 graph->next(*this); 127 return *this; 128 } 129 130 }; 131 132 133 class OutEdgeIt : public Edge { 134 const Graph* graph; 135 public: 136 137 OutEdgeIt() { } 138 139 OutEdgeIt(Invalid i) : Edge(i) { } 140 141 OutEdgeIt(const Graph& _graph, const Node& node) 142 : graph(&_graph) { 143 _graph.firstOut(*this, node); 144 } 145 146 OutEdgeIt(const Graph& _graph, const Edge& edge) 147 : Edge(edge), graph(&_graph) {} 148 149 OutEdgeIt& operator++() { 150 graph->nextOut(*this); 151 return *this; 152 } 153 154 }; 155 156 157 class InEdgeIt : public Edge { 158 const Graph* graph; 159 public: 160 161 InEdgeIt() { } 162 163 InEdgeIt(Invalid i) : Edge(i) { } 164 165 InEdgeIt(const Graph& _graph, const Node& node) 166 : graph(&_graph) { 167 _graph.firstIn(*this, node); 168 } 169 170 InEdgeIt(const Graph& _graph, const Edge& edge) : 171 Edge(edge), graph(&_graph) {} 172 173 InEdgeIt& operator++() { 174 graph->nextIn(*this); 175 return *this; 176 } 177 178 }; 179 180 /// \brief Base node of the iterator 181 /// 182 /// Returns the base node (ie. the source in this case) of the iterator 183 Node baseNode(const OutEdgeIt &e) const { 184 return Parent::source(e); 185 } 186 /// \brief Running node of the iterator 187 /// 188 /// Returns the running node (ie. the target in this case) of the 189 /// iterator 190 Node runningNode(const OutEdgeIt &e) const { 191 return Parent::target(e); 192 } 193 194 /// \brief Base node of the iterator 195 /// 196 /// Returns the base node (ie. the target in this case) of the iterator 197 Node baseNode(const InEdgeIt &e) const { 198 return Parent::target(e); 199 } 200 /// \brief Running node of the iterator 201 /// 202 /// Returns the running node (ie. the source in this case) of the 203 /// iterator 204 Node runningNode(const InEdgeIt &e) const { 205 return Parent::source(e); 206 } 207 208 209 template <typename _Value> 210 class NodeMap 211 : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > { 212 public: 213 typedef GraphExtender Graph; 214 typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent; 215 216 NodeMap(const Graph& _g) 217 : Parent(_g) {} 218 NodeMap(const Graph& _g, const _Value& _v) 219 : Parent(_g, _v) {} 220 221 NodeMap& operator=(const NodeMap& cmap) { 222 return operator=<NodeMap>(cmap); 223 } 224 225 226 /// \brief Template assign operator. 227 /// 228 /// The given parameter should be conform to the ReadMap 229 /// concecpt and could be indiced by the current item set of 230 /// the NodeMap. In this case the value for each item 231 /// is assigned by the value of the given ReadMap. 232 template <typename CMap> 233 NodeMap& operator=(const CMap& cmap) { 234 checkConcept<concept::ReadMap<Node, _Value>, CMap>(); 235 const typename Parent::Graph* graph = Parent::getGraph(); 236 Node it; 237 for (graph->first(it); it != INVALID; graph->next(it)) { 238 Parent::set(it, cmap[it]); 239 } 240 return *this; 241 } 242 243 }; 244 245 template <typename _Value> 246 class EdgeMap 247 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > { 248 public: 249 typedef GraphExtender Graph; 250 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 251 252 EdgeMap(const Graph& _g) 253 : Parent(_g) {} 254 EdgeMap(const Graph& _g, const _Value& _v) 255 : Parent(_g, _v) {} 256 257 EdgeMap& operator=(const EdgeMap& cmap) { 258 return operator=<EdgeMap>(cmap); 259 } 260 261 template <typename CMap> 262 EdgeMap& operator=(const CMap& cmap) { 263 checkConcept<concept::ReadMap<Edge, _Value>, CMap>(); 264 const typename Parent::Graph* graph = Parent::getGraph(); 265 Edge it; 266 for (graph->first(it); it != INVALID; graph->next(it)) { 267 Parent::set(it, cmap[it]); 268 } 269 return *this; 270 } 271 }; 272 273 274 Node addNode() { 275 Node node = Parent::addNode(); 276 getNotifier(Node()).add(node); 277 return node; 278 } 279 280 Edge addEdge(const Node& from, const Node& to) { 281 Edge edge = Parent::addEdge(from, to); 282 getNotifier(Edge()).add(edge); 283 return edge; 284 } 285 286 void clear() { 287 getNotifier(Edge()).clear(); 288 getNotifier(Node()).clear(); 289 Parent::clear(); 290 } 291 292 293 void erase(const Node& node) { 294 Edge edge; 295 Parent::firstOut(edge, node); 296 while (edge != INVALID ) { 297 erase(edge); 298 Parent::firstOut(edge, node); 299 } 300 301 Parent::firstIn(edge, node); 302 while (edge != INVALID ) { 303 erase(edge); 304 Parent::firstIn(edge, node); 305 } 306 307 getNotifier(Node()).erase(node); 308 Parent::erase(node); 309 } 310 311 void erase(const Edge& edge) { 312 getNotifier(Edge()).erase(edge); 313 Parent::erase(edge); 314 } 315 316 317 ~GraphExtender() { 318 getNotifier(Edge()).clear(); 319 getNotifier(Node()).clear(); 320 } 62 321 }; 63 322 64 template <typename _Base> 65 class UGraphExtender : public _Base { 66 typedef _Base Parent; 67 typedef UGraphExtender Graph; 323 template <typename Base> 324 class UGraphBaseExtender : public Base { 68 325 69 326 public: 70 327 328 typedef Base Parent; 71 329 typedef typename Parent::Edge UEdge; 72 330 typedef typename Parent::Node Node; 73 331 332 typedef True UndirectedTag; 333 74 334 class Edge : public UEdge { 75 friend class UGraph Extender;335 friend class UGraphBaseExtender; 76 336 77 337 protected: 78 // FIXME: Marci use opposite logic in his graph adaptors. It would79 // be reasonable to syncronize...80 338 bool forward; 81 339 … … 102 360 103 361 104 /// \brief Edge of opposite direction. 105 /// 106 /// Returns the Edge of opposite direction. 107 Edge oppositeEdge(const Edge &e) const { 108 return Edge(e,!e.forward); 109 } 110 111 public: 112 /// \todo Shouldn't the "source" of an undirected edge be called "aNode" 113 /// or something??? 362 114 363 using Parent::source; 115 364 … … 119 368 } 120 369 121 /// \todo Shouldn't the "target" of an undirected edge be called "bNode"122 /// or something???123 370 using Parent::target; 124 371 … … 126 373 Node target(const Edge &e) const { 127 374 return e.forward ? Parent::target(e) : Parent::source(e); 128 }129 130 Node oppositeNode(const Node &n, const UEdge &e) const {131 if( n == Parent::source(e))132 return Parent::target(e);133 else if( n == Parent::target(e))134 return Parent::source(e);135 else136 return INVALID;137 }138 139 /// \brief Directed edge from an undirected edge and a source node.140 ///141 /// Returns a (directed) Edge corresponding to the specified UEdge142 /// and source Node.143 ///144 Edge direct(const UEdge &ue, const Node &s) const {145 return Edge(ue, s == source(ue));146 375 } 147 376 … … 164 393 165 394 using Parent::first; 395 using Parent::next; 396 166 397 void first(Edge &e) const { 167 398 Parent::first(e); … … 169 400 } 170 401 171 using Parent::next;172 402 void next(Edge &e) const { 173 403 if( e.forward ) { … … 179 409 } 180 410 } 181 182 public:183 411 184 412 void firstOut(Edge &e, const Node &n) const { … … 230 458 } 231 459 232 void firstInc(UEdge &e, const Node &n) const {233 Parent::firstOut(e, n);234 if (e != INVALID) return;235 Parent::firstIn(e, n);236 }237 void nextInc(UEdge &e, const Node &n) const {238 if (Parent::source(e) == n) {239 Parent::nextOut(e);240 if (e != INVALID) return;241 Parent::firstIn(e, n);242 } else {243 Parent::nextIn(e);244 }245 }246 247 460 void firstInc(UEdge &e, bool &d, const Node &n) const { 248 461 d = true; … … 252 465 Parent::firstIn(e, n); 253 466 } 467 254 468 void nextInc(UEdge &e, bool &d) const { 255 469 if (d) { … … 264 478 } 265 479 266 // Miscellaneous stuff: 267 268 /// \todo these methods (id, maxEdgeId) should be moved into separate 269 /// Extender 270 271 // using Parent::id; 272 // Using "using" is not a good idea, cause it could be that there is 273 // no "id" in Parent... 480 Node nodeFromId(int id) const { 481 return Parent::nodeFromId(id); 482 } 483 484 Edge edgeFromId(int id) const { 485 return direct(Parent::edgeFromId(id >> 1), bool(id & 1)); 486 } 487 488 UEdge uEdgeFromId(int id) const { 489 return Parent::edgeFromId(id >> 1); 490 } 274 491 275 492 int id(const Node &n) const { … … 297 514 } 298 515 299 int maxId(Node) const {300 return maxNodeId();301 }302 303 int maxId(Edge) const {304 return maxEdgeId();305 }306 int maxId(UEdge) const {307 return maxUEdgeId();308 }309 516 310 517 int edgeNum() const { … … 315 522 return Parent::edgeNum(); 316 523 } 317 318 Node nodeFromId(int id) const {319 return Parent::nodeFromId(id);320 }321 322 Edge edgeFromId(int id) const {323 return direct(Parent::edgeFromId(id >> 1), bool(id & 1));324 }325 326 UEdge uEdgeFromId(int id) const {327 return Parent::edgeFromId(id >> 1);328 }329 330 Node fromId(int id, Node) const {331 return nodeFromId(id);332 }333 334 Edge fromId(int id, Edge) const {335 return edgeFromId(id);336 }337 338 UEdge fromId(int id, UEdge) const {339 return uEdgeFromId(id);340 }341 342 524 343 525 Edge findEdge(Node source, Node target, Edge prev) const { … … 376 558 return INVALID; 377 559 } 378 379 560 }; 380 561 381 562 382 template <typename _Base>383 class BpUGraphExtender : public _Base {563 template <typename Base> 564 class UGraphExtender : public Base { 384 565 public: 385 typedef _Base Parent; 386 typedef BpUGraphExtender Graph; 566 567 typedef Base Parent; 568 typedef UGraphExtender Graph; 569 570 typedef typename Parent::Node Node; 571 typedef typename Parent::Edge Edge; 572 typedef typename Parent::UEdge UEdge; 573 574 // UGraph extension 575 576 int maxId(Node) const { 577 return Parent::maxNodeId(); 578 } 579 580 int maxId(Edge) const { 581 return Parent::maxEdgeId(); 582 } 583 584 int maxId(UEdge) const { 585 return Parent::maxUEdgeId(); 586 } 587 588 Node fromId(int id, Node) const { 589 return Parent::nodeFromId(id); 590 } 591 592 Edge fromId(int id, Edge) const { 593 return Parent::edgeFromId(id); 594 } 595 596 UEdge fromId(int id, UEdge) const { 597 return Parent::uEdgeFromId(id); 598 } 599 600 Node oppositeNode(const Node &n, const UEdge &e) const { 601 if( n == Parent::source(e)) 602 return Parent::target(e); 603 else if( n == Parent::target(e)) 604 return Parent::source(e); 605 else 606 return INVALID; 607 } 608 609 Edge oppositeEdge(const Edge &e) const { 610 return Parent::direct(e, !Parent::direction(e)); 611 } 612 613 using Parent::direct; 614 Edge direct(const UEdge &ue, const Node &s) const { 615 return Parent::direct(ue, Parent::source(ue) == s); 616 } 617 618 // Alterable extension 619 620 typedef AlterationNotifier<Node> NodeNotifier; 621 typedef AlterationNotifier<Edge> EdgeNotifier; 622 typedef AlterationNotifier<UEdge> UEdgeNotifier; 623 624 625 protected: 626 627 mutable NodeNotifier node_notifier; 628 mutable EdgeNotifier edge_notifier; 629 mutable UEdgeNotifier uedge_notifier; 630 631 public: 632 633 NodeNotifier& getNotifier(Node) const { 634 return node_notifier; 635 } 636 637 EdgeNotifier& getNotifier(Edge) const { 638 return edge_notifier; 639 } 640 641 UEdgeNotifier& getNotifier(UEdge) const { 642 return uedge_notifier; 643 } 644 645 646 647 class NodeIt : public Node { 648 const Graph* graph; 649 public: 650 651 NodeIt() {} 652 653 NodeIt(Invalid i) : Node(i) { } 654 655 explicit NodeIt(const Graph& _graph) : graph(&_graph) { 656 _graph.first(*static_cast<Node*>(this)); 657 } 658 659 NodeIt(const Graph& _graph, const Node& node) 660 : Node(node), graph(&_graph) {} 661 662 NodeIt& operator++() { 663 graph->next(*this); 664 return *this; 665 } 666 667 }; 668 669 670 class EdgeIt : public Edge { 671 const Graph* graph; 672 public: 673 674 EdgeIt() { } 675 676 EdgeIt(Invalid i) : Edge(i) { } 677 678 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { 679 _graph.first(*static_cast<Edge*>(this)); 680 } 681 682 EdgeIt(const Graph& _graph, const Edge& e) : 683 Edge(e), graph(&_graph) { } 684 685 EdgeIt& operator++() { 686 graph->next(*this); 687 return *this; 688 } 689 690 }; 691 692 693 class OutEdgeIt : public Edge { 694 const Graph* graph; 695 public: 696 697 OutEdgeIt() { } 698 699 OutEdgeIt(Invalid i) : Edge(i) { } 700 701 OutEdgeIt(const Graph& _graph, const Node& node) 702 : graph(&_graph) { 703 _graph.firstOut(*this, node); 704 } 705 706 OutEdgeIt(const Graph& _graph, const Edge& edge) 707 : Edge(edge), graph(&_graph) {} 708 709 OutEdgeIt& operator++() { 710 graph->nextOut(*this); 711 return *this; 712 } 713 714 }; 715 716 717 class InEdgeIt : public Edge { 718 const Graph* graph; 719 public: 720 721 InEdgeIt() { } 722 723 InEdgeIt(Invalid i) : Edge(i) { } 724 725 InEdgeIt(const Graph& _graph, const Node& node) 726 : graph(&_graph) { 727 _graph.firstIn(*this, node); 728 } 729 730 InEdgeIt(const Graph& _graph, const Edge& edge) : 731 Edge(edge), graph(&_graph) {} 732 733 InEdgeIt& operator++() { 734 graph->nextIn(*this); 735 return *this; 736 } 737 738 }; 739 740 741 class UEdgeIt : public Parent::UEdge { 742 const Graph* graph; 743 public: 744 745 UEdgeIt() { } 746 747 UEdgeIt(Invalid i) : UEdge(i) { } 748 749 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { 750 _graph.first(*static_cast<UEdge*>(this)); 751 } 752 753 UEdgeIt(const Graph& _graph, const UEdge& e) : 754 UEdge(e), graph(&_graph) { } 755 756 UEdgeIt& operator++() { 757 graph->next(*this); 758 return *this; 759 } 760 761 }; 762 763 class IncEdgeIt : public Parent::UEdge { 764 friend class UGraphExtender; 765 const Graph* graph; 766 bool direction; 767 public: 768 769 IncEdgeIt() { } 770 771 IncEdgeIt(Invalid i) : UEdge(i), direction(false) { } 772 773 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { 774 _graph.firstInc(*this, direction, n); 775 } 776 777 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) 778 : graph(&_graph), UEdge(ue) { 779 direction = (_graph.source(ue) == n); 780 } 781 782 IncEdgeIt& operator++() { 783 graph->nextInc(*this, direction); 784 return *this; 785 } 786 }; 787 788 /// \brief Base node of the iterator 789 /// 790 /// Returns the base node (ie. the source in this case) of the iterator 791 Node baseNode(const OutEdgeIt &e) const { 792 return Parent::source((Edge)e); 793 } 794 /// \brief Running node of the iterator 795 /// 796 /// Returns the running node (ie. the target in this case) of the 797 /// iterator 798 Node runningNode(const OutEdgeIt &e) const { 799 return Parent::target((Edge)e); 800 } 801 802 /// \brief Base node of the iterator 803 /// 804 /// Returns the base node (ie. the target in this case) of the iterator 805 Node baseNode(const InEdgeIt &e) const { 806 return Parent::target((Edge)e); 807 } 808 /// \brief Running node of the iterator 809 /// 810 /// Returns the running node (ie. the source in this case) of the 811 /// iterator 812 Node runningNode(const InEdgeIt &e) const { 813 return Parent::source((Edge)e); 814 } 815 816 /// Base node of the iterator 817 /// 818 /// Returns the base node of the iterator 819 Node baseNode(const IncEdgeIt &e) const { 820 return e.direction ? source(e) : target(e); 821 } 822 /// Running node of the iterator 823 /// 824 /// Returns the running node of the iterator 825 Node runningNode(const IncEdgeIt &e) const { 826 return e.direction ? target(e) : source(e); 827 } 828 829 // Mappable extension 830 831 template <typename _Value> 832 class NodeMap 833 : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > { 834 public: 835 typedef UGraphExtender Graph; 836 typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent; 837 838 NodeMap(const Graph& _g) 839 : Parent(_g) {} 840 NodeMap(const Graph& _g, const _Value& _v) 841 : Parent(_g, _v) {} 842 843 NodeMap& operator=(const NodeMap& cmap) { 844 return operator=<NodeMap>(cmap); 845 } 846 847 848 /// \brief Template assign operator. 849 /// 850 /// The given parameter should be conform to the ReadMap 851 /// concecpt and could be indiced by the current item set of 852 /// the NodeMap. In this case the value for each item 853 /// is assigned by the value of the given ReadMap. 854 template <typename CMap> 855 NodeMap& operator=(const CMap& cmap) { 856 checkConcept<concept::ReadMap<Node, _Value>, CMap>(); 857 const typename Parent::Graph* graph = Parent::getGraph(); 858 Node it; 859 for (graph->first(it); it != INVALID; graph->next(it)) { 860 Parent::set(it, cmap[it]); 861 } 862 return *this; 863 } 864 865 }; 866 867 template <typename _Value> 868 class EdgeMap 869 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > { 870 public: 871 typedef UGraphExtender Graph; 872 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 873 874 EdgeMap(const Graph& _g) 875 : Parent(_g) {} 876 EdgeMap(const Graph& _g, const _Value& _v) 877 : Parent(_g, _v) {} 878 879 EdgeMap& operator=(const EdgeMap& cmap) { 880 return operator=<EdgeMap>(cmap); 881 } 882 883 template <typename CMap> 884 EdgeMap& operator=(const CMap& cmap) { 885 checkConcept<concept::ReadMap<Edge, _Value>, CMap>(); 886 const typename Parent::Graph* graph = Parent::getGraph(); 887 Edge it; 888 for (graph->first(it); it != INVALID; graph->next(it)) { 889 Parent::set(it, cmap[it]); 890 } 891 return *this; 892 } 893 }; 894 895 896 template <typename _Value> 897 class UEdgeMap 898 : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > { 899 public: 900 typedef UGraphExtender Graph; 901 typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > Parent; 902 903 UEdgeMap(const Graph& _g) 904 : Parent(_g) {} 905 UEdgeMap(const Graph& _g, const _Value& _v) 906 : Parent(_g, _v) {} 907 908 UEdgeMap& operator=(const UEdgeMap& cmap) { 909 return operator=<UEdgeMap>(cmap); 910 } 911 912 template <typename CMap> 913 UEdgeMap& operator=(const CMap& cmap) { 914 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>(); 915 const typename Parent::Graph* graph = Parent::getGraph(); 916 UEdge it; 917 for (graph->first(it); it != INVALID; graph->next(it)) { 918 Parent::set(it, cmap[it]); 919 } 920 return *this; 921 } 922 }; 923 924 // Alteration extension 925 926 Node addNode() { 927 Node node = Parent::addNode(); 928 getNotifier(Node()).add(node); 929 return node; 930 } 931 932 UEdge addEdge(const Node& from, const Node& to) { 933 UEdge uedge = Parent::addEdge(from, to); 934 getNotifier(UEdge()).add(uedge); 935 getNotifier(Edge()).add(Parent::direct(uedge, true)); 936 getNotifier(Edge()).add(Parent::direct(uedge, false)); 937 return uedge; 938 } 939 940 void clear() { 941 getNotifier(Edge()).clear(); 942 getNotifier(UEdge()).clear(); 943 getNotifier(Node()).clear(); 944 Parent::clear(); 945 } 946 947 void erase(const Node& node) { 948 Edge edge; 949 Parent::firstOut(edge, node); 950 while (edge != INVALID ) { 951 erase(edge); 952 Parent::firstOut(edge, node); 953 } 954 955 Parent::firstIn(edge, node); 956 while (edge != INVALID ) { 957 erase(edge); 958 Parent::firstIn(edge, node); 959 } 960 961 getNotifier(Node()).erase(node); 962 Parent::erase(node); 963 } 964 965 void erase(const UEdge& uedge) { 966 getNotifier(Edge()).erase(Parent::direct(uedge, true)); 967 getNotifier(Edge()).erase(Parent::direct(uedge, false)); 968 getNotifier(UEdge()).erase(uedge); 969 Parent::erase(uedge); 970 } 971 972 ~UGraphExtender() { 973 getNotifier(Edge()).clear(); 974 getNotifier(UEdge()).clear(); 975 getNotifier(Node()).clear(); 976 } 977 978 }; 979 980 981 template <typename Base> 982 class BpUGraphBaseExtender : public Base { 983 public: 984 typedef Base Parent; 985 typedef BpUGraphBaseExtender Graph; 387 986 388 987 typedef typename Parent::Node Node; 389 988 typedef typename Parent::Edge UEdge; 390 989 990 391 991 using Parent::first; 392 992 using Parent::next; 393 993 394 994 using Parent::id; 995 996 class ANode : public Node { 997 friend class BpUGraphBaseExtender; 998 public: 999 ANode() {} 1000 ANode(const Node& node) : Node(node) { 1001 LEMON_ASSERT(Parent::aNode(node) || node == INVALID, 1002 typename Parent::NodeSetError()); 1003 } 1004 ANode(Invalid) : Node(INVALID) {} 1005 }; 1006 1007 void first(ANode& node) const { 1008 Parent::firstANode(static_cast<Node&>(node)); 1009 } 1010 void next(ANode& node) const { 1011 Parent::nextANode(static_cast<Node&>(node)); 1012 } 1013 1014 int id(const ANode& node) const { 1015 return Parent::aNodeId(node); 1016 } 1017 1018 class BNode : public Node { 1019 friend class BpUGraphBaseExtender; 1020 public: 1021 BNode() {} 1022 BNode(const Node& node) : Node(node) { 1023 LEMON_ASSERT(Parent::bNode(node) || node == INVALID, 1024 typename Parent::NodeSetError()); 1025 } 1026 BNode(Invalid) : Node(INVALID) {} 1027 }; 1028 1029 void first(BNode& node) const { 1030 Parent::firstBNode(static_cast<Node&>(node)); 1031 } 1032 void next(BNode& node) const { 1033 Parent::nextBNode(static_cast<Node&>(node)); 1034 } 1035 1036 int id(const BNode& node) const { 1037 return Parent::aNodeId(node); 1038 } 395 1039 396 1040 Node source(const UEdge& edge) const { … … 428 1072 429 1073 class Edge : public UEdge { 430 friend class BpUGraph Extender;1074 friend class BpUGraphBaseExtender; 431 1075 protected: 432 1076 bool forward; … … 505 1149 } 506 1150 1151 int id(const Edge& edge) const { 1152 return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1); 1153 } 1154 Edge edgeFromId(int id) const { 1155 return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0); 1156 } 1157 int maxEdgeId() const { 1158 return (Parent::maxId(UEdge()) << 1) + 1; 1159 } 1160 507 1161 bool direction(const Edge& edge) const { 508 1162 return edge.forward; 509 1163 } 510 1164 511 Edge direct(const UEdge& edge, const Node& node) const {512 return Edge(edge, node == Parent::source(edge));513 }514 515 1165 Edge direct(const UEdge& edge, bool direction) const { 516 1166 return Edge(edge, direction); 517 1167 } 1168 }; 1169 1170 template <typename Base> 1171 class BpUGraphExtender : public Base { 1172 public: 1173 typedef Base Parent; 1174 typedef BpUGraphExtender Graph; 1175 1176 typedef typename Parent::Node Node; 1177 typedef typename Parent::BNode BNode; 1178 typedef typename Parent::ANode ANode; 1179 typedef typename Parent::Edge Edge; 1180 typedef typename Parent::UEdge UEdge; 518 1181 519 1182 Node oppositeNode(const UEdge& edge, const Node& node) const { … … 522 1185 } 523 1186 1187 using Parent::direct; 1188 Edge direct(const UEdge& edge, const Node& node) const { 1189 return Edge(edge, node == Parent::source(edge)); 1190 } 1191 524 1192 Edge oppositeEdge(const Edge& edge) const { 525 return Edge(edge, !edge.forward); 526 } 527 528 int id(const Edge& edge) const { 529 return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1); 530 } 531 Edge edgeFromId(int id) const { 532 return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0); 533 } 534 int maxEdgeId() const { 535 return (Parent::maxId(UEdge()) << 1) + 1; 536 } 537 538 class ANode : public Node { 539 friend class BpUGraphExtender; 540 public: 541 ANode() {} 542 ANode(const Node& node) : Node(node) { 543 LEMON_ASSERT(Parent::aNode(node) || node == INVALID, 544 typename Parent::NodeSetError()); 545 } 546 ANode(Invalid) : Node(INVALID) {} 547 }; 548 549 void first(ANode& node) const { 550 Parent::firstANode(static_cast<Node&>(node)); 551 } 552 void next(ANode& node) const { 553 Parent::nextANode(static_cast<Node&>(node)); 554 } 555 556 int id(const ANode& node) const { 557 return Parent::aNodeId(node); 558 } 559 560 class BNode : public Node { 561 friend class BpUGraphExtender; 562 public: 563 BNode() {} 564 BNode(const Node& node) : Node(node) { 565 LEMON_ASSERT(Parent::bNode(node) || node == INVALID, 566 typename Parent::NodeSetError()); 567 } 568 BNode(Invalid) : Node(INVALID) {} 569 }; 570 571 void first(BNode& node) const { 572 Parent::firstBNode(static_cast<Node&>(node)); 573 } 574 void next(BNode& node) const { 575 Parent::nextBNode(static_cast<Node&>(node)); 576 } 577 578 int id(const BNode& node) const { 579 return Parent::aNodeId(node); 580 } 581 1193 return Parent::direct(edge, !Parent::direction(edge)); 1194 } 582 1195 583 1196 … … 592 1205 } 593 1206 int maxId(Edge) const { 594 return maxEdgeId();1207 return Parent::maxEdgeId(); 595 1208 } 596 1209 int maxId(UEdge) const { 597 return maxUEdgeId();1210 return Parent::maxUEdgeId(); 598 1211 } 599 1212 … … 609 1222 } 610 1223 Edge fromId(int id, Edge) const { 611 return edgeFromId(id);1224 return Parent::edgeFromId(id); 612 1225 } 613 1226 UEdge fromId(int id, UEdge) const { 614 return uEdgeFromId(id); 615 } 1227 return Parent::uEdgeFromId(id); 1228 } 1229 1230 typedef AlterationNotifier<Node> NodeNotifier; 1231 typedef AlterationNotifier<BNode> BNodeNotifier; 1232 typedef AlterationNotifier<ANode> ANodeNotifier; 1233 typedef AlterationNotifier<Edge> EdgeNotifier; 1234 typedef AlterationNotifier<UEdge> UEdgeNotifier; 1235 1236 protected: 1237 1238 mutable NodeNotifier nodeNotifier; 1239 mutable BNodeNotifier bNodeNotifier; 1240 mutable ANodeNotifier aNodeNotifier; 1241 mutable EdgeNotifier edgeNotifier; 1242 mutable UEdgeNotifier uEdgeNotifier; 1243 1244 public: 1245 1246 NodeNotifier& getNotifier(Node) const { 1247 return nodeNotifier; 1248 } 1249 1250 BNodeNotifier& getNotifier(BNode) const { 1251 return bNodeNotifier; 1252 } 1253 1254 ANodeNotifier& getNotifier(ANode) const { 1255 return aNodeNotifier; 1256 } 1257 1258 EdgeNotifier& getNotifier(Edge) const { 1259 return edgeNotifier; 1260 } 1261 1262 UEdgeNotifier& getNotifier(UEdge) const { 1263 return uEdgeNotifier; 1264 } 1265 1266 ~BpUGraphExtender() { 1267 getNotifier(UEdge()).clear(); 1268 getNotifier(Edge()).clear(); 1269 getNotifier(ANode()).clear(); 1270 getNotifier(BNode()).clear(); 1271 getNotifier(Node()).clear(); 1272 } 1273 1274 1275 class NodeIt : public Node { 1276 const Graph* graph; 1277 public: 1278 1279 NodeIt() { } 1280 1281 NodeIt(Invalid i) : Node(INVALID) { } 1282 1283 explicit NodeIt(const Graph& _graph) : graph(&_graph) { 1284 graph->first(static_cast<Node&>(*this)); 1285 } 1286 1287 NodeIt(const Graph& _graph, const Node& node) 1288 : Node(node), graph(&_graph) { } 1289 1290 NodeIt& operator++() { 1291 graph->next(*this); 1292 return *this; 1293 } 1294 1295 }; 1296 1297 class ANodeIt : public Node { 1298 friend class BpUGraphExtender; 1299 const Graph* graph; 1300 public: 1301 1302 ANodeIt() { } 1303 1304 ANodeIt(Invalid i) : Node(INVALID) { } 1305 1306 explicit ANodeIt(const Graph& _graph) : graph(&_graph) { 1307 graph->firstANode(static_cast<Node&>(*this)); 1308 } 1309 1310 ANodeIt(const Graph& _graph, const Node& node) 1311 : Node(node), graph(&_graph) {} 1312 1313 ANodeIt& operator++() { 1314 graph->nextANode(*this); 1315 return *this; 1316 } 1317 }; 1318 1319 class BNodeIt : public Node { 1320 friend class BpUGraphExtender; 1321 const Graph* graph; 1322 public: 1323 1324 BNodeIt() { } 1325 1326 BNodeIt(Invalid i) : Node(INVALID) { } 1327 1328 explicit BNodeIt(const Graph& _graph) : graph(&_graph) { 1329 graph->firstBNode(static_cast<Node&>(*this)); 1330 } 1331 1332 BNodeIt(const Graph& _graph, const Node& node) 1333 : Node(node), graph(&_graph) {} 1334 1335 BNodeIt& operator++() { 1336 graph->nextBNode(*this); 1337 return *this; 1338 } 1339 }; 1340 1341 class EdgeIt : public Edge { 1342 friend class BpUGraphExtender; 1343 const Graph* graph; 1344 public: 1345 1346 EdgeIt() { } 1347 1348 EdgeIt(Invalid i) : Edge(INVALID) { } 1349 1350 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { 1351 graph->first(static_cast<Edge&>(*this)); 1352 } 1353 1354 EdgeIt(const Graph& _graph, const Edge& edge) 1355 : Edge(edge), graph(&_graph) { } 1356 1357 EdgeIt& operator++() { 1358 graph->next(*this); 1359 return *this; 1360 } 1361 1362 }; 1363 1364 class UEdgeIt : public UEdge { 1365 friend class BpUGraphExtender; 1366 const Graph* graph; 1367 public: 1368 1369 UEdgeIt() { } 1370 1371 UEdgeIt(Invalid i) : UEdge(INVALID) { } 1372 1373 explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { 1374 graph->first(static_cast<UEdge&>(*this)); 1375 } 1376 1377 UEdgeIt(const Graph& _graph, const UEdge& edge) 1378 : UEdge(edge), graph(&_graph) { } 1379 1380 UEdgeIt& operator++() { 1381 graph->next(*this); 1382 return *this; 1383 } 1384 }; 1385 1386 class OutEdgeIt : public Edge { 1387 friend class BpUGraphExtender; 1388 const Graph* graph; 1389 public: 1390 1391 OutEdgeIt() { } 1392 1393 OutEdgeIt(Invalid i) : Edge(i) { } 1394 1395 OutEdgeIt(const Graph& _graph, const Node& node) 1396 : graph(&_graph) { 1397 graph->firstOut(*this, node); 1398 } 1399 1400 OutEdgeIt(const Graph& _graph, const Edge& edge) 1401 : Edge(edge), graph(&_graph) {} 1402 1403 OutEdgeIt& operator++() { 1404 graph->nextOut(*this); 1405 return *this; 1406 } 1407 1408 }; 1409 1410 1411 class InEdgeIt : public Edge { 1412 friend class BpUGraphExtender; 1413 const Graph* graph; 1414 public: 1415 1416 InEdgeIt() { } 1417 1418 InEdgeIt(Invalid i) : Edge(i) { } 1419 1420 InEdgeIt(const Graph& _graph, const Node& node) 1421 : graph(&_graph) { 1422 graph->firstIn(*this, node); 1423 } 1424 1425 InEdgeIt(const Graph& _graph, const Edge& edge) : 1426 Edge(edge), graph(&_graph) {} 1427 1428 InEdgeIt& operator++() { 1429 graph->nextIn(*this); 1430 return *this; 1431 } 1432 1433 }; 1434 1435 /// \brief Base node of the iterator 1436 /// 1437 /// Returns the base node (ie. the source in this case) of the iterator 1438 Node baseNode(const OutEdgeIt &e) const { 1439 return Parent::source((Edge&)e); 1440 } 1441 /// \brief Running node of the iterator 1442 /// 1443 /// Returns the running node (ie. the target in this case) of the 1444 /// iterator 1445 Node runningNode(const OutEdgeIt &e) const { 1446 return Parent::target((Edge&)e); 1447 } 1448 1449 /// \brief Base node of the iterator 1450 /// 1451 /// Returns the base node (ie. the target in this case) of the iterator 1452 Node baseNode(const InEdgeIt &e) const { 1453 return Parent::target((Edge&)e); 1454 } 1455 /// \brief Running node of the iterator 1456 /// 1457 /// Returns the running node (ie. the source in this case) of the 1458 /// iterator 1459 Node runningNode(const InEdgeIt &e) const { 1460 return Parent::source((Edge&)e); 1461 } 1462 1463 class IncEdgeIt : public Parent::UEdge { 1464 friend class BpUGraphExtender; 1465 const Graph* graph; 1466 bool direction; 1467 public: 1468 1469 IncEdgeIt() { } 1470 1471 IncEdgeIt(Invalid i) : UEdge(i), direction(true) { } 1472 1473 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { 1474 graph->firstInc(*this, direction, n); 1475 } 1476 1477 IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) 1478 : graph(&_graph), UEdge(ue) { 1479 direction = (graph->source(ue) == n); 1480 } 1481 1482 IncEdgeIt& operator++() { 1483 graph->nextInc(*this, direction); 1484 return *this; 1485 } 1486 }; 1487 1488 1489 /// Base node of the iterator 1490 /// 1491 /// Returns the base node of the iterator 1492 Node baseNode(const IncEdgeIt &e) const { 1493 return e.direction ? source(e) : target(e); 1494 } 1495 1496 /// Running node of the iterator 1497 /// 1498 /// Returns the running node of the iterator 1499 Node runningNode(const IncEdgeIt &e) const { 1500 return e.direction ? target(e) : source(e); 1501 } 1502 1503 template <typename _Value> 1504 class ANodeMap 1505 : public IterableMapExtender<DefaultMap<Graph, ANode, _Value> > { 1506 public: 1507 typedef BpUGraphExtender Graph; 1508 typedef IterableMapExtender<DefaultMap<Graph, ANode, _Value> > 1509 Parent; 1510 1511 ANodeMap(const Graph& _g) 1512 : Parent(_g) {} 1513 ANodeMap(const Graph& _g, const _Value& _v) 1514 : Parent(_g, _v) {} 1515 1516 ANodeMap& operator=(const ANodeMap& cmap) { 1517 return operator=<ANodeMap>(cmap); 1518 } 1519 1520 1521 /// \brief Template assign operator. 1522 /// 1523 /// The given parameter should be conform to the ReadMap 1524 /// concept and could be indiced by the current item set of 1525 /// the ANodeMap. In this case the value for each item 1526 /// is assigned by the value of the given ReadMap. 1527 template <typename CMap> 1528 ANodeMap& operator=(const CMap& cmap) { 1529 checkConcept<concept::ReadMap<ANode, _Value>, CMap>(); 1530 const typename Parent::Graph* graph = Parent::getGraph(); 1531 ANode it; 1532 for (graph->first(it); it != INVALID; graph->next(it)) { 1533 Parent::set(it, cmap[it]); 1534 } 1535 return *this; 1536 } 1537 1538 }; 1539 1540 template <typename _Value> 1541 class BNodeMap 1542 : public IterableMapExtender<DefaultMap<Graph, BNode, _Value> > { 1543 public: 1544 typedef BpUGraphExtender Graph; 1545 typedef IterableMapExtender<DefaultMap<Graph, BNode, _Value> > 1546 Parent; 1547 1548 BNodeMap(const Graph& _g) 1549 : Parent(_g) {} 1550 BNodeMap(const Graph& _g, const _Value& _v) 1551 : Parent(_g, _v) {} 1552 1553 BNodeMap& operator=(const BNodeMap& cmap) { 1554 return operator=<BNodeMap>(cmap); 1555 } 1556 1557 1558 /// \brief Template assign operator. 1559 /// 1560 /// The given parameter should be conform to the ReadMap 1561 /// concept and could be indiced by the current item set of 1562 /// the BNodeMap. In this case the value for each item 1563 /// is assigned by the value of the given ReadMap. 1564 template <typename CMap> 1565 BNodeMap& operator=(const CMap& cmap) { 1566 checkConcept<concept::ReadMap<BNode, _Value>, CMap>(); 1567 const typename Parent::Graph* graph = Parent::getGraph(); 1568 BNode it; 1569 for (graph->first(it); it != INVALID; graph->next(it)) { 1570 Parent::set(it, cmap[it]); 1571 } 1572 return *this; 1573 } 1574 1575 }; 1576 1577 protected: 1578 1579 template <typename _Value> 1580 class NodeMapBase : public NodeNotifier::ObserverBase { 1581 public: 1582 typedef BpUGraphExtender Graph; 1583 1584 typedef Node Key; 1585 typedef _Value Value; 1586 1587 /// The reference type of the map; 1588 typedef typename BNodeMap<_Value>::Reference Reference; 1589 /// The pointer type of the map; 1590 typedef typename BNodeMap<_Value>::Pointer Pointer; 1591 1592 /// The const value type of the map. 1593 typedef const Value ConstValue; 1594 /// The const reference type of the map; 1595 typedef typename BNodeMap<_Value>::ConstReference ConstReference; 1596 /// The pointer type of the map; 1597 typedef typename BNodeMap<_Value>::ConstPointer ConstPointer; 1598 1599 typedef True ReferenceMapTag; 1600 1601 NodeMapBase(const Graph& _g) 1602 : graph(&_g), bNodeMap(_g), aNodeMap(_g) { 1603 NodeNotifier::ObserverBase::attach(_g.getNotifier(Node())); 1604 } 1605 NodeMapBase(const Graph& _g, const _Value& _v) 1606 : graph(&_g), bNodeMap(_g, _v), 1607 aNodeMap(_g, _v) { 1608 NodeNotifier::ObserverBase::attach(_g.getNotifier(Node())); 1609 } 1610 1611 virtual ~NodeMapBase() { 1612 if (NodeNotifier::ObserverBase::attached()) { 1613 NodeNotifier::ObserverBase::detach(); 1614 } 1615 } 1616 1617 ConstReference operator[](const Key& node) const { 1618 if (Parent::aNode(node)) { 1619 return aNodeMap[node]; 1620 } else { 1621 return bNodeMap[node]; 1622 } 1623 } 1624 1625 Reference operator[](const Key& node) { 1626 if (Parent::aNode(node)) { 1627 return aNodeMap[node]; 1628 } else { 1629 return bNodeMap[node]; 1630 } 1631 } 1632 1633 void set(const Key& node, const Value& value) { 1634 if (Parent::aNode(node)) { 1635 aNodeMap.set(node, value); 1636 } else { 1637 bNodeMap.set(node, value); 1638 } 1639 } 1640 1641 protected: 1642 1643 virtual void add(const Node&) {} 1644 virtual void add(const std::vector<Node>&) {} 1645 virtual void erase(const Node&) {} 1646 virtual void erase(const std::vector<Node>&) {} 1647 virtual void clear() {} 1648 virtual void build() {} 1649 1650 const Graph* getGraph() const { return graph; } 1651 1652 private: 1653 const Graph* graph; 1654 BNodeMap<_Value> bNodeMap; 1655 ANodeMap<_Value> aNodeMap; 1656 }; 1657 1658 public: 1659 1660 template <typename _Value> 1661 class NodeMap 1662 : public IterableMapExtender<NodeMapBase<_Value> > { 1663 public: 1664 typedef BpUGraphExtender Graph; 1665 typedef IterableMapExtender< NodeMapBase<_Value> > Parent; 1666 1667 NodeMap(const Graph& _g) 1668 : Parent(_g) {} 1669 NodeMap(const Graph& _g, const _Value& _v) 1670 : Parent(_g, _v) {} 1671 1672 NodeMap& operator=(const NodeMap& cmap) { 1673 return operator=<NodeMap>(cmap); 1674 } 1675 1676 1677 /// \brief Template assign operator. 1678 /// 1679 /// The given parameter should be conform to the ReadMap 1680 /// concept and could be indiced by the current item set of 1681 /// the NodeMap. In this case the value for each item 1682 /// is assigned by the value of the given ReadMap. 1683 template <typename CMap> 1684 NodeMap& operator=(const CMap& cmap) { 1685 checkConcept<concept::ReadMap<Node, _Value>, CMap>(); 1686 const typename Parent::Graph* graph = Parent::getGraph(); 1687 Node it; 1688 for (graph->first(it); it != INVALID; graph->next(it)) { 1689 Parent::set(it, cmap[it]); 1690 } 1691 return *this; 1692 } 1693 1694 }; 1695 1696 1697 1698 template <typename _Value> 1699 class EdgeMap 1700 : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > { 1701 public: 1702 typedef BpUGraphExtender Graph; 1703 typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 1704 1705 EdgeMap(const Graph& _g) 1706 : Parent(_g) {} 1707 EdgeMap(const Graph& _g, const _Value& _v) 1708 : Parent(_g, _v) {} 1709 1710 EdgeMap& operator=(const EdgeMap& cmap) { 1711 return operator=<EdgeMap>(cmap); 1712 } 1713 1714 template <typename CMap> 1715 EdgeMap& operator=(const CMap& cmap) { 1716 checkConcept<concept::ReadMap<Edge, _Value>, CMap>(); 1717 const typename Parent::Graph* graph = Parent::getGraph(); 1718 Edge it; 1719 for (graph->first(it); it != INVALID; graph->next(it)) { 1720 Parent::set(it, cmap[it]); 1721 } 1722 return *this; 1723 } 1724 }; 1725 1726 template <typename _Value> 1727 class UEdgeMap 1728 : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > { 1729 public: 1730 typedef BpUGraphExtender Graph; 1731 typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > 1732 Parent; 1733 1734 UEdgeMap(const Graph& _g) 1735 : Parent(_g) {} 1736 UEdgeMap(const Graph& _g, const _Value& _v) 1737 : Parent(_g, _v) {} 1738 1739 UEdgeMap& operator=(const UEdgeMap& cmap) { 1740 return operator=<UEdgeMap>(cmap); 1741 } 1742 1743 template <typename CMap> 1744 UEdgeMap& operator=(const CMap& cmap) { 1745 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>(); 1746 const typename Parent::Graph* graph = Parent::getGraph(); 1747 UEdge it; 1748 for (graph->first(it); it != INVALID; graph->next(it)) { 1749 Parent::set(it, cmap[it]); 1750 } 1751 return *this; 1752 } 1753 }; 1754 1755 1756 Node addANode() { 1757 Node node = Parent::addANode(); 1758 getNotifier(ANode()).add(node); 1759 getNotifier(Node()).add(node); 1760 return node; 1761 } 1762 1763 Node addBNode() { 1764 Node node = Parent::addBNode(); 1765 getNotifier(BNode()).add(node); 1766 getNotifier(Node()).add(node); 1767 return node; 1768 } 1769 1770 UEdge addEdge(const Node& source, const Node& target) { 1771 UEdge uedge = Parent::addEdge(source, target); 1772 getNotifier(UEdge()).add(uedge); 1773 1774 std::vector<Edge> edges; 1775 edges.push_back(direct(uedge, true)); 1776 edges.push_back(direct(uedge, false)); 1777 getNotifier(Edge()).add(edges); 1778 1779 return uedge; 1780 } 1781 1782 void clear() { 1783 getNotifier(Edge()).clear(); 1784 getNotifier(UEdge()).clear(); 1785 getNotifier(Node()).clear(); 1786 getNotifier(BNode()).clear(); 1787 getNotifier(ANode()).clear(); 1788 Parent::clear(); 1789 } 1790 1791 void erase(const Node& node) { 1792 UEdge uedge; 1793 bool dir; 1794 Parent::firstInc(uedge, dir, node); 1795 while (uedge != INVALID ) { 1796 erase(uedge); 1797 Parent::firstInc(uedge, dir, node); 1798 } 1799 1800 getNotifier(Node()).erase(node); 1801 Parent::erase(node); 1802 } 1803 1804 void erase(const UEdge& uedge) { 1805 std::vector<Edge> edges; 1806 edges.push_back(direct(uedge, true)); 1807 edges.push_back(direct(uedge, false)); 1808 getNotifier(Edge()).erase(edges); 1809 getNotifier(UEdge()).erase(uedge); 1810 Parent::erase(uedge); 1811 } 1812 1813 1814 ~BpUGraphExtender() { 1815 getNotifier(Edge()).clear(); 1816 getNotifier(UEdge()).clear(); 1817 getNotifier(Node()).clear(); 1818 getNotifier(BNode()).clear(); 1819 getNotifier(ANode()).clear(); 1820 } 1821 616 1822 617 1823 }; -
lemon/bits/static_map.h
r1961 r1979 57 57 public: 58 58 59 /// \brief Exception class for uns inported exceptions.60 class Uns inportedOperation : public lemon::LogicError {59 /// \brief Exception class for unsupported exceptions. 60 class UnsupportedOperation : public lemon::LogicError { 61 61 public: 62 62 virtual const char* exceptionName() const { 63 return "lemon::StaticMap::Uns inportedOperation";63 return "lemon::StaticMap::UnsupportedOperation"; 64 64 } 65 65 }; … … 188 188 189 189 void add(const Key&) { 190 throw Uns inportedOperation();190 throw UnsupportedOperation(); 191 191 } 192 192 … … 196 196 /// and it overrides the erase() member function of the observer base. 197 197 void erase(const Key&) { 198 throw Uns inportedOperation();198 throw UnsupportedOperation(); 199 199 } 200 200 … … 225 225 }; 226 226 227 /// \e228 template <typename _Base>229 class StaticMappableGraphExtender : public _Base {230 public:231 232 typedef StaticMappableGraphExtender<_Base> Graph;233 typedef _Base Parent;234 235 typedef typename Parent::Node Node;236 typedef typename Parent::NodeIt NodeIt;237 238 typedef typename Parent::Edge Edge;239 typedef typename Parent::EdgeIt EdgeIt;240 241 242 template <typename _Value>243 class NodeMap244 : public IterableMapExtender<StaticMap<Graph, Node, _Value> > {245 public:246 typedef StaticMappableGraphExtender Graph;247 typedef IterableMapExtender<StaticMap<Graph, Node, _Value> > Parent;248 249 NodeMap(const Graph& _g)250 : Parent(_g) {}251 NodeMap(const Graph& _g, const _Value& _v)252 : Parent(_g, _v) {}253 254 NodeMap& operator=(const NodeMap& cmap) {255 return operator=<NodeMap>(cmap);256 }257 258 259 /// \brief Template assign operator.260 ///261 /// The given parameter should be conform to the ReadMap262 /// concecpt and could be indiced by the current item set of263 /// the NodeMap. In this case the value for each item264 /// is assigned by the value of the given ReadMap.265 template <typename CMap>266 NodeMap& operator=(const CMap& cmap) {267 checkConcept<concept::ReadMap<Node, _Value>, CMap>();268 const typename Parent::Graph* graph = Parent::getGraph();269 Node it;270 for (graph->first(it); it != INVALID; graph->next(it)) {271 Parent::set(it, cmap[it]);272 }273 return *this;274 }275 276 };277 278 template <typename _Value>279 class EdgeMap280 : public IterableMapExtender<StaticMap<Graph, Edge, _Value> > {281 public:282 typedef StaticMappableGraphExtender Graph;283 typedef IterableMapExtender<StaticMap<Graph, Edge, _Value> > Parent;284 285 EdgeMap(const Graph& _g)286 : Parent(_g) {}287 EdgeMap(const Graph& _g, const _Value& _v)288 : Parent(_g, _v) {}289 290 EdgeMap& operator=(const EdgeMap& cmap) {291 return operator=<EdgeMap>(cmap);292 }293 294 template <typename CMap>295 EdgeMap& operator=(const CMap& cmap) {296 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();297 const typename Parent::Graph* graph = Parent::getGraph();298 Edge it;299 for (graph->first(it); it != INVALID; graph->next(it)) {300 Parent::set(it, cmap[it]);301 }302 return *this;303 }304 };305 306 };307 308 /// \e309 template <typename _Base>310 class StaticMappableUGraphExtender :311 public StaticMappableGraphExtender<_Base> {312 public:313 314 typedef StaticMappableUGraphExtender Graph;315 typedef StaticMappableGraphExtender<_Base> Parent;316 317 typedef typename Parent::UEdge UEdge;318 319 template <typename _Value>320 class UEdgeMap321 : public IterableMapExtender<StaticMap<Graph, UEdge, _Value> > {322 public:323 typedef StaticMappableUGraphExtender Graph;324 typedef IterableMapExtender<325 StaticMap<Graph, UEdge, _Value> > Parent;326 327 UEdgeMap(const Graph& _g)328 : Parent(_g) {}329 UEdgeMap(const Graph& _g, const _Value& _v)330 : Parent(_g, _v) {}331 332 UEdgeMap& operator=(const UEdgeMap& cmap) {333 return operator=<UEdgeMap>(cmap);334 }335 336 template <typename CMap>337 UEdgeMap& operator=(const CMap& cmap) {338 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();339 const typename Parent::Graph* graph = Parent::getGraph();340 UEdge it;341 for (graph->first(it); it != INVALID; graph->next(it)) {342 Parent::set(it, cmap[it]);343 }344 return *this;345 }346 };347 348 };349 350 template <typename _Base>351 class StaticMappableBpUGraphExtender : public _Base {352 public:353 354 typedef _Base Parent;355 typedef StaticMappableBpUGraphExtender Graph;356 357 typedef typename Parent::Node Node;358 typedef typename Parent::ANode ANode;359 typedef typename Parent::BNode BNode;360 typedef typename Parent::Edge Edge;361 typedef typename Parent::UEdge UEdge;362 363 template <typename _Value>364 class ANodeMap365 : public IterableMapExtender<StaticMap<Graph, ANode, _Value> > {366 public:367 typedef StaticMappableBpUGraphExtender Graph;368 typedef IterableMapExtender<StaticMap<Graph, ANode, _Value> >369 Parent;370 371 ANodeMap(const Graph& _g)372 : Parent(_g) {}373 ANodeMap(const Graph& _g, const _Value& _v)374 : Parent(_g, _v) {}375 376 ANodeMap& operator=(const ANodeMap& cmap) {377 return operator=<ANodeMap>(cmap);378 }379 380 381 /// \brief Template assign operator.382 ///383 /// The given parameter should be conform to the ReadMap384 /// concept and could be indiced by the current item set of385 /// the ANodeMap. In this case the value for each item386 /// is assigned by the value of the given ReadMap.387 template <typename CMap>388 ANodeMap& operator=(const CMap& cmap) {389 checkConcept<concept::ReadMap<ANode, _Value>, CMap>();390 const typename Parent::Graph* graph = Parent::getGraph();391 ANode it;392 for (graph->first(it); it != INVALID; graph->next(it)) {393 Parent::set(it, cmap[it]);394 }395 return *this;396 }397 398 };399 400 template <typename _Value>401 class BNodeMap402 : public IterableMapExtender<StaticMap<Graph, BNode, _Value> > {403 public:404 typedef StaticMappableBpUGraphExtender Graph;405 typedef IterableMapExtender<StaticMap<Graph, BNode, _Value> >406 Parent;407 408 BNodeMap(const Graph& _g)409 : Parent(_g) {}410 BNodeMap(const Graph& _g, const _Value& _v)411 : Parent(_g, _v) {}412 413 BNodeMap& operator=(const BNodeMap& cmap) {414 return operator=<BNodeMap>(cmap);415 }416 417 418 /// \brief Template assign operator.419 ///420 /// The given parameter should be conform to the ReadMap421 /// concept and could be indiced by the current item set of422 /// the BNodeMap. In this case the value for each item423 /// is assigned by the value of the given ReadMap.424 template <typename CMap>425 BNodeMap& operator=(const CMap& cmap) {426 checkConcept<concept::ReadMap<BNode, _Value>, CMap>();427 const typename Parent::Graph* graph = Parent::getGraph();428 BNode it;429 for (graph->first(it); it != INVALID; graph->next(it)) {430 Parent::set(it, cmap[it]);431 }432 return *this;433 }434 435 };436 437 protected:438 439 template <typename _Value>440 class NodeMapBase : public Parent::NodeNotifier::ObserverBase {441 public:442 typedef StaticMappableBpUGraphExtender Graph;443 444 typedef Node Key;445 typedef _Value Value;446 447 /// The reference type of the map;448 typedef typename BNodeMap<_Value>::Reference Reference;449 /// The pointer type of the map;450 typedef typename BNodeMap<_Value>::Pointer Pointer;451 452 /// The const value type of the map.453 typedef const Value ConstValue;454 /// The const reference type of the map;455 typedef typename BNodeMap<_Value>::ConstReference ConstReference;456 /// The pointer type of the map;457 typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;458 459 typedef True ReferenceMapTag;460 461 NodeMapBase(const Graph& _g)462 : graph(&_g), bNodeMap(_g), aNodeMap(_g) {463 Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));464 }465 NodeMapBase(const Graph& _g, const _Value& _v)466 : graph(&_g), bNodeMap(_g, _v),467 aNodeMap(_g, _v) {468 Parent::NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));469 }470 471 virtual ~NodeMapBase() {472 if (Parent::NodeNotifier::ObserverBase::attached()) {473 Parent::NodeNotifier::ObserverBase::detach();474 }475 }476 477 ConstReference operator[](const Key& node) const {478 if (Parent::aNode(node)) {479 return aNodeMap[node];480 } else {481 return bNodeMap[node];482 }483 }484 485 Reference operator[](const Key& node) {486 if (Parent::aNode(node)) {487 return aNodeMap[node];488 } else {489 return bNodeMap[node];490 }491 }492 493 void set(const Key& node, const Value& value) {494 if (Parent::aNode(node)) {495 aNodeMap.set(node, value);496 } else {497 bNodeMap.set(node, value);498 }499 }500 501 protected:502 503 virtual void add(const Node&) {}504 virtual void add(const std::vector<Node>&) {}505 virtual void erase(const Node&) {}506 virtual void erase(const std::vector<Node>&) {}507 virtual void clear() {}508 virtual void build() {}509 510 const Graph* getGraph() const { return graph; }511 512 private:513 const Graph* graph;514 BNodeMap<_Value> bNodeMap;515 ANodeMap<_Value> aNodeMap;516 };517 518 public:519 520 template <typename _Value>521 class NodeMap522 : public IterableMapExtender<NodeMapBase<_Value> > {523 public:524 typedef StaticMappableBpUGraphExtender Graph;525 typedef IterableMapExtender< NodeMapBase<_Value> > Parent;526 527 NodeMap(const Graph& _g)528 : Parent(_g) {}529 NodeMap(const Graph& _g, const _Value& _v)530 : Parent(_g, _v) {}531 532 NodeMap& operator=(const NodeMap& cmap) {533 return operator=<NodeMap>(cmap);534 }535 536 537 /// \brief Template assign operator.538 ///539 /// The given parameter should be conform to the ReadMap540 /// concept and could be indiced by the current item set of541 /// the NodeMap. In this case the value for each item542 /// is assigned by the value of the given ReadMap.543 template <typename CMap>544 NodeMap& operator=(const CMap& cmap) {545 checkConcept<concept::ReadMap<Node, _Value>, CMap>();546 const typename Parent::Graph* graph = Parent::getGraph();547 Node it;548 for (graph->first(it); it != INVALID; graph->next(it)) {549 Parent::set(it, cmap[it]);550 }551 return *this;552 }553 554 };555 556 557 558 template <typename _Value>559 class EdgeMap560 : public IterableMapExtender<StaticMap<Graph, Edge, _Value> > {561 public:562 typedef StaticMappableBpUGraphExtender Graph;563 typedef IterableMapExtender<StaticMap<Graph, Edge, _Value> > Parent;564 565 EdgeMap(const Graph& _g)566 : Parent(_g) {}567 EdgeMap(const Graph& _g, const _Value& _v)568 : Parent(_g, _v) {}569 570 EdgeMap& operator=(const EdgeMap& cmap) {571 return operator=<EdgeMap>(cmap);572 }573 574 template <typename CMap>575 EdgeMap& operator=(const CMap& cmap) {576 checkConcept<concept::ReadMap<Edge, _Value>, CMap>();577 const typename Parent::Graph* graph = Parent::getGraph();578 Edge it;579 for (graph->first(it); it != INVALID; graph->next(it)) {580 Parent::set(it, cmap[it]);581 }582 return *this;583 }584 };585 586 template <typename _Value>587 class UEdgeMap588 : public IterableMapExtender<StaticMap<Graph, UEdge, _Value> > {589 public:590 typedef StaticMappableBpUGraphExtender Graph;591 typedef IterableMapExtender<StaticMap<Graph, UEdge, _Value> >592 Parent;593 594 UEdgeMap(const Graph& _g)595 : Parent(_g) {}596 UEdgeMap(const Graph& _g, const _Value& _v)597 : Parent(_g, _v) {}598 599 UEdgeMap& operator=(const UEdgeMap& cmap) {600 return operator=<UEdgeMap>(cmap);601 }602 603 template <typename CMap>604 UEdgeMap& operator=(const CMap& cmap) {605 checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();606 const typename Parent::Graph* graph = Parent::getGraph();607 UEdge it;608 for (graph->first(it); it != INVALID; graph->next(it)) {609 Parent::set(it, cmap[it]);610 }611 return *this;612 }613 };614 615 };616 617 227 } 618 228
Note: See TracChangeset
for help on using the changeset viewer.