COIN-OR::LEMON - Graph Library

source: lemon/lemon/maps.h @ 26:61bf7f22a6d6

Last change on this file since 26:61bf7f22a6d6 was 26:61bf7f22a6d6, checked in by Alpar Juttner <alpar@…>, 12 years ago

Several doc improvements in maps.h

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