COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/maps.h @ 33:d794ec195ec0

Last change on this file since 33:d794ec195ec0 was 33:d794ec195ec0, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Doc improvements in maps.h.

File size: 44.0 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_MAPS_H
20#define LEMON_MAPS_H
21
22#include <iterator>
23#include <functional>
24#include <vector>
25
26#include <lemon/bits/utility.h>
27// #include <lemon/bits/traits.h>
28
29///\file
30///\ingroup maps
31///\brief Miscellaneous property maps
32///
33#include <map>
34
35namespace lemon {
36
37  /// \addtogroup maps
38  /// @{
39
40  /// Base class of maps.
41
42  /// Base class of maps.
43  /// It provides the necessary <tt>typedef</tt>s required by the map concept.
44  template<typename K, typename T>
45  class MapBase {
46  public:
47    /// The key type of the map.
48    typedef K Key;
49    /// The value type of the map. (The type of objects associated with the keys).
50    typedef T Value;
51  };
52
53  /// Null map. (a.k.a. DoNothingMap)
54
55  /// This map can be used if you have to provide a map only for
56  /// its type definitions, or if you have to provide a writable map,
57  /// but data written to it is not required (i.e. it will be sent to
58  /// <tt>/dev/null</tt>).
59  template<typename K, typename T>
60  class NullMap : public MapBase<K, T> {
61  public:
62    typedef MapBase<K, T> Parent;
63    typedef typename Parent::Key Key;
64    typedef typename Parent::Value Value;
65   
66    /// Gives back a default constructed element.
67    T operator[](const K&) const { return T(); }
68    /// Absorbs the value.
69    void set(const K&, const T&) {}
70  };
71
72  ///Returns a \c NullMap class
73
74  ///This function just returns a \c NullMap class.
75  ///\relates NullMap
76  template <typename K, typename V>
77  NullMap<K, V> nullMap() {
78    return NullMap<K, V>();
79  }
80
81
82  /// Constant map.
83
84  /// This is a readable map which assigns a specified value to each key.
85  /// In other aspects it is equivalent to the \c NullMap.
86  template<typename K, typename T>
87  class ConstMap : public MapBase<K, T> {
88  private:
89    T v;
90  public:
91
92    typedef MapBase<K, T> Parent;
93    typedef typename Parent::Key Key;
94    typedef typename Parent::Value Value;
95
96    /// Default constructor
97
98    /// Default constructor.
99    /// The value of the map will be uninitialized.
100    /// (More exactly it will be default constructed.)
101    ConstMap() {}
102   
103    /// Constructor with specified initial value
104
105    /// Constructor with specified initial value.
106    /// \param _v is the initial value of the map.
107    ConstMap(const T &_v) : v(_v) {}
108   
109    ///\e
110    T operator[](const K&) const { return v; }
111
112    ///\e
113    void setAll(const T &t) {
114      v = t;
115    }   
116
117    template<typename T1>
118    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 keys from the range <tt>[0..size-1]</tt>
253  ///
254  /// The current map has the <tt>[0..size-1]</tt> 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(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.
966  ///In most cases they have to be given explicitly because a
967  ///functor typically does not provide such typedefs.
968  ///
969  ///Parameter \c F is the type of the used functor.
970  ///
971  ///\sa MapFunctor
972  template<typename F,
973           typename K = typename F::argument_type,
974           typename V = typename F::result_type>
975  class FunctorMap : public MapBase<K, V> {
976    F f;
977  public:
978    typedef MapBase<K, V> Parent;
979    typedef typename Parent::Key Key;
980    typedef typename Parent::Value Value;
981
982    ///Constructor
983    FunctorMap(const F &_f = F()) : f(_f) {}
984    /// \e
985    Value operator[](Key k) const { return f(k);}
986  };
987 
988  ///Returns a \c FunctorMap class
989
990  ///This function just returns a \c FunctorMap class.
991  ///
992  ///It is specialized for adaptable function classes and
993  ///C++ functions.
994  ///\relates FunctorMap
995  template<typename K, typename V, typename F> inline
996  FunctorMap<F, K, V> functorMap(const F &f) {
997    return FunctorMap<F, K, V>(f);
998  }
999
1000  template <typename F> inline
1001  FunctorMap<F, typename F::argument_type, typename F::result_type>
1002  functorMap(const F &f) {
1003    return FunctorMap<F, typename F::argument_type,
1004      typename F::result_type>(f);
1005  }
1006
1007  template <typename K, typename V> inline
1008  FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
1009    return FunctorMap<V (*)(K), K, V>(f);
1010  }
1011
1012
1013  ///Converts a map to an STL style (unary) functor
1014
1015  ///This class Converts a map to an STL style (unary) functor.
1016  ///that is it provides an <tt>operator()</tt> to read its values.
1017  ///
1018  ///For the sake of convenience it also works as
1019  ///a ususal \c concepts::ReadMap "readable map",
1020  ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
1021  ///
1022  ///\sa FunctorMap
1023  template <typename M>
1024  class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
1025    const M& m;
1026  public:
1027    typedef MapBase<typename M::Key, typename M::Value> Parent;
1028    typedef typename Parent::Key Key;
1029    typedef typename Parent::Value Value;
1030
1031    typedef typename M::Key argument_type;
1032    typedef typename M::Value result_type;
1033
1034    ///Constructor
1035    MapFunctor(const M &_m) : m(_m) {};
1036    ///\e
1037    Value operator()(Key k) const {return m[k];}
1038    ///\e
1039    Value operator[](Key k) const {return m[k];}
1040  };
1041 
1042  ///Returns a \c MapFunctor class
1043
1044  ///This function just returns a \c MapFunctor class.
1045  ///\relates MapFunctor
1046  template<typename M>
1047  inline MapFunctor<M> mapFunctor(const M &m) {
1048    return MapFunctor<M>(m);
1049  }
1050
1051  ///Applies all map setting operations to two maps
1052
1053  ///This map has two \c concepts::ReadMap "readable map"
1054  ///parameters and each read request will be passed just to the
1055  ///first map. This class is the just readable map type of the ForkWriteMap.
1056  ///
1057  ///The \c Key and \c Value are inherited from \c M1.
1058  ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
1059  ///
1060  ///\sa ForkWriteMap
1061  ///
1062  /// \todo Why is it needed?
1063  template<typename  M1, typename M2>
1064  class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
1065    const M1& m1;
1066    const M2& m2;
1067  public:
1068    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1069    typedef typename Parent::Key Key;
1070    typedef typename Parent::Value Value;
1071
1072    ///Constructor
1073    ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {};
1074    /// \e
1075    Value operator[](Key k) const {return m1[k];}
1076  };
1077
1078
1079  ///Applies all map setting operations to two maps
1080
1081  ///This map has two \c concepts::WriteMap "writable map"
1082  ///parameters and each write request will be passed to both of them.
1083  ///If \c M1 is also \c concepts::ReadMap "readable",
1084  ///then the read operations will return the
1085  ///corresponding values of \c M1.
1086  ///
1087  ///The \c Key and \c Value are inherited from \c M1.
1088  ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
1089  ///
1090  ///\sa ForkMap
1091  template<typename  M1, typename M2>
1092  class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
1093    M1& m1;
1094    M2& m2;
1095  public:
1096    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
1097    typedef typename Parent::Key Key;
1098    typedef typename Parent::Value Value;
1099
1100    ///Constructor
1101    ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {};
1102    ///\e
1103    Value operator[](Key k) const {return m1[k];}
1104    ///\e
1105    void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
1106  };
1107 
1108  ///Returns a \c ForkMap class
1109
1110  ///This function just returns a \c ForkMap class.
1111  ///\relates ForkMap
1112  template <typename M1, typename M2>
1113  inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) {
1114    return ForkMap<M1, M2>(m1,m2);
1115  }
1116
1117  ///Returns a \c ForkWriteMap class
1118
1119  ///This function just returns a \c ForkWriteMap class.
1120  ///\relates ForkWriteMap
1121  template <typename M1, typename M2>
1122  inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) {
1123    return ForkWriteMap<M1, M2>(m1,m2);
1124  }
1125
1126
1127 
1128  /* ************* BOOL MAPS ******************* */
1129 
1130  ///Logical 'not' of a map
1131 
1132  ///This bool \c concepts::ReadMap "read only map" returns the
1133  ///logical negation of the value returned by the given map.
1134  ///Its \c Key is inherited from \c M, its Value is \c bool.
1135  ///
1136  ///\sa NotWriteMap
1137  template <typename M>
1138  class NotMap : public MapBase<typename M::Key, bool> {
1139    const M& m;
1140  public:
1141    typedef MapBase<typename M::Key, bool> Parent;
1142    typedef typename Parent::Key Key;
1143    typedef typename Parent::Value Value;
1144
1145    /// Constructor
1146    NotMap(const M &_m) : m(_m) {};
1147    ///\e
1148    Value operator[](Key k) const {return !m[k];}
1149  };
1150
1151  ///Logical 'not' of a map (ReadWrie version)
1152 
1153  ///This bool \c concepts::ReadWriteMap "read-write map" returns the
1154  ///logical negation of the value returned by the given map. When it is set,
1155  ///the opposite value is set to the original map.
1156  ///Its \c Key is inherited from \c M, its Value is \c bool.
1157  ///
1158  ///\sa NotMap
1159  template <typename M>
1160  class NotWriteMap : public MapBase<typename M::Key, bool> {
1161    M& m;
1162  public:
1163    typedef MapBase<typename M::Key, bool> Parent;
1164    typedef typename Parent::Key Key;
1165    typedef typename Parent::Value Value;
1166
1167    /// Constructor
1168    NotWriteMap(M &_m) : m(_m) {};
1169    ///\e
1170    Value operator[](Key k) const {return !m[k];}
1171    ///\e
1172    void set(Key k, bool v) { m.set(k, !v); }
1173  };
1174 
1175  ///Returns a \c NotMap class
1176 
1177  ///This function just returns a \c NotMap class.
1178  ///\relates NotMap
1179  template <typename M>
1180  inline NotMap<M> notMap(const M &m) {
1181    return NotMap<M>(m);
1182  }
1183 
1184  ///Returns a \c NotWriteMap class
1185 
1186  ///This function just returns a \c NotWriteMap class.
1187  ///\relates NotWriteMap
1188  template <typename M>
1189  inline NotWriteMap<M> notMap(M &m) {
1190    return NotWriteMap<M>(m);
1191  }
1192
1193  namespace _maps_bits {
1194
1195    template <typename Value>
1196    struct Identity {
1197      typedef Value argument_type;
1198      typedef Value result_type;
1199      Value operator()(const Value& val) const {
1200        return val;
1201      }
1202    };
1203
1204    template <typename _Iterator, typename Enable = void>
1205    struct IteratorTraits {
1206      typedef typename std::iterator_traits<_Iterator>::value_type Value;
1207    };
1208
1209    template <typename _Iterator>
1210    struct IteratorTraits<_Iterator,
1211      typename exists<typename _Iterator::container_type>::type>
1212    {
1213      typedef typename _Iterator::container_type::value_type Value;
1214    };
1215
1216  }
1217 
1218
1219  /// \brief Writable bool map for logging each \c true assigned element
1220  ///
1221  /// Writable bool map for logging each \c true assigned element, i.e it
1222  /// copies all the keys set to \c true to the given iterator.
1223  ///
1224  /// \note The container of the iterator should contain space
1225  /// for each element.
1226  ///
1227  /// The following example shows how you can write the edges found by the Prim
1228  /// algorithm directly
1229  /// to the standard output.
1230  ///\code
1231  /// typedef IdMap<Graph, Edge> EdgeIdMap;
1232  /// EdgeIdMap edgeId(graph);
1233  ///
1234  /// typedef MapFunctor<EdgeIdMap> EdgeIdFunctor;
1235  /// EdgeIdFunctor edgeIdFunctor(edgeId);
1236  ///
1237  /// StoreBoolMap<ostream_iterator<int>, EdgeIdFunctor>
1238  ///   writerMap(ostream_iterator<int>(cout, " "), edgeIdFunctor);
1239  ///
1240  /// prim(graph, cost, writerMap);
1241  ///\endcode
1242  ///
1243  ///\sa BackInserterBoolMap
1244  ///\sa FrontInserterBoolMap
1245  ///\sa InserterBoolMap
1246  ///
1247  ///\todo Revise the name of this class and the related ones.
1248  template <typename _Iterator,
1249            typename _Functor =
1250            _maps_bits::Identity<typename _maps_bits::
1251                                 IteratorTraits<_Iterator>::Value> >
1252  class StoreBoolMap {
1253  public:
1254    typedef _Iterator Iterator;
1255
1256    typedef typename _Functor::argument_type Key;
1257    typedef bool Value;
1258
1259    typedef _Functor Functor;
1260
1261    /// Constructor
1262    StoreBoolMap(Iterator it, const Functor& functor = Functor())
1263      : _begin(it), _end(it), _functor(functor) {}
1264
1265    /// Gives back the given iterator set for the first key
1266    Iterator begin() const {
1267      return _begin;
1268    }
1269 
1270    /// Gives back the the 'after the last' iterator
1271    Iterator end() const {
1272      return _end;
1273    }
1274
1275    /// The \c set function of the map
1276    void set(const Key& key, Value value) const {
1277      if (value) {
1278        *_end++ = _functor(key);
1279      }
1280    }
1281   
1282  private:
1283    Iterator _begin;
1284    mutable Iterator _end;
1285    Functor _functor;
1286  };
1287
1288  /// \brief Writable bool map for logging each \c true assigned element in
1289  /// a back insertable container.
1290  ///
1291  /// Writable bool map for logging each \c true assigned element by pushing
1292  /// them into a back insertable container.
1293  /// It can be used to retrieve the items into a standard
1294  /// container. The next example shows how you can store the
1295  /// edges found by the Prim algorithm in a vector.
1296  ///
1297  ///\code
1298  /// vector<Edge> span_tree_edges;
1299  /// BackInserterBoolMap<vector<Edge> > inserter_map(span_tree_edges);
1300  /// prim(graph, cost, inserter_map);
1301  ///\endcode
1302  ///
1303  ///\sa StoreBoolMap
1304  ///\sa FrontInserterBoolMap
1305  ///\sa InserterBoolMap
1306  template <typename Container,
1307            typename Functor =
1308            _maps_bits::Identity<typename Container::value_type> >
1309  class BackInserterBoolMap {
1310  public:
1311    typedef typename Container::value_type Key;
1312    typedef bool Value;
1313
1314    /// Constructor
1315    BackInserterBoolMap(Container& _container,
1316                        const Functor& _functor = Functor())
1317      : container(_container), functor(_functor) {}
1318
1319    /// The \c set function of the map
1320    void set(const Key& key, Value value) {
1321      if (value) {
1322        container.push_back(functor(key));
1323      }
1324    }
1325   
1326  private:
1327    Container& container;
1328    Functor functor;
1329  };
1330
1331  /// \brief Writable bool map for logging each \c true assigned element in
1332  /// a front insertable container.
1333  ///
1334  /// Writable bool map for logging each \c true assigned element by pushing
1335  /// them into a front insertable container.
1336  /// It can be used to retrieve the items into a standard
1337  /// container. For example see \ref BackInserterBoolMap.
1338  ///
1339  ///\sa BackInserterBoolMap
1340  ///\sa InserterBoolMap
1341  template <typename Container,
1342            typename Functor =
1343            _maps_bits::Identity<typename Container::value_type> >
1344  class FrontInserterBoolMap {
1345  public:
1346    typedef typename Container::value_type Key;
1347    typedef bool Value;
1348
1349    /// Constructor
1350    FrontInserterBoolMap(Container& _container,
1351                         const Functor& _functor = Functor())
1352      : container(_container), functor(_functor) {}
1353
1354    /// The \c set function of the map
1355    void set(const Key& key, Value value) {
1356      if (value) {
1357        container.push_front(functor(key));
1358      }
1359    }
1360   
1361  private:
1362    Container& container;   
1363    Functor functor;
1364  };
1365
1366  /// \brief Writable bool map for storing each \c true assigned element in
1367  /// an insertable container.
1368  ///
1369  /// Writable bool map for storing each \c true assigned element in an
1370  /// insertable container. It will insert all the keys set to \c true into
1371  /// the container.
1372  ///
1373  /// For example, if you want to store the cut arcs of the strongly
1374  /// connected components in a set you can use the next code:
1375  ///
1376  ///\code
1377  /// set<Arc> cut_arcs;
1378  /// InserterBoolMap<set<Arc> > inserter_map(cut_arcs);
1379  /// stronglyConnectedCutArcs(digraph, cost, inserter_map);
1380  ///\endcode
1381  ///
1382  ///\sa BackInserterBoolMap
1383  ///\sa FrontInserterBoolMap
1384  template <typename Container,
1385            typename Functor =
1386            _maps_bits::Identity<typename Container::value_type> >
1387  class InserterBoolMap {
1388  public:
1389    typedef typename Container::value_type Key;
1390    typedef bool Value;
1391
1392    /// Constructor with specified iterator
1393   
1394    /// Constructor with specified iterator.
1395    /// \param _container The container for storing the elements.
1396    /// \param _it The elements will be inserted before this iterator.
1397    /// \param _functor The functor that is used when an element is stored.
1398    InserterBoolMap(Container& _container, typename Container::iterator _it,
1399                    const Functor& _functor = Functor())
1400      : container(_container), it(_it), functor(_functor) {}
1401
1402    /// Constructor
1403
1404    /// Constructor without specified iterator.
1405    /// The elements will be inserted before <tt>_container.end()</tt>.
1406    /// \param _container The container for storing the elements.
1407    /// \param _functor The functor that is used when an element is stored.
1408    InserterBoolMap(Container& _container, const Functor& _functor = Functor())
1409      : container(_container), it(_container.end()), functor(_functor) {}
1410
1411    /// The \c set function of the map
1412    void set(const Key& key, Value value) {
1413      if (value) {
1414        it = container.insert(it, functor(key));
1415        ++it;
1416      }
1417    }
1418   
1419  private:
1420    Container& container;
1421    typename Container::iterator it;
1422    Functor functor;
1423  };
1424
1425  /// \brief Writable bool map for filling each \c true assigned element with a
1426  /// given value.
1427  ///
1428  /// Writable bool map for filling each \c true assigned element with a
1429  /// given value. The value can set the container.
1430  ///
1431  /// The following code finds the connected components of a graph
1432  /// and stores it in the \c comp map:
1433  ///\code
1434  /// typedef Graph::NodeMap<int> ComponentMap;
1435  /// ComponentMap comp(graph);
1436  /// typedef FillBoolMap<Graph::NodeMap<int> > ComponentFillerMap;
1437  /// ComponentFillerMap filler(comp, 0);
1438  ///
1439  /// Dfs<Graph>::DefProcessedMap<ComponentFillerMap>::Create dfs(graph);
1440  /// dfs.processedMap(filler);
1441  /// dfs.init();
1442  /// for (NodeIt it(graph); it != INVALID; ++it) {
1443  ///   if (!dfs.reached(it)) {
1444  ///     dfs.addSource(it);
1445  ///     dfs.start();
1446  ///     ++filler.fillValue();
1447  ///   }
1448  /// }
1449  ///\endcode
1450  template <typename Map>
1451  class FillBoolMap {
1452  public:
1453    typedef typename Map::Key Key;
1454    typedef bool Value;
1455
1456    /// Constructor
1457    FillBoolMap(Map& _map, const typename Map::Value& _fill)
1458      : map(_map), fill(_fill) {}
1459
1460    /// Constructor
1461    FillBoolMap(Map& _map)
1462      : map(_map), fill() {}
1463
1464    /// Gives back the current fill value
1465    const typename Map::Value& fillValue() const {
1466      return fill;
1467    }
1468
1469    /// Gives back the current fill value
1470    typename Map::Value& fillValue() {
1471      return fill;
1472    }
1473
1474    /// Sets the current fill value
1475    void fillValue(const typename Map::Value& _fill) {
1476      fill = _fill;
1477    }
1478
1479    /// The \c set function of the map
1480    void set(const Key& key, Value value) {
1481      if (value) {
1482        map.set(key, fill);
1483      }
1484    }
1485   
1486  private:
1487    Map& map;
1488    typename Map::Value fill;
1489  };
1490
1491
1492  /// \brief Writable bool map for storing the sequence number of
1493  /// \c true assignments. 
1494  ///
1495  /// Writable bool map that stores for each \c true assigned elements 
1496  /// the sequence number of this setting.
1497  /// It makes it easy to calculate the leaving
1498  /// order of the nodes in the \c Dfs algorithm.
1499  ///
1500  ///\code
1501  /// typedef Digraph::NodeMap<int> OrderMap;
1502  /// OrderMap order(digraph);
1503  /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1504  /// OrderSetterMap setter(order);
1505  /// Dfs<Digraph>::DefProcessedMap<OrderSetterMap>::Create dfs(digraph);
1506  /// dfs.processedMap(setter);
1507  /// dfs.init();
1508  /// for (NodeIt it(digraph); it != INVALID; ++it) {
1509  ///   if (!dfs.reached(it)) {
1510  ///     dfs.addSource(it);
1511  ///     dfs.start();
1512  ///   }
1513  /// }
1514  ///\endcode
1515  ///
1516  /// The storing of the discovering order is more difficult because the
1517  /// ReachedMap should be readable in the dfs algorithm but the setting
1518  /// order map is not readable. Thus we must use the fork map:
1519  ///
1520  ///\code
1521  /// typedef Digraph::NodeMap<int> OrderMap;
1522  /// OrderMap order(digraph);
1523  /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1524  /// OrderSetterMap setter(order);
1525  /// typedef Digraph::NodeMap<bool> StoreMap;
1526  /// StoreMap store(digraph);
1527  ///
1528  /// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap;
1529  /// ReachedMap reached(store, setter);
1530  ///
1531  /// Dfs<Digraph>::DefReachedMap<ReachedMap>::Create dfs(digraph);
1532  /// dfs.reachedMap(reached);
1533  /// dfs.init();
1534  /// for (NodeIt it(digraph); it != INVALID; ++it) {
1535  ///   if (!dfs.reached(it)) {
1536  ///     dfs.addSource(it);
1537  ///     dfs.start();
1538  ///   }
1539  /// }
1540  ///\endcode
1541  template <typename Map>
1542  class SettingOrderBoolMap {
1543  public:
1544    typedef typename Map::Key Key;
1545    typedef bool Value;
1546
1547    /// Constructor
1548    SettingOrderBoolMap(Map& _map)
1549      : map(_map), counter(0) {}
1550
1551    /// Number of set operations.
1552    int num() const {
1553      return counter;
1554    }
1555
1556    /// Setter function of the map
1557    void set(const Key& key, Value value) {
1558      if (value) {
1559        map.set(key, counter++);
1560      }
1561    }
1562   
1563  private:
1564    Map& map;
1565    int counter;
1566  };
1567
1568  /// @}
1569}
1570
1571#endif // LEMON_MAPS_H
Note: See TracBrowser for help on using the repository browser.