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 / [78:c46b3453455f:84:8161012eaa61] in lemon-main


Ignore:
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • doc/groups.dox

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

  • lemon/concepts/maps.h

    r74 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>
    … …  
    5958          Value val = m[key];
    6059          val = m[key];
    61           typename _ReadMap::Value own_val = m[own_key];
    62           own_val = m[own_key];
    63 
    64           ignore_unused_variable_warning(val);
    65           ignore_unused_variable_warning(own_val);
    66           ignore_unused_variable_warning(key);
    67         }
    68         Key& key;
    69         typename _ReadMap::Key& own_key;
    70         _ReadMap& m;
    71       };
    72      
    73     };
    74 
    75 
    76     /// Writable map concept
    77    
    78     /// Writable map concept.
    79     ///
    80     template<typename K, typename T>
    81     class WriteMap
    82     {
    83     public:
    84       /// The key type of the map.
    85       typedef K Key;   
    86       /// The value type of the map. (The type of objects associated with the keys).
    87       typedef T Value;
    88 
    89       /// Sets the value associated with a key.
    90       void set(const Key &,const Value &) {}
    91 
    92       ///Default constructor
    93       WriteMap() {}
    94 
    95       template <typename _WriteMap>
    96       struct Constraints {
    97         void constraints() {
    98           // No constraints for constructor.
    99           m.set(key, val);
    100           m.set(own_key, own_val);
     60          typename _ReadMap::Value own_val = m[own_key];
     61          own_val = m[own_key];
     62
    10163          ignore_unused_variable_warning(key);
    10264          ignore_unused_variable_warning(val);
    … …  
    10466          ignore_unused_variable_warning(own_val);
    10567        }
    106 
    107         Value& val;
    108         typename _WriteMap::Value own_val;
    109         Key& key;
    110         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;
    111110        _WriteMap& m;
    112 
    113111      };
    114112    };
    115113
    116114    /// Read/writable map concept
    117    
     115
    118116    /// Read/writable map concept.
    119117    ///
    … …  
    124122    public:
    125123      /// The key type of the map.
    126       typedef K Key;   
    127       /// The value type of the map. (The type of objects associated with the keys).
    128       typedef T Value;
    129 
    130       /// Returns the value associated with a key.
    131       Value operator[](const Key &) const {return Value();}
    132       /// Sets the value associated with a key.
    133       void set(const Key & ,const Value &) {}
     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 &) {}
    134133
    135134      template<typename _ReadWriteMap>
    … …  
    141140      };
    142141    };
    143  
    144  
     142
     143
    145144    /// Dereferable map concept
    146    
     145
    147146    /// Dereferable map concept.
    148147    ///
    149     /// \todo Rethink this concept.
    150148    template<typename K, typename T, typename R, typename CR>
    151149    class ReferenceMap : public ReadWriteMap<K,T>
    … …  
    155153      typedef True ReferenceMapTag;
    156154      /// The key type of the map.
    157       typedef K Key;   
     155      typedef K Key;
    158156      /// The value type of the map. (The type of objects associated with the keys).
    159157      typedef T Value;
    … …  
    167165    public:
    168166
    169       ///Returns a reference to the value associated with a key.
     167      /// Returns a reference to the value associated with the given key.
    170168      Reference operator[](const Key &) { return tmp; }
    171       ///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.
    172171      ConstReference operator[](const Key &) const { return tmp; }
    173       /// Sets the value associated with a key.
     172
     173      /// Sets the value associated with the given key.
    174174      void set(const Key &k,const Value &t) { operator[](k)=t; }
    175175
    … …  
    178178        void constraints() {
    179179          checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
     180          ref = m[key];
    180181          m[key] = val;
    181           val  = m[key];
    182182          m[key] = ref;
    183           ref = m[key];
     183          m[key] = cref;
     184          own_ref = m[own_key];
    184185          m[own_key] = own_val;
    185           own_val  = m[own_key];
    186186          m[own_key] = own_ref;
    187           own_ref = m[own_key];           
    188         }
    189 
    190         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;
    191196        typename _ReferenceMap::Value& own_val;
    192197        typename _ReferenceMap::Reference own_ref;
    193         Key& key;
    194         Value& val;
    195         Reference ref;
     198        typename _ReferenceMap::ConstReference own_cref;
    196199        _ReferenceMap& m;
    197200      };

  • 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  /// @}

  • 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.