lemon/maps.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 13 Nov 2009 00:10:33 +0100
changeset 815 aef153f430e1
parent 786 e20173729589
parent 789 8ddb7deabab9
child 877 141f9c0db4a3
permissions -rw-r--r--
Entirely rework cycle canceling algorithms (#180)

- Move the cycle canceling algorithms (CycleCanceling, CancelAndTighten)
into one class (CycleCanceling).
- Add a Method parameter to the run() function to be able to select
the used cycle canceling method.
- Use the new interface similarly to NetworkSimplex.
- Rework the implementations using an efficient internal structure
for handling the residual network.
This improvement made the codes much faster.
- Handle GEQ supply type (LEQ is not supported).
- Handle infinite upper bounds.
- Handle negative costs (for arcs of finite upper bound).
- Extend the documentation.
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>
kpeter@694
    25
#include <map>
alpar@25
    26
deba@220
    27
#include <lemon/core.h>
alpar@25
    28
alpar@25
    29
///\file
alpar@25
    30
///\ingroup maps
alpar@25
    31
///\brief Miscellaneous property maps
kpeter@80
    32
alpar@25
    33
namespace lemon {
alpar@25
    34
alpar@25
    35
  /// \addtogroup maps
alpar@25
    36
  /// @{
alpar@25
    37
alpar@25
    38
  /// Base class of maps.
alpar@25
    39
kpeter@80
    40
  /// Base class of maps. It provides the necessary type definitions
kpeter@80
    41
  /// required by the map %concepts.
kpeter@80
    42
  template<typename K, typename V>
alpar@25
    43
  class MapBase {
alpar@25
    44
  public:
kpeter@313
    45
    /// \brief The key type of the map.
alpar@25
    46
    typedef K Key;
kpeter@80
    47
    /// \brief The value type of the map.
kpeter@80
    48
    /// (The type of objects associated with the keys).
kpeter@80
    49
    typedef V Value;
alpar@25
    50
  };
alpar@25
    51
kpeter@80
    52
alpar@25
    53
  /// Null map. (a.k.a. DoNothingMap)
alpar@25
    54
kpeter@29
    55
  /// This map can be used if you have to provide a map only for
kpeter@80
    56
  /// its type definitions, or if you have to provide a writable map,
kpeter@80
    57
  /// but data written to it is not required (i.e. it will be sent to
kpeter@29
    58
  /// <tt>/dev/null</tt>).
kpeter@722
    59
  /// It conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
kpeter@80
    60
  ///
kpeter@80
    61
  /// \sa ConstMap
kpeter@80
    62
  template<typename K, typename V>
kpeter@80
    63
  class NullMap : public MapBase<K, V> {
alpar@25
    64
  public:
kpeter@559
    65
    ///\e
kpeter@559
    66
    typedef K Key;
kpeter@559
    67
    ///\e
kpeter@559
    68
    typedef V Value;
kpeter@80
    69
alpar@25
    70
    /// Gives back a default constructed element.
kpeter@80
    71
    Value operator[](const Key&) const { return Value(); }
alpar@25
    72
    /// Absorbs the value.
kpeter@80
    73
    void set(const Key&, const Value&) {}
alpar@25
    74
  };
alpar@25
    75
kpeter@301
    76
  /// Returns a \c NullMap class
kpeter@301
    77
kpeter@301
    78
  /// This function just returns a \c NullMap class.
kpeter@80
    79
  /// \relates NullMap
kpeter@80
    80
  template <typename K, typename V>
alpar@25
    81
  NullMap<K, V> nullMap() {
alpar@25
    82
    return NullMap<K, V>();
alpar@25
    83
  }
alpar@25
    84
alpar@25
    85
alpar@25
    86
  /// Constant map.
alpar@25
    87
kpeter@82
    88
  /// This \ref concepts::ReadMap "readable map" assigns a specified
kpeter@82
    89
  /// value to each key.
kpeter@80
    90
  ///
kpeter@301
    91
  /// In other aspects it is equivalent to \c NullMap.
kpeter@722
    92
  /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
kpeter@80
    93
  /// concept, but it absorbs the data written to it.
kpeter@80
    94
  ///
kpeter@80
    95
  /// The simplest way of using this map is through the constMap()
kpeter@80
    96
  /// function.
kpeter@80
    97
  ///
kpeter@80
    98
  /// \sa NullMap
kpeter@80
    99
  /// \sa IdentityMap
kpeter@80
   100
  template<typename K, typename V>
kpeter@80
   101
  class ConstMap : public MapBase<K, V> {
alpar@25
   102
  private:
kpeter@80
   103
    V _value;
alpar@25
   104
  public:
kpeter@559
   105
    ///\e
kpeter@559
   106
    typedef K Key;
kpeter@559
   107
    ///\e
kpeter@559
   108
    typedef V Value;
alpar@25
   109
alpar@25
   110
    /// Default constructor
alpar@25
   111
kpeter@29
   112
    /// Default constructor.
kpeter@80
   113
    /// The value of the map will be default constructed.
alpar@25
   114
    ConstMap() {}
kpeter@80
   115
kpeter@29
   116
    /// Constructor with specified initial value
alpar@25
   117
kpeter@29
   118
    /// Constructor with specified initial value.
kpeter@123
   119
    /// \param v The initial value of the map.
kpeter@80
   120
    ConstMap(const Value &v) : _value(v) {}
alpar@25
   121
kpeter@80
   122
    /// Gives back the specified value.
kpeter@80
   123
    Value operator[](const Key&) const { return _value; }
alpar@25
   124
kpeter@80
   125
    /// Absorbs the value.
kpeter@80
   126
    void set(const Key&, const Value&) {}
kpeter@80
   127
kpeter@80
   128
    /// Sets the value that is assigned to each key.
kpeter@80
   129
    void setAll(const Value &v) {
kpeter@80
   130
      _value = v;
kpeter@80
   131
    }
kpeter@80
   132
kpeter@80
   133
    template<typename V1>
kpeter@80
   134
    ConstMap(const ConstMap<K, V1> &, const Value &v) : _value(v) {}
alpar@25
   135
  };
alpar@25
   136
kpeter@301
   137
  /// Returns a \c ConstMap class
kpeter@301
   138
kpeter@301
   139
  /// This function just returns a \c ConstMap class.
kpeter@80
   140
  /// \relates ConstMap
kpeter@80
   141
  template<typename K, typename V>
alpar@25
   142
  inline ConstMap<K, V> constMap(const V &v) {
alpar@25
   143
    return ConstMap<K, V>(v);
alpar@25
   144
  }
alpar@25
   145
kpeter@123
   146
  template<typename K, typename V>
kpeter@123
   147
  inline ConstMap<K, V> constMap() {
kpeter@123
   148
    return ConstMap<K, V>();
kpeter@123
   149
  }
kpeter@123
   150
alpar@25
   151
alpar@25
   152
  template<typename T, T v>
kpeter@80
   153
  struct Const {};
alpar@25
   154
alpar@25
   155
  /// Constant map with inlined constant value.
alpar@25
   156
kpeter@82
   157
  /// This \ref concepts::ReadMap "readable map" assigns a specified
kpeter@82
   158
  /// value to each key.
kpeter@80
   159
  ///
kpeter@301
   160
  /// In other aspects it is equivalent to \c NullMap.
kpeter@722
   161
  /// So it conforms to the \ref concepts::ReadWriteMap "ReadWriteMap"
kpeter@80
   162
  /// concept, but it absorbs the data written to it.
kpeter@80
   163
  ///
kpeter@80
   164
  /// The simplest way of using this map is through the constMap()
kpeter@80
   165
  /// function.
kpeter@80
   166
  ///
kpeter@80
   167
  /// \sa NullMap
kpeter@80
   168
  /// \sa IdentityMap
alpar@25
   169
  template<typename K, typename V, V v>
alpar@25
   170
  class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
alpar@25
   171
  public:
kpeter@559
   172
    ///\e
kpeter@559
   173
    typedef K Key;
kpeter@559
   174
    ///\e
kpeter@559
   175
    typedef V Value;
alpar@25
   176
kpeter@80
   177
    /// Constructor.
kpeter@80
   178
    ConstMap() {}
kpeter@80
   179
kpeter@80
   180
    /// Gives back the specified value.
kpeter@80
   181
    Value operator[](const Key&) const { return v; }
kpeter@80
   182
kpeter@80
   183
    /// Absorbs the value.
kpeter@80
   184
    void set(const Key&, const Value&) {}
alpar@25
   185
  };
alpar@25
   186
kpeter@301
   187
  /// Returns a \c ConstMap class with inlined constant value
kpeter@301
   188
kpeter@301
   189
  /// This function just returns a \c ConstMap class with inlined
kpeter@80
   190
  /// constant value.
kpeter@80
   191
  /// \relates ConstMap
kpeter@80
   192
  template<typename K, typename V, V v>
alpar@25
   193
  inline ConstMap<K, Const<V, v> > constMap() {
alpar@25
   194
    return ConstMap<K, Const<V, v> >();
alpar@25
   195
  }
alpar@25
   196
alpar@25
   197
kpeter@82
   198
  /// Identity map.
kpeter@82
   199
kpeter@82
   200
  /// This \ref concepts::ReadMap "read-only map" gives back the given
kpeter@82
   201
  /// key as value without any modification.
kpeter@80
   202
  ///
kpeter@80
   203
  /// \sa ConstMap
kpeter@80
   204
  template <typename T>
kpeter@80
   205
  class IdentityMap : public MapBase<T, T> {
kpeter@80
   206
  public:
kpeter@559
   207
    ///\e
kpeter@559
   208
    typedef T Key;
kpeter@559
   209
    ///\e
kpeter@559
   210
    typedef T Value;
kpeter@80
   211
kpeter@80
   212
    /// Gives back the given value without any modification.
kpeter@82
   213
    Value operator[](const Key &k) const {
kpeter@82
   214
      return k;
kpeter@80
   215
    }
kpeter@80
   216
  };
kpeter@80
   217
kpeter@301
   218
  /// Returns an \c IdentityMap class
kpeter@301
   219
kpeter@301
   220
  /// This function just returns an \c IdentityMap class.
kpeter@80
   221
  /// \relates IdentityMap
kpeter@80
   222
  template<typename T>
kpeter@80
   223
  inline IdentityMap<T> identityMap() {
kpeter@80
   224
    return IdentityMap<T>();
kpeter@80
   225
  }
kpeter@80
   226
kpeter@80
   227
kpeter@80
   228
  /// \brief Map for storing values for integer keys from the range
kpeter@80
   229
  /// <tt>[0..size-1]</tt>.
kpeter@80
   230
  ///
kpeter@80
   231
  /// This map is essentially a wrapper for \c std::vector. It assigns
kpeter@80
   232
  /// values to integer keys from the range <tt>[0..size-1]</tt>.
kpeter@786
   233
  /// It can be used together with some data structures, e.g.
kpeter@786
   234
  /// heap types and \c UnionFind, when the used items are small
kpeter@722
   235
  /// integers. This map conforms to the \ref concepts::ReferenceMap
kpeter@786
   236
  /// "ReferenceMap" concept. 
kpeter@80
   237
  ///
kpeter@80
   238
  /// The simplest way of using this map is through the rangeMap()
kpeter@80
   239
  /// function.
kpeter@80
   240
  template <typename V>
kpeter@80
   241
  class RangeMap : public MapBase<int, V> {
kpeter@80
   242
    template <typename V1>
kpeter@80
   243
    friend class RangeMap;
kpeter@80
   244
  private:
kpeter@80
   245
kpeter@80
   246
    typedef std::vector<V> Vector;
kpeter@80
   247
    Vector _vector;
kpeter@80
   248
alpar@25
   249
  public:
alpar@25
   250
kpeter@80
   251
    /// Key type
kpeter@559
   252
    typedef int Key;
kpeter@80
   253
    /// Value type
kpeter@559
   254
    typedef V Value;
kpeter@80
   255
    /// Reference type
kpeter@80
   256
    typedef typename Vector::reference Reference;
kpeter@80
   257
    /// Const reference type
kpeter@80
   258
    typedef typename Vector::const_reference ConstReference;
kpeter@80
   259
kpeter@80
   260
    typedef True ReferenceMapTag;
kpeter@80
   261
kpeter@80
   262
  public:
kpeter@80
   263
kpeter@80
   264
    /// Constructor with specified default value.
kpeter@80
   265
    RangeMap(int size = 0, const Value &value = Value())
kpeter@80
   266
      : _vector(size, value) {}
kpeter@80
   267
kpeter@80
   268
    /// Constructs the map from an appropriate \c std::vector.
kpeter@80
   269
    template <typename V1>
kpeter@80
   270
    RangeMap(const std::vector<V1>& vector)
kpeter@80
   271
      : _vector(vector.begin(), vector.end()) {}
kpeter@80
   272
kpeter@301
   273
    /// Constructs the map from another \c RangeMap.
kpeter@80
   274
    template <typename V1>
kpeter@80
   275
    RangeMap(const RangeMap<V1> &c)
kpeter@80
   276
      : _vector(c._vector.begin(), c._vector.end()) {}
kpeter@80
   277
kpeter@80
   278
    /// Returns the size of the map.
kpeter@80
   279
    int size() {
kpeter@80
   280
      return _vector.size();
kpeter@80
   281
    }
kpeter@80
   282
kpeter@80
   283
    /// Resizes the map.
kpeter@80
   284
kpeter@80
   285
    /// Resizes the underlying \c std::vector container, so changes the
kpeter@80
   286
    /// keyset of the map.
kpeter@80
   287
    /// \param size The new size of the map. The new keyset will be the
kpeter@80
   288
    /// range <tt>[0..size-1]</tt>.
kpeter@80
   289
    /// \param value The default value to assign to the new keys.
kpeter@80
   290
    void resize(int size, const Value &value = Value()) {
kpeter@80
   291
      _vector.resize(size, value);
kpeter@80
   292
    }
kpeter@80
   293
kpeter@80
   294
  private:
kpeter@80
   295
kpeter@80
   296
    RangeMap& operator=(const RangeMap&);
kpeter@80
   297
kpeter@80
   298
  public:
kpeter@80
   299
kpeter@80
   300
    ///\e
kpeter@80
   301
    Reference operator[](const Key &k) {
kpeter@80
   302
      return _vector[k];
kpeter@80
   303
    }
kpeter@80
   304
kpeter@80
   305
    ///\e
kpeter@80
   306
    ConstReference operator[](const Key &k) const {
kpeter@80
   307
      return _vector[k];
kpeter@80
   308
    }
kpeter@80
   309
kpeter@80
   310
    ///\e
kpeter@80
   311
    void set(const Key &k, const Value &v) {
kpeter@80
   312
      _vector[k] = v;
kpeter@80
   313
    }
kpeter@80
   314
  };
kpeter@80
   315
kpeter@301
   316
  /// Returns a \c RangeMap class
kpeter@301
   317
kpeter@301
   318
  /// This function just returns a \c RangeMap class.
kpeter@80
   319
  /// \relates RangeMap
kpeter@80
   320
  template<typename V>
kpeter@80
   321
  inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
kpeter@80
   322
    return RangeMap<V>(size, value);
kpeter@80
   323
  }
kpeter@80
   324
kpeter@301
   325
  /// \brief Returns a \c RangeMap class created from an appropriate
kpeter@80
   326
  /// \c std::vector
kpeter@80
   327
kpeter@301
   328
  /// This function just returns a \c RangeMap class created from an
kpeter@80
   329
  /// appropriate \c std::vector.
kpeter@80
   330
  /// \relates RangeMap
kpeter@80
   331
  template<typename V>
kpeter@80
   332
  inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
kpeter@80
   333
    return RangeMap<V>(vector);
kpeter@80
   334
  }
kpeter@80
   335
kpeter@80
   336
kpeter@80
   337
  /// Map type based on \c std::map
kpeter@80
   338
kpeter@80
   339
  /// This map is essentially a wrapper for \c std::map with addition
kpeter@80
   340
  /// that you can specify a default value for the keys that are not
kpeter@80
   341
  /// stored actually. This value can be different from the default
kpeter@80
   342
  /// contructed value (i.e. \c %Value()).
kpeter@722
   343
  /// This type conforms to the \ref concepts::ReferenceMap "ReferenceMap"
kpeter@80
   344
  /// concept.
kpeter@80
   345
  ///
kpeter@80
   346
  /// This map is useful if a default value should be assigned to most of
kpeter@80
   347
  /// the keys and different values should be assigned only to a few
kpeter@80
   348
  /// keys (i.e. the map is "sparse").
kpeter@80
   349
  /// The name of this type also refers to this important usage.
kpeter@80
   350
  ///
kpeter@786
   351
  /// Apart form that, this map can be used in many other cases since it
kpeter@80
   352
  /// is based on \c std::map, which is a general associative container.
kpeter@786
   353
  /// However, keep in mind that it is usually not as efficient as other
kpeter@80
   354
  /// maps.
kpeter@80
   355
  ///
kpeter@80
   356
  /// The simplest way of using this map is through the sparseMap()
kpeter@80
   357
  /// function.
kpeter@559
   358
  template <typename K, typename V, typename Comp = std::less<K> >
kpeter@80
   359
  class SparseMap : public MapBase<K, V> {
kpeter@80
   360
    template <typename K1, typename V1, typename C1>
kpeter@80
   361
    friend class SparseMap;
kpeter@80
   362
  public:
kpeter@80
   363
kpeter@80
   364
    /// Key type
kpeter@559
   365
    typedef K Key;
kpeter@80
   366
    /// Value type
kpeter@559
   367
    typedef V Value;
kpeter@80
   368
    /// Reference type
kpeter@80
   369
    typedef Value& Reference;
kpeter@80
   370
    /// Const reference type
kpeter@80
   371
    typedef const Value& ConstReference;
alpar@25
   372
kpeter@45
   373
    typedef True ReferenceMapTag;
kpeter@45
   374
alpar@25
   375
  private:
kpeter@80
   376
kpeter@559
   377
    typedef std::map<K, V, Comp> Map;
kpeter@80
   378
    Map _map;
alpar@25
   379
    Value _value;
alpar@25
   380
alpar@25
   381
  public:
alpar@25
   382
kpeter@80
   383
    /// \brief Constructor with specified default value.
kpeter@80
   384
    SparseMap(const Value &value = Value()) : _value(value) {}
kpeter@80
   385
    /// \brief Constructs the map from an appropriate \c std::map, and
kpeter@47
   386
    /// explicitly specifies a default value.
kpeter@80
   387
    template <typename V1, typename Comp1>
kpeter@80
   388
    SparseMap(const std::map<Key, V1, Comp1> &map,
kpeter@80
   389
              const Value &value = Value())
alpar@25
   390
      : _map(map.begin(), map.end()), _value(value) {}
kpeter@80
   391
kpeter@301
   392
    /// \brief Constructs the map from another \c SparseMap.
kpeter@80
   393
    template<typename V1, typename Comp1>
kpeter@80
   394
    SparseMap(const SparseMap<Key, V1, Comp1> &c)
alpar@25
   395
      : _map(c._map.begin(), c._map.end()), _value(c._value) {}
alpar@25
   396
alpar@25
   397
  private:
alpar@25
   398
kpeter@80
   399
    SparseMap& operator=(const SparseMap&);
alpar@25
   400
alpar@25
   401
  public:
alpar@25
   402
alpar@25
   403
    ///\e
alpar@25
   404
    Reference operator[](const Key &k) {
alpar@25
   405
      typename Map::iterator it = _map.lower_bound(k);
alpar@25
   406
      if (it != _map.end() && !_map.key_comp()(k, it->first))
alpar@209
   407
        return it->second;
alpar@25
   408
      else
alpar@209
   409
        return _map.insert(it, std::make_pair(k, _value))->second;
alpar@25
   410
    }
alpar@25
   411
kpeter@80
   412
    ///\e
alpar@25
   413
    ConstReference operator[](const Key &k) const {
alpar@25
   414
      typename Map::const_iterator it = _map.find(k);
alpar@25
   415
      if (it != _map.end())
alpar@209
   416
        return it->second;
alpar@25
   417
      else
alpar@209
   418
        return _value;
alpar@25
   419
    }
alpar@25
   420
kpeter@80
   421
    ///\e
kpeter@80
   422
    void set(const Key &k, const Value &v) {
alpar@25
   423
      typename Map::iterator it = _map.lower_bound(k);
alpar@25
   424
      if (it != _map.end() && !_map.key_comp()(k, it->first))
alpar@209
   425
        it->second = v;
alpar@25
   426
      else
alpar@209
   427
        _map.insert(it, std::make_pair(k, v));
alpar@25
   428
    }
alpar@25
   429
kpeter@80
   430
    ///\e
kpeter@80
   431
    void setAll(const Value &v) {
kpeter@80
   432
      _value = v;
alpar@25
   433
      _map.clear();
kpeter@80
   434
    }
kpeter@80
   435
  };
alpar@25
   436
kpeter@301
   437
  /// Returns a \c SparseMap class
kpeter@301
   438
kpeter@301
   439
  /// This function just returns a \c SparseMap class with specified
kpeter@80
   440
  /// default value.
kpeter@80
   441
  /// \relates SparseMap
kpeter@80
   442
  template<typename K, typename V, typename Compare>
kpeter@80
   443
  inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
kpeter@80
   444
    return SparseMap<K, V, Compare>(value);
kpeter@54
   445
  }
kpeter@45
   446
kpeter@80
   447
  template<typename K, typename V>
kpeter@80
   448
  inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
kpeter@80
   449
    return SparseMap<K, V, std::less<K> >(value);
kpeter@45
   450
  }
alpar@25
   451
kpeter@301
   452
  /// \brief Returns a \c SparseMap class created from an appropriate
kpeter@80
   453
  /// \c std::map
alpar@25
   454
kpeter@301
   455
  /// This function just returns a \c SparseMap class created from an
kpeter@80
   456
  /// appropriate \c std::map.
kpeter@80
   457
  /// \relates SparseMap
kpeter@80
   458
  template<typename K, typename V, typename Compare>
kpeter@80
   459
  inline SparseMap<K, V, Compare>
kpeter@80
   460
    sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
kpeter@80
   461
  {
kpeter@80
   462
    return SparseMap<K, V, Compare>(map, value);
kpeter@45
   463
  }
alpar@25
   464
alpar@25
   465
  /// @}
alpar@25
   466
alpar@25
   467
  /// \addtogroup map_adaptors
alpar@25
   468
  /// @{
alpar@25
   469
kpeter@80
   470
  /// Composition of two maps
kpeter@80
   471
kpeter@82
   472
  /// This \ref concepts::ReadMap "read-only map" returns the
kpeter@80
   473
  /// composition of two given maps. That is to say, if \c m1 is of
kpeter@80
   474
  /// type \c M1 and \c m2 is of \c M2, then for
kpeter@80
   475
  /// \code
kpeter@80
   476
  ///   ComposeMap<M1, M2> cm(m1,m2);
kpeter@80
   477
  /// \endcode
kpeter@80
   478
  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
alpar@25
   479
  ///
kpeter@80
   480
  /// The \c Key type of the map is inherited from \c M2 and the
kpeter@80
   481
  /// \c Value type is from \c M1.
kpeter@80
   482
  /// \c M2::Value must be convertible to \c M1::Key.
kpeter@80
   483
  ///
kpeter@80
   484
  /// The simplest way of using this map is through the composeMap()
kpeter@80
   485
  /// function.
kpeter@80
   486
  ///
kpeter@80
   487
  /// \sa CombineMap
kpeter@80
   488
  template <typename M1, typename M2>
kpeter@80
   489
  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
kpeter@80
   490
    const M1 &_m1;
kpeter@80
   491
    const M2 &_m2;
alpar@25
   492
  public:
kpeter@559
   493
    ///\e
kpeter@559
   494
    typedef typename M2::Key Key;
kpeter@559
   495
    ///\e
kpeter@559
   496
    typedef typename M1::Value Value;
alpar@25
   497
kpeter@80
   498
    /// Constructor
kpeter@80
   499
    ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@80
   500
kpeter@559
   501
    ///\e
kpeter@80
   502
    typename MapTraits<M1>::ConstReturnValue
kpeter@80
   503
    operator[](const Key &k) const { return _m1[_m2[k]]; }
alpar@25
   504
  };
alpar@25
   505
kpeter@301
   506
  /// Returns a \c ComposeMap class
kpeter@301
   507
kpeter@301
   508
  /// This function just returns a \c ComposeMap class.
kpeter@80
   509
  ///
kpeter@80
   510
  /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
kpeter@80
   511
  /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
kpeter@80
   512
  /// will be equal to <tt>m1[m2[x]]</tt>.
kpeter@80
   513
  ///
kpeter@80
   514
  /// \relates ComposeMap
kpeter@80
   515
  template <typename M1, typename M2>
kpeter@80
   516
  inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) {
kpeter@80
   517
    return ComposeMap<M1, M2>(m1, m2);
alpar@25
   518
  }
alpar@25
   519
kpeter@80
   520
kpeter@80
   521
  /// Combination of two maps using an STL (binary) functor.
kpeter@80
   522
kpeter@82
   523
  /// This \ref concepts::ReadMap "read-only map" takes two maps and a
kpeter@80
   524
  /// binary functor and returns the combination of the two given maps
kpeter@80
   525
  /// using the functor.
kpeter@80
   526
  /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2
kpeter@80
   527
  /// and \c f is of \c F, then for
kpeter@80
   528
  /// \code
kpeter@80
   529
  ///   CombineMap<M1,M2,F,V> cm(m1,m2,f);
kpeter@80
   530
  /// \endcode
kpeter@80
   531
  /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>.
alpar@26
   532
  ///
kpeter@80
   533
  /// The \c Key type of the map is inherited from \c M1 (\c M1::Key
