COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/maps.h @ 2569:12c2c5c4330b

Last change on this file since 2569:12c2c5c4330b was 2564:3250756f5add, checked in by Peter Kovacs, 16 years ago

Several doc improvements and fixes in maps.h and concepts/maps.h.

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