COIN-OR::LEMON - Graph Library

source: lemon-1.0/lemon/maps.h @ 88:18444049848b

Last change on this file since 88:18444049848b was 54:ff9bac2351bf, checked in by Peter Kovacs <kpeter@…>, 12 years ago

Minor bug fix in maps.h.
Fixed the existing two variants of stdMap() and added two new variants.

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