kpeter@80
   534
  /// must be convertible to \c M2::Key) and the \c Value type is \c V.
kpeter@80
   535
  /// \c M2::Value and \c M1::Value must be convertible to the
kpeter@80
   536
  /// corresponding input parameter of \c F and the return type of \c F
kpeter@80
   537
  /// must be convertible to \c V.
kpeter@80
   538
  ///
kpeter@80
   539
  /// The simplest way of using this map is through the combineMap()
kpeter@80
   540
  /// function.
kpeter@80
   541
  ///
kpeter@80
   542
  /// \sa ComposeMap
kpeter@80
   543
  template<typename M1, typename M2, typename F,
alpar@209
   544
           typename V = typename F::result_type>
kpeter@80
   545
  class CombineMap : public MapBase<typename M1::Key, V> {
kpeter@80
   546
    const M1 &_m1;
kpeter@80
   547
    const M2 &_m2;
kpeter@80
   548
    F _f;
alpar@25
   549
  public:
kpeter@559
   550
    ///\e
kpeter@559
   551
    typedef typename M1::Key Key;
kpeter@559
   552
    ///\e
kpeter@559
   553
    typedef V Value;
alpar@25
   554
kpeter@80
   555
    /// Constructor
kpeter@80
   556
    CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
kpeter@80
   557
      : _m1(m1), _m2(m2), _f(f) {}
kpeter@559
   558
    ///\e
kpeter@80
   559
    Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
kpeter@80
   560
  };
alpar@25
   561
kpeter@301
   562
  /// Returns a \c CombineMap class
kpeter@301
   563
kpeter@301
   564
  /// This function just returns a \c CombineMap class.
kpeter@80
   565
  ///
kpeter@80
   566
  /// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80
   567
  /// values, then
kpeter@80
   568
  /// \code
kpeter@80
   569
  ///   combineMap(m1,m2,std::plus<double>())
kpeter@80
   570
  /// \endcode
kpeter@80
   571
  /// is equivalent to
kpeter@80
   572
  /// \code
kpeter@80
   573
  ///   addMap(m1,m2)
kpeter@80
   574
  /// \endcode
kpeter@80
   575
  ///
kpeter@80
   576
  /// This function is specialized for adaptable binary function
kpeter@80
   577
  /// classes and C++ functions.
kpeter@80
   578
  ///
kpeter@80
   579
  /// \relates CombineMap
kpeter@80
   580
  template<typename M1, typename M2, typename F, typename V>
kpeter@80
   581
  inline CombineMap<M1, M2, F, V>
kpeter@80
   582
  combineMap(const M1 &m1, const M2 &m2, const F &f) {
kpeter@80
   583
    return CombineMap<M1, M2, F, V>(m1,m2,f);
alpar@25
   584
  }
alpar@25
   585
kpeter@80
   586
  template<typename M1, typename M2, typename F>
kpeter@80
   587
  inline CombineMap<M1, M2, F, typename F::result_type>
kpeter@80
   588
  combineMap(const M1 &m1, const M2 &m2, const F &f) {
kpeter@80
   589
    return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
kpeter@80
   590
  }
alpar@25
   591
kpeter@80
   592
  template<typename M1, typename M2, typename K1, typename K2, typename V>
kpeter@80
   593
  inline CombineMap<M1, M2, V (*)(K1, K2), V>
kpeter@80
   594
  combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
kpeter@80
   595
    return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
kpeter@80
   596
  }
kpeter@80
   597
kpeter@80
   598
kpeter@80
   599
  /// Converts an STL style (unary) functor to a map
kpeter@80
   600
kpeter@82
   601
  /// This \ref concepts::ReadMap "read-only map" returns the value
kpeter@80
   602
  /// of a given functor. Actually, it just wraps the functor and
kpeter@80
   603
  /// provides the \c Key and \c Value typedefs.
alpar@26
   604
  ///
kpeter@80
   605
  /// Template parameters \c K and \c V will become its \c Key and
kpeter@80
   606
  /// \c Value. In most cases they have to be given explicitly because
kpeter@80
   607
  /// a functor typically does not provide \c argument_type and
kpeter@80
   608
  /// \c result_type typedefs.
kpeter@80
   609
  /// Parameter \c F is the type of the used functor.
kpeter@29
   610
  ///
kpeter@80
   611
  /// The simplest way of using this map is through the functorToMap()
kpeter@80
   612
  /// function.
kpeter@80
   613
  ///
kpeter@80
   614
  /// \sa MapToFunctor
kpeter@80
   615
  template<typename F,
alpar@209
   616
           typename K = typename F::argument_type,
alpar@209
   617
           typename V = typename F::result_type>
kpeter@80
   618
  class FunctorToMap : public MapBase<K, V> {
kpeter@123
   619
    F _f;
kpeter@80
   620
  public:
kpeter@559
   621
    ///\e
kpeter@559
   622
    typedef K Key;
kpeter@559
   623
    ///\e
kpeter@559
   624
    typedef V Value;
alpar@25
   625
kpeter@80
   626
    /// Constructor
kpeter@80
   627
    FunctorToMap(const F &f = F()) : _f(f) {}
kpeter@559
   628
    ///\e
kpeter@80
   629
    Value operator[](const Key &k) const { return _f(k); }
kpeter@80
   630
  };
kpeter@80
   631
kpeter@301
   632
  /// Returns a \c FunctorToMap class
kpeter@301
   633
kpeter@301
   634
  /// This function just returns a \c FunctorToMap class.
kpeter@80
   635
  ///
kpeter@80
   636
  /// This function is specialized for adaptable binary function
kpeter@80
   637
  /// classes and C++ functions.
kpeter@80
   638
  ///
kpeter@80
   639
  /// \relates FunctorToMap
kpeter@80
   640
  template<typename K, typename V, typename F>
kpeter@80
   641
  inline FunctorToMap<F, K, V> functorToMap(const F &f) {
kpeter@80
   642
    return FunctorToMap<F, K, V>(f);
kpeter@80
   643
  }
kpeter@80
   644
kpeter@80
   645
  template <typename F>
kpeter@80
   646
  inline FunctorToMap<F, typename F::argument_type, typename F::result_type>
kpeter@80
   647
    functorToMap(const F &f)
kpeter@80
   648
  {
kpeter@80
   649
    return FunctorToMap<F, typename F::argument_type,
kpeter@80
   650
      typename F::result_type>(f);
kpeter@80
   651
  }
kpeter@80
   652
kpeter@80
   653
  template <typename K, typename V>
kpeter@80
   654
  inline FunctorToMap<V (*)(K), K, V> functorToMap(V (*f)(K)) {
kpeter@80
   655
    return FunctorToMap<V (*)(K), K, V>(f);
kpeter@80
   656
  }
kpeter@80
   657
kpeter@80
   658
kpeter@80
   659
  /// Converts a map to an STL style (unary) functor
kpeter@80
   660
kpeter@80
   661
  /// This class converts a map to an STL style (unary) functor.
kpeter@80
   662
  /// That is it provides an <tt>operator()</tt> to read its values.
kpeter@80
   663
  ///
kpeter@80
   664
  /// For the sake of convenience it also works as a usual
kpeter@80
   665
  /// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt>
kpeter@80
   666
  /// and the \c Key and \c Value typedefs also exist.
kpeter@80
   667
  ///
kpeter@80
   668
  /// The simplest way of using this map is through the mapToFunctor()
kpeter@80
   669
  /// function.
kpeter@80
   670
  ///
kpeter@80
   671
  ///\sa FunctorToMap
kpeter@80
   672
  template <typename M>
kpeter@80
   673
  class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
   674
    const M &_m;
alpar@25
   675
  public:
kpeter@559
   676
    ///\e
kpeter@559
   677
    typedef typename M::Key Key;
kpeter@559
   678
    ///\e
kpeter@559
   679
    typedef typename M::Value Value;
kpeter@559
   680
kpeter@559
   681
    typedef typename M::Key argument_type;
kpeter@559
   682
    typedef typename M::Value result_type;
kpeter@80
   683
kpeter@80
   684
    /// Constructor
kpeter@80
   685
    MapToFunctor(const M &m) : _m(m) {}
kpeter@559
   686
    ///\e
kpeter@80
   687
    Value operator()(const Key &k) const { return _m[k]; }
kpeter@559
   688
    ///\e
kpeter@80
   689
    Value operator[](const Key &k) const { return _m[k]; }
alpar@25
   690
  };
kpeter@45
   691
kpeter@301
   692
  /// Returns a \c MapToFunctor class
kpeter@301
   693
kpeter@301
   694
  /// This function just returns a \c MapToFunctor class.
kpeter@80
   695
  /// \relates MapToFunctor
kpeter@45
   696
  template<typename M>
kpeter@80
   697
  inline MapToFunctor<M> mapToFunctor(const M &m) {
kpeter@80
   698
    return MapToFunctor<M>(m);
kpeter@45
   699
  }
alpar@25
   700
alpar@25
   701
kpeter@80
   702
  /// \brief Map adaptor to convert the \c Value type of a map to
kpeter@80
   703
  /// another type using the default conversion.
kpeter@80
   704
kpeter@80
   705
  /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap
kpeter@80
   706
  /// "readable map" to another type using the default conversion.
kpeter@80
   707
  /// The \c Key type of it is inherited from \c M and the \c Value
kpeter@80
   708
  /// type is \c V.
kpeter@722
   709
  /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
alpar@26
   710
  ///
kpeter@80
   711
  /// The simplest way of using this map is through the convertMap()
kpeter@80
   712
  /// function.
kpeter@80
   713
  template <typename M, typename V>
kpeter@80
   714
  class ConvertMap : public MapBase<typename M::Key, V> {
kpeter@80
   715
    const M &_m;
kpeter@80
   716
  public:
kpeter@559
   717
    ///\e
kpeter@559
   718
    typedef typename M::Key Key;
kpeter@559
   719
    ///\e
kpeter@559
   720
    typedef V Value;
kpeter@80
   721
kpeter@80
   722
    /// Constructor
kpeter@80
   723
kpeter@80
   724
    /// Constructor.
kpeter@80
   725
    /// \param m The underlying map.
kpeter@80
   726
    ConvertMap(const M &m) : _m(m) {}
kpeter@80
   727
kpeter@559
   728
    ///\e
kpeter@80
   729
    Value operator[](const Key &k) const { return _m[k]; }
kpeter@80
   730
  };
kpeter@80
   731
kpeter@301
   732
  /// Returns a \c ConvertMap class
kpeter@301
   733
kpeter@301
   734
  /// This function just returns a \c ConvertMap class.
kpeter@80
   735
  /// \relates ConvertMap
kpeter@80
   736
  template<typename V, typename M>
kpeter@80
   737
  inline ConvertMap<M, V> convertMap(const M &map) {
kpeter@80
   738
    return ConvertMap<M, V>(map);
kpeter@80
   739
  }
kpeter@80
   740
kpeter@80
   741
kpeter@80
   742
  /// Applies all map setting operations to two maps
kpeter@80
   743
kpeter@80
   744
  /// This map has two \ref concepts::WriteMap "writable map" parameters
kpeter@80
   745
  /// and each write request will be passed to both of them.
kpeter@80
   746
  /// If \c M1 is also \ref concepts::ReadMap "readable", then the read
kpeter@80
   747
  /// operations will return the corresponding values of \c M1.
kpeter@29
   748
  ///
kpeter@80
   749
  /// The \c Key and \c Value types are inherited from \c M1.
kpeter@80
   750
  /// The \c Key and \c Value of \c M2 must be convertible from those
kpeter@80
   751
  /// of \c M1.
kpeter@80
   752
  ///
kpeter@80
   753
  /// The simplest way of using this map is through the forkMap()
kpeter@80
   754
  /// function.
kpeter@80
   755
  template<typename  M1, typename M2>
kpeter@80
   756
  class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80
   757
    M1 &_m1;
kpeter@80
   758
    M2 &_m2;
kpeter@80
   759
  public:
kpeter@559
   760
    ///\e
kpeter@559
   761
    typedef typename M1::Key Key;
kpeter@559
   762
    ///\e
kpeter@559
   763
    typedef typename M1::Value Value;
alpar@25
   764
kpeter@80
   765
    /// Constructor
kpeter@80
   766
    ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@80
   767
    /// Returns the value associated with the given key in the first map.
kpeter@80
   768
    Value operator[](const Key &k) const { return _m1[k]; }
kpeter@80
   769
    /// Sets the value associated with the given key in both maps.
kpeter@80
   770
    void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); }
kpeter@80
   771
  };
kpeter@80
   772
kpeter@301
   773
  /// Returns a \c ForkMap class
kpeter@301
   774
kpeter@301
   775
  /// This function just returns a \c ForkMap class.
kpeter@80
   776
  /// \relates ForkMap
kpeter@80
   777
  template <typename M1, typename M2>
kpeter@80
   778
  inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) {
kpeter@80
   779
    return ForkMap<M1,M2>(m1,m2);
kpeter@80
   780
  }
kpeter@80
   781
kpeter@80
   782
kpeter@80
   783
  /// Sum of two maps
kpeter@80
   784
kpeter@82
   785
  /// This \ref concepts::ReadMap "read-only map" returns the sum
kpeter@80
   786
  /// of the values of the two given maps.
kpeter@80
   787
  /// Its \c Key and \c Value types are inherited from \c M1.
kpeter@80
   788
  /// The \c Key and \c Value of \c M2 must be convertible to those of
kpeter@80
   789
  /// \c M1.
kpeter@80
   790
  ///
kpeter@80
   791
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@80
   792
  /// \code
kpeter@80
   793
  ///   AddMap<M1,M2> am(m1,m2);
kpeter@80
   794
  /// \endcode
kpeter@80
   795
  /// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>.
kpeter@80
   796
  ///
kpeter@80
   797
  /// The simplest way of using this map is through the addMap()
kpeter@80
   798
  /// function.
kpeter@80
   799
  ///
kpeter@80
   800
  /// \sa SubMap, MulMap, DivMap
kpeter@80
   801
  /// \sa ShiftMap, ShiftWriteMap
kpeter@80
   802
  template<typename M1, typename M2>
alpar@25
   803
  class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80
   804
    const M1 &_m1;
kpeter@80
   805
    const M2 &_m2;
alpar@25
   806
  public:
kpeter@559
   807
    ///\e
kpeter@559
   808
    typedef typename M1::Key Key;
kpeter@559
   809
    ///\e
kpeter@559
   810
    typedef typename M1::Value Value;
alpar@25
   811
kpeter@80
   812
    /// Constructor
kpeter@80
   813
    AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559
   814
    ///\e
kpeter@80
   815
    Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
alpar@25
   816
  };
alpar@25
   817
kpeter@301
   818
  /// Returns an \c AddMap class
kpeter@301
   819
kpeter@301
   820
  /// This function just returns an \c AddMap class.
alpar@25
   821
  ///
kpeter@80
   822
  /// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80
   823
  /// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to
kpeter@80
   824
  /// <tt>m1[x]+m2[x]</tt>.
kpeter@80
   825
  ///
kpeter@80
   826
  /// \relates AddMap
kpeter@80
   827
  template<typename M1, typename M2>
kpeter@80
   828
  inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) {
alpar@25
   829
    return AddMap<M1, M2>(m1,m2);
alpar@25
   830
  }
alpar@25
   831
alpar@25
   832
kpeter@80
   833
  /// Difference of two maps
kpeter@80
   834
kpeter@82
   835
  /// This \ref concepts::ReadMap "read-only map" returns the difference
kpeter@80
   836
  /// of the values of the two given maps.
kpeter@80
   837
  /// Its \c Key and \c Value types are inherited from \c M1.
kpeter@80
   838
  /// The \c Key and \c Value of \c M2 must be convertible to those of
kpeter@80
   839
  /// \c M1.
alpar@25
   840
  ///
kpeter@80
   841
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@80
   842
  /// \code
kpeter@80
   843
  ///   SubMap<M1,M2> sm(m1,m2);
kpeter@80
   844
  /// \endcode
kpeter@80
   845
  /// <tt>sm[x]</tt> will be equal to <tt>m1[x]-m2[x]</tt>.
kpeter@29
   846
  ///
kpeter@80
   847
  /// The simplest way of using this map is through the subMap()
kpeter@80
   848
  /// function.
kpeter@80
   849
  ///
kpeter@80
   850
  /// \sa AddMap, MulMap, DivMap
kpeter@80
   851
  template<typename M1, typename M2>
kpeter@80
   852
  class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80
   853
    const M1 &_m1;
kpeter@80
   854
    const M2 &_m2;
kpeter@80
   855
  public:
kpeter@559
   856
    ///\e
kpeter@559
   857
    typedef typename M1::Key Key;
kpeter@559
   858
    ///\e
kpeter@559
   859
    typedef typename M1::Value Value;
kpeter@80
   860
kpeter@80
   861
    /// Constructor
kpeter@80
   862
    SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559
   863
    ///\e
kpeter@80
   864
    Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
kpeter@80
   865
  };
kpeter@80
   866
kpeter@301
   867
  /// Returns a \c SubMap class
kpeter@301
   868
kpeter@301
   869
  /// This function just returns a \c SubMap class.
kpeter@80
   870
  ///
kpeter@80
   871
  /// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80
   872
  /// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to
kpeter@80
   873
  /// <tt>m1[x]-m2[x]</tt>.
kpeter@80
   874
  ///
kpeter@80
   875
  /// \relates SubMap
kpeter@80
   876
  template<typename M1, typename M2>
kpeter@80
   877
  inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
kpeter@80
   878
    return SubMap<M1, M2>(m1,m2);
kpeter@80
   879
  }
kpeter@80
   880
kpeter@80
   881
kpeter@80
   882
  /// Product of two maps
kpeter@80
   883
kpeter@82
   884
  /// This \ref concepts::ReadMap "read-only map" returns the product
kpeter@80
   885
  /// of the values of the two given maps.
kpeter@80
   886
  /// Its \c Key and \c Value types are inherited from \c M1.
kpeter@80
   887
  /// The \c Key and \c Value of \c M2 must be convertible to those of
kpeter@80
   888
  /// \c M1.
kpeter@80
   889
  ///
kpeter@80
   890
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@80
   891
  /// \code
kpeter@80
   892
  ///   MulMap<M1,M2> mm(m1,m2);
kpeter@80
   893
  /// \endcode
kpeter@80
   894
  /// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>.
kpeter@80
   895
  ///
kpeter@80
   896
  /// The simplest way of using this map is through the mulMap()
kpeter@80
   897
  /// function.
kpeter@80
   898
  ///
kpeter@80
   899
  /// \sa AddMap, SubMap, DivMap
kpeter@80
   900
  /// \sa ScaleMap, ScaleWriteMap
kpeter@80
   901
  template<typename M1, typename M2>
kpeter@80
   902
  class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80
   903
    const M1 &_m1;
kpeter@80
   904
    const M2 &_m2;
kpeter@80
   905
  public:
kpeter@559
   906
    ///\e
kpeter@559
   907
    typedef typename M1::Key Key;
kpeter@559
   908
    ///\e
kpeter@559
   909
    typedef typename M1::Value Value;
kpeter@80
   910
kpeter@80
   911
    /// Constructor
kpeter@80
   912
    MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559
   913
    ///\e
kpeter@80
   914
    Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
kpeter@80
   915
  };
kpeter@80
   916
kpeter@301
   917
  /// Returns a \c MulMap class
kpeter@301
   918
kpeter@301
   919
  /// This function just returns a \c MulMap class.
kpeter@80
   920
  ///
kpeter@80
   921
  /// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80
   922
  /// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to
kpeter@80
   923
  /// <tt>m1[x]*m2[x]</tt>.
kpeter@80
   924
  ///
kpeter@80
   925
  /// \relates MulMap
kpeter@80
   926
  template<typename M1, typename M2>
kpeter@80
   927
  inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
kpeter@80
   928
    return MulMap<M1, M2>(m1,m2);
kpeter@80
   929
  }
kpeter@80
   930
kpeter@80
   931
kpeter@80
   932
  /// Quotient of two maps
kpeter@80
   933
kpeter@82
   934
  /// This \ref concepts::ReadMap "read-only map" returns the quotient
kpeter@80
   935
  /// of the values of the two given maps.
kpeter@80
   936
  /// Its \c Key and \c Value types are inherited from \c M1.
kpeter@80
   937
  /// The \c Key and \c Value of \c M2 must be convertible to those of
kpeter@80
   938
  /// \c M1.
kpeter@80
   939
  ///
kpeter@80
   940
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@80
   941
  /// \code
kpeter@80
   942
  ///   DivMap<M1,M2> dm(m1,m2);
kpeter@80
   943
  /// \endcode
kpeter@80
   944
  /// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>.
kpeter@80
   945
  ///
kpeter@80
   946
  /// The simplest way of using this map is through the divMap()
kpeter@80
   947
  /// function.
kpeter@80
   948
  ///
kpeter@80
   949
  /// \sa AddMap, SubMap, MulMap
kpeter@80
   950
  template<typename M1, typename M2>
kpeter@80
   951
  class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
kpeter@80
   952
    const M1 &_m1;
kpeter@80
   953
    const M2 &_m2;
kpeter@80
   954
  public:
kpeter@559
   955
    ///\e
kpeter@559
   956
    typedef typename M1::Key Key;
kpeter@559
   957
    ///\e
kpeter@559
   958
    typedef typename M1::Value Value;
kpeter@80
   959
kpeter@80
   960
    /// Constructor
kpeter@80
   961
    DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559
   962
    ///\e
kpeter@80
   963
    Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
kpeter@80
   964
  };
kpeter@80
   965
kpeter@301
   966
  /// Returns a \c DivMap class
kpeter@301
   967
kpeter@301
   968
  /// This function just returns a \c DivMap class.
kpeter@80
   969
  ///
kpeter@80
   970
  /// For example, if \c m1 and \c m2 are both maps with \c double
kpeter@80
   971
  /// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to
kpeter@80
   972
  /// <tt>m1[x]/m2[x]</tt>.
kpeter@80
   973
  ///
kpeter@80
   974
  /// \relates DivMap
kpeter@80
   975
  template<typename M1, typename M2>
kpeter@80
   976
  inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
kpeter@80
   977
    return DivMap<M1, M2>(m1,m2);
kpeter@80
   978
  }
kpeter@80
   979
kpeter@80
   980
kpeter@80
   981
  /// Shifts a map with a constant.
kpeter@80
   982
kpeter@82
   983
  /// This \ref concepts::ReadMap "read-only map" returns the sum of
kpeter@80
   984
  /// the given map and a constant value (i.e. it shifts the map with
kpeter@80
   985
  /// the constant). Its \c Key and \c Value are inherited from \c M.
kpeter@80
   986
  ///
kpeter@80
   987
  /// Actually,
kpeter@80
   988
  /// \code
kpeter@80
   989
  ///   ShiftMap<M> sh(m,v);
kpeter@80
   990
  /// \endcode
kpeter@80
   991
  /// is equivalent to
kpeter@80
   992
  /// \code
kpeter@80
   993
  ///   ConstMap<M::Key, M::Value> cm(v);
kpeter@80
   994
  ///   AddMap<M, ConstMap<M::Key, M::Value> > sh(m,cm);
kpeter@80
   995
  /// \endcode
kpeter@80
   996
  ///
kpeter@80
   997
  /// The simplest way of using this map is through the shiftMap()
kpeter@80
   998
  /// function.
kpeter@80
   999
  ///
kpeter@80
  1000
  /// \sa ShiftWriteMap
kpeter@80
  1001
  template<typename M, typename C = typename M::Value>
alpar@25
  1002
  class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
  1003
    const M &_m;
kpeter@80
  1004
    C _v;
alpar@25
  1005
  public:
kpeter@559
  1006
    ///\e
kpeter@559
  1007
    typedef typename M::Key Key;
kpeter@559
  1008
    ///\e
kpeter@559
  1009
    typedef typename M::Value Value;
alpar@25
  1010
kpeter@80
  1011
    /// Constructor
alpar@25
  1012
kpeter@80
  1013
    /// Constructor.
kpeter@80
  1014
    /// \param m The undelying map.
kpeter@80
  1015
    /// \param v The constant value.
kpeter@80
  1016
    ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
kpeter@559
  1017
    ///\e
kpeter@80
  1018
    Value operator[](const Key &k) const { return _m[k]+_v; }
alpar@25
  1019
  };
alpar@25
  1020
kpeter@80
  1021
  /// Shifts a map with a constant (read-write version).
alpar@25
  1022
kpeter@80
  1023
  /// This \ref concepts::ReadWriteMap "read-write map" returns the sum
kpeter@80
  1024
  /// of the given map and a constant value (i.e. it shifts the map with
kpeter@80
  1025
  /// the constant). Its \c Key and \c Value are inherited from \c M.
kpeter@80
  1026
  /// It makes also possible to write the map.
alpar@25
  1027
  ///
kpeter@80
  1028
  /// The simplest way of using this map is through the shiftWriteMap()
kpeter@80
  1029
  /// function.
kpeter@80
  1030
  ///
kpeter@80
  1031
  /// \sa ShiftMap
kpeter@80
  1032
  template<typename M, typename C = typename M::Value>
alpar@25
  1033
  class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
  1034
    M &_m;
kpeter@80
  1035
    C _v;
alpar@25
  1036
  public:
kpeter@559
  1037
    ///\e
kpeter@559
  1038
    typedef typename M::Key Key;
kpeter@559
  1039
    ///\e
kpeter@559
  1040
    typedef typename M::Value Value;
alpar@25
  1041
kpeter@80
  1042
    /// Constructor
alpar@25
  1043
kpeter@80
  1044
    /// Constructor.
kpeter@80
  1045
    /// \param m The undelying map.
kpeter@80
  1046
    /// \param v The constant value.
kpeter@80
  1047
    ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
kpeter@559
  1048
    ///\e
