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