COIN-OR::LEMON - Graph Library

source: lemon/lemon/maps.h @ 30:72364ba3466d

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

Bug fix in maps.h.

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