kpeter@80
  1049
    Value operator[](const Key &k) const { return _m[k]+_v; }
kpeter@559
  1050
    ///\e
kpeter@80
  1051
    void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
alpar@25
  1052
  };
alpar@25
  1053
kpeter@301
  1054
  /// Returns a \c ShiftMap class
kpeter@301
  1055
kpeter@301
  1056
  /// This function just returns a \c ShiftMap class.
kpeter@80
  1057
  ///
kpeter@80
  1058
  /// For example, if \c m is a map with \c double values and \c v is
kpeter@80
  1059
  /// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to
kpeter@80
  1060
  /// <tt>m[x]+v</tt>.
kpeter@80
  1061
  ///
kpeter@80
  1062
  /// \relates ShiftMap
kpeter@80
  1063
  template<typename M, typename C>
kpeter@80
  1064
  inline ShiftMap<M, C> shiftMap(const M &m, const C &v) {
alpar@25
  1065
    return ShiftMap<M, C>(m,v);
alpar@25
  1066
  }
alpar@25
  1067
kpeter@301
  1068
  /// Returns a \c ShiftWriteMap class
kpeter@301
  1069
kpeter@301
  1070
  /// This function just returns a \c ShiftWriteMap class.
kpeter@80
  1071
  ///
kpeter@80
  1072
  /// For example, if \c m is a map with \c double values and \c v is
kpeter@80
  1073
  /// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to
kpeter@80
  1074
  /// <tt>m[x]+v</tt>.
kpeter@80
  1075
  /// Moreover it makes also possible to write the map.
kpeter@80
  1076
  ///
kpeter@80
  1077
  /// \relates ShiftWriteMap
kpeter@80
  1078
  template<typename M, typename C>
kpeter@80
  1079
  inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) {
alpar@25
  1080
    return ShiftWriteMap<M, C>(m,v);
alpar@25
  1081
  }
alpar@25
  1082
alpar@25
  1083
kpeter@80
  1084
  /// Scales a map with a constant.
kpeter@80
  1085
kpeter@82
  1086
  /// This \ref concepts::ReadMap "read-only map" returns the value of
kpeter@80
  1087
  /// the given map multiplied from the left side with a constant value.
kpeter@80
  1088
  /// Its \c Key and \c Value are inherited from \c M.
alpar@26
  1089
  ///
kpeter@80
  1090
  /// Actually,
kpeter@80
  1091
  /// \code
kpeter@80
  1092
  ///   ScaleMap<M> sc(m,v);
kpeter@80
  1093
  /// \endcode
kpeter@80
  1094
  /// is equivalent to
kpeter@80
  1095
  /// \code
kpeter@80
  1096
  ///   ConstMap<M::Key, M::Value> cm(v);
kpeter@80
  1097
  ///   MulMap<ConstMap<M::Key, M::Value>, M> sc(cm,m);
kpeter@80
  1098
  /// \endcode
alpar@25
  1099
  ///
kpeter@80
  1100
  /// The simplest way of using this map is through the scaleMap()
kpeter@80
  1101
  /// function.
alpar@25
  1102
  ///
kpeter@80
  1103
  /// \sa ScaleWriteMap
kpeter@80
  1104
  template<typename M, typename C = typename M::Value>
alpar@25
  1105
  class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
  1106
    const M &_m;
kpeter@80
  1107
    C _v;
alpar@25
  1108
  public:
kpeter@559
  1109
    ///\e
kpeter@559
  1110
    typedef typename M::Key Key;
kpeter@559
  1111
    ///\e
kpeter@559
  1112
    typedef typename M::Value Value;
alpar@25
  1113
kpeter@80
  1114
    /// Constructor
alpar@25
  1115
kpeter@80
  1116
    /// Constructor.
kpeter@80
  1117
    /// \param m The undelying map.
kpeter@80
  1118
    /// \param v The constant value.
kpeter@80
  1119
    ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
kpeter@559
  1120
    ///\e
kpeter@80
  1121
    Value operator[](const Key &k) const { return _v*_m[k]; }
alpar@25
  1122
  };
alpar@25
  1123
kpeter@80
  1124
  /// Scales a map with a constant (read-write version).
alpar@25
  1125
kpeter@80
  1126
  /// This \ref concepts::ReadWriteMap "read-write map" returns the value of
kpeter@80
  1127
  /// the given map multiplied from the left side with a constant value.
kpeter@80
  1128
  /// Its \c Key and \c Value are inherited from \c M.
kpeter@80
  1129
  /// It can also be used as write map if the \c / operator is defined
kpeter@80
  1130
  /// between \c Value and \c C and the given multiplier is not zero.
kpeter@29
  1131
  ///
kpeter@80
  1132
  /// The simplest way of using this map is through the scaleWriteMap()
kpeter@80
  1133
  /// function.
kpeter@80
  1134
  ///
kpeter@80
  1135
  /// \sa ScaleMap
kpeter@80
  1136
  template<typename M, typename C = typename M::Value>
alpar@25
  1137
  class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
  1138
    M &_m;
kpeter@80
  1139
    C _v;
alpar@25
  1140
  public:
kpeter@559
  1141
    ///\e
kpeter@559
  1142
    typedef typename M::Key Key;
kpeter@559
  1143
    ///\e
kpeter@559
  1144
    typedef typename M::Value Value;
alpar@25
  1145
kpeter@80
  1146
    /// Constructor
alpar@25
  1147
kpeter@80
  1148
    /// Constructor.
kpeter@80
  1149
    /// \param m The undelying map.
kpeter@80
  1150
    /// \param v The constant value.
kpeter@80
  1151
    ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
kpeter@559
  1152
    ///\e
kpeter@80
  1153
    Value operator[](const Key &k) const { return _v*_m[k]; }
kpeter@559
  1154
    ///\e
kpeter@80
  1155
    void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
alpar@25
  1156
  };
alpar@25
  1157
kpeter@301
  1158
  /// Returns a \c ScaleMap class
kpeter@301
  1159
kpeter@301
  1160
  /// This function just returns a \c ScaleMap class.
kpeter@80
  1161
  ///
kpeter@80
  1162
  /// For example, if \c m is a map with \c double values and \c v is
kpeter@80
  1163
  /// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to
kpeter@80
  1164
  /// <tt>v*m[x]</tt>.
kpeter@80
  1165
  ///
kpeter@80
  1166
  /// \relates ScaleMap
kpeter@80
  1167
  template<typename M, typename C>
kpeter@80
  1168
  inline ScaleMap<M, C> scaleMap(const M &m, const C &v) {
alpar@25
  1169
    return ScaleMap<M, C>(m,v);
alpar@25
  1170
  }
alpar@25
  1171
kpeter@301
  1172
  /// Returns a \c ScaleWriteMap class
kpeter@301
  1173
kpeter@301
  1174
  /// This function just returns a \c ScaleWriteMap class.
kpeter@80
  1175
  ///
kpeter@80
  1176
  /// For example, if \c m is a map with \c double values and \c v is
kpeter@80
  1177
  /// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to
kpeter@80
  1178
  /// <tt>v*m[x]</tt>.
kpeter@80
  1179
  /// Moreover it makes also possible to write the map.
kpeter@80
  1180
  ///
kpeter@80
  1181
  /// \relates ScaleWriteMap
kpeter@80
  1182
  template<typename M, typename C>
kpeter@80
  1183
  inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) {
alpar@25
  1184
    return ScaleWriteMap<M, C>(m,v);
alpar@25
  1185
  }
alpar@25
  1186
alpar@25
  1187
kpeter@80
  1188
  /// Negative of a map
alpar@25
  1189
kpeter@82
  1190
  /// This \ref concepts::ReadMap "read-only map" returns the negative
kpeter@80
  1191
  /// of the values of the given map (using the unary \c - operator).
kpeter@80
  1192
  /// Its \c Key and \c Value are inherited from \c M.
alpar@25
  1193
  ///
kpeter@80
  1194
  /// If M::Value is \c int, \c double etc., then
kpeter@80
  1195
  /// \code
kpeter@80
  1196
  ///   NegMap<M> neg(m);
kpeter@80
  1197
  /// \endcode
kpeter@80
  1198
  /// is equivalent to
kpeter@80
  1199
  /// \code
kpeter@80
  1200
  ///   ScaleMap<M> neg(m,-1);
kpeter@80
  1201
  /// \endcode
kpeter@29
  1202
  ///
kpeter@80
  1203
  /// The simplest way of using this map is through the negMap()
kpeter@80
  1204
  /// function.
kpeter@29
  1205
  ///
kpeter@80
  1206
  /// \sa NegWriteMap
kpeter@80
  1207
  template<typename M>
alpar@25
  1208
  class NegMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
  1209
    const M& _m;
alpar@25
  1210
  public:
kpeter@559
  1211
    ///\e
kpeter@559
  1212
    typedef typename M::Key Key;
kpeter@559
  1213
    ///\e
kpeter@559
  1214
    typedef typename M::Value Value;
alpar@25
  1215
kpeter@80
  1216
    /// Constructor
kpeter@80
  1217
    NegMap(const M &m) : _m(m) {}
kpeter@559
  1218
    ///\e
kpeter@80
  1219
    Value operator[](const Key &k) const { return -_m[k]; }
alpar@25
  1220
  };
alpar@25
  1221
kpeter@80
  1222
  /// Negative of a map (read-write version)
kpeter@80
  1223
kpeter@80
  1224
  /// This \ref concepts::ReadWriteMap "read-write map" returns the
kpeter@80
  1225
  /// negative of the values of the given map (using the unary \c -
kpeter@80
  1226
  /// operator).
kpeter@80
  1227
  /// Its \c Key and \c Value are inherited from \c M.
kpeter@80
  1228
  /// It makes also possible to write the map.
kpeter@80
  1229
  ///
kpeter@80
  1230
  /// If M::Value is \c int, \c double etc., then
kpeter@80
  1231
  /// \code
kpeter@80
  1232
  ///   NegWriteMap<M> neg(m);
kpeter@80
  1233
  /// \endcode
kpeter@80
  1234
  /// is equivalent to
kpeter@80
  1235
  /// \code
kpeter@80
  1236
  ///   ScaleWriteMap<M> neg(m,-1);
kpeter@80
  1237
  /// \endcode
kpeter@80
  1238
  ///
kpeter@80
  1239
  /// The simplest way of using this map is through the negWriteMap()
kpeter@80
  1240
  /// function.
kpeter@29
  1241
  ///
kpeter@29
  1242
  /// \sa NegMap
kpeter@80
  1243
  template<typename M>
alpar@25
  1244
  class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
  1245
    M &_m;
alpar@25
  1246
  public:
kpeter@559
  1247
    ///\e
kpeter@559
  1248
    typedef typename M::Key Key;
kpeter@559
  1249
    ///\e
kpeter@559
  1250
    typedef typename M::Value Value;
alpar@25
  1251
kpeter@80
  1252
    /// Constructor
kpeter@80
  1253
    NegWriteMap(M &m) : _m(m) {}
kpeter@559
  1254
    ///\e
kpeter@80
  1255
    Value operator[](const Key &k) const { return -_m[k]; }
kpeter@559
  1256
    ///\e
kpeter@80
  1257
    void set(const Key &k, const Value &v) { _m.set(k, -v); }
alpar@25
  1258
  };
alpar@25
  1259
kpeter@301
  1260
  /// Returns a \c NegMap class
kpeter@301
  1261
kpeter@301
  1262
  /// This function just returns a \c NegMap class.
kpeter@80
  1263
  ///
kpeter@80
  1264
  /// For example, if \c m is a map with \c double values, then
kpeter@80
  1265
  /// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
kpeter@80
  1266
  ///
kpeter@80
  1267
  /// \relates NegMap
kpeter@80
  1268
  template <typename M>
alpar@25
  1269
  inline NegMap<M> negMap(const M &m) {
alpar@25
  1270
    return NegMap<M>(m);
alpar@25
  1271
  }
alpar@25
  1272
kpeter@301
  1273
  /// Returns a \c NegWriteMap class
kpeter@301
  1274
kpeter@301
  1275
  /// This function just returns a \c NegWriteMap class.
kpeter@80
  1276
  ///
kpeter@80
  1277
  /// For example, if \c m is a map with \c double values, then
kpeter@80
  1278
  /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
kpeter@80
  1279
  /// Moreover it makes also possible to write the map.
kpeter@80
  1280
  ///
kpeter@80
  1281
  /// \relates NegWriteMap
kpeter@80
  1282
  template <typename M>
kpeter@80
  1283
  inline NegWriteMap<M> negWriteMap(M &m) {
alpar@25
  1284
    return NegWriteMap<M>(m);
alpar@25
  1285
  }
alpar@25
  1286
alpar@25
  1287
kpeter@80
  1288
  /// Absolute value of a map
kpeter@80
  1289
kpeter@82
  1290
  /// This \ref concepts::ReadMap "read-only map" returns the absolute
kpeter@80
  1291
  /// value of the values of the given map.
kpeter@80
  1292
  /// Its \c Key and \c Value are inherited from \c M.
kpeter@80
  1293
  /// \c Value must be comparable to \c 0 and the unary \c -
kpeter@80
  1294
  /// operator must be defined for it, of course.
kpeter@80
  1295
  ///
kpeter@80
  1296
  /// The simplest way of using this map is through the absMap()
kpeter@80
  1297
  /// function.
kpeter@80
  1298
  template<typename M>
alpar@25
  1299
  class AbsMap : public MapBase<typename M::Key, typename M::Value> {
kpeter@80
  1300
    const M &_m;
alpar@25
  1301
  public:
kpeter@559
  1302
    ///\e
kpeter@559
  1303
    typedef typename M::Key Key;
kpeter@559
  1304
    ///\e
kpeter@559
  1305
    typedef typename M::Value Value;
alpar@25
  1306
kpeter@80
  1307
    /// Constructor
kpeter@80
  1308
    AbsMap(const M &m) : _m(m) {}
kpeter@559
  1309
    ///\e
kpeter@80
  1310
    Value operator[](const Key &k) const {
kpeter@80
  1311
      Value tmp = _m[k];
alpar@25
  1312
      return tmp >= 0 ? tmp : -tmp;
alpar@25
  1313
    }
alpar@25
  1314
alpar@25
  1315
  };
alpar@25
  1316
kpeter@301
  1317
  /// Returns an \c AbsMap class
kpeter@301
  1318
kpeter@301
  1319
  /// This function just returns an \c AbsMap class.
kpeter@80
  1320
  ///
kpeter@80
  1321
  /// For example, if \c m is a map with \c double values, then
kpeter@80
  1322
  /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if
kpeter@80
  1323
  /// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is
kpeter@80
  1324
  /// negative.
kpeter@80
  1325
  ///
kpeter@80
  1326
  /// \relates AbsMap
kpeter@80
  1327
  template<typename M>
alpar@25
  1328
  inline AbsMap<M> absMap(const M &m) {
alpar@25
  1329
    return AbsMap<M>(m);
alpar@25
  1330
  }
alpar@25
  1331
kpeter@82
  1332
  /// @}
alpar@209
  1333
kpeter@82
  1334
  // Logical maps and map adaptors:
kpeter@82
  1335
kpeter@82
  1336
  /// \addtogroup maps
kpeter@82
  1337
  /// @{
kpeter@82
  1338
kpeter@82
  1339
  /// Constant \c true map.
kpeter@82
  1340
kpeter@82
  1341
  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
kpeter@82
  1342
  /// each key.
kpeter@82
  1343
  ///
kpeter@82
  1344
  /// Note that
kpeter@82
  1345
  /// \code
kpeter@82
  1346
  ///   TrueMap<K> tm;
kpeter@82
  1347
  /// \endcode
kpeter@82
  1348
  /// is equivalent to
kpeter@82
  1349
  /// \code
kpeter@82
  1350
  ///   ConstMap<K,bool> tm(true);
kpeter@82
  1351
  /// \endcode
kpeter@82
  1352
  ///
kpeter@82
  1353
  /// \sa FalseMap
kpeter@82
  1354
  /// \sa ConstMap
kpeter@82
  1355
  template <typename K>
kpeter@82
  1356
  class TrueMap : public MapBase<K, bool> {
kpeter@82
  1357
  public:
kpeter@559
  1358
    ///\e
kpeter@559
  1359
    typedef K Key;
kpeter@559
  1360
    ///\e
kpeter@559
  1361
    typedef bool Value;
kpeter@82
  1362
kpeter@82
  1363
    /// Gives back \c true.
kpeter@82
  1364
    Value operator[](const Key&) const { return true; }
kpeter@82
  1365
  };
kpeter@82
  1366
kpeter@301
  1367
  /// Returns a \c TrueMap class
kpeter@301
  1368
kpeter@301
  1369
  /// This function just returns a \c TrueMap class.
kpeter@82
  1370
  /// \relates TrueMap
kpeter@82
  1371
  template<typename K>
kpeter@82
  1372
  inline TrueMap<K> trueMap() {
kpeter@82
  1373
    return TrueMap<K>();
kpeter@82
  1374
  }
kpeter@82
  1375
kpeter@82
  1376
kpeter@82
  1377
  /// Constant \c false map.
kpeter@82
  1378
kpeter@82
  1379
  /// This \ref concepts::ReadMap "read-only map" assigns \c false to
kpeter@82
  1380
  /// each key.
kpeter@82
  1381
  ///
kpeter@82
  1382
  /// Note that
kpeter@82
  1383
  /// \code
kpeter@82
  1384
  ///   FalseMap<K> fm;
kpeter@82
  1385
  /// \endcode
kpeter@82
  1386
  /// is equivalent to
kpeter@82
  1387
  /// \code
kpeter@82
  1388
  ///   ConstMap<K,bool> fm(false);
kpeter@82
  1389
  /// \endcode
kpeter@82
  1390
  ///
kpeter@82
  1391
  /// \sa TrueMap
kpeter@82
  1392
  /// \sa ConstMap
kpeter@82
  1393
  template <typename K>
kpeter@82
  1394
  class FalseMap : public MapBase<K, bool> {
kpeter@82
  1395
  public:
kpeter@559
  1396
    ///\e
kpeter@559
  1397
    typedef K Key;
kpeter@559
  1398
    ///\e
kpeter@559
  1399
    typedef bool Value;
kpeter@82
  1400
kpeter@82
  1401
    /// Gives back \c false.
kpeter@82
  1402
    Value operator[](const Key&) const { return false; }
kpeter@82
  1403
  };
kpeter@82
  1404
kpeter@301
  1405
  /// Returns a \c FalseMap class
kpeter@301
  1406
kpeter@301
  1407
  /// This function just returns a \c FalseMap class.
kpeter@82
  1408
  /// \relates FalseMap
kpeter@82
  1409
  template<typename K>
kpeter@82
  1410
  inline FalseMap<K> falseMap() {
kpeter@82
  1411
    return FalseMap<K>();
kpeter@82
  1412
  }
kpeter@82
  1413
kpeter@82
  1414
  /// @}
kpeter@82
  1415
kpeter@82
  1416
  /// \addtogroup map_adaptors
kpeter@82
  1417
  /// @{
kpeter@82
  1418
kpeter@82
  1419
  /// Logical 'and' of two maps
kpeter@82
  1420
kpeter@82
  1421
  /// This \ref concepts::ReadMap "read-only map" returns the logical
kpeter@82
  1422
  /// 'and' of the values of the two given maps.
kpeter@82
  1423
  /// Its \c Key type is inherited from \c M1 and its \c Value type is
kpeter@82
  1424
  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
kpeter@82
  1425
  ///
kpeter@82
  1426
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@82
  1427
  /// \code
kpeter@82
  1428
  ///   AndMap<M1,M2> am(m1,m2);
kpeter@82
  1429
  /// \endcode
kpeter@82
  1430
  /// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>.
kpeter@82
  1431
  ///
kpeter@82
  1432
  /// The simplest way of using this map is through the andMap()
kpeter@82
  1433
  /// function.
kpeter@82
  1434
  ///
kpeter@82
  1435
  /// \sa OrMap
kpeter@82
  1436
  /// \sa NotMap, NotWriteMap
kpeter@82
  1437
  template<typename M1, typename M2>
kpeter@82
  1438
  class AndMap : public MapBase<typename M1::Key, bool> {
kpeter@82
  1439
    const M1 &_m1;
kpeter@82
  1440
    const M2 &_m2;
kpeter@82
  1441
  public:
kpeter@559
  1442
    ///\e
kpeter@559
  1443
    typedef typename M1::Key Key;
kpeter@559
  1444
    ///\e
kpeter@559
  1445
    typedef bool Value;
kpeter@82
  1446
kpeter@82
  1447
    /// Constructor
kpeter@82
  1448
    AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559
  1449
    ///\e
kpeter@82
  1450
    Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
kpeter@82
  1451
  };
kpeter@82
  1452
kpeter@301
  1453
  /// Returns an \c AndMap class
kpeter@301
  1454
kpeter@301
  1455
  /// This function just returns an \c AndMap class.
kpeter@82
  1456
  ///
kpeter@82
  1457
  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
kpeter@82
  1458
  /// then <tt>andMap(m1,m2)[x]</tt> will be equal to
kpeter@82
  1459
  /// <tt>m1[x]&&m2[x]</tt>.
kpeter@82
  1460
  ///
kpeter@82
  1461
  /// \relates AndMap
kpeter@82
  1462
  template<typename M1, typename M2>
kpeter@82
  1463
  inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) {
kpeter@82
  1464
    return AndMap<M1, M2>(m1,m2);
kpeter@82
  1465
  }
kpeter@82
  1466
kpeter@82
  1467
kpeter@82
  1468
  /// Logical 'or' of two maps
kpeter@82
  1469
kpeter@82
  1470
  /// This \ref concepts::ReadMap "read-only map" returns the logical
kpeter@82
  1471
  /// 'or' of the values of the two given maps.
kpeter@82
  1472
  /// Its \c Key type is inherited from \c M1 and its \c Value type is
kpeter@82
  1473
  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
kpeter@82
  1474
  ///
kpeter@82
  1475
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@82
  1476
  /// \code
kpeter@82
  1477
  ///   OrMap<M1,M2> om(m1,m2);
kpeter@82
  1478
  /// \endcode
kpeter@82
  1479
  /// <tt>om[x]</tt> will be equal to <tt>m1[x]||m2[x]</tt>.
kpeter@82
  1480
  ///
kpeter@82
  1481
  /// The simplest way of using this map is through the orMap()
kpeter@82
  1482
  /// function.
kpeter@82
  1483
  ///
kpeter@82
  1484
  /// \sa AndMap
kpeter@82
  1485
  /// \sa NotMap, NotWriteMap
kpeter@82
  1486
  template<typename M1, typename M2>
kpeter@82
  1487
  class OrMap : public MapBase<typename M1::Key, bool> {
kpeter@82
  1488
    const M1 &_m1;
kpeter@82
  1489
    const M2 &_m2;
kpeter@82
  1490
  public:
kpeter@559
  1491
    ///\e
kpeter@559
  1492
    typedef typename M1::Key Key;
kpeter@559
  1493
    ///\e
kpeter@559
  1494
    typedef bool Value;
kpeter@82
  1495
kpeter@82
  1496
    /// Constructor
kpeter@82
  1497
    OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559
  1498
    ///\e
kpeter@82
  1499
    Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
kpeter@82
  1500
  };
kpeter@82
  1501
kpeter@301
  1502
  /// Returns an \c OrMap class
kpeter@301
  1503
kpeter@301
  1504
  /// This function just returns an \c OrMap class.
kpeter@82
  1505
  ///
kpeter@82
  1506
  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
kpeter@82
  1507
  /// then <tt>orMap(m1,m2)[x]</tt> will be equal to
kpeter@82
  1508
  /// <tt>m1[x]||m2[x]</tt>.
kpeter@82
  1509
  ///
kpeter@82
  1510
  /// \relates OrMap
kpeter@82
  1511
  template<typename M1, typename M2>
kpeter@82
  1512
  inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) {
kpeter@82
  1513
    return OrMap<M1, M2>(m1,m2);
kpeter@82
  1514
  }
kpeter@82
  1515
alpar@25
  1516
kpeter@80
  1517
  /// Logical 'not' of a map
kpeter@80
  1518
kpeter@82
  1519
  /// This \ref concepts::ReadMap "read-only map" returns the logical
kpeter@80
  1520
  /// negation of the values of the given map.
kpeter@80
  1521
  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
alpar@25
  1522
  ///
kpeter@80
  1523
  /// The simplest way of using this map is through the notMap()
kpeter@80
  1524
  /// function.
alpar@25
  1525
  ///
kpeter@80
  1526
  /// \sa NotWriteMap
kpeter@80
  1527
  template <typename M>
alpar@25
  1528
  class NotMap : public MapBase<typename M::Key, bool> {
kpeter@80
  1529
    const M &_m;
alpar@25
  1530
  public:
kpeter@559
  1531
    ///\e
kpeter@559
  1532
    typedef typename M::Key Key;
kpeter@559
  1533
    ///\e
kpeter@559
  1534
    typedef bool Value;
alpar@25
  1535
alpar@25
  1536
    /// Constructor
kpeter@80
  1537
    NotMap(const M &m) : _m(m) {}
kpeter@559
  1538
    ///\e
kpeter@80
  1539
    Value operator[](const Key &k) const { return !_m[k]; }
alpar@25
  1540
  };
alpar@25
  1541
kpeter@80
  1542
  /// Logical 'not' of a map (read-write version)
kpeter@80
  1543
kpeter@80
  1544
  /// This \ref concepts::ReadWriteMap "read-write map" returns the
kpeter@80
  1545
  /// logical negation of the values of the given map.
kpeter@80
  1546
  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
kpeter@80
  1547
  /// It makes also possible to write the map. When a value is set,
kpeter@80
  1548
  /// the opposite value is set to the original map.
kpeter@29
  1549
  ///
