Changes in / [105:e4948ef6a4ca:106:9ba2d265e191] in lemon
- Files:
-
- 17 added
- 15 edited
Legend:
- Unmodified
- Added
- Removed
-
.hgignore
r9 r85 33 33 ^objs.*/.* 34 34 ^test/[a-z_]*$ 35 ^demo/.*_demo$ -
configure.ac
r64 r91 11 11 12 12 AC_PREREQ([2.59]) 13 AC_INIT([LEMON], [lemon_version()], [ etik-ol@cs.elte.hu], [lemon])13 AC_INIT([LEMON], [lemon_version()], [lemon-devel@lemon.cs.elte.hu], [lemon]) 14 14 AC_CONFIG_AUX_DIR([build-aux]) 15 15 AC_CONFIG_MACRO_DIR([m4]) -
demo/Makefile.am
r1 r85 4 4 if WANT_DEMO 5 5 6 noinst_PROGRAMS += 6 noinst_PROGRAMS += \ 7 demo/arg_parser_demo 7 8 8 9 endif WANT_DEMO 10 11 demo_arg_parser_demo_SOURCES = demo/arg_parser_demo.cc 12 -
doc/groups.dox
r71 r83 39 39 the diverging requirements of the possible users. In order to save on 40 40 running time or on memory usage, some structures may fail to provide 41 some graph features like edge or node deletion.41 some graph features like arc/edge or node deletion. 42 42 43 43 Alteration of standard containers need a very limited number of … … 45 45 In the case of graph structures, different operations are needed which do 46 46 not alter the physical graph, but gives another view. If some nodes or 47 edges have to be hidden or the reverse oriented graph have to be used, then 47 arcs have to be hidden or the reverse oriented graph have to be used, then 48 48 this is the case. It also may happen that in a flow implementation 49 49 the residual graph can be accessed by another algorithm, or a node-set … … 82 82 @defgroup graph_maps Graph Maps 83 83 @ingroup maps 84 \brief Special Graph-Related Maps.84 \brief Special graph-related maps. 85 85 86 86 This group describes maps that are specifically designed to assign 87 values to the nodes and edges of graphs.87 values to the nodes and arcs of graphs. 88 88 */ 89 89 … … 97 97 maps from other maps. 98 98 99 Most of them are \ref lemon::concepts::ReadMap " ReadMap"s. They can100 make arithmetic operations between one or two maps (negation, scaling, 101 addition, multiplication etc.) or e.g. convert a map to another one 102 of different Value type.99 Most of them are \ref lemon::concepts::ReadMap "read-only maps". 100 They can make arithmetic and logical operations between one or two maps 101 (negation, shifting, addition, multiplication, logical 'and', 'or', 102 'not' etc.) or e.g. convert a map to another one of different Value type. 103 103 104 104 The typical usage of this classes is passing implicit maps to 105 105 algorithms. If a function type algorithm is called then the function 106 106 type map adaptors can be used comfortable. For example let's see the 107 usage of map adaptors with the \c graphToEps() function:107 usage of map adaptors with the \c digraphToEps() function. 108 108 \code 109 109 Color nodeColor(int deg) { … … 117 117 } 118 118 119 Graph::NodeMap<int> degree_map(graph);119 Digraph::NodeMap<int> degree_map(graph); 120 120 121 graphToEps(graph, "graph.eps")121 digraphToEps(graph, "graph.eps") 122 122 .coords(coords).scaleToA4().undirected() 123 .nodeColors(composeMap(functor Map(nodeColor), degree_map))123 .nodeColors(composeMap(functorToMap(nodeColor), degree_map)) 124 124 .run(); 125 125 \endcode 126 The \c functor Map() function makes an \c int to \c Color map from the126 The \c functorToMap() function makes an \c int to \c Color map from the 127 127 \e nodeColor() function. The \c composeMap() compose the \e degree_map 128 and the previous created map. The composed map isproper function to129 get color of each node.128 and the previously created map. The composed map is a proper function to 129 get the color of each node. 130 130 131 131 The usage with class type algorithms is little bit harder. In this … … 133 133 function map adaptors give back temporary objects. 134 134 \code 135 Graph graph; 136 137 typedef Graph::EdgeMap<double> DoubleEdgeMap; 138 DoubleEdgeMap length(graph); 139 DoubleEdgeMap speed(graph); 140 141 typedef DivMap<DoubleEdgeMap, DoubleEdgeMap> TimeMap; 142 135 Digraph graph; 136 137 typedef Digraph::ArcMap<double> DoubleArcMap; 138 DoubleArcMap length(graph); 139 DoubleArcMap speed(graph); 140 141 typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap; 143 142 TimeMap time(length, speed); 144 143 145 Dijkstra< Graph, TimeMap> dijkstra(graph, time);144 Dijkstra<Digraph, TimeMap> dijkstra(graph, time); 146 145 dijkstra.run(source, target); 147 146 \endcode 148 149 We have a length map and a maximum speed map on a graph. The minimum 150 time to pass the edge can be calculated as the division of the two 151 maps which can be done implicitly with the \c DivMap template 147 We have a length map and a maximum speed map on the arcs of a digraph. 148 The minimum time to pass the arc can be calculated as the division of 149 the two maps which can be done implicitly with the \c DivMap template 152 150 class. We use the implicit minimum time map as the length map of the 153 151 \c Dijkstra algorithm. … … 316 314 This group contains algorithm objects and functions to calculate 317 315 matchings in graphs and bipartite graphs. The general matching problem is 318 finding a subset of the edges which does not shares common endpoints.316 finding a subset of the arcs which does not shares common endpoints. 319 317 320 318 There are several different algorithms for calculate matchings in -
lemon/Makefile.am
r103 r106 8 8 9 9 lemon_libemon_la_SOURCES = \ 10 lemon/arg_parser.cc \ 10 11 lemon/base.cc \ 11 12 lemon/random.cc … … 16 17 17 18 lemon_HEADERS += \ 18 lemon/concept_check.h \ 19 lemon/arg_parser.h \ 20 lemon/bfs.h \ 21 lemon/bin_heap.h \ 22 lemon/dfs.h \ 23 lemon/dijkstra.h \ 19 24 lemon/dim2.h \ 20 25 lemon/error.h \ 26 lemon/graph_utils.h \ 21 27 lemon/kruskal.h \ 22 28 lemon/list_graph.h \ 23 29 lemon/maps.h \ 24 30 lemon/math.h \ 31 lemon/path.h \ 25 32 lemon/random.h \ 26 33 lemon/tolerance.h \ … … 35 42 lemon/bits/invalid.h \ 36 43 lemon/bits/map_extender.h \ 44 lemon/bits/path_dump.h \ 37 45 lemon/bits/traits.h \ 38 46 lemon/bits/utility.h \ … … 43 51 lemon/concepts/digraph.h \ 44 52 lemon/concepts/graph.h \ 53 lemon/concepts/heap.h \ 45 54 lemon/concepts/maps.h \ 55 lemon/concepts/path.h \ 46 56 lemon/concepts/graph_components.h -
lemon/bits/graph_extender.h
r77 r78 65 65 } 66 66 67 Node oppositeNode(const Node &n , const Arc &e) const {68 if (n == Parent::source(e))69 return Parent::target( e);70 else if(n ==Parent::target(e))71 return Parent::source( e);67 Node oppositeNode(const Node &node, const Arc &arc) const { 68 if (node == Parent::source(arc)) 69 return Parent::target(arc); 70 else if(node == Parent::target(arc)) 71 return Parent::source(arc); 72 72 else 73 73 return INVALID; … … 96 96 97 97 class NodeIt : public Node { 98 const Digraph* digraph;98 const Digraph* _digraph; 99 99 public: 100 100 … … 103 103 NodeIt(Invalid i) : Node(i) { } 104 104 105 explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) {106 _digraph .first(static_cast<Node&>(*this));107 } 108 109 NodeIt(const Digraph& _digraph, const Node& node)110 : Node(node), digraph(&_digraph) {}105 explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) { 106 _digraph->first(static_cast<Node&>(*this)); 107 } 108 109 NodeIt(const Digraph& digraph, const Node& node) 110 : Node(node), _digraph(&digraph) {} 111 111 112 112 NodeIt& operator++() { 113 digraph->next(*this);113 _digraph->next(*this); 114 114 return *this; 115 115 } … … 119 119 120 120 class ArcIt : public Arc { 121 const Digraph* digraph;121 const Digraph* _digraph; 122 122 public: 123 123 … … 126 126 ArcIt(Invalid i) : Arc(i) { } 127 127 128 explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {129 _digraph .first(static_cast<Arc&>(*this));130 } 131 132 ArcIt(const Digraph& _digraph, const Arc& e) :133 Arc( e), digraph(&_digraph) { }128 explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) { 129 _digraph->first(static_cast<Arc&>(*this)); 130 } 131 132 ArcIt(const Digraph& digraph, const Arc& arc) : 133 Arc(arc), _digraph(&digraph) { } 134 134 135 135 ArcIt& operator++() { 136 digraph->next(*this);136 _digraph->next(*this); 137 137 return *this; 138 138 } … … 142 142 143 143 class OutArcIt : public Arc { 144 const Digraph* digraph;144 const Digraph* _digraph; 145 145 public: 146 146 … … 149 149 OutArcIt(Invalid i) : Arc(i) { } 150 150 151 OutArcIt(const Digraph& _digraph, const Node& node)152 : digraph(&_digraph) {153 _digraph .firstOut(*this, node);154 } 155 156 OutArcIt(const Digraph& _digraph, const Arc& arc)157 : Arc(arc), digraph(&_digraph) {}151 OutArcIt(const Digraph& digraph, const Node& node) 152 : _digraph(&digraph) { 153 _digraph->firstOut(*this, node); 154 } 155 156 OutArcIt(const Digraph& digraph, const Arc& arc) 157 : Arc(arc), _digraph(&digraph) {} 158 158 159 159 OutArcIt& operator++() { 160 digraph->nextOut(*this);160 _digraph->nextOut(*this); 161 161 return *this; 162 162 } … … 166 166 167 167 class InArcIt : public Arc { 168 const Digraph* digraph;168 const Digraph* _digraph; 169 169 public: 170 170 … … 173 173 InArcIt(Invalid i) : Arc(i) { } 174 174 175 InArcIt(const Digraph& _digraph, const Node& node)176 : digraph(&_digraph) {177 _digraph .firstIn(*this, node);178 } 179 180 InArcIt(const Digraph& _digraph, const Arc& arc) :181 Arc(arc), digraph(&_digraph) {}175 InArcIt(const Digraph& digraph, const Node& node) 176 : _digraph(&digraph) { 177 _digraph->firstIn(*this, node); 178 } 179 180 InArcIt(const Digraph& digraph, const Arc& arc) : 181 Arc(arc), _digraph(&digraph) {} 182 182 183 183 InArcIt& operator++() { 184 digraph->nextIn(*this);184 _digraph->nextIn(*this); 185 185 return *this; 186 186 } … … 191 191 /// 192 192 /// Returns the base node (i.e. the source in this case) of the iterator 193 Node baseNode(const OutArcIt & e) const {194 return Parent::source( e);193 Node baseNode(const OutArcIt &arc) const { 194 return Parent::source(arc); 195 195 } 196 196 /// \brief Running node of the iterator … … 198 198 /// Returns the running node (i.e. the target in this case) of the 199 199 /// iterator 200 Node runningNode(const OutArcIt & e) const {201 return Parent::target( e);200 Node runningNode(const OutArcIt &arc) const { 201 return Parent::target(arc); 202 202 } 203 203 … … 205 205 /// 206 206 /// Returns the base node (i.e. the target in this case) of the iterator 207 Node baseNode(const InArcIt & e) const {208 return Parent::target( e);207 Node baseNode(const InArcIt &arc) const { 208 return Parent::target(arc); 209 209 } 210 210 /// \brief Running node of the iterator … … 212 212 /// Returns the running node (i.e. the source in this case) of the 213 213 /// iterator 214 Node runningNode(const InArcIt & e) const {215 return Parent::source( e);214 Node runningNode(const InArcIt &arc) const { 215 return Parent::source(arc); 216 216 } 217 217 … … 325 325 }; 326 326 327 /// \ingroup graphbits327 /// \ingroup _graphbits 328 328 /// 329 329 /// \brief Extender for the Graphs … … 333 333 334 334 typedef Base Parent; 335 typedef GraphExtender Digraph;335 typedef GraphExtender Graph; 336 336 337 337 typedef True UndirectedTag; … … 376 376 } 377 377 378 Arc oppositeArc(const Arc & e) const {379 return Parent::direct( e, !Parent::direction(e));378 Arc oppositeArc(const Arc &arc) const { 379 return Parent::direct(arc, !Parent::direction(arc)); 380 380 } 381 381 382 382 using Parent::direct; 383 Arc direct(const Edge & ue, const Node &s) const {384 return Parent::direct( ue, Parent::source(ue) == s);383 Arc direct(const Edge &edge, const Node &node) const { 384 return Parent::direct(edge, Parent::source(edge) == node); 385 385 } 386 386 … … 415 415 416 416 class NodeIt : public Node { 417 const Digraph* digraph;417 const Graph* _graph; 418 418 public: 419 419 … … 422 422 NodeIt(Invalid i) : Node(i) { } 423 423 424 explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) {425 _ digraph.first(static_cast<Node&>(*this));426 } 427 428 NodeIt(const Digraph& _digraph, const Node& node)429 : Node(node), digraph(&_digraph) {}424 explicit NodeIt(const Graph& graph) : _graph(&graph) { 425 _graph->first(static_cast<Node&>(*this)); 426 } 427 428 NodeIt(const Graph& graph, const Node& node) 429 : Node(node), _graph(&graph) {} 430 430 431 431 NodeIt& operator++() { 432 digraph->next(*this);432 _graph->next(*this); 433 433 return *this; 434 434 } … … 438 438 439 439 class ArcIt : public Arc { 440 const Digraph* digraph;440 const Graph* _graph; 441 441 public: 442 442 … … 445 445 ArcIt(Invalid i) : Arc(i) { } 446 446 447 explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {448 _ digraph.first(static_cast<Arc&>(*this));449 } 450 451 ArcIt(const Digraph& _digraph, const Arc& e) :452 Arc( e), digraph(&_digraph) { }447 explicit ArcIt(const Graph& graph) : _graph(&graph) { 448 _graph->first(static_cast<Arc&>(*this)); 449 } 450 451 ArcIt(const Graph& graph, const Arc& arc) : 452 Arc(arc), _graph(&graph) { } 453 453 454 454 ArcIt& operator++() { 455 digraph->next(*this);455 _graph->next(*this); 456 456 return *this; 457 457 } … … 461 461 462 462 class OutArcIt : public Arc { 463 const Digraph* digraph;463 const Graph* _graph; 464 464 public: 465 465 … … 468 468 OutArcIt(Invalid i) : Arc(i) { } 469 469 470 OutArcIt(const Digraph& _digraph, const Node& node)471 : digraph(&_digraph) {472 _ digraph.firstOut(*this, node);473 } 474 475 OutArcIt(const Digraph& _digraph, const Arc& arc)476 : Arc(arc), digraph(&_digraph) {}470 OutArcIt(const Graph& graph, const Node& node) 471 : _graph(&graph) { 472 _graph->firstOut(*this, node); 473 } 474 475 OutArcIt(const Graph& graph, const Arc& arc) 476 : Arc(arc), _graph(&graph) {} 477 477 478 478 OutArcIt& operator++() { 479 digraph->nextOut(*this);479 _graph->nextOut(*this); 480 480 return *this; 481 481 } … … 485 485 486 486 class InArcIt : public Arc { 487 const Digraph* digraph;487 const Graph* _graph; 488 488 public: 489 489 … … 492 492 InArcIt(Invalid i) : Arc(i) { } 493 493 494 InArcIt(const Digraph& _digraph, const Node& node)495 : digraph(&_digraph) {496 _ digraph.firstIn(*this, node);497 } 498 499 InArcIt(const Digraph& _digraph, const Arc& arc) :500 Arc(arc), digraph(&_digraph) {}494 InArcIt(const Graph& graph, const Node& node) 495 : _graph(&graph) { 496 _graph->firstIn(*this, node); 497 } 498 499 InArcIt(const Graph& graph, const Arc& arc) : 500 Arc(arc), _graph(&graph) {} 501 501 502 502 InArcIt& operator++() { 503 digraph->nextIn(*this);503 _graph->nextIn(*this); 504 504 return *this; 505 505 } … … 509 509 510 510 class EdgeIt : public Parent::Edge { 511 const Digraph* digraph;511 const Graph* _graph; 512 512 public: 513 513 … … 516 516 EdgeIt(Invalid i) : Edge(i) { } 517 517 518 explicit EdgeIt(const Digraph& _digraph) : digraph(&_digraph) {519 _ digraph.first(static_cast<Edge&>(*this));520 } 521 522 EdgeIt(const Digraph& _digraph, const Edge&e) :523 Edge(e ), digraph(&_digraph) { }518 explicit EdgeIt(const Graph& graph) : _graph(&graph) { 519 _graph->first(static_cast<Edge&>(*this)); 520 } 521 522 EdgeIt(const Graph& graph, const Edge& edge) : 523 Edge(edge), _graph(&graph) { } 524 524 525 525 EdgeIt& operator++() { 526 digraph->next(*this);527 return *this; 528 } 529 530 }; 531 532 class Inc ArcIt : public Parent::Edge {526 _graph->next(*this); 527 return *this; 528 } 529 530 }; 531 532 class IncEdgeIt : public Parent::Edge { 533 533 friend class GraphExtender; 534 const Digraph* digraph;535 bool direction;536 public: 537 538 Inc ArcIt() { }539 540 Inc ArcIt(Invalid i) : Edge(i),direction(false) { }541 542 Inc ArcIt(const Digraph& _digraph, const Node &n) : digraph(&_digraph) {543 _ digraph.firstInc(*this, direction, n);544 } 545 546 Inc ArcIt(const Digraph& _digraph, const Edge &ue, const Node &n)547 : digraph(&_digraph), Edge(ue) {548 direction = (_digraph.source(ue) == n);549 } 550 551 Inc ArcIt& operator++() {552 digraph->nextInc(*this,direction);534 const Graph* _graph; 535 bool _direction; 536 public: 537 538 IncEdgeIt() { } 539 540 IncEdgeIt(Invalid i) : Edge(i), _direction(false) { } 541 542 IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) { 543 _graph->firstInc(*this, _direction, node); 544 } 545 546 IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node) 547 : _graph(&graph), Edge(edge) { 548 _direction = (_graph->source(edge) == node); 549 } 550 551 IncEdgeIt& operator++() { 552 _graph->nextInc(*this, _direction); 553 553 return *this; 554 554 } … … 558 558 /// 559 559 /// Returns the base node (ie. the source in this case) of the iterator 560 Node baseNode(const OutArcIt & e) const {561 return Parent::source(static_cast<const Arc&>( e));560 Node baseNode(const OutArcIt &arc) const { 561 return Parent::source(static_cast<const Arc&>(arc)); 562 562 } 563 563 /// \brief Running node of the iterator … … 565 565 /// Returns the running node (ie. the target in this case) of the 566 566 /// iterator 567 Node runningNode(const OutArcIt & e) const {568 return Parent::target(static_cast<const Arc&>( e));567 Node runningNode(const OutArcIt &arc) const { 568 return Parent::target(static_cast<const Arc&>(arc)); 569 569 } 570 570 … … 572 572 /// 573 573 /// Returns the base node (ie. the target in this case) of the iterator 574 Node baseNode(const InArcIt & e) const {575 return Parent::target(static_cast<const Arc&>( e));574 Node baseNode(const InArcIt &arc) const { 575 return Parent::target(static_cast<const Arc&>(arc)); 576 576 } 577 577 /// \brief Running node of the iterator … … 579 579 /// Returns the running node (ie. the source in this case) of the 580 580 /// iterator 581 Node runningNode(const InArcIt & e) const {582 return Parent::source(static_cast<const Arc&>( e));581 Node runningNode(const InArcIt &arc) const { 582 return Parent::source(static_cast<const Arc&>(arc)); 583 583 } 584 584 … … 586 586 /// 587 587 /// Returns the base node of the iterator 588 Node baseNode(const Inc ArcIt &e) const {589 return e .direction ? source(e) : target(e);588 Node baseNode(const IncEdgeIt &edge) const { 589 return edge._direction ? source(edge) : target(edge); 590 590 } 591 591 /// Running node of the iterator 592 592 /// 593 593 /// Returns the running node of the iterator 594 Node runningNode(const Inc ArcIt &e) const {595 return e .direction ? target(e) : source(e);594 Node runningNode(const IncEdgeIt &edge) const { 595 return edge._direction ? target(edge) : source(edge); 596 596 } 597 597 … … 600 600 template <typename _Value> 601 601 class NodeMap 602 : public MapExtender<DefaultMap< Digraph, Node, _Value> > {603 public: 604 typedef GraphExtender Digraph;605 typedef MapExtender<DefaultMap< Digraph, Node, _Value> > Parent;606 607 NodeMap(const Digraph& digraph)608 : Parent( digraph) {}609 NodeMap(const Digraph& digraph, const _Value& value)610 : Parent( digraph, value) {}602 : public MapExtender<DefaultMap<Graph, Node, _Value> > { 603 public: 604 typedef GraphExtender Graph; 605 typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent; 606 607 NodeMap(const Graph& graph) 608 : Parent(graph) {} 609 NodeMap(const Graph& graph, const _Value& value) 610 : Parent(graph, value) {} 611 611 612 612 NodeMap& operator=(const NodeMap& cmap) { … … 624 624 template <typename _Value> 625 625 class ArcMap 626 : public MapExtender<DefaultMap< Digraph, Arc, _Value> > {627 public: 628 typedef GraphExtender Digraph;629 typedef MapExtender<DefaultMap< Digraph, Arc, _Value> > Parent;630 631 ArcMap(const Digraph& digraph)632 : Parent( digraph) {}633 ArcMap(const Digraph& digraph, const _Value& value)634 : Parent( digraph, value) {}626 : public MapExtender<DefaultMap<Graph, Arc, _Value> > { 627 public: 628 typedef GraphExtender Graph; 629 typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent; 630 631 ArcMap(const Graph& graph) 632 : Parent(graph) {} 633 ArcMap(const Graph& graph, const _Value& value) 634 : Parent(graph, value) {} 635 635 636 636 ArcMap& operator=(const ArcMap& cmap) { … … 648 648 template <typename _Value> 649 649 class EdgeMap 650 : public MapExtender<DefaultMap< Digraph, Edge, _Value> > {651 public: 652 typedef GraphExtender Digraph;653 typedef MapExtender<DefaultMap< Digraph, Edge, _Value> > Parent;654 655 EdgeMap(const Digraph& digraph)656 : Parent( digraph) {}657 658 EdgeMap(const Digraph& digraph, const _Value& value)659 : Parent( digraph, value) {}650 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { 651 public: 652 typedef GraphExtender Graph; 653 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 654 655 EdgeMap(const Graph& graph) 656 : Parent(graph) {} 657 658 EdgeMap(const Graph& graph, const _Value& value) 659 : Parent(graph, value) {} 660 660 661 661 EdgeMap& operator=(const EdgeMap& cmap) { … … 696 696 } 697 697 698 template <typename Digraph, typename NodeRefMap, typename EdgeRefMap>699 void build(const Digraph& digraph, NodeRefMap& nodeRef,698 template <typename Graph, typename NodeRefMap, typename EdgeRefMap> 699 void build(const Graph& graph, NodeRefMap& nodeRef, 700 700 EdgeRefMap& edgeRef) { 701 Parent::build( digraph, nodeRef, edgeRef);701 Parent::build(graph, nodeRef, edgeRef); 702 702 notifier(Node()).build(); 703 703 notifier(Edge()).build(); … … 724 724 725 725 void erase(const Edge& edge) { 726 std::vector<Arc> ev;727 ev.push_back(Parent::direct(edge, true));728 ev.push_back(Parent::direct(edge, false));729 notifier(Arc()).erase( ev);726 std::vector<Arc> av; 727 av.push_back(Parent::direct(edge, true)); 728 av.push_back(Parent::direct(edge, false)); 729 notifier(Arc()).erase(av); 730 730 notifier(Edge()).erase(edge); 731 731 Parent::erase(edge); -
lemon/concepts/graph.h
r61 r78 64 64 /// the EdgeMap to map values for the edges. The InArcIt and 65 65 /// OutArcIt iterates on the same edges but with opposite 66 /// direction. The Inc ArcIt iterates also on the same edges66 /// direction. The IncEdgeIt iterates also on the same edges 67 67 /// as the OutArcIt and InArcIt but it is not convertible to Arc just 68 68 /// to Edge. … … 271 271 ///\code 272 272 /// int count=0; 273 /// for(Graph::Inc ArcIt e(g, n); e!=INVALID; ++e) ++count;273 /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; 274 274 ///\endcode 275 class Inc ArcIt : public Edge {276 public: 277 /// Default constructor 278 279 /// @warning The default constructor sets the iterator 280 /// to an undefined value. 281 Inc ArcIt() { }282 /// Copy constructor. 283 284 /// Copy constructor. 285 /// 286 Inc ArcIt(const IncArcIt& e) : Edge(e) { }287 /// Initialize the iterator to be invalid. 288 289 /// Initialize the iterator to be invalid. 290 /// 291 Inc ArcIt(Invalid) { }275 class IncEdgeIt : public Edge { 276 public: 277 /// Default constructor 278 279 /// @warning The default constructor sets the iterator 280 /// to an undefined value. 281 IncEdgeIt() { } 282 /// Copy constructor. 283 284 /// Copy constructor. 285 /// 286 IncEdgeIt(const IncEdgeIt& e) : Edge(e) { } 287 /// Initialize the iterator to be invalid. 288 289 /// Initialize the iterator to be invalid. 290 /// 291 IncEdgeIt(Invalid) { } 292 292 /// This constructor sets the iterator to first incident arc. 293 293 294 294 /// This constructor set the iterator to the first incident arc of 295 295 /// the node. 296 Inc ArcIt(const Graph&, const Node&) { }297 /// Edge -> Inc ArcIt conversion296 IncEdgeIt(const Graph&, const Node&) { } 297 /// Edge -> IncEdgeIt conversion 298 298 299 299 /// Sets the iterator to the value of the trivial iterator \c e. 300 300 /// This feature necessitates that each time we 301 301 /// iterate the arc-set, the iteration order is the same. 302 Inc ArcIt(const Graph&, const Edge&) { }302 IncEdgeIt(const Graph&, const Edge&) { } 303 303 /// Next incident arc 304 304 305 305 /// Assign the iterator to the next incident arc 306 306 /// of the corresponding node. 307 Inc ArcIt& operator++() { return *this; }307 IncEdgeIt& operator++() { return *this; } 308 308 }; 309 309 … … 721 721 /// 722 722 /// Returns the base node of the iterator 723 Node baseNode(Inc ArcIt) const {723 Node baseNode(IncEdgeIt) const { 724 724 return INVALID; 725 725 } … … 728 728 /// 729 729 /// Returns the running node of the iterator 730 Node runningNode(Inc ArcIt) const {730 Node runningNode(IncEdgeIt) const { 731 731 return INVALID; 732 732 } -
lemon/concepts/graph_components.h
r57 r78 829 829 /// This iterator goes trough the incident arcs of a certain 830 830 /// node of a graph. 831 typedef GraphIncIt<Graph, Edge, Node, 'u'> Inc ArcIt;831 typedef GraphIncIt<Graph, Edge, Node, 'u'> IncEdgeIt; 832 832 /// \brief The base node of the iterator. 833 833 /// 834 834 /// Gives back the base node of the iterator. 835 Node baseNode(const Inc ArcIt&) const { return INVALID; }835 Node baseNode(const IncEdgeIt&) const { return INVALID; } 836 836 837 837 /// \brief The running node of the iterator. 838 838 /// 839 839 /// Gives back the running node of the iterator. 840 Node runningNode(const Inc ArcIt&) const { return INVALID; }840 Node runningNode(const IncEdgeIt&) const { return INVALID; } 841 841 842 842 /// @} … … 866 866 typename _Graph::EdgeIt >(); 867 867 checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 868 typename _Graph::Node, 'u'>, typename _Graph::Inc ArcIt>();868 typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>(); 869 869 870 870 typename _Graph::Node n; 871 typename _Graph::Inc ArcIt ueit(INVALID);871 typename _Graph::IncEdgeIt ueit(INVALID); 872 872 n = graph.baseNode(ueit); 873 873 n = graph.runningNode(ueit); -
lemon/concepts/maps.h
r74 r94 30 30 31 31 namespace concepts { 32 32 33 33 /// \addtogroup concept 34 34 /// @{ … … 43 43 public: 44 44 /// The key type of the map. 45 typedef K Key; 46 /// The value type of the map. (The type of objects associated with the keys). 47 typedef T Value; 48 49 /// Returns the value associated with a key. 50 51 /// Returns the value associated with a key. 52 /// \bug Value shouldn't need to be default constructible. 53 /// 54 Value operator[](const Key &) const {return Value();} 45 typedef K Key; 46 /// The value type of the map. (The type of objects associated with the keys). 47 typedef T Value; 48 49 /// Returns the value associated with the given key. 50 Value operator[](const Key &) const { 51 return *static_cast<Value *>(0); 52 } 55 53 56 54 template<typename _ReadMap> … … 59 57 Value val = m[key]; 60 58 val = m[key]; 61 typename _ReadMap::Value own_val = m[own_key]; 62 own_val = m[own_key]; 63 64 ignore_unused_variable_warning(val); 65 ignore_unused_variable_warning(own_val); 66 ignore_unused_variable_warning(key); 67 } 68 Key& key; 69 typename _ReadMap::Key& own_key; 70 _ReadMap& m; 71 }; 72 73 }; 74 75 76 /// Writable map concept 77 78 /// Writable map concept. 79 /// 80 template<typename K, typename T> 81 class WriteMap 82 { 83 public: 84 /// The key type of the map. 85 typedef K Key; 86 /// The value type of the map. (The type of objects associated with the keys). 87 typedef T Value; 88 89 /// Sets the value associated with a key. 90 void set(const Key &,const Value &) {} 91 92 ///Default constructor 93 WriteMap() {} 94 95 template <typename _WriteMap> 96 struct Constraints { 97 void constraints() { 98 // No constraints for constructor. 99 m.set(key, val); 100 m.set(own_key, own_val); 59 typename _ReadMap::Value own_val = m[own_key]; 60 own_val = m[own_key]; 61 101 62 ignore_unused_variable_warning(key); 102 63 ignore_unused_variable_warning(val); … … 104 65 ignore_unused_variable_warning(own_val); 105 66 } 106 107 Value& val; 108 typename _WriteMap::Value own_val; 109 Key& key; 110 typename _WriteMap::Key& own_key; 67 const Key& key; 68 const typename _ReadMap::Key& own_key; 69 const _ReadMap& m; 70 }; 71 72 }; 73 74 75 /// Writable map concept 76 77 /// Writable map concept. 78 /// 79 template<typename K, typename T> 80 class WriteMap 81 { 82 public: 83 /// The key type of the map. 84 typedef K Key; 85 /// The value type of the map. (The type of objects associated with the keys). 86 typedef T Value; 87 88 /// Sets the value associated with the given key. 89 void set(const Key &, const Value &) {} 90 91 /// Default constructor. 92 WriteMap() {} 93 94 template <typename _WriteMap> 95 struct Constraints { 96 void constraints() { 97 m.set(key, val); 98 m.set(own_key, own_val); 99 100 ignore_unused_variable_warning(key); 101 ignore_unused_variable_warning(val); 102 ignore_unused_variable_warning(own_key); 103 ignore_unused_variable_warning(own_val); 104 } 105 const Key& key; 106 const Value& val; 107 const typename _WriteMap::Key& own_key; 108 const typename _WriteMap::Value own_val; 111 109 _WriteMap& m; 112 113 110 }; 114 111 }; 115 112 116 113 /// Read/writable map concept 117 114 118 115 /// Read/writable map concept. 119 116 /// … … 124 121 public: 125 122 /// The key type of the map. 126 typedef K Key; 127 /// The value type of the map. (The type of objects associated with the keys). 128 typedef T Value; 129 130 /// Returns the value associated with a key. 131 Value operator[](const Key &) const {return Value();} 132 /// Sets the value associated with a key. 133 void set(const Key & ,const Value &) {} 123 typedef K Key; 124 /// The value type of the map. (The type of objects associated with the keys). 125 typedef T Value; 126 127 /// Returns the value associated with the given key. 128 Value operator[](const Key &) const { 129 return *static_cast<Value *>(0); 130 } 131 132 /// Sets the value associated with the given key. 133 void set(const Key &, const Value &) {} 134 134 135 135 template<typename _ReadWriteMap> … … 141 141 }; 142 142 }; 143 144 143 144 145 145 /// Dereferable map concept 146 146 147 147 /// Dereferable map concept. 148 148 /// 149 /// \todo Rethink this concept.150 149 template<typename K, typename T, typename R, typename CR> 151 150 class ReferenceMap : public ReadWriteMap<K,T> … … 155 154 typedef True ReferenceMapTag; 156 155 /// The key type of the map. 157 typedef K Key; 156 typedef K Key; 158 157 /// The value type of the map. (The type of objects associated with the keys). 159 158 typedef T Value; … … 163 162 typedef CR ConstReference; 164 163 165 protected: 166 Value tmp; 167 public: 168 169 ///Returns a reference to the value associated with a key. 170 Reference operator[](const Key &) { return tmp; } 171 ///Returns a const reference to the value associated with a key. 172 ConstReference operator[](const Key &) const { return tmp; } 173 /// Sets the value associated with a key. 164 public: 165 166 /// Returns a reference to the value associated with the given key. 167 Reference operator[](const Key &) { 168 return *static_cast<Value *>(0); 169 } 170 171 /// Returns a const reference to the value associated with the given key. 172 ConstReference operator[](const Key &) const { 173 return *static_cast<Value *>(0); 174 } 175 176 /// Sets the value associated with the given key. 174 177 void set(const Key &k,const Value &t) { operator[](k)=t; } 175 178 … … 178 181 void constraints() { 179 182 checkConcept<ReadWriteMap<K, T>, _ReferenceMap >(); 183 ref = m[key]; 180 184 m[key] = val; 181 val = m[key];182 185 m[key] = ref; 183 ref = m[key]; 186 m[key] = cref; 187 own_ref = m[own_key]; 184 188 m[own_key] = own_val; 185 own_val = m[own_key];186 189 m[own_key] = own_ref; 187 own_ref = m[own_key]; 188 } 189 190 typename _ReferenceMap::Key& own_key; 190 m[own_key] = own_cref; 191 m[key] = m[own_key]; 192 m[own_key] = m[key]; 193 } 194 const Key& key; 195 Value& val; 196 Reference ref; 197 ConstReference cref; 198 const typename _ReferenceMap::Key& own_key; 191 199 typename _ReferenceMap::Value& own_val; 192 200 typename _ReferenceMap::Reference own_ref; 193 Key& key; 194 Value& val; 195 Reference ref; 201 typename _ReferenceMap::ConstReference own_cref; 196 202 _ReferenceMap& m; 197 203 }; -
lemon/maps.h
r54 r104 25 25 26 26 #include <lemon/bits/utility.h> 27 //#include <lemon/bits/traits.h>27 #include <lemon/bits/traits.h> 28 28 29 29 ///\file 30 30 ///\ingroup maps 31 31 ///\brief Miscellaneous property maps 32 /// 32 33 33 #include <map> 34 34 … … 40 40 /// Base class of maps. 41 41 42 /// Base class of maps. 43 /// It provides the necessary <tt>typedef</tt>s required by the map concept.44 template<typename K, typename T>42 /// Base class of maps. It provides the necessary type definitions 43 /// required by the map %concepts. 44 template<typename K, typename V> 45 45 class MapBase { 46 46 public: 47 /// The key type of the map.47 /// \biref The key type of the map. 48 48 typedef K Key; 49 /// The value type of the map. (The type of objects associated with the keys). 50 typedef T Value; 51 }; 49 /// \brief The value type of the map. 50 /// (The type of objects associated with the keys). 51 typedef V Value; 52 }; 53 52 54 53 55 /// Null map. (a.k.a. DoNothingMap) 54 56 55 57 /// This map can be used if you have to provide a map only for 56 /// its type definitions, or if you have to provide a writable map, 57 /// but data written to it is not required (i.e. it will be sent to 58 /// its type definitions, or if you have to provide a writable map, 59 /// but data written to it is not required (i.e. it will be sent to 58 60 /// <tt>/dev/null</tt>). 59 template<typename K, typename T> 60 class NullMap : public MapBase<K, T> { 61 public: 62 typedef MapBase<K, T> Parent; 63 typedef typename Parent::Key Key; 64 typedef typename Parent::Value Value; 65 61 /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 62 /// 63 /// \sa ConstMap 64 template<typename K, typename V> 65 class NullMap : public MapBase<K, V> { 66 public: 67 typedef MapBase<K, V> Parent; 68 typedef typename Parent::Key Key; 69 typedef typename Parent::Value Value; 70 66 71 /// Gives back a default constructed element. 67 T operator[](const K&) const { return T(); }72 Value operator[](const Key&) const { return Value(); } 68 73 /// Absorbs the value. 69 void set(const K &, const T&) {}70 }; 71 72 /// Returns a \cNullMap class73 74 /// This function just returns a \cNullMap class.75 /// \relates NullMap76 template <typename K, typename V> 74 void set(const Key&, const Value&) {} 75 }; 76 77 /// Returns a \ref NullMap class 78 79 /// This function just returns a \ref NullMap class. 80 /// \relates NullMap 81 template <typename K, typename V> 77 82 NullMap<K, V> nullMap() { 78 83 return NullMap<K, V>(); … … 82 87 /// Constant map. 83 88 84 /// This is a \ref concepts::ReadMap "readable" map which assigns a 85 /// specified value to each key. 86 /// In other aspects it is equivalent to \c NullMap. 87 template<typename K, typename T> 88 class ConstMap : public MapBase<K, T> { 89 /// This \ref concepts::ReadMap "readable map" assigns a specified 90 /// value to each key. 91 /// 92 /// In other aspects it is equivalent to \ref NullMap. 93 /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap" 94 /// concept, but it absorbs the data written to it. 95 /// 96 /// The simplest way of using this map is through the constMap() 97 /// function. 98 /// 99 /// \sa NullMap 100 /// \sa IdentityMap 101 template<typename K, typename V> 102 class ConstMap : public MapBase<K, V> { 89 103 private: 90 T v; 91 public: 92 93 typedef MapBase<K, T> Parent; 104 V _value; 105 public: 106 typedef MapBase<K, V> Parent; 94 107 typedef typename Parent::Key Key; 95 108 typedef typename Parent::Value Value; … … 98 111 99 112 /// Default constructor. 100 /// The value of the map will be uninitialized. 101 /// (More exactly it will be default constructed.) 113 /// The value of the map will be default constructed. 102 114 ConstMap() {} 103 115 104 116 /// Constructor with specified initial value 105 117 106 118 /// Constructor with specified initial value. 107 /// \param _v is the initial value of the map. 108 ConstMap(const T &_v) : v(_v) {} 109 110 ///\e 111 T operator[](const K&) const { return v; } 112 113 ///\e 114 void setAll(const T &t) { 115 v = t; 116 } 117 118 template<typename T1> 119 ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {} 120 }; 121 122 ///Returns a \c ConstMap class 123 124 ///This function just returns a \c ConstMap class. 125 ///\relates ConstMap 126 template<typename K, typename V> 119 /// \param v is the initial value of the map. 120 ConstMap(const Value &v) : _value(v) {} 121 122 /// Gives back the specified value. 123 Value operator[](const Key&) const { return _value; } 124 125 /// Absorbs the value. 126 void set(const Key&, const Value&) {} 127 128 /// Sets the value that is assigned to each key. 129 void setAll(const Value &v) { 130 _value = v; 131 } 132 133 template<typename V1> 134 ConstMap(const ConstMap<K, V1> &, const Value &v) : _value(v) {} 135 }; 136 137 /// Returns a \ref ConstMap class 138 139 /// This function just returns a \ref ConstMap class. 140 /// \relates ConstMap 141 template<typename K, typename V> 127 142 inline ConstMap<K, V> constMap(const V &v) { 128 143 return ConstMap<K, V>(v); … … 131 146 132 147 template<typename T, T v> 133 struct Const { 148 struct Const {}; 134 149 135 150 /// Constant map with inlined constant value. 136 151 137 /// This is a \ref concepts::ReadMap "readable" map which assigns a 138 /// specified value to each key. 139 /// In other aspects it is equivalent to \c NullMap. 152 /// This \ref concepts::ReadMap "readable map" assigns a specified 153 /// value to each key. 154 /// 155 /// In other aspects it is equivalent to \ref NullMap. 156 /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap" 157 /// concept, but it absorbs the data written to it. 158 /// 159 /// The simplest way of using this map is through the constMap() 160 /// function. 161 /// 162 /// \sa NullMap 163 /// \sa IdentityMap 140 164 template<typename K, typename V, V v> 141 165 class ConstMap<K, Const<V, v> > : public MapBase<K, V> { … … 145 169 typedef typename Parent::Value Value; 146 170 147 ConstMap() { } 148 ///\e 149 V operator[](const K&) const { return v; } 150 ///\e 151 void set(const K&, const V&) { } 152 }; 153 154 ///Returns a \c ConstMap class with inlined value 155 156 ///This function just returns a \c ConstMap class with inlined value. 157 ///\relates ConstMap 158 template<typename K, typename V, V v> 171 /// Constructor. 172 ConstMap() {} 173 174 /// Gives back the specified value. 175 Value operator[](const Key&) const { return v; } 176 177 /// Absorbs the value. 178 void set(const Key&, const Value&) {} 179 }; 180 181 /// Returns a \ref ConstMap class with inlined constant value 182 183 /// This function just returns a \ref ConstMap class with inlined 184 /// constant value. 185 /// \relates ConstMap 186 template<typename K, typename V, V v> 159 187 inline ConstMap<K, Const<V, v> > constMap() { 160 188 return ConstMap<K, Const<V, v> >(); 161 189 } 162 190 163 ///Map based on \c std::map 164 165 ///This is essentially a wrapper for \c std::map with addition that 166 ///you can specify a default value different from \c Value(). 167 ///It meets the \ref concepts::ReferenceMap "ReferenceMap" concept. 168 template <typename K, typename T, typename Compare = std::less<K> > 169 class StdMap : public MapBase<K, T> { 170 template <typename K1, typename T1, typename C1> 171 friend class StdMap; 172 public: 173 174 typedef MapBase<K, T> Parent; 175 ///Key type 176 typedef typename Parent::Key Key; 177 ///Value type 178 typedef typename Parent::Value Value; 179 ///Reference Type 180 typedef T& Reference; 181 ///Const reference type 182 typedef const T& ConstReference; 191 192 /// Identity map. 193 194 /// This \ref concepts::ReadMap "read-only map" gives back the given 195 /// key as value without any modification. 196 /// 197 /// \sa ConstMap 198 template <typename T> 199 class IdentityMap : public MapBase<T, T> { 200 public: 201 typedef MapBase<T, T> Parent; 202 typedef typename Parent::Key Key; 203 typedef typename Parent::Value Value; 204 205 /// Gives back the given value without any modification. 206 Value operator[](const Key &k) const { 207 return k; 208 } 209 }; 210 211 /// Returns an \ref IdentityMap class 212 213 /// This function just returns an \ref IdentityMap class. 214 /// \relates IdentityMap 215 template<typename T> 216 inline IdentityMap<T> identityMap() { 217 return IdentityMap<T>(); 218 } 219 220 221 /// \brief Map for storing values for integer keys from the range 222 /// <tt>[0..size-1]</tt>. 223 /// 224 /// This map is essentially a wrapper for \c std::vector. It assigns 225 /// values to integer keys from the range <tt>[0..size-1]</tt>. 226 /// It can be used with some data structures, for example 227 /// \ref UnionFind, \ref BinHeap, when the used items are small 228 /// integers. This map conforms the \ref concepts::ReferenceMap 229 /// "ReferenceMap" concept. 230 /// 231 /// The simplest way of using this map is through the rangeMap() 232 /// function. 233 template <typename V> 234 class RangeMap : public MapBase<int, V> { 235 template <typename V1> 236 friend class RangeMap; 237 private: 238 239 typedef std::vector<V> Vector; 240 Vector _vector; 241 242 public: 243 244 typedef MapBase<int, V> Parent; 245 /// Key type 246 typedef typename Parent::Key Key; 247 /// Value type 248 typedef typename Parent::Value Value; 249 /// Reference type 250 typedef typename Vector::reference Reference; 251 /// Const reference type 252 typedef typename Vector::const_reference ConstReference; 183 253 184 254 typedef True ReferenceMapTag; 185 255 256 public: 257 258 /// Constructor with specified default value. 259 RangeMap(int size = 0, const Value &value = Value()) 260 : _vector(size, value) {} 261 262 /// Constructs the map from an appropriate \c std::vector. 263 template <typename V1> 264 RangeMap(const std::vector<V1>& vector) 265 : _vector(vector.begin(), vector.end()) {} 266 267 /// Constructs the map from another \ref RangeMap. 268 template <typename V1> 269 RangeMap(const RangeMap<V1> &c) 270 : _vector(c._vector.begin(), c._vector.end()) {} 271 272 /// Returns the size of the map. 273 int size() { 274 return _vector.size(); 275 } 276 277 /// Resizes the map. 278 279 /// Resizes the underlying \c std::vector container, so changes the 280 /// keyset of the map. 281 /// \param size The new size of the map. The new keyset will be the 282 /// range <tt>[0..size-1]</tt>. 283 /// \param value The default value to assign to the new keys. 284 void resize(int size, const Value &value = Value()) { 285 _vector.resize(size, value); 286 } 287 186 288 private: 187 188 typedef std::map<K, T, Compare> Map; 289 290 RangeMap& operator=(const RangeMap&); 291 292 public: 293 294 ///\e 295 Reference operator[](const Key &k) { 296 return _vector[k]; 297 } 298 299 ///\e 300 ConstReference operator[](const Key &k) const { 301 return _vector[k]; 302 } 303 304 ///\e 305 void set(const Key &k, const Value &v) { 306 _vector[k] = v; 307 } 308 }; 309 310 /// Returns a \ref RangeMap class 311 312 /// This function just returns a \ref RangeMap class. 313 /// \relates RangeMap 314 template<typename V> 315 inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) { 316 return RangeMap<V>(size, value); 317 } 318 319 /// \brief Returns a \ref RangeMap class created from an appropriate 320 /// \c std::vector 321 322 /// This function just returns a \ref RangeMap class created from an 323 /// appropriate \c std::vector. 324 /// \relates RangeMap 325 template<typename V> 326 inline RangeMap<V> rangeMap(const std::vector<V> &vector) { 327 return RangeMap<V>(vector); 328 } 329 330 331 /// Map type based on \c std::map 332 333 /// This map is essentially a wrapper for \c std::map with addition 334 /// that you can specify a default value for the keys that are not 335 /// stored actually. This value can be different from the default 336 /// contructed value (i.e. \c %Value()). 337 /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap" 338 /// concept. 339 /// 340 /// This map is useful if a default value should be assigned to most of 341 /// the keys and different values should be assigned only to a few 342 /// keys (i.e. the map is "sparse"). 343 /// The name of this type also refers to this important usage. 344 /// 345 /// Apart form that this map can be used in many other cases since it 346 /// is based on \c std::map, which is a general associative container. 347 /// However keep in mind that it is usually not as efficient as other 348 /// maps. 349 /// 350 /// The simplest way of using this map is through the sparseMap() 351 /// function. 352 template <typename K, typename V, typename Compare = std::less<K> > 353 class SparseMap : public MapBase<K, V> { 354 template <typename K1, typename V1, typename C1> 355 friend class SparseMap; 356 public: 357 358 typedef MapBase<K, V> Parent; 359 /// Key type 360 typedef typename Parent::Key Key; 361 /// Value type 362 typedef typename Parent::Value Value; 363 /// Reference type 364 typedef Value& Reference; 365 /// Const reference type 366 typedef const Value& ConstReference; 367 368 typedef True ReferenceMapTag; 369 370 private: 371 372 typedef std::map<K, V, Compare> Map; 373 Map _map; 189 374 Value _value; 190 Map _map; 191 192 public: 193 194 /// Constructor with specified default value 195 StdMap(const T& value = T()) : _value(value) {} 196 /// \brief Constructs the map from an appropriate \c std::map, and 375 376 public: 377 378 /// \brief Constructor with specified default value. 379 SparseMap(const Value &value = Value()) : _value(value) {} 380 /// \brief Constructs the map from an appropriate \c std::map, and 197 381 /// explicitly specifies a default value. 198 template <typename T1, typename Comp1> 199 StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T()) 382 template <typename V1, typename Comp1> 383 SparseMap(const std::map<Key, V1, Comp1> &map, 384 const Value &value = Value()) 200 385 : _map(map.begin(), map.end()), _value(value) {} 201 202 /// \brief Constructs a map from an other \ref StdMap.203 template<typename T1, typename Comp1>204 S tdMap(const StdMap<Key, T1, Comp1> &c)386 387 /// \brief Constructs the map from another \ref SparseMap. 388 template<typename V1, typename Comp1> 389 SparseMap(const SparseMap<Key, V1, Comp1> &c) 205 390 : _map(c._map.begin(), c._map.end()), _value(c._value) {} 206 391 207 392 private: 208 393 209 S tdMap& operator=(const StdMap&);394 SparseMap& operator=(const SparseMap&); 210 395 211 396 public: … … 220 405 } 221 406 222 /// \e407 ///\e 223 408 ConstReference operator[](const Key &k) const { 224 409 typename Map::const_iterator it = _map.find(k); … … 229 414 } 230 415 231 /// \e232 void set(const Key &k, const T &t) {416 ///\e 417 void set(const Key &k, const Value &v) { 233 418 typename Map::iterator it = _map.lower_bound(k); 234 419 if (it != _map.end() && !_map.key_comp()(k, it->first)) 235 it->second = t;420 it->second = v; 236 421 else 237 _map.insert(it, std::make_pair(k, t));422 _map.insert(it, std::make_pair(k, v)); 238 423 } 239 424 240 /// 241 void setAll(const T &t) {242 _value = t;425 ///\e 426 void setAll(const Value &v) { 427 _value = v; 243 428 _map.clear(); 244 }245 246 };247 248 ///Returns a \c StdMap class249 250 ///This function just returns a \c StdMap class with specified251 ///default value.252 ///\relates StdMap253 template<typename K, typename V, typename Compare>254 inline StdMap<K, V, Compare> stdMap(const V& value = V()) {255 return StdMap<K, V, Compare>(value);256 }257 258 ///Returns a \c StdMap class259 260 ///This function just returns a \c StdMap class with specified261 ///default value.262 ///\relates StdMap263 template<typename K, typename V>264 inline StdMap<K, V, std::less<K> > stdMap(const V& value = V()) {265 return StdMap<K, V, std::less<K> >(value);266 }267 268 ///Returns a \c StdMap class created from an appropriate std::map269 270 ///This function just returns a \c StdMap class created from an271 ///appropriate std::map.272 ///\relates StdMap273 template<typename K, typename V, typename Compare>274 inline StdMap<K, V, Compare> stdMap( const std::map<K, V, Compare> &map,275 const V& value = V() ) {276 return StdMap<K, V, Compare>(map, value);277 }278 279 ///Returns a \c StdMap class created from an appropriate std::map280 281 ///This function just returns a \c StdMap class created from an282 ///appropriate std::map.283 ///\relates StdMap284 template<typename K, typename V>285 inline StdMap<K, V, std::less<K> > stdMap( const std::map<K, V, std::less<K> > &map,286 const V& value = V() ) {287 return StdMap<K, V, std::less<K> >(map, value);288 }289 290 /// \brief Map for storing values for keys from the range <tt>[0..size-1]</tt>291 ///292 /// This map has the <tt>[0..size-1]</tt> keyset and the values293 /// are stored in a \c std::vector<T> container. It can be used with294 /// some data structures, for example \c UnionFind, \c BinHeap, when295 /// the used items are small integer numbers.296 /// This map meets the \ref concepts::ReferenceMap "ReferenceMap" concept.297 ///298 /// \todo Revise its name299 template <typename T>300 class IntegerMap : public MapBase<int, T> {301 302 template <typename T1>303 friend class IntegerMap;304 305 public:306 307 typedef MapBase<int, T> Parent;308 ///\e309 typedef typename Parent::Key Key;310 ///\e311 typedef typename Parent::Value Value;312 ///\e313 typedef T& Reference;314 ///\e315 typedef const T& ConstReference;316 317 typedef True ReferenceMapTag;318 319 private:320 321 typedef std::vector<T> Vector;322 Vector _vector;323 324 public:325 326 /// Constructor with specified default value327 IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}328 329 /// \brief Constructs the map from an appropriate \c std::vector.330 template <typename T1>331 IntegerMap(const std::vector<T1>& vector)332 : _vector(vector.begin(), vector.end()) {}333 334 /// \brief Constructs a map from an other \ref IntegerMap.335 template <typename T1>336 IntegerMap(const IntegerMap<T1> &c)337 : _vector(c._vector.begin(), c._vector.end()) {}338 339 /// \brief Resize the container340 void resize(int size, const T& value = T()) {341 _vector.resize(size, value);342 429 } 343 344 private: 345 346 IntegerMap& operator=(const IntegerMap&); 347 348 public: 349 350 ///\e 351 Reference operator[](Key k) { 352 return _vector[k]; 353 } 354 355 /// \e 356 ConstReference operator[](Key k) const { 357 return _vector[k]; 358 } 359 360 /// \e 361 void set(const Key &k, const T& t) { 362 _vector[k] = t; 363 } 364 365 }; 366 367 ///Returns an \c IntegerMap class 368 369 ///This function just returns an \c IntegerMap class. 370 ///\relates IntegerMap 371 template<typename T> 372 inline IntegerMap<T> integerMap(int size = 0, const T& value = T()) { 373 return IntegerMap<T>(size, value); 430 }; 431 432 /// Returns a \ref SparseMap class 433 434 /// This function just returns a \ref SparseMap class with specified 435 /// default value. 436 /// \relates SparseMap 437 template<typename K, typename V, typename Compare> 438 inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) { 439 return SparseMap<K, V, Compare>(value); 440 } 441 442 template<typename K, typename V> 443 inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) { 444 return SparseMap<K, V, std::less<K> >(value); 445 } 446 447 /// \brief Returns a \ref SparseMap class created from an appropriate 448 /// \c std::map 449 450 /// This function just returns a \ref SparseMap class created from an 451 /// appropriate \c std::map. 452 /// \relates SparseMap 453 template<typename K, typename V, typename Compare> 454 inline SparseMap<K, V, Compare> 455 sparseMap(const std::map<K, V, Compare> &map, const V& value = V()) 456 { 457 return SparseMap<K, V, Compare>(map, value); 374 458 } 375 459 … … 379 463 /// @{ 380 464 381 /// \brief Identity map. 382 /// 383 /// This map gives back the given key as value without any 384 /// modification. 385 template <typename T> 386 class IdentityMap : public MapBase<T, T> { 387 public: 388 typedef MapBase<T, T> Parent; 389 typedef typename Parent::Key Key; 390 typedef typename Parent::Value Value; 391 392 /// \e 393 const T& operator[](const T& t) const { 394 return t; 395 } 396 }; 397 398 ///Returns an \c IdentityMap class 399 400 ///This function just returns an \c IdentityMap class. 401 ///\relates IdentityMap 402 template<typename T> 403 inline IdentityMap<T> identityMap() { 404 return IdentityMap<T>(); 405 } 406 407 408 ///\brief Convert the \c Value of a map to another type using 409 ///the default conversion. 410 /// 411 ///This \ref concepts::ReadMap "read only map" 412 ///converts the \c Value of a map to type \c T. 413 ///Its \c Key is inherited from \c M. 414 template <typename M, typename T> 415 class ConvertMap : public MapBase<typename M::Key, T> { 416 const M& m; 417 public: 418 typedef MapBase<typename M::Key, T> Parent; 419 typedef typename Parent::Key Key; 420 typedef typename Parent::Value Value; 421 422 ///Constructor 423 424 ///Constructor. 425 ///\param _m is the underlying map. 426 ConvertMap(const M &_m) : m(_m) {}; 427 428 ///\e 429 Value operator[](const Key& k) const {return m[k];} 430 }; 431 432 ///Returns a \c ConvertMap class 433 434 ///This function just returns a \c ConvertMap class. 435 ///\relates ConvertMap 436 template<typename T, typename M> 437 inline ConvertMap<M, T> convertMap(const M &m) { 438 return ConvertMap<M, T>(m); 439 } 440 441 ///Simple wrapping of a map 442 443 ///This \ref concepts::ReadMap "read only map" returns the simple 444 ///wrapping of the given map. Sometimes the reference maps cannot be 445 ///combined with simple read maps. This map adaptor wraps the given 446 ///map to simple read map. 447 /// 448 ///\sa SimpleWriteMap 449 /// 450 /// \todo Revise the misleading name 451 template<typename M> 452 class SimpleMap : public MapBase<typename M::Key, typename M::Value> { 453 const M& m; 454 465 /// Composition of two maps 466 467 /// This \ref concepts::ReadMap "read-only map" returns the 468 /// composition of two given maps. That is to say, if \c m1 is of 469 /// type \c M1 and \c m2 is of \c M2, then for 470 /// \code 471 /// ComposeMap<M1, M2> cm(m1,m2); 472 /// \endcode 473 /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>. 474 /// 475 /// The \c Key type of the map is inherited from \c M2 and the 476 /// \c Value type is from \c M1. 477 /// \c M2::Value must be convertible to \c M1::Key. 478 /// 479 /// The simplest way of using this map is through the composeMap() 480 /// function. 481 /// 482 /// \sa CombineMap 483 /// 484 /// \todo Check the requirements. 485 template <typename M1, typename M2> 486 class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> { 487 const M1 &_m1; 488 const M2 &_m2; 489 public: 490 typedef MapBase<typename M2::Key, typename M1::Value> Parent; 491 typedef typename Parent::Key Key; 492 typedef typename Parent::Value Value; 493 494 /// Constructor 495 ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 496 497 /// \e 498 typename MapTraits<M1>::ConstReturnValue 499 operator[](const Key &k) const { return _m1[_m2[k]]; } 500 }; 501 502 /// Returns a \ref ComposeMap class 503 504 /// This function just returns a \ref ComposeMap class. 505 /// 506 /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is 507 /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt> 508 /// will be equal to <tt>m1[m2[x]]</tt>. 509 /// 510 /// \relates ComposeMap 511 template <typename M1, typename M2> 512 inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) { 513 return ComposeMap<M1, M2>(m1, m2); 514 } 515 516 517 /// Combination of two maps using an STL (binary) functor. 518 519 /// This \ref concepts::ReadMap "read-only map" takes two maps and a 520 /// binary functor and returns the combination of the two given maps 521 /// using the functor. 522 /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2 523 /// and \c f is of \c F, then for 524 /// \code 525 /// CombineMap<M1,M2,F,V> cm(m1,m2,f); 526 /// \endcode 527 /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>. 528 /// 529 /// The \c Key type of the map is inherited from \c M1 (\c M1::Key 530 /// must be convertible to \c M2::Key) and the \c Value type is \c V. 531 /// \c M2::Value and \c M1::Value must be convertible to the 532 /// corresponding input parameter of \c F and the return type of \c F 533 /// must be convertible to \c V. 534 /// 535 /// The simplest way of using this map is through the combineMap() 536 /// function. 537 /// 538 /// \sa ComposeMap 539 /// 540 /// \todo Check the requirements. 541 template<typename M1, typename M2, typename F, 542 typename V = typename F::result_type> 543 class CombineMap : public MapBase<typename M1::Key, V> { 544 const M1 &_m1; 545 const M2 &_m2; 546 F _f; 547 public: 548 typedef MapBase<typename M1::Key, V> Parent; 549 typedef typename Parent::Key Key; 550 typedef typename Parent::Value Value; 551 552 /// Constructor 553 CombineMap(const M1 &m1, const M2 &m2, const F &f = F()) 554 : _m1(m1), _m2(m2), _f(f) {} 555 /// \e 556 Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); } 557 }; 558 559 /// Returns a \ref CombineMap class 560 561 /// This function just returns a \ref CombineMap class. 562 /// 563 /// For example, if \c m1 and \c m2 are both maps with \c double 564 /// values, then 565 /// \code 566 /// combineMap(m1,m2,std::plus<double>()) 567 /// \endcode 568 /// is equivalent to 569 /// \code 570 /// addMap(m1,m2) 571 /// \endcode 572 /// 573 /// This function is specialized for adaptable binary function 574 /// classes and C++ functions. 575 /// 576 /// \relates CombineMap 577 template<typename M1, typename M2, typename F, typename V> 578 inline CombineMap<M1, M2, F, V> 579 combineMap(const M1 &m1, const M2 &m2, const F &f) { 580 return CombineMap<M1, M2, F, V>(m1,m2,f); 581 } 582 583 template<typename M1, typename M2, typename F> 584 inline CombineMap<M1, M2, F, typename F::result_type> 585 combineMap(const M1 &m1, const M2 &m2, const F &f) { 586 return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f); 587 } 588 589 template<typename M1, typename M2, typename K1, typename K2, typename V> 590 inline CombineMap<M1, M2, V (*)(K1, K2), V> 591 combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) { 592 return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f); 593 } 594 595 596 /// Converts an STL style (unary) functor to a map 597 598 /// This \ref concepts::ReadMap "read-only map" returns the value 599 /// of a given functor. Actually, it just wraps the functor and 600 /// provides the \c Key and \c Value typedefs. 601 /// 602 /// Template parameters \c K and \c V will become its \c Key and 603 /// \c Value. In most cases they have to be given explicitly because 604 /// a functor typically does not provide \c argument_type and 605 /// \c result_type typedefs. 606 /// Parameter \c F is the type of the used functor. 607 /// 608 /// The simplest way of using this map is through the functorToMap() 609 /// function. 610 /// 611 /// \sa MapToFunctor 612 template<typename F, 613 typename K = typename F::argument_type, 614 typename V = typename F::result_type> 615 class FunctorToMap : public MapBase<K, V> { 616 const F &_f; 617 public: 618 typedef MapBase<K, V> Parent; 619 typedef typename Parent::Key Key; 620 typedef typename Parent::Value Value; 621 622 /// Constructor 623 FunctorToMap(const F &f = F()) : _f(f) {} 624 /// \e 625 Value operator[](const Key &k) const { return _f(k); } 626 }; 627 628 /// Returns a \ref FunctorToMap class 629 630 /// This function just returns a \ref FunctorToMap class. 631 /// 632 /// This function is specialized for adaptable binary function 633 /// classes and C++ functions. 634 /// 635 /// \relates FunctorToMap 636 template<typename K, typename V, typename F> 637 inline FunctorToMap<F, K, V> functorToMap(const F &f) { 638 return FunctorToMap<F, K, V>(f); 639 } 640 641 template <typename F> 642 inline FunctorToMap<F, typename F::argument_type, typename F::result_type> 643 functorToMap(const F &f) 644 { 645 return FunctorToMap<F, typename F::argument_type, 646 typename F::result_type>(f); 647 } 648 649 template <typename K, typename V> 650 inline FunctorToMap<V (*)(K), K, V> functorToMap(V (*f)(K)) { 651 return FunctorToMap<V (*)(K), K, V>(f); 652 } 653 654 655 /// Converts a map to an STL style (unary) functor 656 657 /// This class converts a map to an STL style (unary) functor. 658 /// That is it provides an <tt>operator()</tt> to read its values. 659 /// 660 /// For the sake of convenience it also works as a usual 661 /// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt> 662 /// and the \c Key and \c Value typedefs also exist. 663 /// 664 /// The simplest way of using this map is through the mapToFunctor() 665 /// function. 666 /// 667 ///\sa FunctorToMap 668 template <typename M> 669 class MapToFunctor : public MapBase<typename M::Key, typename M::Value> { 670 const M &_m; 455 671 public: 456 672 typedef MapBase<typename M::Key, typename M::Value> Parent; … … 458 674 typedef typename Parent::Value Value; 459 675 460 ///Constructor 461 SimpleMap(const M &_m) : m(_m) {}; 462 ///\e 463 Value operator[](Key k) const {return m[k];} 464 }; 465 466 ///Returns a \c SimpleMap class 467 468 ///This function just returns a \c SimpleMap class. 469 ///\relates SimpleMap 676 typedef typename Parent::Key argument_type; 677 typedef typename Parent::Value result_type; 678 679 /// Constructor 680 MapToFunctor(const M &m) : _m(m) {} 681 /// \e 682 Value operator()(const Key &k) const { return _m[k]; } 683 /// \e 684 Value operator[](const Key &k) const { return _m[k]; } 685 }; 686 687 /// Returns a \ref MapToFunctor class 688 689 /// This function just returns a \ref MapToFunctor class. 690 /// \relates MapToFunctor 470 691 template<typename M> 471 inline SimpleMap<M> simpleMap(const M &m) { 472 return SimpleMap<M>(m); 473 } 474 475 ///Simple writable wrapping of a map 476 477 ///This \ref concepts::ReadWriteMap "read-write map" returns the simple 478 ///wrapping of the given map. Sometimes the reference maps cannot be 479 ///combined with simple read-write maps. This map adaptor wraps the 480 ///given map to simple read-write map. 481 /// 482 ///\sa SimpleMap 483 /// 484 /// \todo Revise the misleading name 485 template<typename M> 486 class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> { 487 M& m; 488 489 public: 490 typedef MapBase<typename M::Key, typename M::Value> Parent; 491 typedef typename Parent::Key Key; 492 typedef typename Parent::Value Value; 493 494 ///Constructor 495 SimpleWriteMap(M &_m) : m(_m) {}; 496 ///\e 497 Value operator[](Key k) const {return m[k];} 498 ///\e 499 void set(Key k, const Value& c) { m.set(k, c); } 500 }; 501 502 ///Returns a \c SimpleWriteMap class 503 504 ///This function just returns a \c SimpleWriteMap class. 505 ///\relates SimpleWriteMap 506 template<typename M> 507 inline SimpleWriteMap<M> simpleWriteMap(M &m) { 508 return SimpleWriteMap<M>(m); 509 } 510 511 ///Sum of two maps 512 513 ///This \ref concepts::ReadMap "read only map" returns the sum of the two 514 ///given maps. 515 ///Its \c Key and \c Value are inherited from \c M1. 516 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. 517 template<typename M1, typename M2> 692 inline MapToFunctor<M> mapToFunctor(const M &m) { 693 return MapToFunctor<M>(m); 694 } 695 696 697 /// \brief Map adaptor to convert the \c Value type of a map to 698 /// another type using the default conversion. 699 700 /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap 701 /// "readable map" to another type using the default conversion. 702 /// The \c Key type of it is inherited from \c M and the \c Value 703 /// type is \c V. 704 /// This type conforms the \ref concepts::ReadMap "ReadMap" concept. 705 /// 706 /// The simplest way of using this map is through the convertMap() 707 /// function. 708 template <typename M, typename V> 709 class ConvertMap : public MapBase<typename M::Key, V> { 710 const M &_m; 711 public: 712 typedef MapBase<typename M::Key, V> Parent; 713 typedef typename Parent::Key Key; 714 typedef typename Parent::Value Value; 715 716 /// Constructor 717 718 /// Constructor. 719 /// \param m The underlying map. 720 ConvertMap(const M &m) : _m(m) {} 721 722 /// \e 723 Value operator[](const Key &k) const { return _m[k]; } 724 }; 725 726 /// Returns a \ref ConvertMap class 727 728 /// This function just returns a \ref ConvertMap class. 729 /// \relates ConvertMap 730 template<typename V, typename M> 731 inline ConvertMap<M, V> convertMap(const M &map) { 732 return ConvertMap<M, V>(map); 733 } 734 735 736 /// Applies all map setting operations to two maps 737 738 /// This map has two \ref concepts::WriteMap "writable map" parameters 739 /// and each write request will be passed to both of them. 740 /// If \c M1 is also \ref concepts::ReadMap "readable", then the read 741 /// operations will return the corresponding values of \c M1. 742 /// 743 /// The \c Key and \c Value types are inherited from \c M1. 744 /// The \c Key and \c Value of \c M2 must be convertible from those 745 /// of \c M1. 746 /// 747 /// The simplest way of using this map is through the forkMap() 748 /// function. 749 template<typename M1, typename M2> 750 class ForkMap : public MapBase<typename M1::Key, typename M1::Value> { 751 M1 &_m1; 752 M2 &_m2; 753 public: 754 typedef MapBase<typename M1::Key, typename M1::Value> Parent; 755 typedef typename Parent::Key Key; 756 typedef typename Parent::Value Value; 757 758 /// Constructor 759 ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {} 760 /// Returns the value associated with the given key in the first map. 761 Value operator[](const Key &k) const { return _m1[k]; } 762 /// Sets the value associated with the given key in both maps. 763 void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); } 764 }; 765 766 /// Returns a \ref ForkMap class 767 768 /// This function just returns a \ref ForkMap class. 769 /// \relates ForkMap 770 template <typename M1, typename M2> 771 inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) { 772 return ForkMap<M1,M2>(m1,m2); 773 } 774 775 776 /// Sum of two maps 777 778 /// This \ref concepts::ReadMap "read-only map" returns the sum 779 /// of the values of the two given maps. 780 /// Its \c Key and \c Value types are inherited from \c M1. 781 /// The \c Key and \c Value of \c M2 must be convertible to those of 782 /// \c M1. 783 /// 784 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for 785 /// \code 786 /// AddMap<M1,M2> am(m1,m2); 787 /// \endcode 788 /// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>. 789 /// 790 /// The simplest way of using this map is through the addMap() 791 /// function. 792 /// 793 /// \sa SubMap, MulMap, DivMap 794 /// \sa ShiftMap, ShiftWriteMap 795 template<typename M1, typename M2> 518 796 class AddMap : public MapBase<typename M1::Key, typename M1::Value> { 519 const M1& m1; 520 const M2& m2; 521 797 const M1 &_m1; 798 const M2 &_m2; 522 799 public: 523 800 typedef MapBase<typename M1::Key, typename M1::Value> Parent; … … 525 802 typedef typename Parent::Value Value; 526 803 527 ///Constructor 528 AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {}; 529 ///\e 530 Value operator[](Key k) const {return m1[k]+m2[k];} 531 }; 532 533 ///Returns an \c AddMap class 534 535 ///This function just returns an \c AddMap class. 536 ///\todo Extend the documentation: how to call these type of functions? 537 /// 538 ///\relates AddMap 539 template<typename M1, typename M2> 540 inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) { 804 /// Constructor 805 AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 806 /// \e 807 Value operator[](const Key &k) const { return _m1[k]+_m2[k]; } 808 }; 809 810 /// Returns an \ref AddMap class 811 812 /// This function just returns an \ref AddMap class. 813 /// 814 /// For example, if \c m1 and \c m2 are both maps with \c double 815 /// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to 816 /// <tt>m1[x]+m2[x]</tt>. 817 /// 818 /// \relates AddMap 819 template<typename M1, typename M2> 820 inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) { 541 821 return AddMap<M1, M2>(m1,m2); 542 822 } 543 823 544 ///Shift a map with a constant. 545 546 ///This \ref concepts::ReadMap "read only map" returns the sum of the 547 ///given map and a constant value. 548 ///Its \c Key and \c Value are inherited from \c M. 549 /// 550 ///Actually, 551 ///\code 552 /// ShiftMap<X> sh(x,v); 553 ///\endcode 554 ///is equivalent to 555 ///\code 556 /// ConstMap<X::Key, X::Value> c_tmp(v); 557 /// AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v); 558 ///\endcode 559 /// 560 ///\sa ShiftWriteMap 561 template<typename M, typename C = typename M::Value> 562 class ShiftMap : public MapBase<typename M::Key, typename M::Value> { 563 const M& m; 564 C v; 565 public: 566 typedef MapBase<typename M::Key, typename M::Value> Parent; 567 typedef typename Parent::Key Key; 568 typedef typename Parent::Value Value; 569 570 ///Constructor 571 572 ///Constructor. 573 ///\param _m is the undelying map. 574 ///\param _v is the shift value. 575 ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {}; 576 ///\e 577 Value operator[](Key k) const {return m[k] + v;} 578 }; 579 580 ///Shift a map with a constant (ReadWrite version). 581 582 ///This \ref concepts::ReadWriteMap "read-write map" returns the sum of the 583 ///given map and a constant value. It makes also possible to write the map. 584 ///Its \c Key and \c Value are inherited from \c M. 585 /// 586 ///\sa ShiftMap 587 template<typename M, typename C = typename M::Value> 588 class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> { 589 M& m; 590 C v; 591 public: 592 typedef MapBase<typename M::Key, typename M::Value> Parent; 593 typedef typename Parent::Key Key; 594 typedef typename Parent::Value Value; 595 596 ///Constructor 597 598 ///Constructor. 599 ///\param _m is the undelying map. 600 ///\param _v is the shift value. 601 ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {}; 602 /// \e 603 Value operator[](Key k) const {return m[k] + v;} 604 /// \e 605 void set(Key k, const Value& c) { m.set(k, c - v); } 606 }; 607 608 ///Returns a \c ShiftMap class 609 610 ///This function just returns a \c ShiftMap class. 611 ///\relates ShiftMap 612 template<typename M, typename C> 613 inline ShiftMap<M, C> shiftMap(const M &m,const C &v) { 614 return ShiftMap<M, C>(m,v); 615 } 616 617 ///Returns a \c ShiftWriteMap class 618 619 ///This function just returns a \c ShiftWriteMap class. 620 ///\relates ShiftWriteMap 621 template<typename M, typename C> 622 inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) { 623 return ShiftWriteMap<M, C>(m,v); 624 } 625 626 ///Difference of two maps 627 628 ///This \ref concepts::ReadMap "read only map" returns the difference 629 ///of the values of the two given maps. 630 ///Its \c Key and \c Value are inherited from \c M1. 631 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. 632 /// 633 /// \todo Revise the misleading name 634 template<typename M1, typename M2> 824 825 /// Difference of two maps 826 827 /// This \ref concepts::ReadMap "read-only map" returns the difference 828 /// of the values of the two given maps. 829 /// Its \c Key and \c Value types are inherited from \c M1. 830 /// The \c Key and \c Value of \c M2 must be convertible to those of 831 /// \c M1. 832 /// 833 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for 834 /// \code 835 /// SubMap<M1,M2> sm(m1,m2); 836 /// \endcode 837 /// <tt>sm[x]</tt> will be equal to <tt>m1[x]-m2[x]</tt>. 838 /// 839 /// The simplest way of using this map is through the subMap() 840 /// function. 841 /// 842 /// \sa AddMap, MulMap, DivMap 843 template<typename M1, typename M2> 635 844 class SubMap : public MapBase<typename M1::Key, typename M1::Value> { 636 const M1 &m1;637 const M2 &m2;845 const M1 &_m1; 846 const M2 &_m2; 638 847 public: 639 848 typedef MapBase<typename M1::Key, typename M1::Value> Parent; … … 641 850 typedef typename Parent::Value Value; 642 851 643 ///Constructor 644 SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {}; 645 /// \e 646 Value operator[](Key k) const {return m1[k]-m2[k];} 647 }; 648 649 ///Returns a \c SubMap class 650 651 ///This function just returns a \c SubMap class. 652 /// 653 ///\relates SubMap 654 template<typename M1, typename M2> 852 /// Constructor 853 SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 854 /// \e 855 Value operator[](const Key &k) const { return _m1[k]-_m2[k]; } 856 }; 857 858 /// Returns a \ref SubMap class 859 860 /// This function just returns a \ref SubMap class. 861 /// 862 /// For example, if \c m1 and \c m2 are both maps with \c double 863 /// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to 864 /// <tt>m1[x]-m2[x]</tt>. 865 /// 866 /// \relates SubMap 867 template<typename M1, typename M2> 655 868 inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) { 656 return SubMap<M1, M2>(m1, m2); 657 } 658 659 ///Product of two maps 660 661 ///This \ref concepts::ReadMap "read only map" returns the product of the 662 ///values of the two given maps. 663 ///Its \c Key and \c Value are inherited from \c M1. 664 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. 665 template<typename M1, typename M2> 869 return SubMap<M1, M2>(m1,m2); 870 } 871 872 873 /// Product of two maps 874 875 /// This \ref concepts::ReadMap "read-only map" returns the product 876 /// of the values of the two given maps. 877 /// Its \c Key and \c Value types are inherited from \c M1. 878 /// The \c Key and \c Value of \c M2 must be convertible to those of 879 /// \c M1. 880 /// 881 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for 882 /// \code 883 /// MulMap<M1,M2> mm(m1,m2); 884 /// \endcode 885 /// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>. 886 /// 887 /// The simplest way of using this map is through the mulMap() 888 /// function. 889 /// 890 /// \sa AddMap, SubMap, DivMap 891 /// \sa ScaleMap, ScaleWriteMap 892 template<typename M1, typename M2> 666 893 class MulMap : public MapBase<typename M1::Key, typename M1::Value> { 667 const M1 &m1;668 const M2 &m2;894 const M1 &_m1; 895 const M2 &_m2; 669 896 public: 670 897 typedef MapBase<typename M1::Key, typename M1::Value> Parent; … … 672 899 typedef typename Parent::Value Value; 673 900 674 ///Constructor 675 MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {}; 676 /// \e 677 Value operator[](Key k) const {return m1[k]*m2[k];} 678 }; 679 680 ///Returns a \c MulMap class 681 682 ///This function just returns a \c MulMap class. 683 ///\relates MulMap 684 template<typename M1, typename M2> 901 /// Constructor 902 MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {} 903 /// \e 904 Value operator[](const Key &k) const { return _m1[k]*_m2[k]; } 905 }; 906 907 /// Returns a \ref MulMap class 908 909 /// This function just returns a \ref MulMap class. 910 /// 911 /// For example, if \c m1 and \c m2 are both maps with \c double 912 /// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to 913 /// <tt>m1[x]*m2[x]</tt>. 914 /// 915 /// \relates MulMap 916 template<typename M1, typename M2> 685 917 inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) { 686 918 return MulMap<M1, M2>(m1,m2); 687 919 } 688 689 ///Scales a map with a constant. 690 691 ///This \ref concepts::ReadMap "read only map" returns the value of the 692 ///given map multiplied from the left side with a constant value. 693 ///Its \c Key and \c Value are inherited from \c M. 694 /// 695 ///Actually, 696 ///\code 697 /// ScaleMap<X> sc(x,v); 698 ///\endcode 699 ///is equivalent to 700 ///\code 701 /// ConstMap<X::Key, X::Value> c_tmp(v); 702 /// MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v); 703 ///\endcode 704 /// 705 ///\sa ScaleWriteMap 706 template<typename M, typename C = typename M::Value> 707 class ScaleMap : public MapBase<typename M::Key, typename M::Value> { 708 const M& m; 709 C v; 710 public: 711 typedef MapBase<typename M::Key, typename M::Value> Parent; 712 typedef typename Parent::Key Key; 713 typedef typename Parent::Value Value; 714 715 ///Constructor 716 717 ///Constructor. 718 ///\param _m is the undelying map. 719 ///\param _v is the scaling value. 720 ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {}; 721 /// \e 722 Value operator[](Key k) const {return v * m[k];} 723 }; 724 725 ///Scales a map with a constant (ReadWrite version). 726 727 ///This \ref concepts::ReadWriteMap "read-write map" returns the value of the 728 ///given map multiplied from the left side with a constant value. It can 729 ///also be used as write map if the \c / operator is defined between 730 ///\c Value and \c C and the given multiplier is not zero. 731 ///Its \c Key and \c Value are inherited from \c M. 732 /// 733 ///\sa ScaleMap 734 template<typename M, typename C = typename M::Value> 735 class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> { 736 M& m; 737 C v; 738 public: 739 typedef MapBase<typename M::Key, typename M::Value> Parent; 740 typedef typename Parent::Key Key; 741 typedef typename Parent::Value Value; 742 743 ///Constructor 744 745 ///Constructor. 746 ///\param _m is the undelying map. 747 ///\param _v is the scaling value. 748 ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {}; 749 /// \e 750 Value operator[](Key k) const {return v * m[k];} 751 /// \e 752 void set(Key k, const Value& c) { m.set(k, c / v);} 753 }; 754 755 ///Returns a \c ScaleMap class 756 757 ///This function just returns a \c ScaleMap class. 758 ///\relates ScaleMap 759 template<typename M, typename C> 760 inline ScaleMap<M, C> scaleMap(const M &m,const C &v) { 761 return ScaleMap<M, C>(m,v); 762 } 763 764 ///Returns a \c ScaleWriteMap class 765 766 ///This function just returns a \c ScaleWriteMap class. 767 ///\relates ScaleWriteMap 768 template<typename M, typename C> 769 inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) { 770 return ScaleWriteMap<M, C>(m,v); 771 } 772 773 ///Quotient of two maps 774 775 ///This \ref concepts::ReadMap "read only map" returns the quotient of the 776 ///values of the two given maps. 777 ///Its \c Key and \c Value are inherited from \c M1. 778 ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1. 779 template<typename M1, typename M2> 920 921 922 /// Quotient of two maps 923 924 /// This \ref concepts::ReadMap "read-only map" returns the quotient 925 /// of the values of the two given maps. 926 /// Its \c Key and \c Value types are inherited from \c M1. 927 /// The \c Key and \c Value of \c M2 must be convertible to those of 928 /// \c M1. 929 /// 930 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for 931 /// \code 932 /// DivMap<M1,M2> dm(m1,m2); 933 /// \endcode 934 /// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>. 935 /// 936 /// The simplest way of using this map is through the divMap() 937 /// function. 938 /// 939 /// \sa AddMap, SubMap, MulMap 940 template<typename M1, typename M2> 780 941 class DivMap : public MapBase<typename M1::Key, typename M1::Value> { 781 const M1 &m1;782 const M2 &m2;942 const M1 &_m1; 943 const M2 &_m2; 783 944 public: 784 945 typedef MapBase<typename M1::Key, typename M1::Value> Parent; … … 786 947 typedef typename Parent::Value Value; 787 948 788 ///Constructor 789 DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {}; 790 /// \e 791 Value operator[](Key k) const {return m1[k]/m2[k];} 792 }; 793 794 ///Returns a \c DivMap class 795 796 ///This function just returns a \c DivMap class. 797 ///\relates DivMap 798 template<typename M1, typename M2> 949 /// Constructor 950 DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {} 951 /// \e 952 Value operator[](const Key &k) const { return _m1[k]/_m2[k]; } 953 }; 954 955 /// Returns a \ref DivMap class 956 957 /// This function just returns a \ref DivMap class. 958 /// 959 /// For example, if \c m1 and \c m2 are both maps with \c double 960 /// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to 961 /// <tt>m1[x]/m2[x]</tt>. 962 /// 963 /// \relates DivMap 964 template<typename M1, typename M2> 799 965 inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) { 800 966 return DivMap<M1, M2>(m1,m2); 801 967 } 802 803 ///Composition of two maps 804 805 ///This \ref concepts::ReadMap "read only map" returns the composition of 806 ///two given maps. 807 ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2, 808 ///then for 809 ///\code 810 /// ComposeMap<M1, M2> cm(m1,m2); 811 ///\endcode 812 /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>. 813 /// 814 ///Its \c Key is inherited from \c M2 and its \c Value is from \c M1. 815 ///\c M2::Value must be convertible to \c M1::Key. 816 /// 817 ///\sa CombineMap 818 /// 819 ///\todo Check the requirements. 820 template <typename M1, typename M2> 821 class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> { 822 const M1& m1; 823 const M2& m2; 824 public: 825 typedef MapBase<typename M2::Key, typename M1::Value> Parent; 826 typedef typename Parent::Key Key; 827 typedef typename Parent::Value Value; 828 829 ///Constructor 830 ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {}; 831 832 /// \e 833 834 835 /// \todo Use the MapTraits once it is ported. 836 /// 837 838 //typename MapTraits<M1>::ConstReturnValue 839 typename M1::Value 840 operator[](Key k) const {return m1[m2[k]];} 841 }; 842 843 ///Returns a \c ComposeMap class 844 845 ///This function just returns a \c ComposeMap class. 846 ///\relates ComposeMap 847 template <typename M1, typename M2> 848 inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) { 849 return ComposeMap<M1, M2>(m1,m2); 850 } 851 852 ///Combine of two maps using an STL (binary) functor. 853 854 ///Combine of two maps using an STL (binary) functor. 855 /// 856 ///This \ref concepts::ReadMap "read only map" takes two maps and a 857 ///binary functor and returns the composition of the two 858 ///given maps unsing the functor. 859 ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2 860 ///and \c f is of \c F, then for 861 ///\code 862 /// CombineMap<M1,M2,F,V> cm(m1,m2,f); 863 ///\endcode 864 /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt> 865 /// 866 ///Its \c Key is inherited from \c M1 and its \c Value is \c V. 867 ///\c M2::Value and \c M1::Value must be convertible to the corresponding 868 ///input parameter of \c F and the return type of \c F must be convertible 869 ///to \c V. 870 /// 871 ///\sa ComposeMap 872 /// 873 ///\todo Check the requirements. 874 template<typename M1, typename M2, typename F, 875 typename V = typename F::result_type> 876 class CombineMap : public MapBase<typename M1::Key, V> { 877 const M1& m1; 878 const M2& m2; 879 F f; 880 public: 881 typedef MapBase<typename M1::Key, V> Parent; 882 typedef typename Parent::Key Key; 883 typedef typename Parent::Value Value; 884 885 ///Constructor 886 CombineMap(const M1 &_m1,const M2 &_m2,const F &_f = F()) 887 : m1(_m1), m2(_m2), f(_f) {}; 888 /// \e 889 Value operator[](Key k) const {return f(m1[k],m2[k]);} 890 }; 891 892 ///Returns a \c CombineMap class 893 894 ///This function just returns a \c CombineMap class. 895 /// 896 ///For example if \c m1 and \c m2 are both \c double valued maps, then 897 ///\code 898 ///combineMap(m1,m2,std::plus<double>()) 899 ///\endcode 900 ///is equivalent to 901 ///\code 902 ///addMap(m1,m2) 903 ///\endcode 904 /// 905 ///This function is specialized for adaptable binary function 906 ///classes and C++ functions. 907 /// 908 ///\relates CombineMap 909 template<typename M1, typename M2, typename F, typename V> 910 inline CombineMap<M1, M2, F, V> 911 combineMap(const M1& m1,const M2& m2, const F& f) { 912 return CombineMap<M1, M2, F, V>(m1,m2,f); 913 } 914 915 template<typename M1, typename M2, typename F> 916 inline CombineMap<M1, M2, F, typename F::result_type> 917 combineMap(const M1& m1, const M2& m2, const F& f) { 918 return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f); 919 } 920 921 template<typename M1, typename M2, typename K1, typename K2, typename V> 922 inline CombineMap<M1, M2, V (*)(K1, K2), V> 923 combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) { 924 return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f); 925 } 926 927 ///Negative value of a map 928 929 ///This \ref concepts::ReadMap "read only map" returns the negative 930 ///value of the value returned by the given map. 931 ///Its \c Key and \c Value are inherited from \c M. 932 ///The unary \c - operator must be defined for \c Value, of course. 933 /// 934 ///\sa NegWriteMap 935 template<typename M> 968 969 970 /// Shifts a map with a constant. 971 972 /// This \ref concepts::ReadMap "read-only map" returns the sum of 973 /// the given map and a constant value (i.e. it shifts the map with 974 /// the constant). Its \c Key and \c Value are inherited from \c M. 975 /// 976 /// Actually, 977 /// \code 978 /// ShiftMap<M> sh(m,v); 979 /// \endcode 980 /// is equivalent to 981 /// \code 982 /// ConstMap<M::Key, M::Value> cm(v); 983 /// AddMap<M, ConstMap<M::Key, M::Value> > sh(m,cm); 984 /// \endcode 985 /// 986 /// The simplest way of using this map is through the shiftMap() 987 /// function. 988 /// 989 /// \sa ShiftWriteMap 990 template<typename M, typename C = typename M::Value> 991 class ShiftMap : public MapBase<typename M::Key, typename M::Value> { 992 const M &_m; 993 C _v; 994 public: 995 typedef MapBase<typename M::Key, typename M::Value> Parent; 996 typedef typename Parent::Key Key; 997 typedef typename Parent::Value Value; 998 999 /// Constructor 1000 1001 /// Constructor. 1002 /// \param m The undelying map. 1003 /// \param v The constant value. 1004 ShiftMap(const M &m, const C &v) : _m(m), _v(v) {} 1005 /// \e 1006 Value operator[](const Key &k) const { return _m[k]+_v; } 1007 }; 1008 1009 /// Shifts a map with a constant (read-write version). 1010 1011 /// This \ref concepts::ReadWriteMap "read-write map" returns the sum 1012 /// of the given map and a constant value (i.e. it shifts the map with 1013 /// the constant). Its \c Key and \c Value are inherited from \c M. 1014 /// It makes also possible to write the map. 1015 /// 1016 /// The simplest way of using this map is through the shiftWriteMap() 1017 /// function. 1018 /// 1019 /// \sa ShiftMap 1020 template<typename M, typename C = typename M::Value> 1021 class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> { 1022 M &_m; 1023 C _v; 1024 public: 1025 typedef MapBase<typename M::Key, typename M::Value> Parent; 1026 typedef typename Parent::Key Key; 1027 typedef typename Parent::Value Value; 1028 1029 /// Constructor 1030 1031 /// Constructor. 1032 /// \param m The undelying map. 1033 /// \param v The constant value. 1034 ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {} 1035 /// \e 1036 Value operator[](const Key &k) const { return _m[k]+_v; } 1037 /// \e 1038 void set(const Key &k, const Value &v) { _m.set(k, v-_v); } 1039 }; 1040 1041 /// Returns a \ref ShiftMap class 1042 1043 /// This function just returns a \ref ShiftMap class. 1044 /// 1045 /// For example, if \c m is a map with \c double values and \c v is 1046 /// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to 1047 /// <tt>m[x]+v</tt>. 1048 /// 1049 /// \relates ShiftMap 1050 template<typename M, typename C> 1051 inline ShiftMap<M, C> shiftMap(const M &m, const C &v) { 1052 return ShiftMap<M, C>(m,v); 1053 } 1054 1055 /// Returns a \ref ShiftWriteMap class 1056 1057 /// This function just returns a \ref ShiftWriteMap class. 1058 /// 1059 /// For example, if \c m is a map with \c double values and \c v is 1060 /// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to 1061 /// <tt>m[x]+v</tt>. 1062 /// Moreover it makes also possible to write the map. 1063 /// 1064 /// \relates ShiftWriteMap 1065 template<typename M, typename C> 1066 inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) { 1067 return ShiftWriteMap<M, C>(m,v); 1068 } 1069 1070 1071 /// Scales a map with a constant. 1072 1073 /// This \ref concepts::ReadMap "read-only map" returns the value of 1074 /// the given map multiplied from the left side with a constant value. 1075 /// Its \c Key and \c Value are inherited from \c M. 1076 /// 1077 /// Actually, 1078 /// \code 1079 /// ScaleMap<M> sc(m,v); 1080 /// \endcode 1081 /// is equivalent to 1082 /// \code 1083 /// ConstMap<M::Key, M::Value> cm(v); 1084 /// MulMap<ConstMap<M::Key, M::Value>, M> sc(cm,m); 1085 /// \endcode 1086 /// 1087 /// The simplest way of using this map is through the scaleMap() 1088 /// function. 1089 /// 1090 /// \sa ScaleWriteMap 1091 template<typename M, typename C = typename M::Value> 1092 class ScaleMap : public MapBase<typename M::Key, typename M::Value> { 1093 const M &_m; 1094 C _v; 1095 public: 1096 typedef MapBase<typename M::Key, typename M::Value> Parent; 1097 typedef typename Parent::Key Key; 1098 typedef typename Parent::Value Value; 1099 1100 /// Constructor 1101 1102 /// Constructor. 1103 /// \param m The undelying map. 1104 /// \param v The constant value. 1105 ScaleMap(const M &m, const C &v) : _m(m), _v(v) {} 1106 /// \e 1107 Value operator[](const Key &k) const { return _v*_m[k]; } 1108 }; 1109 1110 /// Scales a map with a constant (read-write version). 1111 1112 /// This \ref concepts::ReadWriteMap "read-write map" returns the value of 1113 /// the given map multiplied from the left side with a constant value. 1114 /// Its \c Key and \c Value are inherited from \c M. 1115 /// It can also be used as write map if the \c / operator is defined 1116 /// between \c Value and \c C and the given multiplier is not zero. 1117 /// 1118 /// The simplest way of using this map is through the scaleWriteMap() 1119 /// function. 1120 /// 1121 /// \sa ScaleMap 1122 template<typename M, typename C = typename M::Value> 1123 class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> { 1124 M &_m; 1125 C _v; 1126 public: 1127 typedef MapBase<typename M::Key, typename M::Value> Parent; 1128 typedef typename Parent::Key Key; 1129 typedef typename Parent::Value Value; 1130 1131 /// Constructor 1132 1133 /// Constructor. 1134 /// \param m The undelying map. 1135 /// \param v The constant value. 1136 ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {} 1137 /// \e 1138 Value operator[](const Key &k) const { return _v*_m[k]; } 1139 /// \e 1140 void set(const Key &k, const Value &v) { _m.set(k, v/_v); } 1141 }; 1142 1143 /// Returns a \ref ScaleMap class 1144 1145 /// This function just returns a \ref ScaleMap class. 1146 /// 1147 /// For example, if \c m is a map with \c double values and \c v is 1148 /// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to 1149 /// <tt>v*m[x]</tt>. 1150 /// 1151 /// \relates ScaleMap 1152 template<typename M, typename C> 1153 inline ScaleMap<M, C> scaleMap(const M &m, const C &v) { 1154 return ScaleMap<M, C>(m,v); 1155 } 1156 1157 /// Returns a \ref ScaleWriteMap class 1158 1159 /// This function just returns a \ref ScaleWriteMap class. 1160 /// 1161 /// For example, if \c m is a map with \c double values and \c v is 1162 /// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to 1163 /// <tt>v*m[x]</tt>. 1164 /// Moreover it makes also possible to write the map. 1165 /// 1166 /// \relates ScaleWriteMap 1167 template<typename M, typename C> 1168 inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) { 1169 return ScaleWriteMap<M, C>(m,v); 1170 } 1171 1172 1173 /// Negative of a map 1174 1175 /// This \ref concepts::ReadMap "read-only map" returns the negative 1176 /// of the values of the given map (using the unary \c - operator). 1177 /// Its \c Key and \c Value are inherited from \c M. 1178 /// 1179 /// If M::Value is \c int, \c double etc., then 1180 /// \code 1181 /// NegMap<M> neg(m); 1182 /// \endcode 1183 /// is equivalent to 1184 /// \code 1185 /// ScaleMap<M> neg(m,-1); 1186 /// \endcode 1187 /// 1188 /// The simplest way of using this map is through the negMap() 1189 /// function. 1190 /// 1191 /// \sa NegWriteMap 1192 template<typename M> 936 1193 class NegMap : public MapBase<typename M::Key, typename M::Value> { 937 const M& m;1194 const M& _m; 938 1195 public: 939 1196 typedef MapBase<typename M::Key, typename M::Value> Parent; … … 941 1198 typedef typename Parent::Value Value; 942 1199 943 ///Constructor 944 NegMap(const M &_m) : m(_m) {}; 945 /// \e 946 Value operator[](Key k) const {return -m[k];} 947 }; 948 949 ///Negative value of a map (ReadWrite version) 950 951 ///This \ref concepts::ReadWriteMap "read-write map" returns the negative 952 ///value of the value returned by the given map. 953 ///Its \c Key and \c Value are inherited from \c M. 954 ///The unary \c - operator must be defined for \c Value, of course. 1200 /// Constructor 1201 NegMap(const M &m) : _m(m) {} 1202 /// \e 1203 Value operator[](const Key &k) const { return -_m[k]; } 1204 }; 1205 1206 /// Negative of a map (read-write version) 1207 1208 /// This \ref concepts::ReadWriteMap "read-write map" returns the 1209 /// negative of the values of the given map (using the unary \c - 1210 /// operator). 1211 /// Its \c Key and \c Value are inherited from \c M. 1212 /// It makes also possible to write the map. 1213 /// 1214 /// If M::Value is \c int, \c double etc., then 1215 /// \code 1216 /// NegWriteMap<M> neg(m); 1217 /// \endcode 1218 /// is equivalent to 1219 /// \code 1220 /// ScaleWriteMap<M> neg(m,-1); 1221 /// \endcode 1222 /// 1223 /// The simplest way of using this map is through the negWriteMap() 1224 /// function. 955 1225 /// 956 1226 /// \sa NegMap 957 template<typename M> 1227 template<typename M> 958 1228 class NegWriteMap : public MapBase<typename M::Key, typename M::Value> { 959 M &m;1229 M &_m; 960 1230 public: 961 1231 typedef MapBase<typename M::Key, typename M::Value> Parent; … … 963 1233 typedef typename Parent::Value Value; 964 1234 965 ///Constructor 966 NegWriteMap(M &_m) : m(_m) {}; 967 /// \e 968 Value operator[](Key k) const {return -m[k];} 969 /// \e 970 void set(Key k, const Value& v) { m.set(k, -v); } 971 }; 972 973 ///Returns a \c NegMap class 974 975 ///This function just returns a \c NegMap class. 976 ///\relates NegMap 977 template <typename M> 1235 /// Constructor 1236 NegWriteMap(M &m) : _m(m) {} 1237 /// \e 1238 Value operator[](const Key &k) const { return -_m[k]; } 1239 /// \e 1240 void set(const Key &k, const Value &v) { _m.set(k, -v); } 1241 }; 1242 1243 /// Returns a \ref NegMap class 1244 1245 /// This function just returns a \ref NegMap class. 1246 /// 1247 /// For example, if \c m is a map with \c double values, then 1248 /// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>. 1249 /// 1250 /// \relates NegMap 1251 template <typename M> 978 1252 inline NegMap<M> negMap(const M &m) { 979 1253 return NegMap<M>(m); 980 1254 } 981 1255 982 ///Returns a \c NegWriteMap class 983 984 ///This function just returns a \c NegWriteMap class. 985 ///\relates NegWriteMap 986 template <typename M> 987 inline NegWriteMap<M> negMap(M &m) { 1256 /// Returns a \ref NegWriteMap class 1257 1258 /// This function just returns a \ref NegWriteMap class. 1259 /// 1260 /// For example, if \c m is a map with \c double values, then 1261 /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>. 1262 /// Moreover it makes also possible to write the map. 1263 /// 1264 /// \relates NegWriteMap 1265 template <typename M> 1266 inline NegWriteMap<M> negWriteMap(M &m) { 988 1267 return NegWriteMap<M>(m); 989 1268 } 990 1269 991 ///Absolute value of a map 992 993 ///This \ref concepts::ReadMap "read only map" returns the absolute value 994 ///of the value returned by the given map. 995 ///Its \c Key and \c Value are inherited from \c M. 996 ///\c Value must be comparable to \c 0 and the unary \c - 997 ///operator must be defined for it, of course. 998 template<typename M> 1270 1271 /// Absolute value of a map 1272 1273 /// This \ref concepts::ReadMap "read-only map" returns the absolute 1274 /// value of the values of the given map. 1275 /// Its \c Key and \c Value are inherited from \c M. 1276 /// \c Value must be comparable to \c 0 and the unary \c - 1277 /// operator must be defined for it, of course. 1278 /// 1279 /// The simplest way of using this map is through the absMap() 1280 /// function. 1281 template<typename M> 999 1282 class AbsMap : public MapBase<typename M::Key, typename M::Value> { 1000 const M &m;1283 const M &_m; 1001 1284 public: 1002 1285 typedef MapBase<typename M::Key, typename M::Value> Parent; … … 1004 1287 typedef typename Parent::Value Value; 1005 1288 1006 /// Constructor1007 AbsMap(const M & _m) : m(_m) {};1008 /// \e 1009 Value operator[]( Keyk) const {1010 Value tmp = m[k];1289 /// Constructor 1290 AbsMap(const M &m) : _m(m) {} 1291 /// \e 1292 Value operator[](const Key &k) const { 1293 Value tmp = _m[k]; 1011 1294 return tmp >= 0 ? tmp : -tmp; 1012 1295 } 1013 1296 1014 1297 }; 1015 1016 ///Returns an \c AbsMap class 1017 1018 ///This function just returns an \c AbsMap class. 1019 ///\relates AbsMap 1020 template<typename M> 1298 1299 /// Returns an \ref AbsMap class 1300 1301 /// This function just returns an \ref AbsMap class. 1302 /// 1303 /// For example, if \c m is a map with \c double values, then 1304 /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if 1305 /// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is 1306 /// negative. 1307 /// 1308 /// \relates AbsMap 1309 template<typename M> 1021 1310 inline AbsMap<M> absMap(const M &m) { 1022 1311 return AbsMap<M>(m); 1023 1312 } 1024 1313 1025 ///Converts an STL style functor to a map 1026 1027 ///This \ref concepts::ReadMap "read only map" returns the value 1028 ///of a given functor. 1029 /// 1030 ///Template parameters \c K and \c V will become its 1031 ///\c Key and \c Value. 1032 ///In most cases they have to be given explicitly because a 1033 ///functor typically does not provide \c argument_type and 1034 ///\c result_type typedefs. 1035 /// 1036 ///Parameter \c F is the type of the used functor. 1037 /// 1038 ///\sa MapFunctor 1039 template<typename F, 1040 typename K = typename F::argument_type, 1041 typename V = typename F::result_type> 1042 class FunctorMap : public MapBase<K, V> { 1043 F f; 1044 public: 1045 typedef MapBase<K, V> Parent; 1046 typedef typename Parent::Key Key; 1047 typedef typename Parent::Value Value; 1048 1049 ///Constructor 1050 FunctorMap(const F &_f = F()) : f(_f) {} 1051 /// \e 1052 Value operator[](Key k) const { return f(k);} 1053 }; 1314 /// @} 1054 1315 1055 ///Returns a \c FunctorMap class 1056 1057 ///This function just returns a \c FunctorMap class. 1058 /// 1059 ///This function is specialized for adaptable binary function 1060 ///classes and C++ functions. 1061 /// 1062 ///\relates FunctorMap 1063 template<typename K, typename V, typename F> inline 1064 FunctorMap<F, K, V> functorMap(const F &f) { 1065 return FunctorMap<F, K, V>(f); 1066 } 1067 1068 template <typename F> inline 1069 FunctorMap<F, typename F::argument_type, typename F::result_type> 1070 functorMap(const F &f) { 1071 return FunctorMap<F, typename F::argument_type, 1072 typename F::result_type>(f); 1073 } 1074 1075 template <typename K, typename V> inline 1076 FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) { 1077 return FunctorMap<V (*)(K), K, V>(f); 1078 } 1079 1080 1081 ///Converts a map to an STL style (unary) functor 1082 1083 ///This class Converts a map to an STL style (unary) functor. 1084 ///That is it provides an <tt>operator()</tt> to read its values. 1085 /// 1086 ///For the sake of convenience it also works as 1087 ///a ususal \ref concepts::ReadMap "readable map", 1088 ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist. 1089 /// 1090 ///\sa FunctorMap 1091 template <typename M> 1092 class MapFunctor : public MapBase<typename M::Key, typename M::Value> { 1093 const M& m; 1094 public: 1095 typedef MapBase<typename M::Key, typename M::Value> Parent; 1096 typedef typename Parent::Key Key; 1097 typedef typename Parent::Value Value; 1098 1099 typedef typename M::Key argument_type; 1100 typedef typename M::Value result_type; 1101 1102 ///Constructor 1103 MapFunctor(const M &_m) : m(_m) {}; 1104 ///\e 1105 Value operator()(Key k) const {return m[k];} 1106 ///\e 1107 Value operator[](Key k) const {return m[k];} 1108 }; 1109 1110 ///Returns a \c MapFunctor class 1111 1112 ///This function just returns a \c MapFunctor class. 1113 ///\relates MapFunctor 1114 template<typename M> 1115 inline MapFunctor<M> mapFunctor(const M &m) { 1116 return MapFunctor<M>(m); 1117 } 1118 1119 ///Just readable version of \ref ForkWriteMap 1120 1121 ///This map has two \ref concepts::ReadMap "readable map" 1122 ///parameters and each read request will be passed just to the 1123 ///first map. This class is the just readable map type of \c ForkWriteMap. 1124 /// 1125 ///The \c Key and \c Value are inherited from \c M1. 1126 ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1. 1127 /// 1128 ///\sa ForkWriteMap 1129 /// 1130 /// \todo Why is it needed? 1131 template<typename M1, typename M2> 1132 class ForkMap : public MapBase<typename M1::Key, typename M1::Value> { 1133 const M1& m1; 1134 const M2& m2; 1135 public: 1136 typedef MapBase<typename M1::Key, typename M1::Value> Parent; 1137 typedef typename Parent::Key Key; 1138 typedef typename Parent::Value Value; 1139 1140 ///Constructor 1141 ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {}; 1142 /// \e 1143 Value operator[](Key k) const {return m1[k];} 1144 }; 1145 1146 1147 ///Applies all map setting operations to two maps 1148 1149 ///This map has two \ref concepts::WriteMap "writable map" 1150 ///parameters and each write request will be passed to both of them. 1151 ///If \c M1 is also \ref concepts::ReadMap "readable", 1152 ///then the read operations will return the 1153 ///corresponding values of \c M1. 1154 /// 1155 ///The \c Key and \c Value are inherited from \c M1. 1156 ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1. 1157 /// 1158 ///\sa ForkMap 1159 template<typename M1, typename M2> 1160 class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> { 1161 M1& m1; 1162 M2& m2; 1163 public: 1164 typedef MapBase<typename M1::Key, typename M1::Value> Parent; 1165 typedef typename Parent::Key Key; 1166 typedef typename Parent::Value Value; 1167 1168 ///Constructor 1169 ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {}; 1170 ///\e 1171 Value operator[](Key k) const {return m1[k];} 1172 ///\e 1173 void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);} 1174 }; 1175 1176 ///Returns a \c ForkMap class 1177 1178 ///This function just returns a \c ForkMap class. 1179 ///\relates ForkMap 1180 template <typename M1, typename M2> 1181 inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) { 1182 return ForkMap<M1, M2>(m1,m2); 1183 } 1184 1185 ///Returns a \c ForkWriteMap class 1186 1187 ///This function just returns a \c ForkWriteMap class. 1188 ///\relates ForkWriteMap 1189 template <typename M1, typename M2> 1190 inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) { 1191 return ForkWriteMap<M1, M2>(m1,m2); 1192 } 1193 1194 1195 1196 /* ************* BOOL MAPS ******************* */ 1197 1198 ///Logical 'not' of a map 1199 1200 ///This bool \ref concepts::ReadMap "read only map" returns the 1201 ///logical negation of the value returned by the given map. 1202 ///Its \c Key is inherited from \c M, its \c Value is \c bool. 1203 /// 1204 ///\sa NotWriteMap 1205 template <typename M> 1316 // Logical maps and map adaptors: 1317 1318 /// \addtogroup maps 1319 /// @{ 1320 1321 /// Constant \c true map. 1322 1323 /// This \ref concepts::ReadMap "read-only map" assigns \c true to 1324 /// each key. 1325 /// 1326 /// Note that 1327 /// \code 1328 /// TrueMap<K> tm; 1329 /// \endcode 1330 /// is equivalent to 1331 /// \code 1332 /// ConstMap<K,bool> tm(true); 1333 /// \endcode 1334 /// 1335 /// \sa FalseMap 1336 /// \sa ConstMap 1337 template <typename K> 1338 class TrueMap : public MapBase<K, bool> { 1339 public: 1340 typedef MapBase<K, bool> Parent; 1341 typedef typename Parent::Key Key; 1342 typedef typename Parent::Value Value; 1343 1344 /// Gives back \c true. 1345 Value operator[](const Key&) const { return true; } 1346 }; 1347 1348 /// Returns a \ref TrueMap class 1349 1350 /// This function just returns a \ref TrueMap class. 1351 /// \relates TrueMap 1352 template<typename K> 1353 inline TrueMap<K> trueMap() { 1354 return TrueMap<K>(); 1355 } 1356 1357 1358 /// Constant \c false map. 1359 1360 /// This \ref concepts::ReadMap "read-only map" assigns \c false to 1361 /// each key. 1362 /// 1363 /// Note that 1364 /// \code 1365 /// FalseMap<K> fm; 1366 /// \endcode 1367 /// is equivalent to 1368 /// \code 1369 /// ConstMap<K,bool> fm(false); 1370 /// \endcode 1371 /// 1372 /// \sa TrueMap 1373 /// \sa ConstMap 1374 template <typename K> 1375 class FalseMap : public MapBase<K, bool> { 1376 public: 1377 typedef MapBase<K, bool> Parent; 1378 typedef typename Parent::Key Key; 1379 typedef typename Parent::Value Value; 1380 1381 /// Gives back \c false. 1382 Value operator[](const Key&) const { return false; } 1383 }; 1384 1385 /// Returns a \ref FalseMap class 1386 1387 /// This function just returns a \ref FalseMap class. 1388 /// \relates FalseMap 1389 template<typename K> 1390 inline FalseMap<K> falseMap() { 1391 return FalseMap<K>(); 1392 } 1393 1394 /// @} 1395 1396 /// \addtogroup map_adaptors 1397 /// @{ 1398 1399 /// Logical 'and' of two maps 1400 1401 /// This \ref concepts::ReadMap "read-only map" returns the logical 1402 /// 'and' of the values of the two given maps. 1403 /// Its \c Key type is inherited from \c M1 and its \c Value type is 1404 /// \c bool. \c M2::Key must be convertible to \c M1::Key. 1405 /// 1406 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for 1407 /// \code 1408 /// AndMap<M1,M2> am(m1,m2); 1409 /// \endcode 1410 /// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>. 1411 /// 1412 /// The simplest way of using this map is through the andMap() 1413 /// function. 1414 /// 1415 /// \sa OrMap 1416 /// \sa NotMap, NotWriteMap 1417 template<typename M1, typename M2> 1418 class AndMap : public MapBase<typename M1::Key, bool> { 1419 const M1 &_m1; 1420 const M2 &_m2; 1421 public: 1422 typedef MapBase<typename M1::Key, bool> Parent; 1423 typedef typename Parent::Key Key; 1424 typedef typename Parent::Value Value; 1425 1426 /// Constructor 1427 AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 1428 /// \e 1429 Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; } 1430 }; 1431 1432 /// Returns an \ref AndMap class 1433 1434 /// This function just returns an \ref AndMap class. 1435 /// 1436 /// For example, if \c m1 and \c m2 are both maps with \c bool values, 1437 /// then <tt>andMap(m1,m2)[x]</tt> will be equal to 1438 /// <tt>m1[x]&&m2[x]</tt>. 1439 /// 1440 /// \relates AndMap 1441 template<typename M1, typename M2> 1442 inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) { 1443 return AndMap<M1, M2>(m1,m2); 1444 } 1445 1446 1447 /// Logical 'or' of two maps 1448 1449 /// This \ref concepts::ReadMap "read-only map" returns the logical 1450 /// 'or' of the values of the two given maps. 1451 /// Its \c Key type is inherited from \c M1 and its \c Value type is 1452 /// \c bool. \c M2::Key must be convertible to \c M1::Key. 1453 /// 1454 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for 1455 /// \code 1456 /// OrMap<M1,M2> om(m1,m2); 1457 /// \endcode 1458 /// <tt>om[x]</tt> will be equal to <tt>m1[x]||m2[x]</tt>. 1459 /// 1460 /// The simplest way of using this map is through the orMap() 1461 /// function. 1462 /// 1463 /// \sa AndMap 1464 /// \sa NotMap, NotWriteMap 1465 template<typename M1, typename M2> 1466 class OrMap : public MapBase<typename M1::Key, bool> { 1467 const M1 &_m1; 1468 const M2 &_m2; 1469 public: 1470 typedef MapBase<typename M1::Key, bool> Parent; 1471 typedef typename Parent::Key Key; 1472 typedef typename Parent::Value Value; 1473 1474 /// Constructor 1475 OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 1476 /// \e 1477 Value operator[](const Key &k) const { return _m1[k]||_m2[k]; } 1478 }; 1479 1480 /// Returns an \ref OrMap class 1481 1482 /// This function just returns an \ref OrMap class. 1483 /// 1484 /// For example, if \c m1 and \c m2 are both maps with \c bool values, 1485 /// then <tt>orMap(m1,m2)[x]</tt> will be equal to 1486 /// <tt>m1[x]||m2[x]</tt>. 1487 /// 1488 /// \relates OrMap 1489 template<typename M1, typename M2> 1490 inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) { 1491 return OrMap<M1, M2>(m1,m2); 1492 } 1493 1494 1495 /// Logical 'not' of a map 1496 1497 /// This \ref concepts::ReadMap "read-only map" returns the logical 1498 /// negation of the values of the given map. 1499 /// Its \c Key is inherited from \c M and its \c Value is \c bool. 1500 /// 1501 /// The simplest way of using this map is through the notMap() 1502 /// function. 1503 /// 1504 /// \sa NotWriteMap 1505 template <typename M> 1206 1506 class NotMap : public MapBase<typename M::Key, bool> { 1207 const M &m;1507 const M &_m; 1208 1508 public: 1209 1509 typedef MapBase<typename M::Key, bool> Parent; … … 1212 1512 1213 1513 /// Constructor 1214 NotMap(const M &_m) : m(_m) {}; 1215 ///\e 1216 Value operator[](Key k) const {return !m[k];} 1217 }; 1218 1219 ///Logical 'not' of a map (ReadWrie version) 1220 1221 ///This bool \ref concepts::ReadWriteMap "read-write map" returns the 1222 ///logical negation of the value returned by the given map. When it is set, 1223 ///the opposite value is set to the original map. 1224 ///Its \c Key is inherited from \c M, its \c Value is \c bool. 1225 /// 1226 ///\sa NotMap 1227 template <typename M> 1514 NotMap(const M &m) : _m(m) {} 1515 /// \e 1516 Value operator[](const Key &k) const { return !_m[k]; } 1517 }; 1518 1519 /// Logical 'not' of a map (read-write version) 1520 1521 /// This \ref concepts::ReadWriteMap "read-write map" returns the 1522 /// logical negation of the values of the given map. 1523 /// Its \c Key is inherited from \c M and its \c Value is \c bool. 1524 /// It makes also possible to write the map. When a value is set, 1525 /// the opposite value is set to the original map. 1526 /// 1527 /// The simplest way of using this map is through the notWriteMap() 1528 /// function. 1529 /// 1530 /// \sa NotMap 1531 template <typename M> 1228 1532 class NotWriteMap : public MapBase<typename M::Key, bool> { 1229 M &m;1533 M &_m; 1230 1534 public: 1231 1535 typedef MapBase<typename M::Key, bool> Parent; … … 1234 1538 1235 1539 /// Constructor 1236 NotWriteMap(M &_m) : m(_m) {}; 1237 ///\e 1238 Value operator[](Key k) const {return !m[k];} 1239 ///\e 1240 void set(Key k, bool v) { m.set(k, !v); } 1241 }; 1242 1243 ///Returns a \c NotMap class 1244 1245 ///This function just returns a \c NotMap class. 1246 ///\relates NotMap 1247 template <typename M> 1540 NotWriteMap(M &m) : _m(m) {} 1541 /// \e 1542 Value operator[](const Key &k) const { return !_m[k]; } 1543 /// \e 1544 void set(const Key &k, bool v) { _m.set(k, !v); } 1545 }; 1546 1547 /// Returns a \ref NotMap class 1548 1549 /// This function just returns a \ref NotMap class. 1550 /// 1551 /// For example, if \c m is a map with \c bool values, then 1552 /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>. 1553 /// 1554 /// \relates NotMap 1555 template <typename M> 1248 1556 inline NotMap<M> notMap(const M &m) { 1249 1557 return NotMap<M>(m); 1250 1558 } 1251 1252 ///Returns a \c NotWriteMap class 1253 1254 ///This function just returns a \c NotWriteMap class. 1255 ///\relates NotWriteMap 1256 template <typename M> 1257 inline NotWriteMap<M> notMap(M &m) { 1559 1560 /// Returns a \ref NotWriteMap class 1561 1562 /// This function just returns a \ref NotWriteMap class. 1563 /// 1564 /// For example, if \c m is a map with \c bool values, then 1565 /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>. 1566 /// Moreover it makes also possible to write the map. 1567 /// 1568 /// \relates NotWriteMap 1569 template <typename M> 1570 inline NotWriteMap<M> notWriteMap(M &m) { 1258 1571 return NotWriteMap<M>(m); 1572 } 1573 1574 1575 /// Combination of two maps using the \c == operator 1576 1577 /// This \ref concepts::ReadMap "read-only map" assigns \c true to 1578 /// the keys for which the corresponding values of the two maps are 1579 /// equal. 1580 /// Its \c Key type is inherited from \c M1 and its \c Value type is 1581 /// \c bool. \c M2::Key must be convertible to \c M1::Key. 1582 /// 1583 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for 1584 /// \code 1585 /// EqualMap<M1,M2> em(m1,m2); 1586 /// \endcode 1587 /// <tt>em[x]</tt> will be equal to <tt>m1[x]==m2[x]</tt>. 1588 /// 1589 /// The simplest way of using this map is through the equalMap() 1590 /// function. 1591 /// 1592 /// \sa LessMap 1593 template<typename M1, typename M2> 1594 class EqualMap : public MapBase<typename M1::Key, bool> { 1595 const M1 &_m1; 1596 const M2 &_m2; 1597 public: 1598 typedef MapBase<typename M1::Key, bool> Parent; 1599 typedef typename Parent::Key Key; 1600 typedef typename Parent::Value Value; 1601 1602 /// Constructor 1603 EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 1604 /// \e 1605 Value operator[](const Key &k) const { return _m1[k]==_m2[k]; } 1606 }; 1607 1608 /// Returns an \ref EqualMap class 1609 1610 /// This function just returns an \ref EqualMap class. 1611 /// 1612 /// For example, if \c m1 and \c m2 are maps with keys and values of 1613 /// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to 1614 /// <tt>m1[x]==m2[x]</tt>. 1615 /// 1616 /// \relates EqualMap 1617 template<typename M1, typename M2> 1618 inline EqualMap<M1, M2> equalMap(const M1 &m1, const M2 &m2) { 1619 return EqualMap<M1, M2>(m1,m2); 1620 } 1621 1622 1623 /// Combination of two maps using the \c < operator 1624 1625 /// This \ref concepts::ReadMap "read-only map" assigns \c true to 1626 /// the keys for which the corresponding value of the first map is 1627 /// less then the value of the second map. 1628 /// Its \c Key type is inherited from \c M1 and its \c Value type is 1629 /// \c bool. \c M2::Key must be convertible to \c M1::Key. 1630 /// 1631 /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for 1632 /// \code 1633 /// LessMap<M1,M2> lm(m1,m2); 1634 /// \endcode 1635 /// <tt>lm[x]</tt> will be equal to <tt>m1[x]<m2[x]</tt>. 1636 /// 1637 /// The simplest way of using this map is through the lessMap() 1638 /// function. 1639 /// 1640 /// \sa EqualMap 1641 template<typename M1, typename M2> 1642 class LessMap : public MapBase<typename M1::Key, bool> { 1643 const M1 &_m1; 1644 const M2 &_m2; 1645 public: 1646 typedef MapBase<typename M1::Key, bool> Parent; 1647 typedef typename Parent::Key Key; 1648 typedef typename Parent::Value Value; 1649 1650 /// Constructor 1651 LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {} 1652 /// \e 1653 Value operator[](const Key &k) const { return _m1[k]<_m2[k]; } 1654 }; 1655 1656 /// Returns an \ref LessMap class 1657 1658 /// This function just returns an \ref LessMap class. 1659 /// 1660 /// For example, if \c m1 and \c m2 are maps with keys and values of 1661 /// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to 1662 /// <tt>m1[x]<m2[x]</tt>. 1663 /// 1664 /// \relates LessMap 1665 template<typename M1, typename M2> 1666 inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) { 1667 return LessMap<M1, M2>(m1,m2); 1259 1668 } 1260 1669 … … 1277 1686 template <typename _Iterator> 1278 1687 struct IteratorTraits<_Iterator, 1279 typename exists<typename _Iterator::container_type>::type> 1688 typename exists<typename _Iterator::container_type>::type> 1280 1689 { 1281 1690 typedef typename _Iterator::container_type::value_type Value; … … 1283 1692 1284 1693 } 1285 1286 1694 1287 1695 /// \brief Writable bool map for logging each \c true assigned element 1288 1696 /// 1289 /// A \ref concepts::ReadWriteMap "read-write" bool map for logging 1290 /// each \c true assigned element, i.e it copies all the keys set 1291 /// to \c true to the given iterator. 1292 /// 1293 /// \note The container of the iterator should contain space 1294 /// for each element. 1295 /// 1296 /// The following example shows how you can write the edges found by 1297 /// the \ref Prim algorithm directly to the standard output. 1298 ///\code 1299 /// typedef IdMap<Graph, Edge> EdgeIdMap; 1300 /// EdgeIdMap edgeId(graph); 1301 /// 1302 /// typedef MapFunctor<EdgeIdMap> EdgeIdFunctor; 1303 /// EdgeIdFunctor edgeIdFunctor(edgeId); 1304 /// 1305 /// StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor> 1306 /// writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor); 1307 /// 1308 /// prim(graph, cost, writerMap); 1309 ///\endcode 1310 /// 1311 ///\sa BackInserterBoolMap 1312 ///\sa FrontInserterBoolMap 1313 ///\sa InserterBoolMap 1314 /// 1315 ///\todo Revise the name of this class and the related ones. 1316 template <typename _Iterator, 1317 typename _Functor = 1318 _maps_bits::Identity<typename _maps_bits:: 1319 IteratorTraits<_Iterator>::Value> > 1697 /// A \ref concepts::ReadWriteMap "read-write" bool map for logging 1698 /// each \c true assigned element, i.e it copies subsequently each 1699 /// keys set to \c true to the given iterator. 1700 /// 1701 /// \tparam It the type of the Iterator. 1702 /// \tparam Ke the type of the map's Key. The default value should 1703 /// work in most cases. 1704 /// 1705 /// \note The container of the iterator must contain enough space 1706 /// for the elements. (Or it should be an inserter iterator). 1707 /// 1708 /// \todo Revise the name of this class and give an example code. 1709 template <typename It, 1710 typename Ke=typename _maps_bits::IteratorTraits<It>::Value> 1320 1711 class StoreBoolMap { 1321 1712 public: 1322 typedef _IteratorIterator;1323 1324 typedef typename _Functor::argument_type Key;1713 typedef It Iterator; 1714 1715 typedef Ke Key; 1325 1716 typedef bool Value; 1326 1717 1327 typedef _Functor Functor; 1328 1329 /// Constructor 1330 StoreBoolMap(Iterator it, const Functor& functor = Functor()) 1331 : _begin(it), _end(it), _functor(functor) {} 1718 /// Constructor 1719 StoreBoolMap(Iterator it) 1720 : _begin(it), _end(it) {} 1332 1721 1333 1722 /// Gives back the given iterator set for the first key … … 1335 1724 return _begin; 1336 1725 } 1337 1726 1338 1727 /// Gives back the the 'after the last' iterator 1339 1728 Iterator end() const { … … 1341 1730 } 1342 1731 1343 /// The \cset function of the map1732 /// The set function of the map 1344 1733 void set(const Key& key, Value value) const { 1345 1734 if (value) { 1346 *_end++ = _functor(key);1735 *_end++ = key; 1347 1736 } 1348 1737 } 1349 1738 1350 1739 private: 1351 1740 Iterator _begin; 1352 1741 mutable Iterator _end; 1353 Functor _functor;1354 };1355 1356 /// \brief Writable bool map for logging each \c true assigned element in1357 /// a back insertable container.1358 ///1359 /// Writable bool map for logging each \c true assigned element by pushing1360 /// them into a back insertable container.1361 /// It can be used to retrieve the items into a standard1362 /// container. The next example shows how you can store the1363 /// edges found by the Prim algorithm in a vector.1364 ///1365 ///\code1366 /// vector<Edge> span_tree_edges;1367 /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges);1368 /// prim(graph, cost, inserter_map);1369 ///\endcode1370 ///1371 ///\sa StoreBoolMap1372 ///\sa FrontInserterBoolMap1373 ///\sa InserterBoolMap1374 template <typename Container,1375 typename Functor =1376 _maps_bits::Identity<typename Container::value_type> >1377 class BackInserterBoolMap {1378 public:1379 typedef typename Functor::argument_type Key;1380 typedef bool Value;1381 1382 /// Constructor1383 BackInserterBoolMap(Container& _container,1384 const Functor& _functor = Functor())1385 : container(_container), functor(_functor) {}1386 1387 /// The \c set function of the map1388 void set(const Key& key, Value value) {1389 if (value) {1390 container.push_back(functor(key));1391 }1392 }1393 1394 private:1395 Container& container;1396 Functor functor;1397 };1398 1399 /// \brief Writable bool map for logging each \c true assigned element in1400 /// a front insertable container.1401 ///1402 /// Writable bool map for logging each \c true assigned element by pushing1403 /// them into a front insertable container.1404 /// It can be used to retrieve the items into a standard1405 /// container. For example see \ref BackInserterBoolMap.1406 ///1407 ///\sa BackInserterBoolMap1408 ///\sa InserterBoolMap1409 template <typename Container,1410 typename Functor =1411 _maps_bits::Identity<typename Container::value_type> >1412 class FrontInserterBoolMap {1413 public:1414 typedef typename Functor::argument_type Key;1415 typedef bool Value;1416 1417 /// Constructor1418 FrontInserterBoolMap(Container& _container,1419 const Functor& _functor = Functor())1420 : container(_container), functor(_functor) {}1421 1422 /// The \c set function of the map1423 void set(const Key& key, Value value) {1424 if (value) {1425 container.push_front(functor(key));1426 }1427 }1428 1429 private:1430 Container& container;1431 Functor functor;1432 };1433 1434 /// \brief Writable bool map for storing each \c true assigned element in1435 /// an insertable container.1436 ///1437 /// Writable bool map for storing each \c true assigned element in an1438 /// insertable container. It will insert all the keys set to \c true into1439 /// the container.1440 ///1441 /// For example, if you want to store the cut arcs of the strongly1442 /// connected components in a set you can use the next code:1443 ///1444 ///\code1445 /// set<Arc> cut_arcs;1446 /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs);1447 /// stronglyConnectedCutArcs(digraph, cost, inserter_map);1448 ///\endcode1449 ///1450 ///\sa BackInserterBoolMap1451 ///\sa FrontInserterBoolMap1452 template <typename Container,1453 typename Functor =1454 _maps_bits::Identity<typename Container::value_type> >1455 class InserterBoolMap {1456 public:1457 typedef typename Container::value_type Key;1458 typedef bool Value;1459 1460 /// Constructor with specified iterator1461 1462 /// Constructor with specified iterator.1463 /// \param _container The container for storing the elements.1464 /// \param _it The elements will be inserted before this iterator.1465 /// \param _functor The functor that is used when an element is stored.1466 InserterBoolMap(Container& _container, typename Container::iterator _it,1467 const Functor& _functor = Functor())1468 : container(_container), it(_it), functor(_functor) {}1469 1470 /// Constructor1471 1472 /// Constructor without specified iterator.1473 /// The elements will be inserted before <tt>_container.end()</tt>.1474 /// \param _container The container for storing the elements.1475 /// \param _functor The functor that is used when an element is stored.1476 InserterBoolMap(Container& _container, const Functor& _functor = Functor())1477 : container(_container), it(_container.end()), functor(_functor) {}1478 1479 /// The \c set function of the map1480 void set(const Key& key, Value value) {1481 if (value) {1482 it = container.insert(it, functor(key));1483 ++it;1484 }1485 }1486 1487 private:1488 Container& container;1489 typename Container::iterator it;1490 Functor functor;1491 };1492 1493 /// \brief Writable bool map for filling each \c true assigned element with a1494 /// given value.1495 ///1496 /// Writable bool map for filling each \c true assigned element with a1497 /// given value. The value can set the container.1498 ///1499 /// The following code finds the connected components of a graph1500 /// and stores it in the \c comp map:1501 ///\code1502 /// typedef Graph::NodeMap<int> ComponentMap;1503 /// ComponentMap comp(graph);1504 /// typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap;1505 /// ComponentFillerMap filler(comp, 0);1506 ///1507 /// Dfs<Graph>::DefProcessedMap<ComponentFillerMap>::Create dfs(graph);1508 /// dfs.processedMap(filler);1509 /// dfs.init();1510 /// for (NodeIt it(graph); it != INVALID; ++it) {1511 /// if (!dfs.reached(it)) {1512 /// dfs.addSource(it);1513 /// dfs.start();1514 /// ++filler.fillValue();1515 /// }1516 /// }1517 ///\endcode1518 template <typename Map>1519 class FillBoolMap {1520 public:1521 typedef typename Map::Key Key;1522 typedef bool Value;1523 1524 /// Constructor1525 FillBoolMap(Map& _map, const typename Map::Value& _fill)1526 : map(_map), fill(_fill) {}1527 1528 /// Constructor1529 FillBoolMap(Map& _map)1530 : map(_map), fill() {}1531 1532 /// Gives back the current fill value1533 const typename Map::Value& fillValue() const {1534 return fill;1535 }1536 1537 /// Gives back the current fill value1538 typename Map::Value& fillValue() {1539 return fill;1540 }1541 1542 /// Sets the current fill value1543 void fillValue(const typename Map::Value& _fill) {1544 fill = _fill;1545 }1546 1547 /// The \c set function of the map1548 void set(const Key& key, Value value) {1549 if (value) {1550 map.set(key, fill);1551 }1552 }1553 1554 private:1555 Map& map;1556 typename Map::Value fill;1557 };1558 1559 1560 /// \brief Writable bool map for storing the sequence number of1561 /// \c true assignments.1562 ///1563 /// Writable bool map that stores for each \c true assigned elements1564 /// the sequence number of this setting.1565 /// It makes it easy to calculate the leaving1566 /// order of the nodes in the \c Dfs algorithm.1567 ///1568 ///\code1569 /// typedef Digraph::NodeMap<int> OrderMap;1570 /// OrderMap order(digraph);1571 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;1572 /// OrderSetterMap setter(order);1573 /// Dfs<Digraph>::DefProcessedMap<OrderSetterMap>::Create dfs(digraph);1574 /// dfs.processedMap(setter);1575 /// dfs.init();1576 /// for (NodeIt it(digraph); it != INVALID; ++it) {1577 /// if (!dfs.reached(it)) {1578 /// dfs.addSource(it);1579 /// dfs.start();1580 /// }1581 /// }1582 ///\endcode1583 ///1584 /// The storing of the discovering order is more difficult because the1585 /// ReachedMap should be readable in the dfs algorithm but the setting1586 /// order map is not readable. Thus we must use the fork map:1587 ///1588 ///\code1589 /// typedef Digraph::NodeMap<int> OrderMap;1590 /// OrderMap order(digraph);1591 /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;1592 /// OrderSetterMap setter(order);1593 /// typedef Digraph::NodeMap<bool> StoreMap;1594 /// StoreMap store(digraph);1595 ///1596 /// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap;1597 /// ReachedMap reached(store, setter);1598 ///1599 /// Dfs<Digraph>::DefReachedMap<ReachedMap>::Create dfs(digraph);1600 /// dfs.reachedMap(reached);1601 /// dfs.init();1602 /// for (NodeIt it(digraph); it != INVALID; ++it) {1603 /// if (!dfs.reached(it)) {1604 /// dfs.addSource(it);1605 /// dfs.start();1606 /// }1607 /// }1608 ///\endcode1609 template <typename Map>1610 class SettingOrderBoolMap {1611 public:1612 typedef typename Map::Key Key;1613 typedef bool Value;1614 1615 /// Constructor1616 SettingOrderBoolMap(Map& _map)1617 : map(_map), counter(0) {}1618 1619 /// Number of set operations.1620 int num() const {1621 return counter;1622 }1623 1624 /// The \c set function of the map1625 void set(const Key& key, Value value) {1626 if (value) {1627 map.set(key, counter++);1628 }1629 }1630 1631 private:1632 Map& map;1633 int counter;1634 1742 }; 1635 1743 -
lemon/random.h
r68 r102 576 576 } 577 577 578 /// \brief Seeding random sequence 579 /// 580 /// Seeding the random sequence. The current number type will be 581 /// converted to the architecture word type. 582 template <typename Number> 583 void seed(Number seed) { 584 _random_bits::Initializer<Number, Word>::init(core, seed); 585 } 586 587 /// \brief Seeding random sequence 588 /// 589 /// Seeding the random sequence. The given range should contain 590 /// any number type and the numbers will be converted to the 591 /// architecture word type. 592 template <typename Iterator> 593 void seed(Iterator begin, Iterator end) { 594 typedef typename std::iterator_traits<Iterator>::value_type Number; 595 _random_bits::Initializer<Number, Word>::init(core, begin, end); 596 } 597 578 598 /// \brief Returns a random real number from the range [0, 1) 579 599 /// … … 804 824 } 805 825 826 /// Poisson distribution 827 828 /// This function generates a Poisson distribution random number with 829 /// parameter \c lambda. 830 /// 831 /// The probability mass function of this distribusion is 832 /// \f[ \frac{e^{-\lambda}\lambda^k}{k!} \f] 833 /// \note The algorithm is taken from the book of Donald E. Knuth titled 834 /// ''Seminumerical Algorithms'' (1969). Its running time is linear in the 835 /// return value. 836 837 int poisson(double lambda) 838 { 839 const double l = std::exp(-lambda); 840 int k=0; 841 double p = 1.0; 842 do { 843 k++; 844 p*=real<double>(); 845 } while (p>=l); 846 return k-1; 847 } 848 806 849 ///@} 807 850 -
test/Makefile.am
r103 r106 4 4 noinst_HEADERS += \ 5 5 test/digraph_test.h \ 6 test/heap_test.h \ 6 7 test/map_test.h \ 7 8 test/test_tools.h 8 9 9 10 check_PROGRAMS += \ 11 test/bfs_test \ 12 test/dfs_test \ 10 13 test/digraph_test \ 11 14 test/dim_test \ … … 14 17 test/maps_test \ 15 18 test/random_test \ 19 test/path_test \ 16 20 test/test_tools_fail \ 17 21 test/test_tools_pass \ … … 21 25 XFAIL_TESTS += test/test_tools_fail$(EXEEXT) 22 26 27 test_bfs_test_SOURCES = test/bfs_test.cc 28 test_dfs_test_SOURCES = test/dfs_test.cc 23 29 test_digraph_test_SOURCES = test/digraph_test.cc 24 30 test_dim_test_SOURCES = test/dim_test.cc 25 31 #test_error_test_SOURCES = test/error_test.cc 26 32 test_graph_test_SOURCES = test/graph_test.cc 33 # test_heap_test_SOURCES = test/heap_test.cc 27 34 test_kruskal_test_SOURCES = test/kruskal_test.cc 28 35 test_maps_test_SOURCES = test/maps_test.cc 36 test_path_test_SOURCES = test/path_test.cc 29 37 test_random_test_SOURCES = test/random_test.cc 30 38 test_test_tools_fail_SOURCES = test/test_tools_fail.cc -
test/maps_test.cc
r39 r94 32 32 inline bool operator<(A, A) { return true; } 33 33 struct B {}; 34 35 class C { 36 int x; 37 public: 38 C(int _x) : x(_x) {} 39 }; 34 40 35 41 class F { … … 38 44 typedef B result_type; 39 45 40 B operator()(const A &) const {return B();} 46 B operator()(const A&) const { return B(); } 47 private: 48 F& operator=(const F&); 41 49 }; 42 50 43 int func(A) {return 3;} 44 45 int binc(int, B) {return 4;} 46 47 typedef ReadMap<A,double> DoubleMap; 48 typedef ReadWriteMap<A, double> WriteDoubleMap; 49 50 typedef ReadMap<A,bool> BoolMap; 51 int func(A) { return 3; } 52 53 int binc(int a, B) { return a+1; } 54 55 typedef ReadMap<A, double> DoubleMap; 56 typedef ReadWriteMap<A, double> DoubleWriteMap; 57 typedef ReferenceMap<A, double, double&, const double&> DoubleRefMap; 58 59 typedef ReadMap<A, bool> BoolMap; 51 60 typedef ReadWriteMap<A, bool> BoolWriteMap; 61 typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap; 52 62 53 63 int main() 54 { // checking graph components55 64 { 65 // Map concepts 56 66 checkConcept<ReadMap<A,B>, ReadMap<A,B> >(); 67 checkConcept<ReadMap<A,C>, ReadMap<A,C> >(); 57 68 checkConcept<WriteMap<A,B>, WriteMap<A,B> >(); 69 checkConcept<WriteMap<A,C>, WriteMap<A,C> >(); 58 70 checkConcept<ReadWriteMap<A,B>, ReadWriteMap<A,B> >(); 71 checkConcept<ReadWriteMap<A,C>, ReadWriteMap<A,C> >(); 59 72 checkConcept<ReferenceMap<A,B,B&,const B&>, ReferenceMap<A,B,B&,const B&> >(); 60 61 checkConcept<ReadMap<A,double>, AddMap<DoubleMap,DoubleMap> >(); 62 checkConcept<ReadMap<A,double>, SubMap<DoubleMap,DoubleMap> >(); 63 checkConcept<ReadMap<A,double>, MulMap<DoubleMap,DoubleMap> >(); 64 checkConcept<ReadMap<A,double>, DivMap<DoubleMap,DoubleMap> >(); 65 checkConcept<ReadMap<A,double>, NegMap<DoubleMap> >(); 66 checkConcept<ReadWriteMap<A,double>, NegWriteMap<WriteDoubleMap> >(); 67 checkConcept<ReadMap<A,double>, AbsMap<DoubleMap> >(); 68 checkConcept<ReadMap<A,double>, ShiftMap<DoubleMap> >(); 69 checkConcept<ReadWriteMap<A,double>, ShiftWriteMap<WriteDoubleMap> >(); 70 checkConcept<ReadMap<A,double>, ScaleMap<DoubleMap> >(); 71 checkConcept<ReadWriteMap<A,double>, ScaleWriteMap<WriteDoubleMap> >(); 72 checkConcept<ReadMap<A,double>, ForkMap<DoubleMap, DoubleMap> >(); 73 checkConcept<ReadWriteMap<A,double>, 74 ForkWriteMap<WriteDoubleMap, WriteDoubleMap> >(); 75 76 checkConcept<ReadMap<B,double>, ComposeMap<DoubleMap,ReadMap<B,A> > >(); 77 78 checkConcept<ReadMap<A,B>, FunctorMap<F, A, B> >(); 79 80 checkConcept<ReadMap<A, bool>, NotMap<BoolMap> >(); 81 checkConcept<ReadWriteMap<A, bool>, NotWriteMap<BoolWriteMap> >(); 82 83 checkConcept<WriteMap<A, bool>, StoreBoolMap<A*> >(); 84 checkConcept<WriteMap<A, bool>, BackInserterBoolMap<std::deque<A> > >(); 85 checkConcept<WriteMap<A, bool>, FrontInserterBoolMap<std::deque<A> > >(); 86 checkConcept<WriteMap<A, bool>, InserterBoolMap<std::set<A> > >(); 87 checkConcept<WriteMap<A, bool>, FillBoolMap<WriteMap<A, B> > >(); 88 checkConcept<WriteMap<A, bool>, SettingOrderBoolMap<WriteMap<A, int> > >(); 89 90 int a; 91 92 a=mapFunctor(constMap<A,int>(2))(A()); 93 check(a==2,"Something is wrong with mapFunctor"); 94 95 B b; 96 b=functorMap(F())[A()]; 97 98 a=functorMap(&func)[A()]; 99 check(a==3,"Something is wrong with functorMap"); 100 101 a=combineMap(constMap<B, int, 1>(), identityMap<B>(), &binc)[B()]; 102 check(a==4,"Something is wrong with combineMap"); 103 104 105 std::cout << __FILE__ ": All tests passed.\n"; 106 73 checkConcept<ReferenceMap<A,C,C&,const C&>, ReferenceMap<A,C,C&,const C&> >(); 74 75 // NullMap 76 { 77 checkConcept<ReadWriteMap<A,B>, NullMap<A,B> >(); 78 NullMap<A,B> map1; 79 NullMap<A,B> map2 = map1; 80 map1 = nullMap<A,B>(); 81 } 82 83 // ConstMap 84 { 85 checkConcept<ReadWriteMap<A,B>, ConstMap<A,B> >(); 86 ConstMap<A,B> map1; 87 ConstMap<A,B> map2(B()); 88 ConstMap<A,B> map3 = map1; 89 map1 = constMap<A>(B()); 90 map1.setAll(B()); 91 92 checkConcept<ReadWriteMap<A,int>, ConstMap<A,int> >(); 93 check(constMap<A>(10)[A()] == 10, "Something is wrong with ConstMap"); 94 95 checkConcept<ReadWriteMap<A,int>, ConstMap<A,Const<int,10> > >(); 96 ConstMap<A,Const<int,10> > map4; 97 ConstMap<A,Const<int,10> > map5 = map4; 98 map4 = map5; 99 check(map4[A()] == 10 && map5[A()] == 10, "Something is wrong with ConstMap"); 100 } 101 102 // IdentityMap 103 { 104 checkConcept<ReadMap<A,A>, IdentityMap<A> >(); 105 IdentityMap<A> map1; 106 IdentityMap<A> map2 = map1; 107 map1 = identityMap<A>(); 108 109 checkConcept<ReadMap<double,double>, IdentityMap<double> >(); 110 check(identityMap<double>()[1.0] == 1.0 && identityMap<double>()[3.14] == 3.14, 111 "Something is wrong with IdentityMap"); 112 } 113 114 // RangeMap 115 { 116 checkConcept<ReferenceMap<int,B,B&,const B&>, RangeMap<B> >(); 117 RangeMap<B> map1; 118 RangeMap<B> map2(10); 119 RangeMap<B> map3(10,B()); 120 RangeMap<B> map4 = map1; 121 RangeMap<B> map5 = rangeMap<B>(); 122 RangeMap<B> map6 = rangeMap<B>(10); 123 RangeMap<B> map7 = rangeMap(10,B()); 124 125 checkConcept< ReferenceMap<int, double, double&, const double&>, 126 RangeMap<double> >(); 127 std::vector<double> v(10, 0); 128 v[5] = 100; 129 RangeMap<double> map8(v); 130 RangeMap<double> map9 = rangeMap(v); 131 check(map9.size() == 10 && map9[2] == 0 && map9[5] == 100, 132 "Something is wrong with RangeMap"); 133 } 134 135 // SparseMap 136 { 137 checkConcept<ReferenceMap<A,B,B&,const B&>, SparseMap<A,B> >(); 138 SparseMap<A,B> map1; 139 SparseMap<A,B> map2(B()); 140 SparseMap<A,B> map3 = sparseMap<A,B>(); 141 SparseMap<A,B> map4 = sparseMap<A>(B()); 142 143 checkConcept< ReferenceMap<double, int, int&, const int&>, 144 SparseMap<double, int> >(); 145 std::map<double, int> m; 146 SparseMap<double, int> map5(m); 147 SparseMap<double, int> map6(m,10); 148 SparseMap<double, int> map7 = sparseMap(m); 149 SparseMap<double, int> map8 = sparseMap(m,10); 150 151 check(map5[1.0] == 0 && map5[3.14] == 0 && map6[1.0] == 10 && map6[3.14] == 10, 152 "Something is wrong with SparseMap"); 153 map5[1.0] = map6[3.14] = 100; 154 check(map5[1.0] == 100 && map5[3.14] == 0 && map6[1.0] == 10 && map6[3.14] == 100, 155 "Something is wrong with SparseMap"); 156 } 157 158 // ComposeMap 159 { 160 typedef ComposeMap<DoubleMap, ReadMap<B,A> > CompMap; 161 checkConcept<ReadMap<B,double>, CompMap>(); 162 CompMap map1(DoubleMap(),ReadMap<B,A>()); 163 CompMap map2 = composeMap(DoubleMap(), ReadMap<B,A>()); 164 165 SparseMap<double, bool> m1(false); m1[3.14] = true; 166 RangeMap<double> m2(2); m2[0] = 3.0; m2[1] = 3.14; 167 check(!composeMap(m1,m2)[0] && composeMap(m1,m2)[1], "Something is wrong with ComposeMap") 168 } 169 170 // CombineMap 171 { 172 typedef CombineMap<DoubleMap, DoubleMap, std::plus<double> > CombMap; 173 checkConcept<ReadMap<A,double>, CombMap>(); 174 CombMap map1(DoubleMap(), DoubleMap()); 175 CombMap map2 = combineMap(DoubleMap(), DoubleMap(), std::plus<double>()); 176 177 check(combineMap(constMap<B,int,2>(), identityMap<B>(), &binc)[B()] == 3, 178 "Something is wrong with CombineMap"); 179 } 180 181 // FunctorToMap, MapToFunctor 182 { 183 checkConcept<ReadMap<A,B>, FunctorToMap<F,A,B> >(); 184 checkConcept<ReadMap<A,B>, FunctorToMap<F> >(); 185 FunctorToMap<F> map1; 186 FunctorToMap<F> map2(F()); 187 B b = functorToMap(F())[A()]; 188 189 checkConcept<ReadMap<A,B>, MapToFunctor<ReadMap<A,B> > >(); 190 MapToFunctor<ReadMap<A,B> > map(ReadMap<A,B>()); 191 192 check(functorToMap(&func)[A()] == 3, "Something is wrong with FunctorToMap"); 193 check(mapToFunctor(constMap<A,int>(2))(A()) == 2, "Something is wrong with MapToFunctor"); 194 check(mapToFunctor(functorToMap(&func))(A()) == 3 && mapToFunctor(functorToMap(&func))[A()] == 3, 195 "Something is wrong with FunctorToMap or MapToFunctor"); 196 check(functorToMap(mapToFunctor(constMap<A,int>(2)))[A()] == 2, 197 "Something is wrong with FunctorToMap or MapToFunctor"); 198 } 199 200 // ConvertMap 201 { 202 checkConcept<ReadMap<double,double>, ConvertMap<ReadMap<double, int>, double> >(); 203 ConvertMap<RangeMap<bool>, int> map1(rangeMap(1, true)); 204 ConvertMap<RangeMap<bool>, int> map2 = convertMap<int>(rangeMap(2, false)); 205 } 206 207 // ForkMap 208 { 209 checkConcept<DoubleWriteMap, ForkMap<DoubleWriteMap, DoubleWriteMap> >(); 210 211 typedef RangeMap<double> RM; 212 typedef SparseMap<int, double> SM; 213 RM m1(10, -1); 214 SM m2(-1); 215 checkConcept<ReadWriteMap<int, double>, ForkMap<RM, SM> >(); 216 checkConcept<ReadWriteMap<int, double>, ForkMap<SM, RM> >(); 217 ForkMap<RM, SM> map1(m1,m2); 218 ForkMap<SM, RM> map2 = forkMap(m2,m1); 219 map2.set(5, 10); 220 check(m1[1] == -1 && m1[5] == 10 && m2[1] == -1 && m2[5] == 10 && map2[1] == -1 && map2[5] == 10, 221 "Something is wrong with ForkMap"); 222 } 223 224 // Arithmetic maps: 225 // - AddMap, SubMap, MulMap, DivMap 226 // - ShiftMap, ShiftWriteMap, ScaleMap, ScaleWriteMap 227 // - NegMap, NegWriteMap, AbsMap 228 { 229 checkConcept<DoubleMap, AddMap<DoubleMap,DoubleMap> >(); 230 checkConcept<DoubleMap, SubMap<DoubleMap,DoubleMap> >(); 231 checkConcept<DoubleMap, MulMap<DoubleMap,DoubleMap> >(); 232 checkConcept<DoubleMap, DivMap<DoubleMap,DoubleMap> >(); 233 234 ConstMap<int, double> c1(1.0), c2(3.14); 235 IdentityMap<int> im; 236 ConvertMap<IdentityMap<int>, double> id(im); 237 check(addMap(c1,id)[0] == 1.0 && addMap(c1,id)[10] == 11.0, "Something is wrong with AddMap"); 238 check(subMap(id,c1)[0] == -1.0 && subMap(id,c1)[10] == 9.0, "Something is wrong with SubMap"); 239 check(mulMap(id,c2)[0] == 0 && mulMap(id,c2)[2] == 6.28, "Something is wrong with MulMap"); 240 check(divMap(c2,id)[1] == 3.14 && divMap(c2,id)[2] == 1.57, "Something is wrong with DivMap"); 241 242 checkConcept<DoubleMap, ShiftMap<DoubleMap> >(); 243 checkConcept<DoubleWriteMap, ShiftWriteMap<DoubleWriteMap> >(); 244 checkConcept<DoubleMap, ScaleMap<DoubleMap> >(); 245 checkConcept<DoubleWriteMap, ScaleWriteMap<DoubleWriteMap> >(); 246 checkConcept<DoubleMap, NegMap<DoubleMap> >(); 247 checkConcept<DoubleWriteMap, NegWriteMap<DoubleWriteMap> >(); 248 checkConcept<DoubleMap, AbsMap<DoubleMap> >(); 249 250 check(shiftMap(id, 2.0)[1] == 3.0 && shiftMap(id, 2.0)[10] == 12.0, 251 "Something is wrong with ShiftMap"); 252 check(shiftWriteMap(id, 2.0)[1] == 3.0 && shiftWriteMap(id, 2.0)[10] == 12.0, 253 "Something is wrong with ShiftWriteMap"); 254 check(scaleMap(id, 2.0)[1] == 2.0 && scaleMap(id, 2.0)[10] == 20.0, 255 "Something is wrong with ScaleMap"); 256 check(scaleWriteMap(id, 2.0)[1] == 2.0 && scaleWriteMap(id, 2.0)[10] == 20.0, 257 "Something is wrong with ScaleWriteMap"); 258 check(negMap(id)[1] == -1.0 && negMap(id)[-10] == 10.0, 259 "Something is wrong with NegMap"); 260 check(negWriteMap(id)[1] == -1.0 && negWriteMap(id)[-10] == 10.0, 261 "Something is wrong with NegWriteMap"); 262 check(absMap(id)[1] == 1.0 && absMap(id)[-10] == 10.0, 263 "Something is wrong with AbsMap"); 264 } 265 266 // Logical maps: 267 // - TrueMap, FalseMap 268 // - AndMap, OrMap 269 // - NotMap, NotWriteMap 270 // - EqualMap, LessMap 271 { 272 checkConcept<BoolMap, TrueMap<A> >(); 273 checkConcept<BoolMap, FalseMap<A> >(); 274 checkConcept<BoolMap, AndMap<BoolMap,BoolMap> >(); 275 checkConcept<BoolMap, OrMap<BoolMap,BoolMap> >(); 276 checkConcept<BoolMap, NotMap<BoolMap> >(); 277 checkConcept<BoolWriteMap, NotWriteMap<BoolWriteMap> >(); 278 checkConcept<BoolMap, EqualMap<DoubleMap,DoubleMap> >(); 279 checkConcept<BoolMap, LessMap<DoubleMap,DoubleMap> >(); 280 281 TrueMap<int> tm; 282 FalseMap<int> fm; 283 RangeMap<bool> rm(2); 284 rm[0] = true; rm[1] = false; 285 check(andMap(tm,rm)[0] && !andMap(tm,rm)[1] && !andMap(fm,rm)[0] && !andMap(fm,rm)[1], 286 "Something is wrong with AndMap"); 287 check(orMap(tm,rm)[0] && orMap(tm,rm)[1] && orMap(fm,rm)[0] && !orMap(fm,rm)[1], 288 "Something is wrong with OrMap"); 289 check(!notMap(rm)[0] && notMap(rm)[1], "Something is wrong with NotMap"); 290 check(!notWriteMap(rm)[0] && notWriteMap(rm)[1], "Something is wrong with NotWriteMap"); 291 292 ConstMap<int, double> cm(2.0); 293 IdentityMap<int> im; 294 ConvertMap<IdentityMap<int>, double> id(im); 295 check(lessMap(id,cm)[1] && !lessMap(id,cm)[2] && !lessMap(id,cm)[3], 296 "Something is wrong with LessMap"); 297 check(!equalMap(id,cm)[1] && equalMap(id,cm)[2] && !equalMap(id,cm)[3], 298 "Something is wrong with EqualMap"); 299 } 300 107 301 return 0; 108 302 } -
test/random_test.cc
r39 r102 25 25 /// 26 26 27 int seed_array[] = {1, 2}; 28 27 29 int main() 28 30 { … … 34 36 //Does gamma work with integer k? 35 37 a=lemon::rnd.gamma(4.0,0); 38 a=lemon::rnd.poisson(.5); 39 40 lemon::rnd.seed(100); 41 lemon::rnd.seed(seed_array, seed_array + 42 (sizeof(seed_array) / sizeof(seed_array[0]))); 43 44 return 0; 36 45 } -
test/test_tools.h
r39 r100 21 21 22 22 #include <iostream> 23 #include <vector> 24 25 #include <cstdlib> 26 #include <ctime> 27 28 #include <lemon/concept_check.h> 29 #include <lemon/concepts/digraph.h> 30 31 #include <lemon/random.h> 32 33 using namespace lemon; 23 34 24 35 //! \ingroup misc … … 37 48 ///\code check(0==1,"This is obviously false.");\endcode will 38 49 ///print this (and then exits). 39 ///\verbatim graph_test.cc:123: error: This is obviously false. \endverbatim50 ///\verbatim digraph_test.cc:123: error: This is obviously false. \endverbatim 40 51 /// 41 52 ///\todo It should be in \c error.h … … 46 57 } else { } \ 47 58 59 ///Structure returned by \ref addPetersen(). 60 61 ///Structure returned by \ref addPetersen(). 62 /// 63 template<class Digraph> struct PetStruct 64 { 65 ///Vector containing the outer nodes. 66 std::vector<typename Digraph::Node> outer; 67 ///Vector containing the inner nodes. 68 std::vector<typename Digraph::Node> inner; 69 ///Vector containing the arcs of the inner circle. 70 std::vector<typename Digraph::Arc> incir; 71 ///Vector containing the arcs of the outer circle. 72 std::vector<typename Digraph::Arc> outcir; 73 ///Vector containing the chord arcs. 74 std::vector<typename Digraph::Arc> chords; 75 }; 76 77 78 79 ///Adds a Petersen digraph to \c G. 80 81 ///Adds a Petersen digraph to \c G. 82 ///\return The nodes and arcs of the generated digraph. 83 84 template<typename Digraph> 85 PetStruct<Digraph> addPetersen(Digraph &G,int num = 5) 86 { 87 PetStruct<Digraph> n; 88 89 for(int i=0;i<num;i++) { 90 n.outer.push_back(G.addNode()); 91 n.inner.push_back(G.addNode()); 92 } 93 94 for(int i=0;i<num;i++) { 95 n.chords.push_back(G.addArc(n.outer[i],n.inner[i])); 96 n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num])); 97 n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num])); 98 } 99 return n; 100 } 101 102 /// \brief Adds to the digraph the reverse pair of all arcs. 103 /// 104 /// Adds to the digraph the reverse pair of all arcs. 105 /// 106 template<class Digraph> void bidirDigraph(Digraph &G) 107 { 108 typedef typename Digraph::Arc Arc; 109 typedef typename Digraph::ArcIt ArcIt; 110 111 std::vector<Arc> ee; 112 113 for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e); 114 115 for(typename std::vector<Arc>::iterator p=ee.begin();p!=ee.end();p++) 116 G.addArc(G.target(*p),G.source(*p)); 117 } 118 119 120 /// \brief Checks the bidirectioned Petersen digraph. 121 /// 122 /// Checks the bidirectioned Petersen digraph. 123 /// 124 template<class Digraph> void checkBidirPetersen(Digraph &G, int num = 5) 125 { 126 typedef typename Digraph::Node Node; 127 128 typedef typename Digraph::ArcIt ArcIt; 129 typedef typename Digraph::NodeIt NodeIt; 130 131 checkDigraphNodeList(G, 2 * num); 132 checkDigraphArcList(G, 6 * num); 133 134 for(NodeIt n(G);n!=INVALID;++n) { 135 checkDigraphInArcList(G, n, 3); 136 checkDigraphOutArcList(G, n, 3); 137 } 138 } 139 140 ///Structure returned by \ref addUPetersen(). 141 142 ///Structure returned by \ref addUPetersen(). 143 /// 144 template<class Digraph> struct UPetStruct 145 { 146 ///Vector containing the outer nodes. 147 std::vector<typename Digraph::Node> outer; 148 ///Vector containing the inner nodes. 149 std::vector<typename Digraph::Node> inner; 150 ///Vector containing the arcs of the inner circle. 151 std::vector<typename Digraph::Edge> incir; 152 ///Vector containing the arcs of the outer circle. 153 std::vector<typename Digraph::Edge> outcir; 154 ///Vector containing the chord arcs. 155 std::vector<typename Digraph::Edge> chords; 156 }; 157 158 ///Adds a Petersen digraph to the undirected \c G. 159 160 ///Adds a Petersen digraph to the undirected \c G. 161 ///\return The nodes and arcs of the generated digraph. 162 163 template<typename Digraph> 164 UPetStruct<Digraph> addUPetersen(Digraph &G,int num=5) 165 { 166 UPetStruct<Digraph> n; 167 168 for(int i=0;i<num;i++) { 169 n.outer.push_back(G.addNode()); 170 n.inner.push_back(G.addNode()); 171 } 172 173 for(int i=0;i<num;i++) { 174 n.chords.push_back(G.addArc(n.outer[i],n.inner[i])); 175 n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1)%5])); 176 n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2)%5])); 177 } 178 return n; 179 } 180 48 181 #endif
Note: See TracChangeset
for help on using the changeset viewer.