lemon/maps.h
author Alpar Juttner <alpar@cs.elte.hu>
Thu, 05 Nov 2009 10:01:02 +0100
changeset 779 c160bf9f18ef
parent 617 4137ef9aacc6
child 695 8dae88c5943e
child 720 6e8c27ee9079
permissions -rw-r--r--
Merge
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@25
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@25
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
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
deba@220
    26
#include <lemon/core.h>
alpar@25
    27
alpar@25
    28
///\file
alpar@25
    29
///\ingroup maps
alpar@25
    30
///\brief Miscellaneous property maps
kpeter@80
    31
alpar@25
    32
#include <map>
alpar@25
    33
alpar@25
    34
namespace lemon {
alpar@25
    35
alpar@25
    36
  /// \addtogroup maps
alpar@25
    37
  /// @{
alpar@25
    38
alpar@25
    39
  /// Base class of maps.
alpar@25
    40
kpeter@80
    41
  /// Base class of maps. It provides the necessary type definitions
kpeter@80
    42
  /// required by the map %concepts.
kpeter@80
    43
  template<typename K, typename V>
alpar@25
    44
  class MapBase {
alpar@25
    45
  public:
kpeter@313
    46
    /// \brief The key type of the map.
alpar@25
    47
    typedef K Key;
kpeter@80
    48
    /// \brief The value type of the map.
kpeter@80
    49
    /// (The type of objects associated with the keys).
kpeter@80
    50
    typedef V Value;
alpar@25
    51
  };
alpar@25
    52
kpeter@80
    53
alpar@25
    54
  /// Null map. (a.k.a. DoNothingMap)
alpar@25
    55
kpeter@29
    56
  /// This map can be used if you have to provide a map only for
kpeter@80
    57
  /// its type definitions, or if you have to provide a writable map,
kpeter@80
    58
  /// but data written to it is not required (i.e. it will be sent to
kpeter@29
    59
  /// <tt>/dev/null</tt>).
kpeter@80
    60
  /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
kpeter@80
    61
  ///
kpeter@80
    62
  /// \sa ConstMap
kpeter@80
    63
  template<typename K, typename V>
kpeter@80
    64
  class NullMap : public MapBase<K, V> {
alpar@25
    65
  public:
kpeter@559
    66
    ///\e
kpeter@559
    67
    typedef K Key;
kpeter@559
    68
    ///\e
kpeter@559
    69
    typedef V 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@301
    77
  /// Returns a \c NullMap class
kpeter@301
    78
kpeter@301
    79
  /// This function just returns a \c 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@301
    92
  /// In other aspects it is equivalent to \c 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@559
   106
    ///\e
kpeter@559
   107
    typedef K Key;
kpeter@559
   108
    ///\e
kpeter@559
   109
    typedef V Value;
alpar@25
   110
alpar@25
   111
    /// Default constructor
alpar@25
   112
kpeter@29
   113
    /// Default constructor.
kpeter@80
   114
    /// The value of the map will be default constructed.
alpar@25
   115
    ConstMap() {}
kpeter@80
   116
kpeter@29
   117
    /// Constructor with specified initial value
alpar@25
   118
kpeter@29
   119
    /// Constructor with specified initial value.
kpeter@123
   120
    /// \param v The initial value of the map.
kpeter@80
   121
    ConstMap(const Value &v) : _value(v) {}
alpar@25
   122
kpeter@80
   123
    /// Gives back the specified value.
kpeter@80
   124
    Value operator[](const Key&) const { return _value; }
alpar@25
   125
kpeter@80
   126
    /// Absorbs the value.
kpeter@80
   127
    void set(const Key&, const Value&) {}
kpeter@80
   128
kpeter@80
   129
    /// Sets the value that is assigned to each key.
kpeter@80
   130
    void setAll(const Value &v) {
kpeter@80
   131
      _value = v;
kpeter@80
   132
    }
kpeter@80
   133
kpeter@80
   134
    template<typename V1>
kpeter@80
   135
    ConstMap(const ConstMap<K, V1> &, const Value &v) : _value(v) {}
alpar@25
   136
  };
alpar@25
   137
kpeter@301
   138
  /// Returns a \c ConstMap class
kpeter@301
   139
kpeter@301
   140
  /// This function just returns a \c ConstMap class.
kpeter@80
   141
  /// \relates ConstMap
kpeter@80
   142
  template<typename K, typename V>
alpar@25
   143
  inline ConstMap<K, V> constMap(const V &v) {
alpar@25
   144
    return ConstMap<K, V>(v);
alpar@25
   145
  }
alpar@25
   146
kpeter@123
   147
  template<typename K, typename V>
kpeter@123
   148
  inline ConstMap<K, V> constMap() {
kpeter@123
   149
    return ConstMap<K, V>();
kpeter@123
   150
  }
kpeter@123
   151
alpar@25
   152
alpar@25
   153
  template<typename T, T v>
kpeter@80
   154
  struct Const {};
alpar@25
   155
alpar@25
   156
  /// Constant map with inlined constant value.
alpar@25
   157
kpeter@82
   158
  /// This \ref concepts::ReadMap "readable map" assigns a specified
kpeter@82
   159
  /// value to each key.
kpeter@80
   160
  ///
kpeter@301
   161
  /// In other aspects it is equivalent to \c NullMap.
kpeter@80
   162
  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
kpeter@80
   163
  /// concept, but it absorbs the data written to it.
kpeter@80
   164
  ///
kpeter@80
   165
  /// The simplest way of using this map is through the constMap()
kpeter@80
   166
  /// function.
kpeter@80
   167
  ///
kpeter@80
   168
  /// \sa NullMap
kpeter@80
   169
  /// \sa IdentityMap
alpar@25
   170
  template<typename K, typename V, V v>
alpar@25
   171
  class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
alpar@25
   172
  public:
kpeter@559
   173
    ///\e
kpeter@559
   174
    typedef K Key;
kpeter@559
   175
    ///\e
kpeter@559
   176
    typedef V Value;
alpar@25
   177
kpeter@80
   178
    /// Constructor.
kpeter@80
   179
    ConstMap() {}
kpeter@80
   180
kpeter@80
   181
    /// Gives back the specified value.
kpeter@80
   182
    Value operator[](const Key&) const { return v; }
kpeter@80
   183
kpeter@80
   184
    /// Absorbs the value.
kpeter@80
   185
    void set(const Key&, const Value&) {}
alpar@25
   186
  };
alpar@25
   187
kpeter@301
   188
  /// Returns a \c ConstMap class with inlined constant value
kpeter@301
   189
kpeter@301
   190
  /// This function just returns a \c ConstMap class with inlined
kpeter@80
   191
  /// constant value.
kpeter@80
   192
  /// \relates ConstMap
kpeter@80
   193
  template<typename K, typename V, V v>
alpar@25
   194
  inline ConstMap<K, Const<V, v> > constMap() {
alpar@25
   195
    return ConstMap<K, Const<V, v> >();
alpar@25
   196
  }
alpar@25
   197
alpar@25
   198
kpeter@82
   199
  /// Identity map.
kpeter@82
   200
kpeter@82
   201
  /// This \ref concepts::ReadMap "read-only map" gives back the given
kpeter@82
   202
  /// key as value without any modification.
kpeter@80
   203
  ///
kpeter@80
   204
  /// \sa ConstMap
kpeter@80
   205
  template <typename T>
kpeter@80
   206
  class IdentityMap : public MapBase<T, T> {
kpeter@80
   207
  public:
kpeter@559
   208
    ///\e
kpeter@559
   209
    typedef T Key;
kpeter@559
   210
    ///\e
kpeter@559
   211
    typedef T Value;
kpeter@80
   212
kpeter@80
   213
    /// Gives back the given value without any modification.
kpeter@82
   214
    Value operator[](const Key &k) const {
kpeter@82
   215
      return k;
kpeter@80
   216
    }
kpeter@80
   217
  };
kpeter@80
   218
kpeter@301
   219
  /// Returns an \c IdentityMap class
kpeter@301
   220
kpeter@301
   221
  /// This function just returns an \c IdentityMap class.
kpeter@80
   222
  /// \relates IdentityMap
kpeter@80
   223
  template<typename T>
kpeter@80
   224
  inline IdentityMap<T> identityMap() {
kpeter@80
   225
    return IdentityMap<T>();
kpeter@80
   226
  }
kpeter@80
   227
kpeter@80
   228
kpeter@80
   229
  /// \brief Map for storing values for integer keys from the range
kpeter@80
   230
  /// <tt>[0..size-1]</tt>.
kpeter@80
   231
  ///
kpeter@80
   232
  /// This map is essentially a wrapper for \c std::vector. It assigns
kpeter@80
   233
  /// values to integer keys from the range <tt>[0..size-1]</tt>.
kpeter@80
   234
  /// It can be used with some data structures, for example
kpeter@301
   235
  /// \c UnionFind, \c BinHeap, when the used items are small
kpeter@80
   236
  /// integers. This map conforms the \ref concepts::ReferenceMap
kpeter@80
   237
  /// "ReferenceMap" concept.
kpeter@80
   238
  ///
kpeter@80
   239
  /// The simplest way of using this map is through the rangeMap()
kpeter@80
   240
  /// function.
kpeter@80
   241
  template <typename V>
kpeter@80
   242
  class RangeMap : public MapBase<int, V> {
kpeter@80
   243
    template <typename V1>
kpeter@80
   244
    friend class RangeMap;
kpeter@80
   245
  private:
kpeter@80
   246
kpeter@80
   247
    typedef std::vector<V> Vector;
kpeter@80
   248
    Vector _vector;
kpeter@80
   249
alpar@25
   250
  public:
alpar@25
   251
kpeter@80
   252
    /// Key type
kpeter@559
   253
    typedef int Key;
kpeter@80
   254
    /// Value type
kpeter@559
   255
    typedef V Value;
kpeter@80
   256
    /// Reference type
kpeter@80
   257
    typedef typename Vector::reference Reference;
kpeter@80
   258
    /// Const reference type
kpeter@80
   259
    typedef typename Vector::const_reference ConstReference;
kpeter@80
   260
kpeter@80
   261
    typedef True ReferenceMapTag;
kpeter@80
   262
kpeter@80
   263
  public:
kpeter@80
   264
kpeter@80
   265
    /// Constructor with specified default value.
kpeter@80
   266
    RangeMap(int size = 0, const Value &value = Value())
kpeter@80
   267
      : _vector(size, value) {}
kpeter@80
   268
kpeter@80
   269
    /// Constructs the map from an appropriate \c std::vector.
kpeter@80
   270
    template <typename V1>
kpeter@80
   271
    RangeMap(const std::vector<V1>& vector)
kpeter@80
   272
      : _vector(vector.begin(), vector.end()) {}
kpeter@80
   273
kpeter@301
   274
    /// Constructs the map from another \c RangeMap.
kpeter@80
   275
    template <typename V1>
kpeter@80
   276
    RangeMap(const RangeMap<V1> &c)
kpeter@80
   277
      : _vector(c._vector.begin(), c._vector.end()) {}
kpeter@80
   278
kpeter@80
   279
    /// Returns the size of the map.
kpeter@80
   280
    int size() {
kpeter@80
   281
      return _vector.size();
kpeter@80
   282
    }
kpeter@80
   283
kpeter@80
   284
    /// Resizes the map.
kpeter@80
   285
kpeter@80
   286
    /// Resizes the underlying \c std::vector container, so changes the
kpeter@80
   287
    /// keyset of the map.
kpeter@80
   288
    /// \param size The new size of the map. The new keyset will be the
kpeter@80
   289
    /// range <tt>[0..size-1]</tt>.
kpeter@80
   290
    /// \param value The default value to assign to the new keys.
kpeter@80
   291
    void resize(int size, const Value &value = Value()) {
kpeter@80
   292
      _vector.resize(size, value);
kpeter@80
   293
    }
kpeter@80
   294
kpeter@80
   295
  private:
kpeter@80
   296
kpeter@80
   297
    RangeMap& operator=(const RangeMap&);
kpeter@80
   298
kpeter@80
   299
  public:
kpeter@80
   300
kpeter@80
   301
    ///\e
kpeter@80
   302
    Reference operator[](const Key &k) {
kpeter@80
   303
      return _vector[k];
kpeter@80
   304
    }
kpeter@80
   305
kpeter@80
   306
    ///\e
kpeter@80
   307
    ConstReference operator[](const Key &k) const {
kpeter@80
   308
      return _vector[k];
kpeter@80
   309
    }
kpeter@80
   310
kpeter@80
   311
    ///\e
kpeter@80
   312
    void set(const Key &k, const Value &v) {
kpeter@80
   313
      _vector[k] = v;
kpeter@80
   314
    }
kpeter@80
   315
  };
kpeter@80
   316
kpeter@301
   317
  /// Returns a \c RangeMap class
kpeter@301
   318
kpeter@301
   319
  /// This function just returns a \c RangeMap class.
kpeter@80
   320
  /// \relates RangeMap
kpeter@80
   321
  template<typename V>
kpeter@80
   322
  inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
kpeter@80
   323
    return RangeMap<V>(size, value);
kpeter@80
   324
  }
kpeter@80
   325
kpeter@301
   326
  /// \brief Returns a \c RangeMap class created from an appropriate
kpeter@80
   327
  /// \c std::vector
kpeter@80
   328
kpeter@301
   329
  /// This function just returns a \c RangeMap class created from an
kpeter@80
   330
  /// appropriate \c std::vector.
kpeter@80
   331
  /// \relates RangeMap
kpeter@80
   332
  template<typename V>
kpeter@80
   333
  inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
kpeter@80
   334
    return RangeMap<V>(vector);
kpeter@80
   335
  }
kpeter@80
   336
kpeter@80
   337
kpeter@80
   338
  /// Map type based on \c std::map
kpeter@80
   339
kpeter@80
   340
  /// This map is essentially a wrapper for \c std::map with addition
kpeter@80
   341
  /// that you can specify a default value for the keys that are not
kpeter@80
   342
  /// stored actually. This value can be different from the default
kpeter@80
   343
  /// contructed value (i.e. \c %Value()).
kpeter@80
   344
  /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
kpeter@80
   345
  /// concept.
kpeter@80
   346
  ///
kpeter@80
   347
  /// This map is useful if a default value should be assigned to most of
kpeter@80
   348
  /// the keys and different values should be assigned only to a few
kpeter@80
   349
  /// keys (i.e. the map is "sparse").
kpeter@80
   350
  /// The name of this type also refers to this important usage.
kpeter@80
   351
  ///
kpeter@80
   352
  /// Apart form that this map can be used in many other cases since it
kpeter@80
   353
  /// is based on \c std::map, which is a general associative container.
kpeter@80
   354
  /// However keep in mind that it is usually not as efficient as other
kpeter@80
   355
  /// maps.
kpeter@80
   356
  ///
kpeter@80
   357
  /// The simplest way of using this map is through the sparseMap()
kpeter@80
   358
  /// function.
kpeter@559
   359
  template <typename K, typename V, typename Comp = std::less<K> >
