lemon/maps.h
author Balazs Dezso <deba@inf.elte.hu>
Fri, 11 Jul 2008 15:01:49 +0200
changeset 203 215bfc30b14f
parent 159 c7d30f7810e5
child 209 765619b7cbb2
permissions -rw-r--r--
Cleaning of heap test and bug fix in heap concept check (ticket #100)

* The dijkstra heap test's digraph is inlined into the source file
* The random sequences are fixed
* The content of the header is moved to the source file
* Only the binary heap is checked
alpar@25
     1
/* -*- C++ -*-
alpar@25
     2
 *
alpar@25
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@25
     4
 *
alpar@39
     5
 * Copyright (C) 2003-2008
alpar@25
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@25
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@25
     8
 *
alpar@25
     9
 * Permission to use, modify and distribute this software is granted
alpar@25
    10
 * provided that this copyright notice appears in all copies. For
alpar@25
    11
 * precise terms see the accompanying LICENSE file.
alpar@25
    12
 *
alpar@25
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@25
    14
 * express or implied, and with no claim as to its suitability for any
alpar@25
    15
 * purpose.
alpar@25
    16
 *
alpar@25
    17
 */
alpar@25
    18
alpar@25
    19
#ifndef LEMON_MAPS_H
alpar@25
    20
#define LEMON_MAPS_H
alpar@25
    21
alpar@25
    22
#include <iterator>
alpar@25
    23
#include <functional>
alpar@25
    24
#include <vector>
alpar@25
    25
alpar@25
    26
#include <lemon/bits/utility.h>
kpeter@80
    27
#include <lemon/bits/traits.h>
alpar@25
    28
alpar@25
    29
///\file
alpar@25
    30
///\ingroup maps
alpar@25
    31
///\brief Miscellaneous property maps
kpeter@80
    32
alpar@25
    33
#include <map>
alpar@25
    34
alpar@25
    35
namespace lemon {
alpar@25
    36
alpar@25
    37
  /// \addtogroup maps
alpar@25
    38
  /// @{
alpar@25
    39
alpar@25
    40
  /// Base class of maps.
alpar@25
    41
kpeter@80
    42
  /// Base class of maps. It provides the necessary type definitions
kpeter@80
    43
  /// required by the map %concepts.
kpeter@80
    44
  template<typename K, typename V>
alpar@25
    45
  class MapBase {
alpar@25
    46
  public:
kpeter@80
    47
    /// \biref The key type of the map.
alpar@25
    48
    typedef K Key;
kpeter@80
    49
    /// \brief The value type of the map.
kpeter@80
    50
    /// (The type of objects associated with the keys).
kpeter@80
    51
    typedef V Value;
alpar@25
    52
  };
alpar@25
    53
kpeter@80
    54
alpar@25
    55
  /// Null map. (a.k.a. DoNothingMap)
alpar@25
    56
kpeter@29
    57
  /// This map can be used if you have to provide a map only for
kpeter@80
    58
  /// its type definitions, or if you have to provide a writable map,
kpeter@80
    59
  /// but data written to it is not required (i.e. it will be sent to
kpeter@29
    60
  /// <tt>/dev/null</tt>).
kpeter@80
    61
  /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
kpeter@80
    62
  ///
kpeter@80
    63
  /// \sa ConstMap
kpeter@80
    64
  template<typename K, typename V>
kpeter@80
    65
  class NullMap : public MapBase<K, V> {
alpar@25
    66
  public:
kpeter@80
    67
    typedef MapBase<K, V> Parent;
alpar@25
    68
    typedef typename Parent::Key Key;
alpar@25
    69
    typedef typename Parent::Value Value;
kpeter@80
    70
alpar@25
    71
    /// Gives back a default constructed element.
kpeter@80
    72
    Value operator[](const Key&) const { return Value(); }
alpar@25
    73
    /// Absorbs the value.
kpeter@80
    74
    void set(const Key&, const Value&) {}
alpar@25
    75
  };
alpar@25
    76
kpeter@80
    77
  /// Returns a \ref NullMap class
kpeter@29
    78
kpeter@80
    79
  /// This function just returns a \ref NullMap class.
kpeter@80
    80
  /// \relates NullMap
kpeter@80
    81
  template <typename K, typename V>
alpar@25
    82
  NullMap<K, V> nullMap() {
alpar@25
    83
    return NullMap<K, V>();
alpar@25
    84
  }
alpar@25
    85
alpar@25
    86
alpar@25
    87
  /// Constant map.
alpar@25
    88
kpeter@82
    89
  /// This \ref concepts::ReadMap "readable map" assigns a specified
kpeter@82
    90
  /// value to each key.
kpeter@80
    91
  ///
kpeter@80
    92
  /// In other aspects it is equivalent to \ref NullMap.
kpeter@80
    93
  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
kpeter@80
    94
  /// concept, but it absorbs the data written to it.
kpeter@80
    95
  ///
kpeter@80
    96
  /// The simplest way of using this map is through the constMap()
kpeter@80
    97
  /// function.
kpeter@80
    98
  ///
kpeter@80
    99
  /// \sa NullMap
kpeter@80
   100
  /// \sa IdentityMap
kpeter@80
   101
  template<typename K, typename V>
kpeter@80
   102
  class ConstMap : public MapBase<K, V> {
alpar@25
   103
  private:
kpeter@80
   104
    V _value;
alpar@25
   105
  public:
kpeter@80
   106
    typedef MapBase<K, V> Parent;
alpar@25
   107
    typedef typename Parent::Key Key;
alpar@25
   108
    typedef typename Parent::Value Value;
alpar@25
   109
alpar@25
   110
    /// Default constructor
alpar@25
   111
kpeter@29
   112
    /// Default constructor.
kpeter@80
   113
    /// The value of the map will be default constructed.
alpar@25
   114
    ConstMap() {}
kpeter@80
   115
kpeter@29
   116
    /// Constructor with specified initial value
alpar@25
   117
kpeter@29
   118
    /// Constructor with specified initial value.
kpeter@123
   119
    /// \param v The initial value of the map.
kpeter@80
   120
    ConstMap(const Value &v) : _value(v) {}
alpar@25
   121
kpeter@80
   122
    /// Gives back the specified value.
kpeter@80
   123
    Value operator[](const Key&) const { return _value; }
alpar@25
   124
kpeter@80
   125
    /// Absorbs the value.
kpeter@80
   126
    void set(const Key&, const Value&) {}
kpeter@80
   127
kpeter@80
   128
    /// Sets the value that is assigned to each key.
kpeter@80
   129
    void setAll(const Value &v) {
kpeter@80
   130
      _value = v;
kpeter@80
   131
    }
kpeter@80
   132
kpeter@80
   133
    template<typename V1>
kpeter@80
   134
    ConstMap(const ConstMap<K, V1> &, const Value &v) : _value(v) {}
alpar@25
   135
  };
alpar@25
   136
kpeter@80
   137
  /// Returns a \ref ConstMap class
alpar@25
   138
kpeter@80
   139
  /// This function just returns a \ref ConstMap class.
kpeter@80
   140
  /// \relates ConstMap
kpeter@80
   141
  template<typename K, typename V>
alpar@25
   142
  inline ConstMap<K, V> constMap(const V &v) {
alpar@25
   143
    return ConstMap<K, V>(v);
alpar@25
   144
  }
alpar@25
   145
kpeter@123
   146
  template<typename K, typename V>
kpeter@123
   147
  inline ConstMap<K, V> constMap() {
kpeter@123
   148
    return ConstMap<K, V>();
kpeter@123
   149
  }
kpeter@123
   150
alpar@25
   151
alpar@25
   152
  template<typename T, T v>
kpeter@80
   153
  struct Const {};
alpar@25
   154
alpar@25
   155
  /// Constant map with inlined constant value.
alpar@25
   156
kpeter@82
   157
  /// This \ref concepts::ReadMap "readable map" assigns a specified
kpeter@82
   158
  /// value to each key.
kpeter@80
   159
  ///
kpeter@80
   160
  /// In other aspects it is equivalent to \ref NullMap.
kpeter@80
   161
  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
kpeter@80
   162
  /// concept, but it absorbs the data written to it.
kpeter@80
   163
  ///
kpeter@80
   164
  /// The simplest way of using this map is through the constMap()
kpeter@80
   165
  /// function.
kpeter@80
   166
  ///
kpeter@80
   167
  /// \sa NullMap
kpeter@80
   168
  /// \sa IdentityMap
alpar@25
   169
  template<typename K, typename V, V v>
alpar@25
   170
  class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
alpar@25
   171
  public:
alpar@25
   172
    typedef MapBase<K, V> Parent;
alpar@25
   173
    typedef typename Parent::Key Key;
alpar@25
   174
    typedef typename Parent::Value Value;
alpar@25
   175
kpeter@80
   176
    /// Constructor.
kpeter@80
   177
    ConstMap() {}
kpeter@80
   178
kpeter@80
   179
    /// Gives back the specified value.
kpeter@80
   180
    Value operator[](const Key&) const { return v; }
kpeter@80
   181
kpeter@80
   182
    /// Absorbs the value.
kpeter@80
   183
    void set(const Key&, const Value&) {}
alpar@25
   184
  };
alpar@25
   185
kpeter@80
   186
  /// Returns a \ref ConstMap class with inlined constant value
alpar@25
   187
kpeter@80
   188
  /// This function just returns a \ref ConstMap class with inlined
kpeter@80
   189
  /// constant value.
kpeter@80
   190
  /// \relates ConstMap
kpeter@80
   191
  template<typename K, typename V, V v>
alpar@25
   192
  inline ConstMap<K, Const<V, v> > constMap() {
alpar@25
   193
    return ConstMap<K, Const<V, v> >();
alpar@25
   194
  }
alpar@25
   195
alpar@25
   196
kpeter@82
   197
  /// Identity map.
kpeter@82
   198
kpeter@82
   199
  /// This \ref concepts::ReadMap "read-only map" gives back the given
kpeter@82
   200
  /// key as value without any modification.
kpeter@80
   201
  ///
kpeter@80
   202
  /// \sa ConstMap
kpeter@80
   203
  template <typename T>
kpeter@80
   204
  class IdentityMap : public MapBase<T, T> {
kpeter@80
   205
  public:
kpeter@80
   206
    typedef MapBase<T, T> Parent;
kpeter@80
   207
    typedef typename Parent::Key Key;
kpeter@80
   208
    typedef typename Parent::Value Value;
kpeter@80
   209
kpeter@80
   210
    /// Gives back the given value without any modification.
kpeter@82
   211
    Value operator[](const Key &k) const {
kpeter@82
   212
      return k;
kpeter@80
   213
    }
kpeter@80
   214
  };
kpeter@80
   215
kpeter@80
   216
  /// Returns an \ref IdentityMap class
kpeter@80
   217
kpeter@80
   218
  /// This function just returns an \ref IdentityMap class.
kpeter@80
   219
  /// \relates IdentityMap
kpeter@80
   220
  template<typename T>
kpeter@80
   221
  inline IdentityMap<T> identityMap() {
kpeter@80
   222
    return IdentityMap<T>();
kpeter@80
   223
  }
kpeter@80
   224
kpeter@80
   225
kpeter@80
   226
  /// \brief Map for storing values for integer keys from the range
kpeter@80
   227
  /// <tt>[0..size-1]</tt>.
kpeter@80
   228
  ///
kpeter@80
   229
  /// This map is essentially a wrapper for \c std::vector. It assigns
kpeter@80
   230
  /// values to integer keys from the range <tt>[0..size-1]</tt>.
kpeter@80
   231
  /// It can be used with some data structures, for example
kpeter@80
   232
  /// \ref UnionFind, \ref BinHeap, when the used items are small
kpeter@80
   233
  /// integers. This map conforms the \ref concepts::ReferenceMap
kpeter@80
   234
  /// "ReferenceMap" concept.
kpeter@80
   235
  ///
kpeter@80
   236
  /// The simplest way of using this map is through the rangeMap()
kpeter@80
   237
  /// function.
kpeter@80
   238
  template <typename V>
kpeter@80
   239
  class RangeMap : public MapBase<int, V> {
kpeter@80
   240
    template <typename V1>
kpeter@80
   241
    friend class RangeMap;
kpeter@80
   242
  private:
kpeter@80
   243
kpeter@80
   244
    typedef std::vector<V> Vector;
kpeter@80
   245
    Vector _vector;
kpeter@80
   246
alpar@25
   247
  public:
alpar@25
   248
kpeter@80
   249
    typedef MapBase<int, V> Parent;
kpeter@80
   250
    /// Key type
kpeter@45
   251
    typedef typename Parent::Key Key;
kpeter@80
   252
    /// Value type
kpeter@45
   253
    typedef typename Parent::Value Value;
kpeter@80
   254
    /// Reference type
kpeter@80
   255
    typedef typename Vector::reference Reference;
kpeter@80
   256
    /// Const reference type
kpeter@80
   257
    typedef typename Vector::const_reference ConstReference;
kpeter@80
   258
kpeter@80
   259
    typedef True ReferenceMapTag;
kpeter@80
   260
kpeter@80
   261
  public:
kpeter@80
   262
kpeter@80
   263
    /// Constructor with specified default value.
kpeter@80
   264
    RangeMap(int size = 0, const Value &value = Value())
kpeter@80
   265
      : _vector(size, value) {}
kpeter@80
   266
kpeter@80
   267
    /// Constructs the map from an appropriate \c std::vector.
kpeter@80
   268
    template <typename V1>
kpeter@80
   269
    RangeMap(const std::vector<V1>& vector)
kpeter@80
   270
      : _vector(vector.begin(), vector.end()) {}
kpeter@80
   271
kpeter@80
   272
    /// Constructs the map from another \ref RangeMap.
kpeter@80
   273
    template <typename V1>
kpeter@80
   274
    RangeMap(const RangeMap<V1> &c)
kpeter@80
   275
      : _vector(c._vector.begin(), c._vector.end()) {}
kpeter@80
   276
kpeter@80
   277
    /// Returns the size of the map.
kpeter@80
   278
    int size() {
kpeter@80
   279
      return _vector.size();
kpeter@80
   280
    }
kpeter@80
   281
kpeter@80
   282
    /// Resizes the map.
kpeter@80
   283
kpeter@80
   284
    /// Resizes the underlying \c std::vector container, so changes the
kpeter@80
   285
    /// keyset of the map.
kpeter@80
   286
    /// \param size The new size of the map. The new keyset will be the
kpeter@80
   287
    /// range <tt>[0..size-1]</tt>.
kpeter@80
   288
    /// \param value The default value to assign to the new keys.
kpeter@80
   289
    void resize(int size, const Value &value = Value()) {
kpeter@80
   290
      _vector.resize(size, value);
kpeter@80
   291
    }
kpeter@80
   292
kpeter@80
   293
  private:
kpeter@80
   294
kpeter@80
   295
    RangeMap& operator=(const RangeMap&);
kpeter@80
   296
kpeter@80
   297
  public:
kpeter@80
   298
kpeter@80
   299
    ///\e
kpeter@80
   300
    Reference operator[](const Key &k) {
kpeter@80
   301
      return _vector[k];
kpeter@80
   302
    }
kpeter@80
   303
kpeter@80
   304
    ///\e
kpeter@80
   305
    ConstReference operator[](const Key &k) const {
kpeter@80
   306
      return _vector[k];
kpeter@80
   307
    }
kpeter@80
   308
kpeter@80
   309
    ///\e
kpeter@80
   310
    void set(const Key &k, const Value &v) {
kpeter@80
   311
      _vector[k] = v;
kpeter@80
   312
    }
kpeter@80
   313
  };
kpeter@80
   314
kpeter@80
   315
  /// Returns a \ref RangeMap class
kpeter@80
   316
kpeter@80
   317
  /// This function just returns a \ref RangeMap class.
kpeter@80
   318
  /// \relates RangeMap
kpeter@80
   319
  template<typename V>
kpeter@80
   320
  inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
kpeter@80
   321
    return RangeMap<V>(size, value);
kpeter@80
   322
  }
