COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/maps.h @ 464:acfb0f24d178

Last change on this file since 464:acfb0f24d178 was 440:88ed40ad0d4f, checked in by Alpar Juttner <alpar@…>, 16 years ago

Happy New Year again

  • update the copyright headers + run the source unifier
File size: 77.7 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-2009
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    /// \brief 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 \c NullMap class
77
78  /// This function just returns a \c 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 \c 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 \c ConstMap class
137
138  /// This function just returns a \c 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 \c 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 \c ConstMap class with inlined constant value
186
187  /// This function just returns a \c 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 \c IdentityMap class
216
217  /// This function just returns an \c 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  /// \c UnionFind, \c 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 \c 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 \c RangeMap class
315
316  /// This function just returns a \c 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 \c RangeMap class created from an appropriate
324  /// \c std::vector
325
326  /// This function just returns a \c 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 \c 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 \c SparseMap class
437
438  /// This function just returns a \c 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 \c SparseMap class created from an appropriate
452  /// \c std::map
453
454  /// This function just returns a \c 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 \c ComposeMap class
505
506  /// This function just returns a \c 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 \c CombineMap class
560
561  /// This function just returns a \c 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 \c FunctorToMap class
629
630  /// This function just returns a \c 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 \c MapToFunctor class
688
689  /// This function just returns a \c 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 \c ConvertMap class
727
728  /// This function just returns a \c 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 \c ForkMap class
767
768  /// This function just returns a \c 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 \c AddMap class
811
812  /// This function just returns an \c 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 \c SubMap class
859
860  /// This function just returns a \c 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 \c MulMap class
908
909  /// This function just returns a \c 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 \c DivMap class
956
957  /// This function just returns a \c 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 \c ShiftMap class
1042
1043  /// This function just returns a \c 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 \c ShiftWriteMap class
1056
1057  /// This function just returns a \c 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 \c ScaleMap class
1144
1145  /// This function just returns a \c 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 \c ScaleWriteMap class
1158
1159  /// This function just returns a \c 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 \c NegMap class
1244
1245  /// This function just returns a \c 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 \c NegWriteMap class
1257
1258  /// This function just returns a \c 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 \c AbsMap class
1300
1301  /// This function just returns an \c 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 \c TrueMap class
1349
1350  /// This function just returns a \c 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 \c FalseMap class
1386
1387  /// This function just returns a \c 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 \c AndMap class
1433
1434  /// This function just returns an \c 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 \c OrMap class
1481
1482  /// This function just returns an \c 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 \c NotMap class
1548
1549  /// This function just returns a \c 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 \c NotWriteMap class
1561
1562  /// This function just returns a \c 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 \c EqualMap class
1609
1610  /// This function just returns an \c 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 \c LessMap class
1657
1658  /// This function just returns an \c 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  /// @}
1687
1688  /// \addtogroup maps
1689  /// @{
1690
1691  /// \brief Writable bool map for logging each \c true assigned element
1692  ///
1693  /// A \ref concepts::WriteMap "writable" bool map for logging
1694  /// each \c true assigned element, i.e it copies subsequently each
1695  /// keys set to \c true to the given iterator.
1696  /// The most important usage of it is storing certain nodes or arcs
1697  /// that were marked \c true by an algorithm.
1698  ///
1699  /// There are several algorithms that provide solutions through bool
1700  /// maps and most of them assign \c true at most once for each key.
1701  /// In these cases it is a natural request to store each \c true
1702  /// assigned elements (in order of the assignment), which can be
1703  /// easily done with LoggerBoolMap.
1704  ///
1705  /// The simplest way of using this map is through the loggerBoolMap()
1706  /// function.
1707  ///
1708  /// \tparam It The type of the iterator.
1709  /// \tparam Ke The key type of the map. The default value set
1710  /// according to the iterator type should work in most cases.
1711  ///
1712  /// \note The container of the iterator must contain enough space
1713  /// for the elements or the iterator should be an inserter iterator.
1714#ifdef DOXYGEN
1715  template <typename It, typename Ke>
1716#else
1717  template <typename It,
1718            typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
1719#endif
1720  class LoggerBoolMap {
1721  public:
1722    typedef It Iterator;
1723
1724    typedef Ke Key;
1725    typedef bool Value;
1726
1727    /// Constructor
1728    LoggerBoolMap(Iterator it)
1729      : _begin(it), _end(it) {}
1730
1731    /// Gives back the given iterator set for the first key
1732    Iterator begin() const {
1733      return _begin;
1734    }
1735
1736    /// Gives back the the 'after the last' iterator
1737    Iterator end() const {
1738      return _end;
1739    }
1740
1741    /// The set function of the map
1742    void set(const Key& key, Value value) {
1743      if (value) {
1744        *_end++ = key;
1745      }
1746    }
1747
1748  private:
1749    Iterator _begin;
1750    Iterator _end;
1751  };
1752
1753  /// Returns a \c LoggerBoolMap class
1754
1755  /// This function just returns a \c LoggerBoolMap class.
1756  ///
1757  /// The most important usage of it is storing certain nodes or arcs
1758  /// that were marked \c true by an algorithm.
1759  /// For example it makes easier to store the nodes in the processing
1760  /// order of Dfs algorithm, as the following examples show.
1761  /// \code
1762  ///   std::vector<Node> v;
1763  ///   dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
1764  /// \endcode
1765  /// \code
1766  ///   std::vector<Node> v(countNodes(g));
1767  ///   dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
1768  /// \endcode
1769  ///
1770  /// \note The container of the iterator must contain enough space
1771  /// for the elements or the iterator should be an inserter iterator.
1772  ///
1773  /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
1774  /// it cannot be used when a readable map is needed, for example as
1775  /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms.
1776  ///
1777  /// \relates LoggerBoolMap
1778  template<typename Iterator>
1779  inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
1780    return LoggerBoolMap<Iterator>(it);
1781  }
1782
1783  /// @}
1784
1785  /// \addtogroup graph_maps
1786  /// @{
1787
1788  /// Provides an immutable and unique id for each item in the graph.
1789
1790  /// The IdMap class provides a unique and immutable id for each item of the
1791  /// same type (e.g. node) in the graph. This id is <ul><li>\b unique:
1792  /// different items (nodes) get different ids <li>\b immutable: the id of an
1793  /// item (node) does not change (even if you delete other nodes).  </ul>
1794  /// Through this map you get access (i.e. can read) the inner id values of
1795  /// the items stored in the graph. This map can be inverted with its member
1796  /// class \c InverseMap or with the \c operator() member.
1797  ///
1798  template <typename _Graph, typename _Item>
1799  class IdMap {
1800  public:
1801    typedef _Graph Graph;
1802    typedef int Value;
1803    typedef _Item Item;
1804    typedef _Item Key;
1805
1806    /// \brief Constructor.
1807    ///
1808    /// Constructor of the map.
1809    explicit IdMap(const Graph& graph) : _graph(&graph) {}
1810
1811    /// \brief Gives back the \e id of the item.
1812    ///
1813    /// Gives back the immutable and unique \e id of the item.
1814    int operator[](const Item& item) const { return _graph->id(item);}
1815
1816    /// \brief Gives back the item by its id.
1817    ///
1818    /// Gives back the item by its id.
1819    Item operator()(int id) { return _graph->fromId(id, Item()); }
1820
1821  private:
1822    const Graph* _graph;
1823
1824  public:
1825
1826    /// \brief The class represents the inverse of its owner (IdMap).
1827    ///
1828    /// The class represents the inverse of its owner (IdMap).
1829    /// \see inverse()
1830    class InverseMap {
1831    public:
1832
1833      /// \brief Constructor.
1834      ///
1835      /// Constructor for creating an id-to-item map.
1836      explicit InverseMap(const Graph& graph) : _graph(&graph) {}
1837
1838      /// \brief Constructor.
1839      ///
1840      /// Constructor for creating an id-to-item map.
1841      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
1842
1843      /// \brief Gives back the given item from its id.
1844      ///
1845      /// Gives back the given item from its id.
1846      ///
1847      Item operator[](int id) const { return _graph->fromId(id, Item());}
1848
1849    private:
1850      const Graph* _graph;
1851    };
1852
1853    /// \brief Gives back the inverse of the map.
1854    ///
1855    /// Gives back the inverse of the IdMap.
1856    InverseMap inverse() const { return InverseMap(*_graph);}
1857
1858  };
1859
1860
1861  /// \brief General invertable graph-map type.
1862
1863  /// This type provides simple invertable graph-maps.
1864  /// The InvertableMap wraps an arbitrary ReadWriteMap
1865  /// and if a key is set to a new value then store it
1866  /// in the inverse map.
1867  ///
1868  /// The values of the map can be accessed
1869  /// with stl compatible forward iterator.
1870  ///
1871  /// \tparam _Graph The graph type.
1872  /// \tparam _Item The item type of the graph.
1873  /// \tparam _Value The value type of the map.
1874  ///
1875  /// \see IterableValueMap
1876  template <typename _Graph, typename _Item, typename _Value>
1877  class InvertableMap
1878    : protected ItemSetTraits<_Graph, _Item>::template Map<_Value>::Type {
1879  private:
1880
1881    typedef typename ItemSetTraits<_Graph, _Item>::
1882    template Map<_Value>::Type Map;
1883    typedef _Graph Graph;
1884
1885    typedef std::map<_Value, _Item> Container;
1886    Container _inv_map;
1887
1888  public:
1889
1890    /// The key type of InvertableMap (Node, Arc, Edge).
1891    typedef typename Map::Key Key;
1892    /// The value type of the InvertableMap.
1893    typedef typename Map::Value Value;
1894
1895    /// \brief Constructor.
1896    ///
1897    /// Construct a new InvertableMap for the graph.
1898    ///
1899    explicit InvertableMap(const Graph& graph) : Map(graph) {}
1900
1901    /// \brief Forward iterator for values.
1902    ///
1903    /// This iterator is an stl compatible forward
1904    /// iterator on the values of the map. The values can
1905    /// be accessed in the [beginValue, endValue) range.
1906    ///
1907    class ValueIterator
1908      : public std::iterator<std::forward_iterator_tag, Value> {
1909      friend class InvertableMap;
1910    private:
1911      ValueIterator(typename Container::const_iterator _it)
1912        : it(_it) {}
1913    public:
1914
1915      ValueIterator() {}
1916
1917      ValueIterator& operator++() { ++it; return *this; }
1918      ValueIterator operator++(int) {
1919        ValueIterator tmp(*this);
1920        operator++();
1921        return tmp;
1922      }
1923
1924      const Value& operator*() const { return it->first; }
1925      const Value* operator->() const { return &(it->first); }
1926
1927      bool operator==(ValueIterator jt) const { return it == jt.it; }
1928      bool operator!=(ValueIterator jt) const { return it != jt.it; }
1929
1930    private:
1931      typename Container::const_iterator it;
1932    };
1933
1934    /// \brief Returns an iterator to the first value.
1935    ///
1936    /// Returns an stl compatible iterator to the
1937    /// first value of the map. The values of the
1938    /// map can be accessed in the [beginValue, endValue)
1939    /// range.
1940    ValueIterator beginValue() const {
1941      return ValueIterator(_inv_map.begin());
1942    }
1943
1944    /// \brief Returns an iterator after the last value.
1945    ///
1946    /// Returns an stl compatible iterator after the
1947    /// last value of the map. The values of the
1948    /// map can be accessed in the [beginValue, endValue)
1949    /// range.
1950    ValueIterator endValue() const {
1951      return ValueIterator(_inv_map.end());
1952    }
1953
1954    /// \brief The setter function of the map.
1955    ///
1956    /// Sets the mapped value.
1957    void set(const Key& key, const Value& val) {
1958      Value oldval = Map::operator[](key);
1959      typename Container::iterator it = _inv_map.find(oldval);
1960      if (it != _inv_map.end() && it->second == key) {
1961        _inv_map.erase(it);
1962      }
1963      _inv_map.insert(make_pair(val, key));
1964      Map::set(key, val);
1965    }
1966
1967    /// \brief The getter function of the map.
1968    ///
1969    /// It gives back the value associated with the key.
1970    typename MapTraits<Map>::ConstReturnValue
1971    operator[](const Key& key) const {
1972      return Map::operator[](key);
1973    }
1974
1975    /// \brief Gives back the item by its value.
1976    ///
1977    /// Gives back the item by its value.
1978    Key operator()(const Value& key) const {
1979      typename Container::const_iterator it = _inv_map.find(key);
1980      return it != _inv_map.end() ? it->second : INVALID;
1981    }
1982
1983  protected:
1984
1985    /// \brief Erase the key from the map.
1986    ///
1987    /// Erase the key to the map. It is called by the
1988    /// \c AlterationNotifier.
1989    virtual void erase(const Key& key) {
1990      Value val = Map::operator[](key);
1991      typename Container::iterator it = _inv_map.find(val);
1992      if (it != _inv_map.end() && it->second == key) {
1993        _inv_map.erase(it);
1994      }
1995      Map::erase(key);
1996    }
1997
1998    /// \brief Erase more keys from the map.
1999    ///
2000    /// Erase more keys from the map. It is called by the
2001    /// \c AlterationNotifier.
2002    virtual void erase(const std::vector<Key>& keys) {
2003      for (int i = 0; i < int(keys.size()); ++i) {
2004        Value val = Map::operator[](keys[i]);
2005        typename Container::iterator it = _inv_map.find(val);
2006        if (it != _inv_map.end() && it->second == keys[i]) {
2007          _inv_map.erase(it);
2008        }
2009      }
2010      Map::erase(keys);
2011    }
2012
2013    /// \brief Clear the keys from the map and inverse map.
2014    ///
2015    /// Clear the keys from the map and inverse map. It is called by the
2016    /// \c AlterationNotifier.
2017    virtual void clear() {
2018      _inv_map.clear();
2019      Map::clear();
2020    }
2021
2022  public:
2023
2024    /// \brief The inverse map type.
2025    ///
2026    /// The inverse of this map. The subscript operator of the map
2027    /// gives back always the item what was last assigned to the value.
2028    class InverseMap {
2029    public:
2030      /// \brief Constructor of the InverseMap.
2031      ///
2032      /// Constructor of the InverseMap.
2033      explicit InverseMap(const InvertableMap& inverted)
2034        : _inverted(inverted) {}
2035
2036      /// The value type of the InverseMap.
2037      typedef typename InvertableMap::Key Value;
2038      /// The key type of the InverseMap.
2039      typedef typename InvertableMap::Value Key;
2040
2041      /// \brief Subscript operator.
2042      ///
2043      /// Subscript operator. It gives back always the item
2044      /// what was last assigned to the value.
2045      Value operator[](const Key& key) const {
2046        return _inverted(key);
2047      }
2048
2049    private:
2050      const InvertableMap& _inverted;
2051    };
2052
2053    /// \brief It gives back the just readable inverse map.
2054    ///
2055    /// It gives back the just readable inverse map.
2056    InverseMap inverse() const {
2057      return InverseMap(*this);
2058    }
2059
2060  };
2061
2062  /// \brief Provides a mutable, continuous and unique descriptor for each
2063  /// item in the graph.
2064  ///
2065  /// The DescriptorMap class provides a unique and continuous (but mutable)
2066  /// descriptor (id) for each item of the same type (e.g. node) in the
2067  /// graph. This id is <ul><li>\b unique: different items (nodes) get
2068  /// different ids <li>\b continuous: the range of the ids is the set of
2069  /// integers between 0 and \c n-1, where \c n is the number of the items of
2070  /// this type (e.g. nodes) (so the id of a node can change if you delete an
2071  /// other node, i.e. this id is mutable).  </ul> This map can be inverted
2072  /// with its member class \c InverseMap, or with the \c operator() member.
2073  ///
2074  /// \tparam _Graph The graph class the \c DescriptorMap belongs to.
2075  /// \tparam _Item The Item is the Key of the Map. It may be Node, Arc or
2076  /// Edge.
2077  template <typename _Graph, typename _Item>
2078  class DescriptorMap
2079    : protected ItemSetTraits<_Graph, _Item>::template Map<int>::Type {
2080
2081    typedef _Item Item;
2082    typedef typename ItemSetTraits<_Graph, _Item>::template Map<int>::Type Map;
2083
2084  public:
2085    /// The graph class of DescriptorMap.
2086    typedef _Graph Graph;
2087
2088    /// The key type of DescriptorMap (Node, Arc, Edge).
2089    typedef typename Map::Key Key;
2090    /// The value type of DescriptorMap.
2091    typedef typename Map::Value Value;
2092
2093    /// \brief Constructor.
2094    ///
2095    /// Constructor for descriptor map.
2096    explicit DescriptorMap(const Graph& _graph) : Map(_graph) {
2097      Item it;
2098      const typename Map::Notifier* nf = Map::notifier();
2099      for (nf->first(it); it != INVALID; nf->next(it)) {
2100        Map::set(it, _inv_map.size());
2101        _inv_map.push_back(it);
2102      }
2103    }
2104
2105  protected:
2106
2107    /// \brief Add a new key to the map.
2108    ///
2109    /// Add a new key to the map. It is called by the
2110    /// \c AlterationNotifier.
2111    virtual void add(const Item& item) {
2112      Map::add(item);
2113      Map::set(item, _inv_map.size());
2114      _inv_map.push_back(item);
2115    }
2116
2117    /// \brief Add more new keys to the map.
2118    ///
2119    /// Add more new keys to the map. It is called by the
2120    /// \c AlterationNotifier.
2121    virtual void add(const std::vector<Item>& items) {
2122      Map::add(items);
2123      for (int i = 0; i < int(items.size()); ++i) {
2124        Map::set(items[i], _inv_map.size());
2125        _inv_map.push_back(items[i]);
2126      }
2127    }
2128
2129    /// \brief Erase the key from the map.
2130    ///
2131    /// Erase the key from the map. It is called by the
2132    /// \c AlterationNotifier.
2133    virtual void erase(const Item& item) {
2134      Map::set(_inv_map.back(), Map::operator[](item));
2135      _inv_map[Map::operator[](item)] = _inv_map.back();
2136      _inv_map.pop_back();
2137      Map::erase(item);
2138    }
2139
2140    /// \brief Erase more keys from the map.
2141    ///
2142    /// Erase more keys from the map. It is called by the
2143    /// \c AlterationNotifier.
2144    virtual void erase(const std::vector<Item>& items) {
2145      for (int i = 0; i < int(items.size()); ++i) {
2146        Map::set(_inv_map.back(), Map::operator[](items[i]));
2147        _inv_map[Map::operator[](items[i])] = _inv_map.back();
2148        _inv_map.pop_back();
2149      }
2150      Map::erase(items);
2151    }
2152
2153    /// \brief Build the unique map.
2154    ///
2155    /// Build the unique map. It is called by the
2156    /// \c AlterationNotifier.
2157    virtual void build() {
2158      Map::build();
2159      Item it;
2160      const typename Map::Notifier* nf = Map::notifier();
2161      for (nf->first(it); it != INVALID; nf->next(it)) {
2162        Map::set(it, _inv_map.size());
2163        _inv_map.push_back(it);
2164      }
2165    }
2166
2167    /// \brief Clear the keys from the map.
2168    ///
2169    /// Clear the keys from the map. It is called by the
2170    /// \c AlterationNotifier.
2171    virtual void clear() {
2172      _inv_map.clear();
2173      Map::clear();
2174    }
2175
2176  public:
2177
2178    /// \brief Returns the maximal value plus one.
2179    ///
2180    /// Returns the maximal value plus one in the map.
2181    unsigned int size() const {
2182      return _inv_map.size();
2183    }
2184
2185    /// \brief Swaps the position of the two items in the map.
2186    ///
2187    /// Swaps the position of the two items in the map.
2188    void swap(const Item& p, const Item& q) {
2189      int pi = Map::operator[](p);
2190      int qi = Map::operator[](q);
2191      Map::set(p, qi);
2192      _inv_map[qi] = p;
2193      Map::set(q, pi);
2194      _inv_map[pi] = q;
2195    }
2196
2197    /// \brief Gives back the \e descriptor of the item.
2198    ///
2199    /// Gives back the mutable and unique \e descriptor of the map.
2200    int operator[](const Item& item) const {
2201      return Map::operator[](item);
2202    }
2203
2204    /// \brief Gives back the item by its descriptor.
2205    ///
2206    /// Gives back th item by its descriptor.
2207    Item operator()(int id) const {
2208      return _inv_map[id];
2209    }
2210
2211  private:
2212
2213    typedef std::vector<Item> Container;
2214    Container _inv_map;
2215
2216  public:
2217    /// \brief The inverse map type of DescriptorMap.
2218    ///
2219    /// The inverse map type of DescriptorMap.
2220    class InverseMap {
2221    public:
2222      /// \brief Constructor of the InverseMap.
2223      ///
2224      /// Constructor of the InverseMap.
2225      explicit InverseMap(const DescriptorMap& inverted)
2226        : _inverted(inverted) {}
2227
2228
2229      /// The value type of the InverseMap.
2230      typedef typename DescriptorMap::Key Value;
2231      /// The key type of the InverseMap.
2232      typedef typename DescriptorMap::Value Key;
2233
2234      /// \brief Subscript operator.
2235      ///
2236      /// Subscript operator. It gives back the item
2237      /// that the descriptor belongs to currently.
2238      Value operator[](const Key& key) const {
2239        return _inverted(key);
2240      }
2241
2242      /// \brief Size of the map.
2243      ///
2244      /// Returns the size of the map.
2245      unsigned int size() const {
2246        return _inverted.size();
2247      }
2248
2249    private:
2250      const DescriptorMap& _inverted;
2251    };
2252
2253    /// \brief Gives back the inverse of the map.
2254    ///
2255    /// Gives back the inverse of the map.
2256    const InverseMap inverse() const {
2257      return InverseMap(*this);
2258    }
2259  };
2260
2261  /// \brief Returns the source of the given arc.
2262  ///
2263  /// The SourceMap gives back the source Node of the given arc.
2264  /// \see TargetMap
2265  template <typename Digraph>
2266  class SourceMap {
2267  public:
2268
2269    typedef typename Digraph::Node Value;
2270    typedef typename Digraph::Arc Key;
2271
2272    /// \brief Constructor
2273    ///
2274    /// Constructor
2275    /// \param digraph The digraph that the map belongs to.
2276    explicit SourceMap(const Digraph& digraph) : _digraph(digraph) {}
2277
2278    /// \brief The subscript operator.
2279    ///
2280    /// The subscript operator.
2281    /// \param arc The arc
2282    /// \return The source of the arc
2283    Value operator[](const Key& arc) const {
2284      return _digraph.source(arc);
2285    }
2286
2287  private:
2288    const Digraph& _digraph;
2289  };
2290
2291  /// \brief Returns a \c SourceMap class.
2292  ///
2293  /// This function just returns an \c SourceMap class.
2294  /// \relates SourceMap
2295  template <typename Digraph>
2296  inline SourceMap<Digraph> sourceMap(const Digraph& digraph) {
2297    return SourceMap<Digraph>(digraph);
2298  }
2299
2300  /// \brief Returns the target of the given arc.
2301  ///
2302  /// The TargetMap gives back the target Node of the given arc.
2303  /// \see SourceMap
2304  template <typename Digraph>
2305  class TargetMap {
2306  public:
2307
2308    typedef typename Digraph::Node Value;
2309    typedef typename Digraph::Arc Key;
2310
2311    /// \brief Constructor
2312    ///
2313    /// Constructor
2314    /// \param digraph The digraph that the map belongs to.
2315    explicit TargetMap(const Digraph& digraph) : _digraph(digraph) {}
2316
2317    /// \brief The subscript operator.
2318    ///
2319    /// The subscript operator.
2320    /// \param e The arc
2321    /// \return The target of the arc
2322    Value operator[](const Key& e) const {
2323      return _digraph.target(e);
2324    }
2325
2326  private:
2327    const Digraph& _digraph;
2328  };
2329
2330  /// \brief Returns a \c TargetMap class.
2331  ///
2332  /// This function just returns a \c TargetMap class.
2333  /// \relates TargetMap
2334  template <typename Digraph>
2335  inline TargetMap<Digraph> targetMap(const Digraph& digraph) {
2336    return TargetMap<Digraph>(digraph);
2337  }
2338
2339  /// \brief Returns the "forward" directed arc view of an edge.
2340  ///
2341  /// Returns the "forward" directed arc view of an edge.
2342  /// \see BackwardMap
2343  template <typename Graph>
2344  class ForwardMap {
2345  public:
2346
2347    typedef typename Graph::Arc Value;
2348    typedef typename Graph::Edge Key;
2349
2350    /// \brief Constructor
2351    ///
2352    /// Constructor
2353    /// \param graph The graph that the map belongs to.
2354    explicit ForwardMap(const Graph& graph) : _graph(graph) {}
2355
2356    /// \brief The subscript operator.
2357    ///
2358    /// The subscript operator.
2359    /// \param key An edge
2360    /// \return The "forward" directed arc view of edge
2361    Value operator[](const Key& key) const {
2362      return _graph.direct(key, true);
2363    }
2364
2365  private:
2366    const Graph& _graph;
2367  };
2368
2369  /// \brief Returns a \c ForwardMap class.
2370  ///
2371  /// This function just returns an \c ForwardMap class.
2372  /// \relates ForwardMap
2373  template <typename Graph>
2374  inline ForwardMap<Graph> forwardMap(const Graph& graph) {
2375    return ForwardMap<Graph>(graph);
2376  }
2377
2378  /// \brief Returns the "backward" directed arc view of an edge.
2379  ///
2380  /// Returns the "backward" directed arc view of an edge.
2381  /// \see ForwardMap
2382  template <typename Graph>
2383  class BackwardMap {
2384  public:
2385
2386    typedef typename Graph::Arc Value;
2387    typedef typename Graph::Edge Key;
2388
2389    /// \brief Constructor
2390    ///
2391    /// Constructor
2392    /// \param graph The graph that the map belongs to.
2393    explicit BackwardMap(const Graph& graph) : _graph(graph) {}
2394
2395    /// \brief The subscript operator.
2396    ///
2397    /// The subscript operator.
2398    /// \param key An edge
2399    /// \return The "backward" directed arc view of edge
2400    Value operator[](const Key& key) const {
2401      return _graph.direct(key, false);
2402    }
2403
2404  private:
2405    const Graph& _graph;
2406  };
2407
2408  /// \brief Returns a \c BackwardMap class
2409
2410  /// This function just returns a \c BackwardMap class.
2411  /// \relates BackwardMap
2412  template <typename Graph>
2413  inline BackwardMap<Graph> backwardMap(const Graph& graph) {
2414    return BackwardMap<Graph>(graph);
2415  }
2416
2417  /// \brief Potential difference map
2418  ///
2419  /// If there is an potential map on the nodes then we
2420  /// can get an arc map as we get the substraction of the
2421  /// values of the target and source.
2422  template <typename Digraph, typename NodeMap>
2423  class PotentialDifferenceMap {
2424  public:
2425    typedef typename Digraph::Arc Key;
2426    typedef typename NodeMap::Value Value;
2427
2428    /// \brief Constructor
2429    ///
2430    /// Contructor of the map
2431    explicit PotentialDifferenceMap(const Digraph& digraph,
2432                                    const NodeMap& potential)
2433      : _digraph(digraph), _potential(potential) {}
2434
2435    /// \brief Const subscription operator
2436    ///
2437    /// Const subscription operator
2438    Value operator[](const Key& arc) const {
2439      return _potential[_digraph.target(arc)] -
2440        _potential[_digraph.source(arc)];
2441    }
2442
2443  private:
2444    const Digraph& _digraph;
2445    const NodeMap& _potential;
2446  };
2447
2448  /// \brief Returns a PotentialDifferenceMap.
2449  ///
2450  /// This function just returns a PotentialDifferenceMap.
2451  /// \relates PotentialDifferenceMap
2452  template <typename Digraph, typename NodeMap>
2453  PotentialDifferenceMap<Digraph, NodeMap>
2454  potentialDifferenceMap(const Digraph& digraph, const NodeMap& potential) {
2455    return PotentialDifferenceMap<Digraph, NodeMap>(digraph, potential);
2456  }
2457
2458  /// \brief Map of the node in-degrees.
2459  ///
2460  /// This map returns the in-degree of a node. Once it is constructed,
2461  /// the degrees are stored in a standard NodeMap, so each query is done
2462  /// in constant time. On the other hand, the values are updated automatically
2463  /// whenever the digraph changes.
2464  ///
2465  /// \warning Besides addNode() and addArc(), a digraph structure may provide
2466  /// alternative ways to modify the digraph. The correct behavior of InDegMap
2467  /// is not guarantied if these additional features are used. For example
2468  /// the functions \ref ListDigraph::changeSource() "changeSource()",
2469  /// \ref ListDigraph::changeTarget() "changeTarget()" and
2470  /// \ref ListDigraph::reverseArc() "reverseArc()"
2471  /// of \ref ListDigraph will \e not update the degree values correctly.
2472  ///
2473  /// \sa OutDegMap
2474
2475  template <typename _Digraph>
2476  class InDegMap
2477    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
2478      ::ItemNotifier::ObserverBase {
2479
2480  public:
2481
2482    typedef _Digraph Digraph;
2483    typedef int Value;
2484    typedef typename Digraph::Node Key;
2485
2486    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
2487    ::ItemNotifier::ObserverBase Parent;
2488
2489  private:
2490
2491    class AutoNodeMap
2492      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
2493    public:
2494
2495      typedef typename ItemSetTraits<Digraph, Key>::
2496      template Map<int>::Type Parent;
2497
2498      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
2499
2500      virtual void add(const Key& key) {
2501        Parent::add(key);
2502        Parent::set(key, 0);
2503      }
2504
2505      virtual void add(const std::vector<Key>& keys) {
2506        Parent::add(keys);
2507        for (int i = 0; i < int(keys.size()); ++i) {
2508          Parent::set(keys[i], 0);
2509        }
2510      }
2511
2512      virtual void build() {
2513        Parent::build();
2514        Key it;
2515        typename Parent::Notifier* nf = Parent::notifier();
2516        for (nf->first(it); it != INVALID; nf->next(it)) {
2517          Parent::set(it, 0);
2518        }
2519      }
2520    };
2521
2522  public:
2523
2524    /// \brief Constructor.
2525    ///
2526    /// Constructor for creating in-degree map.
2527    explicit InDegMap(const Digraph& digraph)
2528      : _digraph(digraph), _deg(digraph) {
2529      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
2530
2531      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2532        _deg[it] = countInArcs(_digraph, it);
2533      }
2534    }
2535
2536    /// Gives back the in-degree of a Node.
2537    int operator[](const Key& key) const {
2538      return _deg[key];
2539    }
2540
2541  protected:
2542
2543    typedef typename Digraph::Arc Arc;
2544
2545    virtual void add(const Arc& arc) {
2546      ++_deg[_digraph.target(arc)];
2547    }
2548
2549    virtual void add(const std::vector<Arc>& arcs) {
2550      for (int i = 0; i < int(arcs.size()); ++i) {
2551        ++_deg[_digraph.target(arcs[i])];
2552      }
2553    }
2554
2555    virtual void erase(const Arc& arc) {
2556      --_deg[_digraph.target(arc)];
2557    }
2558
2559    virtual void erase(const std::vector<Arc>& arcs) {
2560      for (int i = 0; i < int(arcs.size()); ++i) {
2561        --_deg[_digraph.target(arcs[i])];
2562      }
2563    }
2564
2565    virtual void build() {
2566      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2567        _deg[it] = countInArcs(_digraph, it);
2568      }
2569    }
2570
2571    virtual void clear() {
2572      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2573        _deg[it] = 0;
2574      }
2575    }
2576  private:
2577
2578    const Digraph& _digraph;
2579    AutoNodeMap _deg;
2580  };
2581
2582  /// \brief Map of the node out-degrees.
2583  ///
2584  /// This map returns the out-degree of a node. Once it is constructed,
2585  /// the degrees are stored in a standard NodeMap, so each query is done
2586  /// in constant time. On the other hand, the values are updated automatically
2587  /// whenever the digraph changes.
2588  ///
2589  /// \warning Besides addNode() and addArc(), a digraph structure may provide
2590  /// alternative ways to modify the digraph. The correct behavior of OutDegMap
2591  /// is not guarantied if these additional features are used. For example
2592  /// the functions \ref ListDigraph::changeSource() "changeSource()",
2593  /// \ref ListDigraph::changeTarget() "changeTarget()" and
2594  /// \ref ListDigraph::reverseArc() "reverseArc()"
2595  /// of \ref ListDigraph will \e not update the degree values correctly.
2596  ///
2597  /// \sa InDegMap
2598
2599  template <typename _Digraph>
2600  class OutDegMap
2601    : protected ItemSetTraits<_Digraph, typename _Digraph::Arc>
2602      ::ItemNotifier::ObserverBase {
2603
2604  public:
2605
2606    typedef _Digraph Digraph;
2607    typedef int Value;
2608    typedef typename Digraph::Node Key;
2609
2610    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
2611    ::ItemNotifier::ObserverBase Parent;
2612
2613  private:
2614
2615    class AutoNodeMap
2616      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
2617    public:
2618
2619      typedef typename ItemSetTraits<Digraph, Key>::
2620      template Map<int>::Type Parent;
2621
2622      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
2623
2624      virtual void add(const Key& key) {
2625        Parent::add(key);
2626        Parent::set(key, 0);
2627      }
2628      virtual void add(const std::vector<Key>& keys) {
2629        Parent::add(keys);
2630        for (int i = 0; i < int(keys.size()); ++i) {
2631          Parent::set(keys[i], 0);
2632        }
2633      }
2634      virtual void build() {
2635        Parent::build();
2636        Key it;
2637        typename Parent::Notifier* nf = Parent::notifier();
2638        for (nf->first(it); it != INVALID; nf->next(it)) {
2639          Parent::set(it, 0);
2640        }
2641      }
2642    };
2643
2644  public:
2645
2646    /// \brief Constructor.
2647    ///
2648    /// Constructor for creating out-degree map.
2649    explicit OutDegMap(const Digraph& digraph)
2650      : _digraph(digraph), _deg(digraph) {
2651      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
2652
2653      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2654        _deg[it] = countOutArcs(_digraph, it);
2655      }
2656    }
2657
2658    /// Gives back the out-degree of a Node.
2659    int operator[](const Key& key) const {
2660      return _deg[key];
2661    }
2662
2663  protected:
2664
2665    typedef typename Digraph::Arc Arc;
2666
2667    virtual void add(const Arc& arc) {
2668      ++_deg[_digraph.source(arc)];
2669    }
2670
2671    virtual void add(const std::vector<Arc>& arcs) {
2672      for (int i = 0; i < int(arcs.size()); ++i) {
2673        ++_deg[_digraph.source(arcs[i])];
2674      }
2675    }
2676
2677    virtual void erase(const Arc& arc) {
2678      --_deg[_digraph.source(arc)];
2679    }
2680
2681    virtual void erase(const std::vector<Arc>& arcs) {
2682      for (int i = 0; i < int(arcs.size()); ++i) {
2683        --_deg[_digraph.source(arcs[i])];
2684      }
2685    }
2686
2687    virtual void build() {
2688      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2689        _deg[it] = countOutArcs(_digraph, it);
2690      }
2691    }
2692
2693    virtual void clear() {
2694      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
2695        _deg[it] = 0;
2696      }
2697    }
2698  private:
2699
2700    const Digraph& _digraph;
2701    AutoNodeMap _deg;
2702  };
2703
2704  /// @}
2705}
2706
2707#endif // LEMON_MAPS_H
Note: See TracBrowser for help on using the repository browser.