kpeter@80
   360
  class SparseMap : public MapBase<K, V> {
kpeter@80
   361
    template <typename K1, typename V1, typename C1>
kpeter@80
   362
    friend class SparseMap;
kpeter@80
   363
  public:
kpeter@80
   364
kpeter@80
   365
    /// Key type
kpeter@559
   366
    typedef K Key;
kpeter@80
   367
    /// Value type
kpeter@559
   368
    typedef V Value;
kpeter@80
   369
    /// Reference type
kpeter@80
   370
    typedef Value& Reference;
kpeter@80
   371
    /// Const reference type
kpeter@80
   372
    typedef const Value& ConstReference;
alpar@25
   373
kpeter@45
   374
    typedef True ReferenceMapTag;
kpeter@45
   375
alpar@25
   376
  private:
kpeter@80
   377
kpeter@559
   378
    typedef std::map<K, V, Comp> Map;
kpeter@80
   379
    Map _map;
alpar@25
   380
    Value _value;
alpar@25
   381
alpar@25
   382
  public:
alpar@25
   383
kpeter@80
   384
    /// \brief Constructor with specified default value.
kpeter@80
   385
    SparseMap(const Value &value = Value()) : _value(value) {}
kpeter@80
   386
    /// \brief Constructs the map from an appropriate \c std::map, and
kpeter@47
   387
    /// explicitly specifies a default value.
kpeter@80
   388
    template <typename V1, typename Comp1>
kpeter@80
   389
    SparseMap(const std::map<Key, V1, Comp1> &map,
kpeter@80
   390
              const Value &value = Value())
alpar@25
   391
      : _map(map.begin(), map.end()), _value(value) {}
kpeter@80
   392
kpeter@301
   393
    /// \brief Constructs the map from another \c SparseMap.
kpeter@80
   394
    template<typename V1, typename Comp1>
kpeter@80
   395
    SparseMap(const SparseMap<Key, V1, Comp1> &c)
alpar@25
   396
      : _map(c._map.begin(), c._map.end()), _value(c._value) {}
alpar@25
   397
alpar@25
   398
  private:
alpar@25
   399
kpeter@80
   400
    SparseMap& operator=(const SparseMap&);
alpar@25
   401
alpar@25
   402
  public:
alpar@25
   403
alpar@25
   404
    ///\e
alpar@25
   405
    Reference operator[](const Key &k) {
alpar@25
   406
      typename Map::iterator it = _map.lower_bound(k);
alpar@25
   407
      if (it != _map.end() && !_map.key_comp()(k, it->first))
alpar@209
   408
        return it->second;
alpar@25
   409
      else
alpar@209
   410
        return _map.insert(it, std::make_pair(k, _value))->second;
alpar@25
   411
    }
alpar@25
   412
kpeter@80
   413
    ///\e
alpar@25
   414
    ConstReference operator[](const Key &k) const {
alpar@25
   415
      typename Map::const_iterator it = _map.find(k);
alpar@25
   416
      if (it != _map.end())
alpar@209
   417
        return it->second;
alpar@25
   418
      else
alpar@209
   419
        return _value;
alpar@25
   420
    }
alpar@25
   421
kpeter@80
   422
    ///\e
kpeter@80
   423
    void set(const Key &k, const Value &v) {
alpar@25
   424
      typename Map::iterator it = _map.lower_bound(k);
alpar@25
   425
      if (it != _map.end() && !_map.key_comp()(k, it->first))
alpar@209
   426
        it->second = v;
alpar@25
   427
      else
alpar@209
   428
        _map.insert(it, std::make_pair(k, v));
alpar@25
   429
    }
alpar@25
   430
kpeter@80
   431
    ///\e
kpeter@80
   432
    void setAll(const Value &v) {
kpeter@80
   433
      _value = v;
alpar@25
   434
      _map.clear();
kpeter@80
   435
    }
kpeter@80
   436
  };
alpar@25
   437
kpeter@301
   438
  /// Returns a \c SparseMap class
kpeter@301
   439
kpeter@301
   440
  /// This function just returns a \c SparseMap class with specified
kpeter@80
   441
  /// default value.
kpeter@80
   442
  /// \relates SparseMap
kpeter@80
   443
  template<typename K, typename V, typename Compare>
kpeter@80
   444
  inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
kpeter@80
   445
    return SparseMap<K, V, Compare>(value);
kpeter@54
   446
  }
kpeter@45
   447
kpeter@80
   448
  template<typename K, typename V>
kpeter@80
   449
  inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
kpeter@80
   450
    return SparseMap<K, V, std::less<K> >(value);
kpeter@45
   451
  }
alpar@25
   452
kpeter@301
   453
  /// \brief Returns a \c SparseMap class created from an appropriate
kpeter@80
   454
  /// \c std::map
alpar@25
   455
kpeter@301
   456
  /// This function just returns a \c SparseMap class created from an
kpeter@80
   457
  /// appropriate \c std::map.
kpeter@80
   458
  /// \relates SparseMap
kpeter@80
   459
  template<typename K, typename V, typename Compare>
kpeter@80
   460
  inline SparseMap<K, V, Compare>
kpeter@80
   461
    sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
kpeter@80
   462
  {
kpeter@80
   463
    return SparseMap<K, V, Compare>(map, value);
kpeter@45
   464
  }
alpar@25
   465
alpar@25
   466
  /// @}
alpar@25
   467
alpar@25
   468
  /// \addtogroup map_adaptors
alpar@25
   469
  /// @{
alpar@25
   470
kpeter@80
   471
  /// Composition of two maps
kpeter@80
   472
kpeter@82
   473
  /// This \ref concepts::ReadMap "read-only map" returns the
kpeter@80
   474
  /// composition of two given maps. That is to say, if \c m1 is of
kpeter@80
   475
  /// type \c M1 and \c m2 is of \c M2, then for
kpeter@80
   476
  /// \code
kpeter@80
   477
  ///   ComposeMap<M1, M2> cm(m1,m2);
kpeter@80
   478
  /// \endcode
kpeter@80
   479
  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
alpar@25
   480
  ///
kpeter@80
   481
  /// The \c Key type of the map is inherited from \c M2 and the
kpeter@80
   482
  /// \c Value type is from \c M1.
kpeter@80
   483
  /// \c M2::Value must be convertible to \c M1::Key.
kpeter@80
   484
  ///
kpeter@80
   485
  /// The simplest way of using this map is through the composeMap()
kpeter@80
   486
  /// function.
kpeter@80
   487
  ///
kpeter@80
   488
  /// \sa CombineMap
kpeter@80
   489
  template <typename M1, typename M2>
kpeter@80
   490
  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
kpeter@80
   491
    const M1 &_m1;
kpeter@80
   492
    const M2 &_m2;
alpar@25
   493
  public:
kpeter@559
   494
    ///\e
kpeter@559
   495
    typedef typename M2::Key Key;
kpeter@559
   496
    ///\e
kpeter@559
   497
    typedef typename M1::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
kpeter@559
   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@301
   507
  /// Returns a \c ComposeMap class
kpeter@301
   508
kpeter@301
   509
  /// This function just returns a \c 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
  template<typename M1, typename M2, typename F,
alpar@209
   545
           typename V = typename F::result_type>
kpeter@80
   546
  class CombineMap : public MapBase<typename M1::Key, V> {
kpeter@80
   547
    const M1 &_m1;
kpeter@80
   548
    const M2 &_m2;
kpeter@80
   549
    F _f;
alpar@25
   550
  public:
kpeter@559
   551
    ///\e
kpeter@559
   552
    typedef typename M1::Key Key;
kpeter@559
   553
    ///\e
kpeter@559
   554
    typedef V Value;
alpar@25
   555
kpeter@80
   556
    /// Constructor
kpeter@80
   557
    CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
kpeter@80
   558
      : _m1(m1), _m2(m2), _f(f) {}
kpeter@559
   559
    ///\e
kpeter@80
   560
    Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
kpeter@80
   561
  };
alpar@25
   562
kpeter@301
   563
  /// Returns a \c CombineMap class
kpeter@301
   564
kpeter@301
   565
  /// This function just returns a \c CombineMap class.
kpeter@80
   566
  ///
kpeter@80
   567
  /// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80
   568
  /// values, then
kpeter@80
   569
  /// \code
kpeter@80
   570
  ///   combineMap(m1,m2,std::plus<double>())
kpeter@80
   571
  /// \endcode
kpeter@80
   572
  /// is equivalent to
kpeter@80
   573
  /// \code
kpeter@80
   574
  ///   addMap(m1,m2)
kpeter@80
   575
  /// \endcode
kpeter@80
   576
  ///
kpeter@80
   577
  /// This function is specialized for adaptable binary function
kpeter@80
   578
  /// classes and C++ functions.
kpeter@80
   579
  ///
kpeter@80
   580
  /// \relates CombineMap
kpeter@80
   581
  template<typename M1, typename M2, typename F, typename V>
kpeter@80
   582
  inline CombineMap<M1, M2, F, V>
kpeter@80
   583
  combineMap(const M1 &m1, const M2 &m2, const F &f) {
kpeter@80
   584
    return CombineMap<M1, M2, F, V>(m1,m2,f);
alpar@25
   585
  }
alpar@25
   586
kpeter@80
   587
  template<typename M1, typename M2, typename F>
kpeter@80
   588
  inline CombineMap<M1, M2, F, typename F::result_type>
kpeter@80
   589
  combineMap(const M1 &m1, const M2 &m2, const F &f) {
kpeter@80
   590
    return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
kpeter@80
   591
  }
alpar@25
   592
kpeter@80
   593
  template<typename M1, typename M2, typename K1, typename K2, typename V>
kpeter@80
   594
  inline CombineMap<M1, M2, V (*)(K1, K2), V>
kpeter@80
   595
  combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
kpeter@80
   596
    return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
kpeter@80
   597
  }
kpeter@80
   598
kpeter@80
   599
kpeter@80
   600
  /// Converts an STL style (unary) functor to a map
kpeter@80
   601
kpeter@82
   602
  /// This \ref concepts::ReadMap "read-only map" returns the value
kpeter@80
   603
  /// of a given functor. Actually, it just wraps the functor and
kpeter@80
   604
  /// provides the \c Key and \c Value typedefs.
alpar@26
   605
  ///
kpeter@80
   606
  /// Template parameters \c K and \c V will become its \c Key and
kpeter@80
   607
  /// \c Value. In most cases they have to be given explicitly because
kpeter@80
   608
  /// a functor typically does not provide \c argument_type and
kpeter@80
   609
  /// \c result_type typedefs.
kpeter@80
   610
  /// Parameter \c F is the type of the used functor.
kpeter@29
   611
  ///
kpeter@80
   612
  /// The simplest way of using this map is through the functorToMap()
kpeter@80
   613
  /// function.
kpeter@80
   614
  ///
kpeter@80
   615
  /// \sa MapToFunctor
kpeter@80
   616
  template<typename F,
alpar@209
   617
           typename K = typename F::argument_type,
alpar@209
   618
           typename V = typename F::result_type>
kpeter@80
   619
  class FunctorToMap : public MapBase<K, V> {
kpeter@123
   620
    F _f;
kpeter@80
   621
  public:
kpeter@559
   622
    ///\e
kpeter@559
   623
    typedef K Key;
kpeter@559
   624
    ///\e
kpeter@559
   625
    typedef V Value;
alpar@25
   626
kpeter@80
   627
    /// Constructor
kpeter@80
   628
    FunctorToMap(const F &f = F()) : _f(f) {}
kpeter@559
   629
    ///\e
kpeter@80
   630
    Value operator[](const Key &k) const { return _f(k); }
kpeter@80
   631
  };
kpeter@80
   632
kpeter@301
   633
  /// Returns a \c FunctorToMap class
kpeter@301
   634
kpeter@301
   635
  /// This function just returns a \c 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:
kpeter@559
   677
    ///\e
kpeter@559
   678
    typedef typename M::Key Key;
kpeter@559
   679
    ///\e
kpeter@559
   680
    typedef typename M::Value Value;
kpeter@559
   681
kpeter@559
   682
    typedef typename M::Key argument_type;
kpeter@559
   683
    typedef typename M::Value result_type;
kpeter@80
   684
kpeter@80
   685
    /// Constructor
kpeter@80
   686
    MapToFunctor(const M &m) : _m(m) {}
kpeter@559
   687
    ///\e
kpeter@80
   688
    Value operator()(const Key &k) const { return _m[k]; }
kpeter@559
   689
    ///\e
kpeter@80
   690
    Value operator[](const Key &k) const { return _m[k]; }
alpar@25
   691
  };
kpeter@45
   692
kpeter@301
   693
  /// Returns a \c MapToFunctor class
kpeter@301
   694
kpeter@301
   695
  /// This function just returns a \c MapToFunctor class.
kpeter@80
   696
  /// \relates MapToFunctor
kpeter@45
   697
  template<typename M>
kpeter@80
   698
  inline MapToFunctor<M> mapToFunctor(const M &m) {
kpeter@80
   699
    return MapToFunctor<M>(m);
kpeter@45
   700
  }
alpar@25
   701
alpar@25
   702
kpeter@80
   703
  /// \brief Map adaptor to convert the \c Value type of a map to
kpeter@80
   704
  /// another type using the default conversion.
kpeter@80
   705
kpeter@80
   706
  /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap
kpeter@80
   707
  /// "readable map" to another type using the default conversion.
kpeter@80
   708
  /// The \c Key type of it is inherited from \c M and the \c Value
kpeter@80
   709
  /// type is \c V.
kpeter@80
   710
  /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
alpar@26
   711
  ///
kpeter@80
   712
  /// The simplest way of using this map is through the convertMap()
kpeter@80
   713
  /// function.
kpeter@80
   714
  template <typename M, typename V>
kpeter@80
   715
  class ConvertMap : public MapBase<typename M::Key, V> {
kpeter@80
   716
    const M &_m;
kpeter@80
   717
  public:
kpeter@559
   718
    ///\e
kpeter@559
   719
    typedef typename M::Key Key;
kpeter@559
   720
    ///\e
kpeter@559
   721
    typedef V Value;
kpeter@80
   722
kpeter@80
   723
    /// Constructor
kpeter@80
   724
kpeter@80
   725
    /// Constructor.
kpeter@80
   726
    /// \param m The underlying map.
kpeter@80
   727
    ConvertMap(const M &m) : _m(m) {}
kpeter@80
   728
kpeter@559
   729
    ///\e
kpeter@80
   730
    Value operator[](const Key &k) const { return _m[k]; }
kpeter@80
   731
  };
kpeter@80
   732
kpeter@301
   733
  /// Returns a \c ConvertMap class
kpeter@301
   734
kpeter@301
   735
  /// This function just returns a \c ConvertMap class.
kpeter@80
   736
  /// \relates ConvertMap
kpeter@80
   737
  template<typename V, typename M>
kpeter@80
   738
  inline ConvertMap<M, V> convertMap(const M &map) {
kpeter@80
   739
    return ConvertMap<M, V>(map);
kpeter@80
   740
  }
kpeter@80
   741
kpeter@80
   742
kpeter@80
   743
  /// Applies all map setting operations to two maps
kpeter@80
   744
kpeter@80
   745
  /// This map has two \ref concepts::WriteMap "writable map" parameters
kpeter@80
   746
  /// and each write request will be passed to both of them.
kpeter@80
   747
  /// If \c M1 is also \ref concepts::ReadMap "readable", then the read
kpeter@80
   748
  /// operations will return the corresponding values of \c M1.
kpeter@29
   749
  ///
kpeter@80
   750
  /// The \c Key and \c Value types are inherited from \c M1.
kpeter@80
   751
  /// The \c Key and \c Value of \c M2 must be convertible from those
kpeter@80
   752
  /// of \c M1.
kpeter@80
   753
  ///
kpeter@80
   754
  /// The simplest way of using this map is through the forkMap()
kpeter@80
   755
  /// function.
kpeter@80
   756
  template<typename  M1, typename M2>
kpeter@80
   757
  class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80
   758
    M1 &_m1;
kpeter@80
   759
    M2 &_m2;
kpeter@80
   760
  public:
kpeter@559
   761
    ///\e
kpeter@559
   762
    typedef typename M1::Key Key;
kpeter@559
   763
    ///\e
kpeter@559
   764
    typedef typename M1::Value Value;
alpar@25
   765
kpeter@80
   766
    /// Constructor
kpeter@80
   767
    ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@80
   768
    /// Returns the value associated with the given key in the first map.
kpeter@80
   769
    Value operator[](const Key &k) const { return _m1[k]; }
kpeter@80
   770
    /// Sets the value associated with the given key in both maps.
kpeter@80
   771
    void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); }
kpeter@80
   772
  };
kpeter@80
   773
kpeter@301
   774
  /// Returns a \c ForkMap class
kpeter@301
   775
kpeter@301
   776
  /// This function just returns a \c ForkMap class.
kpeter@80
   777
  /// \relates ForkMap
kpeter@80
   778
  template <typename M1, typename M2>
kpeter@80
   779
  inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) {
kpeter@80
   780
    return ForkMap<M1,M2>(m1,m2);
kpeter@80
   781
  }
kpeter@80
   782
kpeter@80
   783
kpeter@80
   784
  /// Sum of two maps
kpeter@80
   785
kpeter@82
   786
  /// This \ref concepts::ReadMap "read-only map" returns the sum
kpeter@80
   787
  /// of the values of the two given maps.
kpeter@80
   788
  /// Its \c Key and \c Value types are inherited from \c M1.
kpeter@80
   789
  /// The \c Key and \c Value of \c M2 must be convertible to those of
kpeter@80
   790
  /// \c M1.
kpeter@80
   791
  ///
kpeter@80
   792
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@80
   793
  /// \code
kpeter@80
   794
  ///   AddMap<M1,M2> am(m1,m2);
kpeter@80
   795
  /// \endcode
kpeter@80
   796
  /// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>.
kpeter@80
   797
  ///
kpeter@80
   798
  /// The simplest way of using this map is through the addMap()
kpeter@80
   799
  /// function.
kpeter@80
   800
  ///
kpeter@80
   801
  /// \sa SubMap, MulMap, DivMap
kpeter@80
   802
  /// \sa ShiftMap, ShiftWriteMap
kpeter@80
   803
  template<typename M1, typename M2>
alpar@25
   804
  class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80
   805
    const M1 &_m1;
kpeter@80
   806
    const M2 &_m2;
alpar@25
   807
  public:
kpeter@559
   808
    ///\e
kpeter@559
   809
    typedef typename M1::Key Key;
kpeter@559
   810
    ///\e
kpeter@559
   811
    typedef typename M1::Value Value;
alpar@25
   812
kpeter@80
   813
    /// Constructor