kpeter@80
  1550
  /// The simplest way of using this map is through the notWriteMap()
kpeter@80
  1551
  /// function.
kpeter@80
  1552
  ///
kpeter@80
  1553
  /// \sa NotMap
kpeter@80
  1554
  template <typename M>
alpar@25
  1555
  class NotWriteMap : public MapBase<typename M::Key, bool> {
kpeter@80
  1556
    M &_m;
alpar@25
  1557
  public:
kpeter@559
  1558
    ///\e
kpeter@559
  1559
    typedef typename M::Key Key;
kpeter@559
  1560
    ///\e
kpeter@559
  1561
    typedef bool Value;
alpar@25
  1562
alpar@25
  1563
    /// Constructor
kpeter@80
  1564
    NotWriteMap(M &m) : _m(m) {}
kpeter@559
  1565
    ///\e
kpeter@80
  1566
    Value operator[](const Key &k) const { return !_m[k]; }
kpeter@559
  1567
    ///\e
kpeter@80
  1568
    void set(const Key &k, bool v) { _m.set(k, !v); }
alpar@25
  1569
  };
kpeter@80
  1570
kpeter@301
  1571
  /// Returns a \c NotMap class
kpeter@301
  1572
kpeter@301
  1573
  /// This function just returns a \c NotMap class.
kpeter@80
  1574
  ///
kpeter@80
  1575
  /// For example, if \c m is a map with \c bool values, then
kpeter@80
  1576
  /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
kpeter@80
  1577
  ///
kpeter@80
  1578
  /// \relates NotMap
kpeter@80
  1579
  template <typename M>
alpar@25
  1580
  inline NotMap<M> notMap(const M &m) {
alpar@25
  1581
    return NotMap<M>(m);
alpar@25
  1582
  }
kpeter@80
  1583
kpeter@301
  1584
  /// Returns a \c NotWriteMap class
kpeter@301
  1585
kpeter@301
  1586
  /// This function just returns a \c NotWriteMap class.
kpeter@80
  1587
  ///
kpeter@80
  1588
  /// For example, if \c m is a map with \c bool values, then
kpeter@80
  1589
  /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
kpeter@80
  1590
  /// Moreover it makes also possible to write the map.
kpeter@80
  1591
  ///
kpeter@80
  1592
  /// \relates NotWriteMap
kpeter@80
  1593
  template <typename M>
kpeter@80
  1594
  inline NotWriteMap<M> notWriteMap(M &m) {
alpar@25
  1595
    return NotWriteMap<M>(m);
alpar@25
  1596
  }
alpar@25
  1597
kpeter@82
  1598
kpeter@82
  1599
  /// Combination of two maps using the \c == operator
kpeter@82
  1600
kpeter@82
  1601
  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
kpeter@82
  1602
  /// the keys for which the corresponding values of the two maps are
kpeter@82
  1603
  /// equal.
kpeter@82
  1604
  /// Its \c Key type is inherited from \c M1 and its \c Value type is
kpeter@82
  1605
  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
kpeter@82
  1606
  ///
kpeter@82
  1607
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@82
  1608
  /// \code
kpeter@82
  1609
  ///   EqualMap<M1,M2> em(m1,m2);
kpeter@82
  1610
  /// \endcode
kpeter@82
  1611
  /// <tt>em[x]</tt> will be equal to <tt>m1[x]==m2[x]</tt>.
kpeter@82
  1612
  ///
kpeter@82
  1613
  /// The simplest way of using this map is through the equalMap()
kpeter@82
  1614
  /// function.
kpeter@82
  1615
  ///
kpeter@82
  1616
  /// \sa LessMap
kpeter@82
  1617
  template<typename M1, typename M2>
kpeter@82
  1618
  class EqualMap : public MapBase<typename M1::Key, bool> {
kpeter@82
  1619
    const M1 &_m1;
kpeter@82
  1620
    const M2 &_m2;
kpeter@82
  1621
  public:
kpeter@559
  1622
    ///\e
kpeter@559
  1623
    typedef typename M1::Key Key;
kpeter@559
  1624
    ///\e
kpeter@559
  1625
    typedef bool Value;
kpeter@82
  1626
kpeter@82
  1627
    /// Constructor
kpeter@82
  1628
    EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559
  1629
    ///\e
kpeter@82
  1630
    Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
kpeter@82
  1631
  };
kpeter@82
  1632
kpeter@301
  1633
  /// Returns an \c EqualMap class
kpeter@301
  1634
kpeter@301
  1635
  /// This function just returns an \c EqualMap class.
kpeter@82
  1636
  ///
kpeter@82
  1637
  /// For example, if \c m1 and \c m2 are maps with keys and values of
kpeter@82
  1638
  /// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to
kpeter@82
  1639
  /// <tt>m1[x]==m2[x]</tt>.
kpeter@82
  1640
  ///
kpeter@82
  1641
  /// \relates EqualMap
kpeter@82
  1642
  template<typename M1, typename M2>
kpeter@82
  1643
  inline EqualMap<M1, M2> equalMap(const M1 &m1, const M2 &m2) {
kpeter@82
  1644
    return EqualMap<M1, M2>(m1,m2);
kpeter@82
  1645
  }
kpeter@82
  1646
kpeter@82
  1647
kpeter@82
  1648
  /// Combination of two maps using the \c < operator
kpeter@82
  1649
kpeter@82
  1650
  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
kpeter@82
  1651
  /// the keys for which the corresponding value of the first map is
kpeter@82
  1652
  /// less then the value of the second map.
kpeter@82
  1653
  /// Its \c Key type is inherited from \c M1 and its \c Value type is
kpeter@82
  1654
  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
kpeter@82
  1655
  ///
kpeter@82
  1656
  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
kpeter@82
  1657
  /// \code
kpeter@82
  1658
  ///   LessMap<M1,M2> lm(m1,m2);
kpeter@82
  1659
  /// \endcode
kpeter@82
  1660
  /// <tt>lm[x]</tt> will be equal to <tt>m1[x]<m2[x]</tt>.
kpeter@82
  1661
  ///
kpeter@82
  1662
  /// The simplest way of using this map is through the lessMap()
kpeter@82
  1663
  /// function.
kpeter@82
  1664
  ///
kpeter@82
  1665
  /// \sa EqualMap
kpeter@82
  1666
  template<typename M1, typename M2>
kpeter@82
  1667
  class LessMap : public MapBase<typename M1::Key, bool> {
kpeter@82
  1668
    const M1 &_m1;
kpeter@82
  1669
    const M2 &_m2;
kpeter@82
  1670
  public:
kpeter@559
  1671
    ///\e
kpeter@559
  1672
    typedef typename M1::Key Key;
kpeter@559
  1673
    ///\e
kpeter@559
  1674
    typedef bool Value;
kpeter@82
  1675
kpeter@82
  1676
    /// Constructor
kpeter@82
  1677
    LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
kpeter@559
  1678
    ///\e
kpeter@82
  1679
    Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
kpeter@82
  1680
  };
kpeter@82
  1681
kpeter@301
  1682
  /// Returns an \c LessMap class
kpeter@301
  1683
kpeter@301
  1684
  /// This function just returns an \c LessMap class.
kpeter@82
  1685
  ///
kpeter@82
  1686
  /// For example, if \c m1 and \c m2 are maps with keys and values of
kpeter@82
  1687
  /// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to
kpeter@82
  1688
  /// <tt>m1[x]<m2[x]</tt>.
kpeter@82
  1689
  ///
kpeter@82
  1690
  /// \relates LessMap
kpeter@82
  1691
  template<typename M1, typename M2>
kpeter@82
  1692
  inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) {
kpeter@82
  1693
    return LessMap<M1, M2>(m1,m2);
kpeter@82
  1694
  }
kpeter@82
  1695
alpar@104
  1696
  namespace _maps_bits {
alpar@104
  1697
alpar@104
  1698
    template <typename _Iterator, typename Enable = void>
alpar@104
  1699
    struct IteratorTraits {
alpar@104
  1700
      typedef typename std::iterator_traits<_Iterator>::value_type Value;
alpar@104
  1701
    };
alpar@104
  1702
alpar@104
  1703
    template <typename _Iterator>
alpar@104
  1704
    struct IteratorTraits<_Iterator,
alpar@104
  1705
      typename exists<typename _Iterator::container_type>::type>
alpar@104
  1706
    {
alpar@104
  1707
      typedef typename _Iterator::container_type::value_type Value;
alpar@104
  1708
    };
alpar@104
  1709
alpar@104
  1710
  }
alpar@104
  1711
kpeter@314
  1712
  /// @}
kpeter@314
  1713
kpeter@314
  1714
  /// \addtogroup maps
kpeter@314
  1715
  /// @{
kpeter@314
  1716
alpar@104
  1717
  /// \brief Writable bool map for logging each \c true assigned element
alpar@104
  1718
  ///
kpeter@159
  1719
  /// A \ref concepts::WriteMap "writable" bool map for logging
alpar@104
  1720
  /// each \c true assigned element, i.e it copies subsequently each
alpar@104
  1721
  /// keys set to \c true to the given iterator.
kpeter@159
  1722
  /// The most important usage of it is storing certain nodes or arcs
kpeter@159
  1723
  /// that were marked \c true by an algorithm.
alpar@104
  1724
  ///
kpeter@159
  1725
  /// There are several algorithms that provide solutions through bool
kpeter@159
  1726
  /// maps and most of them assign \c true at most once for each key.
kpeter@159
  1727
  /// In these cases it is a natural request to store each \c true
kpeter@159
  1728
  /// assigned elements (in order of the assignment), which can be
kpeter@167
  1729
  /// easily done with LoggerBoolMap.
kpeter@159
  1730
  ///
kpeter@167
  1731
  /// The simplest way of using this map is through the loggerBoolMap()
kpeter@159
  1732
  /// function.
kpeter@159
  1733
  ///
kpeter@559
  1734
  /// \tparam IT The type of the iterator.
kpeter@559
  1735
  /// \tparam KEY The key type of the map. The default value set
kpeter@159
  1736
  /// according to the iterator type should work in most cases.
alpar@104
  1737
  ///
alpar@104
  1738
  /// \note The container of the iterator must contain enough space
kpeter@159
  1739
  /// for the elements or the iterator should be an inserter iterator.
kpeter@159
  1740
#ifdef DOXYGEN
kpeter@559
  1741
  template <typename IT, typename KEY>
kpeter@159
  1742
#else
kpeter@559
  1743
  template <typename IT,
kpeter@559
  1744
            typename KEY = typename _maps_bits::IteratorTraits<IT>::Value>
kpeter@159
  1745
#endif
kpeter@559
  1746
  class LoggerBoolMap : public MapBase<KEY, bool> {
alpar@104
  1747
  public:
kpeter@559
  1748
kpeter@559
  1749
    ///\e
kpeter@559
  1750
    typedef KEY Key;
kpeter@559
  1751
    ///\e
alpar@104
  1752
    typedef bool Value;
kpeter@559
  1753
    ///\e
kpeter@559
  1754
    typedef IT Iterator;
alpar@104
  1755
alpar@104
  1756
    /// Constructor
kpeter@167
  1757
    LoggerBoolMap(Iterator it)
alpar@104
  1758
      : _begin(it), _end(it) {}
alpar@104
  1759
alpar@104
  1760
    /// Gives back the given iterator set for the first key
alpar@104
  1761
    Iterator begin() const {
alpar@104
  1762
      return _begin;
alpar@104
  1763
    }
alpar@104
  1764
alpar@104
  1765
    /// Gives back the the 'after the last' iterator
alpar@104
  1766
    Iterator end() const {
alpar@104
  1767
      return _end;
alpar@104
  1768
    }
alpar@104
  1769
alpar@104
  1770
    /// The set function of the map
kpeter@159
  1771
    void set(const Key& key, Value value) {
alpar@104
  1772
      if (value) {
alpar@209
  1773
        *_end++ = key;
alpar@104
  1774
      }
alpar@104
  1775
    }
alpar@104
  1776
alpar@104
  1777
  private:
alpar@104
  1778
    Iterator _begin;
kpeter@159
  1779
    Iterator _end;
alpar@104
  1780
  };
alpar@209
  1781
kpeter@301
  1782
  /// Returns a \c LoggerBoolMap class
kpeter@301
  1783
kpeter@301
  1784
  /// This function just returns a \c LoggerBoolMap class.
kpeter@159
  1785
  ///
kpeter@159
  1786
  /// The most important usage of it is storing certain nodes or arcs
kpeter@159
  1787
  /// that were marked \c true by an algorithm.
kpeter@786
  1788
  /// For example, it makes easier to store the nodes in the processing
kpeter@159
  1789
  /// order of Dfs algorithm, as the following examples show.
kpeter@159
  1790
  /// \code
kpeter@159
  1791
  ///   std::vector<Node> v;
kpeter@716
  1792
  ///   dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s);
kpeter@159
  1793
  /// \endcode
kpeter@159
  1794
  /// \code
kpeter@159
  1795
  ///   std::vector<Node> v(countNodes(g));
kpeter@716
  1796
  ///   dfs(g).processedMap(loggerBoolMap(v.begin())).run(s);
kpeter@159
  1797
  /// \endcode
kpeter@159
  1798
  ///
kpeter@159
  1799
  /// \note The container of the iterator must contain enough space
kpeter@159
  1800
  /// for the elements or the iterator should be an inserter iterator.
kpeter@159
  1801
  ///
kpeter@167
  1802
  /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
kpeter@786
  1803
  /// it cannot be used when a readable map is needed, for example, as
kpeter@301
  1804
  /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms.
kpeter@159
  1805
  ///
kpeter@167
  1806
  /// \relates LoggerBoolMap
kpeter@159
  1807
  template<typename Iterator>
kpeter@167
  1808
  inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
kpeter@167
  1809
    return LoggerBoolMap<Iterator>(it);
kpeter@159
  1810
  }
alpar@104
  1811
kpeter@314
  1812
  /// @}
kpeter@314
  1813
kpeter@314
  1814
  /// \addtogroup graph_maps
kpeter@314
  1815
  /// @{
kpeter@314
  1816
kpeter@559
  1817
  /// \brief Provides an immutable and unique id for each item in a graph.
kpeter@559
  1818
  ///
kpeter@559
  1819
  /// IdMap provides a unique and immutable id for each item of the
deba@693
  1820
  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
kpeter@559
  1821
  ///  - \b unique: different items get different ids,
kpeter@559
  1822
  ///  - \b immutable: the id of an item does not change (even if you
kpeter@559
  1823
  ///    delete other nodes).
kpeter@559
  1824
  ///
kpeter@559
  1825
  /// Using this map you get access (i.e. can read) the inner id values of
kpeter@559
  1826
  /// the items stored in the graph, which is returned by the \c id()
kpeter@559
  1827
  /// function of the graph. This map can be inverted with its member
kpeter@720
  1828
  /// class \c InverseMap or with the \c operator()() member.
deba@220
  1829
  ///
kpeter@559
  1830
  /// \tparam GR The graph type.
kpeter@559
  1831
  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
kpeter@559
  1832
  /// \c GR::Edge).
kpeter@559
  1833
  ///
alpar@572
  1834
  /// \see RangeIdMap
kpeter@559
  1835
  template <typename GR, typename K>
kpeter@559
  1836
  class IdMap : public MapBase<K, int> {
deba@220
  1837
  public:
kpeter@559
  1838
    /// The graph type of IdMap.
kpeter@559
  1839
    typedef GR Graph;
kpeter@617
  1840
    typedef GR Digraph;
kpeter@559
  1841
    /// The key type of IdMap (\c Node, \c Arc or \c Edge).
kpeter@559
  1842
    typedef K Item;
kpeter@559
  1843
    /// The key type of IdMap (\c Node, \c Arc or \c Edge).
kpeter@559
  1844
    typedef K Key;
kpeter@559
  1845
    /// The value type of IdMap.
deba@220
  1846
    typedef int Value;
deba@220
  1847
deba@220
  1848
    /// \brief Constructor.
deba@220
  1849
    ///
deba@220
  1850
    /// Constructor of the map.
deba@220
  1851
    explicit IdMap(const Graph& graph) : _graph(&graph) {}
deba@220
  1852
deba@220
  1853
    /// \brief Gives back the \e id of the item.
deba@220
  1854
    ///
deba@220
  1855
    /// Gives back the immutable and unique \e id of the item.
deba@220
  1856
    int operator[](const Item& item) const { return _graph->id(item);}
deba@220
  1857
kpeter@559
  1858
    /// \brief Gives back the \e item by its id.
deba@220
  1859
    ///
kpeter@559
  1860
    /// Gives back the \e item by its id.
deba@220
  1861
    Item operator()(int id) { return _graph->fromId(id, Item()); }
deba@220
  1862
deba@220
  1863
  private:
deba@220
  1864
    const Graph* _graph;
deba@220
  1865
deba@220
  1866
  public:
deba@220
  1867
kpeter@722
  1868
    /// \brief The inverse map type of IdMap.
deba@220
  1869
    ///
kpeter@722
  1870
    /// The inverse map type of IdMap. The subscript operator gives back
kpeter@722
  1871
    /// an item by its id.
kpeter@722
  1872
    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
deba@220
  1873
    /// \see inverse()
deba@220
  1874
    class InverseMap {
deba@220
  1875
    public:
deba@220
  1876
deba@220
  1877
      /// \brief Constructor.
deba@220
  1878
      ///
deba@220
  1879
      /// Constructor for creating an id-to-item map.
deba@220
  1880
      explicit InverseMap(const Graph& graph) : _graph(&graph) {}
deba@220
  1881
deba@220
  1882
      /// \brief Constructor.
deba@220
  1883
      ///
deba@220
  1884
      /// Constructor for creating an id-to-item map.
deba@220
  1885
      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
deba@220
  1886
kpeter@722
  1887
      /// \brief Gives back an item by its id.
deba@220
  1888
      ///
kpeter@722
  1889
      /// Gives back an item by its id.
deba@220
  1890
      Item operator[](int id) const { return _graph->fromId(id, Item());}
deba@220
  1891
deba@220
  1892
    private:
deba@220
  1893
      const Graph* _graph;
deba@220
  1894
    };
deba@220
  1895
deba@220
  1896
    /// \brief Gives back the inverse of the map.
deba@220
  1897
    ///
deba@220
  1898
    /// Gives back the inverse of the IdMap.
deba@220
  1899
    InverseMap inverse() const { return InverseMap(*_graph);}
deba@220
  1900
  };
deba@220
  1901
kpeter@725
  1902
  /// \brief Returns an \c IdMap class.
kpeter@725
  1903
  ///
kpeter@725
  1904
  /// This function just returns an \c IdMap class.
kpeter@725
  1905
  /// \relates IdMap
kpeter@725
  1906
  template <typename K, typename GR>
kpeter@725
  1907
  inline IdMap<GR, K> idMap(const GR& graph) {
kpeter@725
  1908
    return IdMap<GR, K>(graph);
kpeter@725
  1909
  }
deba@220
  1910
alpar@572
  1911
  /// \brief General cross reference graph map type.
kpeter@559
  1912
kpeter@559
  1913
  /// This class provides simple invertable graph maps.
kpeter@684
  1914
  /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
kpeter@684
  1915
  /// and if a key is set to a new value, then stores it in the inverse map.
kpeter@722
  1916
  /// The graph items can be accessed by their values either using
kpeter@722
  1917
  /// \c InverseMap or \c operator()(), and the values of the map can be
kpeter@724
  1918
  /// accessed with an STL compatible forward iterator (\c ValueIt).
kpeter@722
  1919
  /// 
kpeter@722
  1920
  /// This map is intended to be used when all associated values are
kpeter@722
  1921
  /// different (the map is actually invertable) or there are only a few
kpeter@722
  1922
  /// items with the same value.
kpeter@722
  1923
  /// Otherwise consider to use \c IterableValueMap, which is more 
kpeter@722
  1924
  /// suitable and more efficient for such cases. It provides iterators
kpeter@786
  1925
  /// to traverse the items with the same associated value, but
kpeter@722
  1926
  /// it does not have \c InverseMap.
deba@220
  1927
  ///
kpeter@694
  1928
  /// This type is not reference map, so it cannot be modified with
kpeter@684
  1929
  /// the subscript operator.
kpeter@694
  1930
  ///
kpeter@559
  1931
  /// \tparam GR The graph type.
kpeter@559
  1932
  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
kpeter@559
  1933
  /// \c GR::Edge).
kpeter@559
  1934
  /// \tparam V The value type of the map.
deba@220
  1935
  ///
deba@220
  1936
  /// \see IterableValueMap
kpeter@559
  1937
  template <typename GR, typename K, typename V>
alpar@572
  1938
  class CrossRefMap
