COIN-OR::LEMON - Graph Library

source: lemon/lemon/maps.h @ 99:dbaa96cc1013

Last change on this file since 99:dbaa96cc1013 was 54:ff9bac2351bf, checked in by Peter Kovacs <kpeter@…>, 17 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
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
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 \ref concepts::ReadMap "readable" map which assigns a
85  /// specified value to each key.
86  /// In other aspects it is equivalent to \c NullMap.
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
99    /// Default constructor.
100    /// The value of the map will be uninitialized.
101    /// (More exactly it will be default constructed.)
102    ConstMap() {}
103   
104    /// Constructor with specified initial value
105
106    /// Constructor with specified initial value.
107    /// \param _v is the initial value of the map.
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
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.
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
154  ///Returns a \c ConstMap class with inlined value
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
163  ///Map based on \c std::map
164
165  ///This is essentially a wrapper for \c std::map with addition that
166  ///you can specify a default value different from \c Value().
167  ///It meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
168  template <typename K, typename T, typename Compare = std::less<K> >
169  class StdMap : public MapBase<K, T> {
170    template <typename K1, typename T1, typename C1>
171    friend class StdMap;
172  public:
173
174    typedef MapBase<K, T> Parent;
175    ///Key type
176    typedef typename Parent::Key Key;
177    ///Value type
178    typedef typename Parent::Value Value;
179    ///Reference Type
180    typedef T& Reference;
181    ///Const reference type
182    typedef const T& ConstReference;
183
184    typedef True ReferenceMapTag;
185
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) {}
196    /// \brief Constructs the map from an appropriate \c std::map, and
197    /// explicitly specifies a default value.
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   
202    /// \brief Constructs a map from an other \ref StdMap.
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  };
247 
248  ///Returns a \c StdMap class
249
250  ///This function just returns a \c StdMap class with specified
251  ///default value.
252  ///\relates StdMap
253  template<typename K, typename V, typename Compare>
254  inline StdMap<K, V, Compare> stdMap(const V& value = V()) {
255    return StdMap<K, V, Compare>(value);
256  }
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  }
278
279  ///Returns a \c StdMap class created from an appropriate std::map
280
281  ///This function just returns a \c StdMap class created from an
282  ///appropriate std::map.
283  ///\relates StdMap
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);
288  }
289
290  /// \brief Map for storing values for keys from the range <tt>[0..size-1]</tt>
291  ///
292  /// This map has the <tt>[0..size-1]</tt> keyset and the values
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
295  /// the used items are small integer numbers.
296  /// This map meets the \ref concepts::ReferenceMap "ReferenceMap" concept.
297  ///
298  /// \todo Revise its name
299  template <typename T>
300  class IntegerMap : public MapBase<int, T> {
301
302    template <typename T1>
303    friend class IntegerMap;
304
305  public:
306
307    typedef MapBase<int, T> Parent;
308    ///\e
309    typedef typename Parent::Key Key;
310    ///\e
311    typedef typename Parent::Value Value;
312    ///\e
313    typedef T& Reference;
314    ///\e
315    typedef const T& ConstReference;
316
317    typedef True ReferenceMapTag;
318
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
329    /// \brief Constructs the map from an appropriate \c std::vector.
330    template <typename T1>
331    IntegerMap(const std::vector<T1>& vector)
332      : _vector(vector.begin(), vector.end()) {}
333   
334    /// \brief Constructs a map from an other \ref IntegerMap.
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  };
366 
367  ///Returns an \c IntegerMap class
368
369  ///This function just returns an \c IntegerMap class.
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  }
375
376  /// @}
377
378  /// \addtogroup map_adaptors
379  /// @{
380
381  /// \brief Identity map.
382  ///
383  /// This map gives back the given key as value without any
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
408  ///\brief Convert the \c Value of a map to another type using
409  ///the default conversion.
410  ///
411  ///This \ref concepts::ReadMap "read only map"
412  ///converts the \c Value of a map to type \c T.
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
424    ///Constructor.
425    ///\param _m is the underlying map.
426    ConvertMap(const M &_m) : m(_m) {};
427
428    ///\e
429    Value operator[](const Key& k) const {return m[k];}
430  };
431 
432  ///Returns a \c ConvertMap class
433
434  ///This function just returns a \c ConvertMap class.
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
441  ///Simple wrapping of a map
442
443  ///This \ref concepts::ReadMap "read only map" returns the simple
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.
447  ///
448  ///\sa SimpleWriteMap
449  ///
450  /// \todo Revise the misleading name
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  };
465 
466  ///Returns a \c SimpleMap class
467
468  ///This function just returns a \c SimpleMap class.
469  ///\relates SimpleMap
470  template<typename M>
471  inline SimpleMap<M> simpleMap(const M &m) {
472    return SimpleMap<M>(m);
473  }
474
475  ///Simple writable wrapping of a map
476
477  ///This \ref concepts::ReadWriteMap "read-write map" returns the simple
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.
481  ///
482  ///\sa SimpleMap
483  ///
484  /// \todo Revise the misleading name
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
502  ///Returns a \c SimpleWriteMap class
503
504  ///This function just returns a \c SimpleWriteMap class.
505  ///\relates SimpleWriteMap
506  template<typename M>
507  inline SimpleWriteMap<M> simpleWriteMap(M &m) {
508    return SimpleWriteMap<M>(m);
509  }
510
511  ///Sum of two maps
512
513  ///This \ref concepts::ReadMap "read only map" returns the sum of the two
514  ///given maps.
515  ///Its \c Key and \c Value are inherited from \c M1.
516  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
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.
536  ///\todo Extend the documentation: how to call these type of functions?
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
546  ///This \ref concepts::ReadMap "read only map" returns the sum of the
547  ///given map and a constant value.
548  ///Its \c Key and \c Value are inherited from \c M.
549  ///
550  ///Actually,
551  ///\code
552  ///  ShiftMap<X> sh(x,v);
553  ///\endcode
554  ///is equivalent to
555  ///\code
556  ///  ConstMap<X::Key, X::Value> c_tmp(v);
557  ///  AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
558  ///\endcode
559  ///
560  ///\sa ShiftWriteMap
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
572    ///Constructor.
573    ///\param _m is the undelying map.
574    ///\param _v is the shift value.
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
580  ///Shift a map with a constant (ReadWrite version).
581
582  ///This \ref concepts::ReadWriteMap "read-write map" returns the sum of the
583  ///given map and a constant value. It makes also possible to write the map.
584  ///Its \c Key and \c Value are inherited from \c M.
585  ///
586  ///\sa ShiftMap
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
598    ///Constructor.
599    ///\param _m is the undelying map.
600    ///\param _v is the shift value.
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 
608  ///Returns a \c ShiftMap class
609
610  ///This function just returns a \c ShiftMap class.
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
617  ///Returns a \c ShiftWriteMap class
618
619  ///This function just returns a \c ShiftWriteMap class.
620  ///\relates ShiftWriteMap
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
628  ///This \ref concepts::ReadMap "read only map" returns the difference
629  ///of the values of the two given maps.
630  ///Its \c Key and \c Value are inherited from \c M1.
631  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
632  ///
633  /// \todo Revise the misleading name
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
661  ///This \ref concepts::ReadMap "read only map" returns the product of the
662  ///values of the two given maps.
663  ///Its \c Key and \c Value are inherited from \c M1.
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 
689  ///Scales a map with a constant.
690
691  ///This \ref concepts::ReadMap "read only map" returns the value of the
692  ///given map multiplied from the left side with a constant value.
693  ///Its \c Key and \c Value are inherited from \c M.
694  ///
695  ///Actually,
696  ///\code
697  ///  ScaleMap<X> sc(x,v);
698  ///\endcode
699  ///is equivalent to
700  ///\code
701  ///  ConstMap<X::Key, X::Value> c_tmp(v);
702  ///  MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
703  ///\endcode
704  ///
705  ///\sa ScaleWriteMap
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
717    ///Constructor.
718    ///\param _m is the undelying map.
719    ///\param _v is the scaling value.
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
725  ///Scales a map with a constant (ReadWrite version).
726
727  ///This \ref concepts::ReadWriteMap "read-write map" returns the value of the
728  ///given map multiplied from the left side with a constant value. It can
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
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
745    ///Constructor.
746    ///\param _m is the undelying map.
747    ///\param _v is the scaling value.
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 
755  ///Returns a \c ScaleMap class
756
757  ///This function just returns a \c ScaleMap class.
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
764  ///Returns a \c ScaleWriteMap class
765
766  ///This function just returns a \c ScaleWriteMap class.
767  ///\relates ScaleWriteMap
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
775  ///This \ref concepts::ReadMap "read only map" returns the quotient of the
776  ///values of the two given maps.
777  ///Its \c Key and \c Value are inherited from \c M1.
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
805  ///This \ref concepts::ReadMap "read only map" returns the composition of
806  ///two given maps.
807  ///That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2,
808  ///then for
809  ///\code
810  ///  ComposeMap<M1, M2> cm(m1,m2);
811  ///\endcode
812  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
813  ///
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  ///
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  };
842
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 
852  ///Combine of two maps using an STL (binary) functor.
853
854  ///Combine of two maps using an STL (binary) functor.
855  ///
856  ///This \ref concepts::ReadMap "read only map" takes two maps and a
857  ///binary functor and returns the composition of the two
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
860  ///and \c f is of \c F, then for
861  ///\code
862  ///  CombineMap<M1,M2,F,V> cm(m1,m2,f);
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.
867  ///\c M2::Value and \c M1::Value must be convertible to the corresponding
868  ///input parameter of \c F and the return type of \c F must be convertible
869  ///to \c V.
870  ///
871  ///\sa ComposeMap
872  ///
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
898  ///combineMap(m1,m2,std::plus<double>())
899  ///\endcode
900  ///is equivalent to
901  ///\code
902  ///addMap(m1,m2)
903  ///\endcode
904  ///
905  ///This function is specialized for adaptable binary function
906  ///classes and C++ functions.
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
929  ///This \ref concepts::ReadMap "read only map" returns the negative
930  ///value of the value returned by the given map.
931  ///Its \c Key and \c Value are inherited from \c M.
932  ///The unary \c - operator must be defined for \c Value, of course.
933  ///
934  ///\sa NegWriteMap
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 
949  ///Negative value of a map (ReadWrite version)
950
951  ///This \ref concepts::ReadWriteMap "read-write map" returns the negative
952  ///value of the value returned by the given map.
953  ///Its \c Key and \c Value are inherited from \c M.
954  ///The unary \c - operator must be defined for \c Value, of course.
955  ///
956  /// \sa NegMap
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
982  ///Returns a \c NegWriteMap class
983
984  ///This function just returns a \c NegWriteMap class.
985  ///\relates NegWriteMap
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
993  ///This \ref concepts::ReadMap "read only map" returns the absolute value
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 -
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 
1016  ///Returns an \c AbsMap class
1017
1018  ///This function just returns an \c AbsMap class.
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
1027  ///This \ref concepts::ReadMap "read only map" returns the value
1028  ///of a given functor.
1029  ///
1030  ///Template parameters \c K and \c V will become its
1031  ///\c Key and \c Value.
1032  ///In most cases they have to be given explicitly because a
1033  ///functor typically does not provide \c argument_type and
1034  ///\c result_type typedefs.
1035  ///
1036  ///Parameter \c F is the type of the used functor.
1037  ///
1038  ///\sa MapFunctor
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  ///
1059  ///This function is specialized for adaptable binary function
1060  ///classes and C++ functions.
1061  ///
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.
1084  ///That is it provides an <tt>operator()</tt> to read its values.
1085  ///
1086  ///For the sake of convenience it also works as
1087  ///a ususal \ref concepts::ReadMap "readable map",
1088  ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
1089  ///
1090  ///\sa FunctorMap
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
1119  ///Just readable version of \ref ForkWriteMap
1120
1121  ///This map has two \ref concepts::ReadMap "readable map"
1122  ///parameters and each read request will be passed just to the
1123  ///first map. This class is the just readable map type of \c ForkWriteMap.
1124  ///
1125  ///The \c Key and \c Value are inherited from \c M1.
1126  ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
1127  ///
1128  ///\sa ForkWriteMap
1129  ///
1130  /// \todo Why is it needed?
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
1149  ///This map has two \ref concepts::WriteMap "writable map"
1150  ///parameters and each write request will be passed to both of them.
1151  ///If \c M1 is also \ref concepts::ReadMap "readable",
1152  ///then the read operations will return the
1153  ///corresponding values of \c M1.
1154  ///
1155  ///The \c Key and \c Value are inherited from \c M1.
1156  ///The \c Key and \c Value of \c M2 must be convertible from those of \c M1.
1157  ///
1158  ///\sa ForkMap
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 
1176  ///Returns a \c ForkMap class
1177
1178  ///This function just returns a \c ForkMap class.
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
1185  ///Returns a \c ForkWriteMap class
1186
1187  ///This function just returns a \c ForkWriteMap class.
1188  ///\relates ForkWriteMap
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 
1200  ///This bool \ref concepts::ReadMap "read only map" returns the
1201  ///logical negation of the value returned by the given map.
1202  ///Its \c Key is inherited from \c M, its \c Value is \c bool.
1203  ///
1204  ///\sa NotWriteMap
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
1219  ///Logical 'not' of a map (ReadWrie version)
1220 
1221  ///This bool \ref concepts::ReadWriteMap "read-write map" returns the
1222  ///logical negation of the value returned by the given map. When it is set,
1223  ///the opposite value is set to the original map.
1224  ///Its \c Key is inherited from \c M, its \c Value is \c bool.
1225  ///
1226  ///\sa NotMap
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 
1252  ///Returns a \c NotWriteMap class
1253 
1254  ///This function just returns a \c NotWriteMap class.
1255  ///\relates NotWriteMap
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
1287  /// \brief Writable bool map for logging each \c true assigned element
1288  ///
1289  /// A \ref concepts::ReadWriteMap "read-write" bool map for logging
1290  /// each \c true assigned element, i.e it copies all the keys set
1291  /// to \c true to the given iterator.
1292  ///
1293  /// \note The container of the iterator should contain space
1294  /// for each element.
1295  ///
1296  /// The following example shows how you can write the edges found by
1297  /// the \ref Prim algorithm directly to the standard output.
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
1310  ///
1311  ///\sa BackInserterBoolMap
1312  ///\sa FrontInserterBoolMap
1313  ///\sa InserterBoolMap
1314  ///
1315  ///\todo Revise the name of this class and the related ones.
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
1333    /// Gives back the given iterator set for the first key
1334    Iterator begin() const {
1335      return _begin;
1336    }
1337 
1338    /// Gives back the the 'after the last' iterator
1339    Iterator end() const {
1340      return _end;
1341    }
1342
1343    /// The \c set function of the map
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
1356  /// \brief Writable bool map for logging each \c true assigned element in
1357  /// a back insertable container.
1358  ///
1359  /// Writable bool map for logging each \c true assigned element by pushing
1360  /// them into a back insertable container.
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.
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
1370  ///
1371  ///\sa StoreBoolMap
1372  ///\sa FrontInserterBoolMap
1373  ///\sa InserterBoolMap
1374  template <typename Container,
1375            typename Functor =
1376            _maps_bits::Identity<typename Container::value_type> >
1377  class BackInserterBoolMap {
1378  public:
1379    typedef typename Functor::argument_type Key;
1380    typedef bool Value;
1381
1382    /// Constructor
1383    BackInserterBoolMap(Container& _container,
1384                        const Functor& _functor = Functor())
1385      : container(_container), functor(_functor) {}
1386
1387    /// The \c set function of the map
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
1399  /// \brief Writable bool map for logging each \c true assigned element in
1400  /// a front insertable container.
1401  ///
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
1409  template <typename Container,
1410            typename Functor =
1411            _maps_bits::Identity<typename Container::value_type> >
1412  class FrontInserterBoolMap {
1413  public:
1414    typedef typename Functor::argument_type Key;
1415    typedef bool Value;
1416
1417    /// Constructor
1418    FrontInserterBoolMap(Container& _container,
1419                         const Functor& _functor = Functor())
1420      : container(_container), functor(_functor) {}
1421
1422    /// The \c set function of the map
1423    void set(const Key& key, Value value) {
1424      if (value) {
1425        container.push_front(functor(key));
1426      }
1427    }
1428   
1429  private:
1430    Container& container;   
1431    Functor functor;
1432  };
1433
1434  /// \brief Writable bool map for storing each \c true assigned element in
1435  /// an insertable container.
1436  ///
1437  /// Writable bool map for storing each \c true assigned element in an
1438  /// insertable container. It will insert all the keys set to \c true into
1439  /// the container.
1440  ///
1441  /// For example, if you want to store the cut arcs of the strongly
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
1449  ///
1450  ///\sa BackInserterBoolMap
1451  ///\sa FrontInserterBoolMap
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
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.
1466    InserterBoolMap(Container& _container, typename Container::iterator _it,
1467                    const Functor& _functor = Functor())
1468      : container(_container), it(_it), functor(_functor) {}
1469
1470    /// Constructor
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.
1476    InserterBoolMap(Container& _container, const Functor& _functor = Functor())
1477      : container(_container), it(_container.end()), functor(_functor) {}
1478
1479    /// The \c set function of the map
1480    void set(const Key& key, Value value) {
1481      if (value) {
1482        it = container.insert(it, functor(key));
1483        ++it;
1484      }
1485    }
1486   
1487  private:
1488    Container& container;
1489    typename Container::iterator it;
1490    Functor functor;
1491  };
1492
1493  /// \brief Writable bool map for filling each \c true assigned element with a
1494  /// given value.
1495  ///
1496  /// Writable bool map for filling each \c true assigned element with a
1497  /// given value. The value can set the container.
1498  ///
1499  /// The following code finds the connected components of a graph
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
1547    /// The \c set function of the map
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
1560  /// \brief Writable bool map for storing the sequence number of
1561  /// \c true assignments. 
1562  ///
1563  /// Writable bool map that stores for each \c true assigned elements 
1564  /// the sequence number of this setting.
1565  /// It makes it easy to calculate the leaving
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  ///
1584  /// The storing of the discovering order is more difficult because the
1585  /// ReachedMap should be readable in the dfs algorithm but the setting
1586  /// order map is not readable. Thus we must use the fork map:
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
1624    /// The \c set function of the map
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.