kpeter@80
   814
    AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559
   815
    ///\e
kpeter@80
   816
    Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
alpar@25
   817
  };
alpar@25
   818
kpeter@301
   819
  /// Returns an \c AddMap class
kpeter@301
   820
kpeter@301
   821
  /// This function just returns an \c AddMap class.
alpar@25
   822
  ///
kpeter@80
   823
  /// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80
   824
  /// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to
kpeter@80
   825
  /// <tt>m1[x]+m2[x]</tt>.
kpeter@80
   826
  ///
kpeter@80
   827
  /// \relates AddMap
kpeter@80
   828
  template<typename M1, typename M2>
kpeter@80
   829
  inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) {
alpar@25
   830
    return AddMap<M1, M2>(m1,m2);
alpar@25
   831
  }
alpar@25
   832
alpar@25
   833
kpeter@80
   834
  /// Difference of two maps
kpeter@80
   835
kpeter@82
   836
  /// This \ref concepts::ReadMap "read-only map" returns the difference
kpeter@80
   837
  /// of the values of the two given maps.
kpeter@80
   838
  /// Its \c Key and \c Value types are inherited from \c M1.
kpeter@80
   839
  /// The \c Key and \c Value of \c M2 must be convertible to those of
kpeter@80
   840
  /// \c M1.
alpar@25
   841
  ///
kpeter@80
   842
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@80
   843
  /// \code
kpeter@80
   844
  ///   SubMap<M1,M2> sm(m1,m2);
kpeter@80
   845
  /// \endcode
kpeter@80
   846
  /// <tt>sm[x]</tt> will be equal to <tt>m1[x]-m2[x]</tt>.
kpeter@29
   847
  ///
kpeter@80
   848
  /// The simplest way of using this map is through the subMap()
kpeter@80
   849
  /// function.
kpeter@80
   850
  ///
kpeter@80
   851
  /// \sa AddMap, MulMap, DivMap
kpeter@80
   852
  template<typename M1, typename M2>
kpeter@80
   853
  class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80
   854
    const M1 &_m1;
kpeter@80
   855
    const M2 &_m2;
kpeter@80
   856
  public:
kpeter@559
   857
    ///\e
kpeter@559
   858
    typedef typename M1::Key Key;
kpeter@559
   859
    ///\e
kpeter@559
   860
    typedef typename M1::Value Value;
kpeter@80
   861
kpeter@80
   862
    /// Constructor
kpeter@80
   863
    SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559
   864
    ///\e
kpeter@80
   865
    Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
kpeter@80
   866
  };
kpeter@80
   867
kpeter@301
   868
  /// Returns a \c SubMap class
kpeter@301
   869
kpeter@301
   870
  /// This function just returns a \c SubMap class.
kpeter@80
   871
  ///
kpeter@80
   872
  /// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80
   873
  /// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to
kpeter@80
   874
  /// <tt>m1[x]-m2[x]</tt>.
kpeter@80
   875
  ///
kpeter@80
   876
  /// \relates SubMap
kpeter@80
   877
  template<typename M1, typename M2>
kpeter@80
   878
  inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
kpeter@80
   879
    return SubMap<M1, M2>(m1,m2);
kpeter@80
   880
  }
kpeter@80
   881
kpeter@80
   882
kpeter@80
   883
  /// Product of two maps
kpeter@80
   884
kpeter@82
   885
  /// This \ref concepts::ReadMap "read-only map" returns the product
kpeter@80
   886
  /// of the values of the two given maps.
kpeter@80
   887
  /// Its \c Key and \c Value types are inherited from \c M1.
kpeter@80
   888
  /// The \c Key and \c Value of \c M2 must be convertible to those of
kpeter@80
   889
  /// \c M1.
kpeter@80
   890
  ///
kpeter@80
   891
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@80
   892
  /// \code
kpeter@80
   893
  ///   MulMap<M1,M2> mm(m1,m2);
kpeter@80
   894
  /// \endcode
kpeter@80
   895
  /// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>.
kpeter@80
   896
  ///
kpeter@80
   897
  /// The simplest way of using this map is through the mulMap()
kpeter@80
   898
  /// function.
kpeter@80
   899
  ///
kpeter@80
   900
  /// \sa AddMap, SubMap, DivMap
kpeter@80
   901
  /// \sa ScaleMap, ScaleWriteMap
kpeter@80
   902
  template<typename M1, typename M2>
kpeter@80
   903
  class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80
   904
    const M1 &_m1;
kpeter@80
   905
    const M2 &_m2;
kpeter@80
   906
  public:
kpeter@559
   907
    ///\e
kpeter@559
   908
    typedef typename M1::Key Key;
kpeter@559
   909
    ///\e
kpeter@559
   910
    typedef typename M1::Value Value;
kpeter@80
   911
kpeter@80
   912
    /// Constructor
kpeter@80
   913
    MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559
   914
    ///\e
kpeter@80
   915
    Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
kpeter@80
   916
  };
kpeter@80
   917
kpeter@301
   918
  /// Returns a \c MulMap class
kpeter@301
   919
kpeter@301
   920
  /// This function just returns a \c MulMap class.
kpeter@80
   921
  ///
kpeter@80
   922
  /// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80
   923
  /// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to
kpeter@80
   924
  /// <tt>m1[x]*m2[x]</tt>.
kpeter@80
   925
  ///
kpeter@80
   926
  /// \relates MulMap
kpeter@80
   927
  template<typename M1, typename M2>
kpeter@80
   928
  inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
kpeter@80
   929
    return MulMap<M1, M2>(m1,m2);
kpeter@80
   930
  }
kpeter@80
   931
kpeter@80
   932
kpeter@80
   933
  /// Quotient of two maps
kpeter@80
   934
kpeter@82
   935
  /// This \ref concepts::ReadMap "read-only map" returns the quotient
kpeter@80
   936
  /// of the values of the two given maps.
kpeter@80
   937
  /// Its \c Key and \c Value types are inherited from \c M1.
kpeter@80
   938
  /// The \c Key and \c Value of \c M2 must be convertible to those of
kpeter@80
   939
  /// \c M1.
kpeter@80
   940
  ///
kpeter@80
   941
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@80
   942
  /// \code
kpeter@80
   943
  ///   DivMap<M1,M2> dm(m1,m2);
kpeter@80
   944
  /// \endcode
kpeter@80
   945
  /// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>.
kpeter@80
   946
  ///
kpeter@80
   947
  /// The simplest way of using this map is through the divMap()
kpeter@80
   948
  /// function.
kpeter@80
   949
  ///
kpeter@80
   950
  /// \sa AddMap, SubMap, MulMap
kpeter@80
   951
  template<typename M1, typename M2>
kpeter@80
   952
  class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80
   953
    const M1 &_m1;
kpeter@80
   954
    const M2 &_m2;
kpeter@80
   955
  public:
kpeter@559
   956
    ///\e
kpeter@559
   957
    typedef typename M1::Key Key;
kpeter@559
   958
    ///\e
kpeter@559
   959
    typedef typename M1::Value Value;
kpeter@80
   960
kpeter@80
   961
    /// Constructor
kpeter@80
   962
    DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559
   963
    ///\e
kpeter@80
   964
    Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
kpeter@80
   965
  };
kpeter@80
   966
kpeter@301
   967
  /// Returns a \c DivMap class
kpeter@301
   968
kpeter@301
   969
  /// This function just returns a \c DivMap class.
kpeter@80
   970
  ///
kpeter@80
   971
  /// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80
   972
  /// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to
kpeter@80
   973
  /// <tt>m1[x]/m2[x]</tt>.
kpeter@80
   974
  ///
kpeter@80
   975
  /// \relates DivMap
kpeter@80
   976
  template<typename M1, typename M2>
kpeter@80
   977
  inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
kpeter@80
   978
    return DivMap<M1, M2>(m1,m2);
kpeter@80
   979
  }
kpeter@80
   980
kpeter@80
   981
kpeter@80
   982
  /// Shifts a map with a constant.
kpeter@80
   983
kpeter@82
   984
  /// This \ref concepts::ReadMap "read-only map" returns the sum of
kpeter@80
   985
  /// the given map and a constant value (i.e. it shifts the map with
kpeter@80
   986
  /// the constant). Its \c Key and \c Value are inherited from \c M.
kpeter@80
   987
  ///
kpeter@80
   988
  /// Actually,
kpeter@80
   989
  /// \code
kpeter@80
   990
  ///   ShiftMap<M> sh(m,v);
kpeter@80
   991
  /// \endcode
kpeter@80
   992
  /// is equivalent to
kpeter@80
   993
  /// \code
kpeter@80
   994
  ///   ConstMap<M::Key, M::Value> cm(v);
kpeter@80
   995
  ///   AddMap<M, ConstMap<M::Key, M::Value> > sh(m,cm);
kpeter@80
   996
  /// \endcode
kpeter@80
   997
  ///
kpeter@80
   998
  /// The simplest way of using this map is through the shiftMap()
kpeter@80
   999
  /// function.
kpeter@80
  1000
  ///
kpeter@80
  1001
  /// \sa ShiftWriteMap
kpeter@80
  1002
  template<typename M, typename C = typename M::Value>
alpar@25
  1003
  class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
  1004
    const M &_m;
kpeter@80
  1005
    C _v;
alpar@25
  1006
  public:
kpeter@559
  1007
    ///\e
kpeter@559
  1008
    typedef typename M::Key Key;
kpeter@559
  1009
    ///\e
kpeter@559
  1010
    typedef typename M::Value Value;
alpar@25
  1011
kpeter@80
  1012
    /// Constructor
alpar@25
  1013
kpeter@80
  1014
    /// Constructor.
kpeter@80
  1015
    /// \param m The undelying map.
kpeter@80
  1016
    /// \param v The constant value.
kpeter@80
  1017
    ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
kpeter@559
  1018
    ///\e
kpeter@80
  1019
    Value operator[](const Key &k) const { return _m[k]+_v; }
alpar@25
  1020
  };
alpar@25
  1021
kpeter@80
  1022
  /// Shifts a map with a constant (read-write version).
alpar@25
  1023
kpeter@80
  1024
  /// This \ref concepts::ReadWriteMap "read-write map" returns the sum
kpeter@80
  1025
  /// of the given map and a constant value (i.e. it shifts the map with
kpeter@80
  1026
  /// the constant). Its \c Key and \c Value are inherited from \c M.
kpeter@80
  1027
  /// It makes also possible to write the map.
alpar@25
  1028
  ///
kpeter@80
  1029
  /// The simplest way of using this map is through the shiftWriteMap()
kpeter@80
  1030
  /// function.
kpeter@80
  1031
  ///
kpeter@80
  1032
  /// \sa ShiftMap
kpeter@80
  1033
  template<typename M, typename C = typename M::Value>
alpar@25
  1034
  class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
  1035
    M &_m;
kpeter@80
  1036
    C _v;
alpar@25
  1037
  public:
kpeter@559
  1038
    ///\e
kpeter@559
  1039
    typedef typename M::Key Key;
kpeter@559
  1040
    ///\e
kpeter@559
  1041
    typedef typename M::Value Value;
alpar@25
  1042
kpeter@80
  1043
    /// Constructor
alpar@25
  1044
kpeter@80
  1045
    /// Constructor.
kpeter@80
  1046
    /// \param m The undelying map.
kpeter@80
  1047
    /// \param v The constant value.
kpeter@80
  1048
    ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
kpeter@559
  1049
    ///\e
kpeter@80
  1050
    Value operator[](const Key &k) const { return _m[k]+_v; }
kpeter@559
  1051
    ///\e
kpeter@80
  1052
    void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
alpar@25
  1053
  };
alpar@25
  1054
kpeter@301
  1055
  /// Returns a \c ShiftMap class
kpeter@301
  1056
kpeter@301
  1057
  /// This function just returns a \c ShiftMap class.
kpeter@80
  1058
  ///
kpeter@80
  1059
  /// For example, if \c m is a map with \c double values and \c v is
kpeter@80
  1060
  /// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to
kpeter@80
  1061
  /// <tt>m[x]+v</tt>.
kpeter@80
  1062
  ///
kpeter@80
  1063
  /// \relates ShiftMap
kpeter@80
  1064
  template<typename M, typename C>
kpeter@80
  1065
  inline ShiftMap<M, C> shiftMap(const M &m, const C &v) {
alpar@25
  1066
    return ShiftMap<M, C>(m,v);
alpar@25
  1067
  }
alpar@25
  1068
kpeter@301
  1069
  /// Returns a \c ShiftWriteMap class
kpeter@301
  1070
kpeter@301
  1071
  /// This function just returns a \c ShiftWriteMap class.
kpeter@80
  1072
  ///
kpeter@80
  1073
  /// For example, if \c m is a map with \c double values and \c v is
kpeter@80
  1074
  /// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to
kpeter@80
  1075
  /// <tt>m[x]+v</tt>.
kpeter@80
  1076
  /// Moreover it makes also possible to write the map.
kpeter@80
  1077
  ///
kpeter@80
  1078
  /// \relates ShiftWriteMap
kpeter@80
  1079
  template<typename M, typename C>
kpeter@80
  1080
  inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) {
alpar@25
  1081
    return ShiftWriteMap<M, C>(m,v);
alpar@25
  1082
  }
alpar@25
  1083
alpar@25
  1084
kpeter@80
  1085
  /// Scales a map with a constant.
kpeter@80
  1086
kpeter@82
  1087
  /// This \ref concepts::ReadMap "read-only map" returns the value of
kpeter@80
  1088
  /// the given map multiplied from the left side with a constant value.
kpeter@80
  1089
  /// Its \c Key and \c Value are inherited from \c M.
alpar@26
  1090
  ///
kpeter@80
  1091
  /// Actually,
kpeter@80
  1092
  /// \code
kpeter@80
  1093
  ///   ScaleMap<M> sc(m,v);
kpeter@80
  1094
  /// \endcode
kpeter@80
  1095
  /// is equivalent to
kpeter@80
  1096
  /// \code
kpeter@80
  1097
  ///   ConstMap<M::Key, M::Value> cm(v);
kpeter@80
  1098
  ///   MulMap<ConstMap<M::Key, M::Value>, M> sc(cm,m);
kpeter@80
  1099
  /// \endcode
alpar@25
  1100
  ///
kpeter@80
  1101
  /// The simplest way of using this map is through the scaleMap()
kpeter@80
  1102
  /// function.
alpar@25
  1103
  ///
kpeter@80
  1104
  /// \sa ScaleWriteMap
kpeter@80
  1105
  template<typename M, typename C = typename M::Value>
alpar@25
  1106
  class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
  1107
    const M &_m;
kpeter@80
  1108
    C _v;
alpar@25
  1109
  public:
kpeter@559
  1110
    ///\e
kpeter@559
  1111
    typedef typename M::Key Key;
kpeter@559
  1112
    ///\e
kpeter@559
  1113
    typedef typename M::Value Value;
alpar@25
  1114
kpeter@80
  1115
    /// Constructor
alpar@25
  1116
kpeter@80
  1117
    /// Constructor.
kpeter@80
  1118
    /// \param m The undelying map.
kpeter@80
  1119
    /// \param v The constant value.
kpeter@80
  1120
    ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
kpeter@559
  1121
    ///\e
kpeter@80
  1122
    Value operator[](const Key &k) const { return _v*_m[k]; }
alpar@25
  1123
  };
alpar@25
  1124
kpeter@80
  1125
  /// Scales a map with a constant (read-write version).
alpar@25
  1126
kpeter@80
  1127
  /// This \ref concepts::ReadWriteMap "read-write map" returns the value of
kpeter@80
  1128
  /// the given map multiplied from the left side with a constant value.
kpeter@80
  1129
  /// Its \c Key and \c Value are inherited from \c M.
kpeter@80
  1130
  /// It can also be used as write map if the \c / operator is defined
kpeter@80
  1131
  /// between \c Value and \c C and the given multiplier is not zero.
kpeter@29
  1132
  ///
kpeter@80
  1133
  /// The simplest way of using this map is through the scaleWriteMap()
kpeter@80
  1134
  /// function.
kpeter@80
  1135
  ///
kpeter@80
  1136
  /// \sa ScaleMap
kpeter@80
  1137
  template<typename M, typename C = typename M::Value>
alpar@25
  1138
  class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
  1139
    M &_m;
kpeter@80
  1140
    C _v;
alpar@25
  1141
  public:
kpeter@559
  1142
    ///\e
kpeter@559
  1143
    typedef typename M::Key Key;
kpeter@559
  1144
    ///\e
kpeter@559
  1145
    typedef typename M::Value Value;
alpar@25
  1146
kpeter@80
  1147
    /// Constructor
alpar@25
  1148
kpeter@80
  1149
    /// Constructor.
kpeter@80
  1150
    /// \param m The undelying map.
kpeter@80
  1151
    /// \param v The constant value.
kpeter@80
  1152
    ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
kpeter@559
  1153
    ///\e