kpeter@559
  1939
    : protected ItemSetTraits<GR, K>::template Map<V>::Type {
deba@220
  1940
  private:
deba@220
  1941
kpeter@559
  1942
    typedef typename ItemSetTraits<GR, K>::
kpeter@559
  1943
      template Map<V>::Type Map;
kpeter@559
  1944
kpeter@684
  1945
    typedef std::multimap<V, K> Container;
deba@220
  1946
    Container _inv_map;
deba@220
  1947
deba@220
  1948
  public:
deba@220
  1949
alpar@572
  1950
    /// The graph type of CrossRefMap.
kpeter@559
  1951
    typedef GR Graph;
kpeter@617
  1952
    typedef GR Digraph;
alpar@572
  1953
    /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
kpeter@559
  1954
    typedef K Item;
alpar@572
  1955
    /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
kpeter@559
  1956
    typedef K Key;
alpar@572
  1957
    /// The value type of CrossRefMap.
kpeter@559
  1958
    typedef V Value;
deba@220
  1959
deba@220
  1960
    /// \brief Constructor.
deba@220
  1961
    ///
alpar@572
  1962
    /// Construct a new CrossRefMap for the given graph.
alpar@572
  1963
    explicit CrossRefMap(const Graph& graph) : Map(graph) {}
deba@220
  1964
deba@220
  1965
    /// \brief Forward iterator for values.
deba@220
  1966
    ///
kpeter@722
  1967
    /// This iterator is an STL compatible forward
deba@220
  1968
    /// iterator on the values of the map. The values can
kpeter@559
  1969
    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
kpeter@684
  1970
    /// They are considered with multiplicity, so each value is
kpeter@684
  1971
    /// traversed for each item it is assigned to.
kpeter@724
  1972
    class ValueIt
deba@220
  1973
      : public std::iterator<std::forward_iterator_tag, Value> {
alpar@572
  1974
      friend class CrossRefMap;
deba@220
  1975
    private:
kpeter@724
  1976
      ValueIt(typename Container::const_iterator _it)
deba@220
  1977
        : it(_it) {}
deba@220
  1978
    public:
deba@220
  1979
kpeter@722
  1980
      /// Constructor
kpeter@724
  1981
      ValueIt() {}
kpeter@694
  1982
kpeter@722
  1983
      /// \e
kpeter@724
  1984
      ValueIt& operator++() { ++it; return *this; }
kpeter@722
  1985
      /// \e
kpeter@724
  1986
      ValueIt operator++(int) {
kpeter@724
  1987
        ValueIt tmp(*this);
deba@220
  1988
        operator++();
deba@220
  1989
        return tmp;
deba@220
  1990
      }
deba@220
  1991
kpeter@722
  1992
      /// \e
deba@220
  1993
      const Value& operator*() const { return it->first; }
kpeter@722
  1994
      /// \e
deba@220
  1995
      const Value* operator->() const { return &(it->first); }
deba@220
  1996
kpeter@722
  1997
      /// \e
kpeter@724
  1998
      bool operator==(ValueIt jt) const { return it == jt.it; }
kpeter@722
  1999
      /// \e
kpeter@724
  2000
      bool operator!=(ValueIt jt) const { return it != jt.it; }
deba@220
  2001
deba@220
  2002
    private:
deba@220
  2003
      typename Container::const_iterator it;
deba@220
  2004
    };
kpeter@724
  2005
    
kpeter@724
  2006
    /// Alias for \c ValueIt
kpeter@724
  2007
    typedef ValueIt ValueIterator;
deba@220
  2008
deba@220
  2009
    /// \brief Returns an iterator to the first value.
deba@220
  2010
    ///
kpeter@722
  2011
    /// Returns an STL compatible iterator to the
deba@220
  2012
    /// first value of the map. The values of the
kpeter@559
  2013
    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
deba@220
  2014
    /// range.
kpeter@724
  2015
    ValueIt beginValue() const {
kpeter@724
  2016
      return ValueIt(_inv_map.begin());
deba@220
  2017
    }
deba@220
  2018
deba@220
  2019
    /// \brief Returns an iterator after the last value.
deba@220
  2020
    ///
kpeter@722
  2021
    /// Returns an STL compatible iterator after the
deba@220
  2022
    /// last value of the map. The values of the
kpeter@559
  2023
    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
deba@220
  2024
    /// range.
kpeter@724
  2025
    ValueIt endValue() const {
kpeter@724
  2026
      return ValueIt(_inv_map.end());
deba@220
  2027
    }
deba@220
  2028
kpeter@559
  2029
    /// \brief Sets the value associated with the given key.
deba@220
  2030
    ///
kpeter@559
  2031
    /// Sets the value associated with the given key.
deba@220
  2032
    void set(const Key& key, const Value& val) {
deba@220
  2033
      Value oldval = Map::operator[](key);
kpeter@684
  2034
      typename Container::iterator it;
kpeter@684
  2035
      for (it = _inv_map.equal_range(oldval).first;
kpeter@684
  2036
           it != _inv_map.equal_range(oldval).second; ++it) {
kpeter@684
  2037
        if (it->second == key) {
kpeter@684
  2038
          _inv_map.erase(it);
kpeter@684
  2039
          break;
kpeter@684
  2040
        }
deba@220
  2041
      }
deba@693
  2042
      _inv_map.insert(std::make_pair(val, key));
deba@220
  2043
      Map::set(key, val);
deba@220
  2044
    }
deba@220
  2045
kpeter@559
  2046
    /// \brief Returns the value associated with the given key.
deba@220
  2047
    ///
kpeter@559
  2048
    /// Returns the value associated with the given key.
deba@220
  2049
    typename MapTraits<Map>::ConstReturnValue
deba@220
  2050
    operator[](const Key& key) const {
deba@220
  2051
      return Map::operator[](key);
deba@220
  2052
    }
deba@220
  2053
kpeter@684
  2054
    /// \brief Gives back an item by its value.
deba@220
  2055
    ///
kpeter@684
  2056
    /// This function gives back an item that is assigned to
kpeter@684
  2057
    /// the given value or \c INVALID if no such item exists.
kpeter@684
  2058
    /// If there are more items with the same associated value,
kpeter@684
  2059
    /// only one of them is returned.
kpeter@684
  2060
    Key operator()(const Value& val) const {
kpeter@684
  2061
      typename Container::const_iterator it = _inv_map.find(val);
deba@220
  2062
      return it != _inv_map.end() ? it->second : INVALID;
deba@220
  2063
    }
kpeter@720
  2064
    
kpeter@720
  2065
    /// \brief Returns the number of items with the given value.
kpeter@720
  2066
    ///
kpeter@720
  2067
    /// This function returns the number of items with the given value
kpeter@720
  2068
    /// associated with it.
kpeter@720
  2069
    int count(const Value &val) const {
kpeter@720
  2070
      return _inv_map.count(val);
kpeter@720
  2071
    }
deba@220
  2072
deba@220
  2073
  protected:
deba@220
  2074
kpeter@559
  2075
    /// \brief Erase the key from the map and the inverse map.
deba@220
  2076
    ///
kpeter@559
  2077
    /// Erase the key from the map and the inverse map. It is called by the
deba@220
  2078
    /// \c AlterationNotifier.
deba@220
  2079
    virtual void erase(const Key& key) {
deba@220
  2080
      Value val = Map::operator[](key);
kpeter@684
  2081
      typename Container::iterator it;
kpeter@684
  2082
      for (it = _inv_map.equal_range(val).first;
kpeter@684
  2083
           it != _inv_map.equal_range(val).second; ++it) {
kpeter@684
  2084
        if (it->second == key) {
kpeter@684
  2085
          _inv_map.erase(it);
kpeter@684
  2086
          break;
kpeter@684
  2087
        }
deba@220
  2088
      }
deba@220
  2089
      Map::erase(key);
deba@220
  2090
    }
deba@220
  2091
kpeter@559
  2092
    /// \brief Erase more keys from the map and the inverse map.
deba@220
  2093
    ///
kpeter@559
  2094
    /// Erase more keys from the map and the inverse map. It is called by the
deba@220
  2095
    /// \c AlterationNotifier.
deba@220
  2096
    virtual void erase(const std::vector<Key>& keys) {
deba@220
  2097
      for (int i = 0; i < int(keys.size()); ++i) {
deba@220
  2098
        Value val = Map::operator[](keys[i]);
kpeter@684
  2099
        typename Container::iterator it;
kpeter@684
  2100
        for (it = _inv_map.equal_range(val).first;
kpeter@684
  2101
             it != _inv_map.equal_range(val).second; ++it) {
kpeter@684
  2102
          if (it->second == keys[i]) {
kpeter@684
  2103
            _inv_map.erase(it);
kpeter@684
  2104
            break;
kpeter@684
  2105
          }
deba@220
  2106
        }
deba@220
  2107
      }
deba@220
  2108
      Map::erase(keys);
deba@220
  2109
    }
deba@220
  2110
kpeter@559
  2111
    /// \brief Clear the keys from the map and the inverse map.
deba@220
  2112
    ///
kpeter@559
  2113
    /// Clear the keys from the map and the inverse map. It is called by the
deba@220
  2114
    /// \c AlterationNotifier.
deba@220
  2115
    virtual void clear() {
deba@220
  2116
      _inv_map.clear();
deba@220
  2117
      Map::clear();
deba@220
  2118
    }
deba@220
  2119
deba@220
  2120
  public:
deba@220
  2121
kpeter@722
  2122
    /// \brief The inverse map type of CrossRefMap.
deba@220
  2123
    ///
kpeter@722
  2124
    /// The inverse map type of CrossRefMap. The subscript operator gives
kpeter@722
  2125
    /// back an item by its value.
kpeter@722
  2126
    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
kpeter@722
  2127
    /// \see inverse()
deba@220
  2128
    class InverseMap {
deba@220
  2129
    public:
kpeter@559
  2130
      /// \brief Constructor
deba@220
  2131
      ///
deba@220
  2132
      /// Constructor of the InverseMap.
alpar@572
  2133
      explicit InverseMap(const CrossRefMap& inverted)
deba@220
  2134
        : _inverted(inverted) {}
deba@220
  2135
deba@220
  2136
      /// The value type of the InverseMap.
alpar@572
  2137
      typedef typename CrossRefMap::Key Value;
deba@220
  2138
      /// The key type of the InverseMap.
alpar@572
  2139
      typedef typename CrossRefMap::Value Key;
deba@220
  2140
deba@220
  2141
      /// \brief Subscript operator.
deba@220
  2142
      ///
kpeter@684
  2143
      /// Subscript operator. It gives back an item
kpeter@684
  2144
      /// that is assigned to the given value or \c INVALID
kpeter@684
  2145
      /// if no such item exists.
deba@220
  2146
      Value operator[](const Key& key) const {
deba@220
  2147
        return _inverted(key);
deba@220
  2148
      }
deba@220
  2149
deba@220
  2150
    private:
alpar@572
  2151
      const CrossRefMap& _inverted;
deba@220
  2152
    };
deba@220
  2153
kpeter@722
  2154
    /// \brief Gives back the inverse of the map.
deba@220
  2155
    ///
kpeter@722
  2156
    /// Gives back the inverse of the CrossRefMap.
deba@220
  2157
    InverseMap inverse() const {
deba@220
  2158
      return InverseMap(*this);
deba@220
  2159
    }
deba@220
  2160
deba@220
  2161
  };
deba@220
  2162
kpeter@720
  2163
  /// \brief Provides continuous and unique id for the
alpar@572
  2164
  /// items of a graph.
deba@220
  2165
  ///
alpar@572
  2166
  /// RangeIdMap provides a unique and continuous
kpeter@720
  2167
  /// id for each item of a given type (\c Node, \c Arc or
kpeter@559
  2168
  /// \c Edge) in a graph. This id is
kpeter@559
  2169
  ///  - \b unique: different items get different ids,
kpeter@559
  2170
  ///  - \b continuous: the range of the ids is the set of integers
kpeter@559
  2171
  ///    between 0 and \c n-1, where \c n is the number of the items of
alpar@572
  2172
  ///    this type (\c Node, \c Arc or \c Edge).
alpar@572
  2173
  ///  - So, the ids can change when deleting an item of the same type.
deba@220
  2174
  ///
kpeter@559
  2175
  /// Thus this id is not (necessarily) the same as what can get using
kpeter@559
  2176
  /// the \c id() function of the graph or \ref IdMap.
kpeter@559
  2177
  /// This map can be inverted with its member class \c InverseMap,
kpeter@720
  2178
  /// or with the \c operator()() member.
kpeter@559
  2179
  ///
kpeter@559
  2180
  /// \tparam GR The graph type.
kpeter@559
  2181
  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
kpeter@559
  2182
  /// \c GR::Edge).
kpeter@559
  2183
  ///
kpeter@559
  2184
  /// \see IdMap
kpeter@559
  2185
  template <typename GR, typename K>
alpar@572
  2186
  class RangeIdMap
kpeter@559
  2187
    : protected ItemSetTraits<GR, K>::template Map<int>::Type {
kpeter@559
  2188
kpeter@559
  2189
    typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Map;
deba@220
  2190
deba@220
  2191
  public:
alpar@572
  2192
    /// The graph type of RangeIdMap.
kpeter@559
  2193
    typedef GR Graph;
kpeter@617
  2194
    typedef GR Digraph;
alpar@572
  2195
    /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge).
kpeter@559
  2196
    typedef K Item;
alpar@572
  2197
    /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge).
kpeter@559
  2198
    typedef K Key;
alpar@572
  2199
    /// The value type of RangeIdMap.
kpeter@559
  2200
    typedef int Value;
deba@220
  2201
deba@220
  2202
    /// \brief Constructor.
deba@220
  2203
    ///
alpar@572
  2204
    /// Constructor.
alpar@572
  2205
    explicit RangeIdMap(const Graph& gr) : Map(gr) {
deba@220
  2206
      Item it;
deba@220
  2207
      const typename Map::Notifier* nf = Map::notifier();
deba@220
  2208
      for (nf->first(it); it != INVALID; nf->next(it)) {
deba@220
  2209
        Map::set(it, _inv_map.size());
deba@220
  2210
        _inv_map.push_back(it);
deba@220
  2211
      }
deba@220
  2212
    }
deba@220
  2213
deba@220
  2214
  protected:
deba@220
  2215
kpeter@559
  2216
    /// \brief Adds a new key to the map.
deba@220
  2217
    ///
deba@220
  2218
    /// Add a new key to the map. It is called by the
deba@220
  2219
    /// \c AlterationNotifier.
deba@220
  2220
    virtual void add(const Item& item) {
deba@220
  2221
      Map::add(item);
deba@220
  2222
      Map::set(item, _inv_map.size());
deba@220
  2223
      _inv_map.push_back(item);
deba@220
  2224
    }
deba@220
  2225
deba@220
  2226
    /// \brief Add more new keys to the map.
deba@220
  2227
    ///
deba@220
  2228
    /// Add more new keys to the map. It is called by the
deba@220
  2229
    /// \c AlterationNotifier.
deba@220
  2230
    virtual void add(const std::vector<Item>& items) {
deba@220
  2231
      Map::add(items);
deba@220
  2232
      for (int i = 0; i < int(items.size()); ++i) {
deba@220
  2233
        Map::set(items[i], _inv_map.size());
deba@220
  2234
        _inv_map.push_back(items[i]);
deba@220
  2235
      }
deba@220
  2236
    }
deba@220
  2237
deba@220
  2238
    /// \brief Erase the key from the map.
deba@220
  2239
    ///
deba@220
  2240
    /// Erase the key from the map. It is called by the
deba@220
  2241
    /// \c AlterationNotifier.
deba@220
  2242
    virtual void erase(const Item& item) {
deba@220
  2243
      Map::set(_inv_map.back(), Map::operator[](item));
deba@220
  2244
      _inv_map[Map::operator[](item)] = _inv_map.back();
deba@220
  2245
      _inv_map.pop_back();
deba@220
  2246
      Map::erase(item);
deba@220
  2247
    }
deba@220
  2248
deba@220
  2249
    /// \brief Erase more keys from the map.
deba@220
  2250
    ///
deba@220
  2251
    /// Erase more keys from the map. It is called by the
deba@220
  2252
    /// \c AlterationNotifier.
deba@220
  2253
    virtual void erase(const std::vector<Item>& items) {
deba@220
  2254
      for (int i = 0; i < int(items.size()); ++i) {
deba@220
  2255
        Map::set(_inv_map.back(), Map::operator[](items[i]));
deba@220
  2256
        _inv_map[Map::operator[](items[i])] = _inv_map.back();
deba@220
  2257
        _inv_map.pop_back();
deba@220
  2258
      }
deba@220
  2259
      Map::erase(items);
deba@220
  2260
    }
deba@220
  2261
deba@220
  2262
    /// \brief Build the unique map.
deba@220
  2263
    ///
deba@220
  2264
    /// Build the unique map. It is called by the
deba@220
  2265
    /// \c AlterationNotifier.
deba@220
  2266
    virtual void build() {
deba@220
  2267
      Map::build();
deba@220
  2268
      Item it;
deba@220
  2269
      const typename Map::Notifier* nf = Map::notifier();
deba@220
  2270
      for (nf->first(it); it != INVALID; nf->next(it)) {
deba@220
  2271
        Map::set(it, _inv_map.size());
deba@220
  2272
        _inv_map.push_back(it);
deba@220
  2273
      }
deba@220
  2274
    }
deba@220
  2275
deba@220
  2276
    /// \brief Clear the keys from the map.
deba@220
  2277
    ///
deba@220
  2278
    /// Clear the keys from the map. It is called by the
deba@220
  2279
    /// \c AlterationNotifier.
deba@220
  2280
    virtual void clear() {
deba@220
  2281
      _inv_map.clear();
deba@220
  2282
      Map::clear();
deba@220
  2283
    }
deba@220
  2284
deba@220
  2285
  public:
deba@220
  2286
deba@220
  2287
    /// \brief Returns the maximal value plus one.
deba@220
  2288
    ///
deba@220
  2289
    /// Returns the maximal value plus one in the map.
deba@220
  2290
    unsigned int size() const {
deba@220
  2291
      return _inv_map.size();
deba@220
  2292
    }
deba@220
  2293
deba@220
  2294
    /// \brief Swaps the position of the two items in the map.
deba@220
  2295
    ///
deba@220
  2296
    /// Swaps the position of the two items in the map.
deba@220
  2297
    void swap(const Item& p, const Item& q) {
deba@220
  2298
      int pi = Map::operator[](p);
deba@220
  2299
      int qi = Map::operator[](q);
deba@220
  2300
      Map::set(p, qi);
deba@220
  2301
      _inv_map[qi] = p;
deba@220
  2302
      Map::set(q, pi);
deba@220
  2303
      _inv_map[pi] = q;
deba@220
  2304
    }
deba@220
  2305
kpeter@722
  2306
    /// \brief Gives back the \e range \e id of the item
deba@220
  2307
    ///
kpeter@722
  2308
    /// Gives back the \e range \e id of the item.
deba@220
  2309
    int operator[](const Item& item) const {
deba@220
  2310
      return Map::operator[](item);
deba@220
  2311
    }
deba@220
  2312
kpeter@722
  2313
    /// \brief Gives back the item belonging to a \e range \e id
deba@693
  2314
    ///
kpeter@722
  2315
    /// Gives back the item belonging to the given \e range \e id.
deba@220
  2316
    Item operator()(int id) const {
deba@220
  2317
      return _inv_map[id];
deba@220
  2318
    }
deba@220
  2319
deba@220
  2320
  private:
deba@220
  2321
deba@220
  2322
    typedef std::vector<Item> Container;
deba@220
  2323
    Container _inv_map;
deba@220
  2324
deba@220
  2325
  public:
kpeter@559
  2326
alpar@572
  2327
    /// \brief The inverse map type of RangeIdMap.
deba@220
  2328
    ///
kpeter@722
  2329
    /// The inverse map type of RangeIdMap. The subscript operator gives
kpeter@722
  2330
    /// back an item by its \e range \e id.
kpeter@722
  2331
    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
deba@220
  2332
    class InverseMap {
deba@220
  2333
    public:
kpeter@559
  2334
      /// \brief Constructor
deba@220
  2335
      ///
deba@220
  2336
      /// Constructor of the InverseMap.
alpar@572
  2337
      explicit InverseMap(const RangeIdMap& inverted)
deba@220
  2338
        : _inverted(inverted) {}
deba@220
  2339
deba@220
  2340
deba@220
  2341
      /// The value type of the InverseMap.
alpar@572
  2342
      typedef typename RangeIdMap::Key Value;
deba@220
  2343
      /// The key type of the InverseMap.
alpar@572
  2344
      typedef typename RangeIdMap::Value Key;
deba@220
  2345
deba@220
  2346
      /// \brief Subscript operator.
deba@220
  2347
      ///
deba@220
  2348
      /// Subscript operator. It gives back the item
kpeter@722
  2349
      /// that the given \e range \e id currently belongs to.
deba@220
  2350
      Value operator[](const Key& key) const {
deba@220
  2351
        return _inverted(key);
deba@220
  2352
      }
deba@220
  2353
deba@220
  2354
      /// \brief Size of the map.
deba@220
  2355
      ///
deba@220
  2356
      /// Returns the size of the map.
deba@220
  2357
      unsigned int size() const {
deba@220
  2358
        return _inverted.size();
deba@220
  2359
      }
deba@220
  2360
deba@220
  2361
    private:
alpar@572
  2362
      const RangeIdMap& _inverted;
deba@220
  2363
    };
deba@220
  2364
deba@220
  2365
    /// \brief Gives back the inverse of the map.
deba@220
  2366
    ///
kpeter@722
  2367
    /// Gives back the inverse of the RangeIdMap.
deba@220
  2368
    const InverseMap inverse() const {
deba@220
  2369
      return InverseMap(*this);
deba@220
  2370
    }
deba@220
  2371
  };
deba@220
  2372
kpeter@725
  2373
  /// \brief Returns a \c RangeIdMap class.
kpeter@725
  2374
  ///
kpeter@725
  2375
  /// This function just returns an \c RangeIdMap class.
kpeter@725
  2376
  /// \relates RangeIdMap
kpeter@725
  2377
  template <typename K, typename GR>
kpeter@725
  2378
  inline RangeIdMap<GR, K> rangeIdMap(const GR& graph) {
kpeter@725
  2379
    return RangeIdMap<GR, K>(graph);
kpeter@725
  2380
  }
kpeter@725
  2381
  
kpeter@694
  2382
  /// \brief Dynamic iterable \c bool map.
deba@693
  2383
  ///
kpeter@694
  2384
  /// This class provides a special graph map type which can store a
kpeter@694
  2385
  /// \c bool value for graph items (\c Node, \c Arc or \c Edge).
kpeter@694
  2386
  /// For both \c true and \c false values it is possible to iterate on
kpeter@722
  2387
  /// the keys mapped to the value.
deba@693
  2388
  ///
kpeter@694
  2389
  /// This type is a reference map, so it can be modified with the
alpar@695
  2390
  /// subscript operator.
kpeter@694
  2391
  ///
kpeter@694
  2392
  /// \tparam GR The graph type.
kpeter@694
  2393
  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
kpeter@694
  2394
  /// \c GR::Edge).
kpeter@694
  2395
  ///
kpeter@694
  2396
  /// \see IterableIntMap, IterableValueMap
kpeter@694
  2397
  /// \see CrossRefMap
kpeter@694
  2398
  template <typename GR, typename K>
deba@693
  2399
  class IterableBoolMap
kpeter@694
  2400
    : protected ItemSetTraits<GR, K>::template Map<int>::Type {
deba@693
  2401
  private:
deba@693
  2402
    typedef GR Graph;
deba@693
  2403
kpeter@694
  2404
    typedef typename ItemSetTraits<GR, K>::ItemIt KeyIt;
kpeter@694
  2405
    typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Parent;
kpeter@694
  2406
kpeter@694
  2407
    std::vector<K> _array;
deba@693
  2408
    int _sep;
deba@693
  2409
deba@693
  2410
  public:
deba@693
  2411
kpeter@694
  2412
    /// Indicates that the map is reference map.
deba@693
  2413
    typedef True ReferenceMapTag;
deba@693
  2414
deba@693
  2415
    /// The key type
kpeter@694
  2416
    typedef K Key;
deba@693
  2417
    /// The value type
deba@693
  2418
    typedef bool Value;
deba@693
  2419
    /// The const reference type.
deba@693
  2420
    typedef const Value& ConstReference;
deba@693
  2421
deba@693
  2422
  private:
deba@693
  2423
deba@693
  2424
    int position(const Key& key) const {
deba@693
  2425
      return Parent::operator[](key);
deba@693
  2426
    }
deba@693
  2427
deba@693
  2428
  public:
deba@693
  2429
kpeter@694
  2430
    /// \brief Reference to the value of the map.
deba@693
  2431
    ///
kpeter@694
  2432
    /// This class is similar to the \c bool type. It can be converted to
kpeter@694
  2433
    /// \c bool and it provides the same operators.
deba@693
  2434
    class Reference {
deba@693
  2435
      friend class IterableBoolMap;
deba@693
  2436
    private:
deba@693
  2437
      Reference(IterableBoolMap& map, const Key& key)
deba@693
  2438
        : _key(key), _map(map) {}
deba@693
  2439
    public:
deba@693
  2440
deba@693
  2441
      Reference& operator=(const Reference& value) {
deba@693
  2442
        _map.set(_key, static_cast<bool>(value));
deba@693
  2443
         return *this;
deba@693
  2444
      }
deba@693
  2445
deba@693
  2446
      operator bool() const {
deba@693
  2447
        return static_cast<const IterableBoolMap&>(_map)[_key];
deba@693
  2448
      }
deba@693
  2449
deba@693
  2450
      Reference& operator=(bool value) {
deba@693
  2451
        _map.set(_key, value);
deba@693
  2452
        return *this;
deba@693
  2453
      }
deba@693
  2454
      Reference& operator&=(bool value) {
deba@693
  2455
        _map.set(_key, _map[_key] & value);
deba@693
  2456
        return *this;
deba@693
  2457
      }
deba@693
  2458
      Reference& operator|=(bool value) {
deba@693
  2459
        _map.set(_key, _map[_key] | value);
deba@693
  2460
        return *this;
deba@693
  2461
      }
deba@693
  2462
      Reference& operator^=(bool value) {
deba@693
  2463
        _map.set(_key, _map[_key] ^ value);
deba@693
  2464
        return *this;
deba@693
  2465
      }
deba@693
  2466
    private:
deba@693
  2467
      Key _key;
deba@693
  2468
      IterableBoolMap& _map;
deba@693
  2469
    };
deba@693
  2470
deba@693
  2471
    /// \brief Constructor of the map with a default value.
deba@693
  2472
    ///
deba@693
  2473
    /// Constructor of the map with a default value.
deba@693
  2474
    explicit IterableBoolMap(const Graph& graph, bool def = false)
deba@693
  2475
      : Parent(graph) {
deba@693
  2476
      typename Parent::Notifier* nf = Parent::notifier();
deba@693
  2477
      Key it;
deba@693
  2478
      for (nf->first(it); it != INVALID; nf->next(it)) {
deba@693
  2479
        Parent::set(it, _array.size());
deba@693
  2480
        _array.push_back(it);
deba@693
  2481
      }
deba@693
  2482
      _sep = (def ? _array.size() : 0);
deba@693
  2483
    }
deba@693
  2484
deba@693
  2485
    /// \brief Const subscript operator of the map.
deba@693
  2486
    ///
deba@693
  2487
    /// Const subscript operator of the map.
deba@693
  2488
    bool operator[](const Key& key) const {
deba@693
  2489
      return position(key) < _sep;
deba@693
  2490
    }
deba@693
  2491
deba@693
  2492
    /// \brief Subscript operator of the map.
deba@693
  2493
    ///
deba@693
  2494
    /// Subscript operator of the map.
deba@693
  2495
    Reference operator[](const Key& key) {
deba@693
  2496
      return Reference(*this, key);
deba@693
  2497
    }
deba@693
  2498
deba@693
  2499
    /// \brief Set operation of the map.
deba@693
  2500
    ///
deba@693
  2501
    /// Set operation of the map.
deba@693
  2502
    void set(const Key& key, bool value) {
deba@693
  2503
      int pos = position(key);
deba@693
  2504
      if (value) {
deba@693
  2505
        if (pos < _sep) return;
deba@693
  2506
        Key tmp = _array[_sep];
deba@693
  2507
        _array[_sep] = key;
deba@693
  2508
        Parent::set(key, _sep);
deba@693
  2509
        _array[pos] = tmp;
deba@693
  2510
        Parent::set(tmp, pos);
deba@693
  2511
        ++_sep;
deba@693
  2512
      } else {
deba@693
  2513
        if (pos >= _sep) return;
deba@693
  2514
        --_sep;
deba@693
  2515
        Key tmp = _array[_sep];
deba@693
  2516
        _array[_sep] = key;
deba@693
  2517
        Parent::set(key, _sep);
deba@693
  2518
        _array[pos] = tmp;
deba@693
  2519
        Parent::set(tmp, pos);
deba@693
  2520
      }
deba@693
  2521
    }
deba@693
  2522
deba@693
  2523
    /// \brief Set all items.
deba@693
  2524
    ///
deba@693
  2525
    /// Set all items in the map.
deba@693
  2526
    /// \note Constant time operation.
deba@693
  2527
    void setAll(bool value) {
deba@693
  2528
      _sep = (value ? _array.size() : 0);
deba@693
  2529
    }
deba@693
  2530
kpeter@694
  2531
    /// \brief Returns the number of the keys mapped to \c true.
deba@693
  2532
    ///
kpeter@694
  2533
    /// Returns the number of the keys mapped to \c true.
deba@693
  2534
    int trueNum() const {
deba@693
  2535
      return _sep;
deba@693
  2536
    }
deba@693
  2537
kpeter@694
  2538
    /// \brief Returns the number of the keys mapped to \c false.
deba@693
  2539
    ///
kpeter@694
  2540
    /// Returns the number of the keys mapped to \c false.
deba@693
  2541
    int falseNum() const {
deba@693
  2542
      return _array.size() - _sep;
deba@693
  2543
    }
deba@693
  2544
kpeter@694
  2545
    /// \brief Iterator for the keys mapped to \c true.
deba@693
  2546
    ///
kpeter@694
  2547
    /// Iterator for the keys mapped to \c true. It works
kpeter@694
  2548
    /// like a graph item iterator, it can be converted to
deba@693
  2549
    /// the key type of the map, incremented with \c ++ operator, and
kpeter@694
  2550
    /// if the iterator leaves the last valid key, it will be equal to
deba@693
  2551
    /// \c INVALID.
deba@693
  2552
    class TrueIt : public Key {
deba@693
  2553
    public:
deba@693
  2554
      typedef Key Parent;
deba@693
  2555
deba@693
  2556
      /// \brief Creates an iterator.
deba@693
  2557
      ///
deba@693
  2558
      /// Creates an iterator. It iterates on the
kpeter@694
  2559
      /// keys mapped to \c true.
kpeter@694
  2560
      /// \param map The IterableBoolMap.
deba@693
  2561
      explicit TrueIt(const IterableBoolMap& map)
deba@693
  2562
        : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID),
deba@693
  2563
          _map(&map) {}
deba@693
  2564
deba@693
  2565
      /// \brief Invalid constructor \& conversion.
deba@693
  2566
      ///
kpeter@694
  2567
      /// This constructor initializes the iterator to be invalid.
deba@693
  2568
      /// \sa Invalid for more details.
deba@693
  2569
      TrueIt(Invalid) : Parent(INVALID), _map(0) {}
deba@693
  2570
deba@693
  2571
      /// \brief Increment operator.
deba@693
  2572
      ///
kpeter@694
  2573
      /// Increment operator.
deba@693
  2574
      TrueIt& operator++() {
deba@693
  2575
        int pos = _map->position(*this);
deba@693
  2576
        Parent::operator=(pos > 0 ? _map->_array[pos - 1] : INVALID);
deba@693
  2577
        return *this;
deba@693
  2578
      }
deba@693
  2579
deba@693
  2580
    private:
deba@693
  2581
      const IterableBoolMap* _map;
deba@693
  2582
    };
