COIN-OR::LEMON - Graph Library

source: lemon-1.0/lemon/maps.h @ 45:bc69cdfe171c

Last change on this file since 45:bc69cdfe171c was 45:bc69cdfe171c, checked in by Peter Kovacs <kpeter@…>, 17 years ago

Added missing inheritances and map-creator functions.

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