COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/maps.h @ 287:bb40b6db0a58

Last change on this file since 287:bb40b6db0a58 was 280:e7f8647ce760, checked in by Alpar Juttner <alpar@…>, 16 years ago

Remove todo-s and convert them to trac tickets

File size: 77.8 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
1851  /// \brief General invertable graph-map type.
1852
1853  /// This type provides simple invertable graph-maps.
1854  /// The InvertableMap wraps an arbitrary ReadWriteMap
1855  /// and if a key is set to a new value then store it
1856  /// in the inverse map.
1857  ///
1858  /// The values of the map can be accessed
1859  /// with stl compatible forward iterator.
1860  ///
1861  /// \tparam _Graph The graph type.
1862  /// \tparam _Item The item type of the graph.
1863  /// \tparam _Value The value type of the map.
1864  ///
1865  /// \see IterableValueMap
1866  template <typename _Graph, typename _Item, typename _Value>
1867  class InvertableMap
1868    : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
1869  private:
1870
1871    typedef typename ItemSetTraits<_Graph, _Item>::
1872    template Map<_Value>::Type Map;
1873    typedef _Graph Graph;
1874
1875    typedef std::map<_Value, _Item> Container;
1876    Container _inv_map;
1877
1878  public:
1879
1880    /// The key type of InvertableMap (Node, Arc, Edge).
1881    typedef typename Map::Key Key;
1882    /// The value type of the InvertableMap.
1883    typedef typename Map::Value Value;
1884
1885
1886
1887    /// \brief Constructor.
1888    ///
1889    /// Construct a new InvertableMap for the graph.
1890    ///
1891    explicit InvertableMap(const Graph& graph) : Map(graph) {}
1892
1893    /// \brief Forward iterator for values.
1894    ///
1895    /// This iterator is an stl compatible forward
1896    /// iterator on the values of the map. The values can
1897    /// be accessed in the [beginValue, endValue) range.
1898    ///
1899    class ValueIterator
1900      : public std::iterator<std::forward_iterator_tag, Value> {
1901      friend class InvertableMap;
1902    private:
1903      ValueIterator(typename Container::const_iterator _it)
1904        : it(_it) {}
1905    public:
1906
1907      ValueIterator() {}
1908
1909      ValueIterator& operator++() { ++it; return *this; }
1910      ValueIterator operator++(int) {
1911        ValueIterator tmp(*this);
1912        operator++();
1913        return tmp;
1914      }
1915
1916      const Value& operator*() const { return it->first; }
1917      const Value* operator->() const { return &(it->first); }
1918
1919      bool operator==(ValueIterator jt) const { return it == jt.it; }
1920      bool operator!=(ValueIterator jt) const { return it != jt.it; }
1921
1922    private:
1923      typename Container::const_iterator it;
1924    };
1925
1926    /// \brief Returns an iterator to the first value.
1927    ///
1928    /// Returns an stl compatible iterator to the
1929    /// first value of the map. The values of the
1930    /// map can be accessed in the [beginValue, endValue)
1931    /// range.
1932    ValueIterator beginValue() const {
1933      return ValueIterator(_inv_map.begin());
1934    }
1935
1936    /// \brief Returns an iterator after the last value.
1937    ///
1938    /// Returns an stl compatible iterator after the
1939    /// last value of the map. The values of the
1940    /// map can be accessed in the [beginValue, endValue)
1941    /// range.
1942    ValueIterator endValue() const {
1943      return ValueIterator(_inv_map.end());
1944    }
1945
1946    /// \brief The setter function of the map.
1947    ///
1948    /// Sets the mapped value.
1949    void set(const Key& key, const Value& val) {
1950      Value oldval = Map::operator[](key);
1951      typename Container::iterator it = _inv_map.find(oldval);
1952      if (it != _inv_map.end() && it->second == key) {
1953        _inv_map.erase(it);
1954      }
1955      _inv_map.insert(make_pair(val, key));
1956      Map::set(key, val);
1957    }
1958
1959    /// \brief The getter function of the map.
1960    ///
1961    /// It gives back the value associated with the key.
1962    typename MapTraits<Map>::ConstReturnValue
1963    operator[](const Key& key) const {
1964      return Map::operator[](key);
1965    }
1966
1967    /// \brief Gives back the item by its value.
1968    ///
1969    /// Gives back the item by its value.
1970    Key operator()(const Value& key) const {
1971      typename Container::const_iterator it = _inv_map.find(key);
1972      return it != _inv_map.end() ? it->second : INVALID;
1973    }
1974
1975  protected:
1976
1977    /// \brief Erase the key from the map.
1978    ///
1979    /// Erase the key to the map. It is called by the
1980    /// \c AlterationNotifier.
1981    virtual void erase(const Key& key) {
1982      Value val = Map::operator[](key);
1983      typename Container::iterator it = _inv_map.find(val);
1984      if (it != _inv_map.end() && it->second == key) {
1985        _inv_map.erase(it);
1986      }
1987      Map::erase(key);
1988    }
1989
1990    /// \brief Erase more keys from the map.
1991    ///
1992    /// Erase more keys from the map. It is called by the
1993    /// \c AlterationNotifier.
1994    virtual void erase(const std::vector<Key>& keys) {
1995      for (int i = 0; i < int(keys.size()); ++i) {
1996        Value val = Map::operator[](keys[i]);
1997        typename Container::iterator it = _inv_map.find(val);
1998        if (it != _inv_map.end() && it->second == keys[i]) {
1999          _inv_map.erase(it);
2000        }
2001      }
2002      Map::erase(keys);
2003    }
2004
2005    /// \brief Clear the keys from the map and inverse map.
2006    ///
2007    /// Clear the keys from the map and inverse map. It is called by the
2008    /// \c AlterationNotifier.
2009    virtual void clear() {
2010      _inv_map.clear();
2011      Map::clear();
2012    }
2013
2014  public:
2015
2016    /// \brief The inverse map type.
2017    ///
2018    /// The inverse of this map. The subscript operator of the map
2019    /// gives back always the item what was last assigned to the value.
2020    class InverseMap {
2021    public:
2022      /// \brief Constructor of the InverseMap.
2023      ///
2024      /// Constructor of the InverseMap.
2025      explicit InverseMap(const InvertableMap& inverted)
2026        : _inverted(inverted) {}
2027
2028      /// The value type of the InverseMap.
2029      typedef typename InvertableMap::Key Value;
2030      /// The key type of the InverseMap.
2031      typedef typename InvertableMap::Value Key;
2032
2033      /// \brief Subscript operator.
2034      ///
2035      /// Subscript operator. It gives back always the item
2036      /// what was last assigned to the value.
2037      Value operator[](const Key& key) const {
2038        return _inverted(key);
2039      }
2040
2041    private:
2042      const InvertableMap& _inverted;
2043    };
2044
2045    /// \brief It gives back the just readable inverse map.
2046    ///
2047    /// It gives back the just readable inverse map.
2048    InverseMap inverse() const {
2049      return InverseMap(*this);
2050    }
2051
2052
2053
2054  };
2055
2056  /// \brief Provides a mutable, continuous and unique descriptor for each
2057  /// item in the graph.
2058  ///
2059  /// The DescriptorMap class provides a unique and continuous (but mutable)
2060  /// descriptor (id) for each item of the same type (e.g. node) in the
2061  /// graph. This id is <ul><li>\b unique: different items (nodes) get
2062  /// different ids <li>\b continuous: the range of the ids is the set of
2063  /// integers between 0 and \c n-1, where \c n is the number of the items of
2064  /// this type (e.g. nodes) (so the id of a node can change if you delete an
2065  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
2066  /// with its member class \c InverseMap, or with the \c operator() member.
2067  ///
2068  /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
2069  /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
2070  /// Edge.
2071  template <typename _Graph, typename _Item>
2072  class DescriptorMap
2073    : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
2074
2075    typedef _Item Item;
2076    typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
2077
2078  public:
2079    /// The graph class of DescriptorMap.
2080    typedef _Graph Graph;
2081
2082    /// The key type of DescriptorMap (Node, Arc, Edge).
2083    typedef typename Map::Key Key;
2084    /// The value type of DescriptorMap.
2085    typedef typename Map::Value Value;
2086
2087    /// \brief Constructor.
2088    ///
2089    /// Constructor for descriptor map.
2090    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
2091      Item it;
2092      const typename Map::Notifier* nf = Map::notifier();
2093      for (nf->first(it); it != INVALID; nf->next(it)) {
2094        Map::set(it, _inv_map.size());
2095        _inv_map.push_back(it);
2096      }
2097    }
2098
2099  protected:
2100
2101    /// \brief Add a new key to the map.
2102    ///
2103    /// Add a new key to the map. It is called by the
2104    /// \c AlterationNotifier.
2105    virtual void add(const Item& item) {
2106      Map::add(item);
2107      Map::set(item, _inv_map.size());
2108      _inv_map.push_back(item);
2109    }
2110
2111    /// \brief Add more new keys to the map.
2112    ///
2113    /// Add more new keys to the map. It is called by the
2114    /// \c AlterationNotifier.
2115    virtual void add(const std::vector<Item>& items) {
2116      Map::add(items);
2117      for (int i = 0; i < int(items.size()); ++i) {
2118        Map::set(items[i], _inv_map.size());
2119        _inv_map.push_back(items[i]);
2120      }
2121    }
2122
2123    /// \brief Erase the key from the map.
2124    ///
2125    /// Erase the key from the map. It is called by the
2126    /// \c AlterationNotifier.
2127    virtual void erase(const Item& item) {
2128      Map::set(_inv_map.back(), Map::operator[](item));
2129      _inv_map[Map::operator[](item)] = _inv_map.back();
2130      _inv_map.pop_back();
2131      Map::erase(item);
2132    }
2133
2134    /// \brief Erase more keys from the map.
2135    ///
2136    /// Erase more keys from the map. It is called by the
2137    /// \c AlterationNotifier.
2138    virtual void erase(const std::vector<Item>& items) {
2139      for (int i = 0; i < int(items.size()); ++i) {
2140        Map::set(_inv_map.back(), Map::operator[](items[i]));
2141        _inv_map[Map::operator[](items[i])] = _inv_map.back();
2142        _inv_map.pop_back();
2143      }
2144      Map::erase(items);
2145    }
2146
2147    /// \brief Build the unique map.
2148    ///
2149    /// Build the unique map. It is called by the
2150    /// \c AlterationNotifier.
2151    virtual void build() {
2152      Map::build();
2153      Item it;
2154      const typename Map::Notifier* nf = Map::notifier();
2155      for (nf->first(it); it != INVALID; nf->next(it)) {
2156        Map::set(it, _inv_map.size());
2157        _inv_map.push_back(it);
2158      }
2159    }
2160
2161    /// \brief Clear the keys from the map.
2162    ///
2163    /// Clear the keys from the map. It is called by the
2164    /// \c AlterationNotifier.
2165    virtual void clear() {
2166      _inv_map.clear();
2167      Map::clear();
2168    }
2169
2170  public:
2171
2172    /// \brief Returns the maximal value plus one.
2173    ///
2174    /// Returns the maximal value plus one in the map.
2175    unsigned int size() const {
2176      return _inv_map.size();
2177    }
2178
2179    /// \brief Swaps the position of the two items in the map.
2180    ///
2181    /// Swaps the position of the two items in the map.
2182    void swap(const Item& p, const Item& q) {
2183      int pi = Map::operator[](p);
2184      int qi = Map::operator[](q);
2185      Map::set(p, qi);
2186      _inv_map[qi] = p;
2187      Map::set(q, pi);
2188      _inv_map[pi] = q;
2189    }
2190
2191    /// \brief Gives back the \e descriptor of the item.
2192    ///
2193    /// Gives back the mutable and unique \e descriptor of the map.
2194    int operator[](const Item& item) const {
2195      return Map::operator[](item);
2196    }
2197
2198    /// \brief Gives back the item by its descriptor.
2199    ///
2200    /// Gives back th item by its descriptor.
2201    Item operator()(int id) const {
2202      return _inv_map[id];
2203    }
2204
2205  private:
2206
2207    typedef std::vector<Item> Container;
2208    Container _inv_map;
2209
2210  public:
2211    /// \brief The inverse map type of DescriptorMap.
2212    ///
2213    /// The inverse map type of DescriptorMap.
2214    class InverseMap {
2215    public:
2216      /// \brief Constructor of the InverseMap.
2217      ///
2218      /// Constructor of the InverseMap.
2219      explicit InverseMap(const DescriptorMap& inverted)
2220        : _inverted(inverted) {}
2221
2222
2223      /// The value type of the InverseMap.
2224      typedef typename DescriptorMap::Key Value;
2225      /// The key type of the InverseMap.
2226      typedef typename DescriptorMap::Value Key;
2227
2228      /// \brief Subscript operator.
2229      ///
2230      /// Subscript operator. It gives back the item
2231      /// that the descriptor belongs to currently.
2232      Value operator[](const Key& key) const {
2233        return _inverted(key);
2234      }
2235
2236      /// \brief Size of the map.
2237      ///
2238      /// Returns the size of the map.
2239      unsigned int size() const {
2240        return _inverted.size();
2241      }
2242
2243    private:
2244      const DescriptorMap& _inverted;
2245    };
2246
2247    /// \brief Gives back the inverse of the map.
2248    ///
2249    /// Gives back the inverse of the map.
2250    const InverseMap inverse() const {
2251      return InverseMap(*this);
2252    }
2253  };
2254
2255  /// \brief Returns the source of the given arc.
2256  ///
2257  /// The SourceMap gives back the source Node of the given arc.
2258  /// \see TargetMap
2259  template <typename Digraph>
2260  class SourceMap {
2261  public:
2262
2263    typedef typename Digraph::Node Value;
2264    typedef typename Digraph::Arc Key;
2265
2266    /// \brief Constructor
2267    ///
2268    /// Constructor
2269    /// \param _digraph The digraph that the map belongs to.
2270    explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
2271
2272    /// \brief The subscript operator.
2273    ///
2274    /// The subscript operator.
2275    /// \param arc The arc
2276    /// \return The source of the arc
2277    Value operator[](const Key& arc) const {
2278      return _digraph.source(arc);
2279    }
2280
2281  private:
2282    const Digraph& _digraph;
2283  };
2284
2285  /// \brief Returns a \ref SourceMap class.
2286  ///
2287  /// This function just returns an \ref SourceMap class.
2288  /// \relates SourceMap
2289  template <typename Digraph>
2290  inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
2291    return SourceMap<Digraph>(digraph);
2292  }
2293
2294  /// \brief Returns the target of the given arc.
2295  ///
2296  /// The TargetMap gives back the target Node of the given arc.
2297  /// \see SourceMap
2298  template <typename Digraph>
2299  class TargetMap {
2300  public:
2301
2302    typedef typename Digraph::Node Value;
2303    typedef typename Digraph::Arc Key;
2304
2305    /// \brief Constructor
2306    ///
2307    /// Constructor
2308    /// \param _digraph The digraph that the map belongs to.
2309    explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
2310
2311    /// \brief The subscript operator.
2312    ///
2313    /// The subscript operator.
2314    /// \param e The arc
2315    /// \return The target of the arc
2316    Value operator[](const Key& e) const {
2317      return _digraph.target(e);
2318    }
2319
2320  private:
2321    const Digraph& _digraph;
2322  };
2323
2324  /// \brief Returns a \ref TargetMap class.
2325  ///
2326  /// This function just returns a \ref TargetMap class.
2327  /// \relates TargetMap
2328  template <typename Digraph>
2329  inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
2330    return TargetMap<Digraph>(digraph);
2331  }
2332
2333  /// \brief Returns the "forward" directed arc view of an edge.
2334  ///
2335  /// Returns the "forward" directed arc view of an edge.
2336  /// \see BackwardMap
2337  template <typename Graph>
2338  class ForwardMap {
2339  public:
2340
2341    typedef typename Graph::Arc Value;
2342    typedef typename Graph::Edge Key;
2343
2344    /// \brief Constructor
2345    ///
2346    /// Constructor
2347    /// \param _graph The graph that the map belongs to.
2348    explicit ForwardMap(const Graph& graph) : _graph(graph) {}
2349
2350    /// \brief The subscript operator.
2351    ///
2352    /// The subscript operator.
2353    /// \param key An edge
2354    /// \return The "forward" directed arc view of edge
2355    Value operator[](const Key& key) const {
2356      return _graph.direct(key, true);
2357    }
2358
2359  private:
2360    const Graph& _graph;
2361  };
2362
2363  /// \brief Returns a \ref ForwardMap class.
2364  ///
2365  /// This function just returns an \ref ForwardMap class.
2366  /// \relates ForwardMap
2367  template <typename Graph>
2368  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
2369    return ForwardMap<Graph>(graph);
2370  }
2371
2372  /// \brief Returns the "backward" directed arc view of an edge.
2373  ///
2374  /// Returns the "backward" directed arc view of an edge.
2375  /// \see ForwardMap
2376  template <typename Graph>
2377  class BackwardMap {
2378  public:
2379
2380    typedef typename Graph::Arc Value;
2381    typedef typename Graph::Edge Key;
2382
2383    /// \brief Constructor
2384    ///
2385    /// Constructor
2386    /// \param _graph The graph that the map belongs to.
2387    explicit BackwardMap(const Graph& graph) : _graph(graph) {}
2388
2389    /// \brief The subscript operator.
2390    ///
2391    /// The subscript operator.
2392    /// \param key An edge
2393    /// \return The "backward" directed arc view of edge
2394    Value operator[](const Key& key) const {
2395      return _graph.direct(key, false);
2396    }
2397
2398  private:
2399    const Graph& _graph;
2400  };
2401
2402  /// \brief Returns a \ref BackwardMap class
2403
2404  /// This function just returns a \ref BackwardMap class.
2405  /// \relates BackwardMap
2406  template <typename Graph>
2407  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
2408    return BackwardMap<Graph>(graph);
2409  }
2410
2411  /// \brief Potential difference map
2412  ///
2413  /// If there is an potential map on the nodes then we
2414  /// can get an arc map as we get the substraction of the
2415  /// values of the target and source.
2416  template <typename Digraph, typename NodeMap>
2417  class PotentialDifferenceMap {
2418  public:
2419    typedef typename Digraph::Arc Key;
2420    typedef typename NodeMap::Value Value;
2421
2422    /// \brief Constructor
2423    ///
2424    /// Contructor of the map
2425    explicit PotentialDifferenceMap(const Digraph& digraph,
2426                                    const NodeMap& potential)
2427      : _digraph(digraph), _potential(potential) {}
2428
2429    /// \brief Const subscription operator
2430    ///
2431    /// Const subscription operator
2432    Value operator[](const Key& arc) const {
2433      return _potential[_digraph.target(arc)] -
2434        _potential[_digraph.source(arc)];
2435    }
2436
2437  private:
2438    const Digraph& _digraph;
2439    const NodeMap& _potential;
2440  };
2441
2442  /// \brief Returns a PotentialDifferenceMap.
2443  ///
2444  /// This function just returns a PotentialDifferenceMap.
2445  /// \relates PotentialDifferenceMap
2446  template <typename Digraph, typename NodeMap>
2447  PotentialDifferenceMap<Digraph, NodeMap>
2448  potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
2449    return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
2450  }
2451
2452  /// \brief Map of the node in-degrees.
2453  ///
2454  /// This map returns the in-degree of a node. Once it is constructed,
2455  /// the degrees are stored in a standard NodeMap, so each query is done
2456  /// in constant time. On the other hand, the values are updated automatically
2457  /// whenever the digraph changes.
2458  ///
2459  /// \warning Besides addNode() and addArc(), a digraph structure may provide
2460  /// alternative ways to modify the digraph. The correct behavior of InDegMap
2461  /// is not guarantied if these additional features are used. For example
2462  /// the functions \ref ListDigraph::changeSource() "changeSource()",
2463  /// \ref ListDigraph::changeTarget() "changeTarget()" and
2464  /// \ref ListDigraph::reverseArc() "reverseArc()"
2465  /// of \ref ListDigraph will \e not update the degree values correctly.
2466  ///
2467  /// \sa OutDegMap
2468
2469  template <typename _Digraph>
2470  class InDegMap
2471    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
2472      ::ItemNotifier::ObserverBase {
2473
2474  public:
2475
2476    typedef _Digraph Digraph;
2477    typedef int Value;
2478    typedef typename Digraph::Node Key;
2479
2480    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
2481    ::ItemNotifier::ObserverBase Parent;
2482
2483  private:
2484
2485    class AutoNodeMap
2486      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
2487    public:
2488
2489      typedef typename ItemSetTraits<Digraph, Key>::
2490      template Map<int>::Type Parent;
2491
2492      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
2493
2494      virtual void add(const Key& key) {
2495        Parent::add(key);
2496        Parent::set(key, 0);
2497      }
2498
2499      virtual void add(const std::vector<Key>& keys) {
2500        Parent::add(keys);
2501        for (int i = 0; i < int(keys.size()); ++i) {
2502          Parent::set(keys[i], 0);
2503        }
2504      }
2505
2506      virtual void build() {
2507        Parent::build();
2508        Key it;
2509        typename Parent::Notifier* nf = Parent::notifier();
2510        for (nf->first(it); it != INVALID; nf->next(it)) {
2511          Parent::set(it, 0);
2512        }
2513      }
2514    };
2515
2516  public:
2517
2518    /// \brief Constructor.
2519    ///
2520    /// Constructor for creating in-degree map.
2521    explicit InDegMap(const Digraph& digraph)
2522      : _digraph(digraph), _deg(digraph) {
2523      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
2524
2525      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2526        _deg[it] = countInArcs(_digraph, it);
2527      }
2528    }
2529
2530    /// Gives back the in-degree of a Node.
2531    int operator[](const Key& key) const {
2532      return _deg[key];
2533    }
2534
2535  protected:
2536
2537    typedef typename Digraph::Arc Arc;
2538
2539    virtual void add(const Arc& arc) {
2540      ++_deg[_digraph.target(arc)];
2541    }
2542
2543    virtual void add(const std::vector<Arc>& arcs) {
2544      for (int i = 0; i < int(arcs.size()); ++i) {
2545        ++_deg[_digraph.target(arcs[i])];
2546      }
2547    }
2548
2549    virtual void erase(const Arc& arc) {
2550      --_deg[_digraph.target(arc)];
2551    }
2552
2553    virtual void erase(const std::vector<Arc>& arcs) {
2554      for (int i = 0; i < int(arcs.size()); ++i) {
2555        --_deg[_digraph.target(arcs[i])];
2556      }
2557    }
2558
2559    virtual void build() {
2560      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2561        _deg[it] = countInArcs(_digraph, it);
2562      }
2563    }
2564
2565    virtual void clear() {
2566      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2567        _deg[it] = 0;
2568      }
2569    }
2570  private:
2571
2572    const Digraph& _digraph;
2573    AutoNodeMap _deg;
2574  };
2575
2576  /// \brief Map of the node out-degrees.
2577  ///
2578  /// This map returns the out-degree of a node. Once it is constructed,
2579  /// the degrees are stored in a standard NodeMap, so each query is done
2580  /// in constant time. On the other hand, the values are updated automatically
2581  /// whenever the digraph changes.
2582  ///
2583  /// \warning Besides addNode() and addArc(), a digraph structure may provide
2584  /// alternative ways to modify the digraph. The correct behavior of OutDegMap
2585  /// is not guarantied if these additional features are used. For example
2586  /// the functions \ref ListDigraph::changeSource() "changeSource()",
2587  /// \ref ListDigraph::changeTarget() "changeTarget()" and
2588  /// \ref ListDigraph::reverseArc() "reverseArc()"
2589  /// of \ref ListDigraph will \e not update the degree values correctly.
2590  ///
2591  /// \sa InDegMap
2592
2593  template <typename _Digraph>
2594  class OutDegMap
2595    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
2596      ::ItemNotifier::ObserverBase {
2597
2598  public:
2599
2600    typedef _Digraph Digraph;
2601    typedef int Value;
2602    typedef typename Digraph::Node Key;
2603
2604    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
2605    ::ItemNotifier::ObserverBase Parent;
2606
2607  private:
2608
2609    class AutoNodeMap
2610      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
2611    public:
2612
2613      typedef typename ItemSetTraits<Digraph, Key>::
2614      template Map<int>::Type Parent;
2615
2616      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
2617
2618      virtual void add(const Key& key) {
2619        Parent::add(key);
2620        Parent::set(key, 0);
2621      }
2622      virtual void add(const std::vector<Key>& keys) {
2623        Parent::add(keys);
2624        for (int i = 0; i < int(keys.size()); ++i) {
2625          Parent::set(keys[i], 0);
2626        }
2627      }
2628      virtual void build() {
2629        Parent::build();
2630        Key it;
2631        typename Parent::Notifier* nf = Parent::notifier();
2632        for (nf->first(it); it != INVALID; nf->next(it)) {
2633          Parent::set(it, 0);
2634        }
2635      }
2636    };
2637
2638  public:
2639
2640    /// \brief Constructor.
2641    ///
2642    /// Constructor for creating out-degree map.
2643    explicit OutDegMap(const Digraph& digraph)
2644      : _digraph(digraph), _deg(digraph) {
2645      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
2646
2647      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2648        _deg[it] = countOutArcs(_digraph, it);
2649      }
2650    }
2651
2652    /// Gives back the out-degree of a Node.
2653    int operator[](const Key& key) const {
2654      return _deg[key];
2655    }
2656
2657  protected:
2658
2659    typedef typename Digraph::Arc Arc;
2660
2661    virtual void add(const Arc& arc) {
2662      ++_deg[_digraph.source(arc)];
2663    }
2664
2665    virtual void add(const std::vector<Arc>& arcs) {
2666      for (int i = 0; i < int(arcs.size()); ++i) {
2667        ++_deg[_digraph.source(arcs[i])];
2668      }
2669    }
2670
2671    virtual void erase(const Arc& arc) {
2672      --_deg[_digraph.source(arc)];
2673    }
2674
2675    virtual void erase(const std::vector<Arc>& arcs) {
2676      for (int i = 0; i < int(arcs.size()); ++i) {
2677        --_deg[_digraph.source(arcs[i])];
2678      }
2679    }
2680
2681    virtual void build() {
2682      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2683        _deg[it] = countOutArcs(_digraph, it);
2684      }
2685    }
2686
2687    virtual void clear() {
2688      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2689        _deg[it] = 0;
2690      }
2691    }
2692  private:
2693
2694    const Digraph& _digraph;
2695    AutoNodeMap _deg;
2696  };
2697
2698  /// @}
2699}
2700
2701#endif // LEMON_MAPS_H
Note: See TracBrowser for help on using the repository browser.