COIN-OR::LEMON - Graph Library

source: lemon/lemon/maps.h @ 324:fafece417795

1.0
Last change on this file since 324:fafece417795 was 324:fafece417795, checked in by Alpar Juttner <alpar@…>, 11 years ago

Remove InverseMap? and DescriptorMap?

File size: 66.1 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
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/core.h>
27
28///\file
29///\ingroup maps
30///\brief Miscellaneous property maps
31
32#include <map>
33
34namespace lemon {
35
36  /// \addtogroup maps
37  /// @{
38
39  /// Base class of maps.
40
41  /// Base class of maps. It provides the necessary type definitions
42  /// required by the map %concepts.
43  template<typename K, typename V>
44  class MapBase {
45  public:
46    /// \biref The key type of the map.
47    typedef K Key;
48    /// \brief The value type of the map.
49    /// (The type of objects associated with the keys).
50    typedef V Value;
51  };
52
53
54  /// Null map. (a.k.a. DoNothingMap)
55
56  /// This map can be used if you have to provide a map only for
57  /// its type definitions, or if you have to provide a writable map,
58  /// but data written to it is not required (i.e. it will be sent to
59  /// <tt>/dev/null</tt>).
60  /// It conforms the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
61  ///
62  /// \sa ConstMap
63  template<typename K, typename V>
64  class NullMap : public MapBase<K, V> {
65  public:
66    typedef MapBase<K, V> Parent;
67    typedef typename Parent::Key Key;
68    typedef typename Parent::Value Value;
69
70    /// Gives back a default constructed element.
71    Value operator[](const Key&) const { return Value(); }
72    /// Absorbs the value.
73    void set(const Key&, const Value&) {}
74  };
75
76  /// Returns a \ref NullMap class
77
78  /// This function just returns a \ref NullMap class.
79  /// \relates NullMap
80  template <typename K, typename V>
81  NullMap<K, V> nullMap() {
82    return NullMap<K, V>();
83  }
84
85
86  /// Constant map.
87
88  /// This \ref concepts::ReadMap "readable map" assigns a specified
89  /// value to each key.
90  ///
91  /// In other aspects it is equivalent to \ref NullMap.
92  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
93  /// concept, but it absorbs the data written to it.
94  ///
95  /// The simplest way of using this map is through the constMap()
96  /// function.
97  ///
98  /// \sa NullMap
99  /// \sa IdentityMap
100  template<typename K, typename V>
101  class ConstMap : public MapBase<K, V> {
102  private:
103    V _value;
104  public:
105    typedef MapBase<K, V> Parent;
106    typedef typename Parent::Key Key;
107    typedef typename Parent::Value Value;
108
109    /// Default constructor
110
111    /// Default constructor.
112    /// The value of the map will be default constructed.
113    ConstMap() {}
114
115    /// Constructor with specified initial value
116
117    /// Constructor with specified initial value.
118    /// \param v The initial value of the map.
119    ConstMap(const Value &v) : _value(v) {}
120
121    /// Gives back the specified value.
122    Value operator[](const Key&) const { return _value; }
123
124    /// Absorbs the value.
125    void set(const Key&, const Value&) {}
126
127    /// Sets the value that is assigned to each key.
128    void setAll(const Value &v) {
129      _value = v;
130    }
131
132    template<typename V1>
133    ConstMap(const ConstMap<K, V1> &, const Value &v) : _value(v) {}
134  };
135
136  /// Returns a \ref ConstMap class
137
138  /// This function just returns a \ref ConstMap class.
139  /// \relates ConstMap
140  template<typename K, typename V>
141  inline ConstMap<K, V> constMap(const V &v) {
142    return ConstMap<K, V>(v);
143  }
144
145  template<typename K, typename V>
146  inline ConstMap<K, V> constMap() {
147    return ConstMap<K, V>();
148  }
149
150
151  template<typename T, T v>
152  struct Const {};
153
154  /// Constant map with inlined constant value.
155
156  /// This \ref concepts::ReadMap "readable map" assigns a specified
157  /// value to each key.
158  ///
159  /// In other aspects it is equivalent to \ref NullMap.
160  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
161  /// concept, but it absorbs the data written to it.
162  ///
163  /// The simplest way of using this map is through the constMap()
164  /// function.
165  ///
166  /// \sa NullMap
167  /// \sa IdentityMap
168  template<typename K, typename V, V v>
169  class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
170  public:
171    typedef MapBase<K, V> Parent;
172    typedef typename Parent::Key Key;
173    typedef typename Parent::Value Value;
174
175    /// Constructor.
176    ConstMap() {}
177
178    /// Gives back the specified value.
179    Value operator[](const Key&) const { return v; }
180
181    /// Absorbs the value.
182    void set(const Key&, const Value&) {}
183  };
184
185  /// Returns a \ref ConstMap class with inlined constant value
186
187  /// This function just returns a \ref ConstMap class with inlined
188  /// constant value.
189  /// \relates ConstMap
190  template<typename K, typename V, V v>
191  inline ConstMap<K, Const<V, v> > constMap() {
192    return ConstMap<K, Const<V, v> >();
193  }
194
195
196  /// Identity map.
197
198  /// This \ref concepts::ReadMap "read-only map" gives back the given
199  /// key as value without any modification.
200  ///
201  /// \sa ConstMap
202  template <typename T>
203  class IdentityMap : public MapBase<T, T> {
204  public:
205    typedef MapBase<T, T> Parent;
206    typedef typename Parent::Key Key;
207    typedef typename Parent::Value Value;
208
209    /// Gives back the given value without any modification.
210    Value operator[](const Key &k) const {
211      return k;
212    }
213  };
214
215  /// Returns an \ref IdentityMap class
216
217  /// This function just returns an \ref IdentityMap class.
218  /// \relates IdentityMap
219  template<typename T>
220  inline IdentityMap<T> identityMap() {
221    return IdentityMap<T>();
222  }
223
224
225  /// \brief Map for storing values for integer keys from the range
226  /// <tt>[0..size-1]</tt>.
227  ///
228  /// This map is essentially a wrapper for \c std::vector. It assigns
229  /// values to integer keys from the range <tt>[0..size-1]</tt>.
230  /// It can be used with some data structures, for example
231  /// \ref UnionFind, \ref BinHeap, when the used items are small
232  /// integers. This map conforms the \ref concepts::ReferenceMap
233  /// "ReferenceMap" concept.
234  ///
235  /// The simplest way of using this map is through the rangeMap()
236  /// function.
237  template <typename V>
238  class RangeMap : public MapBase<int, V> {
239    template <typename V1>
240    friend class RangeMap;
241  private:
242
243    typedef std::vector<V> Vector;
244    Vector _vector;
245
246  public:
247
248    typedef MapBase<int, V> Parent;
249    /// Key type
250    typedef typename Parent::Key Key;
251    /// Value type
252    typedef typename Parent::Value Value;
253    /// Reference type
254    typedef typename Vector::reference Reference;
255    /// Const reference type
256    typedef typename Vector::const_reference ConstReference;
257
258    typedef True ReferenceMapTag;
259
260  public:
261
262    /// Constructor with specified default value.
263    RangeMap(int size = 0, const Value &value = Value())
264      : _vector(size, value) {}
265
266    /// Constructs the map from an appropriate \c std::vector.
267    template <typename V1>
268    RangeMap(const std::vector<V1>& vector)
269      : _vector(vector.begin(), vector.end()) {}
270
271    /// Constructs the map from another \ref RangeMap.
272    template <typename V1>
273    RangeMap(const RangeMap<V1> &c)
274      : _vector(c._vector.begin(), c._vector.end()) {}
275
276    /// Returns the size of the map.
277    int size() {
278      return _vector.size();
279    }
280
281    /// Resizes the map.
282
283    /// Resizes the underlying \c std::vector container, so changes the
284    /// keyset of the map.
285    /// \param size The new size of the map. The new keyset will be the
286    /// range <tt>[0..size-1]</tt>.
287    /// \param value The default value to assign to the new keys.
288    void resize(int size, const Value &value = Value()) {
289      _vector.resize(size, value);
290    }
291
292  private:
293
294    RangeMap& operator=(const RangeMap&);
295
296  public:
297
298    ///\e
299    Reference operator[](const Key &k) {
300      return _vector[k];
301    }
302
303    ///\e
304    ConstReference operator[](const Key &k) const {
305      return _vector[k];
306    }
307
308    ///\e
309    void set(const Key &k, const Value &v) {
310      _vector[k] = v;
311    }
312  };
313
314  /// Returns a \ref RangeMap class
315
316  /// This function just returns a \ref RangeMap class.
317  /// \relates RangeMap
318  template<typename V>
319  inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
320    return RangeMap<V>(size, value);
321  }
322
323  /// \brief Returns a \ref RangeMap class created from an appropriate
324  /// \c std::vector
325
326  /// This function just returns a \ref RangeMap class created from an
327  /// appropriate \c std::vector.
328  /// \relates RangeMap
329  template<typename V>
330  inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
331    return RangeMap<V>(vector);
332  }
333
334
335  /// Map type based on \c std::map
336
337  /// This map is essentially a wrapper for \c std::map with addition
338  /// that you can specify a default value for the keys that are not
339  /// stored actually. This value can be different from the default
340  /// contructed value (i.e. \c %Value()).
341  /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
342  /// concept.
343  ///
344  /// This map is useful if a default value should be assigned to most of
345  /// the keys and different values should be assigned only to a few
346  /// keys (i.e. the map is "sparse").
347  /// The name of this type also refers to this important usage.
348  ///
349  /// Apart form that this map can be used in many other cases since it
350  /// is based on \c std::map, which is a general associative container.
351  /// However keep in mind that it is usually not as efficient as other
352  /// maps.
353  ///
354  /// The simplest way of using this map is through the sparseMap()
355  /// function.
356  template <typename K, typename V, typename Compare = std::less<K> >
357  class SparseMap : public MapBase<K, V> {
358    template <typename K1, typename V1, typename C1>
359    friend class SparseMap;
360  public:
361
362    typedef MapBase<K, V> Parent;
363    /// Key type
364    typedef typename Parent::Key Key;
365    /// Value type
366    typedef typename Parent::Value Value;
367    /// Reference type
368    typedef Value& Reference;
369    /// Const reference type
370    typedef const Value& ConstReference;
371
372    typedef True ReferenceMapTag;
373
374  private:
375
376    typedef std::map<K, V, Compare> Map;
377    Map _map;
378    Value _value;
379
380  public:
381
382    /// \brief Constructor with specified default value.
383    SparseMap(const Value &value = Value()) : _value(value) {}
384    /// \brief Constructs the map from an appropriate \c std::map, and
385    /// explicitly specifies a default value.
386    template <typename V1, typename Comp1>
387    SparseMap(const std::map<Key, V1, Comp1> &map,
388              const Value &value = Value())
389      : _map(map.begin(), map.end()), _value(value) {}
390
391    /// \brief Constructs the map from another \ref SparseMap.
392    template<typename V1, typename Comp1>
393    SparseMap(const SparseMap<Key, V1, Comp1> &c)
394      : _map(c._map.begin(), c._map.end()), _value(c._value) {}
395
396  private:
397
398    SparseMap& operator=(const SparseMap&);
399
400  public:
401
402    ///\e
403    Reference operator[](const Key &k) {
404      typename Map::iterator it = _map.lower_bound(k);
405      if (it != _map.end() && !_map.key_comp()(k, it->first))
406        return it->second;
407      else
408        return _map.insert(it, std::make_pair(k, _value))->second;
409    }
410
411    ///\e
412    ConstReference operator[](const Key &k) const {
413      typename Map::const_iterator it = _map.find(k);
414      if (it != _map.end())
415        return it->second;
416      else
417        return _value;
418    }
419
420    ///\e
421    void set(const Key &k, const Value &v) {
422      typename Map::iterator it = _map.lower_bound(k);
423      if (it != _map.end() && !_map.key_comp()(k, it->first))
424        it->second = v;
425      else
426        _map.insert(it, std::make_pair(k, v));
427    }
428
429    ///\e
430    void setAll(const Value &v) {
431      _value = v;
432      _map.clear();
433    }
434  };
435
436  /// Returns a \ref SparseMap class
437
438  /// This function just returns a \ref SparseMap class with specified
439  /// default value.
440  /// \relates SparseMap
441  template<typename K, typename V, typename Compare>
442  inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
443    return SparseMap<K, V, Compare>(value);
444  }
445
446  template<typename K, typename V>
447  inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
448    return SparseMap<K, V, std::less<K> >(value);
449  }
450
451  /// \brief Returns a \ref SparseMap class created from an appropriate
452  /// \c std::map
453
454  /// This function just returns a \ref SparseMap class created from an
455  /// appropriate \c std::map.
456  /// \relates SparseMap
457  template<typename K, typename V, typename Compare>
458  inline SparseMap<K, V, Compare>
459    sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
460  {
461    return SparseMap<K, V, Compare>(map, value);
462  }
463
464  /// @}
465
466  /// \addtogroup map_adaptors
467  /// @{
468
469  /// Composition of two maps
470
471  /// This \ref concepts::ReadMap "read-only map" returns the
472  /// composition of two given maps. That is to say, if \c m1 is of
473  /// type \c M1 and \c m2 is of \c M2, then for
474  /// \code
475  ///   ComposeMap<M1, M2> cm(m1,m2);
476  /// \endcode
477  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
478  ///
479  /// The \c Key type of the map is inherited from \c M2 and the
480  /// \c Value type is from \c M1.
481  /// \c M2::Value must be convertible to \c M1::Key.
482  ///
483  /// The simplest way of using this map is through the composeMap()
484  /// function.
485  ///
486  /// \sa CombineMap
487  template <typename M1, typename M2>
488  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
489    const M1 &_m1;
490    const M2 &_m2;
491  public:
492    typedef MapBase<typename M2::Key, typename M1::Value> Parent;
493    typedef typename Parent::Key Key;
494    typedef typename Parent::Value Value;
495
496    /// Constructor
497    ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
498
499    /// \e
500    typename MapTraits<M1>::ConstReturnValue
501    operator[](const Key &k) const { return _m1[_m2[k]]; }
502  };
503
504  /// Returns a \ref ComposeMap class
505
506  /// This function just returns a \ref ComposeMap class.
507  ///
508  /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
509  /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
510  /// will be equal to <tt>m1[m2[x]]</tt>.
511  ///
512  /// \relates ComposeMap
513  template <typename M1, typename M2>
514  inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) {
515    return ComposeMap<M1, M2>(m1, m2);
516  }
517
518
519  /// Combination of two maps using an STL (binary) functor.
520
521  /// This \ref concepts::ReadMap "read-only map" takes two maps and a
522  /// binary functor and returns the combination of the two given maps
523  /// using the functor.
524  /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2
525  /// and \c f is of \c F, then for
526  /// \code
527  ///   CombineMap<M1,M2,F,V> cm(m1,m2,f);
528  /// \endcode
529  /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>.
530  ///
531  /// The \c Key type of the map is inherited from \c M1 (\c M1::Key
532  /// must be convertible to \c M2::Key) and the \c Value type is \c V.
533  /// \c M2::Value and \c M1::Value must be convertible to the
534  /// corresponding input parameter of \c F and the return type of \c F
535  /// must be convertible to \c V.
536  ///
537  /// The simplest way of using this map is through the combineMap()
538  /// function.
539  ///
540  /// \sa ComposeMap
541  template<typename M1, typename M2, typename F,
542           typename V = typename F::result_type>
543  class CombineMap : public MapBase<typename M1::Key, V> {
544    const M1 &_m1;
545    const M2 &_m2;
546    F _f;
547  public:
548    typedef MapBase<typename M1::Key, V> Parent;
549    typedef typename Parent::Key Key;
550    typedef typename Parent::Value Value;
551
552    /// Constructor
553    CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
554      : _m1(m1), _m2(m2), _f(f) {}
555    /// \e
556    Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
557  };
558
559  /// Returns a \ref CombineMap class
560
561  /// This function just returns a \ref CombineMap class.
562  ///
563  /// For example, if \c m1 and \c m2 are both maps with \c double
564  /// values, then
565  /// \code
566  ///   combineMap(m1,m2,std::plus<double>())
567  /// \endcode
568  /// is equivalent to
569  /// \code
570  ///   addMap(m1,m2)
571  /// \endcode
572  ///
573  /// This function is specialized for adaptable binary function
574  /// classes and C++ functions.
575  ///
576  /// \relates CombineMap
577  template<typename M1, typename M2, typename F, typename V>
578  inline CombineMap<M1, M2, F, V>
579  combineMap(const M1 &m1, const M2 &m2, const F &f) {
580    return CombineMap<M1, M2, F, V>(m1,m2,f);
581  }
582
583  template<typename M1, typename M2, typename F>
584  inline CombineMap<M1, M2, F, typename F::result_type>
585  combineMap(const M1 &m1, const M2 &m2, const F &f) {
586    return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
587  }
588
589  template<typename M1, typename M2, typename K1, typename K2, typename V>
590  inline CombineMap<M1, M2, V (*)(K1, K2), V>
591  combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
592    return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
593  }
594
595
596  /// Converts an STL style (unary) functor to a map
597
598  /// This \ref concepts::ReadMap "read-only map" returns the value
599  /// of a given functor. Actually, it just wraps the functor and
600  /// provides the \c Key and \c Value typedefs.
601  ///
602  /// Template parameters \c K and \c V will become its \c Key and
603  /// \c Value. In most cases they have to be given explicitly because
604  /// a functor typically does not provide \c argument_type and
605  /// \c result_type typedefs.
606  /// Parameter \c F is the type of the used functor.
607  ///
608  /// The simplest way of using this map is through the functorToMap()
609  /// function.
610  ///
611  /// \sa MapToFunctor
612  template<typename F,
613           typename K = typename F::argument_type,
614           typename V = typename F::result_type>
615  class FunctorToMap : public MapBase<K, V> {
616    F _f;
617  public:
618    typedef MapBase<K, V> Parent;
619    typedef typename Parent::Key Key;
620    typedef typename Parent::Value Value;
621
622    /// Constructor
623    FunctorToMap(const F &f = F()) : _f(f) {}
624    /// \e
625    Value operator[](const Key &k) const { return _f(k); }
626  };
627
628  /// Returns a \ref FunctorToMap class
629
630  /// This function just returns a \ref FunctorToMap class.
631  ///
632  /// This function is specialized for adaptable binary function
633  /// classes and C++ functions.
634  ///
635  /// \relates FunctorToMap
636  template<typename K, typename V, typename F>
637  inline FunctorToMap<F, K, V> functorToMap(const F &f) {
638    return FunctorToMap<F, K, V>(f);
639  }
640
641  template <typename F>
642  inline FunctorToMap<F, typename F::argument_type, typename F::result_type>
643    functorToMap(const F &f)
644  {
645    return FunctorToMap<F, typename F::argument_type,
646      typename F::result_type>(f);
647  }
648
649  template <typename K, typename V>
650  inline FunctorToMap<V (*)(K), K, V> functorToMap(V (*f)(K)) {
651    return FunctorToMap<V (*)(K), K, V>(f);
652  }
653
654
655  /// Converts a map to an STL style (unary) functor
656
657  /// This class converts a map to an STL style (unary) functor.
658  /// That is it provides an <tt>operator()</tt> to read its values.
659  ///
660  /// For the sake of convenience it also works as a usual
661  /// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt>
662  /// and the \c Key and \c Value typedefs also exist.
663  ///
664  /// The simplest way of using this map is through the mapToFunctor()
665  /// function.
666  ///
667  ///\sa FunctorToMap
668  template <typename M>
669  class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
670    const M &_m;
671  public:
672    typedef MapBase<typename M::Key, typename M::Value> Parent;
673    typedef typename Parent::Key Key;
674    typedef typename Parent::Value Value;
675
676    typedef typename Parent::Key argument_type;
677    typedef typename Parent::Value result_type;
678
679    /// Constructor
680    MapToFunctor(const M &m) : _m(m) {}
681    /// \e
682    Value operator()(const Key &k) const { return _m[k]; }
683    /// \e
684    Value operator[](const Key &k) const { return _m[k]; }
685  };
686
687  /// Returns a \ref MapToFunctor class
688
689  /// This function just returns a \ref MapToFunctor class.
690  /// \relates MapToFunctor
691  template<typename M>
692  inline MapToFunctor<M> mapToFunctor(const M &m) {
693    return MapToFunctor<M>(m);
694  }
695
696
697  /// \brief Map adaptor to convert the \c Value type of a map to
698  /// another type using the default conversion.
699
700  /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap
701  /// "readable map" to another type using the default conversion.
702  /// The \c Key type of it is inherited from \c M and the \c Value
703  /// type is \c V.
704  /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
705  ///
706  /// The simplest way of using this map is through the convertMap()
707  /// function.
708  template <typename M, typename V>
709  class ConvertMap : public MapBase<typename M::Key, V> {
710    const M &_m;
711  public:
712    typedef MapBase<typename M::Key, V> Parent;
713    typedef typename Parent::Key Key;
714    typedef typename Parent::Value Value;
715
716    /// Constructor
717
718    /// Constructor.
719    /// \param m The underlying map.
720    ConvertMap(const M &m) : _m(m) {}
721
722    /// \e
723    Value operator[](const Key &k) const { return _m[k]; }
724  };
725
726  /// Returns a \ref ConvertMap class
727
728  /// This function just returns a \ref ConvertMap class.
729  /// \relates ConvertMap
730  template<typename V, typename M>
731  inline ConvertMap<M, V> convertMap(const M &map) {
732    return ConvertMap<M, V>(map);
733  }
734
735
736  /// Applies all map setting operations to two maps
737
738  /// This map has two \ref concepts::WriteMap "writable map" parameters
739  /// and each write request will be passed to both of them.
740  /// If \c M1 is also \ref concepts::ReadMap "readable", then the read
741  /// operations will return the corresponding values of \c M1.
742  ///
743  /// The \c Key and \c Value types are inherited from \c M1.
744  /// The \c Key and \c Value of \c M2 must be convertible from those
745  /// of \c M1.
746  ///
747  /// The simplest way of using this map is through the forkMap()
748  /// function.
749  template<typename  M1, typename M2>
750  class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
751    M1 &_m1;
752    M2 &_m2;
753  public:
754    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
755    typedef typename Parent::Key Key;
756    typedef typename Parent::Value Value;
757
758    /// Constructor
759    ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
760    /// Returns the value associated with the given key in the first map.
761    Value operator[](const Key &k) const { return _m1[k]; }
762    /// Sets the value associated with the given key in both maps.
763    void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); }
764  };
765
766  /// Returns a \ref ForkMap class
767
768  /// This function just returns a \ref ForkMap class.
769  /// \relates ForkMap
770  template <typename M1, typename M2>
771  inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) {
772    return ForkMap<M1,M2>(m1,m2);
773  }
774
775
776  /// Sum of two maps
777
778  /// This \ref concepts::ReadMap "read-only map" returns the sum
779  /// of the values of the two given maps.
780  /// Its \c Key and \c Value types are inherited from \c M1.
781  /// The \c Key and \c Value of \c M2 must be convertible to those of
782  /// \c M1.
783  ///
784  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
785  /// \code
786  ///   AddMap<M1,M2> am(m1,m2);
787  /// \endcode
788  /// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>.
789  ///
790  /// The simplest way of using this map is through the addMap()
791  /// function.
792  ///
793  /// \sa SubMap, MulMap, DivMap
794  /// \sa ShiftMap, ShiftWriteMap
795  template<typename M1, typename M2>
796  class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
797    const M1 &_m1;
798    const M2 &_m2;
799  public:
800    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
801    typedef typename Parent::Key Key;
802    typedef typename Parent::Value Value;
803
804    /// Constructor
805    AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
806    /// \e
807    Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
808  };
809
810  /// Returns an \ref AddMap class
811
812  /// This function just returns an \ref AddMap class.
813  ///
814  /// For example, if \c m1 and \c m2 are both maps with \c double
815  /// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to
816  /// <tt>m1[x]+m2[x]</tt>.
817  ///
818  /// \relates AddMap
819  template<typename M1, typename M2>
820  inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) {
821    return AddMap<M1, M2>(m1,m2);
822  }
823
824
825  /// Difference of two maps
826
827  /// This \ref concepts::ReadMap "read-only map" returns the difference
828  /// of the values of the two given maps.
829  /// Its \c Key and \c Value types are inherited from \c M1.
830  /// The \c Key and \c Value of \c M2 must be convertible to those of
831  /// \c M1.
832  ///
833  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
834  /// \code
835  ///   SubMap<M1,M2> sm(m1,m2);
836  /// \endcode
837  /// <tt>sm[x]</tt> will be equal to <tt>m1[x]-m2[x]</tt>.
838  ///
839  /// The simplest way of using this map is through the subMap()
840  /// function.
841  ///
842  /// \sa AddMap, MulMap, DivMap
843  template<typename M1, typename M2>
844  class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
845    const M1 &_m1;
846    const M2 &_m2;
847  public:
848    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
849    typedef typename Parent::Key Key;
850    typedef typename Parent::Value Value;
851
852    /// Constructor
853    SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
854    /// \e
855    Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
856  };
857
858  /// Returns a \ref SubMap class
859
860  /// This function just returns a \ref SubMap class.
861  ///
862  /// For example, if \c m1 and \c m2 are both maps with \c double
863  /// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to
864  /// <tt>m1[x]-m2[x]</tt>.
865  ///
866  /// \relates SubMap
867  template<typename M1, typename M2>
868  inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
869    return SubMap<M1, M2>(m1,m2);
870  }
871
872
873  /// Product of two maps
874
875  /// This \ref concepts::ReadMap "read-only map" returns the product
876  /// of the values of the two given maps.
877  /// Its \c Key and \c Value types are inherited from \c M1.
878  /// The \c Key and \c Value of \c M2 must be convertible to those of
879  /// \c M1.
880  ///
881  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
882  /// \code
883  ///   MulMap<M1,M2> mm(m1,m2);
884  /// \endcode
885  /// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>.
886  ///
887  /// The simplest way of using this map is through the mulMap()
888  /// function.
889  ///
890  /// \sa AddMap, SubMap, DivMap
891  /// \sa ScaleMap, ScaleWriteMap
892  template<typename M1, typename M2>
893  class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
894    const M1 &_m1;
895    const M2 &_m2;
896  public:
897    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
898    typedef typename Parent::Key Key;
899    typedef typename Parent::Value Value;
900
901    /// Constructor
902    MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
903    /// \e
904    Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
905  };
906
907  /// Returns a \ref MulMap class
908
909  /// This function just returns a \ref MulMap class.
910  ///
911  /// For example, if \c m1 and \c m2 are both maps with \c double
912  /// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to
913  /// <tt>m1[x]*m2[x]</tt>.
914  ///
915  /// \relates MulMap
916  template<typename M1, typename M2>
917  inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
918    return MulMap<M1, M2>(m1,m2);
919  }
920
921
922  /// Quotient of two maps
923
924  /// This \ref concepts::ReadMap "read-only map" returns the quotient
925  /// of the values of the two given maps.
926  /// Its \c Key and \c Value types are inherited from \c M1.
927  /// The \c Key and \c Value of \c M2 must be convertible to those of
928  /// \c M1.
929  ///
930  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
931  /// \code
932  ///   DivMap<M1,M2> dm(m1,m2);
933  /// \endcode
934  /// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>.
935  ///
936  /// The simplest way of using this map is through the divMap()
937  /// function.
938  ///
939  /// \sa AddMap, SubMap, MulMap
940  template<typename M1, typename M2>
941  class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
942    const M1 &_m1;
943    const M2 &_m2;
944  public:
945    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
946    typedef typename Parent::Key Key;
947    typedef typename Parent::Value Value;
948
949    /// Constructor
950    DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
951    /// \e
952    Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
953  };
954
955  /// Returns a \ref DivMap class
956
957  /// This function just returns a \ref DivMap class.
958  ///
959  /// For example, if \c m1 and \c m2 are both maps with \c double
960  /// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to
961  /// <tt>m1[x]/m2[x]</tt>.
962  ///
963  /// \relates DivMap
964  template<typename M1, typename M2>
965  inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
966    return DivMap<M1, M2>(m1,m2);
967  }
968
969
970  /// Shifts a map with a constant.
971
972  /// This \ref concepts::ReadMap "read-only map" returns the sum of
973  /// the given map and a constant value (i.e. it shifts the map with
974  /// the constant). Its \c Key and \c Value are inherited from \c M.
975  ///
976  /// Actually,
977  /// \code
978  ///   ShiftMap<M> sh(m,v);
979  /// \endcode
980  /// is equivalent to
981  /// \code
982  ///   ConstMap<M::Key, M::Value> cm(v);
983  ///   AddMap<M, ConstMap<M::Key, M::Value> > sh(m,cm);
984  /// \endcode
985  ///
986  /// The simplest way of using this map is through the shiftMap()
987  /// function.
988  ///
989  /// \sa ShiftWriteMap
990  template<typename M, typename C = typename M::Value>
991  class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
992    const M &_m;
993    C _v;
994  public:
995    typedef MapBase<typename M::Key, typename M::Value> Parent;
996    typedef typename Parent::Key Key;
997    typedef typename Parent::Value Value;
998
999    /// Constructor
1000
1001    /// Constructor.
1002    /// \param m The undelying map.
1003    /// \param v The constant value.
1004    ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
1005    /// \e
1006    Value operator[](const Key &k) const { return _m[k]+_v; }
1007  };
1008
1009  /// Shifts a map with a constant (read-write version).
1010
1011  /// This \ref concepts::ReadWriteMap "read-write map" returns the sum
1012  /// of the given map and a constant value (i.e. it shifts the map with
1013  /// the constant). Its \c Key and \c Value are inherited from \c M.
1014  /// It makes also possible to write the map.
1015  ///
1016  /// The simplest way of using this map is through the shiftWriteMap()
1017  /// function.
1018  ///
1019  /// \sa ShiftMap
1020  template<typename M, typename C = typename M::Value>
1021  class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
1022    M &_m;
1023    C _v;
1024  public:
1025    typedef MapBase<typename M::Key, typename M::Value> Parent;
1026    typedef typename Parent::Key Key;
1027    typedef typename Parent::Value Value;
1028
1029    /// Constructor
1030
1031    /// Constructor.
1032    /// \param m The undelying map.
1033    /// \param v The constant value.
1034    ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
1035    /// \e
1036    Value operator[](const Key &k) const { return _m[k]+_v; }
1037    /// \e
1038    void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
1039  };
1040
1041  /// Returns a \ref ShiftMap class
1042
1043  /// This function just returns a \ref ShiftMap class.
1044  ///
1045  /// For example, if \c m is a map with \c double values and \c v is
1046  /// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to
1047  /// <tt>m[x]+v</tt>.
1048  ///
1049  /// \relates ShiftMap
1050  template<typename M, typename C>
1051  inline ShiftMap<M, C> shiftMap(const M &m, const C &v) {
1052    return ShiftMap<M, C>(m,v);
1053  }
1054
1055  /// Returns a \ref ShiftWriteMap class
1056
1057  /// This function just returns a \ref ShiftWriteMap class.
1058  ///
1059  /// For example, if \c m is a map with \c double values and \c v is
1060  /// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to
1061  /// <tt>m[x]+v</tt>.
1062  /// Moreover it makes also possible to write the map.
1063  ///
1064  /// \relates ShiftWriteMap
1065  template<typename M, typename C>
1066  inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) {
1067    return ShiftWriteMap<M, C>(m,v);
1068  }
1069
1070
1071  /// Scales a map with a constant.
1072
1073  /// This \ref concepts::ReadMap "read-only map" returns the value of
1074  /// the given map multiplied from the left side with a constant value.
1075  /// Its \c Key and \c Value are inherited from \c M.
1076  ///
1077  /// Actually,
1078  /// \code
1079  ///   ScaleMap<M> sc(m,v);
1080  /// \endcode
1081  /// is equivalent to
1082  /// \code
1083  ///   ConstMap<M::Key, M::Value> cm(v);
1084  ///   MulMap<ConstMap<M::Key, M::Value>, M> sc(cm,m);
1085  /// \endcode
1086  ///
1087  /// The simplest way of using this map is through the scaleMap()
1088  /// function.
1089  ///
1090  /// \sa ScaleWriteMap
1091  template<typename M, typename C = typename M::Value>
1092  class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
1093    const M &_m;
1094    C _v;
1095  public:
1096    typedef MapBase<typename M::Key, typename M::Value> Parent;
1097    typedef typename Parent::Key Key;
1098    typedef typename Parent::Value Value;
1099
1100    /// Constructor
1101
1102    /// Constructor.
1103    /// \param m The undelying map.
1104    /// \param v The constant value.
1105    ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
1106    /// \e
1107    Value operator[](const Key &k) const { return _v*_m[k]; }
1108  };
1109
1110  /// Scales a map with a constant (read-write version).
1111
1112  /// This \ref concepts::ReadWriteMap "read-write map" returns the value of
1113  /// the given map multiplied from the left side with a constant value.
1114  /// Its \c Key and \c Value are inherited from \c M.
1115  /// It can also be used as write map if the \c / operator is defined
1116  /// between \c Value and \c C and the given multiplier is not zero.
1117  ///
1118  /// The simplest way of using this map is through the scaleWriteMap()
1119  /// function.
1120  ///
1121  /// \sa ScaleMap
1122  template<typename M, typename C = typename M::Value>
1123  class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
1124    M &_m;
1125    C _v;
1126  public:
1127    typedef MapBase<typename M::Key, typename M::Value> Parent;
1128    typedef typename Parent::Key Key;
1129    typedef typename Parent::Value Value;
1130
1131    /// Constructor
1132
1133    /// Constructor.
1134    /// \param m The undelying map.
1135    /// \param v The constant value.
1136    ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
1137    /// \e
1138    Value operator[](const Key &k) const { return _v*_m[k]; }
1139    /// \e
1140    void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
1141  };
1142
1143  /// Returns a \ref ScaleMap class
1144
1145  /// This function just returns a \ref ScaleMap class.
1146  ///
1147  /// For example, if \c m is a map with \c double values and \c v is
1148  /// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to
1149  /// <tt>v*m[x]</tt>.
1150  ///
1151  /// \relates ScaleMap
1152  template<typename M, typename C>
1153  inline ScaleMap<M, C> scaleMap(const M &m, const C &v) {
1154    return ScaleMap<M, C>(m,v);
1155  }
1156
1157  /// Returns a \ref ScaleWriteMap class
1158
1159  /// This function just returns a \ref ScaleWriteMap class.
1160  ///
1161  /// For example, if \c m is a map with \c double values and \c v is
1162  /// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to
1163  /// <tt>v*m[x]</tt>.
1164  /// Moreover it makes also possible to write the map.
1165  ///
1166  /// \relates ScaleWriteMap
1167  template<typename M, typename C>
1168  inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) {
1169    return ScaleWriteMap<M, C>(m,v);
1170  }
1171
1172
1173  /// Negative of a map
1174
1175  /// This \ref concepts::ReadMap "read-only map" returns the negative
1176  /// of the values of the given map (using the unary \c - operator).
1177  /// Its \c Key and \c Value are inherited from \c M.
1178  ///
1179  /// If M::Value is \c int, \c double etc., then
1180  /// \code
1181  ///   NegMap<M> neg(m);
1182  /// \endcode
1183  /// is equivalent to
1184  /// \code
1185  ///   ScaleMap<M> neg(m,-1);
1186  /// \endcode
1187  ///
1188  /// The simplest way of using this map is through the negMap()
1189  /// function.
1190  ///
1191  /// \sa NegWriteMap
1192  template<typename M>
1193  class NegMap : public MapBase<typename M::Key, typename M::Value> {
1194    const M& _m;
1195  public:
1196    typedef MapBase<typename M::Key, typename M::Value> Parent;
1197    typedef typename Parent::Key Key;
1198    typedef typename Parent::Value Value;
1199
1200    /// Constructor
1201    NegMap(const M &m) : _m(m) {}
1202    /// \e
1203    Value operator[](const Key &k) const { return -_m[k]; }
1204  };
1205
1206  /// Negative of a map (read-write version)
1207
1208  /// This \ref concepts::ReadWriteMap "read-write map" returns the
1209  /// negative of the values of the given map (using the unary \c -
1210  /// operator).
1211  /// Its \c Key and \c Value are inherited from \c M.
1212  /// It makes also possible to write the map.
1213  ///
1214  /// If M::Value is \c int, \c double etc., then
1215  /// \code
1216  ///   NegWriteMap<M> neg(m);
1217  /// \endcode
1218  /// is equivalent to
1219  /// \code
1220  ///   ScaleWriteMap<M> neg(m,-1);
1221  /// \endcode
1222  ///
1223  /// The simplest way of using this map is through the negWriteMap()
1224  /// function.
1225  ///
1226  /// \sa NegMap
1227  template<typename M>
1228  class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
1229    M &_m;
1230  public:
1231    typedef MapBase<typename M::Key, typename M::Value> Parent;
1232    typedef typename Parent::Key Key;
1233    typedef typename Parent::Value Value;
1234
1235    /// Constructor
1236    NegWriteMap(M &m) : _m(m) {}
1237    /// \e
1238    Value operator[](const Key &k) const { return -_m[k]; }
1239    /// \e
1240    void set(const Key &k, const Value &v) { _m.set(k, -v); }
1241  };
1242
1243  /// Returns a \ref NegMap class
1244
1245  /// This function just returns a \ref NegMap class.
1246  ///
1247  /// For example, if \c m is a map with \c double values, then
1248  /// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
1249  ///
1250  /// \relates NegMap
1251  template <typename M>
1252  inline NegMap<M> negMap(const M &m) {
1253    return NegMap<M>(m);
1254  }
1255
1256  /// Returns a \ref NegWriteMap class
1257
1258  /// This function just returns a \ref NegWriteMap class.
1259  ///
1260  /// For example, if \c m is a map with \c double values, then
1261  /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
1262  /// Moreover it makes also possible to write the map.
1263  ///
1264  /// \relates NegWriteMap
1265  template <typename M>
1266  inline NegWriteMap<M> negWriteMap(M &m) {
1267    return NegWriteMap<M>(m);
1268  }
1269
1270
1271  /// Absolute value of a map
1272
1273  /// This \ref concepts::ReadMap "read-only map" returns the absolute
1274  /// value of the values of the given map.
1275  /// Its \c Key and \c Value are inherited from \c M.
1276  /// \c Value must be comparable to \c 0 and the unary \c -
1277  /// operator must be defined for it, of course.
1278  ///
1279  /// The simplest way of using this map is through the absMap()
1280  /// function.
1281  template<typename M>
1282  class AbsMap : public MapBase<typename M::Key, typename M::Value> {
1283    const M &_m;
1284  public:
1285    typedef MapBase<typename M::Key, typename M::Value> Parent;
1286    typedef typename Parent::Key Key;
1287    typedef typename Parent::Value Value;
1288
1289    /// Constructor
1290    AbsMap(const M &m) : _m(m) {}
1291    /// \e
1292    Value operator[](const Key &k) const {
1293      Value tmp = _m[k];
1294      return tmp >= 0 ? tmp : -tmp;
1295    }
1296
1297  };
1298
1299  /// Returns an \ref AbsMap class
1300
1301  /// This function just returns an \ref AbsMap class.
1302  ///
1303  /// For example, if \c m is a map with \c double values, then
1304  /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if
1305  /// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is
1306  /// negative.
1307  ///
1308  /// \relates AbsMap
1309  template<typename M>
1310  inline AbsMap<M> absMap(const M &m) {
1311    return AbsMap<M>(m);
1312  }
1313
1314  /// @}
1315
1316  // Logical maps and map adaptors:
1317
1318  /// \addtogroup maps
1319  /// @{
1320
1321  /// Constant \c true map.
1322
1323  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1324  /// each key.
1325  ///
1326  /// Note that
1327  /// \code
1328  ///   TrueMap<K> tm;
1329  /// \endcode
1330  /// is equivalent to
1331  /// \code
1332  ///   ConstMap<K,bool> tm(true);
1333  /// \endcode
1334  ///
1335  /// \sa FalseMap
1336  /// \sa ConstMap
1337  template <typename K>
1338  class TrueMap : public MapBase<K, bool> {
1339  public:
1340    typedef MapBase<K, bool> Parent;
1341    typedef typename Parent::Key Key;
1342    typedef typename Parent::Value Value;
1343
1344    /// Gives back \c true.
1345    Value operator[](const Key&) const { return true; }
1346  };
1347
1348  /// Returns a \ref TrueMap class
1349
1350  /// This function just returns a \ref TrueMap class.
1351  /// \relates TrueMap
1352  template<typename K>
1353  inline TrueMap<K> trueMap() {
1354    return TrueMap<K>();
1355  }
1356
1357
1358  /// Constant \c false map.
1359
1360  /// This \ref concepts::ReadMap "read-only map" assigns \c false to
1361  /// each key.
1362  ///
1363  /// Note that
1364  /// \code
1365  ///   FalseMap<K> fm;
1366  /// \endcode
1367  /// is equivalent to
1368  /// \code
1369  ///   ConstMap<K,bool> fm(false);
1370  /// \endcode
1371  ///
1372  /// \sa TrueMap
1373  /// \sa ConstMap
1374  template <typename K>
1375  class FalseMap : public MapBase<K, bool> {
1376  public:
1377    typedef MapBase<K, bool> Parent;
1378    typedef typename Parent::Key Key;
1379    typedef typename Parent::Value Value;
1380
1381    /// Gives back \c false.
1382    Value operator[](const Key&) const { return false; }
1383  };
1384
1385  /// Returns a \ref FalseMap class
1386
1387  /// This function just returns a \ref FalseMap class.
1388  /// \relates FalseMap
1389  template<typename K>
1390  inline FalseMap<K> falseMap() {
1391    return FalseMap<K>();
1392  }
1393
1394  /// @}
1395
1396  /// \addtogroup map_adaptors
1397  /// @{
1398
1399  /// Logical 'and' of two maps
1400
1401  /// This \ref concepts::ReadMap "read-only map" returns the logical
1402  /// 'and' of the values of the two given maps.
1403  /// Its \c Key type is inherited from \c M1 and its \c Value type is
1404  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1405  ///
1406  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1407  /// \code
1408  ///   AndMap<M1,M2> am(m1,m2);
1409  /// \endcode
1410  /// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>.
1411  ///
1412  /// The simplest way of using this map is through the andMap()
1413  /// function.
1414  ///
1415  /// \sa OrMap
1416  /// \sa NotMap, NotWriteMap
1417  template<typename M1, typename M2>
1418  class AndMap : public MapBase<typename M1::Key, bool> {
1419    const M1 &_m1;
1420    const M2 &_m2;
1421  public:
1422    typedef MapBase<typename M1::Key, bool> Parent;
1423    typedef typename Parent::Key Key;
1424    typedef typename Parent::Value Value;
1425
1426    /// Constructor
1427    AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1428    /// \e
1429    Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
1430  };
1431
1432  /// Returns an \ref AndMap class
1433
1434  /// This function just returns an \ref AndMap class.
1435  ///
1436  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
1437  /// then <tt>andMap(m1,m2)[x]</tt> will be equal to
1438  /// <tt>m1[x]&&m2[x]</tt>.
1439  ///
1440  /// \relates AndMap
1441  template<typename M1, typename M2>
1442  inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) {
1443    return AndMap<M1, M2>(m1,m2);
1444  }
1445
1446
1447  /// Logical 'or' of two maps
1448
1449  /// This \ref concepts::ReadMap "read-only map" returns the logical
1450  /// 'or' of the values of the two given maps.
1451  /// Its \c Key type is inherited from \c M1 and its \c Value type is
1452  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1453  ///
1454  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1455  /// \code
1456  ///   OrMap<M1,M2> om(m1,m2);
1457  /// \endcode
1458  /// <tt>om[x]</tt> will be equal to <tt>m1[x]||m2[x]</tt>.
1459  ///
1460  /// The simplest way of using this map is through the orMap()
1461  /// function.
1462  ///
1463  /// \sa AndMap
1464  /// \sa NotMap, NotWriteMap
1465  template<typename M1, typename M2>
1466  class OrMap : public MapBase<typename M1::Key, bool> {
1467    const M1 &_m1;
1468    const M2 &_m2;
1469  public:
1470    typedef MapBase<typename M1::Key, bool> Parent;
1471    typedef typename Parent::Key Key;
1472    typedef typename Parent::Value Value;
1473
1474    /// Constructor
1475    OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1476    /// \e
1477    Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
1478  };
1479
1480  /// Returns an \ref OrMap class
1481
1482  /// This function just returns an \ref OrMap class.
1483  ///
1484  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
1485  /// then <tt>orMap(m1,m2)[x]</tt> will be equal to
1486  /// <tt>m1[x]||m2[x]</tt>.
1487  ///
1488  /// \relates OrMap
1489  template<typename M1, typename M2>
1490  inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) {
1491    return OrMap<M1, M2>(m1,m2);
1492  }
1493
1494
1495  /// Logical 'not' of a map
1496
1497  /// This \ref concepts::ReadMap "read-only map" returns the logical
1498  /// negation of the values of the given map.
1499  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
1500  ///
1501  /// The simplest way of using this map is through the notMap()
1502  /// function.
1503  ///
1504  /// \sa NotWriteMap
1505  template <typename M>
1506  class NotMap : public MapBase<typename M::Key, bool> {
1507    const M &_m;
1508  public:
1509    typedef MapBase<typename M::Key, bool> Parent;
1510    typedef typename Parent::Key Key;
1511    typedef typename Parent::Value Value;
1512
1513    /// Constructor
1514    NotMap(const M &m) : _m(m) {}
1515    /// \e
1516    Value operator[](const Key &k) const { return !_m[k]; }
1517  };
1518
1519  /// Logical 'not' of a map (read-write version)
1520
1521  /// This \ref concepts::ReadWriteMap "read-write map" returns the
1522  /// logical negation of the values of the given map.
1523  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
1524  /// It makes also possible to write the map. When a value is set,
1525  /// the opposite value is set to the original map.
1526  ///
1527  /// The simplest way of using this map is through the notWriteMap()
1528  /// function.
1529  ///
1530  /// \sa NotMap
1531  template <typename M>
1532  class NotWriteMap : public MapBase<typename M::Key, bool> {
1533    M &_m;
1534  public:
1535    typedef MapBase<typename M::Key, bool> Parent;
1536    typedef typename Parent::Key Key;
1537    typedef typename Parent::Value Value;
1538
1539    /// Constructor
1540    NotWriteMap(M &m) : _m(m) {}
1541    /// \e
1542    Value operator[](const Key &k) const { return !_m[k]; }
1543    /// \e
1544    void set(const Key &k, bool v) { _m.set(k, !v); }
1545  };
1546
1547  /// Returns a \ref NotMap class
1548
1549  /// This function just returns a \ref NotMap class.
1550  ///
1551  /// For example, if \c m is a map with \c bool values, then
1552  /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
1553  ///
1554  /// \relates NotMap
1555  template <typename M>
1556  inline NotMap<M> notMap(const M &m) {
1557    return NotMap<M>(m);
1558  }
1559
1560  /// Returns a \ref NotWriteMap class
1561
1562  /// This function just returns a \ref NotWriteMap class.
1563  ///
1564  /// For example, if \c m is a map with \c bool values, then
1565  /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
1566  /// Moreover it makes also possible to write the map.
1567  ///
1568  /// \relates NotWriteMap
1569  template <typename M>
1570  inline NotWriteMap<M> notWriteMap(M &m) {
1571    return NotWriteMap<M>(m);
1572  }
1573
1574
1575  /// Combination of two maps using the \c == operator
1576
1577  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1578  /// the keys for which the corresponding values of the two maps are
1579  /// equal.
1580  /// Its \c Key type is inherited from \c M1 and its \c Value type is
1581  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1582  ///
1583  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1584  /// \code
1585  ///   EqualMap<M1,M2> em(m1,m2);
1586  /// \endcode
1587  /// <tt>em[x]</tt> will be equal to <tt>m1[x]==m2[x]</tt>.
1588  ///
1589  /// The simplest way of using this map is through the equalMap()
1590  /// function.
1591  ///
1592  /// \sa LessMap
1593  template<typename M1, typename M2>
1594  class EqualMap : public MapBase<typename M1::Key, bool> {
1595    const M1 &_m1;
1596    const M2 &_m2;
1597  public:
1598    typedef MapBase<typename M1::Key, bool> Parent;
1599    typedef typename Parent::Key Key;
1600    typedef typename Parent::Value Value;
1601
1602    /// Constructor
1603    EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1604    /// \e
1605    Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
1606  };
1607
1608  /// Returns an \ref EqualMap class
1609
1610  /// This function just returns an \ref EqualMap class.
1611  ///
1612  /// For example, if \c m1 and \c m2 are maps with keys and values of
1613  /// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to
1614  /// <tt>m1[x]==m2[x]</tt>.
1615  ///
1616  /// \relates EqualMap
1617  template<typename M1, typename M2>
1618  inline EqualMap<M1, M2> equalMap(const M1 &m1, const M2 &m2) {
1619    return EqualMap<M1, M2>(m1,m2);
1620  }
1621
1622
1623  /// Combination of two maps using the \c < operator
1624
1625  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1626  /// the keys for which the corresponding value of the first map is
1627  /// less then the value of the second map.
1628  /// Its \c Key type is inherited from \c M1 and its \c Value type is
1629  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1630  ///
1631  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1632  /// \code
1633  ///   LessMap<M1,M2> lm(m1,m2);
1634  /// \endcode
1635  /// <tt>lm[x]</tt> will be equal to <tt>m1[x]<m2[x]</tt>.
1636  ///
1637  /// The simplest way of using this map is through the lessMap()
1638  /// function.
1639  ///
1640  /// \sa EqualMap
1641  template<typename M1, typename M2>
1642  class LessMap : public MapBase<typename M1::Key, bool> {
1643    const M1 &_m1;
1644    const M2 &_m2;
1645  public:
1646    typedef MapBase<typename M1::Key, bool> Parent;
1647    typedef typename Parent::Key Key;
1648    typedef typename Parent::Value Value;
1649
1650    /// Constructor
1651    LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1652    /// \e
1653    Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
1654  };
1655
1656  /// Returns an \ref LessMap class
1657
1658  /// This function just returns an \ref LessMap class.
1659  ///
1660  /// For example, if \c m1 and \c m2 are maps with keys and values of
1661  /// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to
1662  /// <tt>m1[x]<m2[x]</tt>.
1663  ///
1664  /// \relates LessMap
1665  template<typename M1, typename M2>
1666  inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) {
1667    return LessMap<M1, M2>(m1,m2);
1668  }
1669
1670  namespace _maps_bits {
1671
1672    template <typename _Iterator, typename Enable = void>
1673    struct IteratorTraits {
1674      typedef typename std::iterator_traits<_Iterator>::value_type Value;
1675    };
1676
1677    template <typename _Iterator>
1678    struct IteratorTraits<_Iterator,
1679      typename exists<typename _Iterator::container_type>::type>
1680    {
1681      typedef typename _Iterator::container_type::value_type Value;
1682    };
1683
1684  }
1685
1686  /// \brief Writable bool map for logging each \c true assigned element
1687  ///
1688  /// A \ref concepts::WriteMap "writable" bool map for logging
1689  /// each \c true assigned element, i.e it copies subsequently each
1690  /// keys set to \c true to the given iterator.
1691  /// The most important usage of it is storing certain nodes or arcs
1692  /// that were marked \c true by an algorithm.
1693  ///
1694  /// There are several algorithms that provide solutions through bool
1695  /// maps and most of them assign \c true at most once for each key.
1696  /// In these cases it is a natural request to store each \c true
1697  /// assigned elements (in order of the assignment), which can be
1698  /// easily done with LoggerBoolMap.
1699  ///
1700  /// The simplest way of using this map is through the loggerBoolMap()
1701  /// function.
1702  ///
1703  /// \tparam It The type of the iterator.
1704  /// \tparam Ke The key type of the map. The default value set
1705  /// according to the iterator type should work in most cases.
1706  ///
1707  /// \note The container of the iterator must contain enough space
1708  /// for the elements or the iterator should be an inserter iterator.
1709#ifdef DOXYGEN
1710  template <typename It, typename Ke>
1711#else
1712  template <typename It,
1713            typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
1714#endif
1715  class LoggerBoolMap {
1716  public:
1717    typedef It Iterator;
1718
1719    typedef Ke Key;
1720    typedef bool Value;
1721
1722    /// Constructor
1723    LoggerBoolMap(Iterator it)
1724      : _begin(it), _end(it) {}
1725
1726    /// Gives back the given iterator set for the first key
1727    Iterator begin() const {
1728      return _begin;
1729    }
1730
1731    /// Gives back the the 'after the last' iterator
1732    Iterator end() const {
1733      return _end;
1734    }
1735
1736    /// The set function of the map
1737    void set(const Key& key, Value value) {
1738      if (value) {
1739        *_end++ = key;
1740      }
1741    }
1742
1743  private:
1744    Iterator _begin;
1745    Iterator _end;
1746  };
1747
1748  /// Returns a \ref LoggerBoolMap class
1749
1750  /// This function just returns a \ref LoggerBoolMap class.
1751  ///
1752  /// The most important usage of it is storing certain nodes or arcs
1753  /// that were marked \c true by an algorithm.
1754  /// For example it makes easier to store the nodes in the processing
1755  /// order of Dfs algorithm, as the following examples show.
1756  /// \code
1757  ///   std::vector<Node> v;
1758  ///   dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
1759  /// \endcode
1760  /// \code
1761  ///   std::vector<Node> v(countNodes(g));
1762  ///   dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
1763  /// \endcode
1764  ///
1765  /// \note The container of the iterator must contain enough space
1766  /// for the elements or the iterator should be an inserter iterator.
1767  ///
1768  /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
1769  /// it cannot be used when a readable map is needed, for example as
1770  /// \c ReachedMap for \ref Bfs, \ref Dfs and \ref Dijkstra algorithms.
1771  ///
1772  /// \relates LoggerBoolMap
1773  template<typename Iterator>
1774  inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
1775    return LoggerBoolMap<Iterator>(it);
1776  }
1777
1778  /// Provides an immutable and unique id for each item in the graph.
1779
1780  /// The IdMap class provides a unique and immutable id for each item of the
1781  /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
1782  /// different items (nodes) get different ids <li>\b immutable: the id of an
1783  /// item (node) does not change (even if you delete other nodes).  </ul>
1784  /// Through this map you get access (i.e. can read) the inner id values of
1785  /// the items stored in the graph. This map can be inverted with its member
1786  /// class \c InverseMap or with the \c operator() member.
1787  ///
1788  template <typename _Graph, typename _Item>
1789  class IdMap {
1790  public:
1791    typedef _Graph Graph;
1792    typedef int Value;
1793    typedef _Item Item;
1794    typedef _Item Key;
1795
1796    /// \brief Constructor.
1797    ///
1798    /// Constructor of the map.
1799    explicit IdMap(const Graph& graph) : _graph(&graph) {}
1800
1801    /// \brief Gives back the \e id of the item.
1802    ///
1803    /// Gives back the immutable and unique \e id of the item.
1804    int operator[](const Item& item) const { return _graph->id(item);}
1805
1806    /// \brief Gives back the item by its id.
1807    ///
1808    /// Gives back the item by its id.
1809    Item operator()(int id) { return _graph->fromId(id, Item()); }
1810
1811  private:
1812    const Graph* _graph;
1813
1814  public:
1815
1816    /// \brief The class represents the inverse of its owner (IdMap).
1817    ///
1818    /// The class represents the inverse of its owner (IdMap).
1819    /// \see inverse()
1820    class InverseMap {
1821    public:
1822
1823      /// \brief Constructor.
1824      ///
1825      /// Constructor for creating an id-to-item map.
1826      explicit InverseMap(const Graph& graph) : _graph(&graph) {}
1827
1828      /// \brief Constructor.
1829      ///
1830      /// Constructor for creating an id-to-item map.
1831      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
1832
1833      /// \brief Gives back the given item from its id.
1834      ///
1835      /// Gives back the given item from its id.
1836      ///
1837      Item operator[](int id) const { return _graph->fromId(id, Item());}
1838
1839    private:
1840      const Graph* _graph;
1841    };
1842
1843    /// \brief Gives back the inverse of the map.
1844    ///
1845    /// Gives back the inverse of the IdMap.
1846    InverseMap inverse() const { return InverseMap(*_graph);}
1847
1848  };
1849
1850  /// \brief Returns the source of the given arc.
1851  ///
1852  /// The SourceMap gives back the source Node of the given arc.
1853  /// \see TargetMap
1854  template <typename Digraph>
1855  class SourceMap {
1856  public:
1857
1858    typedef typename Digraph::Node Value;
1859    typedef typename Digraph::Arc Key;
1860
1861    /// \brief Constructor
1862    ///
1863    /// Constructor
1864    /// \param _digraph The digraph that the map belongs to.
1865    explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
1866
1867    /// \brief The subscript operator.
1868    ///
1869    /// The subscript operator.
1870    /// \param arc The arc
1871    /// \return The source of the arc
1872    Value operator[](const Key& arc) const {
1873      return _digraph.source(arc);
1874    }
1875
1876  private:
1877    const Digraph& _digraph;
1878  };
1879
1880  /// \brief Returns a \ref SourceMap class.
1881  ///
1882  /// This function just returns an \ref SourceMap class.
1883  /// \relates SourceMap
1884  template <typename Digraph>
1885  inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
1886    return SourceMap<Digraph>(digraph);
1887  }
1888
1889  /// \brief Returns the target of the given arc.
1890  ///
1891  /// The TargetMap gives back the target Node of the given arc.
1892  /// \see SourceMap
1893  template <typename Digraph>
1894  class TargetMap {
1895  public:
1896
1897    typedef typename Digraph::Node Value;
1898    typedef typename Digraph::Arc Key;
1899
1900    /// \brief Constructor
1901    ///
1902    /// Constructor
1903    /// \param _digraph The digraph that the map belongs to.
1904    explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
1905
1906    /// \brief The subscript operator.
1907    ///
1908    /// The subscript operator.
1909    /// \param e The arc
1910    /// \return The target of the arc
1911    Value operator[](const Key& e) const {
1912      return _digraph.target(e);
1913    }
1914
1915  private:
1916    const Digraph& _digraph;
1917  };
1918
1919  /// \brief Returns a \ref TargetMap class.
1920  ///
1921  /// This function just returns a \ref TargetMap class.
1922  /// \relates TargetMap
1923  template <typename Digraph>
1924  inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
1925    return TargetMap<Digraph>(digraph);
1926  }
1927
1928  /// \brief Returns the "forward" directed arc view of an edge.
1929  ///
1930  /// Returns the "forward" directed arc view of an edge.
1931  /// \see BackwardMap
1932  template <typename Graph>
1933  class ForwardMap {
1934  public:
1935
1936    typedef typename Graph::Arc Value;
1937    typedef typename Graph::Edge Key;
1938
1939    /// \brief Constructor
1940    ///
1941    /// Constructor
1942    /// \param _graph The graph that the map belongs to.
1943    explicit ForwardMap(const Graph& graph) : _graph(graph) {}
1944
1945    /// \brief The subscript operator.
1946    ///
1947    /// The subscript operator.
1948    /// \param key An edge
1949    /// \return The "forward" directed arc view of edge
1950    Value operator[](const Key& key) const {
1951      return _graph.direct(key, true);
1952    }
1953
1954  private:
1955    const Graph& _graph;
1956  };
1957
1958  /// \brief Returns a \ref ForwardMap class.
1959  ///
1960  /// This function just returns an \ref ForwardMap class.
1961  /// \relates ForwardMap
1962  template <typename Graph>
1963  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
1964    return ForwardMap<Graph>(graph);
1965  }
1966
1967  /// \brief Returns the "backward" directed arc view of an edge.
1968  ///
1969  /// Returns the "backward" directed arc view of an edge.
1970  /// \see ForwardMap
1971  template <typename Graph>
1972  class BackwardMap {
1973  public:
1974
1975    typedef typename Graph::Arc Value;
1976    typedef typename Graph::Edge Key;
1977
1978    /// \brief Constructor
1979    ///
1980    /// Constructor
1981    /// \param _graph The graph that the map belongs to.
1982    explicit BackwardMap(const Graph& graph) : _graph(graph) {}
1983
1984    /// \brief The subscript operator.
1985    ///
1986    /// The subscript operator.
1987    /// \param key An edge
1988    /// \return The "backward" directed arc view of edge
1989    Value operator[](const Key& key) const {
1990      return _graph.direct(key, false);
1991    }
1992
1993  private:
1994    const Graph& _graph;
1995  };
1996
1997  /// \brief Returns a \ref BackwardMap class
1998
1999  /// This function just returns a \ref BackwardMap class.
2000  /// \relates BackwardMap
2001  template <typename Graph>
2002  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
2003    return BackwardMap<Graph>(graph);
2004  }
2005
2006  /// \brief Potential difference map
2007  ///
2008  /// If there is an potential map on the nodes then we
2009  /// can get an arc map as we get the substraction of the
2010  /// values of the target and source.
2011  template <typename Digraph, typename NodeMap>
2012  class PotentialDifferenceMap {
2013  public:
2014    typedef typename Digraph::Arc Key;
2015    typedef typename NodeMap::Value Value;
2016
2017    /// \brief Constructor
2018    ///
2019    /// Contructor of the map
2020    explicit PotentialDifferenceMap(const Digraph& digraph,
2021                                    const NodeMap& potential)
2022      : _digraph(digraph), _potential(potential) {}
2023
2024    /// \brief Const subscription operator
2025    ///
2026    /// Const subscription operator
2027    Value operator[](const Key& arc) const {
2028      return _potential[_digraph.target(arc)] -
2029        _potential[_digraph.source(arc)];
2030    }
2031
2032  private:
2033    const Digraph& _digraph;
2034    const NodeMap& _potential;
2035  };
2036
2037  /// \brief Returns a PotentialDifferenceMap.
2038  ///
2039  /// This function just returns a PotentialDifferenceMap.
2040  /// \relates PotentialDifferenceMap
2041  template <typename Digraph, typename NodeMap>
2042  PotentialDifferenceMap<Digraph, NodeMap>
2043  potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
2044    return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
2045  }
2046
2047  /// \brief Map of the node in-degrees.
2048  ///
2049  /// This map returns the in-degree of a node. Once it is constructed,
2050  /// the degrees are stored in a standard NodeMap, so each query is done
2051  /// in constant time. On the other hand, the values are updated automatically
2052  /// whenever the digraph changes.
2053  ///
2054  /// \warning Besides addNode() and addArc(), a digraph structure may provide
2055  /// alternative ways to modify the digraph. The correct behavior of InDegMap
2056  /// is not guarantied if these additional features are used. For example
2057  /// the functions \ref ListDigraph::changeSource() "changeSource()",
2058  /// \ref ListDigraph::changeTarget() "changeTarget()" and
2059  /// \ref ListDigraph::reverseArc() "reverseArc()"
2060  /// of \ref ListDigraph will \e not update the degree values correctly.
2061  ///
2062  /// \sa OutDegMap
2063
2064  template <typename _Digraph>
2065  class InDegMap
2066    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
2067      ::ItemNotifier::ObserverBase {
2068
2069  public:
2070
2071    typedef _Digraph Digraph;
2072    typedef int Value;
2073    typedef typename Digraph::Node Key;
2074
2075    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
2076    ::ItemNotifier::ObserverBase Parent;
2077
2078  private:
2079
2080    class AutoNodeMap
2081      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
2082    public:
2083
2084      typedef typename ItemSetTraits<Digraph, Key>::
2085      template Map<int>::Type Parent;
2086
2087      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
2088
2089      virtual void add(const Key& key) {
2090        Parent::add(key);
2091        Parent::set(key, 0);
2092      }
2093
2094      virtual void add(const std::vector<Key>& keys) {
2095        Parent::add(keys);
2096        for (int i = 0; i < int(keys.size()); ++i) {
2097          Parent::set(keys[i], 0);
2098        }
2099      }
2100
2101      virtual void build() {
2102        Parent::build();
2103        Key it;
2104        typename Parent::Notifier* nf = Parent::notifier();
2105        for (nf->first(it); it != INVALID; nf->next(it)) {
2106          Parent::set(it, 0);
2107        }
2108      }
2109    };
2110
2111  public:
2112
2113    /// \brief Constructor.
2114    ///
2115    /// Constructor for creating in-degree map.
2116    explicit InDegMap(const Digraph& digraph)
2117      : _digraph(digraph), _deg(digraph) {
2118      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
2119
2120      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2121        _deg[it] = countInArcs(_digraph, it);
2122      }
2123    }
2124
2125    /// Gives back the in-degree of a Node.
2126    int operator[](const Key& key) const {
2127      return _deg[key];
2128    }
2129
2130  protected:
2131
2132    typedef typename Digraph::Arc Arc;
2133
2134    virtual void add(const Arc& arc) {
2135      ++_deg[_digraph.target(arc)];
2136    }
2137
2138    virtual void add(const std::vector<Arc>& arcs) {
2139      for (int i = 0; i < int(arcs.size()); ++i) {
2140        ++_deg[_digraph.target(arcs[i])];
2141      }
2142    }
2143
2144    virtual void erase(const Arc& arc) {
2145      --_deg[_digraph.target(arc)];
2146    }
2147
2148    virtual void erase(const std::vector<Arc>& arcs) {
2149      for (int i = 0; i < int(arcs.size()); ++i) {
2150        --_deg[_digraph.target(arcs[i])];
2151      }
2152    }
2153
2154    virtual void build() {
2155      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2156        _deg[it] = countInArcs(_digraph, it);
2157      }
2158    }
2159
2160    virtual void clear() {
2161      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2162        _deg[it] = 0;
2163      }
2164    }
2165  private:
2166
2167    const Digraph& _digraph;
2168    AutoNodeMap _deg;
2169  };
2170
2171  /// \brief Map of the node out-degrees.
2172  ///
2173  /// This map returns the out-degree of a node. Once it is constructed,
2174  /// the degrees are stored in a standard NodeMap, so each query is done
2175  /// in constant time. On the other hand, the values are updated automatically
2176  /// whenever the digraph changes.
2177  ///
2178  /// \warning Besides addNode() and addArc(), a digraph structure may provide
2179  /// alternative ways to modify the digraph. The correct behavior of OutDegMap
2180  /// is not guarantied if these additional features are used. For example
2181  /// the functions \ref ListDigraph::changeSource() "changeSource()",
2182  /// \ref ListDigraph::changeTarget() "changeTarget()" and
2183  /// \ref ListDigraph::reverseArc() "reverseArc()"
2184  /// of \ref ListDigraph will \e not update the degree values correctly.
2185  ///
2186  /// \sa InDegMap
2187
2188  template <typename _Digraph>
2189  class OutDegMap
2190    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
2191      ::ItemNotifier::ObserverBase {
2192
2193  public:
2194
2195    typedef _Digraph Digraph;
2196    typedef int Value;
2197    typedef typename Digraph::Node Key;
2198
2199    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
2200    ::ItemNotifier::ObserverBase Parent;
2201
2202  private:
2203
2204    class AutoNodeMap
2205      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
2206    public:
2207
2208      typedef typename ItemSetTraits<Digraph, Key>::
2209      template Map<int>::Type Parent;
2210
2211      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
2212
2213      virtual void add(const Key& key) {
2214        Parent::add(key);
2215        Parent::set(key, 0);
2216      }
2217      virtual void add(const std::vector<Key>& keys) {
2218        Parent::add(keys);
2219        for (int i = 0; i < int(keys.size()); ++i) {
2220          Parent::set(keys[i], 0);
2221        }
2222      }
2223      virtual void build() {
2224        Parent::build();
2225        Key it;
2226        typename Parent::Notifier* nf = Parent::notifier();
2227        for (nf->first(it); it != INVALID; nf->next(it)) {
2228          Parent::set(it, 0);
2229        }
2230      }
2231    };
2232
2233  public:
2234
2235    /// \brief Constructor.
2236    ///
2237    /// Constructor for creating out-degree map.
2238    explicit OutDegMap(const Digraph& digraph)
2239      : _digraph(digraph), _deg(digraph) {
2240      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
2241
2242      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2243        _deg[it] = countOutArcs(_digraph, it);
2244      }
2245    }
2246
2247    /// Gives back the out-degree of a Node.
2248    int operator[](const Key& key) const {
2249      return _deg[key];
2250    }
2251
2252  protected:
2253
2254    typedef typename Digraph::Arc Arc;
2255
2256    virtual void add(const Arc& arc) {
2257      ++_deg[_digraph.source(arc)];
2258    }
2259
2260    virtual void add(const std::vector<Arc>& arcs) {
2261      for (int i = 0; i < int(arcs.size()); ++i) {
2262        ++_deg[_digraph.source(arcs[i])];
2263      }
2264    }
2265
2266    virtual void erase(const Arc& arc) {
2267      --_deg[_digraph.source(arc)];
2268    }
2269
2270    virtual void erase(const std::vector<Arc>& arcs) {
2271      for (int i = 0; i < int(arcs.size()); ++i) {
2272        --_deg[_digraph.source(arcs[i])];
2273      }
2274    }
2275
2276    virtual void build() {
2277      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2278        _deg[it] = countOutArcs(_digraph, it);
2279      }
2280    }
2281
2282    virtual void clear() {
2283      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2284        _deg[it] = 0;
2285      }
2286    }
2287  private:
2288
2289    const Digraph& _digraph;
2290    AutoNodeMap _deg;
2291  };
2292
2293  /// @}
2294}
2295
2296#endif // LEMON_MAPS_H
Note: See TracBrowser for help on using the repository browser.