COIN-OR::LEMON - Graph Library

source: lemon/lemon/maps.h @ 230:af4e8ba94294

Last change on this file since 230:af4e8ba94294 was 220:a5d8c039f218, checked in by Balazs Dezso <deba@…>, 16 years ago

Reorganize header files (Ticket #97)

In addition on some places the DefaultMap?<G, K, V> is replaced with
ItemSetTraits?<G, K>::template Map<V>::Type, to decrease the dependencies
of different tools. It is obviously better solution.

File size: 77.9 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  ///
488  /// \todo Check the requirements.
489  template <typename M1, typename M2>
490  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
491    const M1 &_m1;
492    const M2 &_m2;
493  public:
494    typedef MapBase<typename M2::Key, typename M1::Value> Parent;
495    typedef typename Parent::Key Key;
496    typedef typename Parent::Value Value;
497
498    /// Constructor
499    ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
500
501    /// \e
502    typename MapTraits<M1>::ConstReturnValue
503    operator[](const Key &k) const { return _m1[_m2[k]]; }
504  };
505
506  /// Returns a \ref ComposeMap class
507
508  /// This function just returns a \ref ComposeMap class.
509  ///
510  /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
511  /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
512  /// will be equal to <tt>m1[m2[x]]</tt>.
513  ///
514  /// \relates ComposeMap
515  template <typename M1, typename M2>
516  inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) {
517    return ComposeMap<M1, M2>(m1, m2);
518  }
519
520
521  /// Combination of two maps using an STL (binary) functor.
522
523  /// This \ref concepts::ReadMap "read-only map" takes two maps and a
524  /// binary functor and returns the combination of the two given maps
525  /// using the functor.
526  /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2
527  /// and \c f is of \c F, then for
528  /// \code
529  ///   CombineMap<M1,M2,F,V> cm(m1,m2,f);
530  /// \endcode
531  /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>.
532  ///
533  /// The \c Key type of the map is inherited from \c M1 (\c M1::Key
534  /// must be convertible to \c M2::Key) and the \c Value type is \c V.
535  /// \c M2::Value and \c M1::Value must be convertible to the
536  /// corresponding input parameter of \c F and the return type of \c F
537  /// must be convertible to \c V.
538  ///
539  /// The simplest way of using this map is through the combineMap()
540  /// function.
541  ///
542  /// \sa ComposeMap
543  ///
544  /// \todo Check the requirements.
545  template<typename M1, typename M2, typename F,
546           typename V = typename F::result_type>
547  class CombineMap : public MapBase<typename M1::Key, V> {
548    const M1 &_m1;
549    const M2 &_m2;
550    F _f;
551  public:
552    typedef MapBase<typename M1::Key, V> Parent;
553    typedef typename Parent::Key Key;
554    typedef typename Parent::Value Value;
555
556    /// Constructor
557    CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
558      : _m1(m1), _m2(m2), _f(f) {}
559    /// \e
560    Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
561  };
562
563  /// Returns a \ref CombineMap class
564
565  /// This function just returns a \ref CombineMap class.
566  ///
567  /// For example, if \c m1 and \c m2 are both maps with \c double
568  /// values, then
569  /// \code
570  ///   combineMap(m1,m2,std::plus<double>())
571  /// \endcode
572  /// is equivalent to
573  /// \code
574  ///   addMap(m1,m2)
575  /// \endcode
576  ///
577  /// This function is specialized for adaptable binary function
578  /// classes and C++ functions.
579  ///
580  /// \relates CombineMap
581  template<typename M1, typename M2, typename F, typename V>
582  inline CombineMap<M1, M2, F, V>
583  combineMap(const M1 &m1, const M2 &m2, const F &f) {
584    return CombineMap<M1, M2, F, V>(m1,m2,f);
585  }
586
587  template<typename M1, typename M2, typename F>
588  inline CombineMap<M1, M2, F, typename F::result_type>
589  combineMap(const M1 &m1, const M2 &m2, const F &f) {
590    return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
591  }
592
593  template<typename M1, typename M2, typename K1, typename K2, typename V>
594  inline CombineMap<M1, M2, V (*)(K1, K2), V>
595  combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
596    return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
597  }
598
599
600  /// Converts an STL style (unary) functor to a map
601
602  /// This \ref concepts::ReadMap "read-only map" returns the value
603  /// of a given functor. Actually, it just wraps the functor and
604  /// provides the \c Key and \c Value typedefs.
605  ///
606  /// Template parameters \c K and \c V will become its \c Key and
607  /// \c Value. In most cases they have to be given explicitly because
608  /// a functor typically does not provide \c argument_type and
609  /// \c result_type typedefs.
610  /// Parameter \c F is the type of the used functor.
611  ///
612  /// The simplest way of using this map is through the functorToMap()
613  /// function.
614  ///
615  /// \sa MapToFunctor
616  template<typename F,
617           typename K = typename F::argument_type,
618           typename V = typename F::result_type>
619  class FunctorToMap : public MapBase<K, V> {
620    F _f;
621  public:
622    typedef MapBase<K, V> Parent;
623    typedef typename Parent::Key Key;
624    typedef typename Parent::Value Value;
625
626    /// Constructor
627    FunctorToMap(const F &f = F()) : _f(f) {}
628    /// \e
629    Value operator[](const Key &k) const { return _f(k); }
630  };
631
632  /// Returns a \ref FunctorToMap class
633
634  /// This function just returns a \ref FunctorToMap class.
635  ///
636  /// This function is specialized for adaptable binary function
637  /// classes and C++ functions.
638  ///
639  /// \relates FunctorToMap
640  template<typename K, typename V, typename F>
641  inline FunctorToMap<F, K, V> functorToMap(const F &f) {
642    return FunctorToMap<F, K, V>(f);
643  }
644
645  template <typename F>
646  inline FunctorToMap<F, typename F::argument_type, typename F::result_type>
647    functorToMap(const F &f)
648  {
649    return FunctorToMap<F, typename F::argument_type,
650      typename F::result_type>(f);
651  }
652
653  template <typename K, typename V>
654  inline FunctorToMap<V (*)(K), K, V> functorToMap(V (*f)(K)) {
655    return FunctorToMap<V (*)(K), K, V>(f);
656  }
657
658
659  /// Converts a map to an STL style (unary) functor
660
661  /// This class converts a map to an STL style (unary) functor.
662  /// That is it provides an <tt>operator()</tt> to read its values.
663  ///
664  /// For the sake of convenience it also works as a usual
665  /// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt>
666  /// and the \c Key and \c Value typedefs also exist.
667  ///
668  /// The simplest way of using this map is through the mapToFunctor()
669  /// function.
670  ///
671  ///\sa FunctorToMap
672  template <typename M>
673  class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
674    const M &_m;
675  public:
676    typedef MapBase<typename M::Key, typename M::Value> Parent;
677    typedef typename Parent::Key Key;
678    typedef typename Parent::Value Value;
679
680    typedef typename Parent::Key argument_type;
681    typedef typename Parent::Value result_type;
682
683    /// Constructor
684    MapToFunctor(const M &m) : _m(m) {}
685    /// \e
686    Value operator()(const Key &k) const { return _m[k]; }
687    /// \e
688    Value operator[](const Key &k) const { return _m[k]; }
689  };
690
691  /// Returns a \ref MapToFunctor class
692
693  /// This function just returns a \ref MapToFunctor class.
694  /// \relates MapToFunctor
695  template<typename M>
696  inline MapToFunctor<M> mapToFunctor(const M &m) {
697    return MapToFunctor<M>(m);
698  }
699
700
701  /// \brief Map adaptor to convert the \c Value type of a map to
702  /// another type using the default conversion.
703
704  /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap
705  /// "readable map" to another type using the default conversion.
706  /// The \c Key type of it is inherited from \c M and the \c Value
707  /// type is \c V.
708  /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
709  ///
710  /// The simplest way of using this map is through the convertMap()
711  /// function.
712  template <typename M, typename V>
713  class ConvertMap : public MapBase<typename M::Key, V> {
714    const M &_m;
715  public:
716    typedef MapBase<typename M::Key, V> Parent;
717    typedef typename Parent::Key Key;
718    typedef typename Parent::Value Value;
719
720    /// Constructor
721
722    /// Constructor.
723    /// \param m The underlying map.
724    ConvertMap(const M &m) : _m(m) {}
725
726    /// \e
727    Value operator[](const Key &k) const { return _m[k]; }
728  };
729
730  /// Returns a \ref ConvertMap class
731
732  /// This function just returns a \ref ConvertMap class.
733  /// \relates ConvertMap
734  template<typename V, typename M>
735  inline ConvertMap<M, V> convertMap(const M &map) {
736    return ConvertMap<M, V>(map);
737  }
738
739
740  /// Applies all map setting operations to two maps
741
742  /// This map has two \ref concepts::WriteMap "writable map" parameters
743  /// and each write request will be passed to both of them.
744  /// If \c M1 is also \ref concepts::ReadMap "readable", then the read
745  /// operations will return the corresponding values of \c M1.
746  ///
747  /// The \c Key and \c Value types are inherited from \c M1.
748  /// The \c Key and \c Value of \c M2 must be convertible from those
749  /// of \c M1.
750  ///
751  /// The simplest way of using this map is through the forkMap()
752  /// function.
753  template<typename  M1, typename M2>
754  class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
755    M1 &_m1;
756    M2 &_m2;
757  public:
758    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
759    typedef typename Parent::Key Key;
760    typedef typename Parent::Value Value;
761
762    /// Constructor
763    ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
764    /// Returns the value associated with the given key in the first map.
765    Value operator[](const Key &k) const { return _m1[k]; }
766    /// Sets the value associated with the given key in both maps.
767    void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); }
768  };
769
770  /// Returns a \ref ForkMap class
771
772  /// This function just returns a \ref ForkMap class.
773  /// \relates ForkMap
774  template <typename M1, typename M2>
775  inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) {
776    return ForkMap<M1,M2>(m1,m2);
777  }
778
779
780  /// Sum of two maps
781
782  /// This \ref concepts::ReadMap "read-only map" returns the sum
783  /// of the values of the two given maps.
784  /// Its \c Key and \c Value types are inherited from \c M1.
785  /// The \c Key and \c Value of \c M2 must be convertible to those of
786  /// \c M1.
787  ///
788  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
789  /// \code
790  ///   AddMap<M1,M2> am(m1,m2);
791  /// \endcode
792  /// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>.
793  ///
794  /// The simplest way of using this map is through the addMap()
795  /// function.
796  ///
797  /// \sa SubMap, MulMap, DivMap
798  /// \sa ShiftMap, ShiftWriteMap
799  template<typename M1, typename M2>
800  class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
801    const M1 &_m1;
802    const M2 &_m2;
803  public:
804    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
805    typedef typename Parent::Key Key;
806    typedef typename Parent::Value Value;
807
808    /// Constructor
809    AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
810    /// \e
811    Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
812  };
813
814  /// Returns an \ref AddMap class
815
816  /// This function just returns an \ref AddMap class.
817  ///
818  /// For example, if \c m1 and \c m2 are both maps with \c double
819  /// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to
820  /// <tt>m1[x]+m2[x]</tt>.
821  ///
822  /// \relates AddMap
823  template<typename M1, typename M2>
824  inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) {
825    return AddMap<M1, M2>(m1,m2);
826  }
827
828
829  /// Difference of two maps
830
831  /// This \ref concepts::ReadMap "read-only map" returns the difference
832  /// of the values of the two given maps.
833  /// Its \c Key and \c Value types are inherited from \c M1.
834  /// The \c Key and \c Value of \c M2 must be convertible to those of
835  /// \c M1.
836  ///
837  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
838  /// \code
839  ///   SubMap<M1,M2> sm(m1,m2);
840  /// \endcode
841  /// <tt>sm[x]</tt> will be equal to <tt>m1[x]-m2[x]</tt>.
842  ///
843  /// The simplest way of using this map is through the subMap()
844  /// function.
845  ///
846  /// \sa AddMap, MulMap, DivMap
847  template<typename M1, typename M2>
848  class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
849    const M1 &_m1;
850    const M2 &_m2;
851  public:
852    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
853    typedef typename Parent::Key Key;
854    typedef typename Parent::Value Value;
855
856    /// Constructor
857    SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
858    /// \e
859    Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
860  };
861
862  /// Returns a \ref SubMap class
863
864  /// This function just returns a \ref SubMap class.
865  ///
866  /// For example, if \c m1 and \c m2 are both maps with \c double
867  /// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to
868  /// <tt>m1[x]-m2[x]</tt>.
869  ///
870  /// \relates SubMap
871  template<typename M1, typename M2>
872  inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
873    return SubMap<M1, M2>(m1,m2);
874  }
875
876
877  /// Product of two maps
878
879  /// This \ref concepts::ReadMap "read-only map" returns the product
880  /// of the values of the two given maps.
881  /// Its \c Key and \c Value types are inherited from \c M1.
882  /// The \c Key and \c Value of \c M2 must be convertible to those of
883  /// \c M1.
884  ///
885  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
886  /// \code
887  ///   MulMap<M1,M2> mm(m1,m2);
888  /// \endcode
889  /// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>.
890  ///
891  /// The simplest way of using this map is through the mulMap()
892  /// function.
893  ///
894  /// \sa AddMap, SubMap, DivMap
895  /// \sa ScaleMap, ScaleWriteMap
896  template<typename M1, typename M2>
897  class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
898    const M1 &_m1;
899    const M2 &_m2;
900  public:
901    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
902    typedef typename Parent::Key Key;
903    typedef typename Parent::Value Value;
904
905    /// Constructor
906    MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
907    /// \e
908    Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
909  };
910
911  /// Returns a \ref MulMap class
912
913  /// This function just returns a \ref MulMap class.
914  ///
915  /// For example, if \c m1 and \c m2 are both maps with \c double
916  /// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to
917  /// <tt>m1[x]*m2[x]</tt>.
918  ///
919  /// \relates MulMap
920  template<typename M1, typename M2>
921  inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
922    return MulMap<M1, M2>(m1,m2);
923  }
924
925
926  /// Quotient of two maps
927
928  /// This \ref concepts::ReadMap "read-only map" returns the quotient
929  /// of the values of the two given maps.
930  /// Its \c Key and \c Value types are inherited from \c M1.
931  /// The \c Key and \c Value of \c M2 must be convertible to those of
932  /// \c M1.
933  ///
934  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
935  /// \code
936  ///   DivMap<M1,M2> dm(m1,m2);
937  /// \endcode
938  /// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>.
939  ///
940  /// The simplest way of using this map is through the divMap()
941  /// function.
942  ///
943  /// \sa AddMap, SubMap, MulMap
944  template<typename M1, typename M2>
945  class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
946    const M1 &_m1;
947    const M2 &_m2;
948  public:
949    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
950    typedef typename Parent::Key Key;
951    typedef typename Parent::Value Value;
952
953    /// Constructor
954    DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
955    /// \e
956    Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
957  };
958
959  /// Returns a \ref DivMap class
960
961  /// This function just returns a \ref DivMap class.
962  ///
963  /// For example, if \c m1 and \c m2 are both maps with \c double
964  /// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to
965  /// <tt>m1[x]/m2[x]</tt>.
966  ///
967  /// \relates DivMap
968  template<typename M1, typename M2>
969  inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
970    return DivMap<M1, M2>(m1,m2);
971  }
972
973
974  /// Shifts a map with a constant.
975
976  /// This \ref concepts::ReadMap "read-only map" returns the sum of
977  /// the given map and a constant value (i.e. it shifts the map with
978  /// the constant). Its \c Key and \c Value are inherited from \c M.
979  ///
980  /// Actually,
981  /// \code
982  ///   ShiftMap<M> sh(m,v);
983  /// \endcode
984  /// is equivalent to
985  /// \code
986  ///   ConstMap<M::Key, M::Value> cm(v);
987  ///   AddMap<M, ConstMap<M::Key, M::Value> > sh(m,cm);
988  /// \endcode
989  ///
990  /// The simplest way of using this map is through the shiftMap()
991  /// function.
992  ///
993  /// \sa ShiftWriteMap
994  template<typename M, typename C = typename M::Value>
995  class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
996    const M &_m;
997    C _v;
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
1005    /// Constructor.
1006    /// \param m The undelying map.
1007    /// \param v The constant value.
1008    ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
1009    /// \e
1010    Value operator[](const Key &k) const { return _m[k]+_v; }
1011  };
1012
1013  /// Shifts a map with a constant (read-write version).
1014
1015  /// This \ref concepts::ReadWriteMap "read-write map" returns the sum
1016  /// of the given map and a constant value (i.e. it shifts the map with
1017  /// the constant). Its \c Key and \c Value are inherited from \c M.
1018  /// It makes also possible to write the map.
1019  ///
1020  /// The simplest way of using this map is through the shiftWriteMap()
1021  /// function.
1022  ///
1023  /// \sa ShiftMap
1024  template<typename M, typename C = typename M::Value>
1025  class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
1026    M &_m;
1027    C _v;
1028  public:
1029    typedef MapBase<typename M::Key, typename M::Value> Parent;
1030    typedef typename Parent::Key Key;
1031    typedef typename Parent::Value Value;
1032
1033    /// Constructor
1034
1035    /// Constructor.
1036    /// \param m The undelying map.
1037    /// \param v The constant value.
1038    ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
1039    /// \e
1040    Value operator[](const Key &k) const { return _m[k]+_v; }
1041    /// \e
1042    void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
1043  };
1044
1045  /// Returns a \ref ShiftMap class
1046
1047  /// This function just returns a \ref ShiftMap class.
1048  ///
1049  /// For example, if \c m is a map with \c double values and \c v is
1050  /// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to
1051  /// <tt>m[x]+v</tt>.
1052  ///
1053  /// \relates ShiftMap
1054  template<typename M, typename C>
1055  inline ShiftMap<M, C> shiftMap(const M &m, const C &v) {
1056    return ShiftMap<M, C>(m,v);
1057  }
1058
1059  /// Returns a \ref ShiftWriteMap class
1060
1061  /// This function just returns a \ref ShiftWriteMap class.
1062  ///
1063  /// For example, if \c m is a map with \c double values and \c v is
1064  /// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to
1065  /// <tt>m[x]+v</tt>.
1066  /// Moreover it makes also possible to write the map.
1067  ///
1068  /// \relates ShiftWriteMap
1069  template<typename M, typename C>
1070  inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) {
1071    return ShiftWriteMap<M, C>(m,v);
1072  }
1073
1074
1075  /// Scales a map with a constant.
1076
1077  /// This \ref concepts::ReadMap "read-only map" returns the value of
1078  /// the given map multiplied from the left side with a constant value.
1079  /// Its \c Key and \c Value are inherited from \c M.
1080  ///
1081  /// Actually,
1082  /// \code
1083  ///   ScaleMap<M> sc(m,v);
1084  /// \endcode
1085  /// is equivalent to
1086  /// \code
1087  ///   ConstMap<M::Key, M::Value> cm(v);
1088  ///   MulMap<ConstMap<M::Key, M::Value>, M> sc(cm,m);
1089  /// \endcode
1090  ///
1091  /// The simplest way of using this map is through the scaleMap()
1092  /// function.
1093  ///
1094  /// \sa ScaleWriteMap
1095  template<typename M, typename C = typename M::Value>
1096  class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
1097    const M &_m;
1098    C _v;
1099  public:
1100    typedef MapBase<typename M::Key, typename M::Value> Parent;
1101    typedef typename Parent::Key Key;
1102    typedef typename Parent::Value Value;
1103
1104    /// Constructor
1105
1106    /// Constructor.
1107    /// \param m The undelying map.
1108    /// \param v The constant value.
1109    ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
1110    /// \e
1111    Value operator[](const Key &k) const { return _v*_m[k]; }
1112  };
1113
1114  /// Scales a map with a constant (read-write version).
1115
1116  /// This \ref concepts::ReadWriteMap "read-write map" returns the value of
1117  /// the given map multiplied from the left side with a constant value.
1118  /// Its \c Key and \c Value are inherited from \c M.
1119  /// It can also be used as write map if the \c / operator is defined
1120  /// between \c Value and \c C and the given multiplier is not zero.
1121  ///
1122  /// The simplest way of using this map is through the scaleWriteMap()
1123  /// function.
1124  ///
1125  /// \sa ScaleMap
1126  template<typename M, typename C = typename M::Value>
1127  class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
1128    M &_m;
1129    C _v;
1130  public:
1131    typedef MapBase<typename M::Key, typename M::Value> Parent;
1132    typedef typename Parent::Key Key;
1133    typedef typename Parent::Value Value;
1134
1135    /// Constructor
1136
1137    /// Constructor.
1138    /// \param m The undelying map.
1139    /// \param v The constant value.
1140    ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
1141    /// \e
1142    Value operator[](const Key &k) const { return _v*_m[k]; }
1143    /// \e
1144    void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
1145  };
1146
1147  /// Returns a \ref ScaleMap class
1148
1149  /// This function just returns a \ref ScaleMap class.
1150  ///
1151  /// For example, if \c m is a map with \c double values and \c v is
1152  /// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to
1153  /// <tt>v*m[x]</tt>.
1154  ///
1155  /// \relates ScaleMap
1156  template<typename M, typename C>
1157  inline ScaleMap<M, C> scaleMap(const M &m, const C &v) {
1158    return ScaleMap<M, C>(m,v);
1159  }
1160
1161  /// Returns a \ref ScaleWriteMap class
1162
1163  /// This function just returns a \ref ScaleWriteMap class.
1164  ///
1165  /// For example, if \c m is a map with \c double values and \c v is
1166  /// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to
1167  /// <tt>v*m[x]</tt>.
1168  /// Moreover it makes also possible to write the map.
1169  ///
1170  /// \relates ScaleWriteMap
1171  template<typename M, typename C>
1172  inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) {
1173    return ScaleWriteMap<M, C>(m,v);
1174  }
1175
1176
1177  /// Negative of a map
1178
1179  /// This \ref concepts::ReadMap "read-only map" returns the negative
1180  /// of the values of the given map (using the unary \c - operator).
1181  /// Its \c Key and \c Value are inherited from \c M.
1182  ///
1183  /// If M::Value is \c int, \c double etc., then
1184  /// \code
1185  ///   NegMap<M> neg(m);
1186  /// \endcode
1187  /// is equivalent to
1188  /// \code
1189  ///   ScaleMap<M> neg(m,-1);
1190  /// \endcode
1191  ///
1192  /// The simplest way of using this map is through the negMap()
1193  /// function.
1194  ///
1195  /// \sa NegWriteMap
1196  template<typename M>
1197  class NegMap : public MapBase<typename M::Key, typename M::Value> {
1198    const M& _m;
1199  public:
1200    typedef MapBase<typename M::Key, typename M::Value> Parent;
1201    typedef typename Parent::Key Key;
1202    typedef typename Parent::Value Value;
1203
1204    /// Constructor
1205    NegMap(const M &m) : _m(m) {}
1206    /// \e
1207    Value operator[](const Key &k) const { return -_m[k]; }
1208  };
1209
1210  /// Negative of a map (read-write version)
1211
1212  /// This \ref concepts::ReadWriteMap "read-write map" returns the
1213  /// negative of the values of the given map (using the unary \c -
1214  /// operator).
1215  /// Its \c Key and \c Value are inherited from \c M.
1216  /// It makes also possible to write the map.
1217  ///
1218  /// If M::Value is \c int, \c double etc., then
1219  /// \code
1220  ///   NegWriteMap<M> neg(m);
1221  /// \endcode
1222  /// is equivalent to
1223  /// \code
1224  ///   ScaleWriteMap<M> neg(m,-1);
1225  /// \endcode
1226  ///
1227  /// The simplest way of using this map is through the negWriteMap()
1228  /// function.
1229  ///
1230  /// \sa NegMap
1231  template<typename M>
1232  class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
1233    M &_m;
1234  public:
1235    typedef MapBase<typename M::Key, typename M::Value> Parent;
1236    typedef typename Parent::Key Key;
1237    typedef typename Parent::Value Value;
1238
1239    /// Constructor
1240    NegWriteMap(M &m) : _m(m) {}
1241    /// \e
1242    Value operator[](const Key &k) const { return -_m[k]; }
1243    /// \e
1244    void set(const Key &k, const Value &v) { _m.set(k, -v); }
1245  };
1246
1247  /// Returns a \ref NegMap class
1248
1249  /// This function just returns a \ref NegMap class.
1250  ///
1251  /// For example, if \c m is a map with \c double values, then
1252  /// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
1253  ///
1254  /// \relates NegMap
1255  template <typename M>
1256  inline NegMap<M> negMap(const M &m) {
1257    return NegMap<M>(m);
1258  }
1259
1260  /// Returns a \ref NegWriteMap class
1261
1262  /// This function just returns a \ref NegWriteMap class.
1263  ///
1264  /// For example, if \c m is a map with \c double values, then
1265  /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
1266  /// Moreover it makes also possible to write the map.
1267  ///
1268  /// \relates NegWriteMap
1269  template <typename M>
1270  inline NegWriteMap<M> negWriteMap(M &m) {
1271    return NegWriteMap<M>(m);
1272  }
1273
1274
1275  /// Absolute value of a map
1276
1277  /// This \ref concepts::ReadMap "read-only map" returns the absolute
1278  /// value of the values of the given map.
1279  /// Its \c Key and \c Value are inherited from \c M.
1280  /// \c Value must be comparable to \c 0 and the unary \c -
1281  /// operator must be defined for it, of course.
1282  ///
1283  /// The simplest way of using this map is through the absMap()
1284  /// function.
1285  template<typename M>
1286  class AbsMap : public MapBase<typename M::Key, typename M::Value> {
1287    const M &_m;
1288  public:
1289    typedef MapBase<typename M::Key, typename M::Value> Parent;
1290    typedef typename Parent::Key Key;
1291    typedef typename Parent::Value Value;
1292
1293    /// Constructor
1294    AbsMap(const M &m) : _m(m) {}
1295    /// \e
1296    Value operator[](const Key &k) const {
1297      Value tmp = _m[k];
1298      return tmp >= 0 ? tmp : -tmp;
1299    }
1300
1301  };
1302
1303  /// Returns an \ref AbsMap class
1304
1305  /// This function just returns an \ref AbsMap class.
1306  ///
1307  /// For example, if \c m is a map with \c double values, then
1308  /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if
1309  /// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is
1310  /// negative.
1311  ///
1312  /// \relates AbsMap
1313  template<typename M>
1314  inline AbsMap<M> absMap(const M &m) {
1315    return AbsMap<M>(m);
1316  }
1317
1318  /// @}
1319
1320  // Logical maps and map adaptors:
1321
1322  /// \addtogroup maps
1323  /// @{
1324
1325  /// Constant \c true map.
1326
1327  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1328  /// each key.
1329  ///
1330  /// Note that
1331  /// \code
1332  ///   TrueMap<K> tm;
1333  /// \endcode
1334  /// is equivalent to
1335  /// \code
1336  ///   ConstMap<K,bool> tm(true);
1337  /// \endcode
1338  ///
1339  /// \sa FalseMap
1340  /// \sa ConstMap
1341  template <typename K>
1342  class TrueMap : public MapBase<K, bool> {
1343  public:
1344    typedef MapBase<K, bool> Parent;
1345    typedef typename Parent::Key Key;
1346    typedef typename Parent::Value Value;
1347
1348    /// Gives back \c true.
1349    Value operator[](const Key&) const { return true; }
1350  };
1351
1352  /// Returns a \ref TrueMap class
1353
1354  /// This function just returns a \ref TrueMap class.
1355  /// \relates TrueMap
1356  template<typename K>
1357  inline TrueMap<K> trueMap() {
1358    return TrueMap<K>();
1359  }
1360
1361
1362  /// Constant \c false map.
1363
1364  /// This \ref concepts::ReadMap "read-only map" assigns \c false to
1365  /// each key.
1366  ///
1367  /// Note that
1368  /// \code
1369  ///   FalseMap<K> fm;
1370  /// \endcode
1371  /// is equivalent to
1372  /// \code
1373  ///   ConstMap<K,bool> fm(false);
1374  /// \endcode
1375  ///
1376  /// \sa TrueMap
1377  /// \sa ConstMap
1378  template <typename K>
1379  class FalseMap : public MapBase<K, bool> {
1380  public:
1381    typedef MapBase<K, bool> Parent;
1382    typedef typename Parent::Key Key;
1383    typedef typename Parent::Value Value;
1384
1385    /// Gives back \c false.
1386    Value operator[](const Key&) const { return false; }
1387  };
1388
1389  /// Returns a \ref FalseMap class
1390
1391  /// This function just returns a \ref FalseMap class.
1392  /// \relates FalseMap
1393  template<typename K>
1394  inline FalseMap<K> falseMap() {
1395    return FalseMap<K>();
1396  }
1397
1398  /// @}
1399
1400  /// \addtogroup map_adaptors
1401  /// @{
1402
1403  /// Logical 'and' of two maps
1404
1405  /// This \ref concepts::ReadMap "read-only map" returns the logical
1406  /// 'and' of the values of the two given maps.
1407  /// Its \c Key type is inherited from \c M1 and its \c Value type is
1408  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1409  ///
1410  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1411  /// \code
1412  ///   AndMap<M1,M2> am(m1,m2);
1413  /// \endcode
1414  /// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>.
1415  ///
1416  /// The simplest way of using this map is through the andMap()
1417  /// function.
1418  ///
1419  /// \sa OrMap
1420  /// \sa NotMap, NotWriteMap
1421  template<typename M1, typename M2>
1422  class AndMap : public MapBase<typename M1::Key, bool> {
1423    const M1 &_m1;
1424    const M2 &_m2;
1425  public:
1426    typedef MapBase<typename M1::Key, bool> Parent;
1427    typedef typename Parent::Key Key;
1428    typedef typename Parent::Value Value;
1429
1430    /// Constructor
1431    AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1432    /// \e
1433    Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
1434  };
1435
1436  /// Returns an \ref AndMap class
1437
1438  /// This function just returns an \ref AndMap class.
1439  ///
1440  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
1441  /// then <tt>andMap(m1,m2)[x]</tt> will be equal to
1442  /// <tt>m1[x]&&m2[x]</tt>.
1443  ///
1444  /// \relates AndMap
1445  template<typename M1, typename M2>
1446  inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) {
1447    return AndMap<M1, M2>(m1,m2);
1448  }
1449
1450
1451  /// Logical 'or' of two maps
1452
1453  /// This \ref concepts::ReadMap "read-only map" returns the logical
1454  /// 'or' of the values of the two given maps.
1455  /// Its \c Key type is inherited from \c M1 and its \c Value type is
1456  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1457  ///
1458  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1459  /// \code
1460  ///   OrMap<M1,M2> om(m1,m2);
1461  /// \endcode
1462  /// <tt>om[x]</tt> will be equal to <tt>m1[x]||m2[x]</tt>.
1463  ///
1464  /// The simplest way of using this map is through the orMap()
1465  /// function.
1466  ///
1467  /// \sa AndMap
1468  /// \sa NotMap, NotWriteMap
1469  template<typename M1, typename M2>
1470  class OrMap : public MapBase<typename M1::Key, bool> {
1471    const M1 &_m1;
1472    const M2 &_m2;
1473  public:
1474    typedef MapBase<typename M1::Key, bool> Parent;
1475    typedef typename Parent::Key Key;
1476    typedef typename Parent::Value Value;
1477
1478    /// Constructor
1479    OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1480    /// \e
1481    Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
1482  };
1483
1484  /// Returns an \ref OrMap class
1485
1486  /// This function just returns an \ref OrMap class.
1487  ///
1488  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
1489  /// then <tt>orMap(m1,m2)[x]</tt> will be equal to
1490  /// <tt>m1[x]||m2[x]</tt>.
1491  ///
1492  /// \relates OrMap
1493  template<typename M1, typename M2>
1494  inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) {
1495    return OrMap<M1, M2>(m1,m2);
1496  }
1497
1498
1499  /// Logical 'not' of a map
1500
1501  /// This \ref concepts::ReadMap "read-only map" returns the logical
1502  /// negation of the values of the given map.
1503  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
1504  ///
1505  /// The simplest way of using this map is through the notMap()
1506  /// function.
1507  ///
1508  /// \sa NotWriteMap
1509  template <typename M>
1510  class NotMap : public MapBase<typename M::Key, bool> {
1511    const M &_m;
1512  public:
1513    typedef MapBase<typename M::Key, bool> Parent;
1514    typedef typename Parent::Key Key;
1515    typedef typename Parent::Value Value;
1516
1517    /// Constructor
1518    NotMap(const M &m) : _m(m) {}
1519    /// \e
1520    Value operator[](const Key &k) const { return !_m[k]; }
1521  };
1522
1523  /// Logical 'not' of a map (read-write version)
1524
1525  /// This \ref concepts::ReadWriteMap "read-write map" returns the
1526  /// logical negation of the values of the given map.
1527  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
1528  /// It makes also possible to write the map. When a value is set,
1529  /// the opposite value is set to the original map.
1530  ///
1531  /// The simplest way of using this map is through the notWriteMap()
1532  /// function.
1533  ///
1534  /// \sa NotMap
1535  template <typename M>
1536  class NotWriteMap : public MapBase<typename M::Key, bool> {
1537    M &_m;
1538  public:
1539    typedef MapBase<typename M::Key, bool> Parent;
1540    typedef typename Parent::Key Key;
1541    typedef typename Parent::Value Value;
1542
1543    /// Constructor
1544    NotWriteMap(M &m) : _m(m) {}
1545    /// \e
1546    Value operator[](const Key &k) const { return !_m[k]; }
1547    /// \e
1548    void set(const Key &k, bool v) { _m.set(k, !v); }
1549  };
1550
1551  /// Returns a \ref NotMap class
1552
1553  /// This function just returns a \ref NotMap class.
1554  ///
1555  /// For example, if \c m is a map with \c bool values, then
1556  /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
1557  ///
1558  /// \relates NotMap
1559  template <typename M>
1560  inline NotMap<M> notMap(const M &m) {
1561    return NotMap<M>(m);
1562  }
1563
1564  /// Returns a \ref NotWriteMap class
1565
1566  /// This function just returns a \ref NotWriteMap class.
1567  ///
1568  /// For example, if \c m is a map with \c bool values, then
1569  /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
1570  /// Moreover it makes also possible to write the map.
1571  ///
1572  /// \relates NotWriteMap
1573  template <typename M>
1574  inline NotWriteMap<M> notWriteMap(M &m) {
1575    return NotWriteMap<M>(m);
1576  }
1577
1578
1579  /// Combination of two maps using the \c == operator
1580
1581  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1582  /// the keys for which the corresponding values of the two maps are
1583  /// equal.
1584  /// Its \c Key type is inherited from \c M1 and its \c Value type is
1585  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1586  ///
1587  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1588  /// \code
1589  ///   EqualMap<M1,M2> em(m1,m2);
1590  /// \endcode
1591  /// <tt>em[x]</tt> will be equal to <tt>m1[x]==m2[x]</tt>.
1592  ///
1593  /// The simplest way of using this map is through the equalMap()
1594  /// function.
1595  ///
1596  /// \sa LessMap
1597  template<typename M1, typename M2>
1598  class EqualMap : public MapBase<typename M1::Key, bool> {
1599    const M1 &_m1;
1600    const M2 &_m2;
1601  public:
1602    typedef MapBase<typename M1::Key, bool> Parent;
1603    typedef typename Parent::Key Key;
1604    typedef typename Parent::Value Value;
1605
1606    /// Constructor
1607    EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1608    /// \e
1609    Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
1610  };
1611
1612  /// Returns an \ref EqualMap class
1613
1614  /// This function just returns an \ref EqualMap class.
1615  ///
1616  /// For example, if \c m1 and \c m2 are maps with keys and values of
1617  /// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to
1618  /// <tt>m1[x]==m2[x]</tt>.
1619  ///
1620  /// \relates EqualMap
1621  template<typename M1, typename M2>
1622  inline EqualMap<M1, M2> equalMap(const M1 &m1, const M2 &m2) {
1623    return EqualMap<M1, M2>(m1,m2);
1624  }
1625
1626
1627  /// Combination of two maps using the \c < operator
1628
1629  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1630  /// the keys for which the corresponding value of the first map is
1631  /// less then the value of the second map.
1632  /// Its \c Key type is inherited from \c M1 and its \c Value type is
1633  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1634  ///
1635  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1636  /// \code
1637  ///   LessMap<M1,M2> lm(m1,m2);
1638  /// \endcode
1639  /// <tt>lm[x]</tt> will be equal to <tt>m1[x]<m2[x]</tt>.
1640  ///
1641  /// The simplest way of using this map is through the lessMap()
1642  /// function.
1643  ///
1644  /// \sa EqualMap
1645  template<typename M1, typename M2>
1646  class LessMap : public MapBase<typename M1::Key, bool> {
1647    const M1 &_m1;
1648    const M2 &_m2;
1649  public:
1650    typedef MapBase<typename M1::Key, bool> Parent;
1651    typedef typename Parent::Key Key;
1652    typedef typename Parent::Value Value;
1653
1654    /// Constructor
1655    LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1656    /// \e
1657    Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
1658  };
1659
1660  /// Returns an \ref LessMap class
1661
1662  /// This function just returns an \ref LessMap class.
1663  ///
1664  /// For example, if \c m1 and \c m2 are maps with keys and values of
1665  /// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to
1666  /// <tt>m1[x]<m2[x]</tt>.
1667  ///
1668  /// \relates LessMap
1669  template<typename M1, typename M2>
1670  inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) {
1671    return LessMap<M1, M2>(m1,m2);
1672  }
1673
1674  namespace _maps_bits {
1675
1676    template <typename _Iterator, typename Enable = void>
1677    struct IteratorTraits {
1678      typedef typename std::iterator_traits<_Iterator>::value_type Value;
1679    };
1680
1681    template <typename _Iterator>
1682    struct IteratorTraits<_Iterator,
1683      typename exists<typename _Iterator::container_type>::type>
1684    {
1685      typedef typename _Iterator::container_type::value_type Value;
1686    };
1687
1688  }
1689
1690  /// \brief Writable bool map for logging each \c true assigned element
1691  ///
1692  /// A \ref concepts::WriteMap "writable" bool map for logging
1693  /// each \c true assigned element, i.e it copies subsequently each
1694  /// keys set to \c true to the given iterator.
1695  /// The most important usage of it is storing certain nodes or arcs
1696  /// that were marked \c true by an algorithm.
1697  ///
1698  /// There are several algorithms that provide solutions through bool
1699  /// maps and most of them assign \c true at most once for each key.
1700  /// In these cases it is a natural request to store each \c true
1701  /// assigned elements (in order of the assignment), which can be
1702  /// easily done with LoggerBoolMap.
1703  ///
1704  /// The simplest way of using this map is through the loggerBoolMap()
1705  /// function.
1706  ///
1707  /// \tparam It The type of the iterator.
1708  /// \tparam Ke The key type of the map. The default value set
1709  /// according to the iterator type should work in most cases.
1710  ///
1711  /// \note The container of the iterator must contain enough space
1712  /// for the elements or the iterator should be an inserter iterator.
1713#ifdef DOXYGEN
1714  template <typename It, typename Ke>
1715#else
1716  template <typename It,
1717            typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
1718#endif
1719  class LoggerBoolMap {
1720  public:
1721    typedef It Iterator;
1722
1723    typedef Ke Key;
1724    typedef bool Value;
1725
1726    /// Constructor
1727    LoggerBoolMap(Iterator it)
1728      : _begin(it), _end(it) {}
1729
1730    /// Gives back the given iterator set for the first key
1731    Iterator begin() const {
1732      return _begin;
1733    }
1734
1735    /// Gives back the the 'after the last' iterator
1736    Iterator end() const {
1737      return _end;
1738    }
1739
1740    /// The set function of the map
1741    void set(const Key& key, Value value) {
1742      if (value) {
1743        *_end++ = key;
1744      }
1745    }
1746
1747  private:
1748    Iterator _begin;
1749    Iterator _end;
1750  };
1751
1752  /// Returns a \ref LoggerBoolMap class
1753
1754  /// This function just returns a \ref LoggerBoolMap class.
1755  ///
1756  /// The most important usage of it is storing certain nodes or arcs
1757  /// that were marked \c true by an algorithm.
1758  /// For example it makes easier to store the nodes in the processing
1759  /// order of Dfs algorithm, as the following examples show.
1760  /// \code
1761  ///   std::vector<Node> v;
1762  ///   dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
1763  /// \endcode
1764  /// \code
1765  ///   std::vector<Node> v(countNodes(g));
1766  ///   dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
1767  /// \endcode
1768  ///
1769  /// \note The container of the iterator must contain enough space
1770  /// for the elements or the iterator should be an inserter iterator.
1771  ///
1772  /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
1773  /// it cannot be used when a readable map is needed, for example as
1774  /// \c ReachedMap for \ref Bfs, \ref Dfs and \ref Dijkstra algorithms.
1775  ///
1776  /// \relates LoggerBoolMap
1777  template<typename Iterator>
1778  inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
1779    return LoggerBoolMap<Iterator>(it);
1780  }
1781
1782  /// Provides an immutable and unique id for each item in the graph.
1783
1784  /// The IdMap class provides a unique and immutable id for each item of the
1785  /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
1786  /// different items (nodes) get different ids <li>\b immutable: the id of an
1787  /// item (node) does not change (even if you delete other nodes).  </ul>
1788  /// Through this map you get access (i.e. can read) the inner id values of
1789  /// the items stored in the graph. This map can be inverted with its member
1790  /// class \c InverseMap or with the \c operator() member.
1791  ///
1792  template <typename _Graph, typename _Item>
1793  class IdMap {
1794  public:
1795    typedef _Graph Graph;
1796    typedef int Value;
1797    typedef _Item Item;
1798    typedef _Item Key;
1799
1800    /// \brief Constructor.
1801    ///
1802    /// Constructor of the map.
1803    explicit IdMap(const Graph& graph) : _graph(&graph) {}
1804
1805    /// \brief Gives back the \e id of the item.
1806    ///
1807    /// Gives back the immutable and unique \e id of the item.
1808    int operator[](const Item& item) const { return _graph->id(item);}
1809
1810    /// \brief Gives back the item by its id.
1811    ///
1812    /// Gives back the item by its id.
1813    Item operator()(int id) { return _graph->fromId(id, Item()); }
1814
1815  private:
1816    const Graph* _graph;
1817
1818  public:
1819
1820    /// \brief The class represents the inverse of its owner (IdMap).
1821    ///
1822    /// The class represents the inverse of its owner (IdMap).
1823    /// \see inverse()
1824    class InverseMap {
1825    public:
1826
1827      /// \brief Constructor.
1828      ///
1829      /// Constructor for creating an id-to-item map.
1830      explicit InverseMap(const Graph& graph) : _graph(&graph) {}
1831
1832      /// \brief Constructor.
1833      ///
1834      /// Constructor for creating an id-to-item map.
1835      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
1836
1837      /// \brief Gives back the given item from its id.
1838      ///
1839      /// Gives back the given item from its id.
1840      ///
1841      Item operator[](int id) const { return _graph->fromId(id, Item());}
1842
1843    private:
1844      const Graph* _graph;
1845    };
1846
1847    /// \brief Gives back the inverse of the map.
1848    ///
1849    /// Gives back the inverse of the IdMap.
1850    InverseMap inverse() const { return InverseMap(*_graph);}
1851
1852  };
1853
1854
1855  /// \brief General invertable graph-map type.
1856
1857  /// This type provides simple invertable graph-maps.
1858  /// The InvertableMap wraps an arbitrary ReadWriteMap
1859  /// and if a key is set to a new value then store it
1860  /// in the inverse map.
1861  ///
1862  /// The values of the map can be accessed
1863  /// with stl compatible forward iterator.
1864  ///
1865  /// \tparam _Graph The graph type.
1866  /// \tparam _Item The item type of the graph.
1867  /// \tparam _Value The value type of the map.
1868  ///
1869  /// \see IterableValueMap
1870  template <typename _Graph, typename _Item, typename _Value>
1871  class InvertableMap
1872    : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
1873  private:
1874
1875    typedef typename ItemSetTraits<_Graph, _Item>::
1876    template Map<_Value>::Type Map;
1877    typedef _Graph Graph;
1878
1879    typedef std::map<_Value, _Item> Container;
1880    Container _inv_map;
1881
1882  public:
1883
1884    /// The key type of InvertableMap (Node, Arc, Edge).
1885    typedef typename Map::Key Key;
1886    /// The value type of the InvertableMap.
1887    typedef typename Map::Value Value;
1888
1889
1890
1891    /// \brief Constructor.
1892    ///
1893    /// Construct a new InvertableMap for the graph.
1894    ///
1895    explicit InvertableMap(const Graph& graph) : Map(graph) {}
1896
1897    /// \brief Forward iterator for values.
1898    ///
1899    /// This iterator is an stl compatible forward
1900    /// iterator on the values of the map. The values can
1901    /// be accessed in the [beginValue, endValue) range.
1902    ///
1903    class ValueIterator
1904      : public std::iterator<std::forward_iterator_tag, Value> {
1905      friend class InvertableMap;
1906    private:
1907      ValueIterator(typename Container::const_iterator _it)
1908        : it(_it) {}
1909    public:
1910
1911      ValueIterator() {}
1912
1913      ValueIterator& operator++() { ++it; return *this; }
1914      ValueIterator operator++(int) {
1915        ValueIterator tmp(*this);
1916        operator++();
1917        return tmp;
1918      }
1919
1920      const Value& operator*() const { return it->first; }
1921      const Value* operator->() const { return &(it->first); }
1922
1923      bool operator==(ValueIterator jt) const { return it == jt.it; }
1924      bool operator!=(ValueIterator jt) const { return it != jt.it; }
1925
1926    private:
1927      typename Container::const_iterator it;
1928    };
1929
1930    /// \brief Returns an iterator to the first value.
1931    ///
1932    /// Returns an stl compatible iterator to the
1933    /// first value of the map. The values of the
1934    /// map can be accessed in the [beginValue, endValue)
1935    /// range.
1936    ValueIterator beginValue() const {
1937      return ValueIterator(_inv_map.begin());
1938    }
1939
1940    /// \brief Returns an iterator after the last value.
1941    ///
1942    /// Returns an stl compatible iterator after the
1943    /// last value of the map. The values of the
1944    /// map can be accessed in the [beginValue, endValue)
1945    /// range.
1946    ValueIterator endValue() const {
1947      return ValueIterator(_inv_map.end());
1948    }
1949
1950    /// \brief The setter function of the map.
1951    ///
1952    /// Sets the mapped value.
1953    void set(const Key& key, const Value& val) {
1954      Value oldval = Map::operator[](key);
1955      typename Container::iterator it = _inv_map.find(oldval);
1956      if (it != _inv_map.end() && it->second == key) {
1957        _inv_map.erase(it);
1958      }
1959      _inv_map.insert(make_pair(val, key));
1960      Map::set(key, val);
1961    }
1962
1963    /// \brief The getter function of the map.
1964    ///
1965    /// It gives back the value associated with the key.
1966    typename MapTraits<Map>::ConstReturnValue
1967    operator[](const Key& key) const {
1968      return Map::operator[](key);
1969    }
1970
1971    /// \brief Gives back the item by its value.
1972    ///
1973    /// Gives back the item by its value.
1974    Key operator()(const Value& key) const {
1975      typename Container::const_iterator it = _inv_map.find(key);
1976      return it != _inv_map.end() ? it->second : INVALID;
1977    }
1978
1979  protected:
1980
1981    /// \brief Erase the key from the map.
1982    ///
1983    /// Erase the key to the map. It is called by the
1984    /// \c AlterationNotifier.
1985    virtual void erase(const Key& key) {
1986      Value val = Map::operator[](key);
1987      typename Container::iterator it = _inv_map.find(val);
1988      if (it != _inv_map.end() && it->second == key) {
1989        _inv_map.erase(it);
1990      }
1991      Map::erase(key);
1992    }
1993
1994    /// \brief Erase more keys from the map.
1995    ///
1996    /// Erase more keys from the map. It is called by the
1997    /// \c AlterationNotifier.
1998    virtual void erase(const std::vector<Key>& keys) {
1999      for (int i = 0; i < int(keys.size()); ++i) {
2000        Value val = Map::operator[](keys[i]);
2001        typename Container::iterator it = _inv_map.find(val);
2002        if (it != _inv_map.end() && it->second == keys[i]) {
2003          _inv_map.erase(it);
2004        }
2005      }
2006      Map::erase(keys);
2007    }
2008
2009    /// \brief Clear the keys from the map and inverse map.
2010    ///
2011    /// Clear the keys from the map and inverse map. It is called by the
2012    /// \c AlterationNotifier.
2013    virtual void clear() {
2014      _inv_map.clear();
2015      Map::clear();
2016    }
2017
2018  public:
2019
2020    /// \brief The inverse map type.
2021    ///
2022    /// The inverse of this map. The subscript operator of the map
2023    /// gives back always the item what was last assigned to the value.
2024    class InverseMap {
2025    public:
2026      /// \brief Constructor of the InverseMap.
2027      ///
2028      /// Constructor of the InverseMap.
2029      explicit InverseMap(const InvertableMap& inverted)
2030        : _inverted(inverted) {}
2031
2032      /// The value type of the InverseMap.
2033      typedef typename InvertableMap::Key Value;
2034      /// The key type of the InverseMap.
2035      typedef typename InvertableMap::Value Key;
2036
2037      /// \brief Subscript operator.
2038      ///
2039      /// Subscript operator. It gives back always the item
2040      /// what was last assigned to the value.
2041      Value operator[](const Key& key) const {
2042        return _inverted(key);
2043      }
2044
2045    private:
2046      const InvertableMap& _inverted;
2047    };
2048
2049    /// \brief It gives back the just readable inverse map.
2050    ///
2051    /// It gives back the just readable inverse map.
2052    InverseMap inverse() const {
2053      return InverseMap(*this);
2054    }
2055
2056
2057
2058  };
2059
2060  /// \brief Provides a mutable, continuous and unique descriptor for each
2061  /// item in the graph.
2062  ///
2063  /// The DescriptorMap class provides a unique and continuous (but mutable)
2064  /// descriptor (id) for each item of the same type (e.g. node) in the
2065  /// graph. This id is <ul><li>\b unique: different items (nodes) get
2066  /// different ids <li>\b continuous: the range of the ids is the set of
2067  /// integers between 0 and \c n-1, where \c n is the number of the items of
2068  /// this type (e.g. nodes) (so the id of a node can change if you delete an
2069  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
2070  /// with its member class \c InverseMap, or with the \c operator() member.
2071  ///
2072  /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
2073  /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
2074  /// Edge.
2075  template <typename _Graph, typename _Item>
2076  class DescriptorMap
2077    : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
2078
2079    typedef _Item Item;
2080    typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
2081
2082  public:
2083    /// The graph class of DescriptorMap.
2084    typedef _Graph Graph;
2085
2086    /// The key type of DescriptorMap (Node, Arc, Edge).
2087    typedef typename Map::Key Key;
2088    /// The value type of DescriptorMap.
2089    typedef typename Map::Value Value;
2090
2091    /// \brief Constructor.
2092    ///
2093    /// Constructor for descriptor map.
2094    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
2095      Item it;
2096      const typename Map::Notifier* nf = Map::notifier();
2097      for (nf->first(it); it != INVALID; nf->next(it)) {
2098        Map::set(it, _inv_map.size());
2099        _inv_map.push_back(it);
2100      }
2101    }
2102
2103  protected:
2104
2105    /// \brief Add a new key to the map.
2106    ///
2107    /// Add a new key to the map. It is called by the
2108    /// \c AlterationNotifier.
2109    virtual void add(const Item& item) {
2110      Map::add(item);
2111      Map::set(item, _inv_map.size());
2112      _inv_map.push_back(item);
2113    }
2114
2115    /// \brief Add more new keys to the map.
2116    ///
2117    /// Add more new keys to the map. It is called by the
2118    /// \c AlterationNotifier.
2119    virtual void add(const std::vector<Item>& items) {
2120      Map::add(items);
2121      for (int i = 0; i < int(items.size()); ++i) {
2122        Map::set(items[i], _inv_map.size());
2123        _inv_map.push_back(items[i]);
2124      }
2125    }
2126
2127    /// \brief Erase the key from the map.
2128    ///
2129    /// Erase the key from the map. It is called by the
2130    /// \c AlterationNotifier.
2131    virtual void erase(const Item& item) {
2132      Map::set(_inv_map.back(), Map::operator[](item));
2133      _inv_map[Map::operator[](item)] = _inv_map.back();
2134      _inv_map.pop_back();
2135      Map::erase(item);
2136    }
2137
2138    /// \brief Erase more keys from the map.
2139    ///
2140    /// Erase more keys from the map. It is called by the
2141    /// \c AlterationNotifier.
2142    virtual void erase(const std::vector<Item>& items) {
2143      for (int i = 0; i < int(items.size()); ++i) {
2144        Map::set(_inv_map.back(), Map::operator[](items[i]));
2145        _inv_map[Map::operator[](items[i])] = _inv_map.back();
2146        _inv_map.pop_back();
2147      }
2148      Map::erase(items);
2149    }
2150
2151    /// \brief Build the unique map.
2152    ///
2153    /// Build the unique map. It is called by the
2154    /// \c AlterationNotifier.
2155    virtual void build() {
2156      Map::build();
2157      Item it;
2158      const typename Map::Notifier* nf = Map::notifier();
2159      for (nf->first(it); it != INVALID; nf->next(it)) {
2160        Map::set(it, _inv_map.size());
2161        _inv_map.push_back(it);
2162      }
2163    }
2164
2165    /// \brief Clear the keys from the map.
2166    ///
2167    /// Clear the keys from the map. It is called by the
2168    /// \c AlterationNotifier.
2169    virtual void clear() {
2170      _inv_map.clear();
2171      Map::clear();
2172    }
2173
2174  public:
2175
2176    /// \brief Returns the maximal value plus one.
2177    ///
2178    /// Returns the maximal value plus one in the map.
2179    unsigned int size() const {
2180      return _inv_map.size();
2181    }
2182
2183    /// \brief Swaps the position of the two items in the map.
2184    ///
2185    /// Swaps the position of the two items in the map.
2186    void swap(const Item& p, const Item& q) {
2187      int pi = Map::operator[](p);
2188      int qi = Map::operator[](q);
2189      Map::set(p, qi);
2190      _inv_map[qi] = p;
2191      Map::set(q, pi);
2192      _inv_map[pi] = q;
2193    }
2194
2195    /// \brief Gives back the \e descriptor of the item.
2196    ///
2197    /// Gives back the mutable and unique \e descriptor of the map.
2198    int operator[](const Item& item) const {
2199      return Map::operator[](item);
2200    }
2201
2202    /// \brief Gives back the item by its descriptor.
2203    ///
2204    /// Gives back th item by its descriptor.
2205    Item operator()(int id) const {
2206      return _inv_map[id];
2207    }
2208
2209  private:
2210
2211    typedef std::vector<Item> Container;
2212    Container _inv_map;
2213
2214  public:
2215    /// \brief The inverse map type of DescriptorMap.
2216    ///
2217    /// The inverse map type of DescriptorMap.
2218    class InverseMap {
2219    public:
2220      /// \brief Constructor of the InverseMap.
2221      ///
2222      /// Constructor of the InverseMap.
2223      explicit InverseMap(const DescriptorMap& inverted)
2224        : _inverted(inverted) {}
2225
2226
2227      /// The value type of the InverseMap.
2228      typedef typename DescriptorMap::Key Value;
2229      /// The key type of the InverseMap.
2230      typedef typename DescriptorMap::Value Key;
2231
2232      /// \brief Subscript operator.
2233      ///
2234      /// Subscript operator. It gives back the item
2235      /// that the descriptor belongs to currently.
2236      Value operator[](const Key& key) const {
2237        return _inverted(key);
2238      }
2239
2240      /// \brief Size of the map.
2241      ///
2242      /// Returns the size of the map.
2243      unsigned int size() const {
2244        return _inverted.size();
2245      }
2246
2247    private:
2248      const DescriptorMap& _inverted;
2249    };
2250
2251    /// \brief Gives back the inverse of the map.
2252    ///
2253    /// Gives back the inverse of the map.
2254    const InverseMap inverse() const {
2255      return InverseMap(*this);
2256    }
2257  };
2258
2259  /// \brief Returns the source of the given arc.
2260  ///
2261  /// The SourceMap gives back the source Node of the given arc.
2262  /// \see TargetMap
2263  template <typename Digraph>
2264  class SourceMap {
2265  public:
2266
2267    typedef typename Digraph::Node Value;
2268    typedef typename Digraph::Arc Key;
2269
2270    /// \brief Constructor
2271    ///
2272    /// Constructor
2273    /// \param _digraph The digraph that the map belongs to.
2274    explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
2275
2276    /// \brief The subscript operator.
2277    ///
2278    /// The subscript operator.
2279    /// \param arc The arc
2280    /// \return The source of the arc
2281    Value operator[](const Key& arc) const {
2282      return _digraph.source(arc);
2283    }
2284
2285  private:
2286    const Digraph& _digraph;
2287  };
2288
2289  /// \brief Returns a \ref SourceMap class.
2290  ///
2291  /// This function just returns an \ref SourceMap class.
2292  /// \relates SourceMap
2293  template <typename Digraph>
2294  inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
2295    return SourceMap<Digraph>(digraph);
2296  }
2297
2298  /// \brief Returns the target of the given arc.
2299  ///
2300  /// The TargetMap gives back the target Node of the given arc.
2301  /// \see SourceMap
2302  template <typename Digraph>
2303  class TargetMap {
2304  public:
2305
2306    typedef typename Digraph::Node Value;
2307    typedef typename Digraph::Arc Key;
2308
2309    /// \brief Constructor
2310    ///
2311    /// Constructor
2312    /// \param _digraph The digraph that the map belongs to.
2313    explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
2314
2315    /// \brief The subscript operator.
2316    ///
2317    /// The subscript operator.
2318    /// \param e The arc
2319    /// \return The target of the arc
2320    Value operator[](const Key& e) const {
2321      return _digraph.target(e);
2322    }
2323
2324  private:
2325    const Digraph& _digraph;
2326  };
2327
2328  /// \brief Returns a \ref TargetMap class.
2329  ///
2330  /// This function just returns a \ref TargetMap class.
2331  /// \relates TargetMap
2332  template <typename Digraph>
2333  inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
2334    return TargetMap<Digraph>(digraph);
2335  }
2336
2337  /// \brief Returns the "forward" directed arc view of an edge.
2338  ///
2339  /// Returns the "forward" directed arc view of an edge.
2340  /// \see BackwardMap
2341  template <typename Graph>
2342  class ForwardMap {
2343  public:
2344
2345    typedef typename Graph::Arc Value;
2346    typedef typename Graph::Edge Key;
2347
2348    /// \brief Constructor
2349    ///
2350    /// Constructor
2351    /// \param _graph The graph that the map belongs to.
2352    explicit ForwardMap(const Graph& graph) : _graph(graph) {}
2353
2354    /// \brief The subscript operator.
2355    ///
2356    /// The subscript operator.
2357    /// \param key An edge
2358    /// \return The "forward" directed arc view of edge
2359    Value operator[](const Key& key) const {
2360      return _graph.direct(key, true);
2361    }
2362
2363  private:
2364    const Graph& _graph;
2365  };
2366
2367  /// \brief Returns a \ref ForwardMap class.
2368  ///
2369  /// This function just returns an \ref ForwardMap class.
2370  /// \relates ForwardMap
2371  template <typename Graph>
2372  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
2373    return ForwardMap<Graph>(graph);
2374  }
2375
2376  /// \brief Returns the "backward" directed arc view of an edge.
2377  ///
2378  /// Returns the "backward" directed arc view of an edge.
2379  /// \see ForwardMap
2380  template <typename Graph>
2381  class BackwardMap {
2382  public:
2383
2384    typedef typename Graph::Arc Value;
2385    typedef typename Graph::Edge Key;
2386
2387    /// \brief Constructor
2388    ///
2389    /// Constructor
2390    /// \param _graph The graph that the map belongs to.
2391    explicit BackwardMap(const Graph& graph) : _graph(graph) {}
2392
2393    /// \brief The subscript operator.
2394    ///
2395    /// The subscript operator.
2396    /// \param key An edge
2397    /// \return The "backward" directed arc view of edge
2398    Value operator[](const Key& key) const {
2399      return _graph.direct(key, false);
2400    }
2401
2402  private:
2403    const Graph& _graph;
2404  };
2405
2406  /// \brief Returns a \ref BackwardMap class
2407
2408  /// This function just returns a \ref BackwardMap class.
2409  /// \relates BackwardMap
2410  template <typename Graph>
2411  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
2412    return BackwardMap<Graph>(graph);
2413  }
2414
2415  /// \brief Potential difference map
2416  ///
2417  /// If there is an potential map on the nodes then we
2418  /// can get an arc map as we get the substraction of the
2419  /// values of the target and source.
2420  template <typename Digraph, typename NodeMap>
2421  class PotentialDifferenceMap {
2422  public:
2423    typedef typename Digraph::Arc Key;
2424    typedef typename NodeMap::Value Value;
2425
2426    /// \brief Constructor
2427    ///
2428    /// Contructor of the map
2429    explicit PotentialDifferenceMap(const Digraph& digraph,
2430                                    const NodeMap& potential)
2431      : _digraph(digraph), _potential(potential) {}
2432
2433    /// \brief Const subscription operator
2434    ///
2435    /// Const subscription operator
2436    Value operator[](const Key& arc) const {
2437      return _potential[_digraph.target(arc)] -
2438        _potential[_digraph.source(arc)];
2439    }
2440
2441  private:
2442    const Digraph& _digraph;
2443    const NodeMap& _potential;
2444  };
2445
2446  /// \brief Returns a PotentialDifferenceMap.
2447  ///
2448  /// This function just returns a PotentialDifferenceMap.
2449  /// \relates PotentialDifferenceMap
2450  template <typename Digraph, typename NodeMap>
2451  PotentialDifferenceMap<Digraph, NodeMap>
2452  potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
2453    return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
2454  }
2455
2456  /// \brief Map of the node in-degrees.
2457  ///
2458  /// This map returns the in-degree of a node. Once it is constructed,
2459  /// the degrees are stored in a standard NodeMap, so each query is done
2460  /// in constant time. On the other hand, the values are updated automatically
2461  /// whenever the digraph changes.
2462  ///
2463  /// \warning Besides addNode() and addArc(), a digraph structure may provide
2464  /// alternative ways to modify the digraph. The correct behavior of InDegMap
2465  /// is not guarantied if these additional features are used. For example
2466  /// the functions \ref ListDigraph::changeSource() "changeSource()",
2467  /// \ref ListDigraph::changeTarget() "changeTarget()" and
2468  /// \ref ListDigraph::reverseArc() "reverseArc()"
2469  /// of \ref ListDigraph will \e not update the degree values correctly.
2470  ///
2471  /// \sa OutDegMap
2472
2473  template <typename _Digraph>
2474  class InDegMap
2475    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
2476      ::ItemNotifier::ObserverBase {
2477
2478  public:
2479
2480    typedef _Digraph Digraph;
2481    typedef int Value;
2482    typedef typename Digraph::Node Key;
2483
2484    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
2485    ::ItemNotifier::ObserverBase Parent;
2486
2487  private:
2488
2489    class AutoNodeMap
2490      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
2491    public:
2492
2493      typedef typename ItemSetTraits<Digraph, Key>::
2494      template Map<int>::Type Parent;
2495
2496      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
2497
2498      virtual void add(const Key& key) {
2499        Parent::add(key);
2500        Parent::set(key, 0);
2501      }
2502
2503      virtual void add(const std::vector<Key>& keys) {
2504        Parent::add(keys);
2505        for (int i = 0; i < int(keys.size()); ++i) {
2506          Parent::set(keys[i], 0);
2507        }
2508      }
2509
2510      virtual void build() {
2511        Parent::build();
2512        Key it;
2513        typename Parent::Notifier* nf = Parent::notifier();
2514        for (nf->first(it); it != INVALID; nf->next(it)) {
2515          Parent::set(it, 0);
2516        }
2517      }
2518    };
2519
2520  public:
2521
2522    /// \brief Constructor.
2523    ///
2524    /// Constructor for creating in-degree map.
2525    explicit InDegMap(const Digraph& digraph)
2526      : _digraph(digraph), _deg(digraph) {
2527      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
2528
2529      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2530        _deg[it] = countInArcs(_digraph, it);
2531      }
2532    }
2533
2534    /// Gives back the in-degree of a Node.
2535    int operator[](const Key& key) const {
2536      return _deg[key];
2537    }
2538
2539  protected:
2540
2541    typedef typename Digraph::Arc Arc;
2542
2543    virtual void add(const Arc& arc) {
2544      ++_deg[_digraph.target(arc)];
2545    }
2546
2547    virtual void add(const std::vector<Arc>& arcs) {
2548      for (int i = 0; i < int(arcs.size()); ++i) {
2549        ++_deg[_digraph.target(arcs[i])];
2550      }
2551    }
2552
2553    virtual void erase(const Arc& arc) {
2554      --_deg[_digraph.target(arc)];
2555    }
2556
2557    virtual void erase(const std::vector<Arc>& arcs) {
2558      for (int i = 0; i < int(arcs.size()); ++i) {
2559        --_deg[_digraph.target(arcs[i])];
2560      }
2561    }
2562
2563    virtual void build() {
2564      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2565        _deg[it] = countInArcs(_digraph, it);
2566      }
2567    }
2568
2569    virtual void clear() {
2570      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2571        _deg[it] = 0;
2572      }
2573    }
2574  private:
2575
2576    const Digraph& _digraph;
2577    AutoNodeMap _deg;
2578  };
2579
2580  /// \brief Map of the node out-degrees.
2581  ///
2582  /// This map returns the out-degree of a node. Once it is constructed,
2583  /// the degrees are stored in a standard NodeMap, so each query is done
2584  /// in constant time. On the other hand, the values are updated automatically
2585  /// whenever the digraph changes.
2586  ///
2587  /// \warning Besides addNode() and addArc(), a digraph structure may provide
2588  /// alternative ways to modify the digraph. The correct behavior of OutDegMap
2589  /// is not guarantied if these additional features are used. For example
2590  /// the functions \ref ListDigraph::changeSource() "changeSource()",
2591  /// \ref ListDigraph::changeTarget() "changeTarget()" and
2592  /// \ref ListDigraph::reverseArc() "reverseArc()"
2593  /// of \ref ListDigraph will \e not update the degree values correctly.
2594  ///
2595  /// \sa InDegMap
2596
2597  template <typename _Digraph>
2598  class OutDegMap
2599    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
2600      ::ItemNotifier::ObserverBase {
2601
2602  public:
2603
2604    typedef _Digraph Digraph;
2605    typedef int Value;
2606    typedef typename Digraph::Node Key;
2607
2608    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
2609    ::ItemNotifier::ObserverBase Parent;
2610
2611  private:
2612
2613    class AutoNodeMap
2614      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
2615    public:
2616
2617      typedef typename ItemSetTraits<Digraph, Key>::
2618      template Map<int>::Type Parent;
2619
2620      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
2621
2622      virtual void add(const Key& key) {
2623        Parent::add(key);
2624        Parent::set(key, 0);
2625      }
2626      virtual void add(const std::vector<Key>& keys) {
2627        Parent::add(keys);
2628        for (int i = 0; i < int(keys.size()); ++i) {
2629          Parent::set(keys[i], 0);
2630        }
2631      }
2632      virtual void build() {
2633        Parent::build();
2634        Key it;
2635        typename Parent::Notifier* nf = Parent::notifier();
2636        for (nf->first(it); it != INVALID; nf->next(it)) {
2637          Parent::set(it, 0);
2638        }
2639      }
2640    };
2641
2642  public:
2643
2644    /// \brief Constructor.
2645    ///
2646    /// Constructor for creating out-degree map.
2647    explicit OutDegMap(const Digraph& digraph)
2648      : _digraph(digraph), _deg(digraph) {
2649      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
2650
2651      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2652        _deg[it] = countOutArcs(_digraph, it);
2653      }
2654    }
2655
2656    /// Gives back the out-degree of a Node.
2657    int operator[](const Key& key) const {
2658      return _deg[key];
2659    }
2660
2661  protected:
2662
2663    typedef typename Digraph::Arc Arc;
2664
2665    virtual void add(const Arc& arc) {
2666      ++_deg[_digraph.source(arc)];
2667    }
2668
2669    virtual void add(const std::vector<Arc>& arcs) {
2670      for (int i = 0; i < int(arcs.size()); ++i) {
2671        ++_deg[_digraph.source(arcs[i])];
2672      }
2673    }
2674
2675    virtual void erase(const Arc& arc) {
2676      --_deg[_digraph.source(arc)];
2677    }
2678
2679    virtual void erase(const std::vector<Arc>& arcs) {
2680      for (int i = 0; i < int(arcs.size()); ++i) {
2681        --_deg[_digraph.source(arcs[i])];
2682      }
2683    }
2684
2685    virtual void build() {
2686      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2687        _deg[it] = countOutArcs(_digraph, it);
2688      }
2689    }
2690
2691    virtual void clear() {
2692      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2693        _deg[it] = 0;
2694      }
2695    }
2696  private:
2697
2698    const Digraph& _digraph;
2699    AutoNodeMap _deg;
2700  };
2701
2702  /// @}
2703}
2704
2705#endif // LEMON_MAPS_H
Note: See TracBrowser for help on using the repository browser.