deba@693
  2583
kpeter@694
  2584
    /// \brief Iterator for the keys mapped to \c false.
deba@693
  2585
    ///
kpeter@694
  2586
    /// Iterator for the keys mapped to \c false. It works
kpeter@694
  2587
    /// like a graph item iterator, it can be converted to
deba@693
  2588
    /// the key type of the map, incremented with \c ++ operator, and
kpeter@694
  2589
    /// if the iterator leaves the last valid key, it will be equal to
deba@693
  2590
    /// \c INVALID.
deba@693
  2591
    class FalseIt : public Key {
deba@693
  2592
    public:
deba@693
  2593
      typedef Key Parent;
deba@693
  2594
deba@693
  2595
      /// \brief Creates an iterator.
deba@693
  2596
      ///
deba@693
  2597
      /// Creates an iterator. It iterates on the
kpeter@694
  2598
      /// keys mapped to \c false.
kpeter@694
  2599
      /// \param map The IterableBoolMap.
deba@693
  2600
      explicit FalseIt(const IterableBoolMap& map)
deba@693
  2601
        : Parent(map._sep < int(map._array.size()) ?
deba@693
  2602
                 map._array.back() : INVALID), _map(&map) {}
deba@693
  2603
deba@693
  2604
      /// \brief Invalid constructor \& conversion.
deba@693
  2605
      ///
kpeter@694
  2606
      /// This constructor initializes the iterator to be invalid.
deba@693
  2607
      /// \sa Invalid for more details.
deba@693
  2608
      FalseIt(Invalid) : Parent(INVALID), _map(0) {}
deba@693
  2609
deba@693
  2610
      /// \brief Increment operator.
deba@693
  2611
      ///
kpeter@694
  2612
      /// Increment operator.
deba@693
  2613
      FalseIt& operator++() {
deba@693
  2614
        int pos = _map->position(*this);
deba@693
  2615
        Parent::operator=(pos > _map->_sep ? _map->_array[pos - 1] : INVALID);
deba@693
  2616
        return *this;
deba@693
  2617
      }
deba@693
  2618
deba@693
  2619
    private:
deba@693
  2620
      const IterableBoolMap* _map;
deba@693
  2621
    };
deba@693
  2622
deba@693
  2623
    /// \brief Iterator for the keys mapped to a given value.
deba@693
  2624
    ///
deba@693
  2625
    /// Iterator for the keys mapped to a given value. It works
kpeter@694
  2626
    /// like a graph item iterator, it can be converted to
deba@693
  2627
    /// the key type of the map, incremented with \c ++ operator, and
kpeter@694
  2628
    /// if the iterator leaves the last valid key, it will be equal to
deba@693
  2629
    /// \c INVALID.
deba@693
  2630
    class ItemIt : public Key {
deba@693
  2631
    public:
deba@693
  2632
      typedef Key Parent;
deba@693
  2633
kpeter@694
  2634
      /// \brief Creates an iterator with a value.
deba@693
  2635
      ///
kpeter@694
  2636
      /// Creates an iterator with a value. It iterates on the
kpeter@694
  2637
      /// keys mapped to the given value.
kpeter@694
  2638
      /// \param map The IterableBoolMap.
kpeter@694
  2639
      /// \param value The value.
deba@693
  2640
      ItemIt(const IterableBoolMap& map, bool value)
deba@693
  2641
        : Parent(value ? 
deba@693
  2642
                 (map._sep > 0 ?
deba@693
  2643
                  map._array[map._sep - 1] : INVALID) :
deba@693
  2644
                 (map._sep < int(map._array.size()) ?
deba@693
  2645
                  map._array.back() : INVALID)), _map(&map) {}
deba@693
  2646
deba@693
  2647
      /// \brief Invalid constructor \& conversion.
deba@693
  2648
      ///
kpeter@694
  2649
      /// This constructor initializes the iterator to be invalid.
deba@693
  2650
      /// \sa Invalid for more details.
deba@693
  2651
      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
deba@693
  2652
deba@693
  2653
      /// \brief Increment operator.
deba@693
  2654
      ///
kpeter@694
  2655
      /// Increment operator.
deba@693
  2656
      ItemIt& operator++() {
deba@693
  2657
        int pos = _map->position(*this);
deba@693
  2658
        int _sep = pos >= _map->_sep ? _map->_sep : 0;
deba@693
  2659
        Parent::operator=(pos > _sep ? _map->_array[pos - 1] : INVALID);
deba@693
  2660
        return *this;
deba@693
  2661
      }
deba@693
  2662
deba@693
  2663
    private:
deba@693
  2664
      const IterableBoolMap* _map;
deba@693
  2665
    };
deba@693
  2666
deba@693
  2667
  protected:
deba@693
  2668
deba@693
  2669
    virtual void add(const Key& key) {
deba@693
  2670
      Parent::add(key);
deba@693
  2671
      Parent::set(key, _array.size());
deba@693
  2672
      _array.push_back(key);
deba@693
  2673
    }
deba@693
  2674
deba@693
  2675
    virtual void add(const std::vector<Key>& keys) {
deba@693
  2676
      Parent::add(keys);
deba@693
  2677
      for (int i = 0; i < int(keys.size()); ++i) {
deba@693
  2678
        Parent::set(keys[i], _array.size());
deba@693
  2679
        _array.push_back(keys[i]);
deba@693
  2680
      }
deba@693
  2681
    }
deba@693
  2682
deba@693
  2683
    virtual void erase(const Key& key) {
deba@693
  2684
      int pos = position(key);
deba@693
  2685
      if (pos < _sep) {
deba@693
  2686
        --_sep;
deba@693
  2687
        Parent::set(_array[_sep], pos);
deba@693
  2688
        _array[pos] = _array[_sep];
deba@693
  2689
        Parent::set(_array.back(), _sep);
deba@693
  2690
        _array[_sep] = _array.back();
deba@693
  2691
        _array.pop_back();
deba@693
  2692
      } else {
deba@693
  2693
        Parent::set(_array.back(), pos);
deba@693
  2694
        _array[pos] = _array.back();
deba@693
  2695
        _array.pop_back();
deba@693
  2696
      }
deba@693
  2697
      Parent::erase(key);
deba@693
  2698
    }
deba@693
  2699
deba@693
  2700
    virtual void erase(const std::vector<Key>& keys) {
deba@693
  2701
      for (int i = 0; i < int(keys.size()); ++i) {
deba@693
  2702
        int pos = position(keys[i]);
deba@693
  2703
        if (pos < _sep) {
deba@693
  2704
          --_sep;
deba@693
  2705
          Parent::set(_array[_sep], pos);
deba@693
  2706
          _array[pos] = _array[_sep];
deba@693
  2707
          Parent::set(_array.back(), _sep);
deba@693
  2708
          _array[_sep] = _array.back();
deba@693
  2709
          _array.pop_back();
deba@693
  2710
        } else {
deba@693
  2711
          Parent::set(_array.back(), pos);
deba@693
  2712
          _array[pos] = _array.back();
deba@693
  2713
          _array.pop_back();
deba@693
  2714
        }
deba@693
  2715
      }
deba@693
  2716
      Parent::erase(keys);
deba@693
  2717
    }
deba@693
  2718
deba@693
  2719
    virtual void build() {
deba@693
  2720
      Parent::build();
deba@693
  2721
      typename Parent::Notifier* nf = Parent::notifier();
deba@693
  2722
      Key it;
deba@693
  2723
      for (nf->first(it); it != INVALID; nf->next(it)) {
deba@693
  2724
        Parent::set(it, _array.size());
deba@693
  2725
        _array.push_back(it);
deba@693
  2726
      }
deba@693
  2727
      _sep = 0;
deba@693
  2728
    }
deba@693
  2729
deba@693
  2730
    virtual void clear() {
deba@693
  2731
      _array.clear();
deba@693
  2732
      _sep = 0;
deba@693
  2733
      Parent::clear();
deba@693
  2734
    }
deba@693
  2735
deba@693
  2736
  };
deba@693
  2737
deba@693
  2738
deba@693
  2739
  namespace _maps_bits {
deba@693
  2740
    template <typename Item>
deba@693
  2741
    struct IterableIntMapNode {
deba@693
  2742
      IterableIntMapNode() : value(-1) {}
deba@693
  2743
      IterableIntMapNode(int _value) : value(_value) {}
deba@693
  2744
      Item prev, next;
deba@693
  2745
      int value;
deba@693
  2746
    };
deba@693
  2747
  }
deba@693
  2748
deba@693
  2749
  /// \brief Dynamic iterable integer map.
deba@693
  2750
  ///
kpeter@694
  2751
  /// This class provides a special graph map type which can store an
kpeter@694
  2752
  /// integer value for graph items (\c Node, \c Arc or \c Edge).
kpeter@694
  2753
  /// For each non-negative value it is possible to iterate on the keys
kpeter@694
  2754
  /// mapped to the value.
deba@693
  2755
  ///
kpeter@722
  2756
  /// This map is intended to be used with small integer values, for which
kpeter@722
  2757
  /// it is efficient, and supports iteration only for non-negative values.
kpeter@722
  2758
  /// If you need large values and/or iteration for negative integers,
kpeter@722
  2759
  /// consider to use \ref IterableValueMap instead.
kpeter@722
  2760
  ///
kpeter@694
  2761
  /// This type is a reference map, so it can be modified with the
alpar@695
  2762
  /// subscript operator.
kpeter@694
  2763
  ///
kpeter@694
  2764
  /// \note The size of the data structure depends on the largest
deba@693
  2765
  /// value in the map.
deba@693
  2766
  ///
kpeter@694
  2767
  /// \tparam GR The graph type.
kpeter@694
  2768
  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
kpeter@694
  2769
  /// \c GR::Edge).
kpeter@694
  2770
  ///
kpeter@694
  2771
  /// \see IterableBoolMap, IterableValueMap
kpeter@694
  2772
  /// \see CrossRefMap
kpeter@694
  2773
  template <typename GR, typename K>
deba@693
  2774
  class IterableIntMap
kpeter@694
  2775
    : protected ItemSetTraits<GR, K>::
kpeter@694
  2776
        template Map<_maps_bits::IterableIntMapNode<K> >::Type {
deba@693
  2777
  public:
kpeter@694
  2778
    typedef typename ItemSetTraits<GR, K>::
kpeter@694
  2779
      template Map<_maps_bits::IterableIntMapNode<K> >::Type Parent;
deba@693
  2780
deba@693
  2781
    /// The key type
kpeter@694
  2782
    typedef K Key;
deba@693
  2783
    /// The value type
deba@693
  2784
    typedef int Value;
deba@693
  2785
    /// The graph type
deba@693
  2786
    typedef GR Graph;
deba@693
  2787
deba@693
  2788
    /// \brief Constructor of the map.
deba@693
  2789
    ///
kpeter@694
  2790
    /// Constructor of the map. It sets all values to -1.
deba@693
  2791
    explicit IterableIntMap(const Graph& graph)
deba@693
  2792
      : Parent(graph) {}
deba@693
  2793
deba@693
  2794
    /// \brief Constructor of the map with a given value.
deba@693
  2795
    ///
deba@693
  2796
    /// Constructor of the map with a given value.
deba@693
  2797
    explicit IterableIntMap(const Graph& graph, int value)
kpeter@694
  2798
      : Parent(graph, _maps_bits::IterableIntMapNode<K>(value)) {
deba@693
  2799
      if (value >= 0) {
deba@693
  2800
        for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
deba@693
  2801
          lace(it);
deba@693
  2802
        }
deba@693
  2803
      }
deba@693
  2804
    }
deba@693
  2805
deba@693
  2806
  private:
deba@693
  2807
deba@693
  2808
    void unlace(const Key& key) {
deba@693
  2809
      typename Parent::Value& node = Parent::operator[](key);
deba@693
  2810
      if (node.value < 0) return;
deba@693
  2811
      if (node.prev != INVALID) {
deba@693
  2812
        Parent::operator[](node.prev).next = node.next;
deba@693
  2813
      } else {
deba@693
  2814
        _first[node.value] = node.next;
deba@693
  2815
      }
deba@693
  2816
      if (node.next != INVALID) {
deba@693
  2817
        Parent::operator[](node.next).prev = node.prev;
deba@693
  2818
      }
deba@693
  2819
      while (!_first.empty() && _first.back() == INVALID) {
deba@693
  2820
        _first.pop_back();
deba@693
  2821
      }
deba@693
  2822
    }
deba@693
  2823
deba@693
  2824
    void lace(const Key& key) {
deba@693
  2825
      typename Parent::Value& node = Parent::operator[](key);
deba@693
  2826
      if (node.value < 0) return;
deba@693
  2827
      if (node.value >= int(_first.size())) {
deba@693
  2828
        _first.resize(node.value + 1, INVALID);
deba@693
  2829
      }
deba@693
  2830
      node.prev = INVALID;
deba@693
  2831
      node.next = _first[node.value];
deba@693
  2832
      if (node.next != INVALID) {
deba@693
  2833
        Parent::operator[](node.next).prev = key;
deba@693
  2834
      }
deba@693
  2835
      _first[node.value] = key;
deba@693
  2836
    }
deba@693
  2837
deba@693
  2838
  public:
deba@693
  2839
kpeter@694
  2840
    /// Indicates that the map is reference map.
deba@693
  2841
    typedef True ReferenceMapTag;
deba@693
  2842
kpeter@694
  2843
    /// \brief Reference to the value of the map.
deba@693
  2844
    ///
kpeter@694
  2845
    /// This class is similar to the \c int type. It can
kpeter@694
  2846
    /// be converted to \c int and it has the same operators.
deba@693
  2847
    class Reference {
deba@693
  2848
      friend class IterableIntMap;
deba@693
  2849
    private:
deba@693
  2850
      Reference(IterableIntMap& map, const Key& key)
deba@693
  2851
        : _key(key), _map(map) {}
deba@693
  2852
    public:
deba@693
  2853
deba@693
  2854
      Reference& operator=(const Reference& value) {
deba@693
  2855
        _map.set(_key, static_cast<const int&>(value));
deba@693
  2856
         return *this;
deba@693
  2857
      }
deba@693
  2858
deba@693
  2859
      operator const int&() const {
deba@693
  2860
        return static_cast<const IterableIntMap&>(_map)[_key];
deba@693
  2861
      }
deba@693
  2862
deba@693
  2863
      Reference& operator=(int value) {
deba@693
  2864
        _map.set(_key, value);
deba@693
  2865
        return *this;
deba@693
  2866
      }
deba@693
  2867
      Reference& operator++() {
deba@693
  2868
        _map.set(_key, _map[_key] + 1);
deba@693
  2869
        return *this;
deba@693
  2870
      }
deba@693
  2871
      int operator++(int) {
deba@693
  2872
        int value = _map[_key];
deba@693
  2873
        _map.set(_key, value + 1);
deba@693
  2874
        return value;
deba@693
  2875
      }
deba@693
  2876
      Reference& operator--() {
deba@693
  2877
        _map.set(_key, _map[_key] - 1);
deba@693
  2878
        return *this;
deba@693
  2879
      }
deba@693
  2880
      int operator--(int) {
deba@693
  2881
        int value = _map[_key];
deba@693
  2882
        _map.set(_key, value - 1);
deba@693
  2883
        return value;
deba@693
  2884
      }
deba@693
  2885
      Reference& operator+=(int value) {
deba@693
  2886
        _map.set(_key, _map[_key] + value);
deba@693
  2887
        return *this;
deba@693
  2888
      }
deba@693
  2889
      Reference& operator-=(int value) {
deba@693
  2890
        _map.set(_key, _map[_key] - value);
deba@693
  2891
        return *this;
deba@693
  2892
      }
deba@693
  2893
      Reference& operator*=(int value) {
deba@693
  2894
        _map.set(_key, _map[_key] * value);
deba@693
  2895
        return *this;
deba@693
  2896
      }
deba@693
  2897
      Reference& operator/=(int value) {
deba@693
  2898
        _map.set(_key, _map[_key] / value);
deba@693
  2899
        return *this;
deba@693
  2900
      }
deba@693
  2901
      Reference& operator%=(int value) {
deba@693
  2902
        _map.set(_key, _map[_key] % value);
deba@693
  2903
        return *this;
deba@693
  2904
      }
deba@693
  2905
      Reference& operator&=(int value) {
deba@693
  2906
        _map.set(_key, _map[_key] & value);
deba@693
  2907
        return *this;
deba@693
  2908
      }
deba@693
  2909
      Reference& operator|=(int value) {
deba@693
  2910
        _map.set(_key, _map[_key] | value);
deba@693
  2911
        return *this;
deba@693
  2912
      }
deba@693
  2913
      Reference& operator^=(int value) {
deba@693
  2914
        _map.set(_key, _map[_key] ^ value);
deba@693
  2915
        return *this;
deba@693
  2916
      }
deba@693
  2917
      Reference& operator<<=(int value) {
deba@693
  2918
        _map.set(_key, _map[_key] << value);
deba@693
  2919
        return *this;
deba@693
  2920
      }
deba@693
  2921
      Reference& operator>>=(int value) {
deba@693
  2922
        _map.set(_key, _map[_key] >> value);
deba@693
  2923
        return *this;
deba@693
  2924
      }
deba@693
  2925
deba@693
  2926
    private:
deba@693
  2927
      Key _key;
deba@693
  2928
      IterableIntMap& _map;
deba@693
  2929
    };
deba@693
  2930
deba@693
  2931
    /// The const reference type.
deba@693
  2932
    typedef const Value& ConstReference;
deba@693
  2933
deba@693
  2934
    /// \brief Gives back the maximal value plus one.
deba@693
  2935
    ///
deba@693
  2936
    /// Gives back the maximal value plus one.
deba@693
  2937
    int size() const {
deba@693
  2938
      return _first.size();
deba@693
  2939
    }
deba@693
  2940
deba@693
  2941
    /// \brief Set operation of the map.
deba@693
  2942
    ///
deba@693
  2943
    /// Set operation of the map.
deba@693
  2944
    void set(const Key& key, const Value& value) {
deba@693
  2945
      unlace(key);
deba@693
  2946
      Parent::operator[](key).value = value;
deba@693
  2947
      lace(key);
deba@693
  2948
    }
deba@693
  2949
deba@693
  2950
    /// \brief Const subscript operator of the map.
deba@693
  2951
    ///
deba@693
  2952
    /// Const subscript operator of the map.
deba@693
  2953
    const Value& operator[](const Key& key) const {
deba@693
  2954
      return Parent::operator[](key).value;
deba@693
  2955
    }
deba@693
  2956
deba@693
  2957
    /// \brief Subscript operator of the map.
deba@693
  2958
    ///
deba@693
  2959
    /// Subscript operator of the map.
deba@693
  2960
    Reference operator[](const Key& key) {
deba@693
  2961
      return Reference(*this, key);
deba@693
  2962
    }
deba@693
  2963
deba@693
  2964
    /// \brief Iterator for the keys with the same value.
deba@693
  2965
    ///
deba@693
  2966
    /// Iterator for the keys with the same value. It works
kpeter@694
  2967
    /// like a graph item iterator, it can be converted to
deba@693
  2968
    /// the item type of the map, incremented with \c ++ operator, and
kpeter@694
  2969
    /// if the iterator leaves the last valid item, it will be equal to
deba@693
  2970
    /// \c INVALID.
kpeter@694
  2971
    class ItemIt : public Key {
deba@693
  2972
    public:
kpeter@694
  2973
      typedef Key Parent;
deba@693
  2974
deba@693
  2975
      /// \brief Invalid constructor \& conversion.
deba@693
  2976
      ///
kpeter@694
  2977
      /// This constructor initializes the iterator to be invalid.
deba@693
  2978
      /// \sa Invalid for more details.
deba@693
  2979
      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
deba@693
  2980
deba@693
  2981
      /// \brief Creates an iterator with a value.
deba@693
  2982
      ///
deba@693
  2983
      /// Creates an iterator with a value. It iterates on the
kpeter@694
  2984
      /// keys mapped to the given value.
kpeter@694
  2985
      /// \param map The IterableIntMap.
kpeter@694
  2986
      /// \param value The value.
deba@693
  2987
      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
deba@693
  2988
        if (value < 0 || value >= int(_map->_first.size())) {
deba@693
  2989
          Parent::operator=(INVALID);
deba@693
  2990
        } else {
deba@693
  2991
          Parent::operator=(_map->_first[value]);
deba@693
  2992
        }
deba@693
  2993
      }
deba@693
  2994
deba@693
  2995
      /// \brief Increment operator.
deba@693
  2996
      ///
kpeter@694
  2997
      /// Increment operator.
deba@693
  2998
      ItemIt& operator++() {
deba@693
  2999
        Parent::operator=(_map->IterableIntMap::Parent::
deba@693
  3000
                          operator[](static_cast<Parent&>(*this)).next);
deba@693
  3001
        return *this;
deba@693
  3002
      }
deba@693
  3003
deba@693
  3004
    private:
deba@693
  3005
      const IterableIntMap* _map;
deba@693
  3006
    };
deba@693
  3007
deba@693
  3008
  protected:
deba@693
  3009
deba@693
  3010
    virtual void erase(const Key& key) {
deba@693
  3011
      unlace(key);
deba@693
  3012
      Parent::erase(key);
deba@693
  3013
    }
deba@693
  3014
deba@693
  3015
    virtual void erase(const std::vector<Key>& keys) {
deba@693
  3016
      for (int i = 0; i < int(keys.size()); ++i) {
deba@693
  3017
        unlace(keys[i]);
deba@693
  3018
      }
deba@693
  3019
      Parent::erase(keys);
deba@693
  3020
    }
deba@693
  3021
deba@693
  3022
    virtual void clear() {
deba@693
  3023
      _first.clear();
deba@693
  3024
      Parent::clear();
deba@693
  3025
    }
deba@693
  3026
deba@693
  3027
  private:
kpeter@694
  3028
    std::vector<Key> _first;
deba@693
  3029
  };
deba@693
  3030
deba@693
  3031
  namespace _maps_bits {
deba@693
  3032
    template <typename Item, typename Value>
deba@693
  3033
    struct IterableValueMapNode {
deba@693
  3034
      IterableValueMapNode(Value _value = Value()) : value(_value) {}
deba@693
  3035
      Item prev, next;
deba@693
  3036
      Value value;
deba@693
  3037
    };
deba@693
  3038
  }
deba@693
  3039
deba@693
  3040
  /// \brief Dynamic iterable map for comparable values.
deba@693
  3041
  ///
kpeter@722
  3042
  /// This class provides a special graph map type which can store a
kpeter@694
  3043
  /// comparable value for graph items (\c Node, \c Arc or \c Edge).
kpeter@694
  3044
  /// For each value it is possible to iterate on the keys mapped to
kpeter@722
  3045
  /// the value (\c ItemIt), and the values of the map can be accessed
kpeter@724
  3046
  /// with an STL compatible forward iterator (\c ValueIt).
kpeter@722
  3047
  /// The map stores a linked list for each value, which contains
kpeter@722
  3048
  /// the items mapped to the value, and the used values are stored
kpeter@722
  3049
  /// in balanced binary tree (\c std::map).
kpeter@694
  3050
  ///
kpeter@722
  3051
  /// \ref IterableBoolMap and \ref IterableIntMap are similar classes
kpeter@722
  3052
  /// specialized for \c bool and \c int values, respectively.
deba@693
  3053
  ///
kpeter@694
  3054
  /// This type is not reference map, so it cannot be modified with
alpar@695
  3055
  /// the subscript operator.
deba@693
  3056
  ///
kpeter@694
  3057
  /// \tparam GR The graph type.
kpeter@694
  3058
  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
kpeter@694
  3059
  /// \c GR::Edge).
kpeter@694
  3060
  /// \tparam V The value type of the map. It can be any comparable
kpeter@694
  3061
  /// value type.
deba@693
  3062
  ///
kpeter@694
  3063
  /// \see IterableBoolMap, IterableIntMap
kpeter@694
  3064
  /// \see CrossRefMap
kpeter@694
  3065
  template <typename GR, typename K, typename V>
deba@693
  3066
  class IterableValueMap
kpeter@694
  3067
    : protected ItemSetTraits<GR, K>::