kpeter@80
  1154
    Value operator[](const Key &k) const { return _v*_m[k]; }
kpeter@559
  1155
    ///\e
kpeter@80
  1156
    void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
alpar@25
  1157
  };
alpar@25
  1158
kpeter@301
  1159
  /// Returns a \c ScaleMap class
kpeter@301
  1160
kpeter@301
  1161
  /// This function just returns a \c ScaleMap class.
kpeter@80
  1162
  ///
kpeter@80
  1163
  /// For example, if \c m is a map with \c double values and \c v is
kpeter@80
  1164
  /// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to
kpeter@80
  1165
  /// <tt>v*m[x]</tt>.
kpeter@80
  1166
  ///
kpeter@80
  1167
  /// \relates ScaleMap
kpeter@80
  1168
  template<typename M, typename C>
kpeter@80
  1169
  inline ScaleMap<M, C> scaleMap(const M &m, const C &v) {
alpar@25
  1170
    return ScaleMap<M, C>(m,v);
alpar@25
  1171
  }
alpar@25
  1172
kpeter@301
  1173
  /// Returns a \c ScaleWriteMap class
kpeter@301
  1174
kpeter@301
  1175
  /// This function just returns a \c ScaleWriteMap class.
kpeter@80
  1176
  ///
kpeter@80
  1177
  /// For example, if \c m is a map with \c double values and \c v is
kpeter@80
  1178
  /// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to
kpeter@80
  1179
  /// <tt>v*m[x]</tt>.
kpeter@80
  1180
  /// Moreover it makes also possible to write the map.
kpeter@80
  1181
  ///
kpeter@80
  1182
  /// \relates ScaleWriteMap
kpeter@80
  1183
  template<typename M, typename C>
kpeter@80
  1184
  inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) {
alpar@25
  1185
    return ScaleWriteMap<M, C>(m,v);
alpar@25
  1186
  }
alpar@25
  1187
alpar@25
  1188
kpeter@80
  1189
  /// Negative of a map
alpar@25
  1190
kpeter@82
  1191
  /// This \ref concepts::ReadMap "read-only map" returns the negative
kpeter@80
  1192
  /// of the values of the given map (using the unary \c - operator).
kpeter@80
  1193
  /// Its \c Key and \c Value are inherited from \c M.
alpar@25
  1194
  ///
kpeter@80
  1195
  /// If M::Value is \c int, \c double etc., then
kpeter@80
  1196
  /// \code
kpeter@80
  1197
  ///   NegMap<M> neg(m);
kpeter@80
  1198
  /// \endcode
kpeter@80
  1199
  /// is equivalent to
kpeter@80
  1200
  /// \code
kpeter@80
  1201
  ///   ScaleMap<M> neg(m,-1);
kpeter@80
  1202
  /// \endcode
kpeter@29
  1203
  ///
kpeter@80
  1204
  /// The simplest way of using this map is through the negMap()
kpeter@80
  1205
  /// function.
kpeter@29
  1206
  ///
kpeter@80
  1207
  /// \sa NegWriteMap
kpeter@80
  1208
  template<typename M>
alpar@25
  1209
  class NegMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
  1210
    const M& _m;
alpar@25
  1211
  public:
kpeter@559
  1212
    ///\e
kpeter@559
  1213
    typedef typename M::Key Key;
kpeter@559
  1214
    ///\e
kpeter@559
  1215
    typedef typename M::Value Value;
alpar@25
  1216
kpeter@80
  1217
    /// Constructor
kpeter@80
  1218
    NegMap(const M &m) : _m(m) {}
kpeter@559
  1219
    ///\e
kpeter@80
  1220
    Value operator[](const Key &k) const { return -_m[k]; }
alpar@25
  1221
  };
alpar@25
  1222
kpeter@80
  1223
  /// Negative of a map (read-write version)
kpeter@80
  1224
kpeter@80
  1225
  /// This \ref concepts::ReadWriteMap "read-write map" returns the
kpeter@80
  1226
  /// negative of the values of the given map (using the unary \c -
kpeter@80
  1227
  /// operator).
kpeter@80
  1228
  /// Its \c Key and \c Value are inherited from \c M.
kpeter@80
  1229
  /// It makes also possible to write the map.
kpeter@80
  1230
  ///
kpeter@80
  1231
  /// If M::Value is \c int, \c double etc., then
kpeter@80
  1232
  /// \code
kpeter@80
  1233
  ///   NegWriteMap<M> neg(m);
kpeter@80
  1234
  /// \endcode
kpeter@80
  1235
  /// is equivalent to
kpeter@80
  1236
  /// \code
kpeter@80
  1237
  ///   ScaleWriteMap<M> neg(m,-1);
kpeter@80
  1238
  /// \endcode
kpeter@80
  1239
  ///
kpeter@80
  1240
  /// The simplest way of using this map is through the negWriteMap()
kpeter@80
  1241
  /// function.
kpeter@29
  1242
  ///
kpeter@29
  1243
  /// \sa NegMap
kpeter@80
  1244
  template<typename M>
alpar@25
  1245
  class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
  1246
    M &_m;
alpar@25
  1247
  public:
kpeter@559
  1248
    ///\e
kpeter@559
  1249
    typedef typename M::Key Key;
kpeter@559
  1250
    ///\e
kpeter@559
  1251
    typedef typename M::Value Value;
alpar@25
  1252
kpeter@80
  1253
    /// Constructor
kpeter@80
  1254
    NegWriteMap(M &m) : _m(m) {}
kpeter@559
  1255
    ///\e
kpeter@80
  1256
    Value operator[](const Key &k) const { return -_m[k]; }
kpeter@559
  1257
    ///\e
kpeter@80
  1258
    void set(const Key &k, const Value &v) { _m.set(k, -v); }
alpar@25
  1259
  };
alpar@25
  1260
kpeter@301
  1261
  /// Returns a \c NegMap class
kpeter@301
  1262
kpeter@301
  1263
  /// This function just returns a \c NegMap class.
kpeter@80
  1264
  ///
kpeter@80
  1265
  /// For example, if \c m is a map with \c double values, then
kpeter@80
  1266
  /// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
kpeter@80
  1267
  ///
kpeter@80
  1268
  /// \relates NegMap
kpeter@80
  1269
  template <typename M>
alpar@25
  1270
  inline NegMap<M> negMap(const M &m) {
alpar@25
  1271
    return NegMap<M>(m);
alpar@25
  1272
  }
alpar@25
  1273
kpeter@301
  1274
  /// Returns a \c NegWriteMap class
kpeter@301
  1275
kpeter@301
  1276
  /// This function just returns a \c NegWriteMap class.
kpeter@80
  1277
  ///
kpeter@80
  1278
  /// For example, if \c m is a map with \c double values, then
kpeter@80
  1279
  /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
kpeter@80
  1280
  /// Moreover it makes also possible to write the map.
kpeter@80
  1281
  ///
kpeter@80
  1282
  /// \relates NegWriteMap
kpeter@80
  1283
  template <typename M>
kpeter@80
  1284
  inline NegWriteMap<M> negWriteMap(M &m) {
alpar@25
  1285
    return NegWriteMap<M>(m);
alpar@25
  1286
  }
alpar@25
  1287
alpar@25
  1288
kpeter@80
  1289
  /// Absolute value of a map
kpeter@80
  1290
kpeter@82
  1291
  /// This \ref concepts::ReadMap "read-only map" returns the absolute
kpeter@80
  1292
  /// value of the values of the given map.
kpeter@80
  1293
  /// Its \c Key and \c Value are inherited from \c M.
kpeter@80
  1294
  /// \c Value must be comparable to \c 0 and the unary \c -
kpeter@80
  1295
  /// operator must be defined for it, of course.
kpeter@80
  1296
  ///
kpeter@80
  1297
  /// The simplest way of using this map is through the absMap()
kpeter@80
  1298
  /// function.
kpeter@80
  1299
  template<typename M>
alpar@25
  1300
  class AbsMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
  1301
    const M &_m;
alpar@25
  1302
  public:
kpeter@559
  1303
    ///\e
kpeter@559
  1304
    typedef typename M::Key Key;
kpeter@559
  1305
    ///\e
kpeter@559
  1306
    typedef typename M::Value Value;
alpar@25
  1307
kpeter@80
  1308
    /// Constructor
kpeter@80
  1309
    AbsMap(const M &m) : _m(m) {}
kpeter@559
  1310
    ///\e
kpeter@80
  1311
    Value operator[](const Key &k) const {
kpeter@80
  1312
      Value tmp = _m[k];
alpar@25
  1313
      return tmp >= 0 ? tmp : -tmp;
alpar@25
  1314
    }
alpar@25
  1315
alpar@25
  1316
  };
alpar@25
  1317
kpeter@301
  1318
  /// Returns an \c AbsMap class
kpeter@301
  1319
kpeter@301
  1320
  /// This function just returns an \c AbsMap class.
kpeter@80
  1321
  ///
kpeter@80
  1322
  /// For example, if \c m is a map with \c double values, then
kpeter@80
  1323
  /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if
kpeter@80
  1324
  /// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is
kpeter@80
  1325
  /// negative.
kpeter@80
  1326
  ///
kpeter@80
  1327
  /// \relates AbsMap
kpeter@80
  1328
  template<typename M>
alpar@25
  1329
  inline AbsMap<M> absMap(const M &m) {
alpar@25
  1330
    return AbsMap<M>(m);
alpar@25
  1331
  }
alpar@25
  1332
kpeter@82
  1333
  /// @}
alpar@209
  1334
kpeter@82
  1335
  // Logical maps and map adaptors:
kpeter@82
  1336
kpeter@82
  1337
  /// \addtogroup maps
kpeter@82
  1338
  /// @{
kpeter@82
  1339
kpeter@82
  1340
  /// Constant \c true map.
kpeter@82
  1341
kpeter@82
  1342
  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
kpeter@82
  1343
  /// each key.
kpeter@82
  1344
  ///
kpeter@82
  1345
  /// Note that
kpeter@82
  1346
  /// \code
kpeter@82
  1347
  ///   TrueMap<K> tm;
kpeter@82
  1348
  /// \endcode
kpeter@82
  1349
  /// is equivalent to
kpeter@82
  1350
  /// \code
kpeter@82
  1351
  ///   ConstMap<K,bool> tm(true);
kpeter@82
  1352
  /// \endcode
kpeter@82
  1353
  ///
kpeter@82
  1354
  /// \sa FalseMap
kpeter@82
  1355
  /// \sa ConstMap
kpeter@82
  1356
  template <typename K>
kpeter@82
  1357
  class TrueMap : public MapBase<K, bool> {
kpeter@82
  1358
  public:
kpeter@559
  1359
    ///\e
kpeter@559
  1360
    typedef K Key;
kpeter@559
  1361
    ///\e
kpeter@559
  1362
    typedef bool Value;
kpeter@82
  1363
kpeter@82
  1364
    /// Gives back \c true.
kpeter@82
  1365
    Value operator[](const Key&) const { return true; }
kpeter@82
  1366
  };
kpeter@82
  1367
kpeter@301
  1368
  /// Returns a \c TrueMap class
kpeter@301
  1369
kpeter@301
  1370
  /// This function just returns a \c TrueMap class.
kpeter@82
  1371
  /// \relates TrueMap
kpeter@82
  1372
  template<typename K>
kpeter@82
  1373
  inline TrueMap<K> trueMap() {
kpeter@82
  1374
    return TrueMap<K>();
kpeter@82
  1375
  }
kpeter@82
  1376
kpeter@82
  1377
kpeter@82
  1378
  /// Constant \c false map.
kpeter@82
  1379
kpeter@82
  1380
  /// This \ref concepts::ReadMap "read-only map" assigns \c false to
kpeter@82
  1381
  /// each key.
kpeter@82
  1382
  ///
kpeter@82
  1383
  /// Note that
kpeter@82
  1384
  /// \code
kpeter@82
  1385
  ///   FalseMap<K> fm;
kpeter@82
  1386
  /// \endcode
kpeter@82
  1387
  /// is equivalent to
kpeter@82
  1388
  /// \code
kpeter@82
  1389
  ///   ConstMap<K,bool> fm(false);
kpeter@82
  1390
  /// \endcode
kpeter@82
  1391
  ///
kpeter@82
  1392
  /// \sa TrueMap
kpeter@82
  1393
  /// \sa ConstMap
kpeter@82
  1394
  template <typename K>
kpeter@82
  1395
  class FalseMap : public MapBase<K, bool> {
kpeter@82
  1396
  public:
kpeter@559
  1397
    ///\e
kpeter@559
  1398
    typedef K Key;
kpeter@559
  1399
    ///\e
kpeter@559
  1400
    typedef bool Value;
kpeter@82
  1401
kpeter@82
  1402
    /// Gives back \c false.
kpeter@82
  1403
    Value operator[](const Key&) const { return false; }
kpeter@82
  1404
  };
kpeter@82
  1405
kpeter@301
  1406
  /// Returns a \c FalseMap class
kpeter@301
  1407
kpeter@301
  1408
  /// This function just returns a \c FalseMap class.
kpeter@82
  1409
  /// \relates FalseMap
kpeter@82
  1410
  template<typename K>
kpeter@82
  1411
  inline FalseMap<K> falseMap() {
kpeter@82
  1412
    return FalseMap<K>();
kpeter@82
  1413
  }
kpeter@82
  1414
kpeter@82
  1415
  /// @}
kpeter@82
  1416
kpeter@82
  1417
  /// \addtogroup map_adaptors
kpeter@82
  1418
  /// @{
kpeter@82
  1419
kpeter@82
  1420
  /// Logical 'and' of two maps
kpeter@82
  1421
kpeter@82
  1422
  /// This \ref concepts::ReadMap "read-only map" returns the logical
kpeter@82
  1423
  /// 'and' of the values of the two given maps.
kpeter@82
  1424
  /// Its \c Key type is inherited from \c M1 and its \c Value type is
kpeter@82
  1425
  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
kpeter@82
  1426
  ///
kpeter@82
  1427
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@82
  1428
  /// \code
kpeter@82
  1429
  ///   AndMap<M1,M2> am(m1,m2);
kpeter@82
  1430
  /// \endcode
kpeter@82
  1431
  /// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>.
kpeter@82
  1432
  ///
kpeter@82
  1433
  /// The simplest way of using this map is through the andMap()
kpeter@82
  1434
  /// function.
kpeter@82
  1435
  ///
kpeter@82
  1436
  /// \sa OrMap
kpeter@82
  1437
  /// \sa NotMap, NotWriteMap
kpeter@82
  1438
  template<typename M1, typename M2>
kpeter@82
  1439
  class AndMap : public MapBase<typename M1::Key, bool> {
kpeter@82
  1440
    const M1 &_m1;
kpeter@82
  1441
    const M2 &_m2;
kpeter@82
  1442
  public:
kpeter@559
  1443
    ///\e
kpeter@559
  1444
    typedef typename M1::Key Key;
kpeter@559
  1445
    ///\e
kpeter@559
  1446
    typedef bool Value;
kpeter@82
  1447
kpeter@82
  1448
    /// Constructor
kpeter@82
  1449
    AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559
  1450
    ///\e
kpeter@82
  1451
    Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
kpeter@82
  1452
  };
kpeter@82
  1453
kpeter@301
  1454
  /// Returns an \c AndMap class
kpeter@301
  1455
kpeter@301
  1456
  /// This function just returns an \c AndMap class.
kpeter@82
  1457
  ///
kpeter@82
  1458
  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
kpeter@82
  1459
  /// then <tt>andMap(m1,m2)[x]</tt> will be equal to
kpeter@82
  1460
  /// <tt>m1[x]&&m2[x]</tt>.
kpeter@82
  1461
  ///
kpeter@82
  1462
  /// \relates AndMap
kpeter@82
  1463
  template<typename M1, typename M2>
kpeter@82
  1464
  inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) {
kpeter@82
  1465
    return AndMap<M1, M2>(m1,m2);
kpeter@82
  1466
  }
kpeter@82
  1467
kpeter@82
  1468
kpeter@82
  1469
  /// Logical 'or' of two maps
kpeter@82
  1470
kpeter@82
  1471
  /// This \ref concepts::ReadMap "read-only map" returns the logical
kpeter@82
  1472
  /// 'or' of the values of the two given maps.
kpeter@82
  1473
  /// Its \c Key type is inherited from \c M1 and its \c Value type is
kpeter@82
  1474
  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
kpeter@82
  1475
  ///
kpeter@82
  1476
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@82
  1477
  /// \code
kpeter@82
  1478
  ///   OrMap<M1,M2> om(m1,m2);
kpeter@82
  1479
  /// \endcode
kpeter@82
  1480
  /// <tt>om[x]</tt> will be equal to <tt>m1[x]||m2[x]</tt>.
kpeter@82
  1481
  ///
kpeter@82
  1482
  /// The simplest way of using this map is through the orMap()
