COIN-OR::LEMON - Graph Library

source: lemon-1.0/lemon/maps.h @ 51:90201bb15a8d

Last change on this file since 51:90201bb15a8d was 51:90201bb15a8d, checked in by Alpar Juttner <alpar@…>, 17 years ago

Merge

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