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