COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/maps.h

Last change on this file was 1130:0759d974de81, checked in by Gabor Gevay <ggab90@…>, 6 years ago

STL style iterators (#325)

For

  • graph types,
  • graph adaptors,
  • paths,
  • iterable maps,
  • LP rows/cols and
  • active nodes is BellmanFord?
File size: 118.3 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2013
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#include <map>
26
27#include <lemon/core.h>
28#include <lemon/bits/stl_iterators.h>
29
30///\file
31///\ingroup maps
32///\brief Miscellaneous property maps
33
34namespace lemon {
35
36  /// \addtogroup maps
37  /// @{
38
39  /// Base class of maps.
40
41  /// Base class of maps. It provides the necessary type definitions
42  /// required by the map %concepts.
43  template<typename K, typename V>
44  class MapBase {
45  public:
46    /// \brief The key type of the map.
47    typedef K Key;
48    /// \brief The value type of the map.
49    /// (The type of objects associated with the keys).
50    typedef V Value;
51  };
52
53
54  /// Null map. (a.k.a. DoNothingMap)
55
56  /// This map can be used if you have to provide a map only for
57  /// its type definitions, or if you have to provide a writable map,
58  /// but data written to it is not required (i.e. it will be sent to
59  /// <tt>/dev/null</tt>).
60  /// It conforms to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
61  ///
62  /// \sa ConstMap
63  template<typename K, typename V>
64  class NullMap : public MapBase<K, V> {
65  public:
66    ///\e
67    typedef K Key;
68    ///\e
69    typedef V Value;
70
71    /// Gives back a default constructed element.
72    Value operator[](const Key&) const { return Value(); }
73    /// Absorbs the value.
74    void set(const Key&, const Value&) {}
75  };
76
77  /// Returns a \c NullMap class
78
79  /// This function just returns a \c NullMap class.
80  /// \relates NullMap
81  template <typename K, typename V>
82  NullMap<K, V> nullMap() {
83    return NullMap<K, V>();
84  }
85
86
87  /// Constant map.
88
89  /// This \ref concepts::ReadMap "readable map" assigns a specified
90  /// value to each key.
91  ///
92  /// In other aspects it is equivalent to \c NullMap.
93  /// So it conforms to 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> {
103  private:
104    V _value;
105  public:
106    ///\e
107    typedef K Key;
108    ///\e
109    typedef V Value;
110
111    /// Default constructor
112
113    /// Default constructor.
114    /// The value of the map will be default constructed.
115    ConstMap() {}
116
117    /// Constructor with specified initial value
118
119    /// Constructor with specified initial value.
120    /// \param v The initial value of the map.
121    ConstMap(const Value &v) : _value(v) {}
122
123    /// Gives back the specified value.
124    Value operator[](const Key&) const { return _value; }
125
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) {}
136  };
137
138  /// Returns a \c ConstMap class
139
140  /// This function just returns a \c ConstMap class.
141  /// \relates ConstMap
142  template<typename K, typename V>
143  inline ConstMap<K, V> constMap(const V &v) {
144    return ConstMap<K, V>(v);
145  }
146
147  template<typename K, typename V>
148  inline ConstMap<K, V> constMap() {
149    return ConstMap<K, V>();
150  }
151
152
153  template<typename T, T v>
154  struct Const {};
155
156  /// Constant map with inlined constant value.
157
158  /// This \ref concepts::ReadMap "readable map" assigns a specified
159  /// value to each key.
160  ///
161  /// In other aspects it is equivalent to \c NullMap.
162  /// So it conforms to 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
170  template<typename K, typename V, V v>
171  class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
172  public:
173    ///\e
174    typedef K Key;
175    ///\e
176    typedef V Value;
177
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&) {}
186  };
187
188  /// Returns a \c ConstMap class with inlined constant value
189
190  /// This function just returns a \c ConstMap class with inlined
191  /// constant value.
192  /// \relates ConstMap
193  template<typename K, typename V, V v>
194  inline ConstMap<K, Const<V, v> > constMap() {
195    return ConstMap<K, Const<V, v> >();
196  }
197
198
199  /// Identity map.
200
201  /// This \ref concepts::ReadMap "read-only map" gives back the given
202  /// key as value without any modification.
203  ///
204  /// \sa ConstMap
205  template <typename T>
206  class IdentityMap : public MapBase<T, T> {
207  public:
208    ///\e
209    typedef T Key;
210    ///\e
211    typedef T Value;
212
213    /// Gives back the given value without any modification.
214    Value operator[](const Key &k) const {
215      return k;
216    }
217  };
218
219  /// Returns an \c IdentityMap class
220
221  /// This function just returns an \c IdentityMap class.
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 together with some data structures, e.g.
235  /// heap types and \c UnionFind, when the used items are small
236  /// integers. This map conforms to 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
250  public:
251
252    /// Key type
253    typedef int Key;
254    /// Value type
255    typedef V Value;
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
274    /// Constructs the map from another \c RangeMap.
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
317  /// Returns a \c RangeMap class
318
319  /// This function just returns a \c RangeMap class.
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
326  /// \brief Returns a \c RangeMap class created from an appropriate
327  /// \c std::vector
328
329  /// This function just returns a \c RangeMap class created from an
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 to 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.
359  template <typename K, typename V, typename Comp = std::less<K> >
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
366    typedef K Key;
367    /// Value type
368    typedef V Value;
369    /// Reference type
370    typedef Value& Reference;
371    /// Const reference type
372    typedef const Value& ConstReference;
373
374    typedef True ReferenceMapTag;
375
376  private:
377
378    typedef std::map<K, V, Comp> Map;
379    Map _map;
380    Value _value;
381
382  public:
383
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
387    /// explicitly specifies a default value.
388    template <typename V1, typename Comp1>
389    SparseMap(const std::map<Key, V1, Comp1> &map,
390              const Value &value = Value())
391      : _map(map.begin(), map.end()), _value(value) {}
392
393    /// \brief Constructs the map from another \c SparseMap.
394    template<typename V1, typename Comp1>
395    SparseMap(const SparseMap<Key, V1, Comp1> &c)
396      : _map(c._map.begin(), c._map.end()), _value(c._value) {}
397
398  private:
399
400    SparseMap& operator=(const SparseMap&);
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))
408        return it->second;
409      else
410        return _map.insert(it, std::make_pair(k, _value))->second;
411    }
412
413    ///\e
414    ConstReference operator[](const Key &k) const {
415      typename Map::const_iterator it = _map.find(k);
416      if (it != _map.end())
417        return it->second;
418      else
419        return _value;
420    }
421
422    ///\e
423    void set(const Key &k, const Value &v) {
424      typename Map::iterator it = _map.lower_bound(k);
425      if (it != _map.end() && !_map.key_comp()(k, it->first))
426        it->second = v;
427      else
428        _map.insert(it, std::make_pair(k, v));
429    }
430
431    ///\e
432    void setAll(const Value &v) {
433      _value = v;
434      _map.clear();
435    }
436  };
437
438  /// Returns a \c SparseMap class
439
440  /// This function just returns a \c SparseMap class with specified
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);
446  }
447
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);
451  }
452
453  /// \brief Returns a \c SparseMap class created from an appropriate
454  /// \c std::map
455
456  /// This function just returns a \c SparseMap class created from an
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);
464  }
465
466  /// @}
467
468  /// \addtogroup map_adaptors
469  /// @{
470
471  /// Composition of two maps
472
473  /// This \ref concepts::ReadMap "read-only map" returns the
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>.
480  ///
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;
493  public:
494    ///\e
495    typedef typename M2::Key Key;
496    ///\e
497    typedef typename M1::Value Value;
498
499    /// Constructor
500    ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
501
502    ///\e
503    typename MapTraits<M1>::ConstReturnValue
504    operator[](const Key &k) const { return _m1[_m2[k]]; }
505  };
506
507  /// Returns a \c ComposeMap class
508
509  /// This function just returns a \c ComposeMap class.
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);
519  }
520
521
522  /// Combination of two maps using an STL (binary) functor.
523
524  /// This \ref concepts::ReadMap "read-only map" takes two maps and a
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>.
533  ///
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,
545           typename V = typename F::result_type>
546  class CombineMap : public MapBase<typename M1::Key, V> {
547    const M1 &_m1;
548    const M2 &_m2;
549    F _f;
550  public:
551    ///\e
552    typedef typename M1::Key Key;
553    ///\e
554    typedef V Value;
555
556    /// Constructor
557    CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
558      : _m1(m1), _m2(m2), _f(f) {}
559    ///\e
560    Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
561  };
562
563  /// Returns a \c CombineMap class
564
565  /// This function just returns a \c CombineMap class.
566  ///
567  /// For example, if \c m1 and \c m2 are both maps with \c double
568  /// values, then
569  /// \code
570  ///   combineMap(m1,m2,std::plus<double>())
571  /// \endcode
572  /// is equivalent to
573  /// \code
574  ///   addMap(m1,m2)
575  /// \endcode
576  ///
577  /// This function is specialized for adaptable binary function
578  /// classes and C++ functions.
579  ///
580  /// \relates CombineMap
581  template<typename M1, typename M2, typename F, typename V>
582  inline CombineMap<M1, M2, F, V>
583  combineMap(const M1 &m1, const M2 &m2, const F &f) {
584    return CombineMap<M1, M2, F, V>(m1,m2,f);
585  }
586
587  template<typename M1, typename M2, typename F>
588  inline CombineMap<M1, M2, F, typename F::result_type>
589  combineMap(const M1 &m1, const M2 &m2, const F &f) {
590    return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
591  }
592
593  template<typename M1, typename M2, typename K1, typename K2, typename V>
594  inline CombineMap<M1, M2, V (*)(K1, K2), V>
595  combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
596    return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
597  }
598
599
600  /// Converts an STL style (unary) functor to a map
601
602  /// This \ref concepts::ReadMap "read-only map" returns the value
603  /// of a given functor. Actually, it just wraps the functor and
604  /// provides the \c Key and \c Value typedefs.
605  ///
606  /// Template parameters \c K and \c V will become its \c Key and
607  /// \c Value. In most cases they have to be given explicitly because
608  /// a functor typically does not provide \c argument_type and
609  /// \c result_type typedefs.
610  /// Parameter \c F is the type of the used functor.
611  ///
612  /// The simplest way of using this map is through the functorToMap()
613  /// function.
614  ///
615  /// \sa MapToFunctor
616  template<typename F,
617           typename K = typename F::argument_type,
618           typename V = typename F::result_type>
619  class FunctorToMap : public MapBase<K, V> {
620    F _f;
621  public:
622    ///\e
623    typedef K Key;
624    ///\e
625    typedef V Value;
626
627    /// Constructor
628    FunctorToMap(const F &f = F()) : _f(f) {}
629    ///\e
630    Value operator[](const Key &k) const { return _f(k); }
631  };
632
633  /// Returns a \c FunctorToMap class
634
635  /// This function just returns a \c FunctorToMap class.
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;
676  public:
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;
684
685    /// Constructor
686    MapToFunctor(const M &m) : _m(m) {}
687    ///\e
688    Value operator()(const Key &k) const { return _m[k]; }
689    ///\e
690    Value operator[](const Key &k) const { return _m[k]; }
691  };
692
693  /// Returns a \c MapToFunctor class
694
695  /// This function just returns a \c MapToFunctor class.
696  /// \relates MapToFunctor
697  template<typename M>
698  inline MapToFunctor<M> mapToFunctor(const M &m) {
699    return MapToFunctor<M>(m);
700  }
701
702
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 to the \ref concepts::ReadMap "ReadMap" concept.
711  ///
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:
718    ///\e
719    typedef typename M::Key Key;
720    ///\e
721    typedef V Value;
722
723    /// Constructor
724
725    /// Constructor.
726    /// \param m The underlying map.
727    ConvertMap(const M &m) : _m(m) {}
728
729    ///\e
730    Value operator[](const Key &k) const { return _m[k]; }
731  };
732
733  /// Returns a \c ConvertMap class
734
735  /// This function just returns a \c ConvertMap class.
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.
749  ///
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:
761    ///\e
762    typedef typename M1::Key Key;
763    ///\e
764    typedef typename M1::Value Value;
765
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
774  /// Returns a \c ForkMap class
775
776  /// This function just returns a \c ForkMap class.
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
786  /// This \ref concepts::ReadMap "read-only map" returns the sum
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>
804  class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
805    const M1 &_m1;
806    const M2 &_m2;
807  public:
808    ///\e
809    typedef typename M1::Key Key;
810    ///\e
811    typedef typename M1::Value Value;
812
813    /// Constructor
814    AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
815    ///\e
816    Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
817  };
818
819  /// Returns an \c AddMap class
820
821  /// This function just returns an \c AddMap class.
822  ///
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) {
830    return AddMap<M1, M2>(m1,m2);
831  }
832
833
834  /// Difference of two maps
835
836  /// This \ref concepts::ReadMap "read-only map" returns the difference
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.
841  ///
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>.
847  ///
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:
857    ///\e
858    typedef typename M1::Key Key;
859    ///\e
860    typedef typename M1::Value Value;
861
862    /// Constructor
863    SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
864    ///\e
865    Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
866  };
867
868  /// Returns a \c SubMap class
869
870  /// This function just returns a \c SubMap class.
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
885  /// This \ref concepts::ReadMap "read-only map" returns the product
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:
907    ///\e
908    typedef typename M1::Key Key;
909    ///\e
910    typedef typename M1::Value Value;
911
912    /// Constructor
913    MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
914    ///\e
915    Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
916  };
917
918  /// Returns a \c MulMap class
919
920  /// This function just returns a \c MulMap class.
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
935  /// This \ref concepts::ReadMap "read-only map" returns the quotient
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:
956    ///\e
957    typedef typename M1::Key Key;
958    ///\e
959    typedef typename M1::Value Value;
960
961    /// Constructor
962    DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
963    ///\e
964    Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
965  };
966
967  /// Returns a \c DivMap class
968
969  /// This function just returns a \c DivMap class.
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
984  /// This \ref concepts::ReadMap "read-only map" returns the sum of
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>
1003  class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
1004    const M &_m;
1005    C _v;
1006  public:
1007    ///\e
1008    typedef typename M::Key Key;
1009    ///\e
1010    typedef typename M::Value Value;
1011
1012    /// Constructor
1013
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) {}
1018    ///\e
1019    Value operator[](const Key &k) const { return _m[k]+_v; }
1020  };
1021
1022  /// Shifts a map with a constant (read-write version).
1023
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.
1028  ///
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>
1034  class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
1035    M &_m;
1036    C _v;
1037  public:
1038    ///\e
1039    typedef typename M::Key Key;
1040    ///\e
1041    typedef typename M::Value Value;
1042
1043    /// Constructor
1044
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) {}
1049    ///\e
1050    Value operator[](const Key &k) const { return _m[k]+_v; }
1051    ///\e
1052    void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
1053  };
1054
1055  /// Returns a \c ShiftMap class
1056
1057  /// This function just returns a \c ShiftMap class.
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) {
1066    return ShiftMap<M, C>(m,v);
1067  }
1068
1069  /// Returns a \c ShiftWriteMap class
1070
1071  /// This function just returns a \c ShiftWriteMap class.
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) {
1081    return ShiftWriteMap<M, C>(m,v);
1082  }
1083
1084
1085  /// Scales a map with a constant.
1086
1087  /// This \ref concepts::ReadMap "read-only map" returns the value of
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.
1090  ///
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
1100  ///
1101  /// The simplest way of using this map is through the scaleMap()
1102  /// function.
1103  ///
1104  /// \sa ScaleWriteMap
1105  template<typename M, typename C = typename M::Value>
1106  class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
1107    const M &_m;
1108    C _v;
1109  public:
1110    ///\e
1111    typedef typename M::Key Key;
1112    ///\e
1113    typedef typename M::Value Value;
1114
1115    /// Constructor
1116
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) {}
1121    ///\e
1122    Value operator[](const Key &k) const { return _v*_m[k]; }
1123  };
1124
1125  /// Scales a map with a constant (read-write version).
1126
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.
1132  ///
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>
1138  class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
1139    M &_m;
1140    C _v;
1141  public:
1142    ///\e
1143    typedef typename M::Key Key;
1144    ///\e
1145    typedef typename M::Value Value;
1146
1147    /// Constructor
1148
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) {}
1153    ///\e
1154    Value operator[](const Key &k) const { return _v*_m[k]; }
1155    ///\e
1156    void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
1157  };
1158
1159  /// Returns a \c ScaleMap class
1160
1161  /// This function just returns a \c ScaleMap class.
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) {
1170    return ScaleMap<M, C>(m,v);
1171  }
1172
1173  /// Returns a \c ScaleWriteMap class
1174
1175  /// This function just returns a \c ScaleWriteMap class.
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) {
1185    return ScaleWriteMap<M, C>(m,v);
1186  }
1187
1188
1189  /// Negative of a map
1190
1191  /// This \ref concepts::ReadMap "read-only map" returns the negative
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.
1194  ///
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
1203  ///
1204  /// The simplest way of using this map is through the negMap()
1205  /// function.
1206  ///
1207  /// \sa NegWriteMap
1208  template<typename M>
1209  class NegMap : public MapBase<typename M::Key, typename M::Value> {
1210    const M& _m;
1211  public:
1212    ///\e
1213    typedef typename M::Key Key;
1214    ///\e
1215    typedef typename M::Value Value;
1216
1217    /// Constructor
1218    NegMap(const M &m) : _m(m) {}
1219    ///\e
1220    Value operator[](const Key &k) const { return -_m[k]; }
1221  };
1222
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.
1242  ///
1243  /// \sa NegMap
1244  template<typename M>
1245  class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
1246    M &_m;
1247  public:
1248    ///\e
1249    typedef typename M::Key Key;
1250    ///\e
1251    typedef typename M::Value Value;
1252
1253    /// Constructor
1254    NegWriteMap(M &m) : _m(m) {}
1255    ///\e
1256    Value operator[](const Key &k) const { return -_m[k]; }
1257    ///\e
1258    void set(const Key &k, const Value &v) { _m.set(k, -v); }
1259  };
1260
1261  /// Returns a \c NegMap class
1262
1263  /// This function just returns a \c NegMap class.
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>
1270  inline NegMap<M> negMap(const M &m) {
1271    return NegMap<M>(m);
1272  }
1273
1274  /// Returns a \c NegWriteMap class
1275
1276  /// This function just returns a \c NegWriteMap class.
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) {
1285    return NegWriteMap<M>(m);
1286  }
1287
1288
1289  /// Absolute value of a map
1290
1291  /// This \ref concepts::ReadMap "read-only map" returns the absolute
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>
1300  class AbsMap : public MapBase<typename M::Key, typename M::Value> {
1301    const M &_m;
1302  public:
1303    ///\e
1304    typedef typename M::Key Key;
1305    ///\e
1306    typedef typename M::Value Value;
1307
1308    /// Constructor
1309    AbsMap(const M &m) : _m(m) {}
1310    ///\e
1311    Value operator[](const Key &k) const {
1312      Value tmp = _m[k];
1313      return tmp >= 0 ? tmp : -tmp;
1314    }
1315
1316  };
1317
1318  /// Returns an \c AbsMap class
1319
1320  /// This function just returns an \c AbsMap class.
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>
1329  inline AbsMap<M> absMap(const M &m) {
1330    return AbsMap<M>(m);
1331  }
1332
1333  /// @}
1334
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:
1359    ///\e
1360    typedef K Key;
1361    ///\e
1362    typedef bool Value;
1363
1364    /// Gives back \c true.
1365    Value operator[](const Key&) const { return true; }
1366  };
1367
1368  /// Returns a \c TrueMap class
1369
1370  /// This function just returns a \c TrueMap class.
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:
1397    ///\e
1398    typedef K Key;
1399    ///\e
1400    typedef bool Value;
1401
1402    /// Gives back \c false.
1403    Value operator[](const Key&) const { return false; }
1404  };
1405
1406  /// Returns a \c FalseMap class
1407
1408  /// This function just returns a \c FalseMap class.
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:
1443    ///\e
1444    typedef typename M1::Key Key;
1445    ///\e
1446    typedef bool Value;
1447
1448    /// Constructor
1449    AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1450    ///\e
1451    Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
1452  };
1453
1454  /// Returns an \c AndMap class
1455
1456  /// This function just returns an \c AndMap class.
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:
1492    ///\e
1493    typedef typename M1::Key Key;
1494    ///\e
1495    typedef bool Value;
1496
1497    /// Constructor
1498    OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1499    ///\e
1500    Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
1501  };
1502
1503  /// Returns an \c OrMap class
1504
1505  /// This function just returns an \c OrMap class.
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
1517
1518  /// Logical 'not' of a map
1519
1520  /// This \ref concepts::ReadMap "read-only map" returns the logical
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.
1523  ///
1524  /// The simplest way of using this map is through the notMap()
1525  /// function.
1526  ///
1527  /// \sa NotWriteMap
1528  template <typename M>
1529  class NotMap : public MapBase<typename M::Key, bool> {
1530    const M &_m;
1531  public:
1532    ///\e
1533    typedef typename M::Key Key;
1534    ///\e
1535    typedef bool Value;
1536
1537    /// Constructor
1538    NotMap(const M &m) : _m(m) {}
1539    ///\e
1540    Value operator[](const Key &k) const { return !_m[k]; }
1541  };
1542
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.
1550  ///
1551  /// The simplest way of using this map is through the notWriteMap()
1552  /// function.
1553  ///
1554  /// \sa NotMap
1555  template <typename M>
1556  class NotWriteMap : public MapBase<typename M::Key, bool> {
1557    M &_m;
1558  public:
1559    ///\e
1560    typedef typename M::Key Key;
1561    ///\e
1562    typedef bool Value;
1563
1564    /// Constructor
1565    NotWriteMap(M &m) : _m(m) {}
1566    ///\e
1567    Value operator[](const Key &k) const { return !_m[k]; }
1568    ///\e
1569    void set(const Key &k, bool v) { _m.set(k, !v); }
1570  };
1571
1572  /// Returns a \c NotMap class
1573
1574  /// This function just returns a \c NotMap class.
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>
1581  inline NotMap<M> notMap(const M &m) {
1582    return NotMap<M>(m);
1583  }
1584
1585  /// Returns a \c NotWriteMap class
1586
1587  /// This function just returns a \c NotWriteMap class.
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) {
1596    return NotWriteMap<M>(m);
1597  }
1598
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:
1623    ///\e
1624    typedef typename M1::Key Key;
1625    ///\e
1626    typedef bool Value;
1627
1628    /// Constructor
1629    EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1630    ///\e
1631    Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
1632  };
1633
1634  /// Returns an \c EqualMap class
1635
1636  /// This function just returns an \c EqualMap class.
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:
1672    ///\e
1673    typedef typename M1::Key Key;
1674    ///\e
1675    typedef bool Value;
1676
1677    /// Constructor
1678    LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1679    ///\e
1680    Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
1681  };
1682
1683  /// Returns an \c LessMap class
1684
1685  /// This function just returns an \c LessMap class.
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
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
1713  /// @}
1714
1715  /// \addtogroup maps
1716  /// @{
1717
1718  /// \brief Writable bool map for logging each \c true assigned element
1719  ///
1720  /// A \ref concepts::WriteMap "writable" bool map for logging
1721  /// each \c true assigned element, i.e it copies subsequently each
1722  /// keys set to \c true to the given iterator.
1723  /// The most important usage of it is storing certain nodes or arcs
1724  /// that were marked \c true by an algorithm.
1725  ///
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
1730  /// easily done with LoggerBoolMap.
1731  ///
1732  /// The simplest way of using this map is through the loggerBoolMap()
1733  /// function.
1734  ///
1735  /// \tparam IT The type of the iterator.
1736  /// \tparam KEY The key type of the map. The default value set
1737  /// according to the iterator type should work in most cases.
1738  ///
1739  /// \note The container of the iterator must contain enough space
1740  /// for the elements or the iterator should be an inserter iterator.
1741#ifdef DOXYGEN
1742  template <typename IT, typename KEY>
1743#else
1744  template <typename IT,
1745            typename KEY = typename _maps_bits::IteratorTraits<IT>::Value>
1746#endif
1747  class LoggerBoolMap : public MapBase<KEY, bool> {
1748  public:
1749
1750    ///\e
1751    typedef KEY Key;
1752    ///\e
1753    typedef bool Value;
1754    ///\e
1755    typedef IT Iterator;
1756
1757    /// Constructor
1758    LoggerBoolMap(Iterator it)
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
1772    void set(const Key& key, Value value) {
1773      if (value) {
1774        *_end++ = key;
1775      }
1776    }
1777
1778  private:
1779    Iterator _begin;
1780    Iterator _end;
1781  };
1782
1783  /// Returns a \c LoggerBoolMap class
1784
1785  /// This function just returns a \c LoggerBoolMap class.
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;
1793  ///   dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s);
1794  /// \endcode
1795  /// \code
1796  ///   std::vector<Node> v(countNodes(g));
1797  ///   dfs(g).processedMap(loggerBoolMap(v.begin())).run(s);
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  ///
1803  /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
1804  /// it cannot be used when a readable map is needed, for example, as
1805  /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms.
1806  ///
1807  /// \relates LoggerBoolMap
1808  template<typename Iterator>
1809  inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
1810    return LoggerBoolMap<Iterator>(it);
1811  }
1812
1813  /// @}
1814
1815  /// \addtogroup graph_maps
1816  /// @{
1817
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
1829  /// class \c InverseMap or with the \c operator()() member.
1830  ///
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  ///
1835  /// \see RangeIdMap
1836  template <typename GR, typename K>
1837  class IdMap : public MapBase<K, int> {
1838  public:
1839    /// The graph type of IdMap.
1840    typedef GR Graph;
1841    typedef GR Digraph;
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.
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
1859    /// \brief Gives back the \e item by its id.
1860    ///
1861    /// Gives back the \e item by its id.
1862    Item operator()(int id) { return _graph->fromId(id, Item()); }
1863
1864  private:
1865    const Graph* _graph;
1866
1867  public:
1868
1869    /// \brief The inverse map type of IdMap.
1870    ///
1871    /// The inverse map type of IdMap. The subscript operator gives back
1872    /// an item by its id.
1873    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
1874    /// \see inverse()
1875    class InverseMap {
1876    public:
1877
1878      /// \brief Constructor.
1879      ///
1880      /// Constructor for creating an id-to-item map.
1881      explicit InverseMap(const Graph& graph) : _graph(&graph) {}
1882
1883      /// \brief Constructor.
1884      ///
1885      /// Constructor for creating an id-to-item map.
1886      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
1887
1888      /// \brief Gives back an item by its id.
1889      ///
1890      /// Gives back an item by its id.
1891      Item operator[](int id) const { return _graph->fromId(id, Item());}
1892
1893    private:
1894      const Graph* _graph;
1895    };
1896
1897    /// \brief Gives back the inverse of the map.
1898    ///
1899    /// Gives back the inverse of the IdMap.
1900    InverseMap inverse() const { return InverseMap(*_graph);}
1901  };
1902
1903  /// \brief Returns an \c IdMap class.
1904  ///
1905  /// This function just returns an \c IdMap class.
1906  /// \relates IdMap
1907  template <typename K, typename GR>
1908  inline IdMap<GR, K> idMap(const GR& graph) {
1909    return IdMap<GR, K>(graph);
1910  }
1911
1912  /// \brief General cross reference graph map type.
1913
1914  /// This class provides simple invertable graph maps.
1915  /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
1916  /// and if a key is set to a new value, then stores it in the inverse map.
1917  /// The graph items can be accessed by their values either using
1918  /// \c InverseMap or \c operator()(), and the values of the map can be
1919  /// accessed with an STL compatible forward iterator (\c ValueIt).
1920  ///
1921  /// This map is intended to be used when all associated values are
1922  /// different (the map is actually invertable) or there are only a few
1923  /// items with the same value.
1924  /// Otherwise consider to use \c IterableValueMap, which is more
1925  /// suitable and more efficient for such cases. It provides iterators
1926  /// to traverse the items with the same associated value, but
1927  /// it does not have \c InverseMap.
1928  ///
1929  /// This type is not reference map, so it cannot be modified with
1930  /// the subscript operator.
1931  ///
1932  /// \tparam GR The graph type.
1933  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
1934  /// \c GR::Edge).
1935  /// \tparam V The value type of the map.
1936  ///
1937  /// \see IterableValueMap
1938  template <typename GR, typename K, typename V>
1939  class CrossRefMap
1940    : protected ItemSetTraits<GR, K>::template Map<V>::Type {
1941  private:
1942
1943    typedef typename ItemSetTraits<GR, K>::
1944      template Map<V>::Type Map;
1945
1946    typedef std::multimap<V, K> Container;
1947    Container _inv_map;
1948
1949  public:
1950
1951    /// The graph type of CrossRefMap.
1952    typedef GR Graph;
1953    typedef GR Digraph;
1954    /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
1955    typedef K Item;
1956    /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
1957    typedef K Key;
1958    /// The value type of CrossRefMap.
1959    typedef V Value;
1960
1961    /// \brief Constructor.
1962    ///
1963    /// Construct a new CrossRefMap for the given graph.
1964    explicit CrossRefMap(const Graph& graph) : Map(graph) {}
1965
1966    /// \brief Forward iterator for values.
1967    ///
1968    /// This iterator is an STL compatible forward
1969    /// iterator on the values of the map. The values can
1970    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
1971    /// They are considered with multiplicity, so each value is
1972    /// traversed for each item it is assigned to.
1973    class ValueIt
1974      : public std::iterator<std::forward_iterator_tag, Value> {
1975      friend class CrossRefMap;
1976    private:
1977      ValueIt(typename Container::const_iterator _it)
1978        : it(_it) {}
1979    public:
1980
1981      /// Constructor
1982      ValueIt() {}
1983
1984      /// \e
1985      ValueIt& operator++() { ++it; return *this; }
1986      /// \e
1987      ValueIt operator++(int) {
1988        ValueIt tmp(*this);
1989        operator++();
1990        return tmp;
1991      }
1992
1993      /// \e
1994      const Value& operator*() const { return it->first; }
1995      /// \e
1996      const Value* operator->() const { return &(it->first); }
1997
1998      /// \e
1999      bool operator==(ValueIt jt) const { return it == jt.it; }
2000      /// \e
2001      bool operator!=(ValueIt jt) const { return it != jt.it; }
2002
2003    private:
2004      typename Container::const_iterator it;
2005    };
2006
2007    /// Alias for \c ValueIt
2008    typedef ValueIt ValueIterator;
2009
2010    /// \brief Returns an iterator to the first value.
2011    ///
2012    /// Returns an STL compatible iterator to the
2013    /// first value of the map. The values of the
2014    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
2015    /// range.
2016    ValueIt beginValue() const {
2017      return ValueIt(_inv_map.begin());
2018    }
2019
2020    /// \brief Returns an iterator after the last value.
2021    ///
2022    /// Returns an STL compatible iterator after the
2023    /// last value of the map. The values of the
2024    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
2025    /// range.
2026    ValueIt endValue() const {
2027      return ValueIt(_inv_map.end());
2028    }
2029
2030    /// \brief Sets the value associated with the given key.
2031    ///
2032    /// Sets the value associated with the given key.
2033    void set(const Key& key, const Value& val) {
2034      Value oldval = Map::operator[](key);
2035      typename Container::iterator it;
2036      for (it = _inv_map.equal_range(oldval).first;
2037           it != _inv_map.equal_range(oldval).second; ++it) {
2038        if (it->second == key) {
2039          _inv_map.erase(it);
2040          break;
2041        }
2042      }
2043      _inv_map.insert(std::make_pair(val, key));
2044      Map::set(key, val);
2045    }
2046
2047    /// \brief Returns the value associated with the given key.
2048    ///
2049    /// Returns the value associated with the given key.
2050    typename MapTraits<Map>::ConstReturnValue
2051    operator[](const Key& key) const {
2052      return Map::operator[](key);
2053    }
2054
2055    /// \brief Gives back an item by its value.
2056    ///
2057    /// This function gives back an item that is assigned to
2058    /// the given value or \c INVALID if no such item exists.
2059    /// If there are more items with the same associated value,
2060    /// only one of them is returned.
2061    Key operator()(const Value& val) const {
2062      typename Container::const_iterator it = _inv_map.find(val);
2063      return it != _inv_map.end() ? it->second : INVALID;
2064    }
2065
2066    /// \brief Returns the number of items with the given value.
2067    ///
2068    /// This function returns the number of items with the given value
2069    /// associated with it.
2070    int count(const Value &val) const {
2071      return _inv_map.count(val);
2072    }
2073
2074  protected:
2075
2076    /// \brief Erase the key from the map and the inverse map.
2077    ///
2078    /// Erase the key from the map and the inverse map. It is called by the
2079    /// \c AlterationNotifier.
2080    virtual void erase(const Key& key) {
2081      Value val = Map::operator[](key);
2082      typename Container::iterator it;
2083      for (it = _inv_map.equal_range(val).first;
2084           it != _inv_map.equal_range(val).second; ++it) {
2085        if (it->second == key) {
2086          _inv_map.erase(it);
2087          break;
2088        }
2089      }
2090      Map::erase(key);
2091    }
2092
2093    /// \brief Erase more keys from the map and the inverse map.
2094    ///
2095    /// Erase more keys from the map and the inverse map. It is called by the
2096    /// \c AlterationNotifier.
2097    virtual void erase(const std::vector<Key>& keys) {
2098      for (int i = 0; i < int(keys.size()); ++i) {
2099        Value val = Map::operator[](keys[i]);
2100        typename Container::iterator it;
2101        for (it = _inv_map.equal_range(val).first;
2102             it != _inv_map.equal_range(val).second; ++it) {
2103          if (it->second == keys[i]) {
2104            _inv_map.erase(it);
2105            break;
2106          }
2107        }
2108      }
2109      Map::erase(keys);
2110    }
2111
2112    /// \brief Clear the keys from the map and the inverse map.
2113    ///
2114    /// Clear the keys from the map and the inverse map. It is called by the
2115    /// \c AlterationNotifier.
2116    virtual void clear() {
2117      _inv_map.clear();
2118      Map::clear();
2119    }
2120
2121  public:
2122
2123    /// \brief The inverse map type of CrossRefMap.
2124    ///
2125    /// The inverse map type of CrossRefMap. The subscript operator gives
2126    /// back an item by its value.
2127    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
2128    /// \see inverse()
2129    class InverseMap {
2130    public:
2131      /// \brief Constructor
2132      ///
2133      /// Constructor of the InverseMap.
2134      explicit InverseMap(const CrossRefMap& inverted)
2135        : _inverted(inverted) {}
2136
2137      /// The value type of the InverseMap.
2138      typedef typename CrossRefMap::Key Value;
2139      /// The key type of the InverseMap.
2140      typedef typename CrossRefMap::Value Key;
2141
2142      /// \brief Subscript operator.
2143      ///
2144      /// Subscript operator. It gives back an item
2145      /// that is assigned to the given value or \c INVALID
2146      /// if no such item exists.
2147      Value operator[](const Key& key) const {
2148        return _inverted(key);
2149      }
2150
2151    private:
2152      const CrossRefMap& _inverted;
2153    };
2154
2155    /// \brief Gives back the inverse of the map.
2156    ///
2157    /// Gives back the inverse of the CrossRefMap.
2158    InverseMap inverse() const {
2159      return InverseMap(*this);
2160    }
2161
2162  };
2163
2164  /// \brief Provides continuous and unique id for the
2165  /// items of a graph.
2166  ///
2167  /// RangeIdMap provides a unique and continuous
2168  /// id for each item of a given type (\c Node, \c Arc or
2169  /// \c Edge) in a graph. This id is
2170  ///  - \b unique: different items get different ids,
2171  ///  - \b continuous: the range of the ids is the set of integers
2172  ///    between 0 and \c n-1, where \c n is the number of the items of
2173  ///    this type (\c Node, \c Arc or \c Edge).
2174  ///  - So, the ids can change when deleting an item of the same type.
2175  ///
2176  /// Thus this id is not (necessarily) the same as what can get using
2177  /// the \c id() function of the graph or \ref IdMap.
2178  /// This map can be inverted with its member class \c InverseMap,
2179  /// or with the \c operator()() member.
2180  ///
2181  /// \tparam GR The graph type.
2182  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
2183  /// \c GR::Edge).
2184  ///
2185  /// \see IdMap
2186  template <typename GR, typename K>
2187  class RangeIdMap
2188    : protected ItemSetTraits<GR, K>::template Map<int>::Type {
2189
2190    typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Map;
2191
2192  public:
2193    /// The graph type of RangeIdMap.
2194    typedef GR Graph;
2195    typedef GR Digraph;
2196    /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge).
2197    typedef K Item;
2198    /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge).
2199    typedef K Key;
2200    /// The value type of RangeIdMap.
2201    typedef int Value;
2202
2203    /// \brief Constructor.
2204    ///
2205    /// Constructor.
2206    explicit RangeIdMap(const Graph& gr) : Map(gr) {
2207      Item it;
2208      const typename Map::Notifier* nf = Map::notifier();
2209      for (nf->first(it); it != INVALID; nf->next(it)) {
2210        Map::set(it, _inv_map.size());
2211        _inv_map.push_back(it);
2212      }
2213    }
2214
2215  protected:
2216
2217    /// \brief Adds a new key to the map.
2218    ///
2219    /// Add a new key to the map. It is called by the
2220    /// \c AlterationNotifier.
2221    virtual void add(const Item& item) {
2222      Map::add(item);
2223      Map::set(item, _inv_map.size());
2224      _inv_map.push_back(item);
2225    }
2226
2227    /// \brief Add more new keys to the map.
2228    ///
2229    /// Add more new keys to the map. It is called by the
2230    /// \c AlterationNotifier.
2231    virtual void add(const std::vector<Item>& items) {
2232      Map::add(items);
2233      for (int i = 0; i < int(items.size()); ++i) {
2234        Map::set(items[i], _inv_map.size());
2235        _inv_map.push_back(items[i]);
2236      }
2237    }
2238
2239    /// \brief Erase the key from the map.
2240    ///
2241    /// Erase the key from the map. It is called by the
2242    /// \c AlterationNotifier.
2243    virtual void erase(const Item& item) {
2244      Map::set(_inv_map.back(), Map::operator[](item));
2245      _inv_map[Map::operator[](item)] = _inv_map.back();
2246      _inv_map.pop_back();
2247      Map::erase(item);
2248    }
2249
2250    /// \brief Erase more keys from the map.
2251    ///
2252    /// Erase more keys from the map. It is called by the
2253    /// \c AlterationNotifier.
2254    virtual void erase(const std::vector<Item>& items) {
2255      for (int i = 0; i < int(items.size()); ++i) {
2256        Map::set(_inv_map.back(), Map::operator[](items[i]));
2257        _inv_map[Map::operator[](items[i])] = _inv_map.back();
2258        _inv_map.pop_back();
2259      }
2260      Map::erase(items);
2261    }
2262
2263    /// \brief Build the unique map.
2264    ///
2265    /// Build the unique map. It is called by the
2266    /// \c AlterationNotifier.
2267    virtual void build() {
2268      Map::build();
2269      Item it;
2270      const typename Map::Notifier* nf = Map::notifier();
2271      for (nf->first(it); it != INVALID; nf->next(it)) {
2272        Map::set(it, _inv_map.size());
2273        _inv_map.push_back(it);
2274      }
2275    }
2276
2277    /// \brief Clear the keys from the map.
2278    ///
2279    /// Clear the keys from the map. It is called by the
2280    /// \c AlterationNotifier.
2281    virtual void clear() {
2282      _inv_map.clear();
2283      Map::clear();
2284    }
2285
2286  public:
2287
2288    /// \brief Returns the maximal value plus one.
2289    ///
2290    /// Returns the maximal value plus one in the map.
2291    unsigned int size() const {
2292      return _inv_map.size();
2293    }
2294
2295    /// \brief Swaps the position of the two items in the map.
2296    ///
2297    /// Swaps the position of the two items in the map.
2298    void swap(const Item& p, const Item& q) {
2299      int pi = Map::operator[](p);
2300      int qi = Map::operator[](q);
2301      Map::set(p, qi);
2302      _inv_map[qi] = p;
2303      Map::set(q, pi);
2304      _inv_map[pi] = q;
2305    }
2306
2307    /// \brief Gives back the \e range \e id of the item
2308    ///
2309    /// Gives back the \e range \e id of the item.
2310    int operator[](const Item& item) const {
2311      return Map::operator[](item);
2312    }
2313
2314    /// \brief Gives back the item belonging to a \e range \e id
2315    ///
2316    /// Gives back the item belonging to the given \e range \e id.
2317    Item operator()(int id) const {
2318      return _inv_map[id];
2319    }
2320
2321  private:
2322
2323    typedef std::vector<Item> Container;
2324    Container _inv_map;
2325
2326  public:
2327
2328    /// \brief The inverse map type of RangeIdMap.
2329    ///
2330    /// The inverse map type of RangeIdMap. The subscript operator gives
2331    /// back an item by its \e range \e id.
2332    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
2333    class InverseMap {
2334    public:
2335      /// \brief Constructor
2336      ///
2337      /// Constructor of the InverseMap.
2338      explicit InverseMap(const RangeIdMap& inverted)
2339        : _inverted(inverted) {}
2340
2341
2342      /// The value type of the InverseMap.
2343      typedef typename RangeIdMap::Key Value;
2344      /// The key type of the InverseMap.
2345      typedef typename RangeIdMap::Value Key;
2346
2347      /// \brief Subscript operator.
2348      ///
2349      /// Subscript operator. It gives back the item
2350      /// that the given \e range \e id currently belongs to.
2351      Value operator[](const Key& key) const {
2352        return _inverted(key);
2353      }
2354
2355      /// \brief Size of the map.
2356      ///
2357      /// Returns the size of the map.
2358      unsigned int size() const {
2359        return _inverted.size();
2360      }
2361
2362    private:
2363      const RangeIdMap& _inverted;
2364    };
2365
2366    /// \brief Gives back the inverse of the map.
2367    ///
2368    /// Gives back the inverse of the RangeIdMap.
2369    const InverseMap inverse() const {
2370      return InverseMap(*this);
2371    }
2372  };
2373
2374  /// \brief Returns a \c RangeIdMap class.
2375  ///
2376  /// This function just returns an \c RangeIdMap class.
2377  /// \relates RangeIdMap
2378  template <typename K, typename GR>
2379  inline RangeIdMap<GR, K> rangeIdMap(const GR& graph) {
2380    return RangeIdMap<GR, K>(graph);
2381  }
2382
2383  /// \brief Dynamic iterable \c bool map.
2384  ///
2385  /// This class provides a special graph map type which can store a
2386  /// \c bool value for graph items (\c Node, \c Arc or \c Edge).
2387  /// For both \c true and \c false values it is possible to iterate on
2388  /// the keys mapped to the value.
2389  ///
2390  /// This type is a reference map, so it can be modified with the
2391  /// subscript operator.
2392  ///
2393  /// \tparam GR The graph type.
2394  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
2395  /// \c GR::Edge).
2396  ///
2397  /// \see IterableIntMap, IterableValueMap
2398  /// \see CrossRefMap
2399  template <typename GR, typename K>
2400  class IterableBoolMap
2401    : protected ItemSetTraits<GR, K>::template Map<int>::Type {
2402  private:
2403    typedef GR Graph;
2404
2405    typedef typename ItemSetTraits<GR, K>::ItemIt KeyIt;
2406    typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Parent;
2407
2408    std::vector<K> _array;
2409    int _sep;
2410
2411  public:
2412
2413    /// Indicates that the map is reference map.
2414    typedef True ReferenceMapTag;
2415
2416    /// The key type
2417    typedef K Key;
2418    /// The value type
2419    typedef bool Value;
2420    /// The const reference type.
2421    typedef const Value& ConstReference;
2422
2423  private:
2424
2425    int position(const Key& key) const {
2426      return Parent::operator[](key);
2427    }
2428
2429  public:
2430
2431    /// \brief Reference to the value of the map.
2432    ///
2433    /// This class is similar to the \c bool type. It can be converted to
2434    /// \c bool and it provides the same operators.
2435    class Reference {
2436      friend class IterableBoolMap;
2437    private:
2438      Reference(IterableBoolMap& map, const Key& key)
2439        : _key(key), _map(map) {}
2440    public:
2441
2442      Reference& operator=(const Reference& value) {
2443        _map.set(_key, static_cast<bool>(value));
2444         return *this;
2445      }
2446
2447      operator bool() const {
2448        return static_cast<const IterableBoolMap&>(_map)[_key];
2449      }
2450
2451      Reference& operator=(bool value) {
2452        _map.set(_key, value);
2453        return *this;
2454      }
2455      Reference& operator&=(bool value) {
2456        _map.set(_key, _map[_key] & value);
2457        return *this;
2458      }
2459      Reference& operator|=(bool value) {
2460        _map.set(_key, _map[_key] | value);
2461        return *this;
2462      }
2463      Reference& operator^=(bool value) {
2464        _map.set(_key, _map[_key] ^ value);
2465        return *this;
2466      }
2467    private:
2468      Key _key;
2469      IterableBoolMap& _map;
2470    };
2471
2472    /// \brief Constructor of the map with a default value.
2473    ///
2474    /// Constructor of the map with a default value.
2475    explicit IterableBoolMap(const Graph& graph, bool def = false)
2476      : Parent(graph) {
2477      typename Parent::Notifier* nf = Parent::notifier();
2478      Key it;
2479      for (nf->first(it); it != INVALID; nf->next(it)) {
2480        Parent::set(it, _array.size());
2481        _array.push_back(it);
2482      }
2483      _sep = (def ? _array.size() : 0);
2484    }
2485
2486    /// \brief Const subscript operator of the map.
2487    ///
2488    /// Const subscript operator of the map.
2489    bool operator[](const Key& key) const {
2490      return position(key) < _sep;
2491    }
2492
2493    /// \brief Subscript operator of the map.
2494    ///
2495    /// Subscript operator of the map.
2496    Reference operator[](const Key& key) {
2497      return Reference(*this, key);
2498    }
2499
2500    /// \brief Set operation of the map.
2501    ///
2502    /// Set operation of the map.
2503    void set(const Key& key, bool value) {
2504      int pos = position(key);
2505      if (value) {
2506        if (pos < _sep) return;
2507        Key tmp = _array[_sep];
2508        _array[_sep] = key;
2509        Parent::set(key, _sep);
2510        _array[pos] = tmp;
2511        Parent::set(tmp, pos);
2512        ++_sep;
2513      } else {
2514        if (pos >= _sep) return;
2515        --_sep;
2516        Key tmp = _array[_sep];
2517        _array[_sep] = key;
2518        Parent::set(key, _sep);
2519        _array[pos] = tmp;
2520        Parent::set(tmp, pos);
2521      }
2522    }
2523
2524    /// \brief Set all items.
2525    ///
2526    /// Set all items in the map.
2527    /// \note Constant time operation.
2528    void setAll(bool value) {
2529      _sep = (value ? _array.size() : 0);
2530    }
2531
2532    /// \brief Returns the number of the keys mapped to \c true.
2533    ///
2534    /// Returns the number of the keys mapped to \c true.
2535    int trueNum() const {
2536      return _sep;
2537    }
2538
2539    /// \brief Returns the number of the keys mapped to \c false.
2540    ///
2541    /// Returns the number of the keys mapped to \c false.
2542    int falseNum() const {
2543      return _array.size() - _sep;
2544    }
2545
2546    /// \brief Iterator for the keys mapped to \c true.
2547    ///
2548    /// Iterator for the keys mapped to \c true. It works
2549    /// like a graph item iterator, it can be converted to
2550    /// the key type of the map, incremented with \c ++ operator, and
2551    /// if the iterator leaves the last valid key, it will be equal to
2552    /// \c INVALID.
2553    class TrueIt : public Key {
2554    public:
2555      typedef Key Parent;
2556
2557      /// \brief Creates an iterator.
2558      ///
2559      /// Creates an iterator. It iterates on the
2560      /// keys mapped to \c true.
2561      /// \param map The IterableBoolMap.
2562      explicit TrueIt(const IterableBoolMap& map)
2563        : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID),
2564          _map(&map) {}
2565
2566      /// \brief Invalid constructor \& conversion.
2567      ///
2568      /// This constructor initializes the iterator to be invalid.
2569      /// \sa Invalid for more details.
2570      TrueIt(Invalid) : Parent(INVALID), _map(0) {}
2571
2572      /// \brief Increment operator.
2573      ///
2574      /// Increment operator.
2575      TrueIt& operator++() {
2576        int pos = _map->position(*this);
2577        Parent::operator=(pos > 0 ? _map->_array[pos - 1] : INVALID);
2578        return *this;
2579      }
2580
2581    private:
2582      const IterableBoolMap* _map;
2583    };
2584
2585    /// \brief STL style iterator for the keys mapped to \c true.
2586    ///
2587    /// This is an STL style wrapper for \ref TrueIt.
2588    /// It can be used in range-based for loops, STL algorithms, etc.
2589    LemonRangeWrapper1<TrueIt, IterableBoolMap>
2590    trueKeys() {
2591      return LemonRangeWrapper1<TrueIt, IterableBoolMap>(*this);
2592    }
2593
2594
2595    /// \brief Iterator for the keys mapped to \c false.
2596    ///
2597    /// Iterator for the keys mapped to \c false. It works
2598    /// like a graph item iterator, it can be converted to
2599    /// the key type of the map, incremented with \c ++ operator, and
2600    /// if the iterator leaves the last valid key, it will be equal to
2601    /// \c INVALID.
2602    class FalseIt : public Key {
2603    public:
2604      typedef Key Parent;
2605
2606      /// \brief Creates an iterator.
2607      ///
2608      /// Creates an iterator. It iterates on the
2609      /// keys mapped to \c false.
2610      /// \param map The IterableBoolMap.
2611      explicit FalseIt(const IterableBoolMap& map)
2612        : Parent(map._sep < int(map._array.size()) ?
2613                 map._array.back() : INVALID), _map(&map) {}
2614
2615      /// \brief Invalid constructor \& conversion.
2616      ///
2617      /// This constructor initializes the iterator to be invalid.
2618      /// \sa Invalid for more details.
2619      FalseIt(Invalid) : Parent(INVALID), _map(0) {}
2620
2621      /// \brief Increment operator.
2622      ///
2623      /// Increment operator.
2624      FalseIt& operator++() {
2625        int pos = _map->position(*this);
2626        Parent::operator=(pos > _map->_sep ? _map->_array[pos - 1] : INVALID);
2627        return *this;
2628      }
2629
2630    private:
2631      const IterableBoolMap* _map;
2632    };
2633
2634    /// \brief STL style iterator for the keys mapped to \c false.
2635    ///
2636    /// This is an STL style wrapper for \ref FalseIt.
2637    /// It can be used in range-based for loops, STL algorithms, etc.
2638    LemonRangeWrapper1<FalseIt, IterableBoolMap>
2639    falseKeys() {
2640      return LemonRangeWrapper1<FalseIt, IterableBoolMap>(*this);
2641    }
2642
2643
2644    /// \brief Iterator for the keys mapped to a given value.
2645    ///
2646    /// Iterator for the keys mapped to a given value. It works
2647    /// like a graph item iterator, it can be converted to
2648    /// the key type of the map, incremented with \c ++ operator, and
2649    /// if the iterator leaves the last valid key, it will be equal to
2650    /// \c INVALID.
2651    class ItemIt : public Key {
2652    public:
2653      typedef Key Parent;
2654
2655      /// \brief Creates an iterator with a value.
2656      ///
2657      /// Creates an iterator with a value. It iterates on the
2658      /// keys mapped to the given value.
2659      /// \param map The IterableBoolMap.
2660      /// \param value The value.
2661      ItemIt(const IterableBoolMap& map, bool value)
2662        : Parent(value ?
2663                 (map._sep > 0 ?
2664                  map._array[map._sep - 1] : INVALID) :
2665                 (map._sep < int(map._array.size()) ?
2666                  map._array.back() : INVALID)), _map(&map) {}
2667
2668      /// \brief Invalid constructor \& conversion.
2669      ///
2670      /// This constructor initializes the iterator to be invalid.
2671      /// \sa Invalid for more details.
2672      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
2673
2674      /// \brief Increment operator.
2675      ///
2676      /// Increment operator.
2677      ItemIt& operator++() {
2678        int pos = _map->position(*this);
2679        int _sep = pos >= _map->_sep ? _map->_sep : 0;
2680        Parent::operator=(pos > _sep ? _map->_array[pos - 1] : INVALID);
2681        return *this;
2682      }
2683
2684    private:
2685      const IterableBoolMap* _map;
2686    };
2687
2688    /// \brief STL style iterator for the keys mapped to a given value.
2689    ///
2690    /// This is an STL style wrapper for \ref ItemIt.
2691    /// It can be used in range-based for loops, STL algorithms, etc.
2692    LemonRangeWrapper2<ItemIt, IterableBoolMap, bool>
2693    items(bool value) {
2694      return LemonRangeWrapper2<ItemIt, IterableBoolMap, bool>(*this, value);
2695    }
2696
2697  protected:
2698
2699    virtual void add(const Key& key) {
2700      Parent::add(key);
2701      Parent::set(key, _array.size());
2702      _array.push_back(key);
2703    }
2704
2705    virtual void add(const std::vector<Key>& keys) {
2706      Parent::add(keys);
2707      for (int i = 0; i < int(keys.size()); ++i) {
2708        Parent::set(keys[i], _array.size());
2709        _array.push_back(keys[i]);
2710      }
2711    }
2712
2713    virtual void erase(const Key& key) {
2714      int pos = position(key);
2715      if (pos < _sep) {
2716        --_sep;
2717        Parent::set(_array[_sep], pos);
2718        _array[pos] = _array[_sep];
2719        Parent::set(_array.back(), _sep);
2720        _array[_sep] = _array.back();
2721        _array.pop_back();
2722      } else {
2723        Parent::set(_array.back(), pos);
2724        _array[pos] = _array.back();
2725        _array.pop_back();
2726      }
2727      Parent::erase(key);
2728    }
2729
2730    virtual void erase(const std::vector<Key>& keys) {
2731      for (int i = 0; i < int(keys.size()); ++i) {
2732        int pos = position(keys[i]);
2733        if (pos < _sep) {
2734          --_sep;
2735          Parent::set(_array[_sep], pos);
2736          _array[pos] = _array[_sep];
2737          Parent::set(_array.back(), _sep);
2738          _array[_sep] = _array.back();
2739          _array.pop_back();
2740        } else {
2741          Parent::set(_array.back(), pos);
2742          _array[pos] = _array.back();
2743          _array.pop_back();
2744        }
2745      }
2746      Parent::erase(keys);
2747    }
2748
2749    virtual void build() {
2750      Parent::build();
2751      typename Parent::Notifier* nf = Parent::notifier();
2752      Key it;
2753      for (nf->first(it); it != INVALID; nf->next(it)) {
2754        Parent::set(it, _array.size());
2755        _array.push_back(it);
2756      }
2757      _sep = 0;
2758    }
2759
2760    virtual void clear() {
2761      _array.clear();
2762      _sep = 0;
2763      Parent::clear();
2764    }
2765
2766  };
2767
2768
2769  namespace _maps_bits {
2770    template <typename Item>
2771    struct IterableIntMapNode {
2772      IterableIntMapNode() : value(-1) {}
2773      IterableIntMapNode(int _value) : value(_value) {}
2774      Item prev, next;
2775      int value;
2776    };
2777  }
2778
2779  /// \brief Dynamic iterable integer map.
2780  ///
2781  /// This class provides a special graph map type which can store an
2782  /// integer value for graph items (\c Node, \c Arc or \c Edge).
2783  /// For each non-negative value it is possible to iterate on the keys
2784  /// mapped to the value.
2785  ///
2786  /// This map is intended to be used with small integer values, for which
2787  /// it is efficient, and supports iteration only for non-negative values.
2788  /// If you need large values and/or iteration for negative integers,
2789  /// consider to use \ref IterableValueMap instead.
2790  ///
2791  /// This type is a reference map, so it can be modified with the
2792  /// subscript operator.
2793  ///
2794  /// \note The size of the data structure depends on the largest
2795  /// value in the map.
2796  ///
2797  /// \tparam GR The graph type.
2798  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
2799  /// \c GR::Edge).
2800  ///
2801  /// \see IterableBoolMap, IterableValueMap
2802  /// \see CrossRefMap
2803  template <typename GR, typename K>
2804  class IterableIntMap
2805    : protected ItemSetTraits<GR, K>::
2806        template Map<_maps_bits::IterableIntMapNode<K> >::Type {
2807  public:
2808    typedef typename ItemSetTraits<GR, K>::
2809      template Map<_maps_bits::IterableIntMapNode<K> >::Type Parent;
2810
2811    /// The key type
2812    typedef K Key;
2813    /// The value type
2814    typedef int Value;
2815    /// The graph type
2816    typedef GR Graph;
2817
2818    /// \brief Constructor of the map.
2819    ///
2820    /// Constructor of the map. It sets all values to -1.
2821    explicit IterableIntMap(const Graph& graph)
2822      : Parent(graph) {}
2823
2824    /// \brief Constructor of the map with a given value.
2825    ///
2826    /// Constructor of the map with a given value.
2827    explicit IterableIntMap(const Graph& graph, int value)
2828      : Parent(graph, _maps_bits::IterableIntMapNode<K>(value)) {
2829      if (value >= 0) {
2830        for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
2831          lace(it);
2832        }
2833      }
2834    }
2835
2836  private:
2837
2838    void unlace(const Key& key) {
2839      typename Parent::Value& node = Parent::operator[](key);
2840      if (node.value < 0) return;
2841      if (node.prev != INVALID) {
2842        Parent::operator[](node.prev).next = node.next;
2843      } else {
2844        _first[node.value] = node.next;
2845      }
2846      if (node.next != INVALID) {
2847        Parent::operator[](node.next).prev = node.prev;
2848      }
2849      while (!_first.empty() && _first.back() == INVALID) {
2850        _first.pop_back();
2851      }
2852    }
2853
2854    void lace(const Key& key) {
2855      typename Parent::Value& node = Parent::operator[](key);
2856      if (node.value < 0) return;
2857      if (node.value >= int(_first.size())) {
2858        _first.resize(node.value + 1, INVALID);
2859      }
2860      node.prev = INVALID;
2861      node.next = _first[node.value];
2862      if (node.next != INVALID) {
2863        Parent::operator[](node.next).prev = key;
2864      }
2865      _first[node.value] = key;
2866    }
2867
2868  public:
2869
2870    /// Indicates that the map is reference map.
2871    typedef True ReferenceMapTag;
2872
2873    /// \brief Reference to the value of the map.
2874    ///
2875    /// This class is similar to the \c int type. It can
2876    /// be converted to \c int and it has the same operators.
2877    class Reference {
2878      friend class IterableIntMap;
2879    private:
2880      Reference(IterableIntMap& map, const Key& key)
2881        : _key(key), _map(map) {}
2882    public:
2883
2884      Reference& operator=(const Reference& value) {
2885        _map.set(_key, static_cast<const int&>(value));
2886         return *this;
2887      }
2888
2889      operator const int&() const {
2890        return static_cast<const IterableIntMap&>(_map)[_key];
2891      }
2892
2893      Reference& operator=(int value) {
2894        _map.set(_key, value);
2895        return *this;
2896      }
2897      Reference& operator++() {
2898        _map.set(_key, _map[_key] + 1);
2899        return *this;
2900      }
2901      int operator++(int) {
2902        int value = _map[_key];
2903        _map.set(_key, value + 1);
2904        return value;
2905      }
2906      Reference& operator--() {
2907        _map.set(_key, _map[_key] - 1);
2908        return *this;
2909      }
2910      int operator--(int) {
2911        int value = _map[_key];
2912        _map.set(_key, value - 1);
2913        return value;
2914      }
2915      Reference& operator+=(int value) {
2916        _map.set(_key, _map[_key] + value);
2917        return *this;
2918      }
2919      Reference& operator-=(int value) {
2920        _map.set(_key, _map[_key] - value);
2921        return *this;
2922      }
2923      Reference& operator*=(int value) {
2924        _map.set(_key, _map[_key] * value);
2925        return *this;
2926      }
2927      Reference& operator/=(int value) {
2928        _map.set(_key, _map[_key] / value);
2929        return *this;
2930      }
2931      Reference& operator%=(int value) {
2932        _map.set(_key, _map[_key] % value);
2933        return *this;
2934      }
2935      Reference& operator&=(int value) {
2936        _map.set(_key, _map[_key] & value);
2937        return *this;
2938      }
2939      Reference& operator|=(int value) {
2940        _map.set(_key, _map[_key] | value);
2941        return *this;
2942      }
2943      Reference& operator^=(int value) {
2944        _map.set(_key, _map[_key] ^ value);
2945        return *this;
2946      }
2947      Reference& operator<<=(int value) {
2948        _map.set(_key, _map[_key] << value);
2949        return *this;
2950      }
2951      Reference& operator>>=(int value) {
2952        _map.set(_key, _map[_key] >> value);
2953        return *this;
2954      }
2955
2956    private:
2957      Key _key;
2958      IterableIntMap& _map;
2959    };
2960
2961    /// The const reference type.
2962    typedef const Value& ConstReference;
2963
2964    /// \brief Gives back the maximal value plus one.
2965    ///
2966    /// Gives back the maximal value plus one.
2967    int size() const {
2968      return _first.size();
2969    }
2970
2971    /// \brief Set operation of the map.
2972    ///
2973    /// Set operation of the map.
2974    void set(const Key& key, const Value& value) {
2975      unlace(key);
2976      Parent::operator[](key).value = value;
2977      lace(key);
2978    }
2979
2980    /// \brief Const subscript operator of the map.
2981    ///
2982    /// Const subscript operator of the map.
2983    const Value& operator[](const Key& key) const {
2984      return Parent::operator[](key).value;
2985    }
2986
2987    /// \brief Subscript operator of the map.
2988    ///
2989    /// Subscript operator of the map.
2990    Reference operator[](const Key& key) {
2991      return Reference(*this, key);
2992    }
2993
2994    /// \brief Iterator for the keys with the same value.
2995    ///
2996    /// Iterator for the keys with the same value. It works
2997    /// like a graph item iterator, it can be converted to
2998    /// the item type of the map, incremented with \c ++ operator, and
2999    /// if the iterator leaves the last valid item, it will be equal to
3000    /// \c INVALID.
3001    class ItemIt : public Key {
3002    public:
3003      typedef Key Parent;
3004
3005      /// \brief Invalid constructor \& conversion.
3006      ///
3007      /// This constructor initializes the iterator to be invalid.
3008      /// \sa Invalid for more details.
3009      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
3010
3011      /// \brief Creates an iterator with a value.
3012      ///
3013      /// Creates an iterator with a value. It iterates on the
3014      /// keys mapped to the given value.
3015      /// \param map The IterableIntMap.
3016      /// \param value The value.
3017      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
3018        if (value < 0 || value >= int(_map->_first.size())) {
3019          Parent::operator=(INVALID);
3020        } else {
3021          Parent::operator=(_map->_first[value]);
3022        }
3023      }
3024
3025      /// \brief Increment operator.
3026      ///
3027      /// Increment operator.
3028      ItemIt& operator++() {
3029        Parent::operator=(_map->IterableIntMap::Parent::
3030                          operator[](static_cast<Parent&>(*this)).next);
3031        return *this;
3032      }
3033
3034    private:
3035      const IterableIntMap* _map;
3036    };
3037
3038    /// \brief STL style iterator for the keys with the same value.
3039    ///
3040    /// This is an STL style wrapper for \ref ItemIt.
3041    /// It can be used in range-based for loops, STL algorithms, etc.
3042    LemonRangeWrapper2<ItemIt, IterableIntMap, int>
3043    items(int value) {
3044      return LemonRangeWrapper2<ItemIt, IterableIntMap, int>(*this, value);
3045    }
3046
3047
3048  protected:
3049
3050    virtual void erase(const Key& key) {
3051      unlace(key);
3052      Parent::erase(key);
3053    }
3054
3055    virtual void erase(const std::vector<Key>& keys) {
3056      for (int i = 0; i < int(keys.size()); ++i) {
3057        unlace(keys[i]);
3058      }
3059      Parent::erase(keys);
3060    }
3061
3062    virtual void clear() {
3063      _first.clear();
3064      Parent::clear();
3065    }
3066
3067  private:
3068    std::vector<Key> _first;
3069  };
3070
3071  namespace _maps_bits {
3072    template <typename Item, typename Value>
3073    struct IterableValueMapNode {
3074      IterableValueMapNode(Value _value = Value()) : value(_value) {}
3075      Item prev, next;
3076      Value value;
3077    };
3078  }
3079
3080  /// \brief Dynamic iterable map for comparable values.
3081  ///
3082  /// This class provides a special graph map type which can store a
3083  /// comparable value for graph items (\c Node, \c Arc or \c Edge).
3084  /// For each value it is possible to iterate on the keys mapped to
3085  /// the value (\c ItemIt), and the values of the map can be accessed
3086  /// with an STL compatible forward iterator (\c ValueIt).
3087  /// The map stores a linked list for each value, which contains
3088  /// the items mapped to the value, and the used values are stored
3089  /// in balanced binary tree (\c std::map).
3090  ///
3091  /// \ref IterableBoolMap and \ref IterableIntMap are similar classes
3092  /// specialized for \c bool and \c int values, respectively.
3093  ///
3094  /// This type is not reference map, so it cannot be modified with
3095  /// the subscript operator.
3096  ///
3097  /// \tparam GR The graph type.
3098  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
3099  /// \c GR::Edge).
3100  /// \tparam V The value type of the map. It can be any comparable
3101  /// value type.
3102  ///
3103  /// \see IterableBoolMap, IterableIntMap
3104  /// \see CrossRefMap
3105  template <typename GR, typename K, typename V>
3106  class IterableValueMap
3107    : protected ItemSetTraits<GR, K>::
3108        template Map<_maps_bits::IterableValueMapNode<K, V> >::Type {
3109  public:
3110    typedef typename ItemSetTraits<GR, K>::
3111      template Map<_maps_bits::IterableValueMapNode<K, V> >::Type Parent;
3112
3113    /// The key type
3114    typedef K Key;
3115    /// The value type
3116    typedef V Value;
3117    /// The graph type
3118    typedef GR Graph;
3119
3120  public:
3121
3122    /// \brief Constructor of the map with a given value.
3123    ///
3124    /// Constructor of the map with a given value.
3125    explicit IterableValueMap(const Graph& graph,
3126                              const Value& value = Value())
3127      : Parent(graph, _maps_bits::IterableValueMapNode<K, V>(value)) {
3128      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
3129        lace(it);
3130      }
3131    }
3132
3133  protected:
3134
3135    void unlace(const Key& key) {
3136      typename Parent::Value& node = Parent::operator[](key);
3137      if (node.prev != INVALID) {
3138        Parent::operator[](node.prev).next = node.next;
3139      } else {
3140        if (node.next != INVALID) {
3141          _first[node.value] = node.next;
3142        } else {
3143          _first.erase(node.value);
3144        }
3145      }
3146      if (node.next != INVALID) {
3147        Parent::operator[](node.next).prev = node.prev;
3148      }
3149    }
3150
3151    void lace(const Key& key) {
3152      typename Parent::Value& node = Parent::operator[](key);
3153      typename std::map<Value, Key>::iterator it = _first.find(node.value);
3154      if (it == _first.end()) {
3155        node.prev = node.next = INVALID;
3156        _first.insert(std::make_pair(node.value, key));
3157      } else {
3158        node.prev = INVALID;
3159        node.next = it->second;
3160        if (node.next != INVALID) {
3161          Parent::operator[](node.next).prev = key;
3162        }
3163        it->second = key;
3164      }
3165    }
3166
3167  public:
3168
3169    /// \brief Forward iterator for values.
3170    ///
3171    /// This iterator is an STL compatible forward
3172    /// iterator on the values of the map. The values can
3173    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
3174    class ValueIt
3175      : public std::iterator<std::forward_iterator_tag, Value> {
3176      friend class IterableValueMap;
3177    private:
3178      ValueIt(typename std::map<Value, Key>::const_iterator _it)
3179        : it(_it) {}
3180    public:
3181
3182      /// Constructor
3183      ValueIt() {}
3184
3185      /// \e
3186      ValueIt& operator++() { ++it; return *this; }
3187      /// \e
3188      ValueIt operator++(int) {
3189        ValueIt tmp(*this);
3190        operator++();
3191        return tmp;
3192      }
3193
3194      /// \e
3195      const Value& operator*() const { return it->first; }
3196      /// \e
3197      const Value* operator->() const { return &(it->first); }
3198
3199      /// \e
3200      bool operator==(ValueIt jt) const { return it == jt.it; }
3201      /// \e
3202      bool operator!=(ValueIt jt) const { return it != jt.it; }
3203
3204    private:
3205      typename std::map<Value, Key>::const_iterator it;
3206    };
3207
3208    /// \brief Returns an iterator to the first value.
3209    ///
3210    /// Returns an STL compatible iterator to the
3211    /// first value of the map. The values of the
3212    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
3213    /// range.
3214    ValueIt beginValue() const {
3215      return ValueIt(_first.begin());
3216    }
3217
3218    /// \brief Returns an iterator after the last value.
3219    ///
3220    /// Returns an STL compatible iterator after the
3221    /// last value of the map. The values of the
3222    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
3223    /// range.
3224    ValueIt endValue() const {
3225      return ValueIt(_first.end());
3226    }
3227
3228    /// \brief Set operation of the map.
3229    ///
3230    /// Set operation of the map.
3231    void set(const Key& key, const Value& value) {
3232      unlace(key);
3233      Parent::operator[](key).value = value;
3234      lace(key);
3235    }
3236
3237    /// \brief Const subscript operator of the map.
3238    ///
3239    /// Const subscript operator of the map.
3240    const Value& operator[](const Key& key) const {
3241      return Parent::operator[](key).value;
3242    }
3243
3244    /// \brief Iterator for the keys with the same value.
3245    ///
3246    /// Iterator for the keys with the same value. It works
3247    /// like a graph item iterator, it can be converted to
3248    /// the item type of the map, incremented with \c ++ operator, and
3249    /// if the iterator leaves the last valid item, it will be equal to
3250    /// \c INVALID.
3251    class ItemIt : public Key {
3252    public:
3253      typedef Key Parent;
3254
3255      /// \brief Invalid constructor \& conversion.
3256      ///
3257      /// This constructor initializes the iterator to be invalid.
3258      /// \sa Invalid for more details.
3259      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
3260
3261      /// \brief Creates an iterator with a value.
3262      ///
3263      /// Creates an iterator with a value. It iterates on the
3264      /// keys which have the given value.
3265      /// \param map The IterableValueMap
3266      /// \param value The value
3267      ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
3268        typename std::map<Value, Key>::const_iterator it =
3269          map._first.find(value);
3270        if (it == map._first.end()) {
3271          Parent::operator=(INVALID);
3272        } else {
3273          Parent::operator=(it->second);
3274        }
3275      }
3276
3277      /// \brief Increment operator.
3278      ///
3279      /// Increment Operator.
3280      ItemIt& operator++() {
3281        Parent::operator=(_map->IterableValueMap::Parent::
3282                          operator[](static_cast<Parent&>(*this)).next);
3283        return *this;
3284      }
3285
3286
3287    private:
3288      const IterableValueMap* _map;
3289    };
3290
3291    /// \brief STL style iterator for the keys with the same value.
3292    ///
3293    /// This is an STL style wrapper for \ref ItemIt.
3294    /// It can be used in range-based for loops, STL algorithms, etc.
3295    LemonRangeWrapper2<ItemIt, IterableValueMap, V>
3296    items(const V& value) {
3297      return LemonRangeWrapper2<ItemIt, IterableValueMap, V>(*this, value);
3298    }
3299
3300
3301  protected:
3302
3303    virtual void add(const Key& key) {
3304      Parent::add(key);
3305      lace(key);
3306    }
3307
3308    virtual void add(const std::vector<Key>& keys) {
3309      Parent::add(keys);
3310      for (int i = 0; i < int(keys.size()); ++i) {
3311        lace(keys[i]);
3312      }
3313    }
3314
3315    virtual void erase(const Key& key) {
3316      unlace(key);
3317      Parent::erase(key);
3318    }
3319
3320    virtual void erase(const std::vector<Key>& keys) {
3321      for (int i = 0; i < int(keys.size()); ++i) {
3322        unlace(keys[i]);
3323      }
3324      Parent::erase(keys);
3325    }
3326
3327    virtual void build() {
3328      Parent::build();
3329      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
3330        lace(it);
3331      }
3332    }
3333
3334    virtual void clear() {
3335      _first.clear();
3336      Parent::clear();
3337    }
3338
3339  private:
3340    std::map<Value, Key> _first;
3341  };
3342
3343  /// \brief Map of the source nodes of arcs in a digraph.
3344  ///
3345  /// SourceMap provides access for the source node of each arc in a digraph,
3346  /// which is returned by the \c source() function of the digraph.
3347  /// \tparam GR The digraph type.
3348  /// \see TargetMap
3349  template <typename GR>
3350  class SourceMap {
3351  public:
3352
3353    /// The key type (the \c Arc type of the digraph).
3354    typedef typename GR::Arc Key;
3355    /// The value type (the \c Node type of the digraph).
3356    typedef typename GR::Node Value;
3357
3358    /// \brief Constructor
3359    ///
3360    /// Constructor.
3361    /// \param digraph The digraph that the map belongs to.
3362    explicit SourceMap(const GR& digraph) : _graph(digraph) {}
3363
3364    /// \brief Returns the source node of the given arc.
3365    ///
3366    /// Returns the source node of the given arc.
3367    Value operator[](const Key& arc) const {
3368      return _graph.source(arc);
3369    }
3370
3371  private:
3372    const GR& _graph;
3373  };
3374
3375  /// \brief Returns a \c SourceMap class.
3376  ///
3377  /// This function just returns an \c SourceMap class.
3378  /// \relates SourceMap
3379  template <typename GR>
3380  inline SourceMap<GR> sourceMap(const GR& graph) {
3381    return SourceMap<GR>(graph);
3382  }
3383
3384  /// \brief Map of the target nodes of arcs in a digraph.
3385  ///
3386  /// TargetMap provides access for the target node of each arc in a digraph,
3387  /// which is returned by the \c target() function of the digraph.
3388  /// \tparam GR The digraph type.
3389  /// \see SourceMap
3390  template <typename GR>
3391  class TargetMap {
3392  public:
3393
3394    /// The key type (the \c Arc type of the digraph).
3395    typedef typename GR::Arc Key;
3396    /// The value type (the \c Node type of the digraph).
3397    typedef typename GR::Node Value;
3398
3399    /// \brief Constructor
3400    ///
3401    /// Constructor.
3402    /// \param digraph The digraph that the map belongs to.
3403    explicit TargetMap(const GR& digraph) : _graph(digraph) {}
3404
3405    /// \brief Returns the target node of the given arc.
3406    ///
3407    /// Returns the target node of the given arc.
3408    Value operator[](const Key& e) const {
3409      return _graph.target(e);
3410    }
3411
3412  private:
3413    const GR& _graph;
3414  };
3415
3416  /// \brief Returns a \c TargetMap class.
3417  ///
3418  /// This function just returns a \c TargetMap class.
3419  /// \relates TargetMap
3420  template <typename GR>
3421  inline TargetMap<GR> targetMap(const GR& graph) {
3422    return TargetMap<GR>(graph);
3423  }
3424
3425  /// \brief Map of the "forward" directed arc view of edges in a graph.
3426  ///
3427  /// ForwardMap provides access for the "forward" directed arc view of
3428  /// each edge in a graph, which is returned by the \c direct() function
3429  /// of the graph with \c true parameter.
3430  /// \tparam GR The graph type.
3431  /// \see BackwardMap
3432  template <typename GR>
3433  class ForwardMap {
3434  public:
3435
3436    /// The key type (the \c Edge type of the digraph).
3437    typedef typename GR::Edge Key;
3438    /// The value type (the \c Arc type of the digraph).
3439    typedef typename GR::Arc Value;
3440
3441    /// \brief Constructor
3442    ///
3443    /// Constructor.
3444    /// \param graph The graph that the map belongs to.
3445    explicit ForwardMap(const GR& graph) : _graph(graph) {}
3446
3447    /// \brief Returns the "forward" directed arc view of the given edge.
3448    ///
3449    /// Returns the "forward" directed arc view of the given edge.
3450    Value operator[](const Key& key) const {
3451      return _graph.direct(key, true);
3452    }
3453
3454  private:
3455    const GR& _graph;
3456  };
3457
3458  /// \brief Returns a \c ForwardMap class.
3459  ///
3460  /// This function just returns an \c ForwardMap class.
3461  /// \relates ForwardMap
3462  template <typename GR>
3463  inline ForwardMap<GR> forwardMap(const GR& graph) {
3464    return ForwardMap<GR>(graph);
3465  }
3466
3467  /// \brief Map of the "backward" directed arc view of edges in a graph.
3468  ///
3469  /// BackwardMap provides access for the "backward" directed arc view of
3470  /// each edge in a graph, which is returned by the \c direct() function
3471  /// of the graph with \c false parameter.
3472  /// \tparam GR The graph type.
3473  /// \see ForwardMap
3474  template <typename GR>
3475  class BackwardMap {
3476  public:
3477
3478    /// The key type (the \c Edge type of the digraph).
3479    typedef typename GR::Edge Key;
3480    /// The value type (the \c Arc type of the digraph).
3481    typedef typename GR::Arc Value;
3482
3483    /// \brief Constructor
3484    ///
3485    /// Constructor.
3486    /// \param graph The graph that the map belongs to.
3487    explicit BackwardMap(const GR& graph) : _graph(graph) {}
3488
3489    /// \brief Returns the "backward" directed arc view of the given edge.
3490    ///
3491    /// Returns the "backward" directed arc view of the given edge.
3492    Value operator[](const Key& key) const {
3493      return _graph.direct(key, false);
3494    }
3495
3496  private:
3497    const GR& _graph;
3498  };
3499
3500  /// \brief Returns a \c BackwardMap class
3501
3502  /// This function just returns a \c BackwardMap class.
3503  /// \relates BackwardMap
3504  template <typename GR>
3505  inline BackwardMap<GR> backwardMap(const GR& graph) {
3506    return BackwardMap<GR>(graph);
3507  }
3508
3509  /// \brief Map of the in-degrees of nodes in a digraph.
3510  ///
3511  /// This map returns the in-degree of a node. Once it is constructed,
3512  /// the degrees are stored in a standard \c NodeMap, so each query is done
3513  /// in constant time. On the other hand, the values are updated automatically
3514  /// whenever the digraph changes.
3515  ///
3516  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
3517  /// may provide alternative ways to modify the digraph.
3518  /// The correct behavior of InDegMap is not guarantied if these additional
3519  /// features are used. For example, the functions
3520  /// \ref ListDigraph::changeSource() "changeSource()",
3521  /// \ref ListDigraph::changeTarget() "changeTarget()" and
3522  /// \ref ListDigraph::reverseArc() "reverseArc()"
3523  /// of \ref ListDigraph will \e not update the degree values correctly.
3524  ///
3525  /// \sa OutDegMap
3526  template <typename GR>
3527  class InDegMap
3528    : protected ItemSetTraits<GR, typename GR::Arc>
3529      ::ItemNotifier::ObserverBase {
3530
3531  public:
3532
3533    /// The graph type of InDegMap
3534    typedef GR Graph;
3535    typedef GR Digraph;
3536    /// The key type
3537    typedef typename Digraph::Node Key;
3538    /// The value type
3539    typedef int Value;
3540
3541    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
3542    ::ItemNotifier::ObserverBase Parent;
3543
3544  private:
3545
3546    class AutoNodeMap
3547      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
3548    public:
3549
3550      typedef typename ItemSetTraits<Digraph, Key>::
3551      template Map<int>::Type Parent;
3552
3553      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
3554
3555      virtual void add(const Key& key) {
3556        Parent::add(key);
3557        Parent::set(key, 0);
3558      }
3559
3560      virtual void add(const std::vector<Key>& keys) {
3561        Parent::add(keys);
3562        for (int i = 0; i < int(keys.size()); ++i) {
3563          Parent::set(keys[i], 0);
3564        }
3565      }
3566
3567      virtual void build() {
3568        Parent::build();
3569        Key it;
3570        typename Parent::Notifier* nf = Parent::notifier();
3571        for (nf->first(it); it != INVALID; nf->next(it)) {
3572          Parent::set(it, 0);
3573        }
3574      }
3575    };
3576
3577  public:
3578
3579    /// \brief Constructor.
3580    ///
3581    /// Constructor for creating an in-degree map.
3582    explicit InDegMap(const Digraph& graph)
3583      : _digraph(graph), _deg(graph) {
3584      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
3585
3586      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
3587        _deg[it] = countInArcs(_digraph, it);
3588      }
3589    }
3590
3591    /// \brief Gives back the in-degree of a Node.
3592    ///
3593    /// Gives back the in-degree of a Node.
3594    int operator[](const Key& key) const {
3595      return _deg[key];
3596    }
3597
3598  protected:
3599
3600    typedef typename Digraph::Arc Arc;
3601
3602    virtual void add(const Arc& arc) {
3603      ++_deg[_digraph.target(arc)];
3604    }
3605
3606    virtual void add(const std::vector<Arc>& arcs) {
3607      for (int i = 0; i < int(arcs.size()); ++i) {
3608        ++_deg[_digraph.target(arcs[i])];
3609      }
3610    }
3611
3612    virtual void erase(const Arc& arc) {
3613      --_deg[_digraph.target(arc)];
3614    }
3615
3616    virtual void erase(const std::vector<Arc>& arcs) {
3617      for (int i = 0; i < int(arcs.size()); ++i) {
3618        --_deg[_digraph.target(arcs[i])];
3619      }
3620    }
3621
3622    virtual void build() {
3623      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
3624        _deg[it] = countInArcs(_digraph, it);
3625      }
3626    }
3627
3628    virtual void clear() {
3629      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
3630        _deg[it] = 0;
3631      }
3632    }
3633  private:
3634
3635    const Digraph& _digraph;
3636    AutoNodeMap _deg;
3637  };
3638
3639  /// \brief Map of the out-degrees of nodes in a digraph.
3640  ///
3641  /// This map returns the out-degree of a node. Once it is constructed,
3642  /// the degrees are stored in a standard \c NodeMap, so each query is done
3643  /// in constant time. On the other hand, the values are updated automatically
3644  /// whenever the digraph changes.
3645  ///
3646  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
3647  /// may provide alternative ways to modify the digraph.
3648  /// The correct behavior of OutDegMap is not guarantied if these additional
3649  /// features are used. For example, the functions
3650  /// \ref ListDigraph::changeSource() "changeSource()",
3651  /// \ref ListDigraph::changeTarget() "changeTarget()" and
3652  /// \ref ListDigraph::reverseArc() "reverseArc()"
3653  /// of \ref ListDigraph will \e not update the degree values correctly.
3654  ///
3655  /// \sa InDegMap
3656  template <typename GR>
3657  class OutDegMap
3658    : protected ItemSetTraits<GR, typename GR::Arc>
3659      ::ItemNotifier::ObserverBase {
3660
3661  public:
3662
3663    /// The graph type of OutDegMap
3664    typedef GR Graph;
3665    typedef GR Digraph;
3666    /// The key type
3667    typedef typename Digraph::Node Key;
3668    /// The value type
3669    typedef int Value;
3670
3671    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
3672    ::ItemNotifier::ObserverBase Parent;
3673
3674  private:
3675
3676    class AutoNodeMap
3677      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
3678    public:
3679
3680      typedef typename ItemSetTraits<Digraph, Key>::
3681      template Map<int>::Type Parent;
3682
3683      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
3684
3685      virtual void add(const Key& key) {
3686        Parent::add(key);
3687        Parent::set(key, 0);
3688      }
3689      virtual void add(const std::vector<Key>& keys) {
3690        Parent::add(keys);
3691        for (int i = 0; i < int(keys.size()); ++i) {
3692          Parent::set(keys[i], 0);
3693        }
3694      }
3695      virtual void build() {
3696        Parent::build();
3697        Key it;
3698        typename Parent::Notifier* nf = Parent::notifier();
3699        for (nf->first(it); it != INVALID; nf->next(it)) {
3700          Parent::set(it, 0);
3701        }
3702      }
3703    };
3704
3705  public:
3706
3707    /// \brief Constructor.
3708    ///
3709    /// Constructor for creating an out-degree map.
3710    explicit OutDegMap(const Digraph& graph)
3711      : _digraph(graph), _deg(graph) {
3712      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
3713
3714      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
3715        _deg[it] = countOutArcs(_digraph, it);
3716      }
3717    }
3718
3719    /// \brief Gives back the out-degree of a Node.
3720    ///
3721    /// Gives back the out-degree of a Node.
3722    int operator[](const Key& key) const {
3723      return _deg[key];
3724    }
3725
3726  protected:
3727
3728    typedef typename Digraph::Arc Arc;
3729
3730    virtual void add(const Arc& arc) {
3731      ++_deg[_digraph.source(arc)];
3732    }
3733
3734    virtual void add(const std::vector<Arc>& arcs) {
3735      for (int i = 0; i < int(arcs.size()); ++i) {
3736        ++_deg[_digraph.source(arcs[i])];
3737      }
3738    }
3739
3740    virtual void erase(const Arc& arc) {
3741      --_deg[_digraph.source(arc)];
3742    }
3743
3744    virtual void erase(const std::vector<Arc>& arcs) {
3745      for (int i = 0; i < int(arcs.size()); ++i) {
3746        --_deg[_digraph.source(arcs[i])];
3747      }
3748    }
3749
3750    virtual void build() {
3751      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
3752        _deg[it] = countOutArcs(_digraph, it);
3753      }
3754    }
3755
3756    virtual void clear() {
3757      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
3758        _deg[it] = 0;
3759      }
3760    }
3761  private:
3762
3763    const Digraph& _digraph;
3764    AutoNodeMap _deg;
3765  };
3766
3767  /// \brief Potential difference map
3768  ///
3769  /// PotentialDifferenceMap returns the difference between the potentials of
3770  /// the source and target nodes of each arc in a digraph, i.e. it returns
3771  /// \code
3772  ///   potential[gr.target(arc)] - potential[gr.source(arc)].
3773  /// \endcode
3774  /// \tparam GR The digraph type.
3775  /// \tparam POT A node map storing the potentials.
3776  template <typename GR, typename POT>
3777  class PotentialDifferenceMap {
3778  public:
3779    /// Key type
3780    typedef typename GR::Arc Key;
3781    /// Value type
3782    typedef typename POT::Value Value;
3783
3784    /// \brief Constructor
3785    ///
3786    /// Contructor of the map.
3787    explicit PotentialDifferenceMap(const GR& gr,
3788                                    const POT& potential)
3789      : _digraph(gr), _potential(potential) {}
3790
3791    /// \brief Returns the potential difference for the given arc.
3792    ///
3793    /// Returns the potential difference for the given arc, i.e.
3794    /// \code
3795    ///   potential[gr.target(arc)] - potential[gr.source(arc)].
3796    /// \endcode
3797    Value operator[](const Key& arc) const {
3798      return _potential[_digraph.target(arc)] -
3799        _potential[_digraph.source(arc)];
3800    }
3801
3802  private:
3803    const GR& _digraph;
3804    const POT& _potential;
3805  };
3806
3807  /// \brief Returns a PotentialDifferenceMap.
3808  ///
3809  /// This function just returns a PotentialDifferenceMap.
3810  /// \relates PotentialDifferenceMap
3811  template <typename GR, typename POT>
3812  PotentialDifferenceMap<GR, POT>
3813  potentialDifferenceMap(const GR& gr, const POT& potential) {
3814    return PotentialDifferenceMap<GR, POT>(gr, potential);
3815  }
3816
3817
3818  /// \brief Copy the values of a graph map to another map.
3819  ///
3820  /// This function copies the values of a graph map to another graph map.
3821  /// \c To::Key must be equal or convertible to \c From::Key and
3822  /// \c From::Value must be equal or convertible to \c To::Value.
3823  ///
3824  /// For example, an edge map of \c int value type can be copied to
3825  /// an arc map of \c double value type in an undirected graph, but
3826  /// an arc map cannot be copied to an edge map.
3827  /// Note that even a \ref ConstMap can be copied to a standard graph map,
3828  /// but \ref mapFill() can also be used for this purpose.
3829  ///
3830  /// \param gr The graph for which the maps are defined.
3831  /// \param from The map from which the values have to be copied.
3832  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
3833  /// \param to The map to which the values have to be copied.
3834  /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
3835  template <typename GR, typename From, typename To>
3836  void mapCopy(const GR& gr, const From& from, To& to) {
3837    typedef typename To::Key Item;
3838    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
3839
3840    for (ItemIt it(gr); it != INVALID; ++it) {
3841      to.set(it, from[it]);
3842    }
3843  }
3844
3845  /// \brief Compare two graph maps.
3846  ///
3847  /// This function compares the values of two graph maps. It returns
3848  /// \c true if the maps assign the same value for all items in the graph.
3849  /// The \c Key type of the maps (\c Node, \c Arc or \c Edge) must be equal
3850  /// and their \c Value types must be comparable using \c %operator==().
3851  ///
3852  /// \param gr The graph for which the maps are defined.
3853  /// \param map1 The first map.
3854  /// \param map2 The second map.
3855  template <typename GR, typename Map1, typename Map2>
3856  bool mapCompare(const GR& gr, const Map1& map1, const Map2& map2) {
3857    typedef typename Map2::Key Item;
3858    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
3859
3860    for (ItemIt it(gr); it != INVALID; ++it) {
3861      if (!(map1[it] == map2[it])) return false;
3862    }
3863    return true;
3864  }
3865
3866  /// \brief Return an item having minimum value of a graph map.
3867  ///
3868  /// This function returns an item (\c Node, \c Arc or \c Edge) having
3869  /// minimum value of the given graph map.
3870  /// If the item set is empty, it returns \c INVALID.
3871  ///
3872  /// \param gr The graph for which the map is defined.
3873  /// \param map The graph map.
3874  template <typename GR, typename Map>
3875  typename Map::Key mapMin(const GR& gr, const Map& map) {
3876    return mapMin(gr, map, std::less<typename Map::Value>());
3877  }
3878
3879  /// \brief Return an item having minimum value of a graph map.
3880  ///
3881  /// This function returns an item (\c Node, \c Arc or \c Edge) having
3882  /// minimum value of the given graph map.
3883  /// If the item set is empty, it returns \c INVALID.
3884  ///
3885  /// \param gr The graph for which the map is defined.
3886  /// \param map The graph map.
3887  /// \param comp Comparison function object.
3888  template <typename GR, typename Map, typename Comp>
3889  typename Map::Key mapMin(const GR& gr, const Map& map, const Comp& comp) {
3890    typedef typename Map::Key Item;
3891    typedef typename Map::Value Value;
3892    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
3893
3894    ItemIt min_item(gr);
3895    if (min_item == INVALID) return INVALID;
3896    Value min = map[min_item];
3897    for (ItemIt it(gr); it != INVALID; ++it) {
3898      if (comp(map[it], min)) {
3899        min = map[it];
3900        min_item = it;
3901      }
3902    }
3903    return min_item;
3904  }
3905
3906  /// \brief Return an item having maximum value of a graph map.
3907  ///
3908  /// This function returns an item (\c Node, \c Arc or \c Edge) having
3909  /// maximum value of the given graph map.
3910  /// If the item set is empty, it returns \c INVALID.
3911  ///
3912  /// \param gr The graph for which the map is defined.
3913  /// \param map The graph map.
3914  template <typename GR, typename Map>
3915  typename Map::Key mapMax(const GR& gr, const Map& map) {
3916    return mapMax(gr, map, std::less<typename Map::Value>());
3917  }
3918
3919  /// \brief Return an item having maximum value of a graph map.
3920  ///
3921  /// This function returns an item (\c Node, \c Arc or \c Edge) having
3922  /// maximum value of the given graph map.
3923  /// If the item set is empty, it returns \c INVALID.
3924  ///
3925  /// \param gr The graph for which the map is defined.
3926  /// \param map The graph map.
3927  /// \param comp Comparison function object.
3928  template <typename GR, typename Map, typename Comp>
3929  typename Map::Key mapMax(const GR& gr, const Map& map, const Comp& comp) {
3930    typedef typename Map::Key Item;
3931    typedef typename Map::Value Value;
3932    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
3933
3934    ItemIt max_item(gr);
3935    if (max_item == INVALID) return INVALID;
3936    Value max = map[max_item];
3937    for (ItemIt it(gr); it != INVALID; ++it) {
3938      if (comp(max, map[it])) {
3939        max = map[it];
3940        max_item = it;
3941      }
3942    }
3943    return max_item;
3944  }
3945
3946  /// \brief Return the minimum value of a graph map.
3947  ///
3948  /// This function returns the minimum value of the given graph map.
3949  /// The corresponding item set of the graph must not be empty.
3950  ///
3951  /// \param gr The graph for which the map is defined.
3952  /// \param map The graph map.
3953  template <typename GR, typename Map>
3954  typename Map::Value mapMinValue(const GR& gr, const Map& map) {
3955    return map[mapMin(gr, map, std::less<typename Map::Value>())];
3956  }
3957
3958  /// \brief Return the minimum value of a graph map.
3959  ///
3960  /// This function returns the minimum value of the given graph map.
3961  /// The corresponding item set of the graph must not be empty.
3962  ///
3963  /// \param gr The graph for which the map is defined.
3964  /// \param map The graph map.
3965  /// \param comp Comparison function object.
3966  template <typename GR, typename Map, typename Comp>
3967  typename Map::Value
3968  mapMinValue(const GR& gr, const Map& map, const Comp& comp) {
3969    return map[mapMin(gr, map, comp)];
3970  }
3971
3972  /// \brief Return the maximum value of a graph map.
3973  ///
3974  /// This function returns the maximum value of the given graph map.
3975  /// The corresponding item set of the graph must not be empty.
3976  ///
3977  /// \param gr The graph for which the map is defined.
3978  /// \param map The graph map.
3979  template <typename GR, typename Map>
3980  typename Map::Value mapMaxValue(const GR& gr, const Map& map) {
3981    return map[mapMax(gr, map, std::less<typename Map::Value>())];
3982  }
3983
3984  /// \brief Return the maximum value of a graph map.
3985  ///
3986  /// This function returns the maximum value of the given graph map.
3987  /// The corresponding item set of the graph must not be empty.
3988  ///
3989  /// \param gr The graph for which the map is defined.
3990  /// \param map The graph map.
3991  /// \param comp Comparison function object.
3992  template <typename GR, typename Map, typename Comp>
3993  typename Map::Value
3994  mapMaxValue(const GR& gr, const Map& map, const Comp& comp) {
3995    return map[mapMax(gr, map, comp)];
3996  }
3997
3998  /// \brief Return an item having a specified value in a graph map.
3999  ///
4000  /// This function returns an item (\c Node, \c Arc or \c Edge) having
4001  /// the specified assigned value in the given graph map.
4002  /// If no such item exists, it returns \c INVALID.
4003  ///
4004  /// \param gr The graph for which the map is defined.
4005  /// \param map The graph map.
4006  /// \param val The value that have to be found.
4007  template <typename GR, typename Map>
4008  typename Map::Key
4009  mapFind(const GR& gr, const Map& map, const typename Map::Value& val) {
4010    typedef typename Map::Key Item;
4011    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
4012
4013    for (ItemIt it(gr); it != INVALID; ++it) {
4014      if (map[it] == val) return it;
4015    }
4016    return INVALID;
4017  }
4018
4019  /// \brief Return an item having value for which a certain predicate is
4020  /// true in a graph map.
4021  ///
4022  /// This function returns an item (\c Node, \c Arc or \c Edge) having
4023  /// such assigned value for which the specified predicate is true
4024  /// in the given graph map.
4025  /// If no such item exists, it returns \c INVALID.
4026  ///
4027  /// \param gr The graph for which the map is defined.
4028  /// \param map The graph map.
4029  /// \param pred The predicate function object.
4030  template <typename GR, typename Map, typename Pred>
4031  typename Map::Key
4032  mapFindIf(const GR& gr, const Map& map, const Pred& pred) {
4033    typedef typename Map::Key Item;
4034    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
4035
4036    for (ItemIt it(gr); it != INVALID; ++it) {
4037      if (pred(map[it])) return it;
4038    }
4039    return INVALID;
4040  }
4041
4042  /// \brief Return the number of items having a specified value in a
4043  /// graph map.
4044  ///
4045  /// This function returns the number of items (\c Node, \c Arc or \c Edge)
4046  /// having the specified assigned value in the given graph map.
4047  ///
4048  /// \param gr The graph for which the map is defined.
4049  /// \param map The graph map.
4050  /// \param val The value that have to be counted.
4051  template <typename GR, typename Map>
4052  int mapCount(const GR& gr, const Map& map, const typename Map::Value& val) {
4053    typedef typename Map::Key Item;
4054    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
4055
4056    int cnt = 0;
4057    for (ItemIt it(gr); it != INVALID; ++it) {
4058      if (map[it] == val) ++cnt;
4059    }
4060    return cnt;
4061  }
4062
4063  /// \brief Return the number of items having values for which a certain
4064  /// predicate is true in a graph map.
4065  ///
4066  /// This function returns the number of items (\c Node, \c Arc or \c Edge)
4067  /// having such assigned values for which the specified predicate is true
4068  /// in the given graph map.
4069  ///
4070  /// \param gr The graph for which the map is defined.
4071  /// \param map The graph map.
4072  /// \param pred The predicate function object.
4073  template <typename GR, typename Map, typename Pred>
4074  int mapCountIf(const GR& gr, const Map& map, const Pred& pred) {
4075    typedef typename Map::Key Item;
4076    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
4077
4078    int cnt = 0;
4079    for (ItemIt it(gr); it != INVALID; ++it) {
4080      if (pred(map[it])) ++cnt;
4081    }
4082    return cnt;
4083  }
4084
4085  /// \brief Fill a graph map with a certain value.
4086  ///
4087  /// This function sets the specified value for all items (\c Node,
4088  /// \c Arc or \c Edge) in the given graph map.
4089  ///
4090  /// \param gr The graph for which the map is defined.
4091  /// \param map The graph map. It must conform to the
4092  /// \ref concepts::WriteMap "WriteMap" concept.
4093  /// \param val The value.
4094  template <typename GR, typename Map>
4095  void mapFill(const GR& gr, Map& map, const typename Map::Value& val) {
4096    typedef typename Map::Key Item;
4097    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
4098
4099    for (ItemIt it(gr); it != INVALID; ++it) {
4100      map.set(it, val);
4101    }
4102  }
4103
4104  /// @}
4105}
4106
4107#endif // LEMON_MAPS_H
Note: See TracBrowser for help on using the repository browser.