kpeter@80
   323
kpeter@80
   324
  /// \brief Returns a \ref RangeMap class created from an appropriate
kpeter@80
   325
  /// \c std::vector
kpeter@80
   326
kpeter@80
   327
  /// This function just returns a \ref RangeMap class created from an
kpeter@80
   328
  /// appropriate \c std::vector.
kpeter@80
   329
  /// \relates RangeMap
kpeter@80
   330
  template<typename V>
kpeter@80
   331
  inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
kpeter@80
   332
    return RangeMap<V>(vector);
kpeter@80
   333
  }
kpeter@80
   334
kpeter@80
   335
kpeter@80
   336
  /// Map type based on \c std::map
kpeter@80
   337
kpeter@80
   338
  /// This map is essentially a wrapper for \c std::map with addition
kpeter@80
   339
  /// that you can specify a default value for the keys that are not
kpeter@80
   340
  /// stored actually. This value can be different from the default
kpeter@80
   341
  /// contructed value (i.e. \c %Value()).
kpeter@80
   342
  /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
kpeter@80
   343
  /// concept.
kpeter@80
   344
  ///
kpeter@80
   345
  /// This map is useful if a default value should be assigned to most of
kpeter@80
   346
  /// the keys and different values should be assigned only to a few
kpeter@80
   347
  /// keys (i.e. the map is "sparse").
kpeter@80
   348
  /// The name of this type also refers to this important usage.
kpeter@80
   349
  ///
kpeter@80
   350
  /// Apart form that this map can be used in many other cases since it
kpeter@80
   351
  /// is based on \c std::map, which is a general associative container.
kpeter@80
   352
  /// However keep in mind that it is usually not as efficient as other
kpeter@80
   353
  /// maps.
kpeter@80
   354
  ///
kpeter@80
   355
  /// The simplest way of using this map is through the sparseMap()
kpeter@80
   356
  /// function.
kpeter@80
   357
  template <typename K, typename V, typename Compare = std::less<K> >
kpeter@80
   358
  class SparseMap : public MapBase<K, V> {
kpeter@80
   359
    template <typename K1, typename V1, typename C1>
kpeter@80
   360
    friend class SparseMap;
kpeter@80
   361
  public:
kpeter@80
   362
kpeter@80
   363
    typedef MapBase<K, V> Parent;
kpeter@80
   364
    /// Key type
kpeter@80
   365
    typedef typename Parent::Key Key;
kpeter@80
   366
    /// Value type
kpeter@80
   367
    typedef typename Parent::Value Value;
kpeter@80
   368
    /// Reference type
kpeter@80
   369
    typedef Value& Reference;
kpeter@80
   370
    /// Const reference type
kpeter@80
   371
    typedef const Value& ConstReference;
alpar@25
   372
kpeter@45
   373
    typedef True ReferenceMapTag;
kpeter@45
   374
alpar@25
   375
  private:
kpeter@80
   376
kpeter@80
   377
    typedef std::map<K, V, Compare> Map;
kpeter@80
   378
    Map _map;
alpar@25
   379
    Value _value;
alpar@25
   380
alpar@25
   381
  public:
alpar@25
   382
kpeter@80
   383
    /// \brief Constructor with specified default value.
kpeter@80
   384
    SparseMap(const Value &value = Value()) : _value(value) {}
kpeter@80
   385
    /// \brief Constructs the map from an appropriate \c std::map, and
kpeter@47
   386
    /// explicitly specifies a default value.
kpeter@80
   387
    template <typename V1, typename Comp1>
kpeter@80
   388
    SparseMap(const std::map<Key, V1, Comp1> &map,
kpeter@80
   389
              const Value &value = Value())
alpar@25
   390
      : _map(map.begin(), map.end()), _value(value) {}
kpeter@80
   391
kpeter@80
   392
    /// \brief Constructs the map from another \ref SparseMap.
kpeter@80
   393
    template<typename V1, typename Comp1>
kpeter@80
   394
    SparseMap(const SparseMap<Key, V1, Comp1> &c)
alpar@25
   395
      : _map(c._map.begin(), c._map.end()), _value(c._value) {}
alpar@25
   396
alpar@25
   397
  private:
alpar@25
   398
kpeter@80
   399
    SparseMap& operator=(const SparseMap&);
alpar@25
   400
alpar@25
   401
  public:
alpar@25
   402
alpar@25
   403
    ///\e
alpar@25
   404
    Reference operator[](const Key &k) {
alpar@25
   405
      typename Map::iterator it = _map.lower_bound(k);
alpar@25
   406
      if (it != _map.end() && !_map.key_comp()(k, it->first))
alpar@25
   407
	return it->second;
alpar@25
   408
      else
alpar@25
   409
	return _map.insert(it, std::make_pair(k, _value))->second;
alpar@25
   410
    }
alpar@25
   411
kpeter@80
   412
    ///\e
alpar@25
   413
    ConstReference operator[](const Key &k) const {
alpar@25
   414
      typename Map::const_iterator it = _map.find(k);
alpar@25
   415
      if (it != _map.end())
alpar@25
   416
	return it->second;
alpar@25
   417
      else
alpar@25
   418
	return _value;
alpar@25
   419
    }
alpar@25
   420
kpeter@80
   421
    ///\e
kpeter@80
   422
    void set(const Key &k, const Value &v) {
alpar@25
   423
      typename Map::iterator it = _map.lower_bound(k);
alpar@25
   424
      if (it != _map.end() && !_map.key_comp()(k, it->first))
kpeter@80
   425
	it->second = v;
alpar@25
   426
      else
kpeter@80
   427
	_map.insert(it, std::make_pair(k, v));
alpar@25
   428
    }
alpar@25
   429
kpeter@80
   430
    ///\e
kpeter@80
   431
    void setAll(const Value &v) {
kpeter@80
   432
      _value = v;
alpar@25
   433
      _map.clear();
kpeter@80
   434
    }
kpeter@80
   435
  };
alpar@25
   436
kpeter@80
   437
  /// Returns a \ref SparseMap class
kpeter@45
   438
kpeter@80
   439
  /// This function just returns a \ref SparseMap class with specified
kpeter@80
   440
  /// default value.
kpeter@80
   441
  /// \relates SparseMap
kpeter@80
   442
  template<typename K, typename V, typename Compare>
kpeter@80
   443
  inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
kpeter@80
   444
    return SparseMap<K, V, Compare>(value);
kpeter@54
   445
  }
kpeter@45
   446
kpeter@80
   447
  template<typename K, typename V>
kpeter@80
   448
  inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
kpeter@80
   449
    return SparseMap<K, V, std::less<K> >(value);
kpeter@45
   450
  }
alpar@25
   451
kpeter@80
   452
  /// \brief Returns a \ref SparseMap class created from an appropriate
kpeter@80
   453
  /// \c std::map
alpar@25
   454
kpeter@80
   455
  /// This function just returns a \ref SparseMap class created from an
kpeter@80
   456
  /// appropriate \c std::map.
kpeter@80
   457
  /// \relates SparseMap
kpeter@80
   458
  template<typename K, typename V, typename Compare>
kpeter@80
   459
  inline SparseMap<K, V, Compare>
kpeter@80
   460
    sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