kpeter@694
  3068
        template Map<_maps_bits::IterableValueMapNode<K, V> >::Type {
deba@693
  3069
  public:
kpeter@694
  3070
    typedef typename ItemSetTraits<GR, K>::
kpeter@694
  3071
      template Map<_maps_bits::IterableValueMapNode<K, V> >::Type Parent;
deba@693
  3072
deba@693
  3073
    /// The key type
kpeter@694
  3074
    typedef K Key;
deba@693
  3075
    /// The value type
kpeter@694
  3076
    typedef V Value;
deba@693
  3077
    /// The graph type
deba@693
  3078
    typedef GR Graph;
deba@693
  3079
deba@693
  3080
  public:
deba@693
  3081
kpeter@694
  3082
    /// \brief Constructor of the map with a given value.
deba@693
  3083
    ///
kpeter@694
  3084
    /// Constructor of the map with a given value.
deba@693
  3085
    explicit IterableValueMap(const Graph& graph,
deba@693
  3086
                              const Value& value = Value())
kpeter@694
  3087
      : Parent(graph, _maps_bits::IterableValueMapNode<K, V>(value)) {
deba@693
  3088
      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
deba@693
  3089
        lace(it);
deba@693
  3090
      }
deba@693
  3091
    }
deba@693
  3092
deba@693
  3093
  protected:
deba@693
  3094
deba@693
  3095
    void unlace(const Key& key) {
deba@693
  3096
      typename Parent::Value& node = Parent::operator[](key);
deba@693
  3097
      if (node.prev != INVALID) {
deba@693
  3098
        Parent::operator[](node.prev).next = node.next;
deba@693
  3099
      } else {
deba@693
  3100
        if (node.next != INVALID) {
deba@693
  3101
          _first[node.value] = node.next;
deba@693
  3102
        } else {
deba@693
  3103
          _first.erase(node.value);
deba@693
  3104
        }
deba@693
  3105
      }
deba@693
  3106
      if (node.next != INVALID) {
deba@693
  3107
        Parent::operator[](node.next).prev = node.prev;
deba@693
  3108
      }
deba@693
  3109
    }
deba@693
  3110
deba@693
  3111
    void lace(const Key& key) {
deba@693
  3112
      typename Parent::Value& node = Parent::operator[](key);
deba@693
  3113
      typename std::map<Value, Key>::iterator it = _first.find(node.value);
deba@693
  3114
      if (it == _first.end()) {
deba@693
  3115
        node.prev = node.next = INVALID;
deba@693
  3116
        _first.insert(std::make_pair(node.value, key));
deba@693
  3117
      } else {
deba@693
  3118
        node.prev = INVALID;
deba@693
  3119
        node.next = it->second;
deba@693
  3120
        if (node.next != INVALID) {
deba@693
  3121
          Parent::operator[](node.next).prev = key;
deba@693
  3122
        }
deba@693
  3123
        it->second = key;
deba@693
  3124
      }
deba@693
  3125
    }
deba@693
  3126
deba@693
  3127
  public:
deba@693
  3128
deba@693
  3129
    /// \brief Forward iterator for values.
deba@693
  3130
    ///
kpeter@722
  3131
    /// This iterator is an STL compatible forward
deba@693
  3132
    /// iterator on the values of the map. The values can
kpeter@694
  3133
    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
kpeter@724
  3134
    class ValueIt
deba@693
  3135
      : public std::iterator<std::forward_iterator_tag, Value> {
deba@693
  3136
      friend class IterableValueMap;
deba@693
  3137
    private:
kpeter@724
  3138
      ValueIt(typename std::map<Value, Key>::const_iterator _it)
deba@693
  3139
        : it(_it) {}
deba@693
  3140
    public:
deba@693
  3141
kpeter@722
  3142
      /// Constructor
kpeter@724
  3143
      ValueIt() {}
kpeter@694
  3144
kpeter@722
  3145
      /// \e
kpeter@724
  3146
      ValueIt& operator++() { ++it; return *this; }
kpeter@722
  3147
      /// \e
kpeter@724
  3148
      ValueIt operator++(int) {
kpeter@724
  3149
        ValueIt tmp(*this);
deba@693
  3150
        operator++();
deba@693
  3151
        return tmp;
deba@693
  3152
      }
deba@693
  3153
kpeter@722
  3154
      /// \e
deba@693
  3155
      const Value& operator*() const { return it->first; }
kpeter@722
  3156
      /// \e
deba@693
  3157
      const Value* operator->() const { return &(it->first); }
deba@693
  3158
kpeter@722
  3159
      /// \e
kpeter@724
  3160
      bool operator==(ValueIt jt) const { return it == jt.it; }
kpeter@722
  3161
      /// \e
kpeter@724
  3162
      bool operator!=(ValueIt jt) const { return it != jt.it; }
deba@693
  3163
deba@693
  3164
    private:
deba@693
  3165
      typename std::map<Value, Key>::const_iterator it;
deba@693
  3166
    };
deba@693
  3167
deba@693
  3168
    /// \brief Returns an iterator to the first value.
deba@693
  3169
    ///
kpeter@722
  3170
    /// Returns an STL compatible iterator to the
deba@693
  3171
    /// first value of the map. The values of the
kpeter@694
  3172
    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
deba@693
  3173
    /// range.
kpeter@724
  3174
    ValueIt beginValue() const {
kpeter@724
  3175
      return ValueIt(_first.begin());
deba@693
  3176
    }
deba@693
  3177
deba@693
  3178
    /// \brief Returns an iterator after the last value.
deba@693
  3179
    ///
kpeter@722
  3180
    /// Returns an STL compatible iterator after the
deba@693
  3181
    /// last value of the map. The values of the
kpeter@694
  3182
    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
deba@693
  3183
    /// range.
kpeter@724
  3184
    ValueIt endValue() const {
kpeter@724
  3185
      return ValueIt(_first.end());
deba@693
  3186
    }
deba@693
  3187
deba@693
  3188
    /// \brief Set operation of the map.
deba@693
  3189
    ///
deba@693
  3190
    /// Set operation of the map.
deba@693
  3191
    void set(const Key& key, const Value& value) {
deba@693
  3192
      unlace(key);
deba@693
  3193
      Parent::operator[](key).value = value;
deba@693
  3194
      lace(key);
deba@693
  3195
    }
deba@693
  3196
deba@693
  3197
    /// \brief Const subscript operator of the map.
deba@693
  3198
    ///
deba@693
  3199
    /// Const subscript operator of the map.
deba@693
  3200
    const Value& operator[](const Key& key) const {
deba@693
  3201
      return Parent::operator[](key).value;
deba@693
  3202
    }
deba@693
  3203
deba@693
  3204
    /// \brief Iterator for the keys with the same value.
deba@693
  3205
    ///
deba@693
  3206
    /// Iterator for the keys with the same value. It works
kpeter@694
  3207
    /// like a graph item iterator, it can be converted to
deba@693
  3208
    /// the item type of the map, incremented with \c ++ operator, and
kpeter@694
  3209
    /// if the iterator leaves the last valid item, it will be equal to
deba@693
  3210
    /// \c INVALID.
kpeter@694
  3211
    class ItemIt : public Key {
deba@693
  3212
    public:
kpeter@694
  3213
      typedef Key Parent;
deba@693
  3214
deba@693
  3215
      /// \brief Invalid constructor \& conversion.
deba@693
  3216
      ///
kpeter@694
  3217
      /// This constructor initializes the iterator to be invalid.
deba@693
  3218
      /// \sa Invalid for more details.
deba@693
  3219
      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
deba@693
  3220
deba@693
  3221
      /// \brief Creates an iterator with a value.
deba@693
  3222
      ///
deba@693
  3223
      /// Creates an iterator with a value. It iterates on the
deba@693
  3224
      /// keys which have the given value.
deba@693
  3225
      /// \param map The IterableValueMap
deba@693
  3226
      /// \param value The value
deba@693
  3227
      ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
deba@693
  3228
        typename std::map<Value, Key>::const_iterator it =
deba@693
  3229
          map._first.find(value);
deba@693
  3230
        if (it == map._first.end()) {
deba@693
  3231
          Parent::operator=(INVALID);
deba@693
  3232
        } else {
deba@693
  3233
          Parent::operator=(it->second);
deba@693
  3234
        }
deba@693
  3235
      }
deba@693
  3236
deba@693
  3237
      /// \brief Increment operator.
deba@693
  3238
      ///
deba@693
  3239
      /// Increment Operator.
deba@693
  3240
      ItemIt& operator++() {
deba@693
  3241
        Parent::operator=(_map->IterableValueMap::Parent::
deba@693
  3242
                          operator[](static_cast<Parent&>(*this)).next);
deba@693
  3243
        return *this;
deba@693
  3244
      }
deba@693
  3245
deba@693
  3246
deba@693
  3247
    private:
deba@693
  3248
      const IterableValueMap* _map;
deba@693
  3249
    };
deba@693
  3250
deba@693
  3251
  protected:
deba@693
  3252
deba@693
  3253
    virtual void add(const Key& key) {
deba@693
  3254
      Parent::add(key);
deba@693
  3255
      unlace(key);
deba@693
  3256
    }
deba@693
  3257
deba@693
  3258
    virtual void add(const std::vector<Key>& keys) {
deba@693
  3259
      Parent::add(keys);
deba@693
  3260
      for (int i = 0; i < int(keys.size()); ++i) {
deba@693
  3261
        lace(keys[i]);
deba@693
  3262
      }
deba@693
  3263
    }
deba@693
  3264
deba@693
  3265
    virtual void erase(const Key& key) {
deba@693
  3266
      unlace(key);
deba@693
  3267
      Parent::erase(key);
deba@693
  3268
    }
deba@693
  3269
deba@693
  3270
    virtual void erase(const std::vector<Key>& keys) {
deba@693
  3271
      for (int i = 0; i < int(keys.size()); ++i) {
deba@693
  3272
        unlace(keys[i]);
deba@693
  3273
      }
deba@693
  3274
      Parent::erase(keys);
deba@693
  3275
    }
deba@693
  3276
deba@693
  3277
    virtual void build() {
deba@693
  3278
      Parent::build();
deba@693
  3279
      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
deba@693
  3280
        lace(it);
deba@693
  3281
      }
deba@693
  3282
    }
deba@693
  3283
deba@693
  3284
    virtual void clear() {
deba@693
  3285
      _first.clear();
deba@693
  3286
      Parent::clear();
deba@693
  3287
    }
deba@693
  3288
deba@693
  3289
  private:
deba@693
  3290
    std::map<Value, Key> _first;
deba@693
  3291
  };
deba@693
  3292
kpeter@559
  3293
  /// \brief Map of the source nodes of arcs in a digraph.
deba@220
  3294
  ///
kpeter@559
  3295
  /// SourceMap provides access for the source node of each arc in a digraph,
kpeter@559
  3296
  /// which is returned by the \c source() function of the digraph.
kpeter@559
  3297
  /// \tparam GR The digraph type.
deba@220
  3298
  /// \see TargetMap
kpeter@559
  3299
  template <typename GR>
deba@220
  3300
  class SourceMap {
deba@220
  3301
  public:
deba@220
  3302
kpeter@724
  3303
    /// The key type (the \c Arc type of the digraph).
kpeter@559
  3304
    typedef typename GR::Arc Key;
kpeter@724
  3305
    /// The value type (the \c Node type of the digraph).
kpeter@559
  3306
    typedef typename GR::Node Value;
deba@220
  3307
deba@220
  3308
    /// \brief Constructor
deba@220
  3309
    ///
kpeter@559
  3310
    /// Constructor.
kpeter@313
  3311
    /// \param digraph The digraph that the map belongs to.
kpeter@559
  3312
    explicit SourceMap(const GR& digraph) : _graph(digraph) {}
kpeter@559
  3313
kpeter@559
  3314
    /// \brief Returns the source node of the given arc.
deba@220
  3315
    ///
kpeter@559
  3316
    /// Returns the source node of the given arc.
deba@220
  3317
    Value operator[](const Key& arc) const {
kpeter@559
  3318
      return _graph.source(arc);
deba@220
  3319
    }
deba@220
  3320
deba@220
  3321
  private:
kpeter@559
  3322
    const GR& _graph;
deba@220
  3323
  };
deba@220
  3324
kpeter@301
  3325
  /// \brief Returns a \c SourceMap class.
deba@220
  3326
  ///
kpeter@301
  3327
  /// This function just returns an \c SourceMap class.
deba@220
  3328
  /// \relates SourceMap
kpeter@559
  3329
  template <typename GR>
kpeter@559
  3330
  inline SourceMap<GR> sourceMap(const GR& graph) {
kpeter@559
  3331
    return SourceMap<GR>(graph);
deba@220
  3332
  }
deba@220
  3333
kpeter@559
  3334
  /// \brief Map of the target nodes of arcs in a digraph.
deba@220
  3335
  ///
kpeter@559
  3336
  /// TargetMap provides access for the target node of each arc in a digraph,
kpeter@559
  3337
  /// which is returned by the \c target() function of the digraph.
kpeter@559
  3338
  /// \tparam GR The digraph type.
deba@220
  3339
  /// \see SourceMap
kpeter@559
  3340
  template <typename GR>
deba@220
  3341
  class TargetMap {
deba@220
  3342
  public:
deba@220
  3343
kpeter@724
  3344
    /// The key type (the \c Arc type of the digraph).
kpeter@559
  3345
    typedef typename GR::Arc Key;
kpeter@724
  3346
    /// The value type (the \c Node type of the digraph).
kpeter@559
  3347
    typedef typename GR::Node Value;
deba@220
  3348
deba@220
  3349
    /// \brief Constructor
deba@220
  3350
    ///
kpeter@559
  3351
    /// Constructor.
kpeter@313
  3352
    /// \param digraph The digraph that the map belongs to.
kpeter@559
  3353
    explicit TargetMap(const GR& digraph) : _graph(digraph) {}
kpeter@559
  3354
kpeter@559
  3355
    /// \brief Returns the target node of the given arc.
deba@220
  3356
    ///
kpeter@559
  3357
    /// Returns the target node of the given arc.
deba@220
  3358
    Value operator[](const Key& e) const {
kpeter@559
  3359
      return _graph.target(e);
deba@220
  3360
    }
deba@220
  3361
deba@220
  3362
  private:
kpeter@559
  3363
    const GR& _graph;
deba@220
  3364
  };
deba@220
  3365
kpeter@301
  3366
  /// \brief Returns a \c TargetMap class.
deba@220
  3367
  ///
kpeter@301
  3368
  /// This function just returns a \c TargetMap class.
deba@220
  3369
  /// \relates TargetMap
kpeter@559
  3370
  template <typename GR>
kpeter@559
  3371
  inline TargetMap<GR> targetMap(const GR& graph) {
kpeter@559
  3372
    return TargetMap<GR>(graph);
deba@220
  3373
  }
deba@220
  3374
kpeter@559
  3375
  /// \brief Map of the "forward" directed arc view of edges in a graph.
deba@220
  3376
  ///
kpeter@559
  3377
  /// ForwardMap provides access for the "forward" directed arc view of
kpeter@559
  3378
  /// each edge in a graph, which is returned by the \c direct() function
kpeter@559
  3379
  /// of the graph with \c true parameter.
kpeter@559
  3380
  /// \tparam GR The graph type.
deba@220
  3381
  /// \see BackwardMap
kpeter@559
  3382
  template <typename GR>
deba@220
  3383
  class ForwardMap {
deba@220
  3384
  public:
deba@220
  3385
kpeter@724
  3386
    /// The key type (the \c Edge type of the digraph).
kpeter@724
  3387
    typedef typename GR::Edge Key;
kpeter@724
  3388
    /// The value type (the \c Arc type of the digraph).
kpeter@559
  3389
    typedef typename GR::Arc Value;
deba@220
  3390
deba@220
  3391
    /// \brief Constructor
deba@220
  3392
    ///
kpeter@559
  3393
    /// Constructor.
kpeter@313
  3394
    /// \param graph The graph that the map belongs to.
kpeter@559
  3395
    explicit ForwardMap(const GR& graph) : _graph(graph) {}
kpeter@559
  3396
kpeter@559
  3397
    /// \brief Returns the "forward" directed arc view of the given edge.
deba@220
  3398
    ///
kpeter@559
  3399
    /// Returns the "forward" directed arc view of the given edge.
deba@220
  3400
    Value operator[](const Key& key) const {
deba@220
  3401
      return _graph.direct(key, true);
deba@220
  3402
    }
deba@220
  3403
deba@220
  3404
  private:
kpeter@559
  3405
    const GR& _graph;
deba@220
  3406
  };
deba@220
  3407
kpeter@301
  3408
  /// \brief Returns a \c ForwardMap class.
deba@220
  3409
  ///
kpeter@301
  3410
  /// This function just returns an \c ForwardMap class.
deba@220
  3411
  /// \relates ForwardMap
kpeter@559
  3412
  template <typename GR>
kpeter@559
  3413
  inline ForwardMap<GR> forwardMap(const GR& graph) {
kpeter@559
  3414
    return ForwardMap<GR>(graph);
deba@220
  3415
  }
deba@220
  3416
kpeter@559
  3417
  /// \brief Map of the "backward" directed arc view of edges in a graph.
deba@220
  3418
  ///
kpeter@559
  3419
  /// BackwardMap provides access for the "backward" directed arc view of
kpeter@559
  3420
  /// each edge in a graph, which is returned by the \c direct() function
kpeter@559
  3421
  /// of the graph with \c false parameter.
kpeter@559
  3422
  /// \tparam GR The graph type.
deba@220
  3423
  /// \see ForwardMap
kpeter@559
  3424
  template <typename GR>
deba@220
  3425
  class BackwardMap {
deba@220
  3426
  public:
deba@220
  3427
kpeter@724
  3428
    /// The key type (the \c Edge type of the digraph).
kpeter@724
  3429
    typedef typename GR::Edge Key;
kpeter@724
  3430
    /// The value type (the \c Arc type of the digraph).
kpeter@559
  3431
    typedef typename GR::Arc Value;
deba@220
  3432
deba@220
  3433
    /// \brief Constructor
deba@220
  3434
    ///
kpeter@559
  3435
    /// Constructor.
kpeter@313
  3436
    /// \param graph The graph that the map belongs to.
kpeter@559
  3437
    explicit BackwardMap(const GR& graph) : _graph(graph) {}
kpeter@559
  3438
kpeter@559
  3439
    /// \brief Returns the "backward" directed arc view of the given edge.
deba@220
  3440
    ///
kpeter@559
  3441
    /// Returns the "backward" directed arc view of the given edge.
deba@220
  3442
    Value operator[](const Key& key) const {
deba@220
  3443
      return _graph.direct(key, false);
deba@220
  3444
    }
deba@220
  3445
deba@220
  3446
  private:
kpeter@559
  3447
    const GR& _graph;
deba@220
  3448
  };
deba@220
  3449
kpeter@301
  3450
  /// \brief Returns a \c BackwardMap class
kpeter@301
  3451
kpeter@301
  3452
  /// This function just returns a \c BackwardMap class.
deba@220
  3453
  /// \relates BackwardMap
kpeter@559
  3454
  template <typename GR>
kpeter@559
  3455
  inline BackwardMap<GR> backwardMap(const GR& graph) {
kpeter@559
  3456
    return BackwardMap<GR>(graph);
deba@220
  3457
  }
deba@220
  3458
kpeter@559
  3459
  /// \brief Map of the in-degrees of nodes in a digraph.
deba@220
  3460
  ///
deba@220
  3461
  /// This map returns the in-degree of a node. Once it is constructed,
kpeter@559
  3462
  /// the degrees are stored in a standard \c NodeMap, so each query is done
deba@220
  3463
  /// in constant time. On the other hand, the values are updated automatically
deba@220
  3464
  /// whenever the digraph changes.
deba@220
  3465
  ///
deba@693
  3466
  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
kpeter@559
  3467
  /// may provide alternative ways to modify the digraph.
kpeter@559
  3468
  /// The correct behavior of InDegMap is not guarantied if these additional
kpeter@786
  3469
  /// features are used. For example, the functions
kpeter@559
  3470
  /// \ref ListDigraph::changeSource() "changeSource()",
deba@220
  3471
  /// \ref ListDigraph::changeTarget() "changeTarget()" and
deba@220
  3472
  /// \ref ListDigraph::reverseArc() "reverseArc()"
deba@220
  3473
  /// of \ref ListDigraph will \e not update the degree values correctly.
deba@220
  3474
  ///
deba@220
  3475
  /// \sa OutDegMap
kpeter@559
  3476
  template <typename GR>
deba@220
  3477
  class InDegMap
kpeter@559
  3478
    : protected ItemSetTraits<GR, typename GR::Arc>
deba@220
  3479
      ::ItemNotifier::ObserverBase {
deba@220
  3480
deba@220
  3481
  public:
deba@693
  3482
kpeter@617
  3483
    /// The graph type of InDegMap
kpeter@617
  3484
    typedef GR Graph;
kpeter@559
  3485
    typedef GR Digraph;
kpeter@559
  3486
    /// The key type
kpeter@559
  3487
    typedef typename Digraph::Node Key;
kpeter@559
  3488
    /// The value type
deba@220
  3489
    typedef int Value;
deba@220
  3490
deba@220
  3491
    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
deba@220
  3492
    ::ItemNotifier::ObserverBase Parent;
deba@220
  3493
deba@220
  3494
  private:
deba@220
  3495
deba@220
  3496
    class AutoNodeMap
deba@220
  3497
      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
deba@220
  3498
    public:
deba@220
  3499
deba@220
  3500
      typedef typename ItemSetTraits<Digraph, Key>::
deba@220
  3501
      template Map<int>::Type Parent;
deba@220
  3502
deba@220
  3503
      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
deba@220
  3504
deba@220
  3505
      virtual void add(const Key& key) {
deba@220
  3506
        Parent::add(key);
deba@220
  3507
        Parent::set(key, 0);
deba@220
  3508
      }
deba@220
  3509
deba@220
  3510
      virtual void add(const std::vector<Key>& keys) {
deba@220
  3511
        Parent::add(keys);
deba@220
  3512
        for (int i = 0; i < int(keys.size()); ++i) {
deba@220
  3513
          Parent::set(keys[i], 0);
deba@220
  3514
        }
deba@220
  3515
      }
deba@220
  3516
deba@220
  3517
      virtual void build() {
deba@220
  3518
        Parent::build();
deba@220
  3519
        Key it;
deba@220
  3520
        typename Parent::Notifier* nf = Parent::notifier();
deba@220
  3521
        for (nf->first(it); it != INVALID; nf->next(it)) {
deba@220
  3522
          Parent::set(it, 0);
deba@220
  3523
        }
deba@220
  3524
      }
deba@220
  3525
    };
deba@220
  3526
deba@220
  3527
  public:
deba@220
  3528
deba@220
  3529
    /// \brief Constructor.
deba@220
  3530
    ///
kpeter@559
  3531
    /// Constructor for creating an in-degree map.
kpeter@559
  3532
    explicit InDegMap(const Digraph& graph)
kpeter@559
  3533
      : _digraph(graph), _deg(graph) {
deba@220
  3534
      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
deba@220
  3535
deba@220
  3536
      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220
  3537
        _deg[it] = countInArcs(_digraph, it);
deba@220
  3538
      }
deba@220
  3539
    }
deba@220
  3540
kpeter@559
  3541
    /// \brief Gives back the in-degree of a Node.
kpeter@559
  3542
    ///
deba@220
  3543
    /// Gives back the in-degree of a Node.
deba@220
  3544
    int operator[](const Key& key) const {
deba@220
  3545
      return _deg[key];
deba@220
  3546
    }
deba@220
  3547
deba@220
  3548
  protected:
deba@220
  3549
deba@220
  3550
    typedef typename Digraph::Arc Arc;
deba@220
  3551
deba@220
  3552
    virtual void add(const Arc& arc) {
deba@220
  3553
      ++_deg[_digraph.target(arc)];
deba@220
  3554
    }
deba@220
  3555
deba@220
  3556
    virtual void add(const std::vector<Arc>& arcs) {
deba@220
  3557
      for (int i = 0; i < int(arcs.size()); ++i) {
deba@220
  3558
        ++_deg[_digraph.target(arcs[i])];
deba@220
  3559
      }
deba@220
  3560
    }
deba@220
  3561
deba@220
  3562
    virtual void erase(const Arc& arc) {
deba@220
  3563
      --_deg[_digraph.target(arc)];
deba@220
  3564
    }
deba@220
  3565
deba@220
  3566
    virtual void erase(const std::vector<Arc>& arcs) {
deba@220
  3567
      for (int i = 0; i < int(arcs.size()); ++i) {
deba@220
  3568
        --_deg[_digraph.target(arcs[i])];
deba@220
  3569
      }
deba@220
  3570
    }
deba@220
  3571
deba@220
  3572
    virtual void build() {
deba@220
  3573
      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220
  3574
        _deg[it] = countInArcs(_digraph, it);
deba@220
  3575
      }
deba@220
  3576
    }
deba@220
  3577
deba@220
  3578
    virtual void clear() {
deba@220
  3579
      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220
  3580
        _deg[it] = 0;
deba@220
  3581
      }
deba@220
  3582
    }
deba@220
  3583
  private:
deba@220
  3584
deba@220
  3585
    const Digraph& _digraph;
deba@220
  3586
    AutoNodeMap _deg;
deba@220
  3587
  };
deba@220
  3588
kpeter@559
  3589
  /// \brief Map of the out-degrees of nodes in a digraph.
deba@220
  3590
  ///
deba@220
  3591
  /// This map returns the out-degree of a node. Once it is constructed,
kpeter@559
  3592
  /// the degrees are stored in a standard \c NodeMap, so each query is done
deba@220
  3593
  /// in constant time. On the other hand, the values are updated automatically
deba@220
  3594
  /// whenever the digraph changes.
deba@220
  3595
  ///
deba@693
  3596
  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
kpeter@559
  3597
  /// may provide alternative ways to modify the digraph.