kpeter@82
  1483
  /// function.
kpeter@82
  1484
  ///
kpeter@82
  1485
  /// \sa AndMap
kpeter@82
  1486
  /// \sa NotMap, NotWriteMap
kpeter@82
  1487
  template<typename M1, typename M2>
kpeter@82
  1488
  class OrMap : public MapBase<typename M1::Key, bool> {
kpeter@82
  1489
    const M1 &_m1;
kpeter@82
  1490
    const M2 &_m2;
kpeter@82
  1491
  public:
kpeter@559
  1492
    ///\e
kpeter@559
  1493
    typedef typename M1::Key Key;
kpeter@559
  1494
    ///\e
kpeter@559
  1495
    typedef bool Value;
kpeter@82
  1496
kpeter@82
  1497
    /// Constructor
kpeter@82
  1498
    OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559
  1499
    ///\e
kpeter@82
  1500
    Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
kpeter@82
  1501
  };
kpeter@82
  1502
kpeter@301
  1503
  /// Returns an \c OrMap class
kpeter@301
  1504
kpeter@301
  1505
  /// This function just returns an \c OrMap class.
kpeter@82
  1506
  ///
kpeter@82
  1507
  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
kpeter@82
  1508
  /// then <tt>orMap(m1,m2)[x]</tt> will be equal to
kpeter@82
  1509
  /// <tt>m1[x]||m2[x]</tt>.
kpeter@82
  1510
  ///
kpeter@82
  1511
  /// \relates OrMap
kpeter@82
  1512
  template<typename M1, typename M2>
kpeter@82
  1513
  inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) {
kpeter@82
  1514
    return OrMap<M1, M2>(m1,m2);
kpeter@82
  1515
  }
kpeter@82
  1516
alpar@25
  1517
kpeter@80
  1518
  /// Logical 'not' of a map
kpeter@80
  1519
kpeter@82
  1520
  /// This \ref concepts::ReadMap "read-only map" returns the logical
kpeter@80
  1521
  /// negation of the values of the given map.
kpeter@80
  1522
  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
alpar@25
  1523
  ///
kpeter@80
  1524
  /// The simplest way of using this map is through the notMap()
kpeter@80
  1525
  /// function.
alpar@25
  1526
  ///
kpeter@80
  1527
  /// \sa NotWriteMap
kpeter@80
  1528
  template <typename M>
alpar@25
  1529
  class NotMap : public MapBase<typename M::Key, bool> {
kpeter@80
  1530
    const M &_m;
alpar@25
  1531
  public:
kpeter@559
  1532
    ///\e
kpeter@559
  1533
    typedef typename M::Key Key;
kpeter@559
  1534
    ///\e
kpeter@559
  1535
    typedef bool Value;
alpar@25
  1536
alpar@25
  1537
    /// Constructor
kpeter@80
  1538
    NotMap(const M &m) : _m(m) {}
kpeter@559
  1539
    ///\e
kpeter@80
  1540
    Value operator[](const Key &k) const { return !_m[k]; }
alpar@25
  1541
  };
alpar@25
  1542
kpeter@80
  1543
  /// Logical 'not' of a map (read-write version)
kpeter@80
  1544
kpeter@80
  1545
  /// This \ref concepts::ReadWriteMap "read-write map" returns the
kpeter@80
  1546
  /// logical negation of the values of the given map.
kpeter@80
  1547
  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
kpeter@80
  1548
  /// It makes also possible to write the map. When a value is set,
kpeter@80
  1549
  /// the opposite value is set to the original map.
kpeter@29
  1550
  ///
kpeter@80
  1551
  /// The simplest way of using this map is through the notWriteMap()
kpeter@80
  1552
  /// function.
kpeter@80
  1553
  ///
kpeter@80
  1554
  /// \sa NotMap
kpeter@80
  1555
  template <typename M>
alpar@25
  1556
  class NotWriteMap : public MapBase<typename M::Key, bool> {
kpeter@80
  1557
    M &_m;
alpar@25
  1558
  public:
kpeter@559
  1559
    ///\e
kpeter@559
  1560
    typedef typename M::Key Key;
kpeter@559
  1561
    ///\e
kpeter@559
  1562
    typedef bool Value;
alpar@25
  1563
alpar@25
  1564
    /// Constructor
kpeter@80
  1565
    NotWriteMap(M &m) : _m(m) {}
kpeter@559
  1566
    ///\e
kpeter@80
  1567
    Value operator[](const Key &k) const { return !_m[k]; }
kpeter@559
  1568
    ///\e
kpeter@80
  1569
    void set(const Key &k, bool v) { _m.set(k, !v); }
alpar@25
  1570
  };
kpeter@80
  1571
kpeter@301
  1572
  /// Returns a \c NotMap class
kpeter@301
  1573
kpeter@301
  1574
  /// This function just returns a \c NotMap class.
kpeter@80
  1575
  ///
kpeter@80
  1576
  /// For example, if \c m is a map with \c bool values, then
kpeter@80
  1577
  /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
kpeter@80
  1578
  ///
kpeter@80
  1579
  /// \relates NotMap
kpeter@80
  1580
  template <typename M>
alpar@25
  1581
  inline NotMap<M> notMap(const M &m) {
alpar@25
  1582
    return NotMap<M>(m);
alpar@25
  1583
  }
kpeter@80
  1584
kpeter@301
  1585
  /// Returns a \c NotWriteMap class
kpeter@301
  1586
kpeter@301
  1587
  /// This function just returns a \c NotWriteMap class.
kpeter@80
  1588
  ///
kpeter@80
  1589
  /// For example, if \c m is a map with \c bool values, then
kpeter@80
  1590
  /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
kpeter@80
  1591
  /// Moreover it makes also possible to write the map.
kpeter@80
  1592
  ///
kpeter@80
  1593
  /// \relates NotWriteMap
kpeter@80
  1594
  template <typename M>
kpeter@80
  1595
  inline NotWriteMap<M> notWriteMap(M &m) {
alpar@25
  1596
    return NotWriteMap<M>(m);
alpar@25
  1597
  }
alpar@25
  1598
kpeter@82
  1599
kpeter@82
  1600
  /// Combination of two maps using the \c == operator
kpeter@82
  1601
kpeter@82
  1602
  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
kpeter@82
  1603
  /// the keys for which the corresponding values of the two maps are
kpeter@82
  1604
  /// equal.
kpeter@82
  1605
  /// Its \c Key type is inherited from \c M1 and its \c Value type is
kpeter@82
  1606
  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
kpeter@82
  1607
  ///
kpeter@82
  1608
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@82
  1609
  /// \code
kpeter@82
  1610
  ///   EqualMap<M1,M2> em(m1,m2);
kpeter@82
  1611
  /// \endcode
kpeter@82
  1612
  /// <tt>em[x]</tt> will be equal to <tt>m1[x]==m2[x]</tt>.
kpeter@82
  1613
  ///
kpeter@82
  1614
  /// The simplest way of using this map is through the equalMap()
kpeter@82
  1615
  /// function.
kpeter@82
  1616
  ///
kpeter@82
  1617
  /// \sa LessMap
kpeter@82
  1618
  template<typename M1, typename M2>
kpeter@82
  1619
  class EqualMap : public MapBase<typename M1::Key, bool> {
kpeter@82
  1620
    const M1 &_m1;
kpeter@82
  1621
    const M2 &_m2;
kpeter@82
  1622
  public:
kpeter@559
  1623
    ///\e
kpeter@559
  1624
    typedef typename M1::Key Key;
kpeter@559
  1625
    ///\e
kpeter@559
  1626
    typedef bool Value;
kpeter@82
  1627
kpeter@82
  1628
    /// Constructor
kpeter@82
  1629
    EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559
  1630
    ///\e
kpeter@82
  1631
    Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
kpeter@82
  1632
  };
kpeter@82
  1633
kpeter@301
  1634
  /// Returns an \c EqualMap class
kpeter@301
  1635
kpeter@301
  1636
  /// This function just returns an \c EqualMap class.
kpeter@82
  1637
  ///
kpeter@82
  1638
  /// For example, if \c m1 and \c m2 are maps with keys and values of
kpeter@82
  1639
  /// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to
kpeter@82
  1640
  /// <tt>m1[x]==m2[x]</tt>.
kpeter@82
  1641
  ///
kpeter@82
  1642
  /// \relates EqualMap
kpeter@82
  1643
  template<typename M1, typename M2>
kpeter@82
  1644
  inline EqualMap<M1, M2> equalMap(const M1 &m1, const M2 &m2) {
kpeter@82
  1645
    return EqualMap<M1, M2>(m1,m2);
kpeter@82
  1646
  }
kpeter@82
  1647
kpeter@82
  1648
kpeter@82
  1649
  /// Combination of two maps using the \c < operator
kpeter@82
  1650
kpeter@82
  1651
  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
kpeter@82
  1652
  /// the keys for which the corresponding value of the first map is
kpeter@82
  1653
  /// less then the value of the second map.
kpeter@82
  1654
  /// Its \c Key type is inherited from \c M1 and its \c Value type is
kpeter@82
  1655
  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
kpeter@82
  1656
  ///
kpeter@82
  1657
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@82
  1658
  /// \code
kpeter@82
  1659
  ///   LessMap<M1,M2> lm(m1,m2);
kpeter@82
  1660
  /// \endcode
kpeter@82
  1661
  /// <tt>lm[x]</tt> will be equal to <tt>m1[x]<m2[x]</tt>.
kpeter@82
  1662
  ///
kpeter@82
  1663
  /// The simplest way of using this map is through the lessMap()
kpeter@82
  1664
  /// function.
kpeter@82
  1665
  ///
kpeter@82
  1666
  /// \sa EqualMap
kpeter@82
  1667
  template<typename M1, typename M2>
kpeter@82
  1668
  class LessMap : public MapBase<typename M1::Key, bool> {
kpeter@82
  1669
    const M1 &_m1;
kpeter@82
  1670
    const M2 &_m2;
kpeter@82
  1671
  public:
kpeter@559
  1672
    ///\e
kpeter@559
  1673
    typedef typename M1::Key Key;
kpeter@559
  1674
    ///\e
kpeter@559
  1675
    typedef bool Value;
kpeter@82
  1676
kpeter@82
  1677
    /// Constructor
kpeter@82
  1678
    LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559
  1679
    ///\e
kpeter@82
  1680
    Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
kpeter@82
  1681
  };
kpeter@82
  1682
kpeter@301
  1683
  /// Returns an \c LessMap class
kpeter@301
  1684
kpeter@301
  1685
  /// This function just returns an \c LessMap class.
kpeter@82
  1686
  ///
kpeter@82
  1687
  /// For example, if \c m1 and \c m2 are maps with keys and values of
kpeter@82
  1688
  /// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to
kpeter@82
  1689
  /// <tt>m1[x]<m2[x]</tt>.
kpeter@82
  1690
  ///
kpeter@82
  1691
  /// \relates LessMap
kpeter@82
  1692
  template<typename M1, typename M2>
kpeter@82
  1693
  inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) {
kpeter@82
  1694
    return LessMap<M1, M2>(m1,m2);
kpeter@82
  1695
  }
kpeter@82
  1696
alpar@104
  1697
  namespace _maps_bits {
alpar@104
  1698
alpar@104
  1699
    template <typename _Iterator, typename Enable = void>
alpar@104
  1700
    struct IteratorTraits {
alpar@104
  1701
      typedef typename std::iterator_traits<_Iterator>::value_type Value;
alpar@104
  1702
    };
alpar@104
  1703
alpar@104
  1704
    template <typename _Iterator>
alpar@104
  1705
    struct IteratorTraits<_Iterator,
alpar@104
  1706
      typename exists<typename _Iterator::container_type>::type>
alpar@104
  1707
    {
alpar@104
  1708
      typedef typename _Iterator::container_type::value_type Value;
alpar@104
  1709
    };
alpar@104
  1710
alpar@104
  1711
  }
alpar@104
  1712
kpeter@314
  1713
  /// @}
kpeter@314
  1714
kpeter@314
  1715
  /// \addtogroup maps
kpeter@314
  1716
  /// @{
kpeter@314
  1717
alpar@104
  1718
  /// \brief Writable bool map for logging each \c true assigned element
alpar@104
  1719
  ///
kpeter@159
  1720
  /// A \ref concepts::WriteMap "writable" bool map for logging
alpar@104
  1721
  /// each \c true assigned element, i.e it copies subsequently each
alpar@104
  1722
  /// keys set to \c true to the given iterator.
kpeter@159
  1723
  /// The most important usage of it is storing certain nodes or arcs
kpeter@159
  1724
  /// that were marked \c true by an algorithm.
alpar@104
  1725
  ///
kpeter@159
  1726
  /// There are several algorithms that provide solutions through bool
kpeter@159
  1727
  /// maps and most of them assign \c true at most once for each key.
kpeter@159
  1728
  /// In these cases it is a natural request to store each \c true
kpeter@159
  1729
  /// assigned elements (in order of the assignment), which can be
kpeter@167
  1730
  /// easily done with LoggerBoolMap.
kpeter@159
  1731
  ///
kpeter@167
  1732
  /// The simplest way of using this map is through the loggerBoolMap()
kpeter@159
  1733
  /// function.
kpeter@159
  1734
  ///
kpeter@559
  1735
  /// \tparam IT The type of the iterator.
kpeter@559
  1736
  /// \tparam KEY The key type of the map. The default value set
kpeter@159
  1737
  /// according to the iterator type should work in most cases.
alpar@104
  1738
  ///
alpar@104
  1739
  /// \note The container of the iterator must contain enough space
kpeter@159
  1740
  /// for the elements or the iterator should be an inserter iterator.
kpeter@159
  1741
#ifdef DOXYGEN
kpeter@559
  1742
  template <typename IT, typename KEY>
kpeter@159
  1743
#else
kpeter@559
  1744
  template <typename IT,
kpeter@559
  1745
            typename KEY = typename _maps_bits::IteratorTraits<IT>::Value>
kpeter@159
  1746
#endif
kpeter@559
  1747
  class LoggerBoolMap : public MapBase<KEY, bool> {
alpar@104
  1748
  public:
kpeter@559
  1749
kpeter@559
  1750
    ///\e
kpeter@559
  1751
    typedef KEY Key;
kpeter@559
  1752
    ///\e
alpar@104
  1753
    typedef bool Value;
kpeter@559
  1754
    ///\e
kpeter@559
  1755
    typedef IT Iterator;
alpar@104
  1756
alpar@104
  1757
    /// Constructor
kpeter@167
  1758
    LoggerBoolMap(Iterator it)
alpar@104
  1759
      : _begin(it), _end(it) {}
alpar@104
  1760
alpar@104
  1761
    /// Gives back the given iterator set for the first key
alpar@104
  1762
    Iterator begin() const {
alpar@104
  1763
      return _begin;
alpar@104
  1764
    }
alpar@104
  1765
alpar@104
  1766
    /// Gives back the the 'after the last' iterator
alpar@104
  1767
    Iterator end() const {
alpar@104
  1768
      return _end;
alpar@104
  1769
    }
alpar@104
  1770
alpar@104
  1771
    /// The set function of the map
kpeter@159
  1772
    void set(const Key& key, Value value) {
alpar@104
  1773
      if (value) {
alpar@209
  1774
        *_end++ = key;
alpar@104
  1775
      }
alpar@104
  1776
    }
alpar@104
  1777
alpar@104
  1778
  private:
alpar@104
  1779
    Iterator _begin;
kpeter@159
  1780
    Iterator _end;
alpar@104
  1781
  };
alpar@209
  1782
kpeter@301
  1783
  /// Returns a \c LoggerBoolMap class
kpeter@301
  1784
kpeter@301
  1785
  /// This function just returns a \c LoggerBoolMap class.
kpeter@159
  1786
  ///
kpeter@159
  1787
  /// The most important usage of it is storing certain nodes or arcs
kpeter@159
  1788
  /// that were marked \c true by an algorithm.
kpeter@159
  1789
  /// For example it makes easier to store the nodes in the processing
kpeter@159
  1790
  /// order of Dfs algorithm, as the following examples show.
kpeter@159
  1791
  /// \code
kpeter@159
  1792
  ///   std::vector<Node> v;
kpeter@167
  1793
  ///   dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
kpeter@159
  1794
  /// \endcode
kpeter@159
  1795
  /// \code
kpeter@159
  1796
  ///   std::vector<Node> v(countNodes(g));
kpeter@167
  1797
  ///   dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
kpeter@159
  1798
  /// \endcode
kpeter@159
  1799
  ///
kpeter@159
  1800
  /// \note The container of the iterator must contain enough space
kpeter@159
  1801
  /// for the elements or the iterator should be an inserter iterator.
kpeter@159
  1802
  ///
kpeter@167
  1803
  /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
kpeter@159
  1804
  /// it cannot be used when a readable map is needed, for example as
kpeter@301
  1805
  /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms.