kpeter@80
   461
  {
kpeter@80
   462
    return SparseMap<K, V, Compare>(map, value);
kpeter@45
   463
  }
alpar@25
   464
alpar@25
   465
  /// @}
alpar@25
   466
alpar@25
   467
  /// \addtogroup map_adaptors
alpar@25
   468
  /// @{
alpar@25
   469
kpeter@80
   470
  /// Composition of two maps
kpeter@80
   471
kpeter@82
   472
  /// This \ref concepts::ReadMap "read-only map" returns the
kpeter@80
   473
  /// composition of two given maps. That is to say, if \c m1 is of
kpeter@80
   474
  /// type \c M1 and \c m2 is of \c M2, then for
kpeter@80
   475
  /// \code
kpeter@80
   476
  ///   ComposeMap<M1, M2> cm(m1,m2);
kpeter@80
   477
  /// \endcode
kpeter@80
   478
  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
alpar@25
   479
  ///
kpeter@80
   480
  /// The \c Key type of the map is inherited from \c M2 and the
kpeter@80
   481
  /// \c Value type is from \c M1.
kpeter@80
   482
  /// \c M2::Value must be convertible to \c M1::Key.
kpeter@80
   483
  ///
kpeter@80
   484
  /// The simplest way of using this map is through the composeMap()
kpeter@80
   485
  /// function.
kpeter@80
   486
  ///
kpeter@80
   487
  /// \sa CombineMap
kpeter@80
   488
  ///
kpeter@80
   489
  /// \todo Check the requirements.
kpeter@80
   490
  template <typename M1, typename M2>
kpeter@80
   491
  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
kpeter@80
   492
    const M1 &_m1;
kpeter@80
   493
    const M2 &_m2;
alpar@25
   494
  public:
kpeter@80
   495
    typedef MapBase<typename M2::Key, typename M1::Value> Parent;
alpar@25
   496
    typedef typename Parent::Key Key;
alpar@25
   497
    typedef typename Parent::Value Value;
alpar@25
   498
kpeter@80
   499
    /// Constructor
kpeter@80
   500
    ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@80
   501
alpar@25
   502
    /// \e
kpeter@80
   503
    typename MapTraits<M1>::ConstReturnValue
kpeter@80
   504
    operator[](const Key &k) const { return _m1[_m2[k]]; }
alpar@25
   505
  };
alpar@25
   506
kpeter@80
   507
  /// Returns a \ref ComposeMap class
alpar@25
   508
kpeter@80
   509
  /// This function just returns a \ref ComposeMap class.
kpeter@80
   510
  ///
kpeter@80
   511
  /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
kpeter@80
   512
  /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
kpeter@80
   513
  /// will be equal to <tt>m1[m2[x]]</tt>.
kpeter@80
   514
  ///
kpeter@80
   515
  /// \relates ComposeMap
kpeter@80
   516
  template <typename M1, typename M2>
kpeter@80
   517
  inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) {
kpeter@80
   518
    return ComposeMap<M1, M2>(m1, m2);
alpar@25
   519
  }
alpar@25
   520
kpeter@80
   521
kpeter@80
   522
  /// Combination of two maps using an STL (binary) functor.
kpeter@80
   523
kpeter@82
   524
  /// This \ref concepts::ReadMap "read-only map" takes two maps and a
kpeter@80
   525
  /// binary functor and returns the combination of the two given maps
kpeter@80
   526
  /// using the functor.
kpeter@80
   527
  /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2
kpeter@80
   528
  /// and \c f is of \c F, then for
kpeter@80
   529
  /// \code
kpeter@80
   530
  ///   CombineMap<M1,M2,F,V> cm(m1,m2,f);
kpeter@80
   531
  /// \endcode
kpeter@80
   532
  /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>.
alpar@26
   533
  ///
kpeter@80
   534
  /// The \c Key type of the map is inherited from \c M1 (\c M1::Key
kpeter@80
   535
  /// must be convertible to \c M2::Key) and the \c Value type is \c V.
kpeter@80
   536
  /// \c M2::Value and \c M1::Value must be convertible to the
kpeter@80
   537
  /// corresponding input parameter of \c F and the return type of \c F
kpeter@80
   538
  /// must be convertible to \c V.
kpeter@80
   539
  ///
kpeter@80
   540
  /// The simplest way of using this map is through the combineMap()
kpeter@80
   541
  /// function.
kpeter@80
   542
  ///
kpeter@80
   543
  /// \sa ComposeMap
kpeter@80
   544
  ///
kpeter@80
   545
  /// \todo Check the requirements.
kpeter@80
   546
  template<typename M1, typename M2, typename F,
kpeter@80
   547
	   typename V = typename F::result_type>
kpeter@80
   548
  class CombineMap : public MapBase<typename M1::Key, V> {
kpeter@80
   549
    const M1 &_m1;
kpeter@80
   550
    const M2 &_m2;
kpeter@80
   551
    F _f;
alpar@25
   552
  public:
kpeter@80
   553
    typedef MapBase<typename M1::Key, V> Parent;
alpar@25
   554
    typedef typename Parent::Key Key;
alpar@25
   555
    typedef typename Parent::Value Value;
alpar@25
   556
kpeter@80
   557
    /// Constructor
kpeter@80
   558
    CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
kpeter@80
   559
      : _m1(m1), _m2(m2), _f(f) {}
kpeter@80
   560
    /// \e
kpeter@80
   561
    Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
kpeter@80
   562
  };
alpar@25
   563
kpeter@80
   564
  /// Returns a \ref CombineMap class
alpar@25
   565
kpeter@80
   566
  /// This function just returns a \ref CombineMap class.
kpeter@80
   567
  ///
kpeter@80
   568
  /// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80
   569
  /// values, then
kpeter@80
   570
  /// \code
kpeter@80
   571
  ///   combineMap(m1,m2,std::plus<double>())
kpeter@80
   572
  /// \endcode
kpeter@80
   573
  /// is equivalent to
kpeter@80
   574
  /// \code
kpeter@80
   575
  ///   addMap(m1,m2)
kpeter@80
   576
  /// \endcode
kpeter@80
   577
  ///
kpeter@80
   578
  /// This function is specialized for adaptable binary function
kpeter@80
   579
  /// classes and C++ functions.
kpeter@80
   580
  ///
kpeter@80
   581
  /// \relates CombineMap
kpeter@80
   582
  template<typename M1, typename M2, typename F, typename V>
kpeter@80
   583
  inline CombineMap<M1, M2, F, V>
kpeter@80
   584
  combineMap(const M1 &m1, const M2 &m2, const F &f) {
kpeter@80
   585
    return CombineMap<M1, M2, F, V>(m1,m2,f);
alpar@25
   586
  }
alpar@25
   587
kpeter@80
   588
  template<typename M1, typename M2, typename F>
kpeter@80
   589
  inline CombineMap<M1, M2, F, typename F::result_type>
kpeter@80
   590
  combineMap(const M1 &m1, const M2 &m2, const F &f) {
kpeter@80
   591
    return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
kpeter@80
   592
  }
alpar@25
   593
kpeter@80
   594
  template<typename M1, typename M2, typename K1, typename K2, typename V>
kpeter@80
   595
  inline CombineMap<M1, M2, V (*)(K1, K2), V>
kpeter@80
   596
  combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
kpeter@80
   597
    return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
kpeter@80
   598
  }
kpeter@80
   599
kpeter@80
   600
kpeter@80
   601
  /// Converts an STL style (unary) functor to a map
kpeter@80
   602
kpeter@82
   603
  /// This \ref concepts::ReadMap "read-only map" returns the value
kpeter@80
   604
  /// of a given functor. Actually, it just wraps the functor and
kpeter@80
   605
  /// provides the \c Key and \c Value typedefs.
alpar@26
   606
  ///
kpeter@80
   607
  /// Template parameters \c K and \c V will become its \c Key and
kpeter@80
   608
  /// \c Value. In most cases they have to be given explicitly because
kpeter@80
   609
  /// a functor typically does not provide \c argument_type and
kpeter@80
   610
  /// \c result_type typedefs.
kpeter@80
   611
  /// Parameter \c F is the type of the used functor.
kpeter@29
   612
  ///
kpeter@80
   613
  /// The simplest way of using this map is through the functorToMap()
kpeter@80
   614
  /// function.
kpeter@80
   615
  ///
kpeter@80
   616
  /// \sa MapToFunctor
kpeter@80
   617
  template<typename F,
kpeter@80
   618
	   typename K = typename F::argument_type,
kpeter@80
   619
	   typename V = typename F::result_type>
kpeter@80
   620
  class FunctorToMap : public MapBase<K, V> {
kpeter@123
   621
    F _f;
kpeter@80
   622
  public:
kpeter@80
   623
    typedef MapBase<K, V> Parent;
kpeter@80
   624
    typedef typename Parent::Key Key;
kpeter@80
   625
    typedef typename Parent::Value Value;
alpar@25
   626
kpeter@80
   627
    /// Constructor
kpeter@80
   628
    FunctorToMap(const F &f = F()) : _f(f) {}
kpeter@80
   629
    /// \e
kpeter@80
   630
    Value operator[](const Key &k) const { return _f(k); }
kpeter@80
   631
  };
kpeter@80
   632
kpeter@80
   633
  /// Returns a \ref FunctorToMap class
kpeter@80
   634
kpeter@80
   635
  /// This function just returns a \ref FunctorToMap class.
kpeter@80
   636
  ///
kpeter@80
   637
  /// This function is specialized for adaptable binary function
kpeter@80
   638
  /// classes and C++ functions.
kpeter@80
   639
  ///
kpeter@80
   640
  /// \relates FunctorToMap
kpeter@80
   641
  template<typename K, typename V, typename F>
kpeter@80
   642
  inline FunctorToMap<F, K, V> functorToMap(const F &f) {
kpeter@80
   643
    return FunctorToMap<F, K, V>(f);
kpeter@80
   644
  }
kpeter@80
   645
kpeter@80
   646
  template <typename F>
kpeter@80
   647
  inline FunctorToMap<F, typename F::argument_type, typename F::result_type>
kpeter@80
   648
    functorToMap(const F &f)
kpeter@80
   649
  {
kpeter@80
   650
    return FunctorToMap<F, typename F::argument_type,
kpeter@80
   651
      typename F::result_type>(f);
kpeter@80
   652
  }
kpeter@80
   653
kpeter@80
   654
  template <typename K, typename V>
kpeter@80
   655
  inline FunctorToMap<V (*)(K), K, V> functorToMap(V (*f)(K)) {
kpeter@80
   656
    return FunctorToMap<V (*)(K), K, V>(f);
kpeter@80
   657
  }
kpeter@80
   658
kpeter@80
   659
kpeter@80
   660
  /// Converts a map to an STL style (unary) functor
kpeter@80
   661
kpeter@80
   662
  /// This class converts a map to an STL style (unary) functor.
kpeter@80
   663
  /// That is it provides an <tt>operator()</tt> to read its values.
kpeter@80
   664
  ///
kpeter@80
   665
  /// For the sake of convenience it also works as a usual
kpeter@80
   666
  /// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt>
kpeter@80
   667
  /// and the \c Key and \c Value typedefs also exist.
kpeter@80
   668
  ///
kpeter@80
   669
  /// The simplest way of using this map is through the mapToFunctor()
kpeter@80
   670
  /// function.
kpeter@80
   671
  ///
kpeter@80
   672
  ///\sa FunctorToMap
kpeter@80
   673
  template <typename M>
kpeter@80
   674
  class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
   675
    const M &_m;
alpar@25
   676
  public:
alpar@25
   677
    typedef MapBase<typename M::Key, typename M::Value> Parent;