kpeter@559
  3598
  /// The correct behavior of OutDegMap is not guarantied if these additional
kpeter@786
  3599
  /// features are used. For example, the functions
kpeter@559
  3600
  /// \ref ListDigraph::changeSource() "changeSource()",
deba@220
  3601
  /// \ref ListDigraph::changeTarget() "changeTarget()" and
deba@220
  3602
  /// \ref ListDigraph::reverseArc() "reverseArc()"
deba@220
  3603
  /// of \ref ListDigraph will \e not update the degree values correctly.
deba@220
  3604
  ///
deba@220
  3605
  /// \sa InDegMap
kpeter@559
  3606
  template <typename GR>
deba@220
  3607
  class OutDegMap
kpeter@559
  3608
    : protected ItemSetTraits<GR, typename GR::Arc>
deba@220
  3609
      ::ItemNotifier::ObserverBase {
deba@220
  3610
deba@220
  3611
  public:
deba@220
  3612
kpeter@617
  3613
    /// The graph type of OutDegMap
kpeter@617
  3614
    typedef GR Graph;
kpeter@559
  3615
    typedef GR Digraph;
kpeter@559
  3616
    /// The key type
kpeter@559
  3617
    typedef typename Digraph::Node Key;
kpeter@559
  3618
    /// The value type
deba@220
  3619
    typedef int Value;
deba@220
  3620
deba@220
  3621
    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
deba@220
  3622
    ::ItemNotifier::ObserverBase Parent;
deba@220
  3623
deba@220
  3624
  private:
deba@220
  3625
deba@220
  3626
    class AutoNodeMap
deba@220
  3627
      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
deba@220
  3628
    public:
deba@220
  3629
deba@220
  3630
      typedef typename ItemSetTraits<Digraph, Key>::
deba@220
  3631
      template Map<int>::Type Parent;
deba@220
  3632
deba@220
  3633
      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
deba@220
  3634
deba@220
  3635
      virtual void add(const Key& key) {
deba@220
  3636
        Parent::add(key);
deba@220
  3637
        Parent::set(key, 0);
deba@220
  3638
      }
deba@220
  3639
      virtual void add(const std::vector<Key>& keys) {
deba@220
  3640
        Parent::add(keys);
deba@220
  3641
        for (int i = 0; i < int(keys.size()); ++i) {
deba@220
  3642
          Parent::set(keys[i], 0);
deba@220
  3643
        }
deba@220
  3644
      }
deba@220
  3645
      virtual void build() {
deba@220
  3646
        Parent::build();
deba@220
  3647
        Key it;
deba@220
  3648
        typename Parent::Notifier* nf = Parent::notifier();
deba@220
  3649
        for (nf->first(it); it != INVALID; nf->next(it)) {
deba@220
  3650
          Parent::set(it, 0);
deba@220
  3651
        }
deba@220
  3652
      }
deba@220
  3653
    };
deba@220
  3654
deba@220
  3655
  public:
deba@220
  3656
deba@220
  3657
    /// \brief Constructor.
deba@220
  3658
    ///
kpeter@559
  3659
    /// Constructor for creating an out-degree map.
kpeter@559
  3660
    explicit OutDegMap(const Digraph& graph)
kpeter@559
  3661
      : _digraph(graph), _deg(graph) {
deba@220
  3662
      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
deba@220
  3663
deba@220
  3664
      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220
  3665
        _deg[it] = countOutArcs(_digraph, it);
deba@220
  3666
      }
deba@220
  3667
    }
deba@220
  3668
kpeter@559
  3669
    /// \brief Gives back the out-degree of a Node.
kpeter@559
  3670
    ///
deba@220
  3671
    /// Gives back the out-degree of a Node.
deba@220
  3672
    int operator[](const Key& key) const {
deba@220
  3673
      return _deg[key];
deba@220
  3674
    }
deba@220
  3675
deba@220
  3676
  protected:
deba@220
  3677
deba@220
  3678
    typedef typename Digraph::Arc Arc;
deba@220
  3679
deba@220
  3680
    virtual void add(const Arc& arc) {
deba@220
  3681
      ++_deg[_digraph.source(arc)];
deba@220
  3682
    }
deba@220
  3683
deba@220
  3684
    virtual void add(const std::vector<Arc>& arcs) {
deba@220
  3685
      for (int i = 0; i < int(arcs.size()); ++i) {
deba@220
  3686
        ++_deg[_digraph.source(arcs[i])];
deba@220
  3687
      }
deba@220
  3688
    }
deba@220
  3689
deba@220
  3690
    virtual void erase(const Arc& arc) {
deba@220
  3691
      --_deg[_digraph.source(arc)];
deba@220
  3692
    }
deba@220
  3693
deba@220
  3694
    virtual void erase(const std::vector<Arc>& arcs) {
deba@220
  3695
      for (int i = 0; i < int(arcs.size()); ++i) {
deba@220
  3696
        --_deg[_digraph.source(arcs[i])];
deba@220
  3697
      }
deba@220
  3698
    }
deba@220
  3699
deba@220
  3700
    virtual void build() {
deba@220
  3701
      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220
  3702
        _deg[it] = countOutArcs(_digraph, it);
deba@220
  3703
      }
deba@220
  3704
    }
deba@220
  3705
deba@220
  3706
    virtual void clear() {
deba@220
  3707
      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
deba@220
  3708
        _deg[it] = 0;
deba@220
  3709
      }
deba@220
  3710
    }
deba@220
  3711
  private:
deba@220
  3712
deba@220
  3713
    const Digraph& _digraph;
deba@220
  3714
    AutoNodeMap _deg;
deba@220
  3715
  };
deba@220
  3716
kpeter@559
  3717
  /// \brief Potential difference map
kpeter@559
  3718
  ///
kpeter@584
  3719
  /// PotentialDifferenceMap returns the difference between the potentials of
kpeter@584
  3720
  /// the source and target nodes of each arc in a digraph, i.e. it returns
kpeter@559
  3721
  /// \code
kpeter@559
  3722
  ///   potential[gr.target(arc)] - potential[gr.source(arc)].
kpeter@559
  3723
  /// \endcode
kpeter@559
  3724
  /// \tparam GR The digraph type.
kpeter@559
  3725
  /// \tparam POT A node map storing the potentials.
kpeter@559
  3726
  template <typename GR, typename POT>
kpeter@559
  3727
  class PotentialDifferenceMap {
kpeter@559
  3728
  public:
kpeter@559
  3729
    /// Key type
kpeter@559
  3730
    typedef typename GR::Arc Key;
kpeter@559
  3731
    /// Value type
kpeter@559
  3732
    typedef typename POT::Value Value;
kpeter@559
  3733
kpeter@559
  3734
    /// \brief Constructor
kpeter@559
  3735
    ///
kpeter@559
  3736
    /// Contructor of the map.
kpeter@559
  3737
    explicit PotentialDifferenceMap(const GR& gr,
kpeter@559
  3738
                                    const POT& potential)
kpeter@559
  3739
      : _digraph(gr), _potential(potential) {}
kpeter@559
  3740
kpeter@559
  3741
    /// \brief Returns the potential difference for the given arc.
kpeter@559
  3742
    ///
kpeter@559
  3743
    /// Returns the potential difference for the given arc, i.e.
kpeter@559
  3744
    /// \code
kpeter@559
  3745
    ///   potential[gr.target(arc)] - potential[gr.source(arc)].
kpeter@559
  3746
    /// \endcode
kpeter@559
  3747
    Value operator[](const Key& arc) const {
kpeter@559
  3748
      return _potential[_digraph.target(arc)] -
kpeter@559
  3749
        _potential[_digraph.source(arc)];
kpeter@559
  3750
    }
kpeter@559
  3751
kpeter@559
  3752
  private:
kpeter@559
  3753
    const GR& _digraph;
kpeter@559
  3754
    const POT& _potential;
kpeter@559
  3755
  };
kpeter@559
  3756
kpeter@559
  3757
  /// \brief Returns a PotentialDifferenceMap.
kpeter@559
  3758
  ///
kpeter@559
  3759
  /// This function just returns a PotentialDifferenceMap.
kpeter@559
  3760
  /// \relates PotentialDifferenceMap
kpeter@559
  3761
  template <typename GR, typename POT>
kpeter@559
  3762
  PotentialDifferenceMap<GR, POT>
kpeter@559
  3763
  potentialDifferenceMap(const GR& gr, const POT& potential) {
kpeter@559
  3764
    return PotentialDifferenceMap<GR, POT>(gr, potential);
kpeter@559
  3765
  }
kpeter@559
  3766
kpeter@789
  3767
kpeter@789
  3768
  /// \brief Copy the values of a graph map to another map.
kpeter@789
  3769
  ///
kpeter@789
  3770
  /// This function copies the values of a graph map to another graph map.
kpeter@789
  3771
  /// \c To::Key must be equal or convertible to \c From::Key and
kpeter@789
  3772
  /// \c From::Value must be equal or convertible to \c To::Value.
kpeter@789
  3773
  ///
kpeter@789
  3774
  /// For example, an edge map of \c int value type can be copied to
kpeter@789
  3775
  /// an arc map of \c double value type in an undirected graph, but
kpeter@789
  3776
  /// an arc map cannot be copied to an edge map.
kpeter@789
  3777
  /// Note that even a \ref ConstMap can be copied to a standard graph map,
kpeter@789
  3778
  /// but \ref mapFill() can also be used for this purpose.
kpeter@789
  3779
  ///
kpeter@789
  3780
  /// \param gr The graph for which the maps are defined.
kpeter@789
  3781
  /// \param from The map from which the values have to be copied.
kpeter@789
  3782
  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
kpeter@789
  3783
  /// \param to The map to which the values have to be copied.
kpeter@789
  3784
  /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
kpeter@789
  3785
  template <typename GR, typename From, typename To>
kpeter@789
  3786
  void mapCopy(const GR& gr, const From& from, To& to) {
kpeter@789
  3787
    typedef typename To::Key Item;
kpeter@789
  3788
    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
kpeter@789
  3789
    
kpeter@789
  3790
    for (ItemIt it(gr); it != INVALID; ++it) {
kpeter@789
  3791
      to.set(it, from[it]);
kpeter@789
  3792
    }
kpeter@789
  3793
  }
kpeter@789
  3794
kpeter@789
  3795
  /// \brief Compare two graph maps.
kpeter@789
  3796
  ///
kpeter@789
  3797
  /// This function compares the values of two graph maps. It returns 
kpeter@789
  3798
  /// \c true if the maps assign the same value for all items in the graph.
kpeter@789
  3799
  /// The \c Key type of the maps (\c Node, \c Arc or \c Edge) must be equal
kpeter@789
  3800
  /// and their \c Value types must be comparable using \c %operator==().
kpeter@789
  3801
  ///
kpeter@789
  3802
  /// \param gr The graph for which the maps are defined.
kpeter@789
  3803
  /// \param map1 The first map.
kpeter@789
  3804
  /// \param map2 The second map.
kpeter@789
  3805
  template <typename GR, typename Map1, typename Map2>
kpeter@789
  3806
  bool mapCompare(const GR& gr, const Map1& map1, const Map2& map2) {
kpeter@789
  3807
    typedef typename Map2::Key Item;
kpeter@789
  3808
    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
kpeter@789
  3809
    
kpeter@789
  3810
    for (ItemIt it(gr); it != INVALID; ++it) {
kpeter@789
  3811
      if (!(map1[it] == map2[it])) return false;
kpeter@789
  3812
    }
kpeter@789
  3813
    return true;
kpeter@789
  3814
  }
kpeter@789
  3815
kpeter@789
  3816
  /// \brief Return an item having minimum value of a graph map.
kpeter@789
  3817
  ///
kpeter@789
  3818
  /// This function returns an item (\c Node, \c Arc or \c Edge) having
kpeter@789
  3819
  /// minimum value of the given graph map.
kpeter@789
  3820
  /// If the item set is empty, it returns \c INVALID.
kpeter@789
  3821
  ///
kpeter@789
  3822
  /// \param gr The graph for which the map is defined.
kpeter@789
  3823
  /// \param map The graph map.
kpeter@789
  3824
  template <typename GR, typename Map>
kpeter@789
  3825
  typename Map::Key mapMin(const GR& gr, const Map& map) {
kpeter@789
  3826
    return mapMin(gr, map, std::less<typename Map::Value>());
kpeter@789
  3827
  }
kpeter@789
  3828
kpeter@789
  3829
  /// \brief Return an item having minimum value of a graph map.
kpeter@789
  3830
  ///
kpeter@789
  3831
  /// This function returns an item (\c Node, \c Arc or \c Edge) having
kpeter@789
  3832
  /// minimum value of the given graph map.
kpeter@789
  3833
  /// If the item set is empty, it returns \c INVALID.
kpeter@789
  3834
  ///
kpeter@789
  3835
  /// \param gr The graph for which the map is defined.
kpeter@789
  3836
  /// \param map The graph map.
kpeter@789
  3837
  /// \param comp Comparison function object.
kpeter@789
  3838
  template <typename GR, typename Map, typename Comp>
kpeter@789
  3839
  typename Map::Key mapMin(const GR& gr, const Map& map, const Comp& comp) {
kpeter@789
  3840
    typedef typename Map::Key Item;
kpeter@789
  3841
    typedef typename Map::Value Value;
kpeter@789
  3842
    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
kpeter@789
  3843
kpeter@789
  3844
    ItemIt min_item(gr);
kpeter@789
  3845
    if (min_item == INVALID) return INVALID;
kpeter@789
  3846
    Value min = map[min_item];
kpeter@789
  3847
    for (ItemIt it(gr); it != INVALID; ++it) {
kpeter@789
  3848
      if (comp(map[it], min)) {
kpeter@789
  3849
        min = map[it];
kpeter@789
  3850
        min_item = it;
kpeter@789
  3851
      }
kpeter@789
  3852
    }
kpeter@789
  3853
    return min_item;
kpeter@789
  3854
  }
kpeter@789
  3855
kpeter@789
  3856
  /// \brief Return an item having maximum value of a graph map.
kpeter@789
  3857
  ///
kpeter@789
  3858
  /// This function returns an item (\c Node, \c Arc or \c Edge) having
kpeter@789
  3859
  /// maximum value of the given graph map.
kpeter@789
  3860
  /// If the item set is empty, it returns \c INVALID.
kpeter@789
  3861
  ///
kpeter@789
  3862
  /// \param gr The graph for which the map is defined.
kpeter@789
  3863
  /// \param map The graph map.
kpeter@789
  3864
  template <typename GR, typename Map>
kpeter@789
  3865
  typename Map::Key mapMax(const GR& gr, const Map& map) {
kpeter@789
  3866
    return mapMax(gr, map, std::less<typename Map::Value>());
kpeter@789
  3867
  }
kpeter@789
  3868
kpeter@789
  3869
  /// \brief Return an item having maximum value of a graph map.
kpeter@789
  3870
  ///
kpeter@789
  3871
  /// This function returns an item (\c Node, \c Arc or \c Edge) having
kpeter@789
  3872
  /// maximum value of the given graph map.
kpeter@789
  3873
  /// If the item set is empty, it returns \c INVALID.
kpeter@789
  3874
  ///
kpeter@789
  3875
  /// \param gr The graph for which the map is defined.
kpeter@789
  3876
  /// \param map The graph map.
kpeter@789
  3877
  /// \param comp Comparison function object.
kpeter@789
  3878
  template <typename GR, typename Map, typename Comp>
kpeter@789
  3879
  typename Map::Key mapMax(const GR& gr, const Map& map, const Comp& comp) {
kpeter@789
  3880
    typedef typename Map::Key Item;
kpeter@789
  3881
    typedef typename Map::Value Value;
kpeter@789
  3882
    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
kpeter@789
  3883
kpeter@789
  3884
    ItemIt max_item(gr);
kpeter@789
  3885
    if (max_item == INVALID) return INVALID;
kpeter@789
  3886
    Value max = map[max_item];
kpeter@789
  3887
    for (ItemIt it(gr); it != INVALID; ++it) {
kpeter@789
  3888
      if (comp(max, map[it])) {
kpeter@789
  3889
        max = map[it];
kpeter@789
  3890
        max_item = it;
kpeter@789
  3891
      }
kpeter@789
  3892
    }
kpeter@789
  3893
    return max_item;
kpeter@789
  3894
  }
kpeter@789
  3895
kpeter@789
  3896
  /// \brief Return the minimum value of a graph map.
kpeter@789
  3897
  ///
kpeter@789
  3898
  /// This function returns the minimum value of the given graph map.
kpeter@789
  3899
  /// The corresponding item set of the graph must not be empty.
kpeter@789
  3900
  ///
kpeter@789
  3901
  /// \param gr The graph for which the map is defined.
kpeter@789
  3902
  /// \param map The graph map.
kpeter@789
  3903
  template <typename GR, typename Map>
kpeter@789
  3904
  typename Map::Value mapMinValue(const GR& gr, const Map& map) {
kpeter@789
  3905
    return map[mapMin(gr, map, std::less<typename Map::Value>())];
kpeter@789
  3906
  }
kpeter@789
  3907
kpeter@789
  3908
  /// \brief Return the minimum value of a graph map.
kpeter@789
  3909
  ///
kpeter@789
  3910
  /// This function returns the minimum value of the given graph map.
kpeter@789
  3911
  /// The corresponding item set of the graph must not be empty.
kpeter@789
  3912
  ///
kpeter@789
  3913
  /// \param gr The graph for which the map is defined.
kpeter@789
  3914
  /// \param map The graph map.
kpeter@789
  3915
  /// \param comp Comparison function object.
kpeter@789
  3916
  template <typename GR, typename Map, typename Comp>
kpeter@789
  3917
  typename Map::Value
kpeter@789
  3918
  mapMinValue(const GR& gr, const Map& map, const Comp& comp) {
kpeter@789
  3919
    return map[mapMin(gr, map, comp)];
kpeter@789
  3920
  }
kpeter@789
  3921
kpeter@789
  3922
  /// \brief Return the maximum value of a graph map.
kpeter@789
  3923
  ///
kpeter@789
  3924
  /// This function returns the maximum value of the given graph map.
kpeter@789
  3925
  /// The corresponding item set of the graph must not be empty.
kpeter@789
  3926
  ///
kpeter@789
  3927
  /// \param gr The graph for which the map is defined.
kpeter@789
  3928
  /// \param map The graph map.
kpeter@789
  3929
  template <typename GR, typename Map>
kpeter@789
  3930
  typename Map::Value mapMaxValue(const GR& gr, const Map& map) {
kpeter@789
  3931
    return map[mapMax(gr, map, std::less<typename Map::Value>())];
kpeter@789
  3932
  }
kpeter@789
  3933
kpeter@789
  3934
  /// \brief Return the maximum value of a graph map.
kpeter@789
  3935
  ///
kpeter@789
  3936
  /// This function returns the maximum value of the given graph map.
kpeter@789
  3937
  /// The corresponding item set of the graph must not be empty.
kpeter@789
  3938
  ///
kpeter@789
  3939
  /// \param gr The graph for which the map is defined.
kpeter@789
  3940
  /// \param map The graph map.
kpeter@789
  3941
  /// \param comp Comparison function object.
kpeter@789
  3942
  template <typename GR, typename Map, typename Comp>
kpeter@789
  3943
  typename Map::Value
kpeter@789
  3944
  mapMaxValue(const GR& gr, const Map& map, const Comp& comp) {
kpeter@789
  3945
    return map[mapMax(gr, map, comp)];
kpeter@789
  3946
  }
kpeter@789
  3947
kpeter@789
  3948
  /// \brief Return an item having a specified value in a graph map.
kpeter@789
  3949
  ///
kpeter@789
  3950
  /// This function returns an item (\c Node, \c Arc or \c Edge) having
kpeter@789
  3951
  /// the specified assigned value in the given graph map.
kpeter@789
  3952
  /// If no such item exists, it returns \c INVALID.
kpeter@789
  3953
  ///
kpeter@789
  3954
  /// \param gr The graph for which the map is defined.
kpeter@789
  3955
  /// \param map The graph map.
kpeter@789
  3956
  /// \param val The value that have to be found.
kpeter@789
  3957
  template <typename GR, typename Map>
kpeter@789
  3958
  typename Map::Key
kpeter@789
  3959
  mapFind(const GR& gr, const Map& map, const typename Map::Value& val) {
kpeter@789
  3960
    typedef typename Map::Key Item;
kpeter@789
  3961
    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
kpeter@789
  3962
kpeter@789
  3963
    for (ItemIt it(gr); it != INVALID; ++it) {
kpeter@789
  3964
      if (map[it] == val) return it;
kpeter@789
  3965
    }
kpeter@789
  3966
    return INVALID;
kpeter@789
  3967
  }
kpeter@789
  3968
kpeter@789
  3969
  /// \brief Return an item having value for which a certain predicate is
kpeter@789
  3970
  /// true in a graph map.
kpeter@789
  3971
  ///
kpeter@789
  3972
  /// This function returns an item (\c Node, \c Arc or \c Edge) having
kpeter@789
  3973
  /// such assigned value for which the specified predicate is true
kpeter@789
  3974
  /// in the given graph map.
kpeter@789
  3975
  /// If no such item exists, it returns \c INVALID.
kpeter@789
  3976
  ///
kpeter@789
  3977
  /// \param gr The graph for which the map is defined.
kpeter@789
  3978
  /// \param map The graph map.
kpeter@789
  3979
  /// \param pred The predicate function object.
kpeter@789
  3980
  template <typename GR, typename Map, typename Pred>
kpeter@789
  3981
  typename Map::Key
kpeter@789
  3982
  mapFindIf(const GR& gr, const Map& map, const Pred& pred) {
kpeter@789
  3983
    typedef typename Map::Key Item;
kpeter@789
  3984
    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
kpeter@789
  3985
kpeter@789
  3986
    for (ItemIt it(gr); it != INVALID; ++it) {
kpeter@789
  3987
      if (pred(map[it])) return it;
kpeter@789
  3988
    }
kpeter@789
  3989
    return INVALID;
kpeter@789
  3990
  }
kpeter@789
  3991
kpeter@789
  3992
  /// \brief Return the number of items having a specified value in a
kpeter@789
  3993
  /// graph map.
kpeter@789
  3994
  ///
kpeter@789
  3995
  /// This function returns the number of items (\c Node, \c Arc or \c Edge)
kpeter@789
  3996
  /// having the specified assigned value in the given graph map.
kpeter@789
  3997
  ///
kpeter@789
  3998
  /// \param gr The graph for which the map is defined.
kpeter@789
  3999
  /// \param map The graph map.
kpeter@789
  4000
  /// \param val The value that have to be counted.
kpeter@789
  4001
  template <typename GR, typename Map>
kpeter@789
  4002
  int mapCount(const GR& gr, const Map& map, const typename Map::Value& val) {
kpeter@789
  4003
    typedef typename Map::Key Item;
kpeter@789
  4004
    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
kpeter@789
  4005
kpeter@789
  4006
    int cnt = 0;
kpeter@789
  4007
    for (ItemIt it(gr); it != INVALID; ++it) {
kpeter@789
  4008
      if (map[it] == val) ++cnt;
kpeter@789
  4009
    }
kpeter@789
  4010
    return cnt;
kpeter@789
  4011
  }
kpeter@789
  4012
kpeter@789
  4013
  /// \brief Return the number of items having values for which a certain
kpeter@789
  4014
  /// predicate is true in a graph map.
kpeter@789
  4015
  ///
kpeter@789
  4016
  /// This function returns the number of items (\c Node, \c Arc or \c Edge)
kpeter@789
  4017
  /// having such assigned values for which the specified predicate is true
kpeter@789
  4018
  /// in the given graph map.
kpeter@789
  4019
  ///
kpeter@789
  4020
  /// \param gr The graph for which the map is defined.
kpeter@789
  4021
  /// \param map The graph map.
kpeter@789
  4022
  /// \param pred The predicate function object.
kpeter@789
  4023
  template <typename GR, typename Map, typename Pred>
kpeter@789
  4024
  int mapCountIf(const GR& gr, const Map& map, const Pred& pred) {
kpeter@789
  4025
    typedef typename Map::Key Item;
kpeter@789
  4026
    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
kpeter@789
  4027
kpeter@789
  4028
    int cnt = 0;
kpeter@789
  4029
    for (ItemIt it(gr); it != INVALID; ++it) {
kpeter@789
  4030
      if (pred(map[it])) ++cnt;
kpeter@789
  4031
    }
kpeter@789
  4032
    return cnt;
kpeter@789
  4033
  }
kpeter@789
  4034
kpeter@789
  4035
  /// \brief Fill a graph map with a certain value.
kpeter@789
  4036
  ///
kpeter@789
  4037
  /// This function sets the specified value for all items (\c Node,
kpeter@789
  4038
  /// \c Arc or \c Edge) in the given graph map.
kpeter@789
  4039
  ///
kpeter@789
  4040
  /// \param gr The graph for which the map is defined.
kpeter@789
  4041
  /// \param map The graph map. It must conform to the
kpeter@789
  4042
  /// \ref concepts::WriteMap "WriteMap" concept.
kpeter@789
  4043
  /// \param val The value.
kpeter@789
  4044
  template <typename GR, typename Map>
kpeter@789
  4045
  void mapFill(const GR& gr, Map& map, const typename Map::Value& val) {
kpeter@789
  4046
    typedef typename Map::Key Item;
kpeter@789
  4047
    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
kpeter@789
  4048
kpeter@789
  4049
    for (ItemIt it(gr); it != INVALID; ++it) {
kpeter@789
  4050
      map.set(it, val);
kpeter@789
  4051
    }
kpeter@789
  4052
  }
kpeter@789
  4053
alpar@25
  4054
  /// @}
alpar@25
  4055
}
alpar@25
  4056
alpar@25
  4057
#endif // LEMON_MAPS_H