COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [88:18444049848b:89:e6452a49192c] in lemon-main


Ignore:
Files:
3 added
16 edited

Legend:

Unmodified
Added
Removed

  • Makefile.am

    r5 r70  
    11ACLOCAL_AMFLAGS = -I m4
    22
    3 AM_CPPFLAGS = -I$(top_srcdir)
     3AM_CPPFLAGS = -I$(top_srcdir) -I$(top_builddir)
    44LDADD = $(top_builddir)/lemon/libemon.la
    55

  • configure.ac

    r55 r64  
    1414AC_CONFIG_AUX_DIR([build-aux])
    1515AC_CONFIG_MACRO_DIR([m4])
    16 AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects])
     16AM_INIT_AUTOMAKE([-Wall -Werror foreign subdir-objects nostdinc])
    1717AC_CONFIG_SRCDIR([lemon/list_graph.h])
    1818AC_CONFIG_HEADERS([config.h lemon/config.h])
    … …  
    2727AC_PROG_LIBTOOL
    2828
     29AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
     30
    2931if test x"$lx_cmdline_cxxflags_set" != x"set" -a "$GXX" = yes; then
    3032  CXXFLAGS="$CXXFLAGS -Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas"
    3133fi
    32 
    33 AC_CHECK_PROG([doxygen_found],[doxygen],[yes],[no])
    3434
    3535dnl Checks for libraries.
    … …  
    3737LX_CHECK_CPLEX
    3838LX_CHECK_SOPLEX
    39 
    40 dnl Enable/disable installing the documentation
    41 AC_ARG_ENABLE([doc],
    42 AS_HELP_STRING([--enable-doc@<:@=yes|no|full@:>@], [build the documentation (full enables internal documentation too) @<:@default=yes@:>@])
    43 AS_HELP_STRING([--disable-doc], [do not build the documentation]),
    44               [], [enable_doc=yes])
    45 
    46 AC_MSG_CHECKING([whether to build the documention])
    47 case "$enable_doc" in
    48   yes)
    49     DOXYGEN_INTERNAL_DOCS=NO
    50     AC_MSG_RESULT([yes])
    51     ;;
    52   full)
    53     DOXYGEN_INTERNAL_DOCS=YES
    54     AC_MSG_RESULT([full])
    55     ;;
    56   no)
    57     DOXYGEN_INTERNAL_DOCS=NO
    58     AC_MSG_RESULT([no])
    59     ;;
    60   *)
    61     AC_MSG_ERROR([bad value $enable_doc for option --enable-doc])
    62     ;;
    63 esac
    64 AC_SUBST(DOXYGEN_INTERNAL_DOCS)
    65 AM_CONDITIONAL([WANT_DOC], [test x"$enable_doc" != x"no"])
    6639
    6740dnl Disable/enable building the demo programs
    … …  
    146119echo $prefix.
    147120echo
    148 echo The documentation will be installed in
    149 echo -n '  '
    150 eval echo ${datadir}/doc/$PACKAGE.
    151 echo
    152121echo '*********************************************************************'
    153122

  • doc/Makefile.am

    r56 r60  
    1 htmldir = $(datadir)/doc/$(PACKAGE)/html
    2 
    31EXTRA_DIST += \
    42        doc/Makefile \
    5         doc/Doxyfile.in
     3        doc/Doxyfile.in \
     4        doc/coding_style.dox \
     5        doc/dirs.dox \
     6        doc/groups.dox \
     7        doc/license.dox \
     8        doc/mainpage.dox \
     9        doc/namespaces.dox \
     10        doc/html
    611
    7 doc:
     12doc/html:
     13        $(MAKE) $(AM_MAKEFLAGS) html
     14
     15html-local:
    816        if test ${doxygen_found} = yes; then \
    917          cd doc; \
    1018          doxygen Doxyfile; \
    1119          cd ..; \
    12         fi
    13 
    14 doc-clean:
    15         if test ${doxygen_found} = yes; then \
    16           rm -rf doc/html; \
    17           rm -f doc/doxygen.log; \
    18           cd doc; \
    19           doxygen Doxyfile; \
    20           cd ..; \
     20        else \
     21          echo; \
     22          echo "Doxygen not found."; \
     23          echo; \
     24          exit 1; \
    2125        fi
    2226
    … …  
    2529        -rm -f doc/doxygen.log
    2630
    27 doc/html:
    28         $(MAKE) $(AM_MAKEFLAGS) doc-clean
    29 
    3031update-external-tags:
    3132        wget -O doc/libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag && \
    … …  
    3334        rm doc/libstdc++.tag.tmp
    3435
    35 if WANT_DOC
    36 
    37 install-data-local: doc/html
     36install-html-local: doc/html
    3837        @$(NORMAL_INSTALL)
    39         $(mkinstalldirs) $(DESTDIR)$(htmldir)
    40         @dir='doc/html'; shopt -s nullglob; for p in $$dir/*.html $$dir/*.css $$dir/*.png $$dir/*.gif $$dir/*.dot $$dir/*.php $$dir/*.idx $$dir/*.tag ; do \
     38        $(mkinstalldirs) $(DESTDIR)$(htmldir)/docs
     39        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
    4140          f="`echo $$p | sed -e 's|^.*/||'`"; \
    42           echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/$$f"; \
    43           $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/$$f; \
     41          echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f"; \
     42          $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f; \
    4443        done
    4544
    46 uninstall-local: doc/html
     45uninstall-local:
    4746        @$(NORMAL_UNINSTALL)
    48         @dir='doc/html'; shopt -s nullglob; for p in $$dir/*.html $$dir/*.css $$dir/*.png $$dir/*.gif $$dir/*.dot $$dir/*.php $$dir/*.idx $$dir/*.tag ; do \
     47        for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
    4948          f="`echo $$p | sed -e 's|^.*/||'`"; \
    50           echo " rm -f $(DESTDIR)$(htmldir)/$$f"; \
    51           rm -f $(DESTDIR)$(htmldir)/$$f; \
     49          echo " rm -f $(DESTDIR)$(htmldir)/docs/$$f"; \
     50          rm -f $(DESTDIR)$(htmldir)/docs/$$f; \
    5251        done
    5352
    54 endif WANT_DOC
    55 
    56 .PHONY: doc doc-clean
     53.PHONY: update-external-tags

  • doc/groups.dox

    r50 r83  
    3939the diverging requirements of the possible users.  In order to save on
    4040running time or on memory usage, some structures may fail to provide
    41 some graph features like edge or node deletion.
     41some graph features like arc/edge or node deletion.
    4242
    4343Alteration of standard containers need a very limited number of
    … …  
    4545In the case of graph structures, different operations are needed which do
    4646not alter the physical graph, but gives another view. If some nodes or
    47 edges have to be hidden or the reverse oriented graph have to be used, then
     47arcs have to be hidden or the reverse oriented graph have to be used, then
    4848this is the case. It also may happen that in a flow implementation
    4949the residual graph can be accessed by another algorithm, or a node-set
    … …  
    8282@defgroup graph_maps Graph Maps
    8383@ingroup maps
    84 \brief Special Graph-Related Maps.
     84\brief Special graph-related maps.
    8585
    8686This group describes maps that are specifically designed to assign
    87 values to the nodes and edges of graphs.
     87values to the nodes and arcs of graphs.
    8888*/
    8989
    … …  
    9797maps from other maps.
    9898
    99 Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can
    100 make arithmetic operations between one or two maps (negation, scaling,
    101 addition, multiplication etc.) or e.g. convert a map to another one
    102 of different Value type.
     99Most of them are \ref lemon::concepts::ReadMap "read-only maps".
     100They can make arithmetic and logical operations between one or two maps
     101(negation, shifting, addition, multiplication, logical 'and', 'or',
     102'not' etc.) or e.g. convert a map to another one of different Value type.
    103103
    104104The typical usage of this classes is passing implicit maps to
    105105algorithms.  If a function type algorithm is called then the function
    106106type map adaptors can be used comfortable. For example let's see the
    107 usage of map adaptors with the \c graphToEps() function:
     107usage of map adaptors with the \c digraphToEps() function.
    108108\code
    109109  Color nodeColor(int deg) {
    … …  
    117117  }
    118118 
    119   Graph::NodeMap<int> degree_map(graph);
     119  Digraph::NodeMap<int> degree_map(graph);
    120120 
    121   graphToEps(graph, "graph.eps")
     121  digraphToEps(graph, "graph.eps")
    122122    .coords(coords).scaleToA4().undirected()
    123     .nodeColors(composeMap(functorMap(nodeColor), degree_map))
     123    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
    124124    .run();
    125125\endcode
    126 The \c functorMap() function makes an \c int to \c Color map from the
     126The \c functorToMap() function makes an \c int to \c Color map from the
    127127\e nodeColor() function. The \c composeMap() compose the \e degree_map
    128 and the previous created map. The composed map is proper function to
    129 get color of each node.
     128and the previously created map. The composed map is a proper function to
     129get the color of each node.
    130130
    131131The usage with class type algorithms is little bit harder. In this
    … …  
    133133function map adaptors give back temporary objects.
    134134\code
    135   Graph graph;
    136  
    137   typedef Graph::EdgeMap<double> DoubleEdgeMap;
    138   DoubleEdgeMap length(graph);
    139   DoubleEdgeMap speed(graph);
    140  
    141   typedef DivMap<DoubleEdgeMap, DoubleEdgeMap> TimeMap;
    142  
     135  Digraph graph;
     136
     137  typedef Digraph::ArcMap<double> DoubleArcMap;
     138  DoubleArcMap length(graph);
     139  DoubleArcMap speed(graph);
     140
     141  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
    143142  TimeMap time(length, speed);
    144143 
    145   Dijkstra<Graph, TimeMap> dijkstra(graph, time);
     144  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
    146145  dijkstra.run(source, target);
    147146\endcode
    148 
    149 We have a length map and a maximum speed map on a graph. The minimum
    150 time to pass the edge can be calculated as the division of the two
    151 maps which can be done implicitly with the \c DivMap template
     147We have a length map and a maximum speed map on the arcs of a digraph.
     148The minimum time to pass the arc can be calculated as the division of
     149the two maps which can be done implicitly with the \c DivMap template
    152150class. We use the implicit minimum time map as the length map of the
    153151\c Dijkstra algorithm.
    … …  
    316314This group contains algorithm objects and functions to calculate
    317315matchings in graphs and bipartite graphs. The general matching problem is
    318 finding a subset of the edges which does not shares common endpoints.
     316finding a subset of the arcs which does not shares common endpoints.
    319317 
    320318There are several different algorithms for calculate matchings in
    … …  
    488486@defgroup section_io Section readers and writers
    489487@ingroup lemon_io
    490 \brief Section readers and writers for lemon Input-Output.
    491 
    492 This group describes section readers and writers that can be attached to
     488\brief Section readers and writers for LEMON Input-Output.
     489
     490This group describes section reader and writer classes that can be
     491attached to \ref LemonReader and \ref LemonWriter.
     492*/
     493
     494/**
     495@defgroup item_io Item readers and writers
     496@ingroup lemon_io
     497\brief Item readers and writers for LEMON Input-Output.
     498
     499This group describes reader and writer classes for various data types
     500(e.g. map or attribute values). These classes can be attached to
    493501\ref LemonReader and \ref LemonWriter.
    494 */
    495 
    496 /**
    497 @defgroup item_io Item Readers and Writers
    498 @ingroup lemon_io
    499 \brief Item readers and writers for lemon Input-Output.
    500 
    501 The Input-Output classes can handle more data type by example
    502 as map or attribute value. Each of these should be written and
    503 read some way. The module make possible to do this. 
    504502*/
    505503

  • lemon/Makefile.am

    r85 r89  
    1818lemon_HEADERS += \
    1919        lemon/arg_parser.h \
     20        lemon/concept_check.h \
    2021        lemon/dim2.h \
     22        lemon/error.h \
     23        lemon/list_graph.h \
    2124        lemon/maps.h \
     25        lemon/math.h \
    2226        lemon/random.h \
    23         lemon/list_graph.h \
    2427        lemon/tolerance.h
    2528

  • lemon/bits/graph_extender.h

    r57 r78  
    2121
    2222#include <lemon/bits/invalid.h>
     23#include <lemon/bits/utility.h>
    2324
    2425#include <lemon/bits/map_extender.h>
    … …  
    6465    }
    6566
    66     Node oppositeNode(const Node &n, const Arc &e) const {
    67       if (n == Parent::source(e))
    68         return Parent::target(e);
    69       else if(n==Parent::target(e))
    70         return Parent::source(e);
     67    Node oppositeNode(const Node &node, const Arc &arc) const {
     68      if (node == Parent::source(arc))
     69        return Parent::target(arc);
     70      else if(node == Parent::target(arc))
     71        return Parent::source(arc);
    7172      else
    7273        return INVALID;
    … …  
    9596
    9697    class NodeIt : public Node {
    97       const Digraph* digraph;
     98      const Digraph* _digraph;
    9899    public:
    99100
    … …  
    102103      NodeIt(Invalid i) : Node(i) { }
    103104
    104       explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) {
    105         _digraph.first(static_cast<Node&>(*this));
    106       }
    107 
    108       NodeIt(const Digraph& _digraph, const Node& node)
    109         : 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) {}
    110111
    111112      NodeIt& operator++() {
    112         digraph->next(*this);
     113        _digraph->next(*this);
    113114        return *this;
    114115      }
    … …  
    118119
    119120    class ArcIt : public Arc {
    120       const Digraph* digraph;
     121      const Digraph* _digraph;
    121122    public:
    122123
    … …  
    125126      ArcIt(Invalid i) : Arc(i) { }
    126127
    127       explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {
    128         _digraph.first(static_cast<Arc&>(*this));
    129       }
    130 
    131       ArcIt(const Digraph& _digraph, const Arc& e) :
    132         Arc(e), digraph(&_digraph) { }
     128      explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) {
     129        _digraph->first(static_cast<Arc&>(*this));
     130      }
     131
     132      ArcIt(const Digraph& digraph, const Arc& arc) :
     133        Arc(arc), _digraph(&digraph) { }
    133134
    134135      ArcIt& operator++() {
    135         digraph->next(*this);
     136        _digraph->next(*this);
    136137        return *this;
    137138      }
    … …  
    141142
    142143    class OutArcIt : public Arc {
    143       const Digraph* digraph;
     144      const Digraph* _digraph;
    144145    public:
    145146
    … …  
    148149      OutArcIt(Invalid i) : Arc(i) { }
    149150
    150       OutArcIt(const Digraph& _digraph, const Node& node)
    151         : digraph(&_digraph) {
    152         _digraph.firstOut(*this, node);
    153       }
    154 
    155       OutArcIt(const Digraph& _digraph, const Arc& arc)
    156         : 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) {}
    157158
    158159      OutArcIt& operator++() {
    159         digraph->nextOut(*this);
     160        _digraph->nextOut(*this);
    160161        return *this;
    161162      }
    … …  
    165166
    166167    class InArcIt : public Arc {
    167       const Digraph* digraph;
     168      const Digraph* _digraph;
    168169    public:
    169170
    … …  
    172173      InArcIt(Invalid i) : Arc(i) { }
    173174
    174       InArcIt(const Digraph& _digraph, const Node& node)
    175         : digraph(&_digraph) {
    176         _digraph.firstIn(*this, node);
    177       }
    178 
    179       InArcIt(const Digraph& _digraph, const Arc& arc) :
    180         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) {}
    181182
    182183      InArcIt& operator++() {
    183         digraph->nextIn(*this);
     184        _digraph->nextIn(*this);
    184185        return *this;
    185186      }
    … …  
    190191    ///
    191192    /// Returns the base node (i.e. the source in this case) of the iterator
    192     Node baseNode(const OutArcIt &e) const {
    193       return Parent::source(e);
     193    Node baseNode(const OutArcIt &arc) const {
     194      return Parent::source(arc);
    194195    }
    195196    /// \brief Running node of the iterator
    … …  
    197198    /// Returns the running node (i.e. the target in this case) of the
    198199    /// iterator
    199     Node runningNode(const OutArcIt &e) const {
    200       return Parent::target(e);
     200    Node runningNode(const OutArcIt &arc) const {
     201      return Parent::target(arc);
    201202    }
    202203
    … …  
    204205    ///
    205206    /// Returns the base node (i.e. the target in this case) of the iterator
    206     Node baseNode(const InArcIt &e) const {
    207       return Parent::target(e);
     207    Node baseNode(const InArcIt &arc) const {
     208      return Parent::target(arc);
    208209    }
    209210    /// \brief Running node of the iterator
    … …  
    211212    /// Returns the running node (i.e. the source in this case) of the
    212213    /// iterator
    213     Node runningNode(const InArcIt &e) const {
    214       return Parent::source(e);
     214    Node runningNode(const InArcIt &arc) const {
     215      return Parent::source(arc);
    215216    }
    216217
    … …  
    324325  };
    325326
    326   /// \ingroup graphbits
     327  /// \ingroup _graphbits
    327328  ///
    328329  /// \brief Extender for the Graphs
    … …  
    332333   
    333334    typedef Base Parent;
    334     typedef GraphExtender Digraph;
     335    typedef GraphExtender Graph;
     336
     337    typedef True UndirectedTag;
    335338
    336339    typedef typename Parent::Node Node;
    … …  
    373376    }
    374377
    375     Arc oppositeArc(const Arc &e) const {
    376       return Parent::direct(e, !Parent::direction(e));
     378    Arc oppositeArc(const Arc &arc) const {
     379      return Parent::direct(arc, !Parent::direction(arc));
    377380    }
    378381
    379382    using Parent::direct;
    380     Arc direct(const Edge &ue, const Node &s) const {
    381       return Parent::direct(ue, Parent::source(ue) == s);
     383    Arc direct(const Edge &edge, const Node &node) const {
     384      return Parent::direct(edge, Parent::source(edge) == node);
    382385    }
    383386
    … …  
    412415
    413416    class NodeIt : public Node {
    414       const Digraph* digraph;
     417      const Graph* _graph;
    415418    public:
    416419
    … …  
    419422      NodeIt(Invalid i) : Node(i) { }
    420423
    421       explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) {
    422         _digraph.first(static_cast<Node&>(*this));
    423       }
    424 
    425       NodeIt(const Digraph& _digraph, const Node& node)
    426         : Node(node), digraph(&_digraph) {}
     424      explicit NodeIt(const Graph& graph) : _graph(&graph) {
     425        _graph->first(static_cast<Node&>(*this));
     426      }
     427
     428      NodeIt(const Graph& graph, const Node& node)
     429        : Node(node), _graph(&graph) {}
    427430
    428431      NodeIt& operator++() {
    429         digraph->next(*this);
     432        _graph->next(*this);
    430433        return *this;
    431434      }
    … …  
    435438
    436439    class ArcIt : public Arc {
    437       const Digraph* digraph;
     440      const Graph* _graph;
    438441    public:
    439442
    … …  
    442445      ArcIt(Invalid i) : Arc(i) { }
    443446
    444       explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {
    445         _digraph.first(static_cast<Arc&>(*this));
    446       }
    447 
    448       ArcIt(const Digraph& _digraph, const Arc& e) :
    449         Arc(e), digraph(&_digraph) { }
     447      explicit ArcIt(const Graph& graph) : _graph(&graph) {
     448        _graph->first(static_cast<Arc&>(*this));
     449      }
     450
     451      ArcIt(const Graph& graph, const Arc& arc) :
     452        Arc(arc), _graph(&graph) { }
    450453
    451454      ArcIt& operator++() {
    452         digraph->next(*this);
     455        _graph->next(*this);
    453456        return *this;
    454457      }
    … …  
    458461
    459462    class OutArcIt : public Arc {
    460       const Digraph* digraph;
     463      const Graph* _graph;
    461464    public:
    462465
    … …  
    465468      OutArcIt(Invalid i) : Arc(i) { }
    466469
    467       OutArcIt(const Digraph& _digraph, const Node& node)
    468         : digraph(&_digraph) {
    469         _digraph.firstOut(*this, node);
    470       }
    471 
    472       OutArcIt(const Digraph& _digraph, const Arc& arc)
    473         : Arc(arc), digraph(&_digraph) {}
     470      OutArcIt(const Graph& graph, const Node& node)
     471        : _graph(&graph) {
     472        _graph->firstOut(*this, node);
     473      }
     474
     475      OutArcIt(const Graph& graph, const Arc& arc)
     476        : Arc(arc), _graph(&graph) {}
    474477
    475478      OutArcIt& operator++() {
    476         digraph->nextOut(*this);
     479        _graph->nextOut(*this);
    477480        return *this;
    478481      }
    … …  
    482485
    483486    class InArcIt : public Arc {
    484       const Digraph* digraph;
     487      const Graph* _graph;
    485488    public:
    486489
    … …  
    489492      InArcIt(Invalid i) : Arc(i) { }
    490493
    491       InArcIt(const Digraph& _digraph, const Node& node)
    492         : digraph(&_digraph) {
    493         _digraph.firstIn(*this, node);
    494       }
    495 
    496       InArcIt(const Digraph& _digraph, const Arc& arc) :
    497         Arc(arc), digraph(&_digraph) {}
     494      InArcIt(const Graph& graph, const Node& node)
     495        : _graph(&graph) {
     496        _graph->firstIn(*this, node);
     497      }
     498
     499      InArcIt(const Graph& graph, const Arc& arc) :
     500        Arc(arc), _graph(&graph) {}
    498501
    499502      InArcIt& operator++() {
    500         digraph->nextIn(*this);
     503        _graph->nextIn(*this);
    501504        return *this;
    502505      }
    … …  
    506509
    507510    class EdgeIt : public Parent::Edge {
    508       const Digraph* digraph;
     511      const Graph* _graph;
    509512    public:
    510513
    … …  
    513516      EdgeIt(Invalid i) : Edge(i) { }
    514517
    515       explicit EdgeIt(const Digraph& _digraph) : digraph(&_digraph) {
    516         _digraph.first(static_cast<Edge&>(*this));
    517       }
    518 
    519       EdgeIt(const Digraph& _digraph, const Edge& e) :
    520         Edge(e), digraph(&_digraph) { }
     518      explicit EdgeIt(const Graph& graph) : _graph(&graph) {
     519        _graph->first(static_cast<Edge&>(*this));
     520      }
     521
     522      EdgeIt(const Graph& graph, const Edge& edge) :
     523        Edge(edge), _graph(&graph) { }
    521524
    522525      EdgeIt& operator++() {
    523         digraph->next(*this);
    524         return *this;
    525       }
    526 
    527     };
    528 
    529     class IncArcIt : public Parent::Edge {
     526        _graph->next(*this);
     527        return *this;
     528      }
     529
     530    };
     531
     532    class IncEdgeIt : public Parent::Edge {
    530533      friend class GraphExtender;
    531       const Digraph* digraph;
    532       bool direction;
    533     public:
    534 
    535       IncArcIt() { }
    536 
    537       IncArcIt(Invalid i) : Edge(i), direction(false) { }
    538 
    539       IncArcIt(const Digraph& _digraph, const Node &n) : digraph(&_digraph) {
    540         _digraph.firstInc(*this, direction, n);
    541       }
    542 
    543       IncArcIt(const Digraph& _digraph, const Edge &ue, const Node &n)
    544         : digraph(&_digraph), Edge(ue) {
    545         direction = (_digraph.source(ue) == n);
    546       }
    547 
    548       IncArcIt& operator++() {
    549         digraph->nextInc(*this, direction);
     534      const Graph* _graph;
     535      bool _direction;
     536    public:
     537
     538      IncEdgeIt() { }
     539
     540      IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
     541
     542      IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
     543        _graph->firstInc(*this, _direction, node);
     544      }
     545
     546      IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
     547        : _graph(&graph), Edge(edge) {
     548        _direction = (_graph->source(edge) == node);
     549      }
     550
     551      IncEdgeIt& operator++() {
     552        _graph->nextInc(*this, _direction);
    550553        return *this;
    551554      }
    … …  
    555558    ///
    556559    /// Returns the base node (ie. the source in this case) of the iterator
    557     Node baseNode(const OutArcIt &e) const {
    558       return Parent::source(static_cast<const Arc&>(e));
     560    Node baseNode(const OutArcIt &arc) const {
     561      return Parent::source(static_cast<const Arc&>(arc));
    559562    }
    560563    /// \brief Running node of the iterator
    … …  
    562565    /// Returns the running node (ie. the target in this case) of the
    563566    /// iterator
    564     Node runningNode(const OutArcIt &e) const {
    565       return Parent::target(static_cast<const Arc&>(e));
     567    Node runningNode(const OutArcIt &arc) const {
     568      return Parent::target(static_cast<const Arc&>(arc));
    566569    }
    567570
    … …  
    569572    ///
    570573    /// Returns the base node (ie. the target in this case) of the iterator
    571     Node baseNode(const InArcIt &e) const {
    572       return Parent::target(static_cast<const Arc&>(e));
     574    Node baseNode(const InArcIt &arc) const {
     575      return Parent::target(static_cast<const Arc&>(arc));
    573576    }
    574577    /// \brief Running node of the iterator
    … …  
    576579    /// Returns the running node (ie. the source in this case) of the
    577580    /// iterator
    578     Node runningNode(const InArcIt &e) const {
    579       return Parent::source(static_cast<const Arc&>(e));
     581    Node runningNode(const InArcIt &arc) const {
     582      return Parent::source(static_cast<const Arc&>(arc));
    580583    }
    581584
    … …  
    583586    ///
    584587    /// Returns the base node of the iterator
    585     Node baseNode(const IncArcIt &e) const {
    586       return e.direction ? source(e) : target(e);
     588    Node baseNode(const IncEdgeIt &edge) const {
     589      return edge._direction ? source(edge) : target(edge);
    587590    }
    588591    /// Running node of the iterator
    589592    ///
    590593    /// Returns the running node of the iterator
    591     Node runningNode(const IncArcIt &e) const {
    592       return e.direction ? target(e) : source(e);
     594    Node runningNode(const IncEdgeIt &edge) const {
     595      return edge._direction ? target(edge) : source(edge);
    593596    }
    594597
    … …  
    597600    template <typename _Value>
    598601    class NodeMap
    599       : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
    600     public:
    601       typedef GraphExtender Digraph;
    602       typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
    603 
    604       NodeMap(const Digraph& digraph)
    605         : Parent(digraph) {}
    606       NodeMap(const Digraph& digraph, const _Value& value)
    607         : Parent(digraph, value) {}
     602      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
     603    public:
     604      typedef GraphExtender Graph;
     605      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
     606
     607      NodeMap(const Graph& graph)
     608        : Parent(graph) {}
     609      NodeMap(const Graph& graph, const _Value& value)
     610        : Parent(graph, value) {}
    608611
    609612      NodeMap& operator=(const NodeMap& cmap) {
    … …  
    621624    template <typename _Value>
    622625    class ArcMap
    623       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
    624     public:
    625       typedef GraphExtender Digraph;
    626       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    627 
    628       ArcMap(const Digraph& digraph)
    629         : Parent(digraph) {}
    630       ArcMap(const Digraph& digraph, const _Value& value)
    631         : Parent(digraph, value) {}
     626      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
     627    public:
     628      typedef GraphExtender Graph;
     629      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
     630
     631      ArcMap(const Graph& graph)
     632        : Parent(graph) {}
     633      ArcMap(const Graph& graph, const _Value& value)
     634        : Parent(graph, value) {}
    632635
    633636      ArcMap& operator=(const ArcMap& cmap) {
    … …  
    645648    template <typename _Value>
    646649    class EdgeMap
    647       : public MapExtender<DefaultMap<Digraph, Edge, _Value> > {
    648     public:
    649       typedef GraphExtender Digraph;
    650       typedef MapExtender<DefaultMap<Digraph, Edge, _Value> > Parent;
    651 
    652       EdgeMap(const Digraph& digraph)
    653         : Parent(digraph) {}
    654 
    655       EdgeMap(const Digraph& digraph, const _Value& value)
    656         : Parent(digraph, value) {}
     650      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
     651    public:
     652      typedef GraphExtender Graph;
     653      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
     654
     655      EdgeMap(const Graph& graph)
     656        : Parent(graph) {}
     657
     658      EdgeMap(const Graph& graph, const _Value& value)
     659        : Parent(graph, value) {}
    657660
    658661      EdgeMap& operator=(const EdgeMap& cmap) {
    … …  
    693696    }
    694697
    695     template <typename Digraph, typename NodeRefMap, typename EdgeRefMap>
    696     void build(const Digraph& digraph, NodeRefMap& nodeRef,
     698    template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
     699    void build(const Graph& graph, NodeRefMap& nodeRef,
    697700               EdgeRefMap& edgeRef) {
    698       Parent::build(digraph, nodeRef, edgeRef);
     701      Parent::build(graph, nodeRef, edgeRef);
    699702      notifier(Node()).build();
    700703      notifier(Edge()).build();
    … …  
    721724
    722725    void erase(const Edge& edge) {
    723       std::vector<Arc> ev;
    724       ev.push_back(Parent::direct(edge, true));
    725       ev.push_back(Parent::direct(edge, false));     
    726       notifier(Arc()).erase(ev);
     726      std::vector<Arc> av;
     727      av.push_back(Parent::direct(edge, true));
     728      av.push_back(Parent::direct(edge, false));     
     729      notifier(Arc()).erase(av);
    727730      notifier(Edge()).erase(edge);
    728731      Parent::erase(edge);

  • lemon/concepts/digraph.h

    r57 r61  
    349349      Node source(Arc) const { return INVALID; }
    350350
     351      /// \brief Returns the ID of the node.
     352      int id(Node) const { return -1; }
     353
     354      /// \brief Returns the ID of the arc.
     355      int id(Arc) const { return -1; }
     356
     357      /// \brief Returns the node with the given ID.
     358      ///
     359      /// \pre The argument should be a valid node ID in the graph.
     360      Node nodeFromId(int) const { return INVALID; }
     361
     362      /// \brief Returns the arc with the given ID.
     363      ///
     364      /// \pre The argument should be a valid arc ID in the graph.
     365      Arc arcFromId(int) const { return INVALID; }
     366
     367      /// \brief Returns an upper bound on the node IDs.
     368      int maxNodeId() const { return -1; }
     369
     370      /// \brief Returns an upper bound on the arc IDs.
     371      int maxArcId() const { return -1; }
     372
    351373      void first(Node&) const {}
    352374      void next(Node&) const {}
    … …  
    361383      void firstOut(Arc&, const Node&) const {}
    362384      void nextOut(Arc&) const {}
     385
     386      // The second parameter is dummy.
     387      Node fromId(int, Node) const { return INVALID; }
     388      // The second parameter is dummy.
     389      Arc fromId(int, Arc) const { return INVALID; }
     390
     391      // Dummy parameter.
     392      int maxId(Node) const { return -1; }
     393      // Dummy parameter.
     394      int maxId(Arc) const { return -1; }
    363395
    364396      /// \brief The base node of the iterator.
    … …  
    440472        void constraints() {
    441473          checkConcept<IterableDigraphComponent<>, Digraph>();
     474          checkConcept<IDableDigraphComponent<>, Digraph>();
    442475          checkConcept<MappableDigraphComponent<>, Digraph>();
    443476        }

  • lemon/concepts/graph.h

    r57 r78  
    6464    /// the EdgeMap to map values for the edges. The InArcIt and
    6565    /// OutArcIt iterates on the same edges but with opposite
    66     /// direction. The IncArcIt iterates also on the same edges
     66    /// direction. The IncEdgeIt iterates also on the same edges
    6767    /// as the OutArcIt and InArcIt but it is not convertible to Arc just
    6868    /// to Edge. 
    … …  
    271271      ///\code
    272272      /// int count=0;
    273       /// for(Graph::IncArcIt e(g, n); e!=INVALID; ++e) ++count;
     273      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
    274274      ///\endcode
    275       class IncArcIt : public Edge {
    276       public:
    277         /// Default constructor
    278 
    279         /// @warning The default constructor sets the iterator
    280         /// to an undefined value.
    281         IncArcIt() { }
    282         /// Copy constructor.
    283 
    284         /// Copy constructor.
    285         ///
    286         IncArcIt(const IncArcIt& e) : Edge(e) { }
    287         /// Initialize the iterator to be invalid.
    288 
    289         /// Initialize the iterator to be invalid.
    290         ///
    291         IncArcIt(Invalid) { }
     275      class IncEdgeIt : public Edge {
     276      public:
     277        /// Default constructor
     278
     279        /// @warning The default constructor sets the iterator
     280        /// to an undefined value.
     281        IncEdgeIt() { }
     282        /// Copy constructor.
     283
     284        /// Copy constructor.
     285        ///
     286        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
     287        /// Initialize the iterator to be invalid.
     288
     289        /// Initialize the iterator to be invalid.
     290        ///
     291        IncEdgeIt(Invalid) { }
    292292        /// This constructor sets the iterator to first incident arc.
    293293   
    294294        /// This constructor set the iterator to the first incident arc of
    295295        /// the node.
    296         IncArcIt(const Graph&, const Node&) { }
    297         /// Edge -> IncArcIt conversion
     296        IncEdgeIt(const Graph&, const Node&) { }
     297        /// Edge -> IncEdgeIt conversion
    298298
    299299        /// Sets the iterator to the value of the trivial iterator \c e.
    300300        /// This feature necessitates that each time we
    301301        /// iterate the arc-set, the iteration order is the same.
    302         IncArcIt(const Graph&, const Edge&) { }
     302        IncEdgeIt(const Graph&, const Edge&) { }
    303303        /// Next incident arc
    304304
    305305        /// Assign the iterator to the next incident arc
    306306        /// of the corresponding node.
    307         IncArcIt& operator++() { return *this; }
     307        IncEdgeIt& operator++() { return *this; }
    308308      };
    309309
    … …  
    625625      Node target(Arc) const { return INVALID; }
    626626
     627      /// \brief Returns the id of the node.
     628      int id(Node) const { return -1; }
     629
     630      /// \brief Returns the id of the edge.
     631      int id(Edge) const { return -1; }
     632
     633      /// \brief Returns the id of the arc.
     634      int id(Arc) const { return -1; }
     635
     636      /// \brief Returns the node with the given id.
     637      ///
     638      /// \pre The argument should be a valid node id in the graph.
     639      Node nodeFromId(int) const { return INVALID; }
     640
     641      /// \brief Returns the edge with the given id.
     642      ///
     643      /// \pre The argument should be a valid edge id in the graph.
     644      Edge edgeFromId(int) const { return INVALID; }
     645
     646      /// \brief Returns the arc with the given id.
     647      ///
     648      /// \pre The argument should be a valid arc id in the graph.
     649      Arc arcFromId(int) const { return INVALID; }
     650
     651      /// \brief Returns an upper bound on the node IDs.
     652      int maxNodeId() const { return -1; }
     653
     654      /// \brief Returns an upper bound on the edge IDs.
     655      int maxEdgeId() const { return -1; }
     656
     657      /// \brief Returns an upper bound on the arc IDs.
     658      int maxArcId() const { return -1; }
     659
    627660      void first(Node&) const {}
    628661      void next(Node&) const {}
    … …  
    640673      void nextIn(Arc&) const {}
    641674
    642 
    643675      void firstInc(Edge &, bool &, const Node &) const {}
    644676      void nextInc(Edge &, bool &) const {}
     677
     678      // The second parameter is dummy.
     679      Node fromId(int, Node) const { return INVALID; }
     680      // The second parameter is dummy.
     681      Edge fromId(int, Edge) const { return INVALID; }
     682      // The second parameter is dummy.
     683      Arc fromId(int, Arc) const { return INVALID; }
     684
     685      // Dummy parameter.
     686      int maxId(Node) const { return -1; }
     687      // Dummy parameter.
     688      int maxId(Edge) const { return -1; }
     689      // Dummy parameter.
     690      int maxId(Arc) const { return -1; }
    645691
    646692      /// \brief Base node of the iterator
    … …  
    675721      ///
    676722      /// Returns the base node of the iterator
    677       Node baseNode(IncArcIt) const {
     723      Node baseNode(IncEdgeIt) const {
    678724        return INVALID;
    679725      }
    … …  
    682728      ///
    683729      /// Returns the running node of the iterator
    684       Node runningNode(IncArcIt) const {
     730      Node runningNode(IncEdgeIt) const {
    685731        return INVALID;
    686732      }
    … …  
    690736        void constraints() {
    691737          checkConcept<IterableGraphComponent<>, Graph>();
     738          checkConcept<IDableGraphComponent<>, Graph>();
    692739          checkConcept<MappableGraphComponent<>, Graph>();
    693740        }

  • lemon/concepts/graph_components.h

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

  • lemon/concepts/maps.h

    r51 r79  
    3030
    3131  namespace concepts {
    32  
     32
    3333    /// \addtogroup concept
    3434    /// @{
    … …  
    4343    public:
    4444      /// The key type of the map.
    45       typedef K Key;   
    46       /// The value type of the map. (The type of objects associated with the keys).
    47       typedef T Value;
    48 
    49       /// Returns the value associated with a key.
    50 
    51       /// Returns the value associated with a key.
    52       /// \bug Value shouldn't need to be default constructible.
    53       ///
    54       Value operator[](const Key &) const {return Value();}
     45      typedef K Key;
     46      /// The value type of the map. (The type of objects associated with the keys).
     47      typedef T Value;
     48
     49      /// Returns the value associated with the given key.
     50
     51      /// Returns the value associated with the given key.
     52      /// \bug Value shouldn't need to be default constructible.
     53      Value operator[](const Key &) const { return Value(); }
    5554
    5655      template<typename _ReadMap>
    5756      struct Constraints {
    58 
    5957        void constraints() {
    6058          Value val = m[key];
    6159          val = m[key];
    62           typename _ReadMap::Value own_val = m[own_key];
    63           own_val = m[own_key];
    64 
    65           ignore_unused_variable_warning(val);
    66           ignore_unused_variable_warning(own_val);
    67           ignore_unused_variable_warning(key);
    68         }
    69         Key& key;
    70         typename _ReadMap::Key& own_key;
    71         _ReadMap& m;
    72       };
    73      
    74     };
    75 
    76 
    77     /// Writable map concept
    78    
    79     /// Writable map concept.
    80     ///
    81     template<typename K, typename T>
    82     class WriteMap
    83     {
    84     public:
    85       /// The key type of the map.
    86       typedef K Key;   
    87       /// The value type of the map. (The type of objects associated with the keys).
    88       typedef T Value;
    89 
    90       /// Sets the value associated with a key.
    91       void set(const Key &,const Value &) {}
    92 
    93       ///Default constructor
    94       WriteMap() {}
    95 
    96       template <typename _WriteMap>
    97       struct Constraints {
    98         void constraints() {
    99           // No constraints for constructor.
    100           m.set(key, val);
    101           m.set(own_key, own_val);
     60          typename _ReadMap::Value own_val = m[own_key];
     61          own_val = m[own_key];
     62
    10263          ignore_unused_variable_warning(key);
    10364          ignore_unused_variable_warning(val);
    … …  
    10566          ignore_unused_variable_warning(own_val);
    10667        }
    107 
    108         Value& val;
    109         typename _WriteMap::Value own_val;
    110         Key& key;
    111         typename _WriteMap::Key& own_key;
     68        const Key& key;
     69        const typename _ReadMap::Key& own_key;
     70        const _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 the given 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          m.set(key, val);
     99          m.set(own_key, own_val);
     100
     101          ignore_unused_variable_warning(key);
     102          ignore_unused_variable_warning(val);
     103          ignore_unused_variable_warning(own_key);
     104          ignore_unused_variable_warning(own_val);
     105        }
     106        const Key& key;
     107        const Value& val;
     108        const typename _WriteMap::Key& own_key;
     109        const typename _WriteMap::Value own_val;
    112110        _WriteMap& m;
    113 
    114111      };
    115112    };
    116113
    117114    /// Read/writable map concept
    118    
     115
    119116    /// Read/writable map concept.
    120117    ///
    … …  
    125122    public:
    126123      /// The key type of the map.
    127       typedef K Key;   
    128       /// The value type of the map. (The type of objects associated with the keys).
    129       typedef T Value;
    130 
    131       /// Returns the value associated with a key.
    132       Value operator[](const Key &) const {return Value();}
    133       /// Sets the value associated with a key.
    134       void set(const Key & ,const Value &) {}
     124      typedef K Key;
     125      /// The value type of the map. (The type of objects associated with the keys).
     126      typedef T Value;
     127
     128      /// Returns the value associated with the given key.
     129      Value operator[](const Key &) const { return Value(); }
     130
     131      /// Sets the value associated with the given key.
     132      void set(const Key &, const Value &) {}
    135133
    136134      template<typename _ReadWriteMap>
    … …  
    142140      };
    143141    };
    144  
    145  
     142
     143
    146144    /// Dereferable map concept
    147    
     145
    148146    /// Dereferable map concept.
    149147    ///
    150     /// \todo Rethink this concept.
    151148    template<typename K, typename T, typename R, typename CR>
    152149    class ReferenceMap : public ReadWriteMap<K,T>
    … …  
    156153      typedef True ReferenceMapTag;
    157154      /// The key type of the map.
    158       typedef K Key;   
     155      typedef K Key;
    159156      /// The value type of the map. (The type of objects associated with the keys).
    160157      typedef T Value;
    … …  
    168165    public:
    169166
    170       ///Returns a reference to the value associated with a key.
     167      /// Returns a reference to the value associated with the given key.
    171168      Reference operator[](const Key &) { return tmp; }
    172       ///Returns a const reference to the value associated with a key.
     169
     170      /// Returns a const reference to the value associated with the given key.
    173171      ConstReference operator[](const Key &) const { return tmp; }
    174       /// Sets the value associated with a key.
     172
     173      /// Sets the value associated with the given key.
    175174      void set(const Key &k,const Value &t) { operator[](k)=t; }
    176175
    177176      template<typename _ReferenceMap>
    178       struct ReferenceMapConcept {
    179 
    180         void constraints() {
    181           checkConcept<ReadWriteMap, _ReferenceMap >();
     177      struct Constraints {
     178        void constraints() {
     179          checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
     180          ref = m[key];
    182181          m[key] = val;
    183           val  = m[key];
    184182          m[key] = ref;
    185           ref = m[key];
     183          m[key] = cref;
     184          own_ref = m[own_key];
    186185          m[own_key] = own_val;
    187           own_val  = m[own_key];
    188186          m[own_key] = own_ref;
    189           own_ref = m[own_key];           
    190         }
    191 
    192         typename _ReferenceMap::Key& own_key;
     187          m[own_key] = own_cref;
     188          m[key] = m[own_key];
     189          m[own_key] = m[key];
     190        }
     191        const Key& key;
     192        Value& val;
     193        Reference ref;
     194        ConstReference cref;
     195        const typename _ReferenceMap::Key& own_key;
    193196        typename _ReferenceMap::Value& own_val;
    194         typename _ReferenceMap::Reference& own_ref;
    195         Key& key;
    196         Value& val;
    197         Reference& ref;
     197        typename _ReferenceMap::Reference own_ref;
     198        typename _ReferenceMap::ConstReference own_cref;
    198199        _ReferenceMap& m;
    199200      };

  • lemon/list_graph.h

    r57 r73  
    112112
    113113
    114     void first(Arc& e) const {
     114    void first(Arc& arc) const {
    115115      int n;
    116116      for(n = first_node;
    117117          n!=-1 && nodes[n].first_in == -1;
    118118          n = nodes[n].next);
    119       e.id = (n == -1) ? -1 : nodes[n].first_in;
     119      arc.id = (n == -1) ? -1 : nodes[n].first_in;
    120120    }
    121121
    … …  
    294294  typedef DigraphExtender<ListDigraphBase> ExtendedListDigraphBase;
    295295
    296   /// \addtogroup digraphs
     296  /// \addtogroup graphs
    297297  /// @{
    298298
    299   ///A list digraph class.
    300 
    301   ///This is a simple and fast digraph implementation.
     299  ///A general directed graph structure.
     300
     301  ///\ref ListDigraph is a simple and fast <em>directed graph</em>
     302  ///implementation based on static linked lists that are stored in
     303  ///\c std::vector structures.   
    302304  ///
    303305  ///It conforms to the \ref concepts::Digraph "Digraph concept" and it
    304   ///also provides several additional useful extra functionalities.
    305   ///The most of the member functions and nested classes are
    306   ///documented only in the concept class.
     306  ///also provides several useful additional functionalities.
     307  ///Most of the member functions and nested classes are documented
     308  ///only in the concept class.
    307309  ///
    308310  ///An important extra feature of this digraph implementation is that
    309311  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
    310312  ///
    311   ///\sa concepts::Digraph.
     313  ///\sa concepts::Digraph
    312314
    313315  class ListDigraph : public ExtendedListDigraphBase {
    314316  private:
    315     ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.
    316    
    317     ///ListDigraph is \e not copy constructible. Use DigraphCopy() instead.
     317    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
     318   
     319    ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.
    318320    ///
    319321    ListDigraph(const ListDigraph &) :ExtendedListDigraphBase() {};
    320322    ///\brief Assignment of ListDigraph to another one is \e not allowed.
    321     ///Use DigraphCopy() instead.
     323    ///Use copyDigraph() instead.
    322324
    323325    ///Assignment of ListDigraph to another one is \e not allowed.
    324     ///Use DigraphCopy() instead.
     326    ///Use copyDigraph() instead.
    325327    void operator=(const ListDigraph &) {}
    326328  public:
    … …  
    336338    ///Add a new node to the digraph.
    337339   
    338     /// \return the new node.
    339     ///
     340    ///Add a new node to the digraph.
     341    ///\return the new node.
    340342    Node addNode() { return Parent::addNode(); }
    341343
    … …  
    349351    }
    350352
    351     /// Changes the target of \c e to \c n
    352 
    353     /// Changes the target of \c e to \c n
     353    /// Change the target of \c e to \c n
     354
     355    /// Change the target of \c e to \c n
    354356    ///
    355357    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing
    356358    ///the changed arc remain valid. However <tt>InArcIt</tt>s are
    357359    ///invalidated.
     360    ///
    358361    ///\warning This functionality cannot be used together with the Snapshot
    359362    ///feature.
    … …  
    361364      Parent::changeTarget(e,n);
    362365    }
    363     /// Changes the source of \c e to \c n
    364 
    365     /// Changes the source of \c e to \c n
     366    /// Change the source of \c e to \c n
     367
     368    /// Change the source of \c e to \c n
    366369    ///
    367370    ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s referencing
    368371    ///the changed arc remain valid. However <tt>OutArcIt</tt>s are
    369372    ///invalidated.
     373    ///
    370374    ///\warning This functionality cannot be used together with the Snapshot
    371375    ///feature.
    … …  
    379383    ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are
    380384    ///invalidated.
     385    ///
    381386    ///\warning This functionality cannot be used together with the Snapshot
    382387    ///feature.
    … …  
    387392    }
    388393
    389     /// Using this it is possible to avoid the superfluous memory
     394    /// Reserve memory for nodes.
     395
     396    /// Using this function it is possible to avoid the superfluous memory
    390397    /// allocation: if you know that the digraph you want to build will
    391398    /// be very large (e.g. it will contain millions of nodes and/or arcs)
    … …  
    395402    void reserveNode(int n) { nodes.reserve(n); };
    396403
    397     /// \brief Using this it is possible to avoid the superfluous memory
    398     /// allocation.
    399 
    400     /// Using this it is possible to avoid the superfluous memory
     404    /// Reserve memory for arcs.
     405
     406    /// Using this function it is possible to avoid the superfluous memory
    401407    /// allocation: if you know that the digraph you want to build will
    402408    /// be very large (e.g. it will contain millions of nodes and/or arcs)
    … …  
    409415
    410416    ///This function contracts two nodes.
    411     ///
    412417    ///Node \p b will be removed but instead of deleting
    413418    ///incident arcs, they will be joined to \p a.
    … …  
    415420    ///means that loops will be removed.
    416421    ///
    417     ///\note The <tt>ArcIt</tt>s
    418     ///referencing a moved arc remain
     422    ///\note The <tt>ArcIt</tt>s referencing a moved arc remain
    419423    ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s
    420424    ///may be invalidated.
     425    ///
    421426    ///\warning This functionality cannot be used together with the Snapshot
    422427    ///feature.
    … …  
    453458    ///
    454459    ///\warning This functionality cannot be used together with the
    455     ///Snapshot feature.  \todo It could be implemented in a bit
    456     ///faster way.
     460    ///Snapshot feature.
     461    ///
     462    ///\todo It could be implemented in a bit faster way.
    457463    Node split(Node n, bool connect = true) {
    458464      Node b = addNode();
    … …  
    472478    ///the digraph, then the original arc is re-targeted to \c
    473479    ///b. Finally an arc from \c b to the original target is added.
    474     ///\return The newly created node. 
    475     ///\warning This functionality
    476     ///cannot be used together with the Snapshot feature.
     480    ///
     481    ///\return The newly created node.
     482    ///
     483    ///\warning This functionality cannot be used together with the
     484    ///Snapshot feature.
    477485    Node split(Arc e) {
    478486      Node b = addNode();
    … …  
    483491     
    484492    /// \brief Class to make a snapshot of the digraph and restore
    485     /// to it later.
    486     ///
    487     /// Class to make a snapshot of the digraph and to restore it
    488     /// later.
     493    /// it later.
     494    ///
     495    /// Class to make a snapshot of the digraph and restore it later.
    489496    ///
    490497    /// The newly added nodes and arcs can be removed using the
    491498    /// restore() function.
    492499    ///
    493     /// \warning Arc and node deletions cannot be restored. This
    494     /// events invalidate the snapshot.
     500    /// \warning Arc and node deletions and other modifications (e.g.
     501    /// contracting, splitting, reversing arcs or nodes) cannot be
     502    /// restored. These events invalidate the snapshot.
    495503    class Snapshot {
    496504    protected:
    … …  
    777785      Edge() {}
    778786      Edge (Invalid) { id = -1; }
    779       bool operator==(const Edge& arc) const {return id == arc.id;}
    780       bool operator!=(const Edge& arc) const {return id != arc.id;}
    781       bool operator<(const Edge& arc) const {return id < arc.id;}
     787      bool operator==(const Edge& edge) const {return id == edge.id;}
     788      bool operator!=(const Edge& edge) const {return id != edge.id;}
     789      bool operator<(const Edge& edge) const {return id < edge.id;}
    782790    };
    783791
    … …  
    910918
    911919    void firstInc(Edge &e, bool& d, const Node& v) const {
    912       int de = nodes[v.id].first_out;
    913       if (de != -1 ) {
    914         e.id = de / 2;
    915         d = ((de & 1) == 1);
     920      int a = nodes[v.id].first_out;
     921      if (a != -1 ) {
     922        e.id = a / 2;
     923        d = ((a & 1) == 1);
    916924      } else {
    917925        e.id = -1;
    … …  
    920928    }
    921929    void nextInc(Edge &e, bool& d) const {
    922       int de = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
    923       if (de != -1 ) {
    924         e.id = de / 2;
    925         d = ((de & 1) == 1);
     930      int a = (arcs[(e.id * 2) | (d ? 1 : 0)].next_out);
     931      if (a != -1 ) {
     932        e.id = a / 2;
     933        d = ((a & 1) == 1);
    926934      } else {
    927935        e.id = -1;
    … …  
    10091017    }
    10101018   
    1011     void erase(const Edge& arc) {
    1012       int n = arc.id * 2;
     1019    void erase(const Edge& edge) {
     1020      int n = edge.id * 2;
    10131021     
    10141022      if (arcs[n].next_out != -1) {
    … …  
    10901098  };
    10911099
    1092 //   typedef GraphExtender<UndirDigraphExtender<ListDigraphBase> >
    1093 //   ExtendedListGraphBase;
    1094 
    10951100  typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
    10961101
    10971102
    1098 
    1099   /// \addtogroup digraphs
     1103  /// \addtogroup graphs
    11001104  /// @{
    11011105
    1102   ///An undirected list digraph class.
    1103 
    1104   ///This is a simple and fast undirected digraph implementation.
     1106  ///A general undirected graph structure.
     1107
     1108  ///\ref ListGraph is a simple and fast <em>undirected graph</em>
     1109  ///implementation based on static linked lists that are stored in
     1110  ///\c std::vector structures.
    11051111  ///
    1106   ///An important extra feature of this digraph implementation is that
     1112  ///It conforms to the \ref concepts::Graph "Graph concept" and it
     1113  ///also provides several useful additional functionalities.
     1114  ///Most of the member functions and nested classes are documented
     1115  ///only in the concept class.
     1116  ///
     1117  ///An important extra feature of this graph implementation is that
    11071118  ///its maps are real \ref concepts::ReferenceMap "reference map"s.
    11081119  ///
    1109   ///It conforms to the
    1110   ///\ref concepts::Graph "Graph concept".
    1111   ///
    1112   ///\sa concepts::Graph.
    1113   ///
     1120  ///\sa concepts::Graph
     1121
    11141122  class ListGraph : public ExtendedListGraphBase {
    11151123  private:
    1116     ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
    1117 
    1118     ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
     1124    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
     1125
     1126    ///ListGraph is \e not copy constructible. Use copyGraph() instead.
    11191127    ///
    11201128    ListGraph(const ListGraph &) :ExtendedListGraphBase()  {};
    11211129    ///\brief Assignment of ListGraph to another one is \e not allowed.
    1122     ///Use GraphCopy() instead.
     1130    ///Use copyGraph() instead.
    11231131
    11241132    ///Assignment of ListGraph to another one is \e not allowed.
    1125     ///Use GraphCopy() instead.
     1133    ///Use copyGraph() instead.
    11261134    void operator=(const ListGraph &) {}
    11271135  public:
    … …  
    11341142    typedef ExtendedListGraphBase Parent;
    11351143
    1136     typedef Parent::OutArcIt IncArcIt;
    1137 
    1138     /// \brief Add a new node to the digraph.
    1139     ///
     1144    typedef Parent::OutArcIt IncEdgeIt;
     1145
     1146    /// \brief Add a new node to the graph.
     1147    ///
     1148    /// Add a new node to the graph.
    11401149    /// \return the new node.
    1141     ///
    11421150    Node addNode() { return Parent::addNode(); }
    11431151
    1144     /// \brief Add a new edge to the digraph.
    1145     ///
    1146     /// Add a new arc to the digraph with source node \c s
     1152    /// \brief Add a new edge to the graph.
     1153    ///
     1154    /// Add a new edge to the graph with source node \c s
    11471155    /// and target node \c t.
    11481156    /// \return the new edge.
    … …  
    11501158      return Parent::addEdge(s, t);
    11511159    }
    1152     /// \brief Changes the source of \c e to \c n
    1153     ///
    1154     /// Changes the source of \c e to \c n
     1160    /// \brief Change the source of \c e to \c n
     1161    ///
     1162    /// This function changes the source of \c e to \c n.
    11551163    ///
    11561164    ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
    11571165    ///referencing the changed arc remain
    11581166    ///valid. However <tt>OutArcIt</tt>s are invalidated.
     1167    ///
     1168    ///\warning This functionality cannot be used together with the
     1169    ///Snapshot feature.
    11591170    void changeSource(Edge e, Node n) {
    11601171      Parent::changeSource(e,n);
    11611172    }   
    1162     /// \brief Changes the target of \c e to \c n
    1163     ///
    1164     /// Changes the target of \c e to \c n
     1173    /// \brief Change the target of \c e to \c n
     1174    ///
     1175    /// This function changes the target of \c e to \c n.
    11651176    ///
    11661177    /// \note The <tt>ArcIt</tt>s referencing the changed arc remain
    11671178    /// valid. However the other iterators may be invalidated.
     1179    ///
     1180    ///\warning This functionality cannot be used together with the
     1181    ///Snapshot feature.
    11681182    void changeTarget(Edge e, Node n) {
    11691183      Parent::changeTarget(e,n);
    11701184    }
    1171     /// \brief Changes the source of \c e to \c n
    1172     ///
    1173     /// Changes the source of \c e to \c n. It changes the proper
    1174     /// node of the represented edge.
     1185    /// \brief Change the source of \c e to \c n
     1186    ///
     1187    /// This function changes the source of \c e to \c n.
     1188    /// It also changes the proper node of the represented edge.
    11751189    ///
    11761190    ///\note The <tt>ArcIt</tt>s and <tt>InArcIt</tt>s
    11771191    ///referencing the changed arc remain
    11781192    ///valid. However <tt>OutArcIt</tt>s are invalidated.
     1193    ///
     1194    ///\warning This functionality cannot be used together with the
     1195    ///Snapshot feature.
    11791196    void changeSource(Arc e, Node n) {
    11801197      if (Parent::direction(e)) {
    … …  
    11841201      }
    11851202    }
    1186     /// \brief Changes the target of \c e to \c n
    1187     ///
    1188     /// Changes the target of \c e to \c n. It changes the proper
    1189     /// node of the represented edge.
     1203    /// \brief Change the target of \c e to \c n
     1204    ///
     1205    /// This function changes the target of \c e to \c n.
     1206    /// It also changes the proper node of the represented edge.
    11901207    ///
    11911208    ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s
    11921209    ///referencing the changed arc remain
    11931210    ///valid. However <tt>InArcIt</tt>s are invalidated.
     1211    ///
     1212    ///\warning This functionality cannot be used together with the
     1213    ///Snapshot feature.
    11941214    void changeTarget(Arc e, Node n) {
    11951215      if (Parent::direction(e)) {
    … …  
    12021222    ///
    12031223    /// This function contracts two nodes.
    1204     ///
    12051224    /// Node \p b will be removed but instead of deleting
    12061225    /// its neighboring arcs, they will be joined to \p a.
    … …  
    12101229    /// \note The <tt>ArcIt</tt>s referencing a moved arc remain
    12111230    /// valid.
     1231    ///
     1232    ///\warning This functionality cannot be used together with the
     1233    ///Snapshot feature.
    12121234    void contract(Node a, Node b, bool r = true) {
    1213       for(IncArcIt e(*this, b); e!=INVALID;) {
    1214         IncArcIt f = e; ++f;
     1235      for(IncEdgeIt e(*this, b); e!=INVALID;) {
     1236        IncEdgeIt f = e; ++f;
    12151237        if (r && runningNode(e) == a) {
    12161238          erase(e);
    … …  
    12261248
    12271249
    1228     /// \brief Class to make a snapshot of the digraph and restore
    1229     /// to it later.
    1230     ///
    1231     /// Class to make a snapshot of the digraph and to restore it
    1232     /// later.
     1250    /// \brief Class to make a snapshot of the graph and restore
     1251    /// it later.
     1252    ///
     1253    /// Class to make a snapshot of the graph and restore it later.
    12331254    ///
    12341255    /// The newly added nodes and edges can be removed
    12351256    /// using the restore() function.
    12361257    ///
    1237     /// \warning Arc and node deletions cannot be restored. This
    1238     /// events invalidate the snapshot.
     1258    /// \warning Edge and node deletions and other modifications
     1259    /// (e.g. changing nodes of edges, contracting nodes) cannot be
     1260    /// restored. These events invalidate the snapshot.
    12391261    class Snapshot {
    12401262    protected:
    … …  
    13041326      protected:
    13051327
    1306         virtual void add(const Edge& arc) {
    1307           snapshot.addEdge(arc);
    1308         }
    1309         virtual void add(const std::vector<Edge>& arcs) {
    1310           for (int i = arcs.size() - 1; i >= 0; ++i) {
    1311             snapshot.addEdge(arcs[i]);
    1312           }
    1313         }
    1314         virtual void erase(const Edge& arc) {
    1315           snapshot.eraseEdge(arc);
    1316         }
    1317         virtual void erase(const std::vector<Edge>& arcs) {
    1318           for (int i = 0; i < int(arcs.size()); ++i) {
    1319             snapshot.eraseEdge(arcs[i]);
     1328        virtual void add(const Edge& edge) {
     1329          snapshot.addEdge(edge);
     1330        }
     1331        virtual void add(const std::vector<Edge>& edges) {
     1332          for (int i = edges.size() - 1; i >= 0; ++i) {
     1333            snapshot.addEdge(edges[i]);
     1334          }
     1335        }
     1336        virtual void erase(const Edge& edge) {
     1337          snapshot.eraseEdge(edge);
     1338        }
     1339        virtual void erase(const std::vector<Edge>& edges) {
     1340          for (int i = 0; i < int(edges.size()); ++i) {
     1341            snapshot.eraseEdge(edges[i]);
    13201342          }
    13211343        }
    13221344        virtual void build() {
    1323           Edge arc;
    1324           std::vector<Edge> arcs;
    1325           for (notifier()->first(arc); arc != INVALID;
    1326                notifier()->next(arc)) {
    1327             arcs.push_back(arc);
    1328           }
    1329           for (int i = arcs.size() - 1; i >= 0; --i) {
    1330             snapshot.addEdge(arcs[i]);
     1345          Edge edge;
     1346          std::vector<Edge> edges;
     1347          for (notifier()->first(edge); edge != INVALID;
     1348               notifier()->next(edge)) {
     1349            edges.push_back(edge);
     1350          }
     1351          for (int i = edges.size() - 1; i >= 0; --i) {
     1352            snapshot.addEdge(edges[i]);
    13311353          }
    13321354        }
    13331355        virtual void clear() {
    1334           Edge arc;
    1335           for (notifier()->first(arc); arc != INVALID;
    1336                notifier()->next(arc)) {
    1337             snapshot.eraseEdge(arc);
     1356          Edge edge;
     1357          for (notifier()->first(edge); edge != INVALID;
     1358               notifier()->next(edge)) {
     1359            snapshot.eraseEdge(edge);
    13381360          }
    13391361        }
    … …  
    13411363        Snapshot& snapshot;
    13421364      };
    1343      
    1344       ListGraph *digraph;
     1365
     1366      ListGraph *graph;
    13451367
    13461368      NodeObserverProxy node_observer_proxy;
    1347       EdgeObserverProxy arc_observer_proxy;
     1369      EdgeObserverProxy edge_observer_proxy;
    13481370
    13491371      std::list<Node> added_nodes;
    1350       std::list<Edge> added_arcs;
     1372      std::list<Edge> added_edges;
    13511373
    13521374
    … …  
    13591381        if (it == added_nodes.end()) {
    13601382          clear();
    1361           arc_observer_proxy.detach();
     1383          edge_observer_proxy.detach();
    13621384          throw NodeNotifier::ImmediateDetach();
    13631385        } else {
    … …  
    13661388      }
    13671389
    1368       void addEdge(const Edge& arc) {
    1369         added_arcs.push_front(arc);       
    1370       }
    1371       void eraseEdge(const Edge& arc) {
     1390      void addEdge(const Edge& edge) {
     1391        added_edges.push_front(edge);       
     1392      }
     1393      void eraseEdge(const Edge& edge) {
    13721394        std::list<Edge>::iterator it =
    1373           std::find(added_arcs.begin(), added_arcs.end(), arc);
    1374         if (it == added_arcs.end()) {
     1395          std::find(added_edges.begin(), added_edges.end(), edge);
     1396        if (it == added_edges.end()) {
    13751397          clear();
    13761398          node_observer_proxy.detach();
    13771399          throw EdgeNotifier::ImmediateDetach();
    13781400        } else {
    1379           added_arcs.erase(it);
    1380         }       
    1381       }
    1382 
    1383       void attach(ListGraph &_digraph) {
    1384         digraph = &_digraph;
    1385         node_observer_proxy.attach(digraph->notifier(Node()));
    1386         arc_observer_proxy.attach(digraph->notifier(Edge()));
     1401          added_edges.erase(it);
     1402        }
     1403      }
     1404
     1405      void attach(ListGraph &_graph) {
     1406        graph = &_graph;
     1407        node_observer_proxy.attach(graph->notifier(Node()));
     1408        edge_observer_proxy.attach(graph->notifier(Edge()));
    13871409      }
    13881410           
    13891411      void detach() {
    13901412        node_observer_proxy.detach();
    1391         arc_observer_proxy.detach();
     1413        edge_observer_proxy.detach();
    13921414      }
    13931415
    … …  
    13981420      void clear() {
    13991421        added_nodes.clear();
    1400         added_arcs.clear();       
     1422        added_edges.clear();       
    14011423      }
    14021424
    … …  
    14081430      /// To actually make a snapshot you must call save().
    14091431      Snapshot()
    1410         : digraph(0), node_observer_proxy(*this),
    1411           arc_observer_proxy(*this) {}
     1432        : graph(0), node_observer_proxy(*this),
     1433          edge_observer_proxy(*this) {}
    14121434     
    14131435      /// \brief Constructor that immediately makes a snapshot.
    14141436      ///     
    1415       /// This constructor immediately makes a snapshot of the digraph.
    1416       /// \param _digraph The digraph we make a snapshot of.
    1417       Snapshot(ListGraph &_digraph)
     1437      /// This constructor immediately makes a snapshot of the graph.
     1438      /// \param _graph The graph we make a snapshot of.
     1439      Snapshot(ListGraph &_graph)
    14181440        : node_observer_proxy(*this),
    1419           arc_observer_proxy(*this) {
    1420         attach(_digraph);
     1441          edge_observer_proxy(*this) {
     1442        attach(_graph);
    14211443      }
    14221444     
    14231445      /// \brief Make a snapshot.
    14241446      ///
    1425       /// Make a snapshot of the digraph.
     1447      /// Make a snapshot of the graph.
    14261448      ///
    14271449      /// This function can be called more than once. In case of a repeated
    14281450      /// call, the previous snapshot gets lost.
    1429       /// \param _digraph The digraph we make the snapshot of.
    1430       void save(ListGraph &_digraph) {
     1451      /// \param _graph The graph we make the snapshot of.
     1452      void save(ListGraph &_graph) {
    14311453        if (attached()) {
    14321454          detach();
    14331455          clear();
    14341456        }
    1435         attach(_digraph);
     1457        attach(_graph);
    14361458      }
    14371459     
    … …  
    14411463      void restore() {
    14421464        detach();
    1443         for(std::list<Edge>::iterator it = added_arcs.begin();
    1444             it != added_arcs.end(); ++it) {
    1445           digraph->erase(*it);
     1465        for(std::list<Edge>::iterator it = added_edges.begin();
     1466            it != added_edges.end(); ++it) {
     1467          graph->erase(*it);
    14461468        }
    14471469        for(std::list<Node>::iterator it = added_nodes.begin();
    14481470            it != added_nodes.end(); ++it) {
    1449           digraph->erase(*it);
     1471          graph->erase(*it);
    14501472        }
    14511473        clear();

  • lemon/maps.h

    r54 r82  
    2525
    2626#include <lemon/bits/utility.h>
    27 // #include <lemon/bits/traits.h>
     27#include <lemon/bits/traits.h>
    2828
    2929///\file
    3030///\ingroup maps
    3131///\brief Miscellaneous property maps
    32 ///
     32
    3333#include <map>
    3434
    … …  
    4040  /// Base class of maps.
    4141
    42   /// Base class of maps.
    43   /// It provides the necessary <tt>typedef</tt>s required by the map concept.
    44   template<typename K, typename T>
     42  /// Base class of maps. It provides the necessary type definitions
     43  /// required by the map %concepts.
     44  template<typename K, typename V>
    4545  class MapBase {
    4646  public:
    47     /// The key type of the map.
     47    /// \biref The key type of the map.
    4848    typedef K Key;
    49     /// The value type of the map. (The type of objects associated with the keys).
    50     typedef T Value;
    51   };
     49    /// \brief The value type of the map.
     50    /// (The type of objects associated with the keys).
     51    typedef V Value;
     52  };
     53
    5254
    5355  /// Null map. (a.k.a. DoNothingMap)
    5456
    5557  /// This map can be used if you have to provide a map only for
    56   /// its type definitions, or if you have to provide a writable map, 
    57   /// but data written to it is not required (i.e. it will be sent to 
     58  /// its type definitions, or if you have to provide a writable map,
     59  /// but data written to it is not required (i.e. it will be sent to
    5860  /// <tt>/dev/null</tt>).
    59   template<typename K, typename T>
    60   class NullMap : public MapBase<K, T> {
    61   public:
    62     typedef MapBase<K, T> Parent;
    63     typedef typename Parent::Key Key;
    64     typedef typename Parent::Value Value;
    65    
     61  /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     62  ///
     63  /// \sa ConstMap
     64  template<typename K, typename V>
     65  class NullMap : public MapBase<K, V> {
     66  public:
     67    typedef MapBase<K, V> Parent;
     68    typedef typename Parent::Key Key;
     69    typedef typename Parent::Value Value;
     70
    6671    /// Gives back a default constructed element.
    67     T operator[](const K&) const { return T(); }
     72    Value operator[](const Key&) const { return Value(); }
    6873    /// Absorbs the value.
    69     void set(const K&, const T&) {}
    70   };
    71 
    72   ///Returns a \c NullMap class
    73 
    74   ///This function just returns a \c NullMap class.
    75   ///\relates NullMap
    76   template <typename K, typename V> 
     74    void set(const Key&, const Value&) {}
     75  };
     76
     77  /// Returns a \ref NullMap class
     78
     79  /// This function just returns a \ref NullMap class.
     80  /// \relates NullMap
     81  template <typename K, typename V>
    7782  NullMap<K, V> nullMap() {
    7883    return NullMap<K, V>();
    … …  
    8287  /// Constant map.
    8388
    84   /// This is a \ref concepts::ReadMap "readable" map which assigns a
    85   /// specified value to each key.
    86   /// In other aspects it is equivalent to \c NullMap.
    87   template<typename K, typename T>
    88   class ConstMap : public MapBase<K, T> {
     89  /// This \ref concepts::ReadMap "readable map" assigns a specified
     90  /// value to each key.
     91  ///
     92  /// In other aspects it is equivalent to \ref NullMap.
     93  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
     94  /// concept, but it absorbs the data written to it.
     95  ///
     96  /// The simplest way of using this map is through the constMap()
     97  /// function.
     98  ///
     99  /// \sa NullMap
     100  /// \sa IdentityMap
     101  template<typename K, typename V>
     102  class ConstMap : public MapBase<K, V> {
    89103  private:
    90     T v;
    91   public:
    92 
    93     typedef MapBase<K, T> Parent;
     104    V _value;
     105  public:
     106    typedef MapBase<K, V> Parent;
    94107    typedef typename Parent::Key Key;
    95108    typedef typename Parent::Value Value;
    … …  
    98111
    99112    /// Default constructor.
    100     /// The value of the map will be uninitialized.
    101     /// (More exactly it will be default constructed.)
     113    /// The value of the map will be default constructed.
    102114    ConstMap() {}
    103    
     115
    104116    /// Constructor with specified initial value
    105117
    106118    /// Constructor with specified initial value.
    107     /// \param _v is the initial value of the map.
    108     ConstMap(const T &_v) : v(_v) {}
    109    
    110     ///\e
    111     T operator[](const K&) const { return v; }
    112 
    113     ///\e
    114     void setAll(const T &t) {
    115       v = t;
    116     }   
    117 
    118     template<typename T1>
    119     ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
    120   };
    121 
    122   ///Returns a \c ConstMap class
    123 
    124   ///This function just returns a \c ConstMap class.
    125   ///\relates ConstMap
    126   template<typename K, typename V>
     119    /// \param v is the initial value of the map.
     120    ConstMap(const Value &v) : _value(v) {}
     121
     122    /// Gives back the specified value.
     123    Value operator[](const Key&) const { return _value; }
     124
     125    /// Absorbs the value.
     126    void set(const Key&, const Value&) {}
     127
     128    /// Sets the value that is assigned to each key.
     129    void setAll(const Value &v) {
     130      _value = v;
     131    }
     132
     133    template<typename V1>
     134    ConstMap(const ConstMap<K, V1> &, const Value &v) : _value(v) {}
     135  };
     136
     137  /// Returns a \ref ConstMap class
     138
     139  /// This function just returns a \ref ConstMap class.
     140  /// \relates ConstMap
     141  template<typename K, typename V>
    127142  inline ConstMap<K, V> constMap(const V &v) {
    128143    return ConstMap<K, V>(v);
    … …  
    131146
    132147  template<typename T, T v>
    133   struct Const { };
     148  struct Const {};
    134149
    135150  /// Constant map with inlined constant value.
    136151
    137   /// This is a \ref concepts::ReadMap "readable" map which assigns a
    138   /// specified value to each key.
    139   /// In other aspects it is equivalent to \c NullMap.
     152  /// This \ref concepts::ReadMap "readable map" assigns a specified
     153  /// value to each key.
     154  ///
     155  /// In other aspects it is equivalent to \ref NullMap.
     156  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
     157  /// concept, but it absorbs the data written to it.
     158  ///
     159  /// The simplest way of using this map is through the constMap()
     160  /// function.
     161  ///
     162  /// \sa NullMap
     163  /// \sa IdentityMap
    140164  template<typename K, typename V, V v>
    141165  class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
    … …  
    145169    typedef typename Parent::Value Value;
    146170
    147     ConstMap() { }
    148     ///\e
    149     V operator[](const K&) const { return v; }
    150     ///\e
    151     void set(const K&, const V&) { }
    152   };
    153 
    154   ///Returns a \c ConstMap class with inlined value
    155 
    156   ///This function just returns a \c ConstMap class with inlined value.
    157   ///\relates ConstMap
    158   template<typename K, typename V, V v>
     171    /// Constructor.
     172    ConstMap() {}
     173
     174    /// Gives back the specified value.
     175    Value operator[](const Key&) const { return v; }
     176
     177    /// Absorbs the value.
     178    void set(const Key&, const Value&) {}
     179  };
     180
     181  /// Returns a \ref ConstMap class with inlined constant value
     182
     183  /// This function just returns a \ref ConstMap class with inlined
     184  /// constant value.
     185  /// \relates ConstMap
     186  template<typename K, typename V, V v>
    159187  inline ConstMap<K, Const<V, v> > constMap() {
    160188    return ConstMap<K, Const<V, v> >();
    161189  }
    162190
    163   ///Map based on \c std::map
    164 
    165   ///This is essentially a wrapper for \c std::map with addition that
    166   ///you can specify a default value different from \c Value().
    167   ///It meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
    168   template <typename K, typename T, typename Compare = std::less<K> >
    169   class StdMap : public MapBase<K, T> {
    170     template <typename K1, typename T1, typename C1>
    171     friend class StdMap;
    172   public:
    173 
    174     typedef MapBase<K, T> Parent;
    175     ///Key type
    176     typedef typename Parent::Key Key;
    177     ///Value type
    178     typedef typename Parent::Value Value;
    179     ///Reference Type
    180     typedef T& Reference;
    181     ///Const reference type
    182     typedef const T& ConstReference;
     191
     192  /// Identity map.
     193
     194  /// This \ref concepts::ReadMap "read-only map" gives back the given
     195  /// key as value without any modification.
     196  ///
     197  /// \sa ConstMap
     198  template <typename T>
     199  class IdentityMap : public MapBase<T, T> {
     200  public:
     201    typedef MapBase<T, T> Parent;
     202    typedef typename Parent::Key Key;
     203    typedef typename Parent::Value Value;
     204
     205    /// Gives back the given value without any modification.
     206    Value operator[](const Key &k) const {
     207      return k;
     208    }
     209  };
     210
     211  /// Returns an \ref IdentityMap class
     212
     213  /// This function just returns an \ref IdentityMap class.
     214  /// \relates IdentityMap
     215  template<typename T>
     216  inline IdentityMap<T> identityMap() {
     217    return IdentityMap<T>();
     218  }
     219
     220
     221  /// \brief Map for storing values for integer keys from the range
     222  /// <tt>[0..size-1]</tt>.
     223  ///
     224  /// This map is essentially a wrapper for \c std::vector. It assigns
     225  /// values to integer keys from the range <tt>[0..size-1]</tt>.
     226  /// It can be used with some data structures, for example
     227  /// \ref UnionFind, \ref BinHeap, when the used items are small
     228  /// integers. This map conforms the \ref concepts::ReferenceMap
     229  /// "ReferenceMap" concept.
     230  ///
     231  /// The simplest way of using this map is through the rangeMap()
     232  /// function.
     233  template <typename V>
     234  class RangeMap : public MapBase<int, V> {
     235    template <typename V1>
     236    friend class RangeMap;
     237  private:
     238
     239    typedef std::vector<V> Vector;
     240    Vector _vector;
     241
     242  public:
     243
     244    typedef MapBase<int, V> Parent;
     245    /// Key type
     246    typedef typename Parent::Key Key;
     247    /// Value type
     248    typedef typename Parent::Value Value;
     249    /// Reference type
     250    typedef typename Vector::reference Reference;
     251    /// Const reference type
     252    typedef typename Vector::const_reference ConstReference;
    183253
    184254    typedef True ReferenceMapTag;
    185255
     256  public:
     257
     258    /// Constructor with specified default value.
     259    RangeMap(int size = 0, const Value &value = Value())
     260      : _vector(size, value) {}
     261
     262    /// Constructs the map from an appropriate \c std::vector.
     263    template <typename V1>
     264    RangeMap(const std::vector<V1>& vector)
     265      : _vector(vector.begin(), vector.end()) {}
     266
     267    /// Constructs the map from another \ref RangeMap.
     268    template <typename V1>
     269    RangeMap(const RangeMap<V1> &c)
     270      : _vector(c._vector.begin(), c._vector.end()) {}
     271
     272    /// Returns the size of the map.
     273    int size() {
     274      return _vector.size();
     275    }
     276
     277    /// Resizes the map.
     278
     279    /// Resizes the underlying \c std::vector container, so changes the
     280    /// keyset of the map.
     281    /// \param size The new size of the map. The new keyset will be the
     282    /// range <tt>[0..size-1]</tt>.
     283    /// \param value The default value to assign to the new keys.
     284    void resize(int size, const Value &value = Value()) {
     285      _vector.resize(size, value);
     286    }
     287
    186288  private:
    187    
    188     typedef std::map<K, T, Compare> Map;
     289
     290    RangeMap& operator=(const RangeMap&);
     291
     292  public:
     293
     294    ///\e
     295    Reference operator[](const Key &k) {
     296      return _vector[k];
     297    }
     298
     299    ///\e
     300    ConstReference operator[](const Key &k) const {
     301      return _vector[k];
     302    }
     303
     304    ///\e
     305    void set(const Key &k, const Value &v) {
     306      _vector[k] = v;
     307    }
     308  };
     309
     310  /// Returns a \ref RangeMap class
     311
     312  /// This function just returns a \ref RangeMap class.
     313  /// \relates RangeMap
     314  template<typename V>
     315  inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
     316    return RangeMap<V>(size, value);
     317  }
     318
     319  /// \brief Returns a \ref RangeMap class created from an appropriate
     320  /// \c std::vector
     321
     322  /// This function just returns a \ref RangeMap class created from an
     323  /// appropriate \c std::vector.
     324  /// \relates RangeMap
     325  template<typename V>
     326  inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
     327    return RangeMap<V>(vector);
     328  }
     329
     330
     331  /// Map type based on \c std::map
     332
     333  /// This map is essentially a wrapper for \c std::map with addition
     334  /// that you can specify a default value for the keys that are not
     335  /// stored actually. This value can be different from the default
     336  /// contructed value (i.e. \c %Value()).
     337  /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
     338  /// concept.
     339  ///
     340  /// This map is useful if a default value should be assigned to most of
     341  /// the keys and different values should be assigned only to a few
     342  /// keys (i.e. the map is "sparse").
     343  /// The name of this type also refers to this important usage.
     344  ///
     345  /// Apart form that this map can be used in many other cases since it
     346  /// is based on \c std::map, which is a general associative container.
     347  /// However keep in mind that it is usually not as efficient as other
     348  /// maps.
     349  ///
     350  /// The simplest way of using this map is through the sparseMap()
     351  /// function.
     352  template <typename K, typename V, typename Compare = std::less<K> >
     353  class SparseMap : public MapBase<K, V> {
     354    template <typename K1, typename V1, typename C1>
     355    friend class SparseMap;
     356  public:
     357
     358    typedef MapBase<K, V> Parent;
     359    /// Key type
     360    typedef typename Parent::Key Key;
     361    /// Value type
     362    typedef typename Parent::Value Value;
     363    /// Reference type
     364    typedef Value& Reference;
     365    /// Const reference type
     366    typedef const Value& ConstReference;
     367
     368    typedef True ReferenceMapTag;
     369
     370  private:
     371
     372    typedef std::map<K, V, Compare> Map;
     373    Map _map;
    189374    Value _value;
    190     Map _map;
    191 
    192   public:
    193 
    194     /// Constructor with specified default value
    195     StdMap(const T& value = T()) : _value(value) {}
    196     /// \brief Constructs the map from an appropriate \c std::map, and
     375
     376  public:
     377
     378    /// \brief Constructor with specified default value.
     379    SparseMap(const Value &value = Value()) : _value(value) {}
     380    /// \brief Constructs the map from an appropriate \c std::map, and
    197381    /// explicitly specifies a default value.
    198     template <typename T1, typename Comp1>
    199     StdMap(const std::map<Key, T1, Comp1> &map, const T& value = T())
     382    template <typename V1, typename Comp1>
     383    SparseMap(const std::map<Key, V1, Comp1> &map,
     384              const Value &value = Value())
    200385      : _map(map.begin(), map.end()), _value(value) {}
    201    
    202     /// \brief Constructs a map from an other \ref StdMap.
    203     template<typename T1, typename Comp1>
    204     StdMap(const StdMap<Key, T1, Comp1> &c)
     386
     387    /// \brief Constructs the map from another \ref SparseMap.
     388    template<typename V1, typename Comp1>
     389    SparseMap(const SparseMap<Key, V1, Comp1> &c)
    205390      : _map(c._map.begin(), c._map.end()), _value(c._value) {}
    206391
    207392  private:
    208393
    209     StdMap& operator=(const StdMap&);
     394    SparseMap& operator=(const SparseMap&);
    210395
    211396  public:
    … …  
    220405    }
    221406
    222     /// \e
     407    ///\e
    223408    ConstReference operator[](const Key &k) const {
    224409      typename Map::const_iterator it = _map.find(k);
    … …  
    229414    }
    230415
    231     /// \e
    232     void set(const Key &k, const T &t) {
     416    ///\e
     417    void set(const Key &k, const Value &v) {
    233418      typename Map::iterator it = _map.lower_bound(k);
    234419      if (it != _map.end() && !_map.key_comp()(k, it->first))
    235         it->second = t;
     420        it->second = v;
    236421      else
    237         _map.insert(it, std::make_pair(k, t));
     422        _map.insert(it, std::make_pair(k, v));
    238423    }
    239424
    240     /// \e
    241     void setAll(const T &t) {
    242       _value = t;
     425    ///\e
     426    void setAll(const Value &v) {
     427      _value = v;
    243428      _map.clear();
    244     }   
    245 
    246   };
    247  
    248   ///Returns a \c StdMap class
    249 
    250   ///This function just returns a \c StdMap class with specified
    251   ///default value.
    252   ///\relates StdMap
    253   template<typename K, typename V, typename Compare>
    254   inline StdMap<K, V, Compare> stdMap(const V& value = V()) {
    255     return StdMap<K, V, Compare>(value);
    256   }
    257  
    258   ///Returns a \c StdMap class
    259 
    260   ///This function just returns a \c StdMap class with specified
    261   ///default value.
    262   ///\relates StdMap
    263   template<typename K, typename V>
    264   inline StdMap<K, V, std::less<K> > stdMap(const V& value = V()) {
    265     return StdMap<K, V, std::less<K> >(value);
    266   }
    267  
    268   ///Returns a \c StdMap class created from an appropriate std::map
    269 
    270   ///This function just returns a \c StdMap class created from an
    271   ///appropriate std::map.
    272   ///\relates StdMap
    273   template<typename K, typename V, typename Compare>
    274   inline StdMap<K, V, Compare> stdMap( const std::map<K, V, Compare> &map,
    275                                        const V& value = V() ) {
    276     return StdMap<K, V, Compare>(map, value);
    277   }
    278 
    279   ///Returns a \c StdMap class created from an appropriate std::map
    280 
    281   ///This function just returns a \c StdMap class created from an
    282   ///appropriate std::map.
    283   ///\relates StdMap
    284   template<typename K, typename V>
    285   inline StdMap<K, V, std::less<K> > stdMap( const std::map<K, V, std::less<K> > &map,
    286                                              const V& value = V() ) {
    287     return StdMap<K, V, std::less<K> >(map, value);
    288   }
    289 
    290   /// \brief Map for storing values for keys from the range <tt>[0..size-1]</tt>
    291   ///
    292   /// This map has the <tt>[0..size-1]</tt> keyset and the values
    293   /// are stored in a \c std::vector<T>  container. It can be used with
    294   /// some data structures, for example \c UnionFind, \c BinHeap, when
    295   /// the used items are small integer numbers.
    296   /// This map meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
    297   ///
    298   /// \todo Revise its name
    299   template <typename T>
    300   class IntegerMap : public MapBase<int, T> {
    301 
    302     template <typename T1>
    303     friend class IntegerMap;
    304 
    305   public:
    306 
    307     typedef MapBase<int, T> Parent;
    308     ///\e
    309     typedef typename Parent::Key Key;
    310     ///\e
    311     typedef typename Parent::Value Value;
    312     ///\e
    313     typedef T& Reference;
    314     ///\e
    315     typedef const T& ConstReference;
    316 
    317     typedef True ReferenceMapTag;
    318 
    319   private:
    320    
    321     typedef std::vector<T> Vector;
    322     Vector _vector;
    323 
    324   public:
    325 
    326     /// Constructor with specified default value
    327     IntegerMap(int size = 0, const T& value = T()) : _vector(size, value) {}
    328 
    329     /// \brief Constructs the map from an appropriate \c std::vector.
    330     template <typename T1>
    331     IntegerMap(const std::vector<T1>& vector)
    332       : _vector(vector.begin(), vector.end()) {}
    333    
    334     /// \brief Constructs a map from an other \ref IntegerMap.
    335     template <typename T1>
    336     IntegerMap(const IntegerMap<T1> &c)
    337       : _vector(c._vector.begin(), c._vector.end()) {}
    338 
    339     /// \brief Resize the container
    340     void resize(int size, const T& value = T()) {
    341       _vector.resize(size, value);
    342429    }
    343 
    344   private:
    345 
    346     IntegerMap& operator=(const IntegerMap&);
    347 
    348   public:
    349 
    350     ///\e
    351     Reference operator[](Key k) {
    352       return _vector[k];
    353     }
    354 
    355     /// \e
    356     ConstReference operator[](Key k) const {
    357       return _vector[k];
    358     }
    359 
    360     /// \e
    361     void set(const Key &k, const T& t) {
    362       _vector[k] = t;
    363     }
    364 
    365   };
    366  
    367   ///Returns an \c IntegerMap class
    368 
    369   ///This function just returns an \c IntegerMap class.
    370   ///\relates IntegerMap
    371   template<typename T>
    372   inline IntegerMap<T> integerMap(int size = 0, const T& value = T()) {
    373     return IntegerMap<T>(size, value);
     430  };
     431
     432  /// Returns a \ref SparseMap class
     433
     434  /// This function just returns a \ref SparseMap class with specified
     435  /// default value.
     436  /// \relates SparseMap
     437  template<typename K, typename V, typename Compare>
     438  inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
     439    return SparseMap<K, V, Compare>(value);
     440  }
     441
     442  template<typename K, typename V>
     443  inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
     444    return SparseMap<K, V, std::less<K> >(value);
     445  }
     446
     447  /// \brief Returns a \ref SparseMap class created from an appropriate
     448  /// \c std::map
     449
     450  /// This function just returns a \ref SparseMap class created from an
     451  /// appropriate \c std::map.
     452  /// \relates SparseMap
     453  template<typename K, typename V, typename Compare>
     454  inline SparseMap<K, V, Compare>
     455    sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
     456  {
     457    return SparseMap<K, V, Compare>(map, value);
    374458  }
    375459
    … …  
    379463  /// @{
    380464
    381   /// \brief Identity map.
    382   ///
    383   /// This map gives back the given key as value without any
    384   /// modification.
    385   template <typename T>
    386   class IdentityMap : public MapBase<T, T> {
    387   public:
    388     typedef MapBase<T, T> Parent;
    389     typedef typename Parent::Key Key;
    390     typedef typename Parent::Value Value;
    391 
    392     /// \e
    393     const T& operator[](const T& t) const {
    394       return t;
    395     }
    396   };
    397 
    398   ///Returns an \c IdentityMap class
    399 
    400   ///This function just returns an \c IdentityMap class.
    401   ///\relates IdentityMap
    402   template<typename T>
    403   inline IdentityMap<T> identityMap() {
    404     return IdentityMap<T>();
    405   }
    406  
    407 
    408   ///\brief Convert the \c Value of a map to another type using
    409   ///the default conversion.
    410   ///
    411   ///This \ref concepts::ReadMap "read only map"
    412   ///converts the \c Value of a map to type \c T.
    413   ///Its \c Key is inherited from \c M.
    414   template <typename M, typename T>
    415   class ConvertMap : public MapBase<typename M::Key, T> {
    416     const M& m;
    417   public:
    418     typedef MapBase<typename M::Key, T> Parent;
    419     typedef typename Parent::Key Key;
    420     typedef typename Parent::Value Value;
    421 
    422     ///Constructor
    423 
    424     ///Constructor.
    425     ///\param _m is the underlying map.
    426     ConvertMap(const M &_m) : m(_m) {};
    427 
    428     ///\e
    429     Value operator[](const Key& k) const {return m[k];}
    430   };
    431  
    432   ///Returns a \c ConvertMap class
    433 
    434   ///This function just returns a \c ConvertMap class.
    435   ///\relates ConvertMap
    436   template<typename T, typename M>
    437   inline ConvertMap<M, T> convertMap(const M &m) {
    438     return ConvertMap<M, T>(m);
    439   }
    440 
    441   ///Simple wrapping of a map
    442 
    443   ///This \ref concepts::ReadMap "read only map" returns the simple
    444   ///wrapping of the given map. Sometimes the reference maps cannot be
    445   ///combined with simple read maps. This map adaptor wraps the given
    446   ///map to simple read map.
    447   ///
    448   ///\sa SimpleWriteMap
    449   ///
    450   /// \todo Revise the misleading name
    451   template<typename M>
    452   class SimpleMap : public MapBase<typename M::Key, typename M::Value> {
    453     const M& m;
    454 
     465  /// Composition of two maps
     466
     467  /// This \ref concepts::ReadMap "read-only map" returns the
     468  /// composition of two given maps. That is to say, if \c m1 is of
     469  /// type \c M1 and \c m2 is of \c M2, then for
     470  /// \code
     471  ///   ComposeMap<M1, M2> cm(m1,m2);
     472  /// \endcode
     473  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
     474  ///
     475  /// The \c Key type of the map is inherited from \c M2 and the
     476  /// \c Value type is from \c M1.
     477  /// \c M2::Value must be convertible to \c M1::Key.
     478  ///
     479  /// The simplest way of using this map is through the composeMap()
     480  /// function.
     481  ///
     482  /// \sa CombineMap
     483  ///
     484  /// \todo Check the requirements.
     485  template <typename M1, typename M2>
     486  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
     487    const M1 &_m1;
     488    const M2 &_m2;
     489  public:
     490    typedef MapBase<typename M2::Key, typename M1::Value> Parent;
     491    typedef typename Parent::Key Key;
     492    typedef typename Parent::Value Value;
     493
     494    /// Constructor
     495    ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
     496
     497    /// \e
     498    typename MapTraits<M1>::ConstReturnValue
     499    operator[](const Key &k) const { return _m1[_m2[k]]; }
     500  };
     501
     502  /// Returns a \ref ComposeMap class
     503
     504  /// This function just returns a \ref ComposeMap class.
     505  ///
     506  /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
     507  /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
     508  /// will be equal to <tt>m1[m2[x]]</tt>.
     509  ///
     510  /// \relates ComposeMap
     511  template <typename M1, typename M2>
     512  inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) {
     513    return ComposeMap<M1, M2>(m1, m2);
     514  }
     515
     516
     517  /// Combination of two maps using an STL (binary) functor.
     518
     519  /// This \ref concepts::ReadMap "read-only map" takes two maps and a
     520  /// binary functor and returns the combination of the two given maps
     521  /// using the functor.
     522  /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2
     523  /// and \c f is of \c F, then for
     524  /// \code
     525  ///   CombineMap<M1,M2,F,V> cm(m1,m2,f);
     526  /// \endcode
     527  /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>.
     528  ///
     529  /// The \c Key type of the map is inherited from \c M1 (\c M1::Key
     530  /// must be convertible to \c M2::Key) and the \c Value type is \c V.
     531  /// \c M2::Value and \c M1::Value must be convertible to the
     532  /// corresponding input parameter of \c F and the return type of \c F
     533  /// must be convertible to \c V.
     534  ///
     535  /// The simplest way of using this map is through the combineMap()
     536  /// function.
     537  ///
     538  /// \sa ComposeMap
     539  ///
     540  /// \todo Check the requirements.
     541  template<typename M1, typename M2, typename F,
     542           typename V = typename F::result_type>
     543  class CombineMap : public MapBase<typename M1::Key, V> {
     544    const M1 &_m1;
     545    const M2 &_m2;
     546    F _f;
     547  public:
     548    typedef MapBase<typename M1::Key, V> Parent;
     549    typedef typename Parent::Key Key;
     550    typedef typename Parent::Value Value;
     551
     552    /// Constructor
     553    CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
     554      : _m1(m1), _m2(m2), _f(f) {}
     555    /// \e
     556    Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
     557  };
     558
     559  /// Returns a \ref CombineMap class
     560
     561  /// This function just returns a \ref CombineMap class.
     562  ///
     563  /// For example, if \c m1 and \c m2 are both maps with \c double
     564  /// values, then
     565  /// \code
     566  ///   combineMap(m1,m2,std::plus<double>())
     567  /// \endcode
     568  /// is equivalent to
     569  /// \code
     570  ///   addMap(m1,m2)
     571  /// \endcode
     572  ///
     573  /// This function is specialized for adaptable binary function
     574  /// classes and C++ functions.
     575  ///
     576  /// \relates CombineMap
     577  template<typename M1, typename M2, typename F, typename V>
     578  inline CombineMap<M1, M2, F, V>
     579  combineMap(const M1 &m1, const M2 &m2, const F &f) {
     580    return CombineMap<M1, M2, F, V>(m1,m2,f);
     581  }
     582
     583  template<typename M1, typename M2, typename F>
     584  inline CombineMap<M1, M2, F, typename F::result_type>
     585  combineMap(const M1 &m1, const M2 &m2, const F &f) {
     586    return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
     587  }
     588
     589  template<typename M1, typename M2, typename K1, typename K2, typename V>
     590  inline CombineMap<M1, M2, V (*)(K1, K2), V>
     591  combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
     592    return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
     593  }
     594
     595
     596  /// Converts an STL style (unary) functor to a map
     597
     598  /// This \ref concepts::ReadMap "read-only map" returns the value
     599  /// of a given functor. Actually, it just wraps the functor and
     600  /// provides the \c Key and \c Value typedefs.
     601  ///
     602  /// Template parameters \c K and \c V will become its \c Key and
     603  /// \c Value. In most cases they have to be given explicitly because
     604  /// a functor typically does not provide \c argument_type and
     605  /// \c result_type typedefs.
     606  /// Parameter \c F is the type of the used functor.
     607  ///
     608  /// The simplest way of using this map is through the functorToMap()
     609  /// function.
     610  ///
     611  /// \sa MapToFunctor
     612  template<typename F,
     613           typename K = typename F::argument_type,
     614           typename V = typename F::result_type>
     615  class FunctorToMap : public MapBase<K, V> {
     616    const F &_f;
     617  public:
     618    typedef MapBase<K, V> Parent;
     619    typedef typename Parent::Key Key;
     620    typedef typename Parent::Value Value;
     621
     622    /// Constructor
     623    FunctorToMap(const F &f = F()) : _f(f) {}
     624    /// \e
     625    Value operator[](const Key &k) const { return _f(k); }
     626  };
     627
     628  /// Returns a \ref FunctorToMap class
     629
     630  /// This function just returns a \ref FunctorToMap class.
     631  ///
     632  /// This function is specialized for adaptable binary function
     633  /// classes and C++ functions.
     634  ///
     635  /// \relates FunctorToMap
     636  template<typename K, typename V, typename F>
     637  inline FunctorToMap<F, K, V> functorToMap(const F &f) {
     638    return FunctorToMap<F, K, V>(f);
     639  }
     640
     641  template <typename F>
     642  inline FunctorToMap<F, typename F::argument_type, typename F::result_type>
     643    functorToMap(const F &f)
     644  {
     645    return FunctorToMap<F, typename F::argument_type,
     646      typename F::result_type>(f);
     647  }
     648
     649  template <typename K, typename V>
     650  inline FunctorToMap<V (*)(K), K, V> functorToMap(V (*f)(K)) {
     651    return FunctorToMap<V (*)(K), K, V>(f);
     652  }
     653
     654
     655  /// Converts a map to an STL style (unary) functor
     656
     657  /// This class converts a map to an STL style (unary) functor.
     658  /// That is it provides an <tt>operator()</tt> to read its values.
     659  ///
     660  /// For the sake of convenience it also works as a usual
     661  /// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt>
     662  /// and the \c Key and \c Value typedefs also exist.
     663  ///
     664  /// The simplest way of using this map is through the mapToFunctor()
     665  /// function.
     666  ///
     667  ///\sa FunctorToMap
     668  template <typename M>
     669  class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
     670    const M &_m;
    455671  public:
    456672    typedef MapBase<typename M::Key, typename M::Value> Parent;
    … …  
    458674    typedef typename Parent::Value Value;
    459675
    460     ///Constructor
    461     SimpleMap(const M &_m) : m(_m) {};
    462     ///\e
    463     Value operator[](Key k) const {return m[k];}
    464   };
    465  
    466   ///Returns a \c SimpleMap class
    467 
    468   ///This function just returns a \c SimpleMap class.
    469   ///\relates SimpleMap
     676    typedef typename Parent::Key argument_type;
     677    typedef typename Parent::Value result_type;
     678
     679    /// Constructor
     680    MapToFunctor(const M &m) : _m(m) {}
     681    /// \e
     682    Value operator()(const Key &k) const { return _m[k]; }
     683    /// \e
     684    Value operator[](const Key &k) const { return _m[k]; }
     685  };
     686
     687  /// Returns a \ref MapToFunctor class
     688
     689  /// This function just returns a \ref MapToFunctor class.
     690  /// \relates MapToFunctor
    470691  template<typename M>
    471   inline SimpleMap<M> simpleMap(const M &m) {
    472     return SimpleMap<M>(m);
    473   }
    474 
    475   ///Simple writable wrapping of a map
    476 
    477   ///This \ref concepts::ReadWriteMap "read-write map" returns the simple
    478   ///wrapping of the given map. Sometimes the reference maps cannot be
    479   ///combined with simple read-write maps. This map adaptor wraps the
    480   ///given map to simple read-write map.
    481   ///
    482   ///\sa SimpleMap
    483   ///
    484   /// \todo Revise the misleading name
    485   template<typename M>
    486   class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> {
    487     M& m;
    488 
    489   public:
    490     typedef MapBase<typename M::Key, typename M::Value> Parent;
    491     typedef typename Parent::Key Key;
    492     typedef typename Parent::Value Value;
    493 
    494     ///Constructor
    495     SimpleWriteMap(M &_m) : m(_m) {};
    496     ///\e
    497     Value operator[](Key k) const {return m[k];}
    498     ///\e
    499     void set(Key k, const Value& c) { m.set(k, c); }
    500   };
    501 
    502   ///Returns a \c SimpleWriteMap class
    503 
    504   ///This function just returns a \c SimpleWriteMap class.
    505   ///\relates SimpleWriteMap
    506   template<typename M>
    507   inline SimpleWriteMap<M> simpleWriteMap(M &m) {
    508     return SimpleWriteMap<M>(m);
    509   }
    510 
    511   ///Sum of two maps
    512 
    513   ///This \ref concepts::ReadMap "read only map" returns the sum of the two
    514   ///given maps.
    515   ///Its \c Key and \c Value are inherited from \c M1.
    516   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
    517   template<typename M1, typename M2>
     692  inline MapToFunctor<M> mapToFunctor(const M &m) {
     693    return MapToFunctor<M>(m);
     694  }
     695
     696
     697  /// \brief Map adaptor to convert the \c Value type of a map to
     698  /// another type using the default conversion.
     699
     700  /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap
     701  /// "readable map" to another type using the default conversion.
     702  /// The \c Key type of it is inherited from \c M and the \c Value
     703  /// type is \c V.
     704  /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
     705  ///
     706  /// The simplest way of using this map is through the convertMap()
     707  /// function.
     708  template <typename M, typename V>
     709  class ConvertMap : public MapBase<typename M::Key, V> {
     710    const M &_m;
     711  public:
     712    typedef MapBase<typename M::Key, V> Parent;
     713    typedef typename Parent::Key Key;
     714    typedef typename Parent::Value Value;
     715
     716    /// Constructor
     717
     718    /// Constructor.
     719    /// \param m The underlying map.
     720    ConvertMap(const M &m) : _m(m) {}
     721
     722    /// \e
     723    Value operator[](const Key &k) const { return _m[k]; }
     724  };
     725
     726  /// Returns a \ref ConvertMap class
     727
     728  /// This function just returns a \ref ConvertMap class.
     729  /// \relates ConvertMap
     730  template<typename V, typename M>
     731  inline ConvertMap<M, V> convertMap(const M &map) {
     732    return ConvertMap<M, V>(map);
     733  }
     734
     735
     736  /// Applies all map setting operations to two maps
     737
     738  /// This map has two \ref concepts::WriteMap "writable map" parameters
     739  /// and each write request will be passed to both of them.
     740  /// If \c M1 is also \ref concepts::ReadMap "readable", then the read
     741  /// operations will return the corresponding values of \c M1.
     742  ///
     743  /// The \c Key and \c Value types are inherited from \c M1.
     744  /// The \c Key and \c Value of \c M2 must be convertible from those
     745  /// of \c M1.
     746  ///
     747  /// The simplest way of using this map is through the forkMap()
     748  /// function.
     749  template<typename  M1, typename M2>
     750  class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
     751    M1 &_m1;
     752    M2 &_m2;
     753  public:
     754    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
     755    typedef typename Parent::Key Key;
     756    typedef typename Parent::Value Value;
     757
     758    /// Constructor
     759    ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
     760    /// Returns the value associated with the given key in the first map.
     761    Value operator[](const Key &k) const { return _m1[k]; }
     762    /// Sets the value associated with the given key in both maps.
     763    void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); }
     764  };
     765
     766  /// Returns a \ref ForkMap class
     767
     768  /// This function just returns a \ref ForkMap class.
     769  /// \relates ForkMap
     770  template <typename M1, typename M2>
     771  inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) {
     772    return ForkMap<M1,M2>(m1,m2);
     773  }
     774
     775
     776  /// Sum of two maps
     777
     778  /// This \ref concepts::ReadMap "read-only map" returns the sum
     779  /// of the values of the two given maps.
     780  /// Its \c Key and \c Value types are inherited from \c M1.
     781  /// The \c Key and \c Value of \c M2 must be convertible to those of
     782  /// \c M1.
     783  ///
     784  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
     785  /// \code
     786  ///   AddMap<M1,M2> am(m1,m2);
     787  /// \endcode
     788  /// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>.
     789  ///
     790  /// The simplest way of using this map is through the addMap()
     791  /// function.
     792  ///
     793  /// \sa SubMap, MulMap, DivMap
     794  /// \sa ShiftMap, ShiftWriteMap
     795  template<typename M1, typename M2>
    518796  class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
    519     const M1& m1;
    520     const M2& m2;
    521 
     797    const M1 &_m1;
     798    const M2 &_m2;
    522799  public:
    523800    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
    … …  
    525802    typedef typename Parent::Value Value;
    526803
    527     ///Constructor
    528     AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
    529     ///\e
    530     Value operator[](Key k) const {return m1[k]+m2[k];}
    531   };
    532  
    533   ///Returns an \c AddMap class
    534 
    535   ///This function just returns an \c AddMap class.
    536   ///\todo Extend the documentation: how to call these type of functions?
    537   ///
    538   ///\relates AddMap
    539   template<typename M1, typename M2>
    540   inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
     804    /// Constructor
     805    AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
     806    /// \e
     807    Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
     808  };
     809
     810  /// Returns an \ref AddMap class
     811
     812  /// This function just returns an \ref AddMap class.
     813  ///
     814  /// For example, if \c m1 and \c m2 are both maps with \c double
     815  /// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to
     816  /// <tt>m1[x]+m2[x]</tt>.
     817  ///
     818  /// \relates AddMap
     819  template<typename M1, typename M2>
     820  inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) {
    541821    return AddMap<M1, M2>(m1,m2);
    542822  }
    543823
    544   ///Shift a map with a constant.
    545 
    546   ///This \ref concepts::ReadMap "read only map" returns the sum of the
    547   ///given map and a constant value.
    548   ///Its \c Key and \c Value are inherited from \c M.
    549   ///
    550   ///Actually,
    551   ///\code
    552   ///  ShiftMap<X> sh(x,v);
    553   ///\endcode
    554   ///is equivalent to
    555   ///\code
    556   ///  ConstMap<X::Key, X::Value> c_tmp(v);
    557   ///  AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
    558   ///\endcode
    559   ///
    560   ///\sa ShiftWriteMap
    561   template<typename M, typename C = typename M::Value>
    562   class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
    563     const M& m;
    564     C v;
    565   public:
    566     typedef MapBase<typename M::Key, typename M::Value> Parent;
    567     typedef typename Parent::Key Key;
    568     typedef typename Parent::Value Value;
    569 
    570     ///Constructor
    571 
    572     ///Constructor.
    573     ///\param _m is the undelying map.
    574     ///\param _v is the shift value.
    575     ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
    576     ///\e
    577     Value operator[](Key k) const {return m[k] + v;}
    578   };
    579 
    580   ///Shift a map with a constant (ReadWrite version).
    581 
    582   ///This \ref concepts::ReadWriteMap "read-write map" returns the sum of the
    583   ///given map and a constant value. It makes also possible to write the map.
    584   ///Its \c Key and \c Value are inherited from \c M.
    585   ///
    586   ///\sa ShiftMap
    587   template<typename M, typename C = typename M::Value>
    588   class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
    589     M& m;
    590     C v;
    591   public:
    592     typedef MapBase<typename M::Key, typename M::Value> Parent;
    593     typedef typename Parent::Key Key;
    594     typedef typename Parent::Value Value;
    595 
    596     ///Constructor
    597 
    598     ///Constructor.
    599     ///\param _m is the undelying map.
    600     ///\param _v is the shift value.
    601     ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
    602     /// \e
    603     Value operator[](Key k) const {return m[k] + v;}
    604     /// \e
    605     void set(Key k, const Value& c) { m.set(k, c - v); }
    606   };
    607  
    608   ///Returns a \c ShiftMap class
    609 
    610   ///This function just returns a \c ShiftMap class.
    611   ///\relates ShiftMap
    612   template<typename M, typename C>
    613   inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
    614     return ShiftMap<M, C>(m,v);
    615   }
    616 
    617   ///Returns a \c ShiftWriteMap class
    618 
    619   ///This function just returns a \c ShiftWriteMap class.
    620   ///\relates ShiftWriteMap
    621   template<typename M, typename C>
    622   inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) {
    623     return ShiftWriteMap<M, C>(m,v);
    624   }
    625 
    626   ///Difference of two maps
    627 
    628   ///This \ref concepts::ReadMap "read only map" returns the difference
    629   ///of the values of the two given maps.
    630   ///Its \c Key and \c Value are inherited from \c M1.
    631   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
    632   ///
    633   /// \todo Revise the misleading name
    634   template<typename M1, typename M2>
     824
     825  /// Difference of two maps
     826
     827  /// This \ref concepts::ReadMap "read-only map" returns the difference
     828  /// of the values of the two given maps.
     829  /// Its \c Key and \c Value types are inherited from \c M1.
     830  /// The \c Key and \c Value of \c M2 must be convertible to those of
     831  /// \c M1.
     832  ///
     833  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
     834  /// \code
     835  ///   SubMap<M1,M2> sm(m1,m2);
     836  /// \endcode
     837  /// <tt>sm[x]</tt> will be equal to <tt>m1[x]-m2[x]</tt>.
     838  ///
     839  /// The simplest way of using this map is through the subMap()
     840  /// function.
     841  ///
     842  /// \sa AddMap, MulMap, DivMap
     843  template<typename M1, typename M2>
    635844  class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
    636     const M1& m1;
    637     const M2& m2;
     845    const M1 &_m1;
     846    const M2 &_m2;
    638847  public:
    639848    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
    … …  
    641850    typedef typename Parent::Value Value;
    642851
    643     ///Constructor
    644     SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
    645     /// \e
    646     Value operator[](Key k) const {return m1[k]-m2[k];}
    647   };
    648  
    649   ///Returns a \c SubMap class
    650 
    651   ///This function just returns a \c SubMap class.
    652   ///
    653   ///\relates SubMap
    654   template<typename M1, typename M2>
     852    /// Constructor
     853    SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
     854    /// \e
     855    Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
     856  };
     857
     858  /// Returns a \ref SubMap class
     859
     860  /// This function just returns a \ref SubMap class.
     861  ///
     862  /// For example, if \c m1 and \c m2 are both maps with \c double
     863  /// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to
     864  /// <tt>m1[x]-m2[x]</tt>.
     865  ///
     866  /// \relates SubMap
     867  template<typename M1, typename M2>
    655868  inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
    656     return SubMap<M1, M2>(m1, m2);
    657   }
    658 
    659   ///Product of two maps
    660 
    661   ///This \ref concepts::ReadMap "read only map" returns the product of the
    662   ///values of the two given maps.
    663   ///Its \c Key and \c Value are inherited from \c M1.
    664   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
    665   template<typename M1, typename M2>
     869    return SubMap<M1, M2>(m1,m2);
     870  }
     871
     872
     873  /// Product of two maps
     874
     875  /// This \ref concepts::ReadMap "read-only map" returns the product
     876  /// of the values of the two given maps.
     877  /// Its \c Key and \c Value types are inherited from \c M1.
     878  /// The \c Key and \c Value of \c M2 must be convertible to those of
     879  /// \c M1.
     880  ///
     881  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
     882  /// \code
     883  ///   MulMap<M1,M2> mm(m1,m2);
     884  /// \endcode
     885  /// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>.
     886  ///
     887  /// The simplest way of using this map is through the mulMap()
     888  /// function.
     889  ///
     890  /// \sa AddMap, SubMap, DivMap
     891  /// \sa ScaleMap, ScaleWriteMap
     892  template<typename M1, typename M2>
    666893  class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
    667     const M1& m1;
    668     const M2& m2;
     894    const M1 &_m1;
     895    const M2 &_m2;
    669896  public:
    670897    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
    … …  
    672899    typedef typename Parent::Value Value;
    673900
    674     ///Constructor
    675     MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
    676     /// \e
    677     Value operator[](Key k) const {return m1[k]*m2[k];}
    678   };
    679  
    680   ///Returns a \c MulMap class
    681 
    682   ///This function just returns a \c MulMap class.
    683   ///\relates MulMap
    684   template<typename M1, typename M2>
     901    /// Constructor
     902    MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
     903    /// \e
     904    Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
     905  };
     906
     907  /// Returns a \ref MulMap class
     908
     909  /// This function just returns a \ref MulMap class.
     910  ///
     911  /// For example, if \c m1 and \c m2 are both maps with \c double
     912  /// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to
     913  /// <tt>m1[x]*m2[x]</tt>.
     914  ///
     915  /// \relates MulMap
     916  template<typename M1, typename M2>
    685917  inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
    686918    return MulMap<M1, M2>(m1,m2);
    687919  }
    688  
    689   ///Scales a map with a constant.
    690 
    691   ///This \ref concepts::ReadMap "read only map" returns the value of the
    692   ///given map multiplied from the left side with a constant value.
    693   ///Its \c Key and \c Value are inherited from \c M.
    694   ///
    695   ///Actually,
    696   ///\code
    697   ///  ScaleMap<X> sc(x,v);
    698   ///\endcode
    699   ///is equivalent to
    700   ///\code
    701   ///  ConstMap<X::Key, X::Value> c_tmp(v);
    702   ///  MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
    703   ///\endcode
    704   ///
    705   ///\sa ScaleWriteMap
    706   template<typename M, typename C = typename M::Value>
    707   class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
    708     const M& m;
    709     C v;
    710   public:
    711     typedef MapBase<typename M::Key, typename M::Value> Parent;
    712     typedef typename Parent::Key Key;
    713     typedef typename Parent::Value Value;
    714 
    715     ///Constructor
    716 
    717     ///Constructor.
    718     ///\param _m is the undelying map.
    719     ///\param _v is the scaling value.
    720     ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
    721     /// \e
    722     Value operator[](Key k) const {return v * m[k];}
    723   };
    724 
    725   ///Scales a map with a constant (ReadWrite version).
    726 
    727   ///This \ref concepts::ReadWriteMap "read-write map" returns the value of the
    728   ///given map multiplied from the left side with a constant value. It can
    729   ///also be used as write map if the \c / operator is defined between
    730   ///\c Value and \c C and the given multiplier is not zero.
    731   ///Its \c Key and \c Value are inherited from \c M.
    732   ///
    733   ///\sa ScaleMap
    734   template<typename M, typename C = typename M::Value>
    735   class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
    736     M& m;
    737     C v;
    738   public:
    739     typedef MapBase<typename M::Key, typename M::Value> Parent;
    740     typedef typename Parent::Key Key;
    741     typedef typename Parent::Value Value;
    742 
    743     ///Constructor
    744 
    745     ///Constructor.
    746     ///\param _m is the undelying map.
    747     ///\param _v is the scaling value.
    748     ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
    749     /// \e
    750     Value operator[](Key k) const {return v * m[k];}
    751     /// \e
    752     void set(Key k, const Value& c) { m.set(k, c / v);}
    753   };
    754  
    755   ///Returns a \c ScaleMap class
    756 
    757   ///This function just returns a \c ScaleMap class.
    758   ///\relates ScaleMap
    759   template<typename M, typename C>
    760   inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
    761     return ScaleMap<M, C>(m,v);
    762   }
    763 
    764   ///Returns a \c ScaleWriteMap class
    765 
    766   ///This function just returns a \c ScaleWriteMap class.
    767   ///\relates ScaleWriteMap
    768   template<typename M, typename C>
    769   inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) {
    770     return ScaleWriteMap<M, C>(m,v);
    771   }
    772 
    773   ///Quotient of two maps
    774 
    775   ///This \ref concepts::ReadMap "read only map" returns the quotient of the
    776   ///values of the two given maps.
    777   ///Its \c Key and \c Value are inherited from \c M1.
    778   ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
    779   template<typename M1, typename M2>
     920
     921
     922  /// Quotient of two maps
     923
     924  /// This \ref concepts::ReadMap "read-only map" returns the quotient
     925  /// of the values of the two given maps.
     926  /// Its \c Key and \c Value types are inherited from \c M1.
     927  /// The \c Key and \c Value of \c M2 must be convertible to those of
     928  /// \c M1.
     929  ///
     930  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
     931  /// \code
     932  ///   DivMap<M1,M2> dm(m1,m2);
     933  /// \endcode
     934  /// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>.
     935  ///
     936  /// The simplest way of using this map is through the divMap()
     937  /// function.
     938  ///
     939  /// \sa AddMap, SubMap, MulMap
     940  template<typename M1, typename M2>
    780941  class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
    781     const M1& m1;
    782     const M2& m2;
     942    const M1 &_m1;
     943    const M2 &_m2;
    783944  public:
    784945    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
    … …  
    786947    typedef typename Parent::Value Value;
    787948
    788     ///Constructor
    789     DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
    790     /// \e
    791     Value operator[](Key k) const {return m1[k]/m2[k];}
    792   };
    793  
    794   ///Returns a \c DivMap class
    795 
    796   ///This function just returns a \c DivMap class.
    797   ///\relates DivMap
    798   template<typename M1, typename M2>
     949    /// Constructor
     950    DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
     951    /// \e
     952    Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
     953  };
     954
     955  /// Returns a \ref DivMap class
     956
     957  /// This function just returns a \ref DivMap class.
     958  ///
     959  /// For example, if \c m1 and \c m2 are both maps with \c double
     960  /// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to
     961  /// <tt>m1[x]/m2[x]</tt>.
     962  ///
     963  /// \relates DivMap
     964  template<typename M1, typename M2>
    799965  inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
    800966    return DivMap<M1, M2>(m1,m2);
    801967  }
    802  
    803   ///Composition of two maps
    804 
    805   ///This \ref concepts::ReadMap "read only map" returns the composition of
    806   ///two given maps.
    807   ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2,
    808   ///then for
    809   ///\code
    810   ///  ComposeMap<M1, M2> cm(m1,m2);
    811   ///\endcode
    812   /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
    813   ///
    814   ///Its \c Key is inherited from \c M2 and its \c Value is from \c M1.
    815   ///\c M2::Value must be convertible to \c M1::Key.
    816   ///
    817   ///\sa CombineMap
    818   ///
    819   ///\todo Check the requirements.
    820   template <typename M1, typename M2>
    821   class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
    822     const M1& m1;
    823     const M2& m2;
    824   public:
    825     typedef MapBase<typename M2::Key, typename M1::Value> Parent;
    826     typedef typename Parent::Key Key;
    827     typedef typename Parent::Value Value;
    828 
    829     ///Constructor
    830     ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
    831    
    832     /// \e
    833 
    834 
    835     /// \todo Use the  MapTraits once it is ported.
    836     ///
    837 
    838     //typename MapTraits<M1>::ConstReturnValue
    839     typename M1::Value
    840     operator[](Key k) const {return m1[m2[k]];}
    841   };
    842 
    843   ///Returns a \c ComposeMap class
    844 
    845   ///This function just returns a \c ComposeMap class.
    846   ///\relates ComposeMap
    847   template <typename M1, typename M2>
    848   inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
    849     return ComposeMap<M1, M2>(m1,m2);
    850   }
    851  
    852   ///Combine of two maps using an STL (binary) functor.
    853 
    854   ///Combine of two maps using an STL (binary) functor.
    855   ///
    856   ///This \ref concepts::ReadMap "read only map" takes two maps and a
    857   ///binary functor and returns the composition of the two
    858   ///given maps unsing the functor.
    859   ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
    860   ///and \c f is of \c F, then for
    861   ///\code
    862   ///  CombineMap<M1,M2,F,V> cm(m1,m2,f);
    863   ///\endcode
    864   /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
    865   ///
    866   ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
    867   ///\c M2::Value and \c M1::Value must be convertible to the corresponding
    868   ///input parameter of \c F and the return type of \c F must be convertible
    869   ///to \c V.
    870   ///
    871   ///\sa ComposeMap
    872   ///
    873   ///\todo Check the requirements.
    874   template<typename M1, typename M2, typename F,
    875            typename V = typename F::result_type>
    876   class CombineMap : public MapBase<typename M1::Key, V> {
    877     const M1& m1;
    878     const M2& m2;
    879     F f;
    880   public:
    881     typedef MapBase<typename M1::Key, V> Parent;
    882     typedef typename Parent::Key Key;
    883     typedef typename Parent::Value Value;
    884 
    885     ///Constructor
    886     CombineMap(const M1 &_m1,const M2 &_m2,const F &_f = F())
    887       : m1(_m1), m2(_m2), f(_f) {};
    888     /// \e
    889     Value operator[](Key k) const {return f(m1[k],m2[k]);}
    890   };
    891  
    892   ///Returns a \c CombineMap class
    893 
    894   ///This function just returns a \c CombineMap class.
    895   ///
    896   ///For example if \c m1 and \c m2 are both \c double valued maps, then
    897   ///\code
    898   ///combineMap(m1,m2,std::plus<double>())
    899   ///\endcode
    900   ///is equivalent to
    901   ///\code
    902   ///addMap(m1,m2)
    903   ///\endcode
    904   ///
    905   ///This function is specialized for adaptable binary function
    906   ///classes and C++ functions.
    907   ///
    908   ///\relates CombineMap
    909   template<typename M1, typename M2, typename F, typename V>
    910   inline CombineMap<M1, M2, F, V>
    911   combineMap(const M1& m1,const M2& m2, const F& f) {
    912     return CombineMap<M1, M2, F, V>(m1,m2,f);
    913   }
    914 
    915   template<typename M1, typename M2, typename F>
    916   inline CombineMap<M1, M2, F, typename F::result_type>
    917   combineMap(const M1& m1, const M2& m2, const F& f) {
    918     return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
    919   }
    920 
    921   template<typename M1, typename M2, typename K1, typename K2, typename V>
    922   inline CombineMap<M1, M2, V (*)(K1, K2), V>
    923   combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
    924     return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
    925   }
    926 
    927   ///Negative value of a map
    928 
    929   ///This \ref concepts::ReadMap "read only map" returns the negative
    930   ///value of the value returned by the given map.
    931   ///Its \c Key and \c Value are inherited from \c M.
    932   ///The unary \c - operator must be defined for \c Value, of course.
    933   ///
    934   ///\sa NegWriteMap
    935   template<typename M>
     968
     969
     970  /// Shifts a map with a constant.
     971
     972  /// This \ref concepts::ReadMap "read-only map" returns the sum of
     973  /// the given map and a constant value (i.e. it shifts the map with
     974  /// the constant). Its \c Key and \c Value are inherited from \c M.
     975  ///
     976  /// Actually,
     977  /// \code
     978  ///   ShiftMap<M> sh(m,v);
     979  /// \endcode
     980  /// is equivalent to
     981  /// \code
     982  ///   ConstMap<M::Key, M::Value> cm(v);
     983  ///   AddMap<M, ConstMap<M::Key, M::Value> > sh(m,cm);
     984  /// \endcode
     985  ///
     986  /// The simplest way of using this map is through the shiftMap()
     987  /// function.
     988  ///
     989  /// \sa ShiftWriteMap
     990  template<typename M, typename C = typename M::Value>
     991  class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
     992    const M &_m;
     993    C _v;
     994  public:
     995    typedef MapBase<typename M::Key, typename M::Value> Parent;
     996    typedef typename Parent::Key Key;
     997    typedef typename Parent::Value Value;
     998
     999    /// Constructor
     1000
     1001    /// Constructor.
     1002    /// \param m The undelying map.
     1003    /// \param v The constant value.
     1004    ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
     1005    /// \e
     1006    Value operator[](const Key &k) const { return _m[k]+_v; }
     1007  };
     1008
     1009  /// Shifts a map with a constant (read-write version).
     1010
     1011  /// This \ref concepts::ReadWriteMap "read-write map" returns the sum
     1012  /// of the given map and a constant value (i.e. it shifts the map with
     1013  /// the constant). Its \c Key and \c Value are inherited from \c M.
     1014  /// It makes also possible to write the map.
     1015  ///
     1016  /// The simplest way of using this map is through the shiftWriteMap()
     1017  /// function.
     1018  ///
     1019  /// \sa ShiftMap
     1020  template<typename M, typename C = typename M::Value>
     1021  class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
     1022    M &_m;
     1023    C _v;
     1024  public:
     1025    typedef MapBase<typename M::Key, typename M::Value> Parent;
     1026    typedef typename Parent::Key Key;
     1027    typedef typename Parent::Value Value;
     1028
     1029    /// Constructor
     1030
     1031    /// Constructor.
     1032    /// \param m The undelying map.
     1033    /// \param v The constant value.
     1034    ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
     1035    /// \e
     1036    Value operator[](const Key &k) const { return _m[k]+_v; }
     1037    /// \e
     1038    void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
     1039  };
     1040
     1041  /// Returns a \ref ShiftMap class
     1042
     1043  /// This function just returns a \ref ShiftMap class.
     1044  ///
     1045  /// For example, if \c m is a map with \c double values and \c v is
     1046  /// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to
     1047  /// <tt>m[x]+v</tt>.
     1048  ///
     1049  /// \relates ShiftMap
     1050  template<typename M, typename C>
     1051  inline ShiftMap<M, C> shiftMap(const M &m, const C &v) {
     1052    return ShiftMap<M, C>(m,v);
     1053  }
     1054
     1055  /// Returns a \ref ShiftWriteMap class
     1056
     1057  /// This function just returns a \ref ShiftWriteMap class.
     1058  ///
     1059  /// For example, if \c m is a map with \c double values and \c v is
     1060  /// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to
     1061  /// <tt>m[x]+v</tt>.
     1062  /// Moreover it makes also possible to write the map.
     1063  ///
     1064  /// \relates ShiftWriteMap
     1065  template<typename M, typename C>
     1066  inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) {
     1067    return ShiftWriteMap<M, C>(m,v);
     1068  }
     1069
     1070
     1071  /// Scales a map with a constant.
     1072
     1073  /// This \ref concepts::ReadMap "read-only map" returns the value of
     1074  /// the given map multiplied from the left side with a constant value.
     1075  /// Its \c Key and \c Value are inherited from \c M.
     1076  ///
     1077  /// Actually,
     1078  /// \code
     1079  ///   ScaleMap<M> sc(m,v);
     1080  /// \endcode
     1081  /// is equivalent to
     1082  /// \code
     1083  ///   ConstMap<M::Key, M::Value> cm(v);
     1084  ///   MulMap<ConstMap<M::Key, M::Value>, M> sc(cm,m);
     1085  /// \endcode
     1086  ///
     1087  /// The simplest way of using this map is through the scaleMap()
     1088  /// function.
     1089  ///
     1090  /// \sa ScaleWriteMap
     1091  template<typename M, typename C = typename M::Value>
     1092  class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
     1093    const M &_m;
     1094    C _v;
     1095  public:
     1096    typedef MapBase<typename M::Key, typename M::Value> Parent;
     1097    typedef typename Parent::Key Key;
     1098    typedef typename Parent::Value Value;
     1099
     1100    /// Constructor
     1101
     1102    /// Constructor.
     1103    /// \param m The undelying map.
     1104    /// \param v The constant value.
     1105    ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
     1106    /// \e
     1107    Value operator[](const Key &k) const { return _v*_m[k]; }
     1108  };
     1109
     1110  /// Scales a map with a constant (read-write version).
     1111
     1112  /// This \ref concepts::ReadWriteMap "read-write map" returns the value of
     1113  /// the given map multiplied from the left side with a constant value.
     1114  /// Its \c Key and \c Value are inherited from \c M.
     1115  /// It can also be used as write map if the \c / operator is defined
     1116  /// between \c Value and \c C and the given multiplier is not zero.
     1117  ///
     1118  /// The simplest way of using this map is through the scaleWriteMap()
     1119  /// function.
     1120  ///
     1121  /// \sa ScaleMap
     1122  template<typename M, typename C = typename M::Value>
     1123  class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
     1124    M &_m;
     1125    C _v;
     1126  public:
     1127    typedef MapBase<typename M::Key, typename M::Value> Parent;
     1128    typedef typename Parent::Key Key;
     1129    typedef typename Parent::Value Value;
     1130
     1131    /// Constructor
     1132
     1133    /// Constructor.
     1134    /// \param m The undelying map.
     1135    /// \param v The constant value.
     1136    ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
     1137    /// \e
     1138    Value operator[](const Key &k) const { return _v*_m[k]; }
     1139    /// \e
     1140    void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
     1141  };
     1142
     1143  /// Returns a \ref ScaleMap class
     1144
     1145  /// This function just returns a \ref ScaleMap class.
     1146  ///
     1147  /// For example, if \c m is a map with \c double values and \c v is
     1148  /// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to
     1149  /// <tt>v*m[x]</tt>.
     1150  ///
     1151  /// \relates ScaleMap
     1152  template<typename M, typename C>
     1153  inline ScaleMap<M, C> scaleMap(const M &m, const C &v) {
     1154    return ScaleMap<M, C>(m,v);
     1155  }
     1156
     1157  /// Returns a \ref ScaleWriteMap class
     1158
     1159  /// This function just returns a \ref ScaleWriteMap class.
     1160  ///
     1161  /// For example, if \c m is a map with \c double values and \c v is
     1162  /// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to
     1163  /// <tt>v*m[x]</tt>.
     1164  /// Moreover it makes also possible to write the map.
     1165  ///
     1166  /// \relates ScaleWriteMap
     1167  template<typename M, typename C>
     1168  inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) {
     1169    return ScaleWriteMap<M, C>(m,v);
     1170  }
     1171
     1172
     1173  /// Negative of a map
     1174
     1175  /// This \ref concepts::ReadMap "read-only map" returns the negative
     1176  /// of the values of the given map (using the unary \c - operator).
     1177  /// Its \c Key and \c Value are inherited from \c M.
     1178  ///
     1179  /// If M::Value is \c int, \c double etc., then
     1180  /// \code
     1181  ///   NegMap<M> neg(m);
     1182  /// \endcode
     1183  /// is equivalent to
     1184  /// \code
     1185  ///   ScaleMap<M> neg(m,-1);
     1186  /// \endcode
     1187  ///
     1188  /// The simplest way of using this map is through the negMap()
     1189  /// function.
     1190  ///
     1191  /// \sa NegWriteMap
     1192  template<typename M>
    9361193  class NegMap : public MapBase<typename M::Key, typename M::Value> {
    937     const M& m;
     1194    const M& _m;
    9381195  public:
    9391196    typedef MapBase<typename M::Key, typename M::Value> Parent;
    … …  
    9411198    typedef typename Parent::Value Value;
    9421199
    943     ///Constructor
    944     NegMap(const M &_m) : m(_m) {};
    945     /// \e
    946     Value operator[](Key k) const {return -m[k];}
    947   };
    948  
    949   ///Negative value of a map (ReadWrite version)
    950 
    951   ///This \ref concepts::ReadWriteMap "read-write map" returns the negative
    952   ///value of the value returned by the given map.
    953   ///Its \c Key and \c Value are inherited from \c M.
    954   ///The unary \c - operator must be defined for \c Value, of course.
     1200    /// Constructor
     1201    NegMap(const M &m) : _m(m) {}
     1202    /// \e
     1203    Value operator[](const Key &k) const { return -_m[k]; }
     1204  };
     1205
     1206  /// Negative of a map (read-write version)
     1207
     1208  /// This \ref concepts::ReadWriteMap "read-write map" returns the
     1209  /// negative of the values of the given map (using the unary \c -
     1210  /// operator).
     1211  /// Its \c Key and \c Value are inherited from \c M.
     1212  /// It makes also possible to write the map.
     1213  ///
     1214  /// If M::Value is \c int, \c double etc., then
     1215  /// \code
     1216  ///   NegWriteMap<M> neg(m);
     1217  /// \endcode
     1218  /// is equivalent to
     1219  /// \code
     1220  ///   ScaleWriteMap<M> neg(m,-1);
     1221  /// \endcode
     1222  ///
     1223  /// The simplest way of using this map is through the negWriteMap()
     1224  /// function.
    9551225  ///
    9561226  /// \sa NegMap
    957   template<typename M> 
     1227  template<typename M>
    9581228  class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
    959     M& m;
     1229    M &_m;
    9601230  public:
    9611231    typedef MapBase<typename M::Key, typename M::Value> Parent;
    … …  
    9631233    typedef typename Parent::Value Value;
    9641234
    965     ///Constructor
    966     NegWriteMap(M &_m) : m(_m) {};
    967     /// \e
    968     Value operator[](Key k) const {return -m[k];}
    969     /// \e
    970     void set(Key k, const Value& v) { m.set(k, -v); }
    971   };
    972 
    973   ///Returns a \c NegMap class
    974 
    975   ///This function just returns a \c NegMap class.
    976   ///\relates NegMap
    977   template <typename M>
     1235    /// Constructor
     1236    NegWriteMap(M &m) : _m(m) {}
     1237    /// \e
     1238    Value operator[](const Key &k) const { return -_m[k]; }
     1239    /// \e
     1240    void set(const Key &k, const Value &v) { _m.set(k, -v); }
     1241  };
     1242
     1243  /// Returns a \ref NegMap class
     1244
     1245  /// This function just returns a \ref NegMap class.
     1246  ///
     1247  /// For example, if \c m is a map with \c double values, then
     1248  /// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
     1249  ///
     1250  /// \relates NegMap
     1251  template <typename M>
    9781252  inline NegMap<M> negMap(const M &m) {
    9791253    return NegMap<M>(m);
    9801254  }
    9811255
    982   ///Returns a \c NegWriteMap class
    983 
    984   ///This function just returns a \c NegWriteMap class.
    985   ///\relates NegWriteMap
    986   template <typename M>
    987   inline NegWriteMap<M> negMap(M &m) {
     1256  /// Returns a \ref NegWriteMap class
     1257
     1258  /// This function just returns a \ref NegWriteMap class.
     1259  ///
     1260  /// For example, if \c m is a map with \c double values, then
     1261  /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
     1262  /// Moreover it makes also possible to write the map.
     1263  ///
     1264  /// \relates NegWriteMap
     1265  template <typename M>
     1266  inline NegWriteMap<M> negWriteMap(M &m) {
    9881267    return NegWriteMap<M>(m);
    9891268  }
    9901269
    991   ///Absolute value of a map
    992 
    993   ///This \ref concepts::ReadMap "read only map" returns the absolute value
    994   ///of the value returned by the given map.
    995   ///Its \c Key and \c Value are inherited from \c M.
    996   ///\c Value must be comparable to \c 0 and the unary \c -
    997   ///operator must be defined for it, of course.
    998   template<typename M>
     1270
     1271  /// Absolute value of a map
     1272
     1273  /// This \ref concepts::ReadMap "read-only map" returns the absolute
     1274  /// value of the values of the given map.
     1275  /// Its \c Key and \c Value are inherited from \c M.
     1276  /// \c Value must be comparable to \c 0 and the unary \c -
     1277  /// operator must be defined for it, of course.
     1278  ///
     1279  /// The simplest way of using this map is through the absMap()
     1280  /// function.
     1281  template<typename M>
    9991282  class AbsMap : public MapBase<typename M::Key, typename M::Value> {
    1000     const M& m;
     1283    const M &_m;
    10011284  public:
    10021285    typedef MapBase<typename M::Key, typename M::Value> Parent;
    … …  
    10041287    typedef typename Parent::Value Value;
    10051288
    1006     ///Constructor
    1007     AbsMap(const M &_m) : m(_m) {};
    1008     /// \e
    1009     Value operator[](Key k) const {
    1010       Value tmp = m[k];
     1289    /// Constructor
     1290    AbsMap(const M &m) : _m(m) {}
     1291    /// \e
     1292    Value operator[](const Key &k) const {
     1293      Value tmp = _m[k];
    10111294      return tmp >= 0 ? tmp : -tmp;
    10121295    }
    10131296
    10141297  };
    1015  
    1016   ///Returns an \c AbsMap class
    1017 
    1018   ///This function just returns an \c AbsMap class.
    1019   ///\relates AbsMap
    1020   template<typename M>
     1298
     1299  /// Returns an \ref AbsMap class
     1300
     1301  /// This function just returns an \ref AbsMap class.
     1302  ///
     1303  /// For example, if \c m is a map with \c double values, then
     1304  /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if
     1305  /// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is
     1306  /// negative.
     1307  ///
     1308  /// \relates AbsMap
     1309  template<typename M>
    10211310  inline AbsMap<M> absMap(const M &m) {
    10221311    return AbsMap<M>(m);
    10231312  }
    10241313
    1025   ///Converts an STL style functor to a map
    1026 
    1027   ///This \ref concepts::ReadMap "read only map" returns the value
    1028   ///of a given functor.
    1029   ///
    1030   ///Template parameters \c K and \c V will become its
    1031   ///\c Key and \c Value.
    1032   ///In most cases they have to be given explicitly because a
    1033   ///functor typically does not provide \c argument_type and
    1034   ///\c result_type typedefs.
    1035   ///
    1036   ///Parameter \c F is the type of the used functor.
    1037   ///
    1038   ///\sa MapFunctor
    1039   template<typename F,
    1040            typename K = typename F::argument_type,
    1041            typename V = typename F::result_type>
    1042   class FunctorMap : public MapBase<K, V> {
    1043     F f;
    1044   public:
    1045     typedef MapBase<K, V> Parent;
    1046     typedef typename Parent::Key Key;
    1047     typedef typename Parent::Value Value;
    1048 
    1049     ///Constructor
    1050     FunctorMap(const F &_f = F()) : f(_f) {}
    1051     /// \e
    1052     Value operator[](Key k) const { return f(k);}
    1053   };
     1314  /// @}
    10541315 
    1055   ///Returns a \c FunctorMap class
    1056 
    1057   ///This function just returns a \c FunctorMap class.
    1058   ///
    1059   ///This function is specialized for adaptable binary function
    1060   ///classes and C++ functions.
    1061   ///
    1062   ///\relates FunctorMap
    1063   template<typename K, typename V, typename F> inline
    1064   FunctorMap<F, K, V> functorMap(const F &f) {
    1065     return FunctorMap<F, K, V>(f);
    1066   }
    1067 
    1068   template <typename F> inline
    1069   FunctorMap<F, typename F::argument_type, typename F::result_type>
    1070   functorMap(const F &f) {
    1071     return FunctorMap<F, typename F::argument_type,
    1072       typename F::result_type>(f);
    1073   }
    1074 
    1075   template <typename K, typename V> inline
    1076   FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
    1077     return FunctorMap<V (*)(K), K, V>(f);
    1078   }
    1079 
    1080 
    1081   ///Converts a map to an STL style (unary) functor
    1082 
    1083   ///This class Converts a map to an STL style (unary) functor.
    1084   ///That is it provides an <tt>operator()</tt> to read its values.
    1085   ///
    1086   ///For the sake of convenience it also works as
    1087   ///a ususal \ref concepts::ReadMap "readable map",
    1088   ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
    1089   ///
    1090   ///\sa FunctorMap
    1091   template <typename M>
    1092   class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
    1093     const M& m;
    1094   public:
    1095     typedef MapBase<typename M::Key, typename M::Value> Parent;
    1096     typedef typename Parent::Key Key;
    1097     typedef typename Parent::Value Value;
    1098 
    1099     typedef typename M::Key argument_type;
    1100     typedef typename M::Value result_type;
    1101 
    1102     ///Constructor
    1103     MapFunctor(const M &_m) : m(_m) {};
    1104     ///\e
    1105     Value operator()(Key k) const {return m[k];}
    1106     ///\e
    1107     Value operator[](Key k) const {return m[k];}
    1108   };
    1109  
    1110   ///Returns a \c MapFunctor class
    1111 
    1112   ///This function just returns a \c MapFunctor class.
    1113   ///\relates MapFunctor
    1114   template<typename M>
    1115   inline MapFunctor<M> mapFunctor(const M &m) {
    1116     return MapFunctor<M>(m);
    1117   }
    1118 
    1119   ///Just readable version of \ref ForkWriteMap
    1120 
    1121   ///This map has two \ref concepts::ReadMap "readable map"
    1122   ///parameters and each read request will be passed just to the
    1123   ///first map. This class is the just readable map type of \c ForkWriteMap.
    1124   ///
    1125   ///The \c Key and \c Value are inherited from \c M1.
    1126   ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
    1127   ///
    1128   ///\sa ForkWriteMap
    1129   ///
    1130   /// \todo Why is it needed?
    1131   template<typename  M1, typename M2>
    1132   class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
    1133     const M1& m1;
    1134     const M2& m2;
    1135   public:
    1136     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
    1137     typedef typename Parent::Key Key;
    1138     typedef typename Parent::Value Value;
    1139 
    1140     ///Constructor
    1141     ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {};
    1142     /// \e
    1143     Value operator[](Key k) const {return m1[k];}
    1144   };
    1145 
    1146 
    1147   ///Applies all map setting operations to two maps
    1148 
    1149   ///This map has two \ref concepts::WriteMap "writable map"
    1150   ///parameters and each write request will be passed to both of them.
    1151   ///If \c M1 is also \ref concepts::ReadMap "readable",
    1152   ///then the read operations will return the
    1153   ///corresponding values of \c M1.
    1154   ///
    1155   ///The \c Key and \c Value are inherited from \c M1.
    1156   ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
    1157   ///
    1158   ///\sa ForkMap
    1159   template<typename  M1, typename M2>
    1160   class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
    1161     M1& m1;
    1162     M2& m2;
    1163   public:
    1164     typedef MapBase<typename M1::Key, typename M1::Value> Parent;
    1165     typedef typename Parent::Key Key;
    1166     typedef typename Parent::Value Value;
    1167 
    1168     ///Constructor
    1169     ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {};
    1170     ///\e
    1171     Value operator[](Key k) const {return m1[k];}
    1172     ///\e
    1173     void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
    1174   };
    1175  
    1176   ///Returns a \c ForkMap class
    1177 
    1178   ///This function just returns a \c ForkMap class.
    1179   ///\relates ForkMap
    1180   template <typename M1, typename M2>
    1181   inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) {
    1182     return ForkMap<M1, M2>(m1,m2);
    1183   }
    1184 
    1185   ///Returns a \c ForkWriteMap class
    1186 
    1187   ///This function just returns a \c ForkWriteMap class.
    1188   ///\relates ForkWriteMap
    1189   template <typename M1, typename M2>
    1190   inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) {
    1191     return ForkWriteMap<M1, M2>(m1,m2);
    1192   }
    1193 
    1194 
    1195  
    1196   /* ************* BOOL MAPS ******************* */
    1197  
    1198   ///Logical 'not' of a map
    1199  
    1200   ///This bool \ref concepts::ReadMap "read only map" returns the
    1201   ///logical negation of the value returned by the given map.
    1202   ///Its \c Key is inherited from \c M, its \c Value is \c bool.
    1203   ///
    1204   ///\sa NotWriteMap
    1205   template <typename M>
     1316  // Logical maps and map adaptors:
     1317
     1318  /// \addtogroup maps
     1319  /// @{
     1320
     1321  /// Constant \c true map.
     1322
     1323  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
     1324  /// each key.
     1325  ///
     1326  /// Note that
     1327  /// \code
     1328  ///   TrueMap<K> tm;
     1329  /// \endcode
     1330  /// is equivalent to
     1331  /// \code
     1332  ///   ConstMap<K,bool> tm(true);
     1333  /// \endcode
     1334  ///
     1335  /// \sa FalseMap
     1336  /// \sa ConstMap
     1337  template <typename K>
     1338  class TrueMap : public MapBase<K, bool> {
     1339  public:
     1340    typedef MapBase<K, bool> Parent;
     1341    typedef typename Parent::Key Key;
     1342    typedef typename Parent::Value Value;
     1343
     1344    /// Gives back \c true.
     1345    Value operator[](const Key&) const { return true; }
     1346  };
     1347
     1348  /// Returns a \ref TrueMap class
     1349
     1350  /// This function just returns a \ref TrueMap class.
     1351  /// \relates TrueMap
     1352  template<typename K>
     1353  inline TrueMap<K> trueMap() {
     1354    return TrueMap<K>();
     1355  }
     1356
     1357
     1358  /// Constant \c false map.
     1359
     1360  /// This \ref concepts::ReadMap "read-only map" assigns \c false to
     1361  /// each key.
     1362  ///
     1363  /// Note that
     1364  /// \code
     1365  ///   FalseMap<K> fm;
     1366  /// \endcode
     1367  /// is equivalent to
     1368  /// \code
     1369  ///   ConstMap<K,bool> fm(false);
     1370  /// \endcode
     1371  ///
     1372  /// \sa TrueMap
     1373  /// \sa ConstMap
     1374  template <typename K>
     1375  class FalseMap : public MapBase<K, bool> {
     1376  public:
     1377    typedef MapBase<K, bool> Parent;
     1378    typedef typename Parent::Key Key;
     1379    typedef typename Parent::Value Value;
     1380
     1381    /// Gives back \c false.
     1382    Value operator[](const Key&) const { return false; }
     1383  };
     1384
     1385  /// Returns a \ref FalseMap class
     1386
     1387  /// This function just returns a \ref FalseMap class.
     1388  /// \relates FalseMap
     1389  template<typename K>
     1390  inline FalseMap<K> falseMap() {
     1391    return FalseMap<K>();
     1392  }
     1393
     1394  /// @}
     1395
     1396  /// \addtogroup map_adaptors
     1397  /// @{
     1398
     1399  /// Logical 'and' of two maps
     1400
     1401  /// This \ref concepts::ReadMap "read-only map" returns the logical
     1402  /// 'and' of the values of the two given maps.
     1403  /// Its \c Key type is inherited from \c M1 and its \c Value type is
     1404  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
     1405  ///
     1406  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
     1407  /// \code
     1408  ///   AndMap<M1,M2> am(m1,m2);
     1409  /// \endcode
     1410  /// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>.
     1411  ///
     1412  /// The simplest way of using this map is through the andMap()
     1413  /// function.
     1414  ///
     1415  /// \sa OrMap
     1416  /// \sa NotMap, NotWriteMap
     1417  template<typename M1, typename M2>
     1418  class AndMap : public MapBase<typename M1::Key, bool> {
     1419    const M1 &_m1;
     1420    const M2 &_m2;
     1421  public:
     1422    typedef MapBase<typename M1::Key, bool> Parent;
     1423    typedef typename Parent::Key Key;
     1424    typedef typename Parent::Value Value;
     1425
     1426    /// Constructor
     1427    AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
     1428    /// \e
     1429    Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
     1430  };
     1431
     1432  /// Returns an \ref AndMap class
     1433
     1434  /// This function just returns an \ref AndMap class.
     1435  ///
     1436  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
     1437  /// then <tt>andMap(m1,m2)[x]</tt> will be equal to
     1438  /// <tt>m1[x]&&m2[x]</tt>.
     1439  ///
     1440  /// \relates AndMap
     1441  template<typename M1, typename M2>
     1442  inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) {
     1443    return AndMap<M1, M2>(m1,m2);
     1444  }
     1445
     1446
     1447  /// Logical 'or' of two maps
     1448
     1449  /// This \ref concepts::ReadMap "read-only map" returns the logical
     1450  /// 'or' of the values of the two given maps.
     1451  /// Its \c Key type is inherited from \c M1 and its \c Value type is
     1452  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
     1453  ///
     1454  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
     1455  /// \code
     1456  ///   OrMap<M1,M2> om(m1,m2);
     1457  /// \endcode
     1458  /// <tt>om[x]</tt> will be equal to <tt>m1[x]||m2[x]</tt>.
     1459  ///
     1460  /// The simplest way of using this map is through the orMap()
     1461  /// function.
     1462  ///
     1463  /// \sa AndMap
     1464  /// \sa NotMap, NotWriteMap
     1465  template<typename M1, typename M2>
     1466  class OrMap : public MapBase<typename M1::Key, bool> {
     1467    const M1 &_m1;
     1468    const M2 &_m2;
     1469  public:
     1470    typedef MapBase<typename M1::Key, bool> Parent;
     1471    typedef typename Parent::Key Key;
     1472    typedef typename Parent::Value Value;
     1473
     1474    /// Constructor
     1475    OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
     1476    /// \e
     1477    Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
     1478  };
     1479
     1480  /// Returns an \ref OrMap class
     1481
     1482  /// This function just returns an \ref OrMap class.
     1483  ///
     1484  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
     1485  /// then <tt>orMap(m1,m2)[x]</tt> will be equal to
     1486  /// <tt>m1[x]||m2[x]</tt>.
     1487  ///
     1488  /// \relates OrMap
     1489  template<typename M1, typename M2>
     1490  inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) {
     1491    return OrMap<M1, M2>(m1,m2);
     1492  }
     1493
     1494
     1495  /// Logical 'not' of a map
     1496
     1497  /// This \ref concepts::ReadMap "read-only map" returns the logical
     1498  /// negation of the values of the given map.
     1499  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
     1500  ///
     1501  /// The simplest way of using this map is through the notMap()
     1502  /// function.
     1503  ///
     1504  /// \sa NotWriteMap
     1505  template <typename M>
    12061506  class NotMap : public MapBase<typename M::Key, bool> {
    1207     const M& m;
     1507    const M &_m;
    12081508  public:
    12091509    typedef MapBase<typename M::Key, bool> Parent;
    … …  
    12121512
    12131513    /// Constructor
    1214     NotMap(const M &_m) : m(_m) {};
    1215     ///\e
    1216     Value operator[](Key k) const {return !m[k];}
    1217   };
    1218 
    1219   ///Logical 'not' of a map (ReadWrie version)
    1220  
    1221   ///This bool \ref concepts::ReadWriteMap "read-write map" returns the
    1222   ///logical negation of the value returned by the given map. When it is set,
    1223   ///the opposite value is set to the original map.
    1224   ///Its \c Key is inherited from \c M, its \c Value is \c bool.
    1225   ///
    1226   ///\sa NotMap
    1227   template <typename M>
     1514    NotMap(const M &m) : _m(m) {}
     1515    /// \e
     1516    Value operator[](const Key &k) const { return !_m[k]; }
     1517  };
     1518
     1519  /// Logical 'not' of a map (read-write version)
     1520
     1521  /// This \ref concepts::ReadWriteMap "read-write map" returns the
     1522  /// logical negation of the values of the given map.
     1523  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
     1524  /// It makes also possible to write the map. When a value is set,
     1525  /// the opposite value is set to the original map.
     1526  ///
     1527  /// The simplest way of using this map is through the notWriteMap()
     1528  /// function.
     1529  ///
     1530  /// \sa NotMap
     1531  template <typename M>
    12281532  class NotWriteMap : public MapBase<typename M::Key, bool> {
    1229     M& m;
     1533    M &_m;
    12301534  public:
    12311535    typedef MapBase<typename M::Key, bool> Parent;
    … …  
    12341538
    12351539    /// Constructor
    1236     NotWriteMap(M &_m) : m(_m) {};
    1237     ///\e
    1238     Value operator[](Key k) const {return !m[k];}
    1239     ///\e
    1240     void set(Key k, bool v) { m.set(k, !v); }
    1241   };
    1242  
    1243   ///Returns a \c NotMap class
    1244  
    1245   ///This function just returns a \c NotMap class.
    1246   ///\relates NotMap
    1247   template <typename M>
     1540    NotWriteMap(M &m) : _m(m) {}
     1541    /// \e
     1542    Value operator[](const Key &k) const { return !_m[k]; }
     1543    /// \e
     1544    void set(const Key &k, bool v) { _m.set(k, !v); }
     1545  };
     1546
     1547  /// Returns a \ref NotMap class
     1548
     1549  /// This function just returns a \ref NotMap class.
     1550  ///
     1551  /// For example, if \c m is a map with \c bool values, then
     1552  /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
     1553  ///
     1554  /// \relates NotMap
     1555  template <typename M>
    12481556  inline NotMap<M> notMap(const M &m) {
    12491557    return NotMap<M>(m);
    12501558  }
    1251  
    1252   ///Returns a \c NotWriteMap class
    1253  
    1254   ///This function just returns a \c NotWriteMap class.
    1255   ///\relates NotWriteMap
    1256   template <typename M>
    1257   inline NotWriteMap<M> notMap(M &m) {
     1559
     1560  /// Returns a \ref NotWriteMap class
     1561
     1562  /// This function just returns a \ref NotWriteMap class.
     1563  ///
     1564  /// For example, if \c m is a map with \c bool values, then
     1565  /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
     1566  /// Moreover it makes also possible to write the map.
     1567  ///
     1568  /// \relates NotWriteMap
     1569  template <typename M>
     1570  inline NotWriteMap<M> notWriteMap(M &m) {
    12581571    return NotWriteMap<M>(m);
    12591572  }
    12601573
    1261   namespace _maps_bits {
    1262 
    1263     template <typename Value>
    1264     struct Identity {
    1265       typedef Value argument_type;
    1266       typedef Value result_type;
    1267       Value operator()(const Value& val) const {
    1268         return val;
    1269       }
    1270     };
    1271 
    1272     template <typename _Iterator, typename Enable = void>
    1273     struct IteratorTraits {
    1274       typedef typename std::iterator_traits<_Iterator>::value_type Value;
    1275     };
    1276 
    1277     template <typename _Iterator>
    1278     struct IteratorTraits<_Iterator,
    1279       typename exists<typename _Iterator::container_type>::type>
    1280     {
    1281       typedef typename _Iterator::container_type::value_type Value;
    1282     };
    1283 
    1284   }
    1285  
    1286 
    1287   /// \brief Writable bool map for logging each \c true assigned element
    1288   ///
    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> >
    1320   class StoreBoolMap {
    1321   public:
    1322     typedef _Iterator Iterator;
    1323 
    1324     typedef typename _Functor::argument_type Key;
    1325     typedef bool Value;
    1326 
    1327     typedef _Functor Functor;
    1328 
    1329     /// Constructor
    1330     StoreBoolMap(Iterator it, const Functor& functor = Functor())
    1331       : _begin(it), _end(it), _functor(functor) {}
    1332 
    1333     /// Gives back the given iterator set for the first key
    1334     Iterator begin() const {
    1335       return _begin;
    1336     }
    1337  
    1338     /// Gives back the the 'after the last' iterator
    1339     Iterator end() const {
    1340       return _end;
    1341     }
    1342 
    1343     /// The \c set function of the map
    1344     void set(const Key& key, Value value) const {
    1345       if (value) {
    1346         *_end++ = _functor(key);
    1347       }
    1348     }
    1349    
    1350   private:
    1351     Iterator _begin;
    1352     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;
    1634   };
     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);
     1668  }
    16351669
    16361670  /// @}

  • lemon/random.h

    r49 r68  
    6868
    6969#include <ctime>
    70 #include <cmath>
    71 
     70
     71#include <lemon/math.h>
    7272#include <lemon/dim2.h>
     73
    7374///\ingroup misc
    7475///\file
    … …  
    255256          --curr;
    256257        }
    257         curr[0] = (((curr[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^
     258        state[0] = (((state[0] & hiMask) | (curr[length - 1] & loMask)) >> 1) ^
    258259          curr[length - shift] ^ mask[curr[length - 1] & 1ul];
    259260
    … …  
    760761      double xi,nu;
    761762      const double delta = k-std::floor(k);
    762       const double v0=M_E/(M_E-delta);
     763      const double v0=E/(E-delta);
    763764      do {
    764765        double V0=1.0-real<double>();

  • lemon/tolerance.h

    r49 r72  
    4141  ///as a result of a probably inexact computation.
    4242  ///
    43   ///This is an abstract class, it should be specialized for all numerical
    44   ///data types. These specialized classes like \ref Tolerance<double>
    45   ///may offer additional tuning parameters.
     43  ///This is an abstract class, it should be specialized for all
     44  ///numerical data types. These specialized classes like
     45  ///Tolerance<double> may offer additional tuning parameters.
    4646  ///
    4747  ///\sa Tolerance<float>
    … …  
    118118
    119119    ///\name Comparisons
    120     ///See \ref Tolerance for more details.
     120    ///See \ref lemon::Tolerance "Tolerance" for more details.
    121121
    122122    ///@{
    … …  
    169169
    170170    ///\name Comparisons
    171     ///See \ref Tolerance for more details.
     171    ///See \ref lemon::Tolerance "Tolerance" for more details.
    172172
    173173    ///@{
    … …  
    220220
    221221    ///\name Comparisons
    222     ///See \ref Tolerance for more details.
     222    ///See \ref lemon::Tolerance "Tolerance" for more details.
    223223
    224224    ///@{
    … …  
    253253
    254254    ///\name Comparisons
    255     ///See \ref Tolerance for more details.
     255    ///See \ref lemon::Tolerance "Tolerance" for more details.
    256256
    257257    ///@{
    … …  
    276276  ///Unsigned integer specialization of Tolerance.
    277277
    278   ///Unsigned integer specialization of \ref Tolerance.
     278  ///Unsigned integer specialization of Tolerance.
    279279  ///\sa Tolerance
    280280  template<>
    … …  
    286286
    287287    ///\name Comparisons
    288     ///See \ref Tolerance for more details.
     288    ///See \ref lemon::Tolerance "Tolerance" for more details.
    289289
    290290    ///@{
    … …  
    320320
    321321    ///\name Comparisons
    322     ///See \ref Tolerance for more details.
     322    ///See \ref lemon::Tolerance "Tolerance" for more details.
    323323
    324324    ///@{
    … …  
    343343  ///Unsigned long integer specialization of Tolerance.
    344344
    345   ///Unsigned long integer specialization of \ref Tolerance.
     345  ///Unsigned long integer specialization of Tolerance.
    346346  ///\sa Tolerance
    347347  template<>
    … …  
    353353
    354354    ///\name Comparisons
    355     ///See \ref Tolerance for more details.
     355    ///See \ref lemon::Tolerance "Tolerance" for more details.
    356356
    357357    ///@{
    … …  
    378378  ///Long long integer specialization of Tolerance.
    379379
    380   ///Long long integer specialization of \ref Tolerance.
     380  ///Long long integer specialization of Tolerance.
    381381  ///\warning This class (more exactly, type <tt>long long</tt>)
    382382  ///is not ansi compatible.
    … …  
    390390
    391391    ///\name Comparisons
    392     ///See \ref Tolerance for more details.
     392    ///See \ref lemon::Tolerance "Tolerance" for more details.
    393393
    394394    ///@{
    … …  
    413413  ///Unsigned long long integer specialization of Tolerance.
    414414
    415   ///Unsigned long long integer specialization of \ref Tolerance.
     415  ///Unsigned long long integer specialization of Tolerance.
    416416  ///\warning This class (more exactly, type <tt>unsigned long long</tt>)
    417417  ///is not ansi compatible.
    … …  
    425425
    426426    ///\name Comparisons
    427     ///See \ref Tolerance for more details.
     427    ///See \ref lemon::Tolerance "Tolerance" for more details.
    428428
    429429    ///@{

  • test/Makefile.am

    r58 r67  
    1111        test/dim_test \
    1212        test/graph_test \
     13        test/maps_test \
    1314        test/random_test \
    1415        test/test_tools_fail \
    … …  
    2021test_digraph_test_SOURCES = test/digraph_test.cc
    2122test_dim_test_SOURCES = test/dim_test.cc
     23#test_error_test_SOURCES = test/error_test.cc
    2224test_graph_test_SOURCES = test/graph_test.cc
     25test_maps_test_SOURCES = test/maps_test.cc
    2326test_random_test_SOURCES = test/random_test.cc
    2427test_test_tools_fail_SOURCES = test/test_tools_fail.cc

  • test/maps_test.cc

    r39 r82  
    3838  typedef B result_type;
    3939
    40   B operator()(const A &) const {return B();}
     40  B operator()(const A&) const { return B(); }
     41private:
     42  F& operator=(const F&);
    4143};
    4244
    43 int func(A) {return 3;}
    44 
    45 int binc(int, B) {return 4;}
    46 
    47 typedef ReadMap<A,double> DoubleMap;
    48 typedef ReadWriteMap<A, double> WriteDoubleMap;
    49 
    50 typedef ReadMap<A,bool> BoolMap;
     45int func(A) { return 3; }
     46
     47int binc(int a, B) { return a+1; }
     48
     49typedef ReadMap<A, double> DoubleMap;
     50typedef ReadWriteMap<A, double> DoubleWriteMap;
     51typedef ReferenceMap<A, double, double&, const double&> DoubleRefMap;
     52
     53typedef ReadMap<A, bool> BoolMap;
    5154typedef ReadWriteMap<A, bool> BoolWriteMap;
     55typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;
    5256
    5357int main()
    54 { // checking graph components
    55  
     58{
     59  // Map concepts
    5660  checkConcept<ReadMap<A,B>, ReadMap<A,B> >();
    5761  checkConcept<WriteMap<A,B>, WriteMap<A,B> >();
    … …  
    5963  checkConcept<ReferenceMap<A,B,B&,const B&>, ReferenceMap<A,B,B&,const B&> >();
    6064
    61   checkConcept<ReadMap<A,double>, AddMap<DoubleMap,DoubleMap> >();
    62   checkConcept<ReadMap<A,double>, SubMap<DoubleMap,DoubleMap> >();
    63   checkConcept<ReadMap<A,double>, MulMap<DoubleMap,DoubleMap> >();
    64   checkConcept<ReadMap<A,double>, DivMap<DoubleMap,DoubleMap> >();
    65   checkConcept<ReadMap<A,double>, NegMap<DoubleMap> >();
    66   checkConcept<ReadWriteMap<A,double>, NegWriteMap<WriteDoubleMap> >();
    67   checkConcept<ReadMap<A,double>, AbsMap<DoubleMap> >();
    68   checkConcept<ReadMap<A,double>, ShiftMap<DoubleMap> >();
    69   checkConcept<ReadWriteMap<A,double>, ShiftWriteMap<WriteDoubleMap> >();
    70   checkConcept<ReadMap<A,double>, ScaleMap<DoubleMap> >();
    71   checkConcept<ReadWriteMap<A,double>, ScaleWriteMap<WriteDoubleMap> >();
    72   checkConcept<ReadMap<A,double>, ForkMap<DoubleMap, DoubleMap> >();
    73   checkConcept<ReadWriteMap<A,double>,
    74     ForkWriteMap<WriteDoubleMap, WriteDoubleMap> >();
    75  
    76   checkConcept<ReadMap<B,double>, ComposeMap<DoubleMap,ReadMap<B,A> > >();
    77 
    78   checkConcept<ReadMap<A,B>, FunctorMap<F, A, B> >();
    79 
    80   checkConcept<ReadMap<A, bool>, NotMap<BoolMap> >();
    81   checkConcept<ReadWriteMap<A, bool>, NotWriteMap<BoolWriteMap> >();
    82 
    83   checkConcept<WriteMap<A, bool>, StoreBoolMap<A*> >();
    84   checkConcept<WriteMap<A, bool>, BackInserterBoolMap<std::deque<A> > >();
    85   checkConcept<WriteMap<A, bool>, FrontInserterBoolMap<std::deque<A> > >();
    86   checkConcept<WriteMap<A, bool>, InserterBoolMap<std::set<A> > >();
    87   checkConcept<WriteMap<A, bool>, FillBoolMap<WriteMap<A, B> > >();
    88   checkConcept<WriteMap<A, bool>, SettingOrderBoolMap<WriteMap<A, int> > >();
    89 
    90   int a;
    91  
    92   a=mapFunctor(constMap<A,int>(2))(A());
    93   check(a==2,"Something is wrong with mapFunctor");
    94 
    95   B b;
    96   b=functorMap(F())[A()];
    97 
    98   a=functorMap(&func)[A()];
    99   check(a==3,"Something is wrong with functorMap");
    100 
    101   a=combineMap(constMap<B, int, 1>(), identityMap<B>(), &binc)[B()];
    102   check(a==4,"Something is wrong with combineMap");
    103  
    104 
    105   std::cout << __FILE__ ": All tests passed.\n";
    106  
     65  // NullMap
     66  {
     67    checkConcept<ReadWriteMap<A,B>, NullMap<A,B> >();
     68    NullMap<A,B> map1;
     69    NullMap<A,B> map2 = map1;
     70    map1 = nullMap<A,B>();
     71  }
     72
     73  // ConstMap
     74  {
     75    checkConcept<ReadWriteMap<A,B>, ConstMap<A,B> >();
     76    ConstMap<A,B> map1;
     77    ConstMap<A,B> map2(B());
     78    ConstMap<A,B> map3 = map1;
     79    map1 = constMap<A>(B());
     80    map1.setAll(B());
     81
     82    checkConcept<ReadWriteMap<A,int>, ConstMap<A,int> >();
     83    check(constMap<A>(10)[A()] == 10, "Something is wrong with ConstMap");
     84
     85    checkConcept<ReadWriteMap<A,int>, ConstMap<A,Const<int,10> > >();
     86    ConstMap<A,Const<int,10> > map4;
     87    ConstMap<A,Const<int,10> > map5 = map4;
     88    map4 = map5;
     89    check(map4[A()] == 10 && map5[A()] == 10, "Something is wrong with ConstMap");
     90  }
     91
     92  // IdentityMap
     93  {
     94    checkConcept<ReadMap<A,A>, IdentityMap<A> >();
     95    IdentityMap<A> map1;
     96    IdentityMap<A> map2 = map1;
     97    map1 = identityMap<A>();
     98
     99    checkConcept<ReadMap<double,double>, IdentityMap<double> >();
     100    check(identityMap<double>()[1.0] == 1.0 && identityMap<double>()[3.14] == 3.14,
     101          "Something is wrong with IdentityMap");
     102  }
     103
     104  // RangeMap
     105  {
     106    checkConcept<ReferenceMap<int,B,B&,const B&>, RangeMap<B> >();
     107    RangeMap<B> map1;
     108    RangeMap<B> map2(10);
     109    RangeMap<B> map3(10,B());
     110    RangeMap<B> map4 = map1;
     111    RangeMap<B> map5 = rangeMap<B>();
     112    RangeMap<B> map6 = rangeMap<B>(10);
     113    RangeMap<B> map7 = rangeMap(10,B());
     114
     115    checkConcept< ReferenceMap<int, double, double&, const double&>,
     116                  RangeMap<double> >();
     117    std::vector<double> v(10, 0);
     118    v[5] = 100;
     119    RangeMap<double> map8(v);
     120    RangeMap<double> map9 = rangeMap(v);
     121    check(map9.size() == 10 && map9[2] == 0 && map9[5] == 100,
     122          "Something is wrong with RangeMap");
     123  }
     124
     125  // SparseMap
     126  {
     127    checkConcept<ReferenceMap<A,B,B&,const B&>, SparseMap<A,B> >();
     128    SparseMap<A,B> map1;
     129    SparseMap<A,B> map2(B());
     130    SparseMap<A,B> map3 = sparseMap<A,B>();
     131    SparseMap<A,B> map4 = sparseMap<A>(B());
     132
     133    checkConcept< ReferenceMap<double, int, int&, const int&>,
     134                  SparseMap<double, int> >();
     135    std::map<double, int> m;
     136    SparseMap<double, int> map5(m);
     137    SparseMap<double, int> map6(m,10);
     138    SparseMap<double, int> map7 = sparseMap(m);
     139    SparseMap<double, int> map8 = sparseMap(m,10);
     140
     141    check(map5[1.0] == 0 && map5[3.14] == 0 && map6[1.0] == 10 && map6[3.14] == 10,
     142          "Something is wrong with SparseMap");
     143    map5[1.0] = map6[3.14] = 100;
     144    check(map5[1.0] == 100 && map5[3.14] == 0 && map6[1.0] == 10 && map6[3.14] == 100,
     145          "Something is wrong with SparseMap");
     146  }
     147
     148  // ComposeMap
     149  {
     150    typedef ComposeMap<DoubleMap, ReadMap<B,A> > CompMap;
     151    checkConcept<ReadMap<B,double>, CompMap>();
     152    CompMap map1(DoubleMap(),ReadMap<B,A>());
     153    CompMap map2 = composeMap(DoubleMap(), ReadMap<B,A>());
     154
     155    SparseMap<double, bool> m1(false); m1[3.14] = true;
     156    RangeMap<double> m2(2); m2[0] = 3.0; m2[1] = 3.14;
     157    check(!composeMap(m1,m2)[0] && composeMap(m1,m2)[1], "Something is wrong with ComposeMap")
     158  }
     159
     160  // CombineMap
     161  {
     162    typedef CombineMap<DoubleMap, DoubleMap, std::plus<double> > CombMap;
     163    checkConcept<ReadMap<A,double>, CombMap>();
     164    CombMap map1(DoubleMap(), DoubleMap());
     165    CombMap map2 = combineMap(DoubleMap(), DoubleMap(), std::plus<double>());
     166
     167    check(combineMap(constMap<B,int,2>(), identityMap<B>(), &binc)[B()] == 3,
     168          "Something is wrong with CombineMap");
     169  }
     170
     171  // FunctorToMap, MapToFunctor
     172  {
     173    checkConcept<ReadMap<A,B>, FunctorToMap<F,A,B> >();
     174    checkConcept<ReadMap<A,B>, FunctorToMap<F> >();
     175    FunctorToMap<F> map1;
     176    FunctorToMap<F> map2(F());
     177    B b = functorToMap(F())[A()];
     178
     179    checkConcept<ReadMap<A,B>, MapToFunctor<ReadMap<A,B> > >();
     180    MapToFunctor<ReadMap<A,B> > map(ReadMap<A,B>());
     181
     182    check(functorToMap(&func)[A()] == 3, "Something is wrong with FunctorToMap");
     183    check(mapToFunctor(constMap<A,int>(2))(A()) == 2, "Something is wrong with MapToFunctor");
     184    check(mapToFunctor(functorToMap(&func))(A()) == 3 && mapToFunctor(functorToMap(&func))[A()] == 3,
     185          "Something is wrong with FunctorToMap or MapToFunctor");
     186    check(functorToMap(mapToFunctor(constMap<A,int>(2)))[A()] == 2,
     187          "Something is wrong with FunctorToMap or MapToFunctor");
     188  }
     189
     190  // ConvertMap
     191  {
     192    checkConcept<ReadMap<double,double>, ConvertMap<ReadMap<double, int>, double> >();
     193    ConvertMap<RangeMap<bool>, int> map1(rangeMap(1, true));
     194    ConvertMap<RangeMap<bool>, int> map2 = convertMap<int>(rangeMap(2, false));
     195  }
     196
     197  // ForkMap
     198  {
     199    checkConcept<DoubleWriteMap, ForkMap<DoubleWriteMap, DoubleWriteMap> >();
     200
     201    typedef RangeMap<double> RM;
     202    typedef SparseMap<int, double> SM;
     203    RM m1(10, -1);
     204    SM m2(-1);
     205    checkConcept<ReadWriteMap<int, double>, ForkMap<RM, SM> >();
     206    checkConcept<ReadWriteMap<int, double>, ForkMap<SM, RM> >();
     207    ForkMap<RM, SM> map1(m1,m2);
     208    ForkMap<SM, RM> map2 = forkMap(m2,m1);
     209    map2.set(5, 10);
     210    check(m1[1] == -1 && m1[5] == 10 && m2[1] == -1 && m2[5] == 10 && map2[1] == -1 && map2[5] == 10,
     211          "Something is wrong with ForkMap");
     212  }
     213
     214  // Arithmetic maps:
     215  // - AddMap, SubMap, MulMap, DivMap
     216  // - ShiftMap, ShiftWriteMap, ScaleMap, ScaleWriteMap
     217  // - NegMap, NegWriteMap, AbsMap
     218  {
     219    checkConcept<DoubleMap, AddMap<DoubleMap,DoubleMap> >();
     220    checkConcept<DoubleMap, SubMap<DoubleMap,DoubleMap> >();
     221    checkConcept<DoubleMap, MulMap<DoubleMap,DoubleMap> >();
     222    checkConcept<DoubleMap, DivMap<DoubleMap,DoubleMap> >();
     223
     224    ConstMap<int, double> c1(1.0), c2(3.14);
     225    IdentityMap<int> im;
     226    ConvertMap<IdentityMap<int>, double> id(im);
     227    check(addMap(c1,id)[0] == 1.0  && addMap(c1,id)[10] == 11.0, "Something is wrong with AddMap");
     228    check(subMap(id,c1)[0] == -1.0 && subMap(id,c1)[10] == 9.0,  "Something is wrong with SubMap");
     229    check(mulMap(id,c2)[0] == 0    && mulMap(id,c2)[2]  == 6.28, "Something is wrong with MulMap");
     230    check(divMap(c2,id)[1] == 3.14 && divMap(c2,id)[2]  == 1.57, "Something is wrong with DivMap");
     231
     232    checkConcept<DoubleMap, ShiftMap<DoubleMap> >();
     233    checkConcept<DoubleWriteMap, ShiftWriteMap<DoubleWriteMap> >();
     234    checkConcept<DoubleMap, ScaleMap<DoubleMap> >();
     235    checkConcept<DoubleWriteMap, ScaleWriteMap<DoubleWriteMap> >();
     236    checkConcept<DoubleMap, NegMap<DoubleMap> >();
     237    checkConcept<DoubleWriteMap, NegWriteMap<DoubleWriteMap> >();
     238    checkConcept<DoubleMap, AbsMap<DoubleMap> >();
     239
     240    check(shiftMap(id, 2.0)[1] == 3.0 && shiftMap(id, 2.0)[10] == 12.0,
     241          "Something is wrong with ShiftMap");
     242    check(shiftWriteMap(id, 2.0)[1] == 3.0 && shiftWriteMap(id, 2.0)[10] == 12.0,
     243          "Something is wrong with ShiftWriteMap");
     244    check(scaleMap(id, 2.0)[1] == 2.0 && scaleMap(id, 2.0)[10] == 20.0,
     245          "Something is wrong with ScaleMap");
     246    check(scaleWriteMap(id, 2.0)[1] == 2.0 && scaleWriteMap(id, 2.0)[10] == 20.0,
     247          "Something is wrong with ScaleWriteMap");
     248    check(negMap(id)[1] == -1.0 && negMap(id)[-10] == 10.0,
     249          "Something is wrong with NegMap");
     250    check(negWriteMap(id)[1] == -1.0 && negWriteMap(id)[-10] == 10.0,
     251          "Something is wrong with NegWriteMap");
     252    check(absMap(id)[1] == 1.0 && absMap(id)[-10] == 10.0,
     253          "Something is wrong with AbsMap");
     254  }
     255
     256  // Logical maps:
     257  // - TrueMap, FalseMap
     258  // - AndMap, OrMap
     259  // - NotMap, NotWriteMap
     260  // - EqualMap, LessMap
     261  {
     262    checkConcept<BoolMap, TrueMap<A> >();
     263    checkConcept<BoolMap, FalseMap<A> >();
     264    checkConcept<BoolMap, AndMap<BoolMap,BoolMap> >();
     265    checkConcept<BoolMap, OrMap<BoolMap,BoolMap> >();
     266    checkConcept<BoolMap, NotMap<BoolMap> >();
     267    checkConcept<BoolWriteMap, NotWriteMap<BoolWriteMap> >();
     268    checkConcept<BoolMap, EqualMap<DoubleMap,DoubleMap> >();
     269    checkConcept<BoolMap, LessMap<DoubleMap,DoubleMap> >();
     270
     271    TrueMap<int> tm;
     272    FalseMap<int> fm;
     273    RangeMap<bool> rm(2);
     274    rm[0] = true; rm[1] = false;
     275    check(andMap(tm,rm)[0] && !andMap(tm,rm)[1] && !andMap(fm,rm)[0] && !andMap(fm,rm)[1],
     276          "Something is wrong with AndMap");
     277    check(orMap(tm,rm)[0] && orMap(tm,rm)[1] && orMap(fm,rm)[0] && !orMap(fm,rm)[1],
     278          "Something is wrong with OrMap");
     279    check(!notMap(rm)[0] && notMap(rm)[1], "Something is wrong with NotMap");
     280    check(!notWriteMap(rm)[0] && notWriteMap(rm)[1], "Something is wrong with NotWriteMap");
     281
     282    ConstMap<int, double> cm(2.0);
     283    IdentityMap<int> im;
     284    ConvertMap<IdentityMap<int>, double> id(im);
     285    check(lessMap(id,cm)[1] && !lessMap(id,cm)[2] && !lessMap(id,cm)[3],
     286          "Something is wrong with LessMap");
     287    check(!equalMap(id,cm)[1] && equalMap(id,cm)[2] && !equalMap(id,cm)[3],
     288          "Something is wrong with EqualMap");
     289  }
     290
    107291  return 0;
    108292}
Note: See TracChangeset for help on using the changeset viewer.