COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/maps.h @ 684:7b1a6e963018

Last change on this file since 684:7b1a6e963018 was 684:7b1a6e963018, checked in by Peter Kovacs <kpeter@…>, 10 years ago

Fix the implementation and doc of CrossRefMap? (#302)

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