alpar@25
   678
    typedef typename Parent::Key Key;
alpar@25
   679
    typedef typename Parent::Value Value;
alpar@25
   680
kpeter@80
   681
    typedef typename Parent::Key argument_type;
kpeter@80
   682
    typedef typename Parent::Value result_type;
kpeter@80
   683
kpeter@80
   684
    /// Constructor
kpeter@80
   685
    MapToFunctor(const M &m) : _m(m) {}
kpeter@80
   686
    /// \e
kpeter@80
   687
    Value operator()(const Key &k) const { return _m[k]; }
kpeter@80
   688
    /// \e
kpeter@80
   689
    Value operator[](const Key &k) const { return _m[k]; }
alpar@25
   690
  };
kpeter@45
   691
kpeter@80
   692
  /// Returns a \ref MapToFunctor class
kpeter@80
   693
kpeter@80
   694
  /// This function just returns a \ref MapToFunctor class.
kpeter@80
   695
  /// \relates MapToFunctor
kpeter@45
   696
  template<typename M>
kpeter@80
   697
  inline MapToFunctor<M> mapToFunctor(const M &m) {
kpeter@80
   698
    return MapToFunctor<M>(m);
kpeter@45
   699
  }
alpar@25
   700
alpar@25
   701
kpeter@80
   702
  /// \brief Map adaptor to convert the \c Value type of a map to
kpeter@80
   703
  /// another type using the default conversion.
kpeter@80
   704
kpeter@80
   705
  /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap
kpeter@80
   706
  /// "readable map" to another type using the default conversion.
kpeter@80
   707
  /// The \c Key type of it is inherited from \c M and the \c Value
kpeter@80
   708
  /// type is \c V.
kpeter@80
   709
  /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
alpar@26
   710
  ///
kpeter@80
   711
  /// The simplest way of using this map is through the convertMap()
kpeter@80
   712
  /// function.
kpeter@80
   713
  template <typename M, typename V>
kpeter@80
   714
  class ConvertMap : public MapBase<typename M::Key, V> {
kpeter@80
   715
    const M &_m;
kpeter@80
   716
  public:
kpeter@80
   717
    typedef MapBase<typename M::Key, V> Parent;
kpeter@80
   718
    typedef typename Parent::Key Key;
kpeter@80
   719
    typedef typename Parent::Value Value;
kpeter@80
   720
kpeter@80
   721
    /// Constructor
kpeter@80
   722
kpeter@80
   723
    /// Constructor.
kpeter@80
   724
    /// \param m The underlying map.
kpeter@80
   725
    ConvertMap(const M &m) : _m(m) {}
kpeter@80
   726
kpeter@80
   727
    /// \e
kpeter@80
   728
    Value operator[](const Key &k) const { return _m[k]; }
kpeter@80
   729
  };
kpeter@80
   730
kpeter@80
   731
  /// Returns a \ref ConvertMap class
kpeter@80
   732
kpeter@80
   733
  /// This function just returns a \ref ConvertMap class.
kpeter@80
   734
  /// \relates ConvertMap
kpeter@80
   735
  template<typename V, typename M>
kpeter@80
   736
  inline ConvertMap<M, V> convertMap(const M &map) {
kpeter@80
   737
    return ConvertMap<M, V>(map);
kpeter@80
   738
  }
kpeter@80
   739
kpeter@80
   740
kpeter@80
   741
  /// Applies all map setting operations to two maps
kpeter@80
   742
kpeter@80
   743
  /// This map has two \ref concepts::WriteMap "writable map" parameters
kpeter@80
   744
  /// and each write request will be passed to both of them.
kpeter@80
   745
  /// If \c M1 is also \ref concepts::ReadMap "readable", then the read
kpeter@80
   746
  /// operations will return the corresponding values of \c M1.
kpeter@29
   747
  ///
kpeter@80
   748
  /// The \c Key and \c Value types are inherited from \c M1.
kpeter@80
   749
  /// The \c Key and \c Value of \c M2 must be convertible from those
kpeter@80
   750
  /// of \c M1.
kpeter@80
   751
  ///
kpeter@80
   752
  /// The simplest way of using this map is through the forkMap()
kpeter@80
   753
  /// function.
kpeter@80
   754
  template<typename  M1, typename M2>
kpeter@80
   755
  class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80
   756
    M1 &_m1;
kpeter@80
   757
    M2 &_m2;
kpeter@80
   758
  public:
kpeter@80
   759
    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
kpeter@80
   760
    typedef typename Parent::Key Key;
kpeter@80
   761
    typedef typename Parent::Value Value;
alpar@25
   762
kpeter@80
   763
    /// Constructor
kpeter@80
   764
    ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@80
   765
    /// Returns the value associated with the given key in the first map.
kpeter@80
   766
    Value operator[](const Key &k) const { return _m1[k]; }
kpeter@80
   767
    /// Sets the value associated with the given key in both maps.
kpeter@80
   768
    void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); }
kpeter@80
   769
  };
kpeter@80
   770
kpeter@80
   771
  /// Returns a \ref ForkMap class
kpeter@80
   772
kpeter@80
   773
  /// This function just returns a \ref ForkMap class.
kpeter@80
   774
  /// \relates ForkMap
kpeter@80
   775
  template <typename M1, typename M2>
kpeter@80
   776
  inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) {
kpeter@80
   777
    return ForkMap<M1,M2>(m1,m2);
kpeter@80
   778
  }
kpeter@80
   779
kpeter@80
   780
kpeter@80
   781
  /// Sum of two maps
kpeter@80
   782
kpeter@82
   783
  /// This \ref concepts::ReadMap "read-only map" returns the sum
kpeter@80
   784
  /// of the values of the two given maps.
kpeter@80
   785
  /// Its \c Key and \c Value types are inherited from \c M1.
kpeter@80
   786
  /// The \c Key and \c Value of \c M2 must be convertible to those of
kpeter@80
   787
  /// \c M1.
kpeter@80
   788
  ///
kpeter@80
   789
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@80
   790
  /// \code
kpeter@80
   791
  ///   AddMap<M1,M2> am(m1,m2);
kpeter@80
   792
  /// \endcode
kpeter@80
   793
  /// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>.
kpeter@80
   794
  ///
kpeter@80
   795
  /// The simplest way of using this map is through the addMap()
kpeter@80
   796
  /// function.
kpeter@80
   797
  ///
kpeter@80
   798
  /// \sa SubMap, MulMap, DivMap
kpeter@80
   799
  /// \sa ShiftMap, ShiftWriteMap
kpeter@80
   800
  template<typename M1, typename M2>
alpar@25
   801
  class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80
   802
    const M1 &_m1;
kpeter@80
   803
    const M2 &_m2;
alpar@25
   804
  public:
alpar@25
   805
    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
alpar@25
   806
    typedef typename Parent::Key Key;
alpar@25
   807
    typedef typename Parent::Value Value;
alpar@25
   808
kpeter@80
   809
    /// Constructor
kpeter@80
   810
    AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@80
   811
    /// \e
kpeter@80
   812
    Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
alpar@25
   813
  };
alpar@25
   814
kpeter@80
   815
  /// Returns an \ref AddMap class
kpeter@80
   816
kpeter@80
   817
  /// This function just returns an \ref AddMap class.
alpar@25
   818
  ///
kpeter@80
   819
  /// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80
   820
  /// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to
kpeter@80
   821
  /// <tt>m1[x]+m2[x]</tt>.
kpeter@80
   822
  ///
kpeter@80
   823
  /// \relates AddMap
kpeter@80
   824
  template<typename M1, typename M2>
kpeter@80
   825
  inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) {
alpar@25
   826
    return AddMap<M1, M2>(m1,m2);
alpar@25
   827
  }
alpar@25
   828
alpar@25
   829
kpeter@80
   830
  /// Difference of two maps
kpeter@80
   831
kpeter@82
   832
  /// This \ref concepts::ReadMap "read-only map" returns the difference
kpeter@80
   833
  /// of the values of the two given maps.
kpeter@80
   834
  /// Its \c Key and \c Value types are inherited from \c M1.
kpeter@80
   835
  /// The \c Key and \c Value of \c M2 must be convertible to those of
kpeter@80
   836
  /// \c M1.
alpar@25
   837
  ///
kpeter@80
   838
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@80
   839
  /// \code
kpeter@80
   840
  ///   SubMap<M1,M2> sm(m1,m2);
kpeter@80
   841
  /// \endcode
kpeter@80
   842
  /// <tt>sm[x]</tt> will be equal to <tt>m1[x]-m2[x]</tt>.
kpeter@29
   843
  ///
kpeter@80
   844
  /// The simplest way of using this map is through the subMap()
kpeter@80
   845
  /// function.
kpeter@80
   846
  ///
kpeter@80
   847
  /// \sa AddMap, MulMap, DivMap
kpeter@80
   848
  template<typename M1, typename M2>
kpeter@80
   849
  class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80
   850
    const M1 &_m1;
kpeter@80
   851
    const M2 &_m2;
kpeter@80
   852
  public:
kpeter@80
   853
    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
kpeter@80
   854
    typedef typename Parent::Key Key;
kpeter@80
   855
    typedef typename Parent::Value Value;
kpeter@80
   856
kpeter@80
   857
    /// Constructor
kpeter@80
   858
    SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@80
   859
    /// \e
kpeter@80
   860
    Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
kpeter@80
   861
  };
kpeter@80
   862
kpeter@80
   863
  /// Returns a \ref SubMap class
kpeter@80
   864
kpeter@80
   865
  /// This function just returns a \ref SubMap class.
kpeter@80
   866
  ///
kpeter@80
   867
  /// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80
   868
  /// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to
kpeter@80
   869
  /// <tt>m1[x]-m2[x]</tt>.
kpeter@80
   870
  ///
kpeter@80
   871
  /// \relates SubMap
kpeter@80
   872
  template<typename M1, typename M2>
kpeter@80
   873
  inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
kpeter@80
   874
    return SubMap<M1, M2>(m1,m2);
kpeter@80
   875
  }
kpeter@80
   876
kpeter@80
   877
kpeter@80
   878
  /// Product of two maps
kpeter@80
   879
kpeter@82
   880
  /// This \ref concepts::ReadMap "read-only map" returns the product
kpeter@80
   881
  /// of the values of the two given maps.
kpeter@80
   882
  /// Its \c Key and \c Value types are inherited from \c M1.
kpeter@80
   883
  /// The \c Key and \c Value of \c M2 must be convertible to those of
kpeter@80
   884
  /// \c M1.
kpeter@80
   885
  ///
kpeter@80
   886
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@80
   887
  /// \code
kpeter@80
   888
  ///   MulMap<M1,M2> mm(m1,m2);
kpeter@80
   889
  /// \endcode
kpeter@80
   890
  /// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>.
kpeter@80
   891
  ///
kpeter@80
   892
  /// The simplest way of using this map is through the mulMap()
kpeter@80
   893
  /// function.
kpeter@80
   894
  ///
kpeter@80
   895
  /// \sa AddMap, SubMap, DivMap
kpeter@80
   896
  /// \sa ScaleMap, ScaleWriteMap
kpeter@80
   897
  template<typename M1, typename M2>
kpeter@80
   898
  class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80
   899
    const M1 &_m1;
kpeter@80
   900
    const M2 &_m2;
kpeter@80
   901
  public:
kpeter@80
   902
    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
kpeter@80
   903
    typedef typename Parent::Key Key;
kpeter@80
   904
    typedef typename Parent::Value Value;
kpeter@80
   905
kpeter@80
   906
    /// Constructor
kpeter@80
   907
    MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@80
   908
    /// \e
kpeter@80
   909
    Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