kpeter@159
  1806
  ///
kpeter@167
  1807
  /// \relates LoggerBoolMap
kpeter@159
  1808
  template<typename Iterator>
kpeter@167
  1809
  inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
kpeter@167
  1810
    return LoggerBoolMap<Iterator>(it);
kpeter@159
  1811
  }
alpar@104
  1812
kpeter@314
  1813
  /// @}
kpeter@314
  1814
kpeter@314
  1815
  /// \addtogroup graph_maps
kpeter@314
  1816
  /// @{
kpeter@314
  1817
kpeter@559
  1818
  /// \brief Provides an immutable and unique id for each item in a graph.
kpeter@559
  1819
  ///
kpeter@559
  1820
  /// IdMap provides a unique and immutable id for each item of the
kpeter@559
  1821
  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is 
kpeter@559
  1822
  ///  - \b unique: different items get different ids,
kpeter@559
  1823
  ///  - \b immutable: the id of an item does not change (even if you
kpeter@559
  1824
  ///    delete other nodes).
kpeter@559
  1825
  ///
kpeter@559
  1826
  /// Using this map you get access (i.e. can read) the inner id values of
kpeter@559
  1827
  /// the items stored in the graph, which is returned by the \c id()
kpeter@559
  1828
  /// function of the graph. This map can be inverted with its member
deba@220
  1829
  /// class \c InverseMap or with the \c operator() member.
deba@220
  1830
  ///
kpeter@559
  1831
  /// \tparam GR The graph type.
kpeter@559
  1832
  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
kpeter@559
  1833
  /// \c GR::Edge).
kpeter@559
  1834
  ///
alpar@572
  1835
  /// \see RangeIdMap
kpeter@559
  1836
  template <typename GR, typename K>
kpeter@559
  1837
  class IdMap : public MapBase<K, int> {
deba@220
  1838
  public:
kpeter@559
  1839
    /// The graph type of IdMap.
kpeter@559
  1840
    typedef GR Graph;
kpeter@617
  1841
    typedef GR Digraph;
kpeter@559
  1842
    /// The key type of IdMap (\c Node, \c Arc or \c Edge).
kpeter@559
  1843
    typedef K Item;
kpeter@559
  1844
    /// The key type of IdMap (\c Node, \c Arc or \c Edge).
kpeter@559
  1845
    typedef K Key;
kpeter@559
  1846
    /// The value type of IdMap.
deba@220
  1847
    typedef int Value;
deba@220
  1848
deba@220
  1849
    /// \brief Constructor.
deba@220
  1850
    ///
deba@220
  1851
    /// Constructor of the map.
deba@220
  1852
    explicit IdMap(const Graph& graph) : _graph(&graph) {}
deba@220
  1853
deba@220
  1854
    /// \brief Gives back the \e id of the item.
deba@220
  1855
    ///
deba@220
  1856
    /// Gives back the immutable and unique \e id of the item.
deba@220
  1857
    int operator[](const Item& item) const { return _graph->id(item);}
deba@220
  1858
kpeter@559
  1859
    /// \brief Gives back the \e item by its id.
deba@220
  1860
    ///
kpeter@559
  1861
    /// Gives back the \e item by its id.
deba@220
  1862
    Item operator()(int id) { return _graph->fromId(id, Item()); }
deba@220
  1863
deba@220
  1864
  private:
deba@220
  1865
    const Graph* _graph;
deba@220
  1866
deba@220
  1867
  public:
deba@220
  1868
kpeter@559
  1869
    /// \brief This class represents the inverse of its owner (IdMap).
deba@220
  1870
    ///
kpeter@559
  1871
    /// This class represents the inverse of its owner (IdMap).
deba@220
  1872
    /// \see inverse()
deba@220
  1873
    class InverseMap {
deba@220
  1874
    public:
deba@220
  1875
deba@220
  1876
      /// \brief Constructor.
deba@220
  1877
      ///
deba@220
  1878
      /// Constructor for creating an id-to-item map.
deba@220
  1879
      explicit InverseMap(const Graph& graph) : _graph(&graph) {}
deba@220
  1880
deba@220
  1881
      /// \brief Constructor.
deba@220
  1882
      ///
deba@220
  1883
      /// Constructor for creating an id-to-item map.
deba@220
  1884
      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
deba@220
  1885
deba@220
  1886
      /// \brief Gives back the given item from its id.
deba@220
  1887
      ///
deba@220
  1888
      /// Gives back the given item from its id.
deba@220
  1889
      Item operator[](int id) const { return _graph->fromId(id, Item());}
deba@220
  1890
deba@220
  1891
    private:
deba@220
  1892
      const Graph* _graph;
deba@220
  1893
    };
deba@220
  1894
deba@220
  1895
    /// \brief Gives back the inverse of the map.
deba@220
  1896
    ///
deba@220
  1897
    /// Gives back the inverse of the IdMap.
deba@220
  1898
    InverseMap inverse() const { return InverseMap(*_graph);}
deba@220
  1899
  };
deba@220
  1900
deba@220
  1901
alpar@572
  1902
  /// \brief General cross reference graph map type.
kpeter@559
  1903
kpeter@559
  1904
  /// This class provides simple invertable graph maps.
kpeter@684
  1905
  /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
kpeter@684
  1906
  /// and if a key is set to a new value, then stores it in the inverse map.
deba@220
  1907
  /// The values of the map can be accessed
deba@220
  1908
  /// with stl compatible forward iterator.
deba@220
  1909
  ///
kpeter@684
  1910
  /// This type is not reference map, so it cannot be modified with
kpeter@684
  1911
  /// the subscript operator.
kpeter@684
  1912
  ///
kpeter@559
  1913
  /// \tparam GR The graph type.
kpeter@559
  1914
  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
kpeter@559
  1915
  /// \c GR::Edge).
kpeter@559
  1916
  /// \tparam V The value type of the map.
deba@220
  1917
  ///
deba@220
  1918
  /// \see IterableValueMap
kpeter@559
  1919
  template <typename GR, typename K, typename V>
alpar@572
  1920
  class CrossRefMap
kpeter@559
  1921
    : protected ItemSetTraits<GR, K>::template Map<V>::Type {
deba@220
  1922
  private:
deba@220
  1923
kpeter@559
  1924
    typedef typename ItemSetTraits<GR, K>::
kpeter@559
  1925
      template Map<V>::Type Map;
kpeter@559
  1926
kpeter@684
  1927
    typedef std::multimap<V, K> Container;
deba@220
  1928
    Container _inv_map;
deba@220
  1929
deba@220
  1930
  public:
deba@220
  1931
alpar@572
  1932
    /// The graph type of CrossRefMap.
kpeter@559
  1933
    typedef GR Graph;
kpeter@617
  1934
    typedef GR Digraph;
alpar@572
  1935
    /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
kpeter@559
  1936
    typedef K Item;
alpar@572
  1937
    /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
kpeter@559
  1938
    typedef K Key;
alpar@572
  1939
    /// The value type of CrossRefMap.
kpeter@559
  1940
    typedef V Value;
deba@220
  1941
deba@220
  1942
    /// \brief Constructor.
deba@220
  1943
    ///
alpar@572
  1944
    /// Construct a new CrossRefMap for the given graph.
alpar@572
  1945
    explicit CrossRefMap(const Graph& graph) : Map(graph) {}
deba@220
  1946
deba@220
  1947
    /// \brief Forward iterator for values.
deba@220
  1948
    ///
deba@220
  1949
    /// This iterator is an stl compatible forward
deba@220
  1950
    /// iterator on the values of the map. The values can
kpeter@559
  1951
    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
kpeter@684
  1952
    /// They are considered with multiplicity, so each value is
kpeter@684
  1953
    /// traversed for each item it is assigned to.
deba@220
  1954
    class ValueIterator
deba@220
  1955
      : public std::iterator<std::forward_iterator_tag, Value> {
alpar@572
  1956
      friend class CrossRefMap;
deba@220
  1957
    private:
deba@220
  1958
      ValueIterator(typename Container::const_iterator _it)
deba@220
  1959
        : it(_it) {}
deba@220
  1960
    public:
deba@220
  1961
deba@220
  1962
      ValueIterator() {}
deba@220
  1963
deba@220
  1964
      ValueIterator& operator++() { ++it; return *this; }
deba@220
  1965
      ValueIterator operator++(int) {
deba@220
  1966
        ValueIterator tmp(*this);
deba@220
  1967
        operator++();
deba@220
  1968
        return tmp;
deba@220
  1969
      }
deba@220
  1970
deba@220
  1971
      const Value& operator*() const { return it->first; }
deba@220
  1972
      const Value* operator->() const { return &(it->first); }
deba@220
  1973
deba@220
  1974
      bool operator==(ValueIterator jt) const { return it == jt.it; }
deba@220
  1975
      bool operator!=(ValueIterator jt) const { return it != jt.it; }
deba@220
  1976
deba@220
  1977
    private:
deba@220
  1978
      typename Container::const_iterator it;
deba@220
  1979
    };
deba@220
  1980
deba@220
  1981
    /// \brief Returns an iterator to the first value.
deba@220
  1982
    ///
deba@220
  1983
    /// Returns an stl compatible iterator to the
deba@220
  1984
    /// first value of the map. The values of the
kpeter@559
  1985
    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
deba@220
  1986
    /// range.
deba@220
  1987
    ValueIterator beginValue() const {
deba@220
  1988
      return ValueIterator(_inv_map.begin());
deba@220
  1989
    }
deba@220
  1990
deba@220
  1991
    /// \brief Returns an iterator after the last value.
deba@220
  1992
    ///
deba@220
  1993
    /// Returns an stl compatible iterator after the
deba@220
  1994
    /// last value of the map. The values of the
kpeter@559
  1995
    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
deba@220
  1996
    /// range.
deba@220
  1997
    ValueIterator endValue() const {
deba@220
  1998
      return ValueIterator(_inv_map.end());
deba@220
  1999
    }
deba@220
  2000
kpeter@559
  2001
    /// \brief Sets the value associated with the given key.
deba@220
  2002
    ///
kpeter@559
  2003
    /// Sets the value associated with the given key.
deba@220
  2004
    void set(const Key& key, const Value& val) {
deba@220
  2005
      Value oldval = Map::operator[](key);
kpeter@684
  2006
      typename Container::iterator it;
kpeter@684
  2007
      for (it = _inv_map.equal_range(oldval).first;
kpeter@684
  2008
           it != _inv_map.equal_range(oldval).second; ++it) {
kpeter@684
  2009
        if (it->second == key) {
kpeter@684
  2010
          _inv_map.erase(it);
kpeter@684
  2011
          break;
kpeter@684
  2012
        }
deba@220
  2013
      }
kpeter@684
  2014
      _inv_map.insert(std::make_pair(val, key));
deba@220
  2015
      Map::set(key, val);
deba@220
  2016
    }
deba@220
  2017
kpeter@559
  2018
    /// \brief Returns the value associated with the given key.
deba@220
  2019
    ///
kpeter@559
  2020
    /// Returns the value associated with the given key.
deba@220
  2021
    typename MapTraits<Map>::ConstReturnValue
deba@220
  2022
    operator[](const Key& key) const {
deba@220
  2023
      return Map::operator[](key);
deba@220
  2024
    }
deba@220
  2025
kpeter@684
  2026
    /// \brief Gives back an item by its value.
deba@220
  2027
    ///
kpeter@684
  2028
    /// This function gives back an item that is assigned to
kpeter@684
  2029
    /// the given value or \c INVALID if no such item exists.
kpeter@684
  2030
    /// If there are more items with the same associated value,
kpeter@684
  2031
    /// only one of them is returned.
kpeter@684
  2032
    Key operator()(const Value& val) const {
kpeter@684
  2033
      typename Container::const_iterator it = _inv_map.find(val);
deba@220
  2034
      return it != _inv_map.end() ? it->second : INVALID;
deba@220
  2035
    }
deba@220
  2036
deba@220
  2037
  protected:
deba@220
  2038
kpeter@559
  2039
    /// \brief Erase the key from the map and the inverse map.
deba@220
  2040
    ///
kpeter@559
  2041
    /// Erase the key from the map and the inverse map. It is called by the
deba@220
  2042
    /// \c AlterationNotifier.
deba@220
  2043
    virtual void erase(const Key& key) {
deba@220
  2044
      Value val = Map::operator[](key);
kpeter@684
  2045
      typename Container::iterator it;
kpeter@684
  2046
      for (it = _inv_map.equal_range(val).first;
kpeter@684
  2047
           it != _inv_map.equal_range(val).second; ++it) {
kpeter@684
  2048
        if (it->second == key) {
kpeter@684
  2049
          _inv_map.erase(it);
kpeter@684
  2050
          break;
kpeter@684
  2051
        }
deba@220
  2052
      }
deba@220
  2053
      Map::erase(key);
deba@220
  2054
    }
deba@220
  2055
kpeter@559
  2056
    /// \brief Erase more keys from the map and the inverse map.
deba@220
  2057
    ///
kpeter@559
  2058
    /// Erase more keys from the map and the inverse map. It is called by the
deba@220
  2059
    /// \c AlterationNotifier.
deba@220
  2060
    virtual void erase(const std::vector<Key>& keys) {
deba@220
  2061
      for (int i = 0; i < int(keys.size()); ++i) {
deba@220
  2062
        Value val = Map::operator[](keys[i]);
kpeter@684
  2063
        typename Container::iterator it;
kpeter@684
  2064
        for (it = _inv_map.equal_range(val).first;
kpeter@684
  2065
             it != _inv_map.equal_range(val).second; ++it) {
kpeter@684
  2066
          if (it->second == keys[i]) {
kpeter@684
  2067
            _inv_map.erase(it);
kpeter@684
  2068
            break;
kpeter@684
  2069
          }
deba@220
  2070
        }
deba@220
  2071
      }
deba@220
  2072
      Map::erase(keys);
deba@220
  2073
    }
deba@220
  2074
kpeter@559
  2075
    /// \brief Clear the keys from the map and the inverse map.
deba@220
  2076
    ///
kpeter@559
  2077
    /// Clear the keys from the map and the inverse map. It is called by the
deba@220
  2078
    /// \c AlterationNotifier.
deba@220
  2079
    virtual void clear() {
deba@220
  2080
      _inv_map.clear();
deba@220
  2081
      Map::clear();
deba@220
  2082
    }
deba@220
  2083
deba@220
  2084
  public:
deba@220
  2085
deba@220
  2086
    /// \brief The inverse map type.
deba@220
  2087
    ///
deba@220
  2088
    /// The inverse of this map. The subscript operator of the map
kpeter@559
  2089
    /// gives back the item that was last assigned to the value.
deba@220
  2090
    class InverseMap {
deba@220
  2091
    public:
kpeter@559
  2092
      /// \brief Constructor
deba@220
  2093
      ///
deba@220
  2094
      /// Constructor of the InverseMap.
alpar@572
  2095
      explicit InverseMap(const CrossRefMap& inverted)
deba@220
  2096
        : _inverted(inverted) {}
deba@220
  2097
deba@220
  2098
      /// The value type of the InverseMap.
alpar@572
  2099
      typedef typename CrossRefMap::Key Value;
deba@220
  2100
      /// The key type of the InverseMap.
alpar@572
  2101
      typedef typename CrossRefMap::Value Key;
deba@220
  2102
deba@220
  2103
      /// \brief Subscript operator.
deba@220
  2104
      ///
kpeter@684
  2105
      /// Subscript operator. It gives back an item
kpeter@684
  2106
      /// that is assigned to the given value or \c INVALID
kpeter@684
  2107
      /// if no such item exists.
deba@220
  2108
      Value operator[](const Key& key) const {
deba@220
  2109
        return _inverted(key);
deba@220
  2110
      }
deba@220
  2111
deba@220
  2112
    private:
alpar@572
  2113
      const CrossRefMap& _inverted;
deba@220
  2114
    };
deba@220
  2115
kpeter@559
  2116
    /// \brief It gives back the read-only inverse map.
deba@220
  2117
    ///
kpeter@559
  2118
    /// It gives back the read-only inverse map.
deba@220
  2119
    InverseMap inverse() const {
deba@220
  2120
      return InverseMap(*this);
deba@220
  2121
    }
deba@220
  2122
deba@220
  2123
  };
deba@220
  2124
alpar@572
  2125
  /// \brief Provides continuous and unique ID for the
alpar@572
  2126
  /// items of a graph.
deba@220
  2127
  ///
alpar@572
  2128
  /// RangeIdMap provides a unique and continuous
alpar@572
  2129
  /// ID for each item of a given type (\c Node, \c Arc or
kpeter@559
  2130
  /// \c Edge) in a graph. This id is
kpeter@559
  2131
  ///  - \b unique: different items get different ids,
kpeter@559
  2132
  ///  - \b continuous: the range of the ids is the set of integers
kpeter@559
  2133
  ///    between 0 and \c n-1, where \c n is the number of the items of
