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