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