kpeter@80
   910
  };
kpeter@80
   911
kpeter@80
   912
  /// Returns a \ref MulMap class
kpeter@80
   913
kpeter@80
   914
  /// This function just returns a \ref MulMap class.
kpeter@80
   915
  ///
kpeter@80
   916
  /// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80
   917
  /// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to
kpeter@80
   918
  /// <tt>m1[x]*m2[x]</tt>.
kpeter@80
   919
  ///
kpeter@80
   920
  /// \relates MulMap
kpeter@80
   921
  template<typename M1, typename M2>
kpeter@80
   922
  inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
kpeter@80
   923
    return MulMap<M1, M2>(m1,m2);
kpeter@80
   924
  }
kpeter@80
   925
kpeter@80
   926
kpeter@80
   927
  /// Quotient of two maps
kpeter@80
   928
kpeter@82
   929
  /// This \ref concepts::ReadMap "read-only map" returns the quotient
kpeter@80
   930
  /// of the values of the two given maps.
kpeter@80
   931
  /// Its \c Key and \c Value types are inherited from \c M1.
kpeter@80
   932
  /// The \c Key and \c Value of \c M2 must be convertible to those of
kpeter@80
   933
  /// \c M1.
kpeter@80
   934
  ///
kpeter@80
   935
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@80
   936
  /// \code
kpeter@80
   937
  ///   DivMap<M1,M2> dm(m1,m2);
kpeter@80
   938
  /// \endcode
kpeter@80
   939
  /// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>.
kpeter@80
   940
  ///
kpeter@80
   941
  /// The simplest way of using this map is through the divMap()
kpeter@80
   942
  /// function.
kpeter@80
   943
  ///
kpeter@80
   944
  /// \sa AddMap, SubMap, MulMap
kpeter@80
   945
  template<typename M1, typename M2>
kpeter@80
   946
  class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80
   947
    const M1 &_m1;
kpeter@80
   948
    const M2 &_m2;
kpeter@80
   949
  public:
kpeter@80
   950
    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
kpeter@80
   951
    typedef typename Parent::Key Key;
kpeter@80
   952
    typedef typename Parent::Value Value;
kpeter@80
   953
kpeter@80
   954
    /// Constructor
kpeter@80
   955
    DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@80
   956
    /// \e
kpeter@80
   957
    Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
kpeter@80
   958
  };
kpeter@80
   959
kpeter@80
   960
  /// Returns a \ref DivMap class
kpeter@80
   961
kpeter@80
   962
  /// This function just returns a \ref DivMap class.
kpeter@80
   963
  ///
kpeter@80
   964
  /// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80
   965
  /// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to
kpeter@80
   966
  /// <tt>m1[x]/m2[x]</tt>.
kpeter@80
   967
  ///
kpeter@80
   968
  /// \relates DivMap
kpeter@80
   969
  template<typename M1, typename M2>
kpeter@80
   970
  inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
kpeter@80
   971
    return DivMap<M1, M2>(m1,m2);
kpeter@80
   972
  }
kpeter@80
   973
kpeter@80
   974
kpeter@80
   975
  /// Shifts a map with a constant.
kpeter@80
   976
kpeter@82
   977
  /// This \ref concepts::ReadMap "read-only map" returns the sum of
kpeter@80
   978
  /// the given map and a constant value (i.e. it shifts the map with
kpeter@80
   979
  /// the constant). Its \c Key and \c Value are inherited from \c M.
kpeter@80
   980
  ///
kpeter@80
   981
  /// Actually,
kpeter@80
   982
  /// \code
kpeter@80
   983
  ///   ShiftMap<M> sh(m,v);
kpeter@80
   984
  /// \endcode
kpeter@80
   985
  /// is equivalent to
kpeter@80
   986
  /// \code
kpeter@80
   987
  ///   ConstMap<M::Key, M::Value> cm(v);
kpeter@80
   988
  ///   AddMap<M, ConstMap<M::Key, M::Value> > sh(m,cm);
kpeter@80
   989
  /// \endcode
kpeter@80
   990
  ///
kpeter@80
   991
  /// The simplest way of using this map is through the shiftMap()
kpeter@80
   992
  /// function.
kpeter@80
   993
  ///
kpeter@80
   994
  /// \sa ShiftWriteMap
kpeter@80
   995
  template<typename M, typename C = typename M::Value>
alpar@25
   996
  class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
   997
    const M &_m;
kpeter@80
   998
    C _v;
alpar@25
   999
  public:
alpar@25
  1000
    typedef MapBase<typename M::Key, typename M::Value> Parent;
alpar@25
  1001
    typedef typename Parent::Key Key;
alpar@25
  1002
    typedef typename Parent::Value Value;
alpar@25
  1003
kpeter@80
  1004
    /// Constructor
alpar@25
  1005
kpeter@80
  1006
    /// Constructor.
kpeter@80
  1007
    /// \param m The undelying map.
kpeter@80
  1008
    /// \param v The constant value.
kpeter@80
  1009
    ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
kpeter@80
  1010
    /// \e
kpeter@80
  1011
    Value operator[](const Key &k) const { return _m[k]+_v; }
alpar@25
  1012
  };
alpar@25
  1013
kpeter@80
  1014
  /// Shifts a map with a constant (read-write version).
alpar@25
  1015
kpeter@80
  1016
  /// This \ref concepts::ReadWriteMap "read-write map" returns the sum
kpeter@80
  1017
  /// of the given map and a constant value (i.e. it shifts the map with
kpeter@80
  1018
  /// the constant). Its \c Key and \c Value are inherited from \c M.
kpeter@80
  1019
  /// It makes also possible to write the map.
alpar@25
  1020
  ///
kpeter@80
  1021
  /// The simplest way of using this map is through the shiftWriteMap()
kpeter@80
  1022
  /// function.
kpeter@80
  1023
  ///
kpeter@80
  1024
  /// \sa ShiftMap
kpeter@80
  1025
  template<typename M, typename C = typename M::Value>
alpar@25
  1026
  class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
  1027
    M &_m;
kpeter@80
  1028
    C _v;
alpar@25
  1029
  public:
alpar@25
  1030
    typedef MapBase<typename M::Key, typename M::Value> Parent;
alpar@25
  1031
    typedef typename Parent::Key Key;
alpar@25
  1032
    typedef typename Parent::Value Value;
alpar@25
  1033
kpeter@80
  1034
    /// Constructor
alpar@25
  1035
kpeter@80
  1036
    /// Constructor.
kpeter@80
  1037
    /// \param m The undelying map.
kpeter@80
  1038
    /// \param v The constant value.
kpeter@80
  1039
    ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
alpar@25
  1040
    /// \e
kpeter@80
  1041
    Value operator[](const Key &k) const { return _m[k]+_v; }
alpar@25
  1042
    /// \e
kpeter@80
  1043
    void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
alpar@25
  1044
  };
alpar@25
  1045
kpeter@80
  1046
  /// Returns a \ref ShiftMap class
kpeter@80
  1047
kpeter@80
  1048
  /// This function just returns a \ref ShiftMap class.
kpeter@80
  1049
  ///
kpeter@80
  1050
  /// For example, if \c m is a map with \c double values and \c v is
kpeter@80
  1051
  /// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to
kpeter@80
  1052
  /// <tt>m[x]+v</tt>.
kpeter@80
  1053
  ///
kpeter@80
  1054
  /// \relates ShiftMap
kpeter@80
  1055
  template<typename M, typename C>
kpeter@80
  1056
  inline ShiftMap<M, C> shiftMap(const M &m, const C &v) {
alpar@25
  1057
    return ShiftMap<M, C>(m,v);
alpar@25
  1058
  }
alpar@25
  1059
kpeter@80
  1060
  /// Returns a \ref ShiftWriteMap class
kpeter@29
  1061
kpeter@80
  1062
  /// This function just returns a \ref ShiftWriteMap class.
kpeter@80
  1063
  ///
kpeter@80
  1064
  /// For example, if \c m is a map with \c double values and \c v is
kpeter@80
  1065
  /// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to
kpeter@80
  1066
  /// <tt>m[x]+v</tt>.
kpeter@80
  1067
  /// Moreover it makes also possible to write the map.
kpeter@80
  1068
  ///
kpeter@80
  1069
  /// \relates ShiftWriteMap
kpeter@80
  1070
  template<typename M, typename C>
kpeter@80
  1071
  inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) {
alpar@25
  1072
    return ShiftWriteMap<M, C>(m,v);
alpar@25
  1073
  }
alpar@25
  1074
alpar@25
  1075
kpeter@80
  1076
  /// Scales a map with a constant.
kpeter@80
  1077
kpeter@82
  1078
  /// This \ref concepts::ReadMap "read-only map" returns the value of
kpeter@80
  1079
  /// the given map multiplied from the left side with a constant value.
kpeter@80
  1080
  /// Its \c Key and \c Value are inherited from \c M.
alpar@26
  1081
  ///
kpeter@80
  1082
  /// Actually,
kpeter@80
  1083
  /// \code
kpeter@80
  1084
  ///   ScaleMap<M> sc(m,v);
kpeter@80
  1085
  /// \endcode
kpeter@80
  1086
  /// is equivalent to
kpeter@80
  1087
  /// \code
kpeter@80
  1088
  ///   ConstMap<M::Key, M::Value> cm(v);
kpeter@80
  1089
  ///   MulMap<ConstMap<M::Key, M::Value>, M> sc(cm,m);
kpeter@80
  1090
  /// \endcode
alpar@25
  1091
  ///
kpeter@80
  1092
  /// The simplest way of using this map is through the scaleMap()
kpeter@80
  1093
  /// function.
alpar@25
  1094
  ///
kpeter@80
  1095
  /// \sa ScaleWriteMap
kpeter@80
  1096
  template<typename M, typename C = typename M::Value>
alpar@25
  1097
  class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
  1098
    const M &_m;
kpeter@80
  1099
    C _v;
alpar@25
  1100
  public:
alpar@25
  1101
    typedef MapBase<typename M::Key, typename M::Value> Parent;
alpar@25
  1102
    typedef typename Parent::Key Key;
alpar@25
  1103
    typedef typename Parent::Value Value;
alpar@25
  1104
kpeter@80
  1105
    /// Constructor
alpar@25
  1106
kpeter@80
  1107
    /// Constructor.
kpeter@80
  1108
    /// \param m The undelying map.
kpeter@80
  1109
    /// \param v The constant value.
kpeter@80
  1110
    ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
alpar@25
  1111
    /// \e
kpeter@80
  1112
    Value operator[](const Key &k) const { return _v*_m[k]; }
alpar@25
  1113
  };
alpar@25
  1114
kpeter@80
  1115
  /// Scales a map with a constant (read-write version).
alpar@25
  1116
kpeter@80
  1117
  /// This \ref concepts::ReadWriteMap "read-write map" returns the value of
kpeter@80
  1118
  /// the given map multiplied from the left side with a constant value.
kpeter@80
  1119
  /// Its \c Key and \c Value are inherited from \c M.
kpeter@80
  1120
  /// It can also be used as write map if the \c / operator is defined
kpeter@80
  1121
  /// between \c Value and \c C and the given multiplier is not zero.
kpeter@29
  1122
  ///
kpeter@80
  1123
  /// The simplest way of using this map is through the scaleWriteMap()
kpeter@80
  1124
  /// function.
kpeter@80
  1125
  ///
kpeter@80
  1126
  /// \sa ScaleMap
kpeter@80
  1127
  template<typename M, typename C = typename M::Value>
alpar@25
  1128
  class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
  1129
    M &_m;
kpeter@80
  1130
    C _v;
alpar@25
  1131
  public:
alpar@25
  1132
    typedef MapBase<typename M::Key, typename M::Value> Parent;
alpar@25
  1133
    typedef typename Parent::Key Key;
alpar@25
  1134
    typedef typename Parent::Value Value;
alpar@25
  1135
kpeter@80
  1136
    /// Constructor
alpar@25
  1137
kpeter@80
  1138
    /// Constructor.
kpeter@80
  1139
    /// \param m The undelying map.
kpeter@80
  1140
    /// \param v The constant value.
kpeter@80
  1141
    ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
alpar@25
  1142
    /// \e
kpeter@80
  1143
    Value operator[](const Key &k) const { return _v*_m[k]; }
alpar@25
  1144
    /// \e
kpeter@80
  1145
    void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
alpar@25
  1146
  };
alpar@25
  1147
kpeter@80
  1148
  /// Returns a \ref ScaleMap class
kpeter@80
  1149
kpeter@80
  1150
  /// This function just returns a \ref ScaleMap class.
kpeter@80
  1151
  ///
kpeter@80
  1152
  /// For example, if \c m is a map with \c double values and \c v is
kpeter@80
  1153
  /// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to
kpeter@80
  1154
  /// <tt>v*m[x]</tt>.
kpeter@80
  1155
  ///
kpeter@80
  1156
  /// \relates ScaleMap
kpeter@80
  1157
  template<typename M, typename C>
kpeter@80
  1158
  inline ScaleMap<M, C> scaleMap(const M &m, const C &v) {
alpar@25
  1159
    return ScaleMap<M, C>(m,v);
alpar@25
  1160
  }
alpar@25
  1161
kpeter@80
  1162
  /// Returns a \ref ScaleWriteMap class
kpeter@29
  1163
kpeter@80
  1164
  /// This function just returns a \ref ScaleWriteMap class.
kpeter@80
  1165
  ///
kpeter@80
  1166
  /// For example, if \c m is a map with \c double values and \c v is
kpeter@80
  1167
  /// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to
kpeter@80
  1168
  /// <tt>v*m[x]</tt>.
kpeter@80
  1169
  /// Moreover it makes also possible to write the map.
kpeter@80
  1170
  ///
kpeter@80
  1171
  /// \relates ScaleWriteMap
kpeter@80
  1172
  template<typename M, typename C>
kpeter@80
  1173
  inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) {
alpar@25
  1174
    return ScaleWriteMap<M, C>(m,v);
alpar@25
  1175
  }
alpar@25
  1176
alpar@25
  1177
kpeter@80
  1178
  /// Negative of a map
alpar@25
  1179
kpeter@82
  1180
  /// This \ref concepts::ReadMap "read-only map" returns the negative
kpeter@80
  1181
  /// of the values of the given map (using the unary \c - operator).
kpeter@80
  1182
  /// Its \c Key and \c Value are inherited from \c M.
alpar@25
  1183
  ///
kpeter@80
  1184
  /// If M::Value is \c int, \c double etc., then
kpeter@80
  1185
  /// \code
kpeter@80
  1186
  ///   NegMap<M> neg(m);
kpeter@80
  1187
  /// \endcode
kpeter@80
  1188
  /// is equivalent to
kpeter@80
  1189
  /// \code
kpeter@80
  1190
  ///   ScaleMap<M> neg(m,-1);
kpeter@80
  1191
  /// \endcode
kpeter@29
  1192
  ///
kpeter@80
  1193
  /// The simplest way of using this map is through the negMap()
kpeter@80
  1194
  /// function.
kpeter@29
  1195
  ///
kpeter@80
  1196
  /// \sa NegWriteMap
kpeter@80
  1197
  template<typename M>
alpar@25
  1198
  class NegMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
  1199
    const M& _m;
alpar@25
  1200
  public:
alpar@25
  1201
    typedef MapBase<typename M::Key, typename M::Value> Parent;
alpar@25
  1202
    typedef typename Parent::Key Key;
alpar@25
  1203
    typedef typename Parent::Value Value;
alpar@25
  1204
kpeter@80
  1205
    /// Constructor
kpeter@80
  1206
    NegMap(const M &m) : _m(m) {}
alpar@25
  1207
    /// \e
kpeter@80
  1208
    Value operator[](const Key &k) const { return -_m[k]; }
alpar@25
  1209
  };
alpar@25
  1210
kpeter@80
  1211
  /// Negative of a map (read-write version)
kpeter@80
  1212
kpeter@80
  1213
  /// This \ref concepts::ReadWriteMap "read-write map" returns the
kpeter@80
  1214
  /// negative of the values of the given map (using the unary \c -
kpeter@80
  1215
  /// operator).
kpeter@80
  1216
  /// Its \c Key and \c Value are inherited from \c M.
kpeter@80
  1217
  /// It makes also possible to write the map.
kpeter@80
  1218
  ///
kpeter@80
  1219
  /// If M::Value is \c int, \c double etc., then
kpeter@80
  1220
  /// \code
kpeter@80
  1221
  ///   NegWriteMap<M> neg(m);
kpeter@80
  1222
  /// \endcode
kpeter@80
  1223
  /// is equivalent to
kpeter@80
  1224
  /// \code
kpeter@80
  1225
  ///   ScaleWriteMap<M> neg(m,-1);
kpeter@80
  1226
  /// \endcode
kpeter@80
  1227
  ///
kpeter@80
  1228
  /// The simplest way of using this map is through the negWriteMap()
kpeter@80
  1229
  /// function.
kpeter@29
  1230
  ///
kpeter@29
  1231
  /// \sa NegMap
kpeter@80
  1232
  template<typename M>
alpar@25
  1233
  class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
  1234
    M &_m;
alpar@25
  1235
  public:
alpar@25
  1236
    typedef MapBase<typename M::Key, typename M::Value> Parent;
alpar@25
  1237
    typedef typename Parent::Key Key;
alpar@25
  1238
    typedef typename Parent::Value Value;
alpar@25
  1239
kpeter@80
  1240
    /// Constructor
kpeter@80
  1241
    NegWriteMap(M &m) : _m(m) {}
alpar@25
  1242
    /// \e
kpeter@80
  1243
    Value operator[](const Key &k) const { return -_m[k]; }
alpar@25
  1244
    /// \e
kpeter@80
  1245
    void set(const Key &k, const Value &v) { _m.set(k, -v); }
alpar@25
  1246
  };
alpar@25
  1247
kpeter@80
  1248
  /// Returns a \ref NegMap class
alpar@25
  1249
kpeter@80
  1250
  /// This function just returns a \ref NegMap class.
kpeter@80
  1251
  ///
kpeter@80
  1252
  /// For example, if \c m is a map with \c double values, then
kpeter@80
  1253
  /// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
kpeter@80
  1254
  ///
kpeter@80
  1255
  /// \relates NegMap
kpeter@80
  1256
  template <typename M>
alpar@25
  1257
  inline NegMap<M> negMap(const M &m) {
alpar@25
  1258
    return NegMap<M>(m);
alpar@25
  1259
  }
alpar@25
  1260
kpeter@80
  1261
  /// Returns a \ref NegWriteMap class
kpeter@29
  1262
kpeter@80
  1263
  /// This function just returns a \ref NegWriteMap class.
kpeter@80
  1264
  ///
kpeter@80
  1265
  /// For example, if \c m is a map with \c double values, then
kpeter@80
  1266
  /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
kpeter@80
  1267
  /// Moreover it makes also possible to write the map.
kpeter@80
  1268
  ///
kpeter@80
  1269
  /// \relates NegWriteMap
kpeter@80
  1270
  template <typename M>
kpeter@80
  1271
  inline NegWriteMap<M> negWriteMap(M &m) {
alpar@25
  1272
    return NegWriteMap<M>(m);
alpar@25
  1273
  }
alpar@25
  1274
alpar@25
  1275
kpeter@80
  1276
  /// Absolute value of a map
kpeter@80
  1277
kpeter@82
  1278
  /// This \ref concepts::ReadMap "read-only map" returns the absolute
kpeter@80
  1279
  /// value of the values of the given map.
kpeter@80
  1280
  /// Its \c Key and \c Value are inherited from \c M.
kpeter@80
  1281
  /// \c Value must be comparable to \c 0 and the unary \c -
kpeter@80
  1282
  /// operator must be defined for it, of course.
kpeter@80
  1283
  ///
kpeter@80
  1284
  /// The simplest way of using this map is through the absMap()
kpeter@80
  1285
  /// function.
kpeter@80
  1286
  template<typename M>
alpar@25
  1287
  class AbsMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
  1288
    const M &_m;
alpar@25
  1289
  public:
alpar@25
  1290
    typedef MapBase<typename M::Key, typename M::Value> Parent;
alpar@25
  1291
    typedef typename Parent::Key Key;
alpar@25
  1292
    typedef typename Parent::Value Value;
alpar@25
  1293
kpeter@80
  1294
    /// Constructor
kpeter@80
  1295
    AbsMap(const M &m) : _m(m) {}
alpar@25
  1296
    /// \e
kpeter@80
  1297
    Value operator[](const Key &k) const {
kpeter@80
  1298
      Value tmp = _m[k];
alpar@25
  1299
      return tmp >= 0 ? tmp : -tmp;
alpar@25
  1300
    }
alpar@25
  1301
alpar@25
  1302
  };
alpar@25
  1303
kpeter@80
  1304
  /// Returns an \ref AbsMap class
kpeter@80
  1305
kpeter@80
  1306
  /// This function just returns an \ref AbsMap class.
kpeter@80
  1307
  ///
kpeter@80
  1308
  /// For example, if \c m is a map with \c double values, then
kpeter@80
  1309
  /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if
kpeter@80
  1310
  /// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is
kpeter@80
  1311
  /// negative.
kpeter@80
  1312
  ///
kpeter@80
  1313
  /// \relates AbsMap
kpeter@80
  1314
  template<typename M>
alpar@25
  1315
  inline AbsMap<M> absMap(const M &m) {
alpar@25
  1316
    return AbsMap<M>(m);
alpar@25
  1317
  }
alpar@25
  1318
kpeter@82
  1319
  /// @}
kpeter@82
  1320
  
kpeter@82
  1321
  // Logical maps and map adaptors:
kpeter@82
  1322
kpeter@82
  1323
  /// \addtogroup maps
kpeter@82
  1324
  /// @{
kpeter@82
  1325
kpeter@82
  1326
  /// Constant \c true map.
kpeter@82
  1327
kpeter@82
  1328
  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
kpeter@82
  1329
  /// each key.
kpeter@82
  1330
  ///
kpeter@82
  1331
  /// Note that
kpeter@82
  1332
  /// \code
kpeter@82
  1333
  ///   TrueMap<K> tm;
kpeter@82
  1334
  /// \endcode
kpeter@82
  1335
  /// is equivalent to
kpeter@82
  1336
  /// \code
kpeter@82
  1337
  ///   ConstMap<K,bool> tm(true);
kpeter@82
  1338
  /// \endcode
kpeter@82
  1339
  ///
kpeter@82
  1340
  /// \sa FalseMap
kpeter@82
  1341
  /// \sa ConstMap
kpeter@82
  1342
  template <typename K>
kpeter@82
  1343
  class TrueMap : public MapBase<K, bool> {
kpeter@82
  1344
  public:
kpeter@82
  1345
    typedef MapBase<K, bool> Parent;
kpeter@82
  1346
    typedef typename Parent::Key Key;
kpeter@82
  1347
    typedef typename Parent::Value Value;
kpeter@82
  1348
kpeter@82
  1349
    /// Gives back \c true.
kpeter@82
  1350
    Value operator[](const Key&) const { return true; }
kpeter@82
  1351
  };
