COIN-OR::LEMON - Graph Library

Ignore:
Files:
17 added
15 edited

Legend:

Unmodified
Added
Removed
  • .hgignore

    r9 r85  
    3333^objs.*/.*
    3434^test/[a-z_]*$
     35^demo/.*_demo$
  • configure.ac

    r64 r91  
    1111
    1212AC_PREREQ([2.59])
    13 AC_INIT([LEMON], [lemon_version()], [etik-ol@cs.elte.hu], [lemon])
     13AC_INIT([LEMON], [lemon_version()], [lemon-devel@lemon.cs.elte.hu], [lemon])
    1414AC_CONFIG_AUX_DIR([build-aux])
    1515AC_CONFIG_MACRO_DIR([m4])
  • demo/Makefile.am

    r1 r85  
    44if WANT_DEMO
    55
    6 noinst_PROGRAMS +=
     6noinst_PROGRAMS += \
     7        demo/arg_parser_demo
    78
    89endif WANT_DEMO
     10
     11demo_arg_parser_demo_SOURCES = demo/arg_parser_demo.cc
     12
  • doc/groups.dox

    r71 r83  
    3939the diverging requirements of the possible users.  In order to save on
    4040running time or on memory usage, some structures may fail to provide
    41 some graph features like edge or node deletion.
     41some graph features like arc/edge or node deletion.
    4242
    4343Alteration of standard containers need a very limited number of
     
    4545In the case of graph structures, different operations are needed which do
    4646not 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
     47arcs have to be hidden or the reverse oriented graph have to be used, then
    4848this is the case. It also may happen that in a flow implementation
    4949the residual graph can be accessed by another algorithm, or a node-set
     
    8282@defgroup graph_maps Graph Maps
    8383@ingroup maps
    84 \brief Special Graph-Related Maps.
     84\brief Special graph-related maps.
    8585
    8686This group describes maps that are specifically designed to assign
    87 values to the nodes and edges of graphs.
     87values to the nodes and arcs of graphs.
    8888*/
    8989
     
    9797maps from other maps.
    9898
    99 Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can
    100 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.
     99Most of them are \ref lemon::concepts::ReadMap "read-only maps".
     100They 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.
    103103
    104104The typical usage of this classes is passing implicit maps to
    105105algorithms.  If a function type algorithm is called then the function
    106106type map adaptors can be used comfortable. For example let's see the
    107 usage of map adaptors with the \c graphToEps() function:
     107usage of map adaptors with the \c digraphToEps() function.
    108108\code
    109109  Color nodeColor(int deg) {
     
    117117  }
    118118 
    119   Graph::NodeMap<int> degree_map(graph);
     119  Digraph::NodeMap<int> degree_map(graph);
    120120 
    121   graphToEps(graph, "graph.eps")
     121  digraphToEps(graph, "graph.eps")
    122122    .coords(coords).scaleToA4().undirected()
    123     .nodeColors(composeMap(functorMap(nodeColor), degree_map))
     123    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
    124124    .run();
    125125\endcode
    126 The \c functorMap() function makes an \c int to \c Color map from the
     126The \c functorToMap() function makes an \c int to \c Color map from the
    127127\e nodeColor() function. The \c composeMap() compose the \e degree_map
    128 and the previous created map. The composed map is proper function to
    129 get color of each node.
     128and the previously created map. The composed map is a proper function to
     129get the color of each node.
    130130
    131131The usage with class type algorithms is little bit harder. In this
     
    133133function map adaptors give back temporary objects.
    134134\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;
    143142  TimeMap time(length, speed);
    144143 
    145   Dijkstra<Graph, TimeMap> dijkstra(graph, time);
     144  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
    146145  dijkstra.run(source, target);
    147146\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
     147We have a length map and a maximum speed map on the arcs of a digraph.
     148The minimum time to pass the arc can be calculated as the division of
     149the two maps which can be done implicitly with the \c DivMap template
    152150class. We use the implicit minimum time map as the length map of the
    153151\c Dijkstra algorithm.
     
    316314This group contains algorithm objects and functions to calculate
    317315matchings in graphs and bipartite graphs. The general matching problem is
    318 finding a subset of the edges which does not shares common endpoints.
     316finding a subset of the arcs which does not shares common endpoints.
    319317 
    320318There are several different algorithms for calculate matchings in
  • lemon/Makefile.am

    r103 r106  
    88
    99lemon_libemon_la_SOURCES = \
     10        lemon/arg_parser.cc \
    1011        lemon/base.cc \
    1112        lemon/random.cc
     
    1617
    1718lemon_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 \
    1924        lemon/dim2.h \
    2025        lemon/error.h \
     26        lemon/graph_utils.h \
    2127        lemon/kruskal.h \
    2228        lemon/list_graph.h \
    2329        lemon/maps.h \
    2430        lemon/math.h \
     31        lemon/path.h \
    2532        lemon/random.h \
    2633        lemon/tolerance.h \
     
    3542        lemon/bits/invalid.h \
    3643        lemon/bits/map_extender.h \
     44        lemon/bits/path_dump.h \
    3745        lemon/bits/traits.h \
    3846        lemon/bits/utility.h \
     
    4351        lemon/concepts/digraph.h \
    4452        lemon/concepts/graph.h \
     53        lemon/concepts/heap.h \
    4554        lemon/concepts/maps.h \
     55        lemon/concepts/path.h \
    4656        lemon/concepts/graph_components.h
  • lemon/bits/graph_extender.h

    r77 r78  
    6565    }
    6666
    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);
    7272      else
    7373        return INVALID;
     
    9696
    9797    class NodeIt : public Node {
    98       const Digraph* digraph;
     98      const Digraph* _digraph;
    9999    public:
    100100
     
    103103      NodeIt(Invalid i) : Node(i) { }
    104104
    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) {}
    111111
    112112      NodeIt& operator++() {
    113         digraph->next(*this);
     113        _digraph->next(*this);
    114114        return *this;
    115115      }
     
    119119
    120120    class ArcIt : public Arc {
    121       const Digraph* digraph;
     121      const Digraph* _digraph;
    122122    public:
    123123
     
    126126      ArcIt(Invalid i) : Arc(i) { }
    127127
    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) { }
    134134
    135135      ArcIt& operator++() {
    136         digraph->next(*this);
     136        _digraph->next(*this);
    137137        return *this;
    138138      }
     
    142142
    143143    class OutArcIt : public Arc {
    144       const Digraph* digraph;
     144      const Digraph* _digraph;
    145145    public:
    146146
     
    149149      OutArcIt(Invalid i) : Arc(i) { }
    150150
    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) {}
    158158
    159159      OutArcIt& operator++() {
    160         digraph->nextOut(*this);
     160        _digraph->nextOut(*this);
    161161        return *this;
    162162      }
     
    166166
    167167    class InArcIt : public Arc {
    168       const Digraph* digraph;
     168      const Digraph* _digraph;
    169169    public:
    170170
     
    173173      InArcIt(Invalid i) : Arc(i) { }
    174174
    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) {}
    182182
    183183      InArcIt& operator++() {
    184         digraph->nextIn(*this);
     184        _digraph->nextIn(*this);
    185185        return *this;
    186186      }
     
    191191    ///
    192192    /// 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);
    195195    }
    196196    /// \brief Running node of the iterator
     
    198198    /// Returns the running node (i.e. the target in this case) of the
    199199    /// 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);
    202202    }
    203203
     
    205205    ///
    206206    /// 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);
    209209    }
    210210    /// \brief Running node of the iterator
     
    212212    /// Returns the running node (i.e. the source in this case) of the
    213213    /// 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);
    216216    }
    217217
     
    325325  };
    326326
    327   /// \ingroup graphbits
     327  /// \ingroup _graphbits
    328328  ///
    329329  /// \brief Extender for the Graphs
     
    333333   
    334334    typedef Base Parent;
    335     typedef GraphExtender Digraph;
     335    typedef GraphExtender Graph;
    336336
    337337    typedef True UndirectedTag;
     
    376376    }
    377377
    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));
    380380    }
    381381
    382382    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);
    385385    }
    386386
     
    415415
    416416    class NodeIt : public Node {
    417       const Digraph* digraph;
     417      const Graph* _graph;
    418418    public:
    419419
     
    422422      NodeIt(Invalid i) : Node(i) { }
    423423
    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) {}
    430430
    431431      NodeIt& operator++() {
    432         digraph->next(*this);
     432        _graph->next(*this);
    433433        return *this;
    434434      }
     
    438438
    439439    class ArcIt : public Arc {
    440       const Digraph* digraph;
     440      const Graph* _graph;
    441441    public:
    442442
     
    445445      ArcIt(Invalid i) : Arc(i) { }
    446446
    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) { }
    453453
    454454      ArcIt& operator++() {
    455         digraph->next(*this);
     455        _graph->next(*this);
    456456        return *this;
    457457      }
     
    461461
    462462    class OutArcIt : public Arc {
    463       const Digraph* digraph;
     463      const Graph* _graph;
    464464    public:
    465465
     
    468468      OutArcIt(Invalid i) : Arc(i) { }
    469469
    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) {}
    477477
    478478      OutArcIt& operator++() {
    479         digraph->nextOut(*this);
     479        _graph->nextOut(*this);
    480480        return *this;
    481481      }
     
    485485
    486486    class InArcIt : public Arc {
    487       const Digraph* digraph;
     487      const Graph* _graph;
    488488    public:
    489489
     
    492492      InArcIt(Invalid i) : Arc(i) { }
    493493
    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) {}
    501501
    502502      InArcIt& operator++() {
    503         digraph->nextIn(*this);
     503        _graph->nextIn(*this);
    504504        return *this;
    505505      }
     
    509509
    510510    class EdgeIt : public Parent::Edge {
    511       const Digraph* digraph;
     511      const Graph* _graph;
    512512    public:
    513513
     
    516516      EdgeIt(Invalid i) : Edge(i) { }
    517517
    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) { }
    524524
    525525      EdgeIt& operator++() {
    526         digraph->next(*this);
    527         return *this;
    528       }
    529 
    530     };
    531 
    532     class IncArcIt : public Parent::Edge {
     526        _graph->next(*this);
     527        return *this;
     528      }
     529
     530    };
     531
     532    class IncEdgeIt : public Parent::Edge {
    533533      friend class GraphExtender;
    534       const Digraph* digraph;
    535       bool direction;
    536     public:
    537 
    538       IncArcIt() { }
    539 
    540       IncArcIt(Invalid i) : Edge(i), direction(false) { }
    541 
    542       IncArcIt(const Digraph& _digraph, const Node &n) : digraph(&_digraph) {
    543         _digraph.firstInc(*this, direction, n);
    544       }
    545 
    546       IncArcIt(const Digraph& _digraph, const Edge &ue, const Node &n)
    547         : digraph(&_digraph), Edge(ue) {
    548         direction = (_digraph.source(ue) == n);
    549       }
    550 
    551       IncArcIt& 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);
    553553        return *this;
    554554      }
     
    558558    ///
    559559    /// 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));
    562562    }
    563563    /// \brief Running node of the iterator
     
    565565    /// Returns the running node (ie. the target in this case) of the
    566566    /// 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));
    569569    }
    570570
     
    572572    ///
    573573    /// 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));
    576576    }
    577577    /// \brief Running node of the iterator
     
    579579    /// Returns the running node (ie. the source in this case) of the
    580580    /// 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));
    583583    }
    584584
     
    586586    ///
    587587    /// Returns the base node of the iterator
    588     Node baseNode(const IncArcIt &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);
    590590    }
    591591    /// Running node of the iterator
    592592    ///
    593593    /// Returns the running node of the iterator
    594     Node runningNode(const IncArcIt &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);
    596596    }
    597597
     
    600600    template <typename _Value>
    601601    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) {}
    611611
    612612      NodeMap& operator=(const NodeMap& cmap) {
     
    624624    template <typename _Value>
    625625    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) {}
    635635
    636636      ArcMap& operator=(const ArcMap& cmap) {
     
    648648    template <typename _Value>
    649649    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) {}
    660660
    661661      EdgeMap& operator=(const EdgeMap& cmap) {
     
    696696    }
    697697
    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,
    700700               EdgeRefMap& edgeRef) {
    701       Parent::build(digraph, nodeRef, edgeRef);
     701      Parent::build(graph, nodeRef, edgeRef);
    702702      notifier(Node()).build();
    703703      notifier(Edge()).build();
     
    724724
    725725    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);
    730730      notifier(Edge()).erase(edge);
    731731      Parent::erase(edge);
  • lemon/concepts/graph.h

    r61 r78  
    6464    /// the EdgeMap to map values for the edges. The InArcIt and
    6565    /// OutArcIt iterates on the same edges but with opposite
    66     /// direction. The IncArcIt iterates also on the same edges
     66    /// direction. The IncEdgeIt iterates also on the same edges
    6767    /// as the OutArcIt and InArcIt but it is not convertible to Arc just
    6868    /// to Edge. 
     
    271271      ///\code
    272272      /// int count=0;
    273       /// for(Graph::IncArcIt e(g, n); e!=INVALID; ++e) ++count;
     273      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
    274274      ///\endcode
    275       class IncArcIt : public Edge {
    276       public:
    277         /// Default constructor
    278 
    279         /// @warning The default constructor sets the iterator
    280         /// to an undefined value.
    281         IncArcIt() { }
    282         /// Copy constructor.
    283 
    284         /// Copy constructor.
    285         ///
    286         IncArcIt(const IncArcIt& e) : Edge(e) { }
    287         /// Initialize the iterator to be invalid.
    288 
    289         /// Initialize the iterator to be invalid.
    290         ///
    291         IncArcIt(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) { }
    292292        /// This constructor sets the iterator to first incident arc.
    293293   
    294294        /// This constructor set the iterator to the first incident arc of
    295295        /// the node.
    296         IncArcIt(const Graph&, const Node&) { }
    297         /// Edge -> IncArcIt conversion
     296        IncEdgeIt(const Graph&, const Node&) { }
     297        /// Edge -> IncEdgeIt conversion
    298298
    299299        /// Sets the iterator to the value of the trivial iterator \c e.
    300300        /// This feature necessitates that each time we
    301301        /// iterate the arc-set, the iteration order is the same.
    302         IncArcIt(const Graph&, const Edge&) { }
     302        IncEdgeIt(const Graph&, const Edge&) { }
    303303        /// Next incident arc
    304304
    305305        /// Assign the iterator to the next incident arc
    306306        /// of the corresponding node.
    307         IncArcIt& operator++() { return *this; }
     307        IncEdgeIt& operator++() { return *this; }
    308308      };
    309309
     
    721721      ///
    722722      /// Returns the base node of the iterator
    723       Node baseNode(IncArcIt) const {
     723      Node baseNode(IncEdgeIt) const {
    724724        return INVALID;
    725725      }
     
    728728      ///
    729729      /// Returns the running node of the iterator
    730       Node runningNode(IncArcIt) const {
     730      Node runningNode(IncEdgeIt) const {
    731731        return INVALID;
    732732      }
  • lemon/concepts/graph_components.h

    r57 r78  
    829829      /// This iterator goes trough the incident arcs of a certain
    830830      /// node of a graph.
    831       typedef GraphIncIt<Graph, Edge, Node, 'u'> IncArcIt;
     831      typedef GraphIncIt<Graph, Edge, Node, 'u'> IncEdgeIt;
    832832      /// \brief The base node of the iterator.
    833833      ///
    834834      /// Gives back the base node of the iterator.
    835       Node baseNode(const IncArcIt&) const { return INVALID; }
     835      Node baseNode(const IncEdgeIt&) const { return INVALID; }
    836836
    837837      /// \brief The running node of the iterator.
    838838      ///
    839839      /// Gives back the running node of the iterator.
    840       Node runningNode(const IncArcIt&) const { return INVALID; }
     840      Node runningNode(const IncEdgeIt&) const { return INVALID; }
    841841
    842842      /// @}
     
    866866              typename _Graph::EdgeIt >();
    867867            checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
    868               typename _Graph::Node, 'u'>, typename _Graph::IncArcIt>();
     868              typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();
    869869           
    870870            typename _Graph::Node n;
    871             typename _Graph::IncArcIt ueit(INVALID);
     871            typename _Graph::IncEdgeIt ueit(INVALID);
    872872            n = graph.baseNode(ueit);
    873873            n = graph.runningNode(ueit);
  • lemon/concepts/maps.h

    r74 r94  
    3030
    3131  namespace concepts {
    32  
     32
    3333    /// \addtogroup concept
    3434    /// @{
     
    4343    public:
    4444      /// 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      }
    5553
    5654      template<typename _ReadMap>
     
    5957          Value val = m[key];
    6058          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
    10162          ignore_unused_variable_warning(key);
    10263          ignore_unused_variable_warning(val);
     
    10465          ignore_unused_variable_warning(own_val);
    10566        }
    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;
    111109        _WriteMap& m;
    112 
    113110      };
    114111    };
    115112
    116113    /// Read/writable map concept
    117    
     114
    118115    /// Read/writable map concept.
    119116    ///
     
    124121    public:
    125122      /// 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 &) {}
    134134
    135135      template<typename _ReadWriteMap>
     
    141141      };
    142142    };
    143  
    144  
     143
     144
    145145    /// Dereferable map concept
    146    
     146
    147147    /// Dereferable map concept.
    148148    ///
    149     /// \todo Rethink this concept.
    150149    template<typename K, typename T, typename R, typename CR>
    151150    class ReferenceMap : public ReadWriteMap<K,T>
     
    155154      typedef True ReferenceMapTag;
    156155      /// The key type of the map.
    157       typedef K Key;   
     156      typedef K Key;
    158157      /// The value type of the map. (The type of objects associated with the keys).
    159158      typedef T Value;
     
    163162      typedef CR ConstReference;
    164163
    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.
    174177      void set(const Key &k,const Value &t) { operator[](k)=t; }
    175178
     
    178181        void constraints() {
    179182          checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
     183          ref = m[key];
    180184          m[key] = val;
    181           val  = m[key];
    182185          m[key] = ref;
    183           ref = m[key];
     186          m[key] = cref;
     187          own_ref = m[own_key];
    184188          m[own_key] = own_val;
    185           own_val  = m[own_key];
    186189          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;
    191199        typename _ReferenceMap::Value& own_val;
    192200        typename _ReferenceMap::Reference own_ref;
    193         Key& key;
    194         Value& val;
    195         Reference ref;
     201        typename _ReferenceMap::ConstReference own_cref;
    196202        _ReferenceMap& m;
    197203      };
  • lemon/maps.h

    r54 r104  
    2525
    2626#include <lemon/bits/utility.h>
    27 // #include <lemon/bits/traits.h>
     27#include <lemon/bits/traits.h>
    2828
    2929///\file
    3030///\ingroup maps
    3131///\brief Miscellaneous property maps
    32 ///
     32
    3333#include <map>
    3434
     
    4040  /// Base class of maps.
    4141
    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>
    4545  class MapBase {
    4646  public:
    47     /// The key type of the map.
     47    /// \biref The key type of the map.
    4848    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
    5254
    5355  /// Null map. (a.k.a. DoNothingMap)
    5456
    5557  /// 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
    5860  /// <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
    6671    /// Gives back a default constructed element.
    67     T operator[](const K&) const { return T(); }
     72    Value operator[](const Key&) const { return Value(); }
    6873    /// Absorbs the value.
    69     void set(const K&, const T&) {}
    70   };
    71 
    72   ///Returns a \c NullMap class
    73 
    74   ///This function just returns a \c NullMap class.
    75   ///\relates NullMap
    76   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>
    7782  NullMap<K, V> nullMap() {
    7883    return NullMap<K, V>();
     
    8287  /// Constant map.
    8388
    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> {
    89103  private:
    90     T v;
    91   public:
    92 
    93     typedef MapBase<K, T> Parent;
     104    V _value;
     105  public:
     106    typedef MapBase<K, V> Parent;
    94107    typedef typename Parent::Key Key;
    95108    typedef typename Parent::Value Value;
     
    98111
    99112    /// 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.
    102114    ConstMap() {}
    103    
     115
    104116    /// Constructor with specified initial value
    105117
    106118    /// 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>
    127142  inline ConstMap<K, V> constMap(const V &v) {
    128143    return ConstMap<K, V>(v);
     
    131146
    132147  template<typename T, T v>
    133   struct Const { };
     148  struct Const {};
    134149
    135150  /// Constant map with inlined constant value.
    136151
    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
    140164  template<typename K, typename V, V v>
    141165  class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
     
    145169    typedef typename Parent::Value Value;
    146170
    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>
    159187  inline ConstMap<K, Const<V, v> > constMap() {
    160188    return ConstMap<K, Const<V, v> >();
    161189  }
    162190
    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;
    183253
    184254    typedef True ReferenceMapTag;
    185255
     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
    186288  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;
    189374    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
    197381    /// 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())
    200385      : _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     StdMap(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)
    205390      : _map(c._map.begin(), c._map.end()), _value(c._value) {}
    206391
    207392  private:
    208393
    209     StdMap& operator=(const StdMap&);
     394    SparseMap& operator=(const SparseMap&);
    210395
    211396  public:
     
    220405    }
    221406
    222     /// \e
     407    ///\e
    223408    ConstReference operator[](const Key &k) const {
    224409      typename Map::const_iterator it = _map.find(k);
     
    229414    }
    230415
    231     /// \e
    232     void set(const Key &k, const T &t) {
     416    ///\e
     417    void set(const Key &k, const Value &v) {
    233418      typename Map::iterator it = _map.lower_bound(k);
    234419      if (it != _map.end() && !_map.key_comp()(k, it->first))
    235         it->second = t;
     420        it->second = v;
    236421      else
    237         _map.insert(it, std::make_pair(k, t));
     422        _map.insert(it, std::make_pair(k, v));
    238423    }
    239424
    240     /// \e
    241     void setAll(const T &t) {
    242       _value = t;
     425    ///\e
     426    void setAll(const Value &v) {
     427      _value = v;
    243428      _map.clear();
    244     }   
    245 
    246   };
    247  
    248   ///Returns a \c StdMap class
    249 
    250   ///This function just returns a \c StdMap class with specified
    251   ///default value.
    252   ///\relates StdMap
    253   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 class
    259 
    260   ///This function just returns a \c StdMap class with specified
    261   ///default value.
    262   ///\relates StdMap
    263   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::map
    269 
    270   ///This function just returns a \c StdMap class created from an
    271   ///appropriate std::map.
    272   ///\relates StdMap
    273   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::map
    280 
    281   ///This function just returns a \c StdMap class created from an
    282   ///appropriate std::map.
    283   ///\relates StdMap
    284   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 values
    293   /// are stored in a \c std::vector<T>  container. It can be used with
    294   /// some data structures, for example \c UnionFind, \c BinHeap, when
    295   /// the used items are small integer numbers.
    296   /// This map meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
    297   ///
    298   /// \todo Revise its name
    299   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     ///\e
    309     typedef typename Parent::Key Key;
    310     ///\e
    311     typedef typename Parent::Value Value;
    312     ///\e
    313     typedef T& Reference;
    314     ///\e
    315     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 value
    327     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 container
    340     void resize(int size, const T& value = T()) {
    341       _vector.resize(size, value);
    342429    }
    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);
    374458  }
    375459
     
    379463  /// @{
    380464
    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;
    455671  public:
    456672    typedef MapBase<typename M::Key, typename M::Value> Parent;
     
    458674    typedef typename Parent::Value Value;
    459675
    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
    470691  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>
    518796  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;
    522799  public:
    523800    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
     
    525802    typedef typename Parent::Value Value;
    526803
    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) {
    541821    return AddMap<M1, M2>(m1,m2);
    542822  }
    543823
    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>
    635844  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;
    638847  public:
    639848    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
     
    641850    typedef typename Parent::Value Value;
    642851
    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>
    655868  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>
    666893  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;
    669896  public:
    670897    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
     
    672899    typedef typename Parent::Value Value;
    673900
    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>
    685917  inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
    686918    return MulMap<M1, M2>(m1,m2);
    687919  }
    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>
    780941  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;
    783944  public:
    784945    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
     
    786947    typedef typename Parent::Value Value;
    787948
    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>
    799965  inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
    800966    return DivMap<M1, M2>(m1,m2);
    801967  }
    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>
    9361193  class NegMap : public MapBase<typename M::Key, typename M::Value> {
    937     const M& m;
     1194    const M& _m;
    9381195  public:
    9391196    typedef MapBase<typename M::Key, typename M::Value> Parent;
     
    9411198    typedef typename Parent::Value Value;
    9421199
    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.
    9551225  ///
    9561226  /// \sa NegMap
    957   template<typename M> 
     1227  template<typename M>
    9581228  class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
    959     M& m;
     1229    M &_m;
    9601230  public:
    9611231    typedef MapBase<typename M::Key, typename M::Value> Parent;
     
    9631233    typedef typename Parent::Value Value;
    9641234
    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>
    9781252  inline NegMap<M> negMap(const M &m) {
    9791253    return NegMap<M>(m);
    9801254  }
    9811255
    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) {
    9881267    return NegWriteMap<M>(m);
    9891268  }
    9901269
    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>
    9991282  class AbsMap : public MapBase<typename M::Key, typename M::Value> {
    1000     const M& m;
     1283    const M &_m;
    10011284  public:
    10021285    typedef MapBase<typename M::Key, typename M::Value> Parent;
     
    10041287    typedef typename Parent::Value Value;
    10051288
    1006     ///Constructor
    1007     AbsMap(const M &_m) : m(_m) {};
    1008     /// \e
    1009     Value operator[](Key k) 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];
    10111294      return tmp >= 0 ? tmp : -tmp;
    10121295    }
    10131296
    10141297  };
    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>
    10211310  inline AbsMap<M> absMap(const M &m) {
    10221311    return AbsMap<M>(m);
    10231312  }
    10241313
    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  /// @}
    10541315 
    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>
    12061506  class NotMap : public MapBase<typename M::Key, bool> {
    1207     const M& m;
     1507    const M &_m;
    12081508  public:
    12091509    typedef MapBase<typename M::Key, bool> Parent;
     
    12121512
    12131513    /// 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>
    12281532  class NotWriteMap : public MapBase<typename M::Key, bool> {
    1229     M& m;
     1533    M &_m;
    12301534  public:
    12311535    typedef MapBase<typename M::Key, bool> Parent;
     
    12341538
    12351539    /// 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>
    12481556  inline NotMap<M> notMap(const M &m) {
    12491557    return NotMap<M>(m);
    12501558  }
    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) {
    12581571    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);
    12591668  }
    12601669
     
    12771686    template <typename _Iterator>
    12781687    struct IteratorTraits<_Iterator,
    1279       typename exists<typename _Iterator::container_type>::type> 
     1688      typename exists<typename _Iterator::container_type>::type>
    12801689    {
    12811690      typedef typename _Iterator::container_type::value_type Value;
     
    12831692
    12841693  }
    1285  
    12861694
    12871695  /// \brief Writable bool map for logging each \c true assigned element
    12881696  ///
    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>
    13201711  class StoreBoolMap {
    13211712  public:
    1322     typedef _Iterator Iterator;
    1323 
    1324     typedef typename _Functor::argument_type Key;
     1713    typedef It Iterator;
     1714
     1715    typedef Ke Key;
    13251716    typedef bool Value;
    13261717
    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) {}
    13321721
    13331722    /// Gives back the given iterator set for the first key
     
    13351724      return _begin;
    13361725    }
    1337  
     1726
    13381727    /// Gives back the the 'after the last' iterator
    13391728    Iterator end() const {
     
    13411730    }
    13421731
    1343     /// The \c set function of the map
     1732    /// The set function of the map
    13441733    void set(const Key& key, Value value) const {
    13451734      if (value) {
    1346         *_end++ = _functor(key);
     1735        *_end++ = key;
    13471736      }
    13481737    }
    1349    
     1738
    13501739  private:
    13511740    Iterator _begin;
    13521741    mutable Iterator _end;
    1353     Functor _functor;
    1354   };
    1355 
    1356   /// \brief Writable bool map for logging each \c true assigned element in
    1357   /// a back insertable container.
    1358   ///
    1359   /// Writable bool map for logging each \c true assigned element by pushing
    1360   /// them into a back insertable container.
    1361   /// It can be used to retrieve the items into a standard
    1362   /// container. The next example shows how you can store the
    1363   /// edges found by the Prim algorithm in a vector.
    1364   ///
    1365   ///\code
    1366   /// vector<Edge> span_tree_edges;
    1367   /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges);
    1368   /// prim(graph, cost, inserter_map);
    1369   ///\endcode
    1370   ///
    1371   ///\sa StoreBoolMap
    1372   ///\sa FrontInserterBoolMap
    1373   ///\sa InserterBoolMap
    1374   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     /// Constructor
    1383     BackInserterBoolMap(Container& _container,
    1384                         const Functor& _functor = Functor())
    1385       : container(_container), functor(_functor) {}
    1386 
    1387     /// The \c set function of the map
    1388     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 in
    1400   /// a front insertable container.
    1401   ///
    1402   /// Writable bool map for logging each \c true assigned element by pushing
    1403   /// them into a front insertable container.
    1404   /// It can be used to retrieve the items into a standard
    1405   /// container. For example see \ref BackInserterBoolMap.
    1406   ///
    1407   ///\sa BackInserterBoolMap
    1408   ///\sa InserterBoolMap
    1409   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     /// Constructor
    1418     FrontInserterBoolMap(Container& _container,
    1419                          const Functor& _functor = Functor())
    1420       : container(_container), functor(_functor) {}
    1421 
    1422     /// The \c set function of the map
    1423     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 in
    1435   /// an insertable container.
    1436   ///
    1437   /// Writable bool map for storing each \c true assigned element in an
    1438   /// insertable container. It will insert all the keys set to \c true into
    1439   /// the container.
    1440   ///
    1441   /// For example, if you want to store the cut arcs of the strongly
    1442   /// connected components in a set you can use the next code:
    1443   ///
    1444   ///\code
    1445   /// set<Arc> cut_arcs;
    1446   /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs);
    1447   /// stronglyConnectedCutArcs(digraph, cost, inserter_map);
    1448   ///\endcode
    1449   ///
    1450   ///\sa BackInserterBoolMap
    1451   ///\sa FrontInserterBoolMap
    1452   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 iterator
    1461    
    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     /// Constructor
    1471 
    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 map
    1480     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 a
    1494   /// given value.
    1495   ///
    1496   /// Writable bool map for filling each \c true assigned element with a
    1497   /// given value. The value can set the container.
    1498   ///
    1499   /// The following code finds the connected components of a graph
    1500   /// and stores it in the \c comp map:
    1501   ///\code
    1502   /// 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   ///\endcode
    1518   template <typename Map>
    1519   class FillBoolMap {
    1520   public:
    1521     typedef typename Map::Key Key;
    1522     typedef bool Value;
    1523 
    1524     /// Constructor
    1525     FillBoolMap(Map& _map, const typename Map::Value& _fill)
    1526       : map(_map), fill(_fill) {}
    1527 
    1528     /// Constructor
    1529     FillBoolMap(Map& _map)
    1530       : map(_map), fill() {}
    1531 
    1532     /// Gives back the current fill value
    1533     const typename Map::Value& fillValue() const {
    1534       return fill;
    1535     }
    1536 
    1537     /// Gives back the current fill value
    1538     typename Map::Value& fillValue() {
    1539       return fill;
    1540     }
    1541 
    1542     /// Sets the current fill value
    1543     void fillValue(const typename Map::Value& _fill) {
    1544       fill = _fill;
    1545     }
    1546 
    1547     /// The \c set function of the map
    1548     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 of
    1561   /// \c true assignments. 
    1562   ///
    1563   /// Writable bool map that stores for each \c true assigned elements 
    1564   /// the sequence number of this setting.
    1565   /// It makes it easy to calculate the leaving
    1566   /// order of the nodes in the \c Dfs algorithm.
    1567   ///
    1568   ///\code
    1569   /// 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   ///\endcode
    1583   ///
    1584   /// The storing of the discovering order is more difficult because the
    1585   /// ReachedMap should be readable in the dfs algorithm but the setting
    1586   /// order map is not readable. Thus we must use the fork map:
    1587   ///
    1588   ///\code
    1589   /// 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   ///\endcode
    1609   template <typename Map>
    1610   class SettingOrderBoolMap {
    1611   public:
    1612     typedef typename Map::Key Key;
    1613     typedef bool Value;
    1614 
    1615     /// Constructor
    1616     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 map
    1625     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;
    16341742  };
    16351743
  • lemon/random.h

    r68 r102  
    576576    }
    577577
     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
    578598    /// \brief Returns a random real number from the range [0, 1)
    579599    ///
     
    804824    } 
    805825     
     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     
    806849    ///@}
    807850   
  • test/Makefile.am

    r103 r106  
    44noinst_HEADERS += \
    55        test/digraph_test.h \
     6        test/heap_test.h \
    67        test/map_test.h \
    78        test/test_tools.h
    89
    910check_PROGRAMS += \
     11        test/bfs_test \
     12        test/dfs_test \
    1013        test/digraph_test \
    1114        test/dim_test \
     
    1417        test/maps_test \
    1518        test/random_test \
     19        test/path_test \
    1620        test/test_tools_fail \
    1721        test/test_tools_pass \
     
    2125XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
    2226
     27test_bfs_test_SOURCES = test/bfs_test.cc
     28test_dfs_test_SOURCES = test/dfs_test.cc
    2329test_digraph_test_SOURCES = test/digraph_test.cc
    2430test_dim_test_SOURCES = test/dim_test.cc
    2531#test_error_test_SOURCES = test/error_test.cc
    2632test_graph_test_SOURCES = test/graph_test.cc
     33# test_heap_test_SOURCES = test/heap_test.cc
    2734test_kruskal_test_SOURCES = test/kruskal_test.cc
    2835test_maps_test_SOURCES = test/maps_test.cc
     36test_path_test_SOURCES = test/path_test.cc
    2937test_random_test_SOURCES = test/random_test.cc
    3038test_test_tools_fail_SOURCES = test/test_tools_fail.cc
  • test/maps_test.cc

    r39 r94  
    3232inline bool operator<(A, A) { return true; }
    3333struct B {};
     34
     35class C {
     36  int x;
     37public:
     38  C(int _x) : x(_x) {}
     39};
    3440
    3541class F {
     
    3844  typedef B result_type;
    3945
    40   B operator()(const A &) const {return B();}
     46  B operator()(const A&) const { return B(); }
     47private:
     48  F& operator=(const F&);
    4149};
    4250
    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;
     51int func(A) { return 3; }
     52
     53int binc(int a, B) { return a+1; }
     54
     55typedef ReadMap<A, double> DoubleMap;
     56typedef ReadWriteMap<A, double> DoubleWriteMap;
     57typedef ReferenceMap<A, double, double&, const double&> DoubleRefMap;
     58
     59typedef ReadMap<A, bool> BoolMap;
    5160typedef ReadWriteMap<A, bool> BoolWriteMap;
     61typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;
    5262
    5363int main()
    54 { // checking graph components
    55  
     64{
     65  // Map concepts
    5666  checkConcept<ReadMap<A,B>, ReadMap<A,B> >();
     67  checkConcept<ReadMap<A,C>, ReadMap<A,C> >();
    5768  checkConcept<WriteMap<A,B>, WriteMap<A,B> >();
     69  checkConcept<WriteMap<A,C>, WriteMap<A,C> >();
    5870  checkConcept<ReadWriteMap<A,B>, ReadWriteMap<A,B> >();
     71  checkConcept<ReadWriteMap<A,C>, ReadWriteMap<A,C> >();
    5972  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
    107301  return 0;
    108302}
  • test/random_test.cc

    r39 r102  
    2525///
    2626
     27int seed_array[] = {1, 2};
     28
    2729int main()
    2830{
     
    3436  //Does gamma work with integer k?
    3537  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;
    3645}
  • test/test_tools.h

    r39 r100  
    2121
    2222#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
     33using namespace lemon;
    2334
    2435//! \ingroup misc
     
    3748///\code check(0==1,"This is obviously false.");\endcode will
    3849///print this (and then exits).
    39 ///\verbatim graph_test.cc:123: error: This is obviously false. \endverbatim
     50///\verbatim digraph_test.cc:123: error: This is obviously false. \endverbatim
    4051///
    4152///\todo It should be in \c error.h
     
    4657  } else { } \
    4758
     59///Structure returned by \ref addPetersen().
     60
     61///Structure returned by \ref addPetersen().
     62///
     63template<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
     84template<typename Digraph>
     85PetStruct<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///
     106template<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///
     124template<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///
     144template<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
     163template<typename Digraph>
     164UPetStruct<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
    48181#endif
Note: See TracChangeset for help on using the changeset viewer.