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


Ignore:
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • doc/groups.dox

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

  • lemon/concepts/maps.h

    r79 r74  
    3030
    3131  namespace concepts {
    32 
     32 
    3333    /// \addtogroup concept
    3434    /// @{
    … …  
    4343    public:
    4444      /// The key type of the map.
    45       typedef K Key;
    46       /// The value type of the map. (The type of objects associated with the keys).
    47       typedef T Value;
    48 
    49       /// Returns the value associated with the given key.
    50 
    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(); }
     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();}
    5455
    5556      template<typename _ReadMap>
    … …  
    5859          Value val = m[key];
    5960          val = m[key];
    60           typename _ReadMap::Value own_val = m[own_key];
    61           own_val = m[own_key];
    62 
     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);
    63101          ignore_unused_variable_warning(key);
    64102          ignore_unused_variable_warning(val);
    … …  
    66104          ignore_unused_variable_warning(own_val);
    67105        }
    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;
     106
     107        Value& val;
     108        typename _WriteMap::Value own_val;
     109        Key& key;
     110        typename _WriteMap::Key& own_key;
    110111        _WriteMap& m;
     112
    111113      };
    112114    };
    113115
    114116    /// Read/writable map concept
    115 
     117   
    116118    /// Read/writable map concept.
    117119    ///
    … …  
    122124    public:
    123125      /// The key type of the map.
    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 &) {}
     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 &) {}
    133134
    134135      template<typename _ReadWriteMap>
    … …  
    140141      };
    141142    };
    142 
    143 
     143 
     144 
    144145    /// Dereferable map concept
    145 
     146   
    146147    /// Dereferable map concept.
    147148    ///
     149    /// \todo Rethink this concept.
    148150    template<typename K, typename T, typename R, typename CR>
    149151    class ReferenceMap : public ReadWriteMap<K,T>
    … …  
    153155      typedef True ReferenceMapTag;
    154156      /// The key type of the map.
    155       typedef K Key;
     157      typedef K Key;   
    156158      /// The value type of the map. (The type of objects associated with the keys).
    157159      typedef T Value;
    … …  
    165167    public:
    166168
    167       /// Returns a reference to the value associated with the given key.
     169      ///Returns a reference to the value associated with a key.
    168170      Reference operator[](const Key &) { return tmp; }
    169 
    170       /// Returns a const reference to the value associated with the given key.
     171      ///Returns a const reference to the value associated with a key.
    171172      ConstReference operator[](const Key &) const { return tmp; }
    172 
    173       /// Sets the value associated with the given key.
     173      /// Sets the value associated with a key.
    174174      void set(const Key &k,const Value &t) { operator[](k)=t; }
    175175
    … …  
    178178        void constraints() {
    179179          checkConcept<ReadWriteMap<K, T>, _ReferenceMap >();
     180          m[key] = val;
     181          val  = m[key];
     182          m[key] = ref;
    180183          ref = m[key];
    181           m[key] = val;
    182           m[key] = ref;
    183           m[key] = cref;
    184           own_ref = m[own_key];
    185184          m[own_key] = own_val;
     185          own_val  = m[own_key];
    186186          m[own_key] = own_ref;
    187           m[own_key] = own_cref;
    188           m[key] = m[own_key];
    189           m[own_key] = m[key];
    190         }
    191         const Key& key;
     187          own_ref = m[own_key];           
     188        }
     189
     190        typename _ReferenceMap::Key& own_key;
     191        typename _ReferenceMap::Value& own_val;
     192        typename _ReferenceMap::Reference own_ref;
     193        Key& key;
    192194        Value& val;
    193195        Reference ref;
    194         ConstReference cref;
    195         const typename _ReferenceMap::Key& own_key;
    196         typename _ReferenceMap::Value& own_val;
    197         typename _ReferenceMap::Reference own_ref;
    198         typename _ReferenceMap::ConstReference own_cref;
    199196        _ReferenceMap& m;
    200197      };

  • lemon/maps.h

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

  • test/maps_test.cc

    r82 r39  
    3838  typedef B result_type;
    3939
    40   B operator()(const A&) const { return B(); }
    41 private:
    42   F& operator=(const F&);
     40  B operator()(const A &) const {return B();}
    4341};
    4442
    45 int func(A) { return 3; }
     43int func(A) {return 3;}
    4644
    47 int binc(int a, B) { return a+1; }
     45int binc(int, B) {return 4;}
    4846
    49 typedef ReadMap<A, double> DoubleMap;
    50 typedef ReadWriteMap<A, double> DoubleWriteMap;
    51 typedef ReferenceMap<A, double, double&, const double&> DoubleRefMap;
     47typedef ReadMap<A,double> DoubleMap;
     48typedef ReadWriteMap<A, double> WriteDoubleMap;
    5249
    53 typedef ReadMap<A, bool> BoolMap;
     50typedef ReadMap<A,bool> BoolMap;
    5451typedef ReadWriteMap<A, bool> BoolWriteMap;
    55 typedef ReferenceMap<A, bool, bool&, const bool&> BoolRefMap;
    5652
    5753int main()
    58 {
    59   // Map concepts
     54{ // checking graph components
     55 
    6056  checkConcept<ReadMap<A,B>, ReadMap<A,B> >();
    6157  checkConcept<WriteMap<A,B>, WriteMap<A,B> >();
    … …  
    6359  checkConcept<ReferenceMap<A,B,B&,const B&>, ReferenceMap<A,B,B&,const B&> >();
    6460
    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   }
     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> > >();
    7277
    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());
     78  checkConcept<ReadMap<A,B>, FunctorMap<F, A, B> >();
    8179
    82     checkConcept<ReadWriteMap<A,int>, ConstMap<A,int> >();
    83     check(constMap<A>(10)[A()] == 10, "Something is wrong with ConstMap");
     80  checkConcept<ReadMap<A, bool>, NotMap<BoolMap> >();
     81  checkConcept<ReadWriteMap<A, bool>, NotWriteMap<BoolWriteMap> >();
    8482
    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   }
     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> > >();
    9189
    92   // IdentityMap
    93   {
    94     checkConcept<ReadMap<A,A>, IdentityMap<A> >();
    95     IdentityMap<A> map1;
    96     IdentityMap<A> map2 = map1;
    97     map1 = identityMap<A>();
     90  int a;
     91 
     92  a=mapFunctor(constMap<A,int>(2))(A());
     93  check(a==2,"Something is wrong with mapFunctor");
    9894
    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   }
     95  B b;
     96  b=functorMap(F())[A()];
    10397
    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());
     98  a=functorMap(&func)[A()];
     99  check(a==3,"Something is wrong with functorMap");
    114100
    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   }
     101  a=combineMap(constMap<B, int, 1>(), identityMap<B>(), &binc)[B()];
     102  check(a==4,"Something is wrong with combineMap");
     103 
    124104
    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 
     105  std::cout << __FILE__ ": All tests passed.\n";
     106 
    291107  return 0;
    292108}
Note: See TracChangeset for help on using the changeset viewer.