kpeter@82
  1352
kpeter@82
  1353
  /// Returns a \ref TrueMap class
kpeter@82
  1354
kpeter@82
  1355
  /// This function just returns a \ref TrueMap class.
kpeter@82
  1356
  /// \relates TrueMap
kpeter@82
  1357
  template<typename K>
kpeter@82
  1358
  inline TrueMap<K> trueMap() {
kpeter@82
  1359
    return TrueMap<K>();
kpeter@82
  1360
  }
kpeter@82
  1361
kpeter@82
  1362
kpeter@82
  1363
  /// Constant \c false map.
kpeter@82
  1364
kpeter@82
  1365
  /// This \ref concepts::ReadMap "read-only map" assigns \c false to
kpeter@82
  1366
  /// each key.
kpeter@82
  1367
  ///
kpeter@82
  1368
  /// Note that
kpeter@82
  1369
  /// \code
kpeter@82
  1370
  ///   FalseMap<K> fm;
kpeter@82
  1371
  /// \endcode
kpeter@82
  1372
  /// is equivalent to
kpeter@82
  1373
  /// \code
kpeter@82
  1374
  ///   ConstMap<K,bool> fm(false);
kpeter@82
  1375
  /// \endcode
kpeter@82
  1376
  ///
kpeter@82
  1377
  /// \sa TrueMap
kpeter@82
  1378
  /// \sa ConstMap
kpeter@82
  1379
  template <typename K>
kpeter@82
  1380
  class FalseMap : public MapBase<K, bool> {
kpeter@82
  1381
  public:
kpeter@82
  1382
    typedef MapBase<K, bool> Parent;
kpeter@82
  1383
    typedef typename Parent::Key Key;
kpeter@82
  1384
    typedef typename Parent::Value Value;
kpeter@82
  1385
kpeter@82
  1386
    /// Gives back \c false.
kpeter@82
  1387
    Value operator[](const Key&) const { return false; }
kpeter@82
  1388
  };
kpeter@82
  1389
kpeter@82
  1390
  /// Returns a \ref FalseMap class
kpeter@82
  1391
kpeter@82
  1392
  /// This function just returns a \ref FalseMap class.
kpeter@82
  1393
  /// \relates FalseMap
kpeter@82
  1394
  template<typename K>
kpeter@82
  1395
  inline FalseMap<K> falseMap() {
kpeter@82
  1396
    return FalseMap<K>();
kpeter@82
  1397
  }
kpeter@82
  1398
kpeter@82
  1399
  /// @}
kpeter@82
  1400
kpeter@82
  1401
  /// \addtogroup map_adaptors
kpeter@82
  1402
  /// @{
kpeter@82
  1403
kpeter@82
  1404
  /// Logical 'and' of two maps
kpeter@82
  1405
kpeter@82
  1406
  /// This \ref concepts::ReadMap "read-only map" returns the logical
kpeter@82
  1407
  /// 'and' of the values of the two given maps.
kpeter@82
  1408
  /// Its \c Key type is inherited from \c M1 and its \c Value type is
kpeter@82
  1409
  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
kpeter@82
  1410
  ///
kpeter@82
  1411
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@82
  1412
  /// \code
kpeter@82
  1413
  ///   AndMap<M1,M2> am(m1,m2);
kpeter@82
  1414
  /// \endcode
kpeter@82
  1415
  /// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>.
kpeter@82
  1416
  ///
kpeter@82
  1417
  /// The simplest way of using this map is through the andMap()
kpeter@82
  1418
  /// function.
kpeter@82
  1419
  ///
kpeter@82
  1420
  /// \sa OrMap
kpeter@82
  1421
  /// \sa NotMap, NotWriteMap
kpeter@82
  1422
  template<typename M1, typename M2>
kpeter@82
  1423
  class AndMap : public MapBase<typename M1::Key, bool> {
kpeter@82
  1424
    const M1 &_m1;
kpeter@82
  1425
    const M2 &_m2;
kpeter@82
  1426
  public:
kpeter@82
  1427
    typedef MapBase<typename M1::Key, bool> Parent;
kpeter@82
  1428
    typedef typename Parent::Key Key;
kpeter@82
  1429
    typedef typename Parent::Value Value;
kpeter@82
  1430
kpeter@82
  1431
    /// Constructor
kpeter@82
  1432
    AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@82
  1433
    /// \e
kpeter@82
  1434
    Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
kpeter@82
  1435
  };
kpeter@82
  1436
kpeter@82
  1437
  /// Returns an \ref AndMap class
kpeter@82
  1438
kpeter@82
  1439
  /// This function just returns an \ref AndMap class.
kpeter@82
  1440
  ///
kpeter@82
  1441
  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
kpeter@82
  1442
  /// then <tt>andMap(m1,m2)[x]</tt> will be equal to
kpeter@82
  1443
  /// <tt>m1[x]&&m2[x]</tt>.
kpeter@82
  1444
  ///
kpeter@82
  1445
  /// \relates AndMap
kpeter@82
  1446
  template<typename M1, typename M2>
kpeter@82
  1447
  inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) {
kpeter@82
  1448
    return AndMap<M1, M2>(m1,m2);
kpeter@82
  1449
  }
kpeter@82
  1450
kpeter@82
  1451
kpeter@82
  1452
  /// Logical 'or' of two maps
kpeter@82
  1453
kpeter@82
  1454
  /// This \ref concepts::ReadMap "read-only map" returns the logical
kpeter@82
  1455
  /// 'or' of the values of the two given maps.
kpeter@82
  1456
  /// Its \c Key type is inherited from \c M1 and its \c Value type is
kpeter@82
  1457
  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
kpeter@82
  1458
  ///
kpeter@82
  1459
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@82
  1460
  /// \code
kpeter@82
  1461
  ///   OrMap<M1,M2> om(m1,m2);
kpeter@82
  1462
  /// \endcode
kpeter@82
  1463
  /// <tt>om[x]</tt> will be equal to <tt>m1[x]||m2[x]</tt>.
kpeter@82
  1464
  ///
kpeter@82
  1465
  /// The simplest way of using this map is through the orMap()
kpeter@82
  1466
  /// function.
kpeter@82
  1467
  ///
kpeter@82
  1468
  /// \sa AndMap
kpeter@82
  1469
  /// \sa NotMap, NotWriteMap
kpeter@82
  1470
  template<typename M1, typename M2>
kpeter@82
  1471
  class OrMap : public MapBase<typename M1::Key, bool> {
kpeter@82
  1472
    const M1 &_m1;
kpeter@82
  1473
    const M2 &_m2;
kpeter@82
  1474
  public:
kpeter@82
  1475
    typedef MapBase<typename M1::Key, bool> Parent;
kpeter@82
  1476
    typedef typename Parent::Key Key;
kpeter@82
  1477
    typedef typename Parent::Value Value;
kpeter@82
  1478
kpeter@82
  1479
    /// Constructor
kpeter@82
  1480
    OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@82
  1481
    /// \e
kpeter@82
  1482
    Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
kpeter@82
  1483
  };
kpeter@82
  1484
kpeter@82
  1485
  /// Returns an \ref OrMap class
kpeter@82
  1486
kpeter@82
  1487
  /// This function just returns an \ref OrMap class.
kpeter@82
  1488
  ///
kpeter@82
  1489
  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
kpeter@82
  1490
  /// then <tt>orMap(m1,m2)[x]</tt> will be equal to
kpeter@82
  1491
  /// <tt>m1[x]||m2[x]</tt>.
kpeter@82
  1492
  ///
kpeter@82
  1493
  /// \relates OrMap
kpeter@82
  1494
  template<typename M1, typename M2>
kpeter@82
  1495
  inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) {
kpeter@82
  1496
    return OrMap<M1, M2>(m1,m2);
kpeter@82
  1497
  }
kpeter@82
  1498
alpar@25
  1499
kpeter@80
  1500
  /// Logical 'not' of a map
kpeter@80
  1501
kpeter@82
  1502
  /// This \ref concepts::ReadMap "read-only map" returns the logical
kpeter@80
  1503
  /// negation of the values of the given map.
kpeter@80
  1504
  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
alpar@25
  1505
  ///
kpeter@80
  1506
  /// The simplest way of using this map is through the notMap()
kpeter@80
  1507
  /// function.
alpar@25
  1508
  ///
kpeter@80
  1509
  /// \sa NotWriteMap
kpeter@80
  1510
  template <typename M>
alpar@25
  1511
  class NotMap : public MapBase<typename M::Key, bool> {
kpeter@80
  1512
    const M &_m;
alpar@25
  1513
  public:
alpar@25
  1514
    typedef MapBase<typename M::Key, bool> Parent;
alpar@25
  1515
    typedef typename Parent::Key Key;
alpar@25
  1516
    typedef typename Parent::Value Value;
alpar@25
  1517
alpar@25
  1518
    /// Constructor
kpeter@80
  1519
    NotMap(const M &m) : _m(m) {}
kpeter@80
  1520
    /// \e
kpeter@80
  1521
    Value operator[](const Key &k) const { return !_m[k]; }
alpar@25
  1522
  };
alpar@25
  1523
kpeter@80
  1524
  /// Logical 'not' of a map (read-write version)
kpeter@80
  1525
kpeter@80
  1526
  /// This \ref concepts::ReadWriteMap "read-write map" returns the
kpeter@80
  1527
  /// logical negation of the values of the given map.
kpeter@80
  1528
  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
kpeter@80
  1529
  /// It makes also possible to write the map. When a value is set,
kpeter@80
  1530
  /// the opposite value is set to the original map.
kpeter@29
  1531
  ///
kpeter@80
  1532
  /// The simplest way of using this map is through the notWriteMap()
kpeter@80
  1533
  /// function.
kpeter@80
  1534
  ///
kpeter@80
  1535
  /// \sa NotMap
kpeter@80
  1536
  template <typename M>
alpar@25
  1537
  class NotWriteMap : public MapBase<typename M::Key, bool> {
kpeter@80
  1538
    M &_m;
alpar@25
  1539
  public:
alpar@25
  1540
    typedef MapBase<typename M::Key, bool> Parent;
alpar@25
  1541
    typedef typename Parent::Key Key;
alpar@25
  1542
    typedef typename Parent::Value Value;
alpar@25
  1543
alpar@25
  1544
    /// Constructor
kpeter@80
  1545
    NotWriteMap(M &m) : _m(m) {}
kpeter@80
  1546
    /// \e
kpeter@80
  1547
    Value operator[](const Key &k) const { return !_m[k]; }
kpeter@80
  1548
    /// \e
kpeter@80
  1549
    void set(const Key &k, bool v) { _m.set(k, !v); }
alpar@25
  1550
  };
kpeter@80
  1551
kpeter@80
  1552
  /// Returns a \ref NotMap class
kpeter@80
  1553
kpeter@80
  1554
  /// This function just returns a \ref NotMap class.
kpeter@80
  1555
  ///
kpeter@80
  1556
  /// For example, if \c m is a map with \c bool values, then
kpeter@80
  1557
  /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
kpeter@80
  1558
  ///
kpeter@80
  1559
  /// \relates NotMap
kpeter@80
  1560
  template <typename M>
alpar@25
  1561
  inline NotMap<M> notMap(const M &m) {
alpar@25
  1562
    return NotMap<M>(m);
alpar@25
  1563
  }
kpeter@80
  1564
kpeter@80
  1565
  /// Returns a \ref NotWriteMap class
kpeter@80
  1566
kpeter@80
  1567
  /// This function just returns a \ref NotWriteMap class.
kpeter@80
  1568
  ///
kpeter@80
  1569
  /// For example, if \c m is a map with \c bool values, then
