COIN-OR::LEMON - Graph Library

Changes in / [106:9ba2d265e191:105:e4948ef6a4ca] in lemon-1.0


Ignore:
Files:
17 deleted
15 edited

Legend:

Unmodified
Added
Removed
  • .hgignore

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

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

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

    r83 r71  
    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 arc/edge or node deletion.
     41some graph features like 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 arcs have to be hidden or the reverse oriented graph have to be used, then
     47edges 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 arcs of graphs.
     87values to the nodes and edges of graphs.
    8888*/
    8989
     
    9797maps from other maps.
    9898
    99 Most of them are \ref lemon::concepts::ReadMap "read-only maps".
    100 They can make arithmetic and logical operations between one or two maps
    101 (negation, shifting, addition, multiplication, logical 'and', 'or',
    102 'not' etc.) or e.g. convert a map to another one of different Value type.
     99Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can
     100make arithmetic operations between one or two maps (negation, scaling,
     101addition, multiplication etc.) or e.g. convert a map to another one
     102of 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 digraphToEps() function.
     107usage of map adaptors with the \c graphToEps() function:
    108108\code
    109109  Color nodeColor(int deg) {
     
    117117  }
    118118 
    119   Digraph::NodeMap<int> degree_map(graph);
     119  Graph::NodeMap<int> degree_map(graph);
    120120 
    121   digraphToEps(graph, "graph.eps")
     121  graphToEps(graph, "graph.eps")
    122122    .coords(coords).scaleToA4().undirected()
    123     .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
     123    .nodeColors(composeMap(functorMap(nodeColor), degree_map))
    124124    .run();
    125125\endcode
    126 The \c functorToMap() function makes an \c int to \c Color map from the
     126The \c functorMap() 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 previously created map. The composed map is a proper function to
    129 get the color of each node.
     128and the previous created map. The composed map is proper function to
     129get 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   Digraph graph;
    136 
    137   typedef Digraph::ArcMap<double> DoubleArcMap;
    138   DoubleArcMap length(graph);
    139   DoubleArcMap speed(graph);
    140 
    141   typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
     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 
    142143  TimeMap time(length, speed);
    143144 
    144   Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
     145  Dijkstra<Graph, TimeMap> dijkstra(graph, time);
    145146  dijkstra.run(source, target);
    146147\endcode
    147 We have a length map and a maximum speed map on the arcs of a digraph.
    148 The minimum time to pass the arc can be calculated as the division of
    149 the two maps which can be done implicitly with the \c DivMap template
     148
     149We have a length map and a maximum speed map on a graph. The minimum
     150time to pass the edge can be calculated as the division of the two
     151maps which can be done implicitly with the \c DivMap template
    150152class. We use the implicit minimum time map as the length map of the
    151153\c Dijkstra algorithm.
     
    314316This group contains algorithm objects and functions to calculate
    315317matchings in graphs and bipartite graphs. The general matching problem is
    316 finding a subset of the arcs which does not shares common endpoints.
     318finding a subset of the edges which does not shares common endpoints.
    317319 
    318320There are several different algorithms for calculate matchings in
  • lemon/Makefile.am

    r106 r103  
    88
    99lemon_libemon_la_SOURCES = \
    10         lemon/arg_parser.cc \
    1110        lemon/base.cc \
    1211        lemon/random.cc
     
    1716
    1817lemon_HEADERS += \
    19         lemon/arg_parser.h \
    20         lemon/bfs.h \
    21         lemon/bin_heap.h \
    22         lemon/dfs.h \
    23         lemon/dijkstra.h \
     18        lemon/concept_check.h \
    2419        lemon/dim2.h \
    2520        lemon/error.h \
    26         lemon/graph_utils.h \
    2721        lemon/kruskal.h \
    2822        lemon/list_graph.h \
    2923        lemon/maps.h \
    3024        lemon/math.h \
    31         lemon/path.h \
    3225        lemon/random.h \
    3326        lemon/tolerance.h \
     
    4235        lemon/bits/invalid.h \
    4336        lemon/bits/map_extender.h \
    44         lemon/bits/path_dump.h \
    4537        lemon/bits/traits.h \
    4638        lemon/bits/utility.h \
     
    5143        lemon/concepts/digraph.h \
    5244        lemon/concepts/graph.h \
    53         lemon/concepts/heap.h \
    5445        lemon/concepts/maps.h \
    55         lemon/concepts/path.h \
    5646        lemon/concepts/graph_components.h
  • lemon/bits/graph_extender.h

    r78 r77  
    6565    }
    6666
    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);
     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);
    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& arc) :
    133         Arc(arc), _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& e) :
     133        Arc(e), 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 &arc) const {
    194       return Parent::source(arc);
     193    Node baseNode(const OutArcIt &e) const {
     194      return Parent::source(e);
    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 &arc) const {
    201       return Parent::target(arc);
     200    Node runningNode(const OutArcIt &e) const {
     201      return Parent::target(e);
    202202    }
    203203
     
    205205    ///
    206206    /// Returns the base node (i.e. the target in this case) of the iterator
    207     Node baseNode(const InArcIt &arc) const {
    208       return Parent::target(arc);
     207    Node baseNode(const InArcIt &e) const {
     208      return Parent::target(e);
    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 &arc) const {
    215       return Parent::source(arc);
     214    Node runningNode(const InArcIt &e) const {
     215      return Parent::source(e);
    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 Graph;
     335    typedef GraphExtender Digraph;
    336336
    337337    typedef True UndirectedTag;
     
    376376    }
    377377
    378     Arc oppositeArc(const Arc &arc) const {
    379       return Parent::direct(arc, !Parent::direction(arc));
     378    Arc oppositeArc(const Arc &e) const {
     379      return Parent::direct(e, !Parent::direction(e));
    380380    }
    381381
    382382    using Parent::direct;
    383     Arc direct(const Edge &edge, const Node &node) const {
    384       return Parent::direct(edge, Parent::source(edge) == node);
     383    Arc direct(const Edge &ue, const Node &s) const {
     384      return Parent::direct(ue, Parent::source(ue) == s);
    385385    }
    386386
     
    415415
    416416    class NodeIt : public Node {
    417       const Graph* _graph;
     417      const Digraph* digraph;
    418418    public:
    419419
     
    422422      NodeIt(Invalid i) : Node(i) { }
    423423
    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) {}
     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) {}
    430430
    431431      NodeIt& operator++() {
    432         _graph->next(*this);
     432        digraph->next(*this);
    433433        return *this;
    434434      }
     
    438438
    439439    class ArcIt : public Arc {
    440       const Graph* _graph;
     440      const Digraph* digraph;
    441441    public:
    442442
     
    445445      ArcIt(Invalid i) : Arc(i) { }
    446446
    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) { }
     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) { }
    453453
    454454      ArcIt& operator++() {
    455         _graph->next(*this);
     455        digraph->next(*this);
    456456        return *this;
    457457      }
     
    461461
    462462    class OutArcIt : public Arc {
    463       const Graph* _graph;
     463      const Digraph* digraph;
    464464    public:
    465465
     
    468468      OutArcIt(Invalid i) : Arc(i) { }
    469469
    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) {}
     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) {}
    477477
    478478      OutArcIt& operator++() {
    479         _graph->nextOut(*this);
     479        digraph->nextOut(*this);
    480480        return *this;
    481481      }
     
    485485
    486486    class InArcIt : public Arc {
    487       const Graph* _graph;
     487      const Digraph* digraph;
    488488    public:
    489489
     
    492492      InArcIt(Invalid i) : Arc(i) { }
    493493
    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) {}
     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) {}
    501501
    502502      InArcIt& operator++() {
    503         _graph->nextIn(*this);
     503        digraph->nextIn(*this);
    504504        return *this;
    505505      }
     
    509509
    510510    class EdgeIt : public Parent::Edge {
    511       const Graph* _graph;
     511      const Digraph* digraph;
    512512    public:
    513513
     
    516516      EdgeIt(Invalid i) : Edge(i) { }
    517517
    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) { }
     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) { }
    524524
    525525      EdgeIt& operator++() {
    526         _graph->next(*this);
    527         return *this;
    528       }
    529 
    530     };
    531 
    532     class IncEdgeIt : public Parent::Edge {
     526        digraph->next(*this);
     527        return *this;
     528      }
     529
     530    };
     531
     532    class IncArcIt : public Parent::Edge {
    533533      friend class GraphExtender;
    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);
     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);
    553553        return *this;
    554554      }
     
    558558    ///
    559559    /// Returns the base node (ie. the source in this case) of the iterator
    560     Node baseNode(const OutArcIt &arc) const {
    561       return Parent::source(static_cast<const Arc&>(arc));
     560    Node baseNode(const OutArcIt &e) const {
     561      return Parent::source(static_cast<const Arc&>(e));
    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 &arc) const {
    568       return Parent::target(static_cast<const Arc&>(arc));
     567    Node runningNode(const OutArcIt &e) const {
     568      return Parent::target(static_cast<const Arc&>(e));
    569569    }
    570570
     
    572572    ///
    573573    /// Returns the base node (ie. the target in this case) of the iterator
    574     Node baseNode(const InArcIt &arc) const {
    575       return Parent::target(static_cast<const Arc&>(arc));
     574    Node baseNode(const InArcIt &e) const {
     575      return Parent::target(static_cast<const Arc&>(e));
    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 &arc) const {
    582       return Parent::source(static_cast<const Arc&>(arc));
     581    Node runningNode(const InArcIt &e) const {
     582      return Parent::source(static_cast<const Arc&>(e));
    583583    }
    584584
     
    586586    ///
    587587    /// Returns the base node of the iterator
    588     Node baseNode(const IncEdgeIt &edge) const {
    589       return edge._direction ? source(edge) : target(edge);
     588    Node baseNode(const IncArcIt &e) const {
     589      return e.direction ? source(e) : target(e);
    590590    }
    591591    /// Running node of the iterator
    592592    ///
    593593    /// Returns the running node of the iterator
    594     Node runningNode(const IncEdgeIt &edge) const {
    595       return edge._direction ? target(edge) : source(edge);
     594    Node runningNode(const IncArcIt &e) const {
     595      return e.direction ? target(e) : source(e);
    596596    }
    597597
     
    600600    template <typename _Value>
    601601    class NodeMap
    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) {}
     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) {}
    611611
    612612      NodeMap& operator=(const NodeMap& cmap) {
     
    624624    template <typename _Value>
    625625    class ArcMap
    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) {}
     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) {}
    635635
    636636      ArcMap& operator=(const ArcMap& cmap) {
     
    648648    template <typename _Value>
    649649    class EdgeMap
    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) {}
     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) {}
    660660
    661661      EdgeMap& operator=(const EdgeMap& cmap) {
     
    696696    }
    697697
    698     template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
    699     void build(const Graph& graph, NodeRefMap& nodeRef,
     698    template <typename Digraph, typename NodeRefMap, typename EdgeRefMap>
     699    void build(const Digraph& digraph, NodeRefMap& nodeRef,
    700700               EdgeRefMap& edgeRef) {
    701       Parent::build(graph, nodeRef, edgeRef);
     701      Parent::build(digraph, nodeRef, edgeRef);
    702702      notifier(Node()).build();
    703703      notifier(Edge()).build();
     
    724724
    725725    void erase(const Edge& edge) {
    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);
     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);
    730730      notifier(Edge()).erase(edge);
    731731      Parent::erase(edge);
  • lemon/concepts/graph.h

    r78 r61  
    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 IncEdgeIt iterates also on the same edges
     66    /// direction. The IncArcIt 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::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
     273      /// for(Graph::IncArcIt e(g, n); e!=INVALID; ++e) ++count;
    274274      ///\endcode
    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) { }
     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) { }
    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         IncEdgeIt(const Graph&, const Node&) { }
    297         /// Edge -> IncEdgeIt conversion
     296        IncArcIt(const Graph&, const Node&) { }
     297        /// Edge -> IncArcIt 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         IncEdgeIt(const Graph&, const Edge&) { }
     302        IncArcIt(const Graph&, const Edge&) { }
    303303        /// Next incident arc
    304304
    305305        /// Assign the iterator to the next incident arc
    306306        /// of the corresponding node.
    307         IncEdgeIt& operator++() { return *this; }
     307        IncArcIt& operator++() { return *this; }
    308308      };
    309309
     
    721721      ///
    722722      /// Returns the base node of the iterator
    723       Node baseNode(IncEdgeIt) const {
     723      Node baseNode(IncArcIt) const {
    724724        return INVALID;
    725725      }
     
    728728      ///
    729729      /// Returns the running node of the iterator
    730       Node runningNode(IncEdgeIt) const {
     730      Node runningNode(IncArcIt) const {
    731731        return INVALID;
    732732      }
  • lemon/concepts/graph_components.h

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

    r94 r74  
    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 the given key.
    50       Value operator[](const Key &) const {
    51         return *static_cast<Value *>(0);
    52       }
     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();}
    5355
    5456      template<typename _ReadMap>
     
    5759          Value val = m[key];
    5860          val = m[key];
    59           typename _ReadMap::Value own_val = m[own_key];
    60           own_val = m[own_key];
    61 
     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);
    62101          ignore_unused_variable_warning(key);
    63102          ignore_unused_variable_warning(val);
     
    65104          ignore_unused_variable_warning(own_val);
    66105        }
    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;
     106
     107        Value& val;
     108        typename _WriteMap::Value own_val;
     109        Key& key;
     110        typename _WriteMap::Key& own_key;
    109111        _WriteMap& m;
     112
    110113      };
    111114    };
    112115
    113116    /// Read/writable map concept
    114 
     117   
    115118    /// Read/writable map concept.
    116119    ///
     
    121124    public:
    122125      /// The key type of the map.
    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 &) {}
     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 &) {}
    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.
    149150    template<typename K, typename T, typename R, typename CR>
    150151    class ReferenceMap : public ReadWriteMap<K,T>
     
    154155      typedef True ReferenceMapTag;
    155156      /// The key type of the map.
    156       typedef K Key;
     157      typedef K Key;   
    157158      /// The value type of the map. (The type of objects associated with the keys).
    158159      typedef T Value;
     
    162163      typedef CR ConstReference;
    163164
    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.
     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.
    177174      void set(const Key &k,const Value &t) { operator[](k)=t; }
    178175
     
    181178        void constraints() {
    182179          checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
     180          m[key] = val;
     181          val  = m[key];
     182          m[key] = ref;
    183183          ref = m[key];
    184           m[key] = val;
    185           m[key] = ref;
    186           m[key] = cref;
    187           own_ref = m[own_key];
    188184          m[own_key] = own_val;
     185          own_val  = m[own_key];
    189186          m[own_key] = own_ref;
    190           m[own_key] = own_cref;
    191           m[key] = m[own_key];
    192           m[own_key] = m[key];
    193         }
    194         const Key& key;
     187          own_ref = m[own_key];           
     188        }
     189
     190        typename _ReferenceMap::Key& own_key;
     191        typename _ReferenceMap::Value& own_val;
     192        typename _ReferenceMap::Reference own_ref;
     193        Key& key;
    195194        Value& val;
    196195        Reference ref;
    197         ConstReference cref;
    198         const typename _ReferenceMap::Key& own_key;
    199         typename _ReferenceMap::Value& own_val;
    200         typename _ReferenceMap::Reference own_ref;
    201         typename _ReferenceMap::ConstReference own_cref;
    202196        _ReferenceMap& m;
    203197      };
  • lemon/maps.h

    r104 r54  
    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. It provides the necessary type definitions
    43   /// required by the map %concepts.
    44   template<typename K, typename V>
     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>
    4545  class MapBase {
    4646  public:
    47     /// \biref The key type of the map.
     47    /// The key type of the map.
    4848    typedef K Key;
    49     /// \brief The value type of the map.
    50     /// (The type of objects associated with the keys).
    51     typedef V Value;
    52   };
    53 
     49    /// The value type of the map. (The type of objects associated with the keys).
     50    typedef T Value;
     51  };
    5452
    5553  /// Null map. (a.k.a. DoNothingMap)
    5654
    5755  /// This map can be used if you have to provide a map only for
    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
     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 
    6058  /// <tt>/dev/null</tt>).
    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 
     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   
    7166    /// Gives back a default constructed element.
    72     Value operator[](const Key&) const { return Value(); }
     67    T operator[](const K&) const { return T(); }
    7368    /// Absorbs the value.
    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>
     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> 
    8277  NullMap<K, V> nullMap() {
    8378    return NullMap<K, V>();
     
    8782  /// Constant map.
    8883
    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> {
     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> {
    10389  private:
    104     V _value;
    105   public:
    106     typedef MapBase<K, V> Parent;
     90    T v;
     91  public:
     92
     93    typedef MapBase<K, T> Parent;
    10794    typedef typename Parent::Key Key;
    10895    typedef typename Parent::Value Value;
     
    11198
    11299    /// Default constructor.
    113     /// The value of the map will be default constructed.
     100    /// The value of the map will be uninitialized.
     101    /// (More exactly it will be default constructed.)
    114102    ConstMap() {}
    115 
     103   
    116104    /// Constructor with specified initial value
    117105
    118106    /// Constructor with specified initial value.
    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>
     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>
    142127  inline ConstMap<K, V> constMap(const V &v) {
    143128    return ConstMap<K, V>(v);
     
    146131
    147132  template<typename T, T v>
    148   struct Const {};
     133  struct Const { };
    149134
    150135  /// Constant map with inlined constant value.
    151136
    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
     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.
    164140  template<typename K, typename V, V v>
    165141  class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
     
    169145    typedef typename Parent::Value Value;
    170146
    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>
     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>
    187159  inline ConstMap<K, Const<V, v> > constMap() {
    188160    return ConstMap<K, Const<V, v> >();
    189161  }
    190162
    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;
     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;
     183
     184    typedef True ReferenceMapTag;
     185
    237186  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;
    253 
    254     typedef True ReferenceMapTag;
    255 
    256   public:
    257 
    258     /// Constructor with specified default value.
    259     RangeMap(int size = 0, const Value &value = Value())
    260       : _vector(size, value) {}
    261 
    262     /// Constructs the map from an appropriate \c std::vector.
    263     template <typename V1>
    264     RangeMap(const std::vector<V1>& vector)
    265       : _vector(vector.begin(), vector.end()) {}
    266 
    267     /// Constructs the map from another \ref RangeMap.
    268     template <typename V1>
    269     RangeMap(const RangeMap<V1> &c)
    270       : _vector(c._vector.begin(), c._vector.end()) {}
    271 
    272     /// Returns the size of the map.
    273     int size() {
    274       return _vector.size();
    275     }
    276 
    277     /// Resizes the map.
    278 
    279     /// Resizes the underlying \c std::vector container, so changes the
    280     /// keyset of the map.
    281     /// \param size The new size of the map. The new keyset will be the
    282     /// range <tt>[0..size-1]</tt>.
    283     /// \param value The default value to assign to the new keys.
    284     void resize(int size, const Value &value = Value()) {
    285       _vector.resize(size, value);
    286     }
     187   
     188    typedef std::map<K, T, Compare> Map;
     189    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
     197    /// explicitly specifies a default value.
     198    template <typename T1, typename Comp1>
     199    StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T())
     200      : _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)
     205      : _map(c._map.begin(), c._map.end()), _value(c._value) {}
    287206
    288207  private:
    289208
    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;
    374     Value _value;
    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
    381     /// explicitly specifies a default value.
    382     template <typename V1, typename Comp1>
    383     SparseMap(const std::map<Key, V1, Comp1> &map,
    384               const Value &value = Value())
    385       : _map(map.begin(), map.end()), _value(value) {}
    386 
    387     /// \brief Constructs the map from another \ref SparseMap.
    388     template<typename V1, typename Comp1>
    389     SparseMap(const SparseMap<Key, V1, Comp1> &c)
    390       : _map(c._map.begin(), c._map.end()), _value(c._value) {}
    391 
    392   private:
    393 
    394     SparseMap& operator=(const SparseMap&);
     209    StdMap& operator=(const StdMap&);
    395210
    396211  public:
     
    405220    }
    406221
    407     ///\e
     222    /// \e
    408223    ConstReference operator[](const Key &k) const {
    409224      typename Map::const_iterator it = _map.find(k);
     
    414229    }
    415230
    416     ///\e
    417     void set(const Key &k, const Value &v) {
     231    /// \e
     232    void set(const Key &k, const T &t) {
    418233      typename Map::iterator it = _map.lower_bound(k);
    419234      if (it != _map.end() && !_map.key_comp()(k, it->first))
    420         it->second = v;
     235        it->second = t;
    421236      else
    422         _map.insert(it, std::make_pair(k, v));
    423     }
    424 
    425     ///\e
    426     void setAll(const Value &v) {
    427       _value = v;
     237        _map.insert(it, std::make_pair(k, t));
     238    }
     239
     240    /// \e
     241    void setAll(const T &t) {
     242      _value = t;
    428243      _map.clear();
    429     }
    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);
     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);
     342    }
     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);
    458374  }
    459375
     
    463379  /// @{
    464380
    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
     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
     455  public:
     456    typedef MapBase<typename M::Key, typename M::Value> Parent;
     457    typedef typename Parent::Key Key;
     458    typedef typename Parent::Value Value;
     459
     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
     470  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>
     518  class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
     519    const M1& m1;
     520    const M2& m2;
     521
     522  public:
     523    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
     524    typedef typename Parent::Key Key;
     525    typedef typename Parent::Value Value;
     526
     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) {
     541    return AddMap<M1, M2>(m1,m2);
     542  }
     543
     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>
     635  class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
     636    const M1& m1;
     637    const M2& m2;
     638  public:
     639    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
     640    typedef typename Parent::Key Key;
     641    typedef typename Parent::Value Value;
     642
     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>
     655  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>
     666  class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
     667    const M1& m1;
     668    const M2& m2;
     669  public:
     670    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
     671    typedef typename Parent::Key Key;
     672    typedef typename Parent::Value Value;
     673
     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>
     685  inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
     686    return MulMap<M1, M2>(m1,m2);
     687  }
     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>
     780  class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
     781    const M1& m1;
     782    const M2& m2;
     783  public:
     784    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
     785    typedef typename Parent::Key Key;
     786    typedef typename Parent::Value Value;
     787
     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>
     799  inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
     800    return DivMap<M1, M2>(m1,m2);
     801  }
     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
    473812  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
    474813  ///
    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>
     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>
    486821  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
    487     const M1 &_m1;
    488     const M2 &_m2;
     822    const M1& m1;
     823    const M2& m2;
    489824  public:
    490825    typedef MapBase<typename M2::Key, typename M1::Value> Parent;
     
    492827    typedef typename Parent::Value Value;
    493828
    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.
     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.
    541874  template<typename M1, typename M2, typename F,
    542            typename V = typename F::result_type>
     875           typename V = typename F::result_type> 
    543876  class CombineMap : public MapBase<typename M1::Key, V> {
    544     const M1 &_m1;
    545     const M2 &_m2;
    546     F _f;
     877    const M1& m1;
     878    const M2& m2;
     879    F f;
    547880  public:
    548881    typedef MapBase<typename M1::Key, V> Parent;
     
    550883    typedef typename Parent::Value Value;
    551884
    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) {
     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) {
    580912    return CombineMap<M1, M2, F, V>(m1,m2,f);
    581913  }
    582914
    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) {
     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) {
    586918    return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
    587919  }
    588920
    589   template<typename M1, typename M2, typename K1, typename K2, typename V>
    590   inline CombineMap<M1, M2, V (*)(K1, K2), V>
     921  template<typename M1, typename M2, typename K1, typename K2, typename V> 
     922  inline CombineMap<M1, M2, V (*)(K1, K2), V> 
    591923  combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
    592924    return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
    593925  }
    594926
    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;
     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>
     936  class NegMap : public MapBase<typename M::Key, typename M::Value> {
     937    const M& m;
    671938  public:
    672939    typedef MapBase<typename M::Key, typename M::Value> Parent;
     
    674941    typedef typename Parent::Value Value;
    675942
    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
    691   template<typename M>
    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>
    796   class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
    797     const M1 &_m1;
    798     const M2 &_m2;
    799   public:
    800     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
    801     typedef typename Parent::Key Key;
    802     typedef typename Parent::Value Value;
    803 
    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) {
    821     return AddMap<M1, M2>(m1,m2);
    822   }
    823 
    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>
    844   class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
    845     const M1 &_m1;
    846     const M2 &_m2;
    847   public:
    848     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
    849     typedef typename Parent::Key Key;
    850     typedef typename Parent::Value Value;
    851 
    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>
    868   inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &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>
    893   class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
    894     const M1 &_m1;
    895     const M2 &_m2;
    896   public:
    897     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
    898     typedef typename Parent::Key Key;
    899     typedef typename Parent::Value Value;
    900 
    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>
    917   inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
    918     return MulMap<M1, M2>(m1,m2);
    919   }
    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>
    941   class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
    942     const M1 &_m1;
    943     const M2 &_m2;
    944   public:
    945     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
    946     typedef typename Parent::Key Key;
    947     typedef typename Parent::Value Value;
    948 
    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>
    965   inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
    966     return DivMap<M1, M2>(m1,m2);
    967   }
    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;
     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.
     955  ///
     956  /// \sa NegMap
     957  template<typename M>
     958  class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
     959    M& m;
    994960  public:
    995961    typedef MapBase<typename M::Key, typename M::Value> Parent;
     
    997963    typedef typename Parent::Value Value;
    998964
    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>
    1193   class NegMap : public MapBase<typename M::Key, typename M::Value> {
    1194     const M& _m;
    1195   public:
    1196     typedef MapBase<typename M::Key, typename M::Value> Parent;
    1197     typedef typename Parent::Key Key;
    1198     typedef typename Parent::Value Value;
    1199 
    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.
    1225   ///
    1226   /// \sa NegMap
    1227   template<typename M>
    1228   class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
    1229     M &_m;
    1230   public:
    1231     typedef MapBase<typename M::Key, typename M::Value> Parent;
    1232     typedef typename Parent::Key Key;
    1233     typedef typename Parent::Value Value;
    1234 
    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>
     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>
    1252978  inline NegMap<M> negMap(const M &m) {
    1253979    return NegMap<M>(m);
    1254980  }
    1255981
    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) {
     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) {
    1267988    return NegWriteMap<M>(m);
    1268989  }
    1269990
    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>
     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>
    1282999  class AbsMap : public MapBase<typename M::Key, typename M::Value> {
    1283     const M &_m;
     1000    const M& m;
    12841001  public:
    12851002    typedef MapBase<typename M::Key, typename M::Value> Parent;
     
    12871004    typedef typename Parent::Value Value;
    12881005
    1289     /// Constructor
    1290     AbsMap(const M &m) : _m(m) {}
    1291     /// \e
    1292     Value operator[](const Key &k) const {
    1293       Value tmp = _m[k];
     1006    ///Constructor
     1007    AbsMap(const M &_m) : m(_m) {};
     1008    /// \e
     1009    Value operator[](Key k) const {
     1010      Value tmp = m[k];
    12941011      return tmp >= 0 ? tmp : -tmp;
    12951012    }
    12961013
    12971014  };
    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>
     1015 
     1016  ///Returns an \c AbsMap class
     1017
     1018  ///This function just returns an \c AbsMap class.
     1019  ///\relates AbsMap
     1020  template<typename M>
    13101021  inline AbsMap<M> absMap(const M &m) {
    13111022    return AbsMap<M>(m);
    13121023  }
    13131024
    1314   /// @}
    1315  
    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;
     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  };
     1054 
     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>
     1206  class NotMap : public MapBase<typename M::Key, bool> {
     1207    const M& m;
     1208  public:
     1209    typedef MapBase<typename M::Key, bool> Parent;
    14231210    typedef typename Parent::Key Key;
    14241211    typedef typename Parent::Value Value;
    14251212
    14261213    /// 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;
     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>
     1228  class NotWriteMap : public MapBase<typename M::Key, bool> {
     1229    M& m;
     1230  public:
     1231    typedef MapBase<typename M::Key, bool> Parent;
    14711232    typedef typename Parent::Key Key;
    14721233    typedef typename Parent::Value Value;
    14731234
    14741235    /// 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>
    1506   class NotMap : public MapBase<typename M::Key, bool> {
    1507     const M &_m;
    1508   public:
    1509     typedef MapBase<typename M::Key, bool> Parent;
    1510     typedef typename Parent::Key Key;
    1511     typedef typename Parent::Value Value;
    1512 
    1513     /// Constructor
    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>
    1532   class NotWriteMap : public MapBase<typename M::Key, bool> {
    1533     M &_m;
    1534   public:
    1535     typedef MapBase<typename M::Key, bool> Parent;
    1536     typedef typename Parent::Key Key;
    1537     typedef typename Parent::Value Value;
    1538 
    1539     /// Constructor
    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>
     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>
    15561248  inline NotMap<M> notMap(const M &m) {
    15571249    return NotMap<M>(m);
    15581250  }
    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) {
     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) {
    15711258    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);
    16681259  }
    16691260
     
    16861277    template <typename _Iterator>
    16871278    struct IteratorTraits<_Iterator,
    1688       typename exists<typename _Iterator::container_type>::type>
     1279      typename exists<typename _Iterator::container_type>::type> 
    16891280    {
    16901281      typedef typename _Iterator::container_type::value_type Value;
     
    16921283
    16931284  }
     1285 
    16941286
    16951287  /// \brief Writable bool map for logging each \c true assigned element
    16961288  ///
    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>
     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> >
    17111320  class StoreBoolMap {
    17121321  public:
    1713     typedef It Iterator;
    1714 
    1715     typedef Ke Key;
     1322    typedef _Iterator Iterator;
     1323
     1324    typedef typename _Functor::argument_type Key;
    17161325    typedef bool Value;
    17171326
     1327    typedef _Functor Functor;
     1328
    17181329    /// Constructor
    1719     StoreBoolMap(Iterator it)
    1720       : _begin(it), _end(it) {}
     1330    StoreBoolMap(Iterator it, const Functor& functor = Functor())
     1331      : _begin(it), _end(it), _functor(functor) {}
    17211332
    17221333    /// Gives back the given iterator set for the first key
     
    17241335      return _begin;
    17251336    }
    1726 
     1337 
    17271338    /// Gives back the the 'after the last' iterator
    17281339    Iterator end() const {
     
    17301341    }
    17311342
    1732     /// The set function of the map
     1343    /// The \c set function of the map
    17331344    void set(const Key& key, Value value) const {
    17341345      if (value) {
    1735         *_end++ = key;
     1346        *_end++ = _functor(key);
    17361347      }
    17371348    }
    1738 
     1349   
    17391350  private:
    17401351    Iterator _begin;
    17411352    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;
    17421634  };
    17431635
  • lemon/random.h

    r102 r68  
    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 
    598578    /// \brief Returns a random real number from the range [0, 1)
    599579    ///
     
    824804    } 
    825805     
    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      
    849806    ///@}
    850807   
  • test/Makefile.am

    r106 r103  
    44noinst_HEADERS += \
    55        test/digraph_test.h \
    6         test/heap_test.h \
    76        test/map_test.h \
    87        test/test_tools.h
    98
    109check_PROGRAMS += \
    11         test/bfs_test \
    12         test/dfs_test \
    1310        test/digraph_test \
    1411        test/dim_test \
     
    1714        test/maps_test \
    1815        test/random_test \
    19         test/path_test \
    2016        test/test_tools_fail \
    2117        test/test_tools_pass \
     
    2521XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
    2622
    27 test_bfs_test_SOURCES = test/bfs_test.cc
    28 test_dfs_test_SOURCES = test/dfs_test.cc
    2923test_digraph_test_SOURCES = test/digraph_test.cc
    3024test_dim_test_SOURCES = test/dim_test.cc
    3125#test_error_test_SOURCES = test/error_test.cc
    3226test_graph_test_SOURCES = test/graph_test.cc
    33 # test_heap_test_SOURCES = test/heap_test.cc
    3427test_kruskal_test_SOURCES = test/kruskal_test.cc
    3528test_maps_test_SOURCES = test/maps_test.cc
    36 test_path_test_SOURCES = test/path_test.cc
    3729test_random_test_SOURCES = test/random_test.cc
    3830test_test_tools_fail_SOURCES = test/test_tools_fail.cc
  • test/maps_test.cc

    r94 r39  
    3333struct B {};
    3434
    35 class C {
    36   int x;
    37 public:
    38   C(int _x) : x(_x) {}
    39 };
    40 
    4135class F {
    4236public:
     
    4438  typedef B result_type;
    4539
    46   B operator()(const A&) const { return B(); }
    47 private:
    48   F& operator=(const F&);
     40  B operator()(const A &) const {return B();}
    4941};
    5042
    51 int func(A) { return 3; }
     43int func(A) {return 3;}
    5244
    53 int binc(int a, B) { return a+1; }
     45int binc(int, B) {return 4;}
    5446
    55 typedef ReadMap<A, double> DoubleMap;
    56 typedef ReadWriteMap<A, double> DoubleWriteMap;
    57 typedef ReferenceMap<A, double, double&, const double&> DoubleRefMap;
     47typedef ReadMap<A,double> DoubleMap;
     48typedef ReadWriteMap<A, double> WriteDoubleMap;
    5849
    59 typedef ReadMap<A, bool> BoolMap;
     50typedef ReadMap<A,bool> BoolMap;
    6051typedef ReadWriteMap<A, bool> BoolWriteMap;
    61 typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;
    6252
    6353int main()
    64 {
    65   // Map concepts
     54{ // checking graph components
     55 
    6656  checkConcept<ReadMap<A,B>, ReadMap<A,B> >();
    67   checkConcept<ReadMap<A,C>, ReadMap<A,C> >();
    6857  checkConcept<WriteMap<A,B>, WriteMap<A,B> >();
    69   checkConcept<WriteMap<A,C>, WriteMap<A,C> >();
    7058  checkConcept<ReadWriteMap<A,B>, ReadWriteMap<A,B> >();
    71   checkConcept<ReadWriteMap<A,C>, ReadWriteMap<A,C> >();
    7259  checkConcept<ReferenceMap<A,B,B&,const B&>, ReferenceMap<A,B,B&,const B&> >();
    73   checkConcept<ReferenceMap<A,C,C&,const C&>, ReferenceMap<A,C,C&,const C&> >();
    7460
    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   }
     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> > >();
    8277
    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());
     78  checkConcept<ReadMap<A,B>, FunctorMap<F, A, B> >();
    9179
    92     checkConcept<ReadWriteMap<A,int>, ConstMap<A,int> >();
    93     check(constMap<A>(10)[A()] == 10, "Something is wrong with ConstMap");
     80  checkConcept<ReadMap<A, bool>, NotMap<BoolMap> >();
     81  checkConcept<ReadWriteMap<A, bool>, NotWriteMap<BoolWriteMap> >();
    9482
    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   }
     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> > >();
    10189
    102   // IdentityMap
    103   {
    104     checkConcept<ReadMap<A,A>, IdentityMap<A> >();
    105     IdentityMap<A> map1;
    106     IdentityMap<A> map2 = map1;
    107     map1 = identityMap<A>();
     90  int a;
     91 
     92  a=mapFunctor(constMap<A,int>(2))(A());
     93  check(a==2,"Something is wrong with mapFunctor");
    10894
    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   }
     95  B b;
     96  b=functorMap(F())[A()];
    11397
    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());
     98  a=functorMap(&func)[A()];
     99  check(a==3,"Something is wrong with functorMap");
    124100
    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   }
     101  a=combineMap(constMap<B, int, 1>(), identityMap<B>(), &binc)[B()];
     102  check(a==4,"Something is wrong with combineMap");
     103 
    134104
    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 
     105  std::cout << __FILE__ ": All tests passed.\n";
     106 
    301107  return 0;
    302108}
  • test/random_test.cc

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

    r100 r39  
    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 
    33 using namespace lemon;
    3423
    3524//! \ingroup misc
     
    4837///\code check(0==1,"This is obviously false.");\endcode will
    4938///print this (and then exits).
    50 ///\verbatim digraph_test.cc:123: error: This is obviously false. \endverbatim
     39///\verbatim graph_test.cc:123: error: This is obviously false. \endverbatim
    5140///
    5241///\todo It should be in \c error.h
     
    5746  } else { } \
    5847
    59 ///Structure returned by \ref addPetersen().
    60 
    61 ///Structure returned by \ref addPetersen().
    62 ///
    63 template<class Digraph> struct PetStruct
    64 {
    65   ///Vector containing the outer nodes.
    66   std::vector<typename Digraph::Node> outer;
    67   ///Vector containing the inner nodes.
    68   std::vector<typename Digraph::Node> inner;
    69   ///Vector containing the arcs of the inner circle.
    70   std::vector<typename Digraph::Arc> incir;
    71   ///Vector containing the arcs of the outer circle.
    72   std::vector<typename Digraph::Arc> outcir;
    73   ///Vector containing the chord arcs.
    74   std::vector<typename Digraph::Arc> chords;
    75 };
    76 
    77 
    78 
    79 ///Adds a Petersen digraph to \c G.
    80 
    81 ///Adds a Petersen digraph to \c G.
    82 ///\return The nodes and arcs of the generated digraph.
    83 
    84 template<typename Digraph>
    85 PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
    86 {
    87   PetStruct<Digraph> n;
    88 
    89   for(int i=0;i<num;i++) {
    90     n.outer.push_back(G.addNode());
    91     n.inner.push_back(G.addNode());
    92   }
    93 
    94  for(int i=0;i<num;i++) {
    95    n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
    96    n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
    97    n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
    98   }
    99  return n;
    100 }
    101 
    102 /// \brief Adds to the digraph the reverse pair of all arcs.
    103 ///
    104 /// Adds to the digraph the reverse pair of all arcs.
    105 ///
    106 template<class Digraph> void bidirDigraph(Digraph &G)
    107 {
    108   typedef typename Digraph::Arc Arc;
    109   typedef typename Digraph::ArcIt ArcIt;
    110  
    111   std::vector<Arc> ee;
    112  
    113   for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
    114 
    115   for(typename std::vector<Arc>::iterator p=ee.begin();p!=ee.end();p++)
    116     G.addArc(G.target(*p),G.source(*p));
    117 }
    118 
    119 
    120 /// \brief Checks the bidirectioned Petersen digraph.
    121 ///
    122 ///  Checks the bidirectioned Petersen digraph.
    123 ///
    124 template<class Digraph> void checkBidirPetersen(Digraph &G, int num = 5)
    125 {
    126   typedef typename Digraph::Node Node;
    127 
    128   typedef typename Digraph::ArcIt ArcIt;
    129   typedef typename Digraph::NodeIt NodeIt;
    130 
    131   checkDigraphNodeList(G, 2 * num);
    132   checkDigraphArcList(G, 6 * num);
    133 
    134   for(NodeIt n(G);n!=INVALID;++n) {
    135     checkDigraphInArcList(G, n, 3);
    136     checkDigraphOutArcList(G, n, 3);
    137   } 
    138 }
    139 
    140 ///Structure returned by \ref addUPetersen().
    141 
    142 ///Structure returned by \ref addUPetersen().
    143 ///
    144 template<class Digraph> struct UPetStruct
    145 {
    146   ///Vector containing the outer nodes.
    147   std::vector<typename Digraph::Node> outer;
    148   ///Vector containing the inner nodes.
    149   std::vector<typename Digraph::Node> inner;
    150   ///Vector containing the arcs of the inner circle.
    151   std::vector<typename Digraph::Edge> incir;
    152   ///Vector containing the arcs of the outer circle.
    153   std::vector<typename Digraph::Edge> outcir;
    154   ///Vector containing the chord arcs.
    155   std::vector<typename Digraph::Edge> chords;
    156 };
    157 
    158 ///Adds a Petersen digraph to the undirected \c G.
    159 
    160 ///Adds a Petersen digraph to the undirected \c G.
    161 ///\return The nodes and arcs of the generated digraph.
    162 
    163 template<typename Digraph>
    164 UPetStruct<Digraph> addUPetersen(Digraph &G,int num=5)
    165 {
    166   UPetStruct<Digraph> n;
    167 
    168   for(int i=0;i<num;i++) {
    169     n.outer.push_back(G.addNode());
    170     n.inner.push_back(G.addNode());
    171   }
    172 
    173  for(int i=0;i<num;i++) {
    174    n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
    175    n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1)%5]));
    176    n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2)%5]));
    177  }
    178  return n;
    179 }
    180 
    18148#endif
Note: See TracChangeset for help on using the changeset viewer.