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