kpeter@80
  1570
  /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
kpeter@80
  1571
  /// Moreover it makes also possible to write the map.
kpeter@80
  1572
  ///
kpeter@80
  1573
  /// \relates NotWriteMap
kpeter@80
  1574
  template <typename M>
kpeter@80
  1575
  inline NotWriteMap<M> notWriteMap(M &m) {
alpar@25
  1576
    return NotWriteMap<M>(m);
alpar@25
  1577
  }
alpar@25
  1578
kpeter@82
  1579
kpeter@82
  1580
  /// Combination of two maps using the \c == operator
kpeter@82
  1581
kpeter@82
  1582
  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
kpeter@82
  1583
  /// the keys for which the corresponding values of the two maps are
kpeter@82
  1584
  /// equal.
kpeter@82
  1585
  /// Its \c Key type is inherited from \c M1 and its \c Value type is
kpeter@82
  1586
  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
kpeter@82
  1587
  ///
kpeter@82
  1588
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@82
  1589
  /// \code
kpeter@82
  1590
  ///   EqualMap<M1,M2> em(m1,m2);
kpeter@82
  1591
  /// \endcode
kpeter@82
  1592
  /// <tt>em[x]</tt> will be equal to <tt>m1[x]==m2[x]</tt>.
kpeter@82
  1593
  ///
kpeter@82
  1594
  /// The simplest way of using this map is through the equalMap()
kpeter@82
  1595
  /// function.
kpeter@82
  1596
  ///
kpeter@82
  1597
  /// \sa LessMap
kpeter@82
  1598
  template<typename M1, typename M2>
kpeter@82
  1599
  class EqualMap : public MapBase<typename M1::Key, bool> {
kpeter@82
  1600
    const M1 &_m1;
kpeter@82
  1601
    const M2 &_m2;
kpeter@82
  1602
  public:
kpeter@82
  1603
    typedef MapBase<typename M1::Key, bool> Parent;
kpeter@82
  1604
    typedef typename Parent::Key Key;
kpeter@82
  1605
    typedef typename Parent::Value Value;
kpeter@82
  1606
kpeter@82
  1607
    /// Constructor
kpeter@82
  1608
    EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@82
  1609
    /// \e
kpeter@82
  1610
    Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
kpeter@82
  1611
  };
kpeter@82
  1612
kpeter@82
  1613
  /// Returns an \ref EqualMap class
kpeter@82
  1614
kpeter@82
  1615
  /// This function just returns an \ref EqualMap class.
kpeter@82
  1616
  ///
kpeter@82
  1617
  /// For example, if \c m1 and \c m2 are maps with keys and values of
kpeter@82
  1618
  /// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to
kpeter@82
  1619
  /// <tt>m1[x]==m2[x]</tt>.
kpeter@82
  1620
  ///
kpeter@82
  1621
  /// \relates EqualMap
kpeter@82
  1622
  template<typename M1, typename M2>
kpeter@82
  1623
  inline EqualMap<M1, M2> equalMap(const M1 &m1, const M2 &m2) {
kpeter@82
  1624
    return EqualMap<M1, M2>(m1,m2);
kpeter@82
  1625
  }
kpeter@82
  1626
kpeter@82
  1627
kpeter@82
  1628
  /// Combination of two maps using the \c < operator
kpeter@82
  1629
kpeter@82
  1630
  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
kpeter@82
  1631
  /// the keys for which the corresponding value of the first map is
kpeter@82
  1632
  /// less then the value of the second map.
kpeter@82
  1633
  /// Its \c Key type is inherited from \c M1 and its \c Value type is
kpeter@82
  1634
  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
kpeter@82
  1635
  ///
kpeter@82
  1636
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@82
  1637
  /// \code
kpeter@82
  1638
  ///   LessMap<M1,M2> lm(m1,m2);
kpeter@82
  1639
  /// \endcode
kpeter@82
  1640
  /// <tt>lm[x]</tt> will be equal to <tt>m1[x]<m2[x]</tt>.
kpeter@82
  1641
  ///
kpeter@82
  1642
  /// The simplest way of using this map is through the lessMap()
kpeter@82
  1643
  /// function.
kpeter@82
  1644
  ///
kpeter@82
  1645
  /// \sa EqualMap
kpeter@82
  1646
  template<typename M1, typename M2>
kpeter@82
  1647
  class LessMap : public MapBase<typename M1::Key, bool> {
kpeter@82
  1648
    const M1 &_m1;
kpeter@82
  1649
    const M2 &_m2;
kpeter@82
  1650
  public:
kpeter@82
  1651
    typedef MapBase<typename M1::Key, bool> Parent;
kpeter@82
  1652
    typedef typename Parent::Key Key;
kpeter@82
  1653
    typedef typename Parent::Value Value;
kpeter@82
  1654
kpeter@82
  1655
    /// Constructor
kpeter@82
  1656
    LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@82
  1657
    /// \e
kpeter@82
  1658
    Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
kpeter@82
  1659
  };
kpeter@82
  1660
kpeter@82
  1661
  /// Returns an \ref LessMap class
kpeter@82
  1662
kpeter@82
  1663
  /// This function just returns an \ref LessMap class.
kpeter@82
  1664
  ///
kpeter@82
  1665
  /// For example, if \c m1 and \c m2 are maps with keys and values of
kpeter@82
  1666
  /// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to
kpeter@82
  1667
  /// <tt>m1[x]<m2[x]</tt>.
kpeter@82
  1668
  ///
kpeter@82
  1669
  /// \relates LessMap
kpeter@82
  1670
  template<typename M1, typename M2>
kpeter@82
  1671
  inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) {
kpeter@82
  1672
    return LessMap<M1, M2>(m1,m2);
kpeter@82
  1673
  }
kpeter@82
  1674
alpar@104
  1675
  namespace _maps_bits {
alpar@104
  1676
alpar@104
  1677
    template <typename _Iterator, typename Enable = void>
alpar@104
  1678
    struct IteratorTraits {
alpar@104
  1679
      typedef typename std::iterator_traits<_Iterator>::value_type Value;
alpar@104
  1680
    };
alpar@104
  1681
alpar@104
  1682
    template <typename _Iterator>
alpar@104
  1683
    struct IteratorTraits<_Iterator,
alpar@104
  1684
      typename exists<typename _Iterator::container_type>::type>
alpar@104
  1685
    {
alpar@104
  1686
      typedef typename _Iterator::container_type::value_type Value;
alpar@104
  1687
    };
alpar@104
  1688
alpar@104
  1689
  }
alpar@104
  1690
alpar@104
  1691
  /// \brief Writable bool map for logging each \c true assigned element
alpar@104
  1692
  ///
kpeter@159
  1693
  /// A \ref concepts::WriteMap "writable" bool map for logging
alpar@104
  1694
  /// each \c true assigned element, i.e it copies subsequently each
alpar@104
  1695
  /// keys set to \c true to the given iterator.
kpeter@159
  1696
  /// The most important usage of it is storing certain nodes or arcs
kpeter@159
  1697
  /// that were marked \c true by an algorithm.
alpar@104
  1698
  ///
kpeter@159
  1699
  /// There are several algorithms that provide solutions through bool
kpeter@159
  1700
  /// maps and most of them assign \c true at most once for each key.
kpeter@159
  1701
  /// In these cases it is a natural request to store each \c true
kpeter@159
  1702
  /// assigned elements (in order of the assignment), which can be
kpeter@167
  1703
  /// easily done with LoggerBoolMap.
kpeter@159
  1704
  ///
kpeter@167
  1705
  /// The simplest way of using this map is through the loggerBoolMap()
kpeter@159
  1706
  /// function.
kpeter@159
  1707
  ///
kpeter@159
  1708
  /// \tparam It The type of the iterator.
kpeter@159
  1709
  /// \tparam Ke The key type of the map. The default value set
kpeter@159
  1710
  /// according to the iterator type should work in most cases.
alpar@104
  1711
  ///
alpar@104
  1712
  /// \note The container of the iterator must contain enough space
kpeter@159
  1713
  /// for the elements or the iterator should be an inserter iterator.
kpeter@159
  1714
#ifdef DOXYGEN
kpeter@159
  1715
  template <typename It, typename Ke>
kpeter@159
  1716
#else
alpar@104
  1717
  template <typename It,
alpar@104
  1718
	    typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
kpeter@159
  1719
#endif
kpeter@167
  1720
  class LoggerBoolMap {
alpar@104
  1721
  public:
alpar@104
  1722
    typedef It Iterator;
alpar@104
  1723
alpar@104
  1724
    typedef Ke Key;
alpar@104
  1725
    typedef bool Value;
alpar@104
  1726
alpar@104
  1727
    /// Constructor
kpeter@167
  1728
    LoggerBoolMap(Iterator it)
alpar@104
  1729
      : _begin(it), _end(it) {}
alpar@104
  1730
alpar@104
  1731
    /// Gives back the given iterator set for the first key
alpar@104
  1732
    Iterator begin() const {
alpar@104
  1733
      return _begin;
alpar@104
  1734
    }
alpar@104
  1735
alpar@104
  1736
    /// Gives back the the 'after the last' iterator
alpar@104
  1737
    Iterator end() const {
alpar@104
  1738
      return _end;
alpar@104
  1739
    }
alpar@104
  1740
alpar@104
  1741
    /// The set function of the map
kpeter@159
  1742
    void set(const Key& key, Value value) {
alpar@104
  1743
      if (value) {
alpar@104
  1744
	*_end++ = key;
alpar@104
  1745
      }
alpar@104
  1746
    }
alpar@104
  1747
alpar@104
  1748
  private:
alpar@104
  1749
    Iterator _begin;
kpeter@159
  1750
    Iterator _end;
alpar@104
  1751
  };
kpeter@159
  1752
  
kpeter@167
  1753
  /// Returns a \ref LoggerBoolMap class
kpeter@159
  1754
kpeter@167
  1755
  /// This function just returns a \ref LoggerBoolMap class.
kpeter@159
  1756
  ///
kpeter@159
  1757
  /// The most important usage of it is storing certain nodes or arcs
kpeter@159
  1758
  /// that were marked \c true by an algorithm.
kpeter@159
  1759
  /// For example it makes easier to store the nodes in the processing
kpeter@159
  1760
  /// order of Dfs algorithm, as the following examples show.
kpeter@159
  1761
  /// \code
kpeter@159
  1762
  ///   std::vector<Node> v;
kpeter@167
  1763
  ///   dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
kpeter@159
  1764
  /// \endcode
kpeter@159
  1765
  /// \code
kpeter@159
  1766
  ///   std::vector<Node> v(countNodes(g));
kpeter@167
  1767
  ///   dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
kpeter@159
  1768
  /// \endcode
kpeter@159
  1769
  ///
kpeter@159
  1770
  /// \note The container of the iterator must contain enough space
kpeter@159
  1771
  /// for the elements or the iterator should be an inserter iterator.
kpeter@159
  1772
  ///
kpeter@167
  1773
  /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
kpeter@159
  1774
  /// it cannot be used when a readable map is needed, for example as
kpeter@167
  1775
  /// \c ReachedMap for \ref Bfs, \ref Dfs and \ref Dijkstra algorithms.
kpeter@159
  1776
  ///
kpeter@167
  1777
  /// \relates LoggerBoolMap
kpeter@159
  1778
  template<typename Iterator>
kpeter@167
  1779
  inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
kpeter@167
  1780
    return LoggerBoolMap<Iterator>(it);
kpeter@159
  1781
  }
alpar@104
  1782
alpar@25
  1783
  /// @}
alpar@25
  1784
}
alpar@25
  1785
alpar@25
  1786
#endif // LEMON_MAPS_H