alpar@572
  2134
  ///    this type (\c Node, \c Arc or \c Edge).
alpar@572
  2135
  ///  - So, the ids can change when deleting an item of the same type.
deba@220
  2136
  ///
kpeter@559
  2137
  /// Thus this id is not (necessarily) the same as what can get using
kpeter@559
  2138
  /// the \c id() function of the graph or \ref IdMap.
kpeter@559
  2139
  /// This map can be inverted with its member class \c InverseMap,
kpeter@559
  2140
  /// or with the \c operator() member.
kpeter@559
  2141
  ///
kpeter@559
  2142
  /// \tparam GR The graph type.
kpeter@559
  2143
  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
kpeter@559
  2144
  /// \c GR::Edge).
kpeter@559
  2145
  ///
kpeter@559
  2146
  /// \see IdMap
kpeter@559
  2147
  template <typename GR, typename K>
alpar@572
  2148
  class RangeIdMap
kpeter@559
  2149
    : protected ItemSetTraits<GR, K>::template Map<int>::Type {
kpeter@559
  2150
kpeter@559
  2151
    typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Map;
deba@220
  2152
deba@220
  2153
  public:
alpar@572
  2154
    /// The graph type of RangeIdMap.
kpeter@559
  2155
    typedef GR Graph;
kpeter@617
  2156
    typedef GR Digraph;
alpar@572
  2157
    /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge).
kpeter@559
  2158
    typedef K Item;
alpar@572
  2159
    /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge).
kpeter@559
  2160
    typedef K Key;
alpar@572
  2161
    /// The value type of RangeIdMap.
kpeter@559
  2162
    typedef int Value;
deba@220
  2163
deba@220
  2164
    /// \brief Constructor.
deba@220
  2165
    ///
alpar@572
  2166
    /// Constructor.
alpar@572
  2167
    explicit RangeIdMap(const Graph& gr) : Map(gr) {
deba@220
  2168
      Item it;
deba@220
  2169
      const typename Map::Notifier* nf = Map::notifier();
deba@220
  2170
      for (nf->first(it); it != INVALID; nf->next(it)) {
deba@220
  2171
        Map::set(it, _inv_map.size());
deba@220
  2172
        _inv_map.push_back(it);
deba@220
  2173
      }
deba@220
  2174
    }
deba@220
  2175
deba@220
  2176
  protected:
deba@220
  2177
kpeter@559
  2178
    /// \brief Adds a new key to the map.
deba@220
  2179
    ///
deba@220
  2180
    /// Add a new key to the map. It is called by the
deba@220
  2181
    /// \c AlterationNotifier.
deba@220
  2182
    virtual void add(const Item& item) {
deba@220
  2183
      Map::add(item);
deba@220
  2184
      Map::set(item, _inv_map.size());
deba@220
  2185
      _inv_map.push_back(item);
deba@220
  2186
    }
deba@220
  2187
deba@220
  2188
    /// \brief Add more new keys to the map.
deba@220
  2189
    ///
deba@220
  2190
    /// Add more new keys to the map. It is called by the
deba@220
  2191
    /// \c AlterationNotifier.
deba@220
  2192
    virtual void add(const std::vector<Item>& items) {
deba@220
  2193
      Map::add(items);
deba@220
  2194
      for (int i = 0; i < int(items.size()); ++i) {
deba@220
  2195
        Map::set(items[i], _inv_map.size());
deba@220
  2196
        _inv_map.push_back(items[i]);
deba@220
  2197
      }
deba@220
  2198
    }
deba@220
  2199
deba@220
  2200
    /// \brief Erase the key from the map.
deba@220
  2201
    ///
deba@220
  2202
    /// Erase the key from the map. It is called by the
deba@220
  2203
    /// \c AlterationNotifier.
deba@220
  2204
    virtual void erase(const Item& item) {
deba@220
  2205
      Map::set(_inv_map.back(), Map::operator[](item));
deba@220
  2206
      _inv_map[Map::operator[](item)] = _inv_map.back();
deba@220
  2207
      _inv_map.pop_back();
deba@220
  2208
      Map::erase(item);
deba@220
  2209
    }
deba@220
  2210
deba@220
  2211
    /// \brief Erase more keys from the map.
deba@220
  2212
    ///
deba@220
  2213
    /// Erase more keys from the map. It is called by the
deba@220
  2214
    /// \c AlterationNotifier.
deba@220
  2215
    virtual void erase(const std::vector<Item>& items) {
deba@220
  2216
      for (int i = 0; i < int(items.size()); ++i) {
deba@220
  2217
        Map::set(_inv_map.back(), Map::operator[](items[i]));
deba@220
  2218
        _inv_map[Map::operator[](items[i])] = _inv_map.back();
deba@220
  2219
        _inv_map.pop_back();
deba@220
  2220
      }
deba@220
  2221
      Map::erase(items);
deba@220
  2222
    }
deba@220
  2223
deba@220
  2224
    /// \brief Build the unique map.
deba@220
  2225
    ///
deba@220
  2226
    /// Build the unique map. It is called by the
deba@220
  2227
    /// \c AlterationNotifier.
deba@220
  2228
    virtual void build() {
deba@220
  2229
      Map::build();
deba@220
  2230
      Item it;
deba@220
  2231
      const typename Map::Notifier* nf = Map::notifier();
deba@220
  2232
      for (nf->first(it); it != INVALID; nf->next(it)) {
deba@220
  2233
        Map::set(it, _inv_map.size());
deba@220
  2234
        _inv_map.push_back(it);
deba@220
  2235
      }
deba@220
  2236
    }
deba@220
  2237
deba@220
  2238
    /// \brief Clear the keys from the map.
deba@220
  2239
    ///
deba@220
  2240
    /// Clear the keys from the map. It is called by the
deba@220
  2241
    /// \c AlterationNotifier.
deba@220
  2242
    virtual void clear() {
deba@220
  2243
      _inv_map.clear();
deba@220
  2244
      Map::clear();
deba@220
  2245
    }
deba@220
  2246
deba@220
  2247
  public:
deba@220
  2248
deba@220
  2249
    /// \brief Returns the maximal value plus one.
deba@220
  2250
    ///
deba@220
  2251
    /// Returns the maximal value plus one in the map.
deba@220
  2252
    unsigned int size() const {
deba@220
  2253
      return _inv_map.size();
deba@220
  2254
    }
deba@220
  2255
deba@220
  2256
    /// \brief Swaps the position of the two items in the map.
deba@220
  2257
    ///
deba@220
  2258
    /// Swaps the position of the two items in the map.
deba@220
  2259
    void swap(const Item& p, const Item& q) {
deba@220
  2260
      int pi = Map::operator[](p);
deba@220
  2261
      int qi = Map::operator[](q);
deba@220
  2262
      Map::set(p, qi);
deba@220
  2263
      _inv_map[qi] = p;
deba@220
  2264
      Map::set(q, pi);
deba@220
  2265
      _inv_map[pi] = q;
deba@220
  2266
    }
deba@220
  2267
alpar@572
  2268
    /// \brief Gives back the \e RangeId of the item
deba@220
  2269
    ///
alpar@572
  2270
    /// Gives back the \e RangeId of the item.
deba@220
  2271
    int operator[](const Item& item) const {
deba@220
  2272
      return Map::operator[](item);
deba@220
  2273
    }
deba@220
  2274
alpar@572
  2275
    /// \brief Gives back the item belonging to a \e RangeId
alpar@572
  2276
    /// 
alpar@572
  2277
    /// Gives back the item belonging to a \e RangeId.
deba@220
  2278
    Item operator()(int id) const {
deba@220
  2279
      return _inv_map[id];
deba@220
  2280
    }
deba@220
  2281
deba@220
  2282
  private:
deba@220
  2283
deba@220
  2284
    typedef std::vector<Item> Container;
deba@220
  2285
    Container _inv_map;
deba@220
  2286
deba@220
  2287
  public:
kpeter@559
  2288
alpar@572
  2289
    /// \brief The inverse map type of RangeIdMap.
deba@220
  2290
    ///
alpar@572
  2291
    /// The inverse map type of RangeIdMap.
deba@220
  2292
    class InverseMap {
deba@220
  2293
    public:
kpeter@559
  2294
      /// \brief Constructor
deba@220
  2295
      ///
deba@220
  2296
      /// Constructor of the InverseMap.
alpar@572
  2297
      explicit InverseMap(const RangeIdMap& inverted)
deba@220
  2298
        : _inverted(inverted) {}
deba@220
  2299
deba@220
  2300
deba@220
  2301
      /// The value type of the InverseMap.
alpar@572
  2302
      typedef typename RangeIdMap::Key Value;
deba@220
  2303
      /// The key type of the InverseMap.
alpar@572
  2304
      typedef typename RangeIdMap::Value Key;
deba@220
  2305
deba@220
  2306
      /// \brief Subscript operator.
deba@220
  2307
      ///
deba@220
  2308
      /// Subscript operator. It gives back the item
kpeter@559
  2309
      /// that the descriptor currently belongs to.
deba@220
  2310
      Value operator[](const Key& key) const {
deba@220
  2311
        return _inverted(key);
deba@220
  2312
      }
deba@220
  2313
deba@220
  2314
      /// \brief Size of the map.
deba@220
  2315
      ///
deba@220
  2316
      /// Returns the size of the map.
deba@220
  2317
      unsigned int size() const {
deba@220
  2318
        return _inverted.size();
deba@220
  2319
      }
deba@220
  2320
deba@220
  2321
    private:
alpar@572
  2322
      const RangeIdMap& _inverted;
deba@220
  2323
    };
deba@220
  2324
deba@220
  2325
    /// \brief Gives back the inverse of the map.
deba@220
  2326
    ///
deba@220
  2327
    /// Gives back the inverse of the map.
deba@220
  2328
    const InverseMap inverse() const {
deba@220
  2329
      return InverseMap(*this);
deba@220
  2330
    }
deba@220
  2331
  };
deba@220
  2332
kpeter@559
  2333
  /// \brief Map of the source nodes of arcs in a digraph.
deba@220
  2334
  ///
kpeter@559
  2335
  /// SourceMap provides access for the source node of each arc in a digraph,
kpeter@559
  2336
  /// which is returned by the \c source() function of the digraph.
kpeter@559
  2337
  /// \tparam GR The digraph type.
deba@220
  2338
  /// \see TargetMap
kpeter@559
  2339
  template <typename GR>
deba@220
  2340
  class SourceMap {
deba@220
  2341
  public:
deba@220
  2342
kpeter@559
  2343
    ///\e
kpeter@559
  2344
    typedef typename GR::Arc Key;
kpeter@559
  2345
    ///\e
kpeter@559
  2346
    typedef typename GR::Node Value;
deba@220
  2347
deba@220
  2348
    /// \brief Constructor
deba@220
  2349
    ///
kpeter@559
  2350
    /// Constructor.
kpeter@313
  2351
    /// \param digraph The digraph that the map belongs to.
kpeter@559
  2352
    explicit SourceMap(const GR& digraph) : _graph(digraph) {}
kpeter@559
  2353
kpeter@559
  2354
    /// \brief Returns the source node of the given arc.
deba@220
  2355
    ///
kpeter@559
  2356
    /// Returns the source node of the given arc.
deba@220
  2357
    Value operator[](const Key& arc) const {
kpeter@559
  2358
      return _graph.source(arc);
deba@220
  2359
    }
deba@220
  2360
deba@220
  2361
  private:
kpeter@559
  2362
    const GR& _graph;
deba@220
  2363
  };
deba@220
  2364
kpeter@301
  2365
  /// \brief Returns a \c SourceMap class.
deba@220
  2366
  ///
kpeter@301
  2367
  /// This function just returns an \c SourceMap class.
deba@220
  2368
  /// \relates SourceMap
kpeter@559
  2369
  template <typename GR>
kpeter@559
  2370
  inline SourceMap<GR> sourceMap(const GR& graph) {
kpeter@559
  2371
    return SourceMap<GR>(graph);
deba@220
  2372
  }
deba@220
  2373
kpeter@559
  2374
  /// \brief Map of the target nodes of arcs in a digraph.
deba@220
  2375
  ///
kpeter@559
  2376
  /// TargetMap provides access for the target node of each arc in a digraph,
kpeter@559
  2377
  /// which is returned by the \c target() function of the digraph.
kpeter@559
  2378
  /// \tparam GR The digraph type.
deba@220
  2379
  /// \see SourceMap
kpeter@559
  2380
  template <typename GR>
deba@220
  2381
  class TargetMap {
deba@220
  2382
  public:
deba@220
  2383
kpeter@559
  2384
    ///\e
kpeter@559
  2385
    typedef typename GR::Arc Key;
kpeter@559
  2386
    ///\e
kpeter@559
  2387
    typedef typename GR::Node Value;
deba@220
  2388
deba@220
  2389
    /// \brief Constructor
deba@220
  2390
    ///
kpeter@559
  2391
    /// Constructor.
kpeter@313
  2392
    /// \param digraph The digraph that the map belongs to.
kpeter@559
  2393
    explicit TargetMap(const GR& digraph) : _graph(digraph) {}
kpeter@559
  2394
kpeter@559
  2395
    /// \brief Returns the target node of the given arc.
deba@220
  2396
    ///
kpeter@559
  2397
    /// Returns the target node of the given arc.
deba@220
  2398
    Value operator[](const Key& e) const {
kpeter@559
  2399
      return _graph.target(e);
deba@220
  2400
    }
deba@220
  2401
deba@220
  2402
  private:
kpeter@559
  2403
    const GR& _graph;
deba@220
  2404
  };
deba@220
  2405
kpeter@301
  2406
  /// \brief Returns a \c TargetMap class.
deba@220
  2407
  ///
kpeter@301
  2408
  /// This function just returns a \c TargetMap class.
deba@220
  2409
  /// \relates TargetMap
kpeter@559
  2410
  template <typename GR>
kpeter@559
  2411
  inline TargetMap<GR> targetMap(const GR& graph) {
kpeter@559
  2412
    return TargetMap<GR>(graph);
deba@220
  2413
  }
deba@220
  2414
kpeter@559
  2415
  /// \brief Map of the "forward" directed arc view of edges in a graph.
deba@220
  2416
  ///
kpeter@559
  2417
  /// ForwardMap provides access for the "forward" directed arc view of
kpeter@559
  2418
  /// each edge in a graph, which is returned by the \c direct() function
kpeter@559
  2419
  /// of the graph with \c true parameter.
kpeter@559
  2420
  /// \tparam GR The graph type.
deba@220
  2421
  /// \see BackwardMap
kpeter@559
  2422
  template <typename GR>
deba@220
  2423
  class ForwardMap {
deba@220
  2424
  public:
deba@220
  2425
kpeter@559
  2426
    typedef typename GR::Arc Value;
kpeter@559
  2427
    typedef typename GR::Edge Key;
deba@220
  2428
deba@220
  2429
    /// \brief Constructor
deba@220
  2430
    ///
kpeter@559
  2431
    /// Constructor.
kpeter@313
  2432
    /// \param graph The graph that the map belongs to.
kpeter@559
  2433
    explicit ForwardMap(const GR& graph) : _graph(graph) {}
kpeter@559
  2434
kpeter@559
  2435
    /// \brief Returns the "forward" directed arc view of the given edge.
deba@220
  2436
    ///
kpeter@559
  2437
    /// Returns the "forward" directed arc view of the given edge.
deba@220
  2438
    Value operator[](const Key& key) const {
deba@220
  2439
      return _graph.direct(key, true);
deba@220
  2440
    }
deba@220
  2441
deba@220
  2442
  private:
kpeter@559
  2443
    const GR& _graph;
deba@220
  2444
  };
deba@220
  2445
kpeter@301
  2446
  /// \brief Returns a \c ForwardMap class.
deba@220
  2447
  ///
kpeter@301
  2448
  /// This function just returns an \c ForwardMap class.
deba@220
  2449
  /// \relates ForwardMap
kpeter@559
  2450
  template <typename GR>
kpeter@559
  2451
  inline ForwardMap<GR> forwardMap(const GR& graph) {
kpeter@559
  2452
    return ForwardMap<GR>(graph);
deba@220
  2453
  }
deba@220
  2454
kpeter@559
  2455
  /// \brief Map of the "backward" directed arc view of edges in a graph.
deba@220
  2456
  ///
kpeter@559
  2457
  /// BackwardMap provides access for the "backward" directed arc view of
kpeter@559
  2458
  /// each edge in a graph, which is returned by the \c direct() function
kpeter@559
  2459
  /// of the graph with \c false parameter.
kpeter@559
  2460
  /// \tparam GR The graph type.
deba@220
  2461
  /// \see ForwardMap
kpeter@559
  2462
  template <typename GR>
deba@220
  2463
  class BackwardMap {
deba@220
  2464
  public:
deba@220
  2465
kpeter@559
  2466
    typedef typename GR::Arc Value;
kpeter@559
  2467
    typedef typename GR::Edge Key;
deba@220
  2468
deba@220
  2469
    /// \brief Constructor
deba@220
  2470
    ///
kpeter@559
  2471
    /// Constructor.
kpeter@313
  2472
    /// \param graph The graph that the map belongs to.
kpeter@559
  2473
    explicit BackwardMap(const GR& graph) : _graph(graph) {}
kpeter@559
  2474
kpeter@559
  2475
    /// \brief Returns the "backward" directed arc view of the given edge.
deba@220
  2476
    ///
kpeter@559
  2477
    /// Returns the "backward" directed arc view of the given edge.
deba@220
  2478
    Value operator[](const Key& key) const {
deba@220
  2479
      return _graph.direct(key, false);
deba@220
  2480
    }
deba@220
  2481
deba@220
  2482
  private:
kpeter@559
  2483
    const GR& _graph;
deba@220
  2484
  };
deba@220
  2485
kpeter@301
  2486
  /// \brief Returns a \c BackwardMap class
kpeter@301
  2487
kpeter@301
  2488
  /// This function just returns a \c BackwardMap class.
deba@220
  2489
  /// \relates BackwardMap
kpeter@559
  2490
  template <typename GR>
kpeter@559
  2491
  inline BackwardMap<GR> backwardMap(const GR& graph) {
kpeter@559
  2492
    return BackwardMap<GR>(graph);
deba@220
  2493
  }
deba@220
  2494
kpeter@559
  2495
  /// \brief Map of the in-degrees of nodes in a digraph.
deba@220
  2496
  ///
deba@220
  2497
  /// This map returns the in-degree of a node. Once it is constructed,
kpeter@559
  2498
  /// the degrees are stored in a standard \c NodeMap, so each query is done
deba@220
  2499
  /// in constant time. On the other hand, the values are updated automatically
deba@220
  2500
  /// whenever the digraph changes.
deba@220
  2501
  ///
kpeter@559
  2502
  /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
kpeter@559
  2503
  /// may provide alternative ways to modify the digraph.
kpeter@559
  2504
  /// The correct behavior of InDegMap is not guarantied if these additional
kpeter@559
  2505
  /// features are used. For example the functions
kpeter@559
  2506
  /// \ref ListDigraph::changeSource() "changeSource()",
deba@220
  2507
  /// \ref ListDigraph::changeTarget() "changeTarget()" and
deba@220
  2508
  /// \ref ListDigraph::reverseArc() "reverseArc()"
deba@220
  2509
  /// of \ref ListDigraph will \e not update the degree values correctly.
deba@220
  2510
  ///
deba@220
  2511
  /// \sa OutDegMap
kpeter@559
  2512
  template <typename GR>
deba@220
  2513
  class InDegMap
kpeter@559
  2514
    : protected ItemSetTraits<GR, typename GR::Arc>
deba@220
  2515
      ::ItemNotifier::ObserverBase {
deba@220
  2516
deba@220
  2517
  public:
kpeter@559
  2518
    
kpeter@617
  2519
    /// The graph type of InDegMap
kpeter@617
  2520
    typedef GR Graph;
kpeter@559
  2521
    typedef GR Digraph;
kpeter@559
  2522
    /// The key type
kpeter@559
  2523
    typedef typename Digraph::Node Key;
kpeter@559
  2524
    /// The value type
deba@220
  2525
    typedef int Value;
deba@220
  2526
deba@220
  2527
    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
deba@220
  2528
    ::ItemNotifier::ObserverBase Parent;
deba@220
  2529
deba@220
  2530
  private:
deba@220
  2531
deba@220
  2532
    class AutoNodeMap
deba@220
  2533
      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
deba@220
  2534
    public:
deba@220
  2535
deba@220
  2536
      typedef typename ItemSetTraits<Digraph, Key>::
deba@220
  2537
      template Map<int>::Type Parent;
deba@220
  2538
deba@220
  2539
      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
deba@220
  2540
deba@220
  2541
      virtual void add(const Key& key) {
deba@220
  2542
        Parent::add(key);
deba@220
  2543
        Parent::set(key, 0);
deba@220
  2544
      }
deba@220
  2545
deba@220
  2546
      virtual void add(const std::vector<Key>& keys) {
deba@220
  2547
        Parent::add(keys);
deba@220
  2548
        for (int i = 0; i < int(keys.size()); ++i) {
deba@220
  2549
          Parent::set(keys[i], 0);
deba@220
  2550
        }
deba@220
  2551
      }
deba@220
  2552
deba@220
  2553
      virtual void build() {
deba@220
  2554
        Parent::build();
deba@220
  2555
        Key it;
deba@220
  2556
        typename Parent::Notifier* nf = Parent::notifier();
deba@220
  2557
        for (nf->first(it); it != INVALID; nf->next(it)) {
deba@220
  2558
          Parent::set(it, 0);
deba@220
  2559
        }
deba@220
  2560
      }
deba@220
  2561
    };
deba@220
  2562
deba@220
  2563
  public:
deba@220
  2564
deba@220
  2565
    /// \brief Constructor.
deba@220
  2566
    ///
kpeter@559
  2567
    /// Constructor for creating an in-degree map.
kpeter@559
  2568
    explicit InDegMap(const Digraph& graph)
kpeter@559
  2569
      : _digraph(graph), _deg(graph) {
deba@220
  2570
      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
deba@220
  2571
deba@220
  2572
      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220
  2573
        _deg[it] = countInArcs(_digraph, it);
deba@220
  2574
      }
deba@220
  2575
    }
deba@220
  2576
kpeter@559
  2577
    /// \brief Gives back the in-degree of a Node.
kpeter@559
  2578
    ///
deba@220
  2579
    /// Gives back the in-degree of a Node.
deba@220
  2580
    int operator[](const Key& key) const {
deba@220
  2581
      return _deg[key];
deba@220
  2582
    }
deba@220
  2583
deba@220
  2584
  protected:
deba@220
  2585
deba@220
  2586
    typedef typename Digraph::Arc Arc;
deba@220
  2587
deba@220
  2588
    virtual void add(const Arc& arc) {
deba@220
  2589
      ++_deg[_digraph.target(arc)];
deba@220
  2590
    }
deba@220
  2591
deba@220
  2592
    virtual void add(const std::vector<Arc>& arcs) {
deba@220
  2593
      for (int i = 0; i < int(arcs.size()); ++i) {
deba@220
  2594
        ++_deg[_digraph.target(arcs[i])];
deba@220
  2595
      }
deba@220
  2596
    }
deba@220
  2597
deba@220
  2598
    virtual void erase(const Arc& arc) {
deba@220
  2599
      --_deg[_digraph.target(arc)];
deba@220
  2600
    }
deba@220
  2601
deba@220
  2602
    virtual void erase(const std::vector<Arc>& arcs) {
deba@220
  2603
      for (int i = 0; i < int(arcs.size()); ++i) {
deba@220
  2604
        --_deg[_digraph.target(arcs[i])];
deba@220
  2605
      }
deba@220
  2606
    }
deba@220
  2607
deba@220
  2608
    virtual void build() {
deba@220
  2609
      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220
  2610
        _deg[it] = countInArcs(_digraph, it);
deba@220
  2611
      }
deba@220
  2612
    }
deba@220
  2613
deba@220
  2614
    virtual void clear() {
deba@220
  2615
      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220
  2616
        _deg[it] = 0;
deba@220
  2617
      }
deba@220
  2618
    }
deba@220
  2619
  private:
deba@220
  2620
deba@220
  2621
    const Digraph& _digraph;
deba@220
  2622
    AutoNodeMap _deg;
deba@220
  2623
  };
deba@220
  2624
kpeter@559
  2625
  /// \brief Map of the out-degrees of nodes in a digraph.
deba@220
  2626
  ///
deba@220
  2627
  /// This map returns the out-degree of a node. Once it is constructed,
kpeter@559
  2628
  /// the degrees are stored in a standard \c NodeMap, so each query is done
deba@220
  2629
  /// in constant time. On the other hand, the values are updated automatically
deba@220
  2630
  /// whenever the digraph changes.
deba@220
  2631
  ///
kpeter@559
  2632
  /// \warning Besides \c addNode() and \c addArc(), a digraph structure 
kpeter@559
  2633
  /// may provide alternative ways to modify the digraph.
kpeter@559
  2634
  /// The correct behavior of OutDegMap is not guarantied if these additional
kpeter@559
  2635
  /// features are used. For example the functions
kpeter@559
  2636
  /// \ref ListDigraph::changeSource() "changeSource()",
deba@220
  2637
  /// \ref ListDigraph::changeTarget() "changeTarget()" and
deba@220
  2638
  /// \ref ListDigraph::reverseArc() "reverseArc()"
deba@220
  2639
  /// of \ref ListDigraph will \e not update the degree values correctly.
deba@220
  2640
  ///
deba@220
  2641
  /// \sa InDegMap
kpeter@559
  2642
  template <typename GR>
deba@220
  2643
  class OutDegMap
kpeter@559
  2644
    : protected ItemSetTraits<GR, typename GR::Arc>
deba@220
  2645
      ::ItemNotifier::ObserverBase {
deba@220
  2646
deba@220
  2647
  public:
deba@220
  2648
kpeter@617
  2649
    /// The graph type of OutDegMap
kpeter@617
  2650
    typedef GR Graph;
kpeter@559
  2651
    typedef GR Digraph;
kpeter@559
  2652
    /// The key type
kpeter@559
  2653
    typedef typename Digraph::Node Key;
kpeter@559
  2654
    /// The value type
deba@220
  2655
    typedef int Value;
deba@220
  2656
deba@220
  2657
    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
deba@220
  2658
    ::ItemNotifier::ObserverBase Parent;
deba@220
  2659
deba@220
  2660
  private:
deba@220
  2661
deba@220
  2662
    class AutoNodeMap
deba@220
  2663
      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
deba@220
  2664
    public:
deba@220
  2665
deba@220
  2666
      typedef typename ItemSetTraits<Digraph, Key>::
deba@220
  2667
      template Map<int>::Type Parent;
deba@220
  2668
deba@220
  2669
      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
deba@220
  2670
deba@220
  2671
      virtual void add(const Key& key) {
deba@220
  2672
        Parent::add(key);
deba@220
  2673
        Parent::set(key, 0);
deba@220
  2674
      }
deba@220
  2675
      virtual void add(const std::vector<Key>& keys) {
deba@220
  2676
        Parent::add(keys);
deba@220
  2677
        for (int i = 0; i < int(keys.size()); ++i) {
deba@220
  2678
          Parent::set(keys[i], 0);
deba@220
  2679
        }
deba@220
  2680
      }
deba@220
  2681
      virtual void build() {
deba@220
  2682
        Parent::build();
deba@220
  2683
        Key it;
deba@220
  2684
        typename Parent::Notifier* nf = Parent::notifier();
deba@220
  2685
        for (nf->first(it); it != INVALID; nf->next(it)) {
deba@220
  2686
          Parent::set(it, 0);
deba@220
  2687
        }
deba@220
  2688
      }
deba@220
  2689
    };
deba@220
  2690
deba@220
  2691
  public:
deba@220
  2692
deba@220
  2693
    /// \brief Constructor.
deba@220
  2694
    ///
kpeter@559
  2695
    /// Constructor for creating an out-degree map.
kpeter@559
  2696
    explicit OutDegMap(const Digraph& graph)
kpeter@559
  2697
      : _digraph(graph), _deg(graph) {
deba@220
  2698
      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
deba@220
  2699
deba@220
  2700
      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220
  2701
        _deg[it] = countOutArcs(_digraph, it);
deba@220
  2702
      }
deba@220
  2703
    }
deba@220
  2704
kpeter@559
  2705
    /// \brief Gives back the out-degree of a Node.
kpeter@559
  2706
    ///
deba@220
  2707
    /// Gives back the out-degree of a Node.
deba@220
  2708
    int operator[](const Key& key) const {
deba@220
  2709
      return _deg[key];
deba@220
  2710
    }
deba@220
  2711
deba@220
  2712
  protected:
deba@220
  2713
deba@220
  2714
    typedef typename Digraph::Arc Arc;
deba@220
  2715
deba@220
  2716
    virtual void add(const Arc& arc) {
deba@220
  2717
      ++_deg[_digraph.source(arc)];
deba@220
  2718
    }
deba@220
  2719
deba@220
  2720
    virtual void add(const std::vector<Arc>& arcs) {
deba@220
  2721
      for (int i = 0; i < int(arcs.size()); ++i) {
deba@220
  2722
        ++_deg[_digraph.source(arcs[i])];
deba@220
  2723
      }
deba@220
  2724
    }
deba@220
  2725
deba@220
  2726
    virtual void erase(const Arc& arc) {
deba@220
  2727
      --_deg[_digraph.source(arc)];
deba@220
  2728
    }
deba@220
  2729
deba@220
  2730
    virtual void erase(const std::vector<Arc>& arcs) {
deba@220
  2731
      for (int i = 0; i < int(arcs.size()); ++i) {
deba@220
  2732
        --_deg[_digraph.source(arcs[i])];
deba@220
  2733
      }
deba@220
  2734
    }
deba@220
  2735
deba@220
  2736
    virtual void build() {
deba@220
  2737
      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220
  2738
        _deg[it] = countOutArcs(_digraph, it);
deba@220
  2739
      }
deba@220
  2740
    }
deba@220
  2741
deba@220
  2742
    virtual void clear() {
deba@220
  2743
      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220
  2744
        _deg[it] = 0;
deba@220
  2745
      }
deba@220
  2746
    }
deba@220
  2747
  private:
deba@220
  2748
deba@220
  2749
    const Digraph& _digraph;
deba@220
  2750
    AutoNodeMap _deg;
deba@220
  2751
  };
deba@220
  2752
kpeter@559
  2753
  /// \brief Potential difference map
kpeter@559
  2754
  ///
kpeter@584
  2755
  /// PotentialDifferenceMap returns the difference between the potentials of
kpeter@584
  2756
  /// the source and target nodes of each arc in a digraph, i.e. it returns
kpeter@559
  2757
  /// \code
kpeter@559
  2758
  ///   potential[gr.target(arc)] - potential[gr.source(arc)].
kpeter@559
  2759
  /// \endcode
kpeter@559
  2760
  /// \tparam GR The digraph type.
kpeter@559
  2761
  /// \tparam POT A node map storing the potentials.
kpeter@559
  2762
  template <typename GR, typename POT>
kpeter@559
  2763
  class PotentialDifferenceMap {
kpeter@559
  2764
  public:
kpeter@559
  2765
    /// Key type
kpeter@559
  2766
    typedef typename GR::Arc Key;
kpeter@559
  2767
    /// Value type
kpeter@559
  2768
    typedef typename POT::Value Value;
kpeter@559
  2769
kpeter@559
  2770
    /// \brief Constructor
kpeter@559
  2771
    ///
kpeter@559
  2772
    /// Contructor of the map.
kpeter@559
  2773
    explicit PotentialDifferenceMap(const GR& gr,
kpeter@559
  2774
                                    const POT& potential)
kpeter@559
  2775
      : _digraph(gr), _potential(potential) {}
kpeter@559
  2776
kpeter@559
  2777
    /// \brief Returns the potential difference for the given arc.
kpeter@559
  2778
    ///
kpeter@559
  2779
    /// Returns the potential difference for the given arc, i.e.
kpeter@559
  2780
    /// \code
kpeter@559
  2781
    ///   potential[gr.target(arc)] - potential[gr.source(arc)].
kpeter@559
  2782
    /// \endcode
kpeter@559
  2783
    Value operator[](const Key& arc) const {
kpeter@559
  2784
      return _potential[_digraph.target(arc)] -
kpeter@559
  2785
        _potential[_digraph.source(arc)];
kpeter@559
  2786
    }
kpeter@559
  2787
kpeter@559
  2788
  private:
kpeter@559
  2789
    const GR& _digraph;
kpeter@559
  2790
    const POT& _potential;
kpeter@559
  2791
  };
kpeter@559
  2792
kpeter@559
  2793
  /// \brief Returns a PotentialDifferenceMap.
kpeter@559
  2794
  ///
kpeter@559
  2795
  /// This function just returns a PotentialDifferenceMap.
kpeter@559
  2796
  /// \relates PotentialDifferenceMap
kpeter@559
  2797
  template <typename GR, typename POT>
kpeter@559
  2798
  PotentialDifferenceMap<GR, POT>
kpeter@559
  2799
  potentialDifferenceMap(const GR& gr, const POT& potential) {
kpeter@559
  2800
    return PotentialDifferenceMap<GR, POT>(gr, potential);
kpeter@559
  2801
  }
kpeter@559
  2802
alpar@25
  2803
  /// @}
alpar@25
  2804
}
alpar@25
  2805
alpar@25
  2806
#endif // LEMON_MAPS_H