COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/maps.h @ 1210:da87dbdf3daf

Last change on this file since 1210:da87dbdf3daf was 1210:da87dbdf3daf, checked in by Alpar Juttner <alpar@…>, 14 months ago

Resolve deprecation warnings of gcc 9 (#633)

File size: 118.4 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    // RangeMap(const RangeMap&);
303
304    ///\e
305    Reference operator[](const Key &k) {
306      return _vector[k];
307    }
308
309    ///\e
310    ConstReference operator[](const Key &k) const {
311      return _vector[k];
312    }
313
314    ///\e
315    void set(const Key &k, const Value &v) {
316      _vector[k] = v;
317    }
318  };
319
320  /// Returns a \c RangeMap class
321
322  /// This function just returns a \c RangeMap class.
323  /// \relates RangeMap
324  template<typename V>
325  inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
326    return RangeMap<V>(size, value);
327  }
328
329  /// \brief Returns a \c RangeMap class created from an appropriate
330  /// \c std::vector
331
332  /// This function just returns a \c RangeMap class created from an
333  /// appropriate \c std::vector.
334  /// \relates RangeMap
335  template<typename V>
336  inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
337    return RangeMap<V>(vector);
338  }
339
340
341  /// Map type based on \c std::map
342
343  /// This map is essentially a wrapper for \c std::map with addition
344  /// that you can specify a default value for the keys that are not
345  /// stored actually. This value can be different from the default
346  /// contructed value (i.e. \c %Value()).
347  /// This type conforms to the \ref concepts::ReferenceMap "ReferenceMap"
348  /// concept.
349  ///
350  /// This map is useful if a default value should be assigned to most of
351  /// the keys and different values should be assigned only to a few
352  /// keys (i.e. the map is "sparse").
353  /// The name of this type also refers to this important usage.
354  ///
355  /// Apart form that, this map can be used in many other cases since it
356  /// is based on \c std::map, which is a general associative container.
357  /// However, keep in mind that it is usually not as efficient as other
358  /// maps.
359  ///
360  /// The simplest way of using this map is through the sparseMap()
361  /// function.
362  template <typename K, typename V, typename Comp = std::less<K> >
363  class SparseMap : public MapBase<K, V> {
364    template <typename K1, typename V1, typename C1>
365    friend class SparseMap;
366  public:
367
368    /// Key type
369    typedef K Key;
370    /// Value type
371    typedef V Value;
372    /// Reference type
373    typedef Value& Reference;
374    /// Const reference type
375    typedef const Value& ConstReference;
376
377    typedef True ReferenceMapTag;
378
379  private:
380
381    typedef std::map<K, V, Comp> Map;
382    Map _map;
383    Value _value;
384
385  public:
386
387    /// \brief Constructor with specified default value.
388    SparseMap(const Value &value = Value()) : _value(value) {}
389    /// \brief Constructs the map from an appropriate \c std::map, and
390    /// explicitly specifies a default value.
391    template <typename V1, typename Comp1>
392    SparseMap(const std::map<Key, V1, Comp1> &map,
393              const Value &value = Value())
394      : _map(map.begin(), map.end()), _value(value) {}
395
396    /// \brief Constructs the map from another \c SparseMap.
397    template<typename V1, typename Comp1>
398    SparseMap(const SparseMap<Key, V1, Comp1> &c)
399      : _map(c._map.begin(), c._map.end()), _value(c._value) {}
400
401  private:
402
403    SparseMap& operator=(const SparseMap&);
404
405  public:
406
407    ///\e
408    Reference operator[](const Key &k) {
409      typename Map::iterator it = _map.lower_bound(k);
410      if (it != _map.end() && !_map.key_comp()(k, it->first))
411        return it->second;
412      else
413        return _map.insert(it, std::make_pair(k, _value))->second;
414    }
415
416    ///\e
417    ConstReference operator[](const Key &k) const {
418      typename Map::const_iterator it = _map.find(k);
419      if (it != _map.end())
420        return it->second;
421      else
422        return _value;
423    }
424
425    ///\e
426    void set(const Key &k, const Value &v) {
427      typename Map::iterator it = _map.lower_bound(k);
428      if (it != _map.end() && !_map.key_comp()(k, it->first))
429        it->second = v;
430      else
431        _map.insert(it, std::make_pair(k, v));
432    }
433
434    ///\e
435    void setAll(const Value &v) {
436      _value = v;
437      _map.clear();
438    }
439  };
440
441  /// Returns a \c SparseMap class
442
443  /// This function just returns a \c SparseMap class with specified
444  /// default value.
445  /// \relates SparseMap
446  template<typename K, typename V, typename Compare>
447  inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
448    return SparseMap<K, V, Compare>(value);
449  }
450
451  template<typename K, typename V>
452  inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
453    return SparseMap<K, V, std::less<K> >(value);
454  }
455
456  /// \brief Returns a \c SparseMap class created from an appropriate
457  /// \c std::map
458
459  /// This function just returns a \c SparseMap class created from an
460  /// appropriate \c std::map.
461  /// \relates SparseMap
462  template<typename K, typename V, typename Compare>
463  inline SparseMap<K, V, Compare>
464    sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
465  {
466    return SparseMap<K, V, Compare>(map, value);
467  }
468
469  /// @}
470
471  /// \addtogroup map_adaptors
472  /// @{
473
474  /// Composition of two maps
475
476  /// This \ref concepts::ReadMap "read-only map" returns the
477  /// composition of two given maps. That is to say, if \c m1 is of
478  /// type \c M1 and \c m2 is of \c M2, then for
479  /// \code
480  ///   ComposeMap<M1, M2> cm(m1,m2);
481  /// \endcode
482  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
483  ///
484  /// The \c Key type of the map is inherited from \c M2 and the
485  /// \c Value type is from \c M1.
486  /// \c M2::Value must be convertible to \c M1::Key.
487  ///
488  /// The simplest way of using this map is through the composeMap()
489  /// function.
490  ///
491  /// \sa CombineMap
492  template <typename M1, typename M2>
493  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
494    const M1 &_m1;
495    const M2 &_m2;
496  public:
497    ///\e
498    typedef typename M2::Key Key;
499    ///\e
500    typedef typename M1::Value Value;
501
502    /// Constructor
503    ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
504
505    ///\e
506    typename MapTraits<M1>::ConstReturnValue
507    operator[](const Key &k) const { return _m1[_m2[k]]; }
508  };
509
510  /// Returns a \c ComposeMap class
511
512  /// This function just returns a \c ComposeMap class.
513  ///
514  /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
515  /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
516  /// will be equal to <tt>m1[m2[x]]</tt>.
517  ///
518  /// \relates ComposeMap
519  template <typename M1, typename M2>
520  inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) {
521    return ComposeMap<M1, M2>(m1, m2);
522  }
523
524
525  /// Combination of two maps using an STL (binary) functor.
526
527  /// This \ref concepts::ReadMap "read-only map" takes two maps and a
528  /// binary functor and returns the combination of the two given maps
529  /// using the functor.
530  /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2
531  /// and \c f is of \c F, then for
532  /// \code
533  ///   CombineMap<M1,M2,F,V> cm(m1,m2,f);
534  /// \endcode
535  /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>.
536  ///
537  /// The \c Key type of the map is inherited from \c M1 (\c M1::Key
538  /// must be convertible to \c M2::Key) and the \c Value type is \c V.
539  /// \c M2::Value and \c M1::Value must be convertible to the
540  /// corresponding input parameter of \c F and the return type of \c F
541  /// must be convertible to \c V.
542  ///
543  /// The simplest way of using this map is through the combineMap()
544  /// function.
545  ///
546  /// \sa ComposeMap
547  template<typename M1, typename M2, typename F,
548           typename V = typename F::result_type>
549  class CombineMap : public MapBase<typename M1::Key, V> {
550    const M1 &_m1;
551    const M2 &_m2;
552    F _f;
553  public:
554    ///\e
555    typedef typename M1::Key Key;
556    ///\e
557    typedef V Value;
558
559    /// Constructor
560    CombineMap(const M1 &m1, const M2 &m2, const F &f = F())
561      : _m1(m1), _m2(m2), _f(f) {}
562    ///\e
563    Value operator[](const Key &k) const { return _f(_m1[k],_m2[k]); }
564  };
565
566  /// Returns a \c CombineMap class
567
568  /// This function just returns a \c CombineMap class.
569  ///
570  /// For example, if \c m1 and \c m2 are both maps with \c double
571  /// values, then
572  /// \code
573  ///   combineMap(m1,m2,std::plus<double>())
574  /// \endcode
575  /// is equivalent to
576  /// \code
577  ///   addMap(m1,m2)
578  /// \endcode
579  ///
580  /// This function is specialized for adaptable binary function
581  /// classes and C++ functions.
582  ///
583  /// \relates CombineMap
584  template<typename M1, typename M2, typename F, typename V>
585  inline CombineMap<M1, M2, F, V>
586  combineMap(const M1 &m1, const M2 &m2, const F &f) {
587    return CombineMap<M1, M2, F, V>(m1,m2,f);
588  }
589
590  template<typename M1, typename M2, typename F>
591  inline CombineMap<M1, M2, F, typename F::result_type>
592  combineMap(const M1 &m1, const M2 &m2, const F &f) {
593    return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
594  }
595
596  template<typename M1, typename M2, typename K1, typename K2, typename V>
597  inline CombineMap<M1, M2, V (*)(K1, K2), V>
598  combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
599    return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
600  }
601
602
603  /// Converts an STL style (unary) functor to a map
604
605  /// This \ref concepts::ReadMap "read-only map" returns the value
606  /// of a given functor. Actually, it just wraps the functor and
607  /// provides the \c Key and \c Value typedefs.
608  ///
609  /// Template parameters \c K and \c V will become its \c Key and
610  /// \c Value. In most cases they have to be given explicitly because
611  /// a functor typically does not provide \c argument_type and
612  /// \c result_type typedefs.
613  /// Parameter \c F is the type of the used functor.
614  ///
615  /// The simplest way of using this map is through the functorToMap()
616  /// function.
617  ///
618  /// \sa MapToFunctor
619  template<typename F,
620           typename K = typename F::argument_type,
621           typename V = typename F::result_type>
622  class FunctorToMap : public MapBase<K, V> {
623    F _f;
624  public:
625    ///\e
626    typedef K Key;
627    ///\e
628    typedef V Value;
629
630    /// Constructor
631    FunctorToMap(const F &f = F()) : _f(f) {}
632    ///\e
633    Value operator[](const Key &k) const { return _f(k); }
634  };
635
636  /// Returns a \c FunctorToMap class
637
638  /// This function just returns a \c FunctorToMap class.
639  ///
640  /// This function is specialized for adaptable binary function
641  /// classes and C++ functions.
642  ///
643  /// \relates FunctorToMap
644  template<typename K, typename V, typename F>
645  inline FunctorToMap<F, K, V> functorToMap(const F &f) {
646    return FunctorToMap<F, K, V>(f);
647  }
648
649  template <typename F>
650  inline FunctorToMap<F, typename F::argument_type, typename F::result_type>
651    functorToMap(const F &f)
652  {
653    return FunctorToMap<F, typename F::argument_type,
654      typename F::result_type>(f);
655  }
656
657  template <typename K, typename V>
658  inline FunctorToMap<V (*)(K), K, V> functorToMap(V (*f)(K)) {
659    return FunctorToMap<V (*)(K), K, V>(f);
660  }
661
662
663  /// Converts a map to an STL style (unary) functor
664
665  /// This class converts a map to an STL style (unary) functor.
666  /// That is it provides an <tt>operator()</tt> to read its values.
667  ///
668  /// For the sake of convenience it also works as a usual
669  /// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt>
670  /// and the \c Key and \c Value typedefs also exist.
671  ///
672  /// The simplest way of using this map is through the mapToFunctor()
673  /// function.
674  ///
675  ///\sa FunctorToMap
676  template <typename M>
677  class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
678    const M &_m;
679  public:
680    ///\e
681    typedef typename M::Key Key;
682    ///\e
683    typedef typename M::Value Value;
684
685    typedef typename M::Key argument_type;
686    typedef typename M::Value result_type;
687
688    /// Constructor
689    MapToFunctor(const M &m) : _m(m) {}
690    ///\e
691    Value operator()(const Key &k) const { return _m[k]; }
692    ///\e
693    Value operator[](const Key &k) const { return _m[k]; }
694  };
695
696  /// Returns a \c MapToFunctor class
697
698  /// This function just returns a \c MapToFunctor class.
699  /// \relates MapToFunctor
700  template<typename M>
701  inline MapToFunctor<M> mapToFunctor(const M &m) {
702    return MapToFunctor<M>(m);
703  }
704
705
706  /// \brief Map adaptor to convert the \c Value type of a map to
707  /// another type using the default conversion.
708
709  /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap
710  /// "readable map" to another type using the default conversion.
711  /// The \c Key type of it is inherited from \c M and the \c Value
712  /// type is \c V.
713  /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
714  ///
715  /// The simplest way of using this map is through the convertMap()
716  /// function.
717  template <typename M, typename V>
718  class ConvertMap : public MapBase<typename M::Key, V> {
719    const M &_m;
720  public:
721    ///\e
722    typedef typename M::Key Key;
723    ///\e
724    typedef V Value;
725
726    /// Constructor
727
728    /// Constructor.
729    /// \param m The underlying map.
730    ConvertMap(const M &m) : _m(m) {}
731
732    ///\e
733    Value operator[](const Key &k) const { return _m[k]; }
734  };
735
736  /// Returns a \c ConvertMap class
737
738  /// This function just returns a \c ConvertMap class.
739  /// \relates ConvertMap
740  template<typename V, typename M>
741  inline ConvertMap<M, V> convertMap(const M &map) {
742    return ConvertMap<M, V>(map);
743  }
744
745
746  /// Applies all map setting operations to two maps
747
748  /// This map has two \ref concepts::WriteMap "writable map" parameters
749  /// and each write request will be passed to both of them.
750  /// If \c M1 is also \ref concepts::ReadMap "readable", then the read
751  /// operations will return the corresponding values of \c M1.
752  ///
753  /// The \c Key and \c Value types are inherited from \c M1.
754  /// The \c Key and \c Value of \c M2 must be convertible from those
755  /// of \c M1.
756  ///
757  /// The simplest way of using this map is through the forkMap()
758  /// function.
759  template<typename  M1, typename M2>
760  class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
761    M1 &_m1;
762    M2 &_m2;
763  public:
764    ///\e
765    typedef typename M1::Key Key;
766    ///\e
767    typedef typename M1::Value Value;
768
769    /// Constructor
770    ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
771    /// Returns the value associated with the given key in the first map.
772    Value operator[](const Key &k) const { return _m1[k]; }
773    /// Sets the value associated with the given key in both maps.
774    void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); }
775  };
776
777  /// Returns a \c ForkMap class
778
779  /// This function just returns a \c ForkMap class.
780  /// \relates ForkMap
781  template <typename M1, typename M2>
782  inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) {
783    return ForkMap<M1,M2>(m1,m2);
784  }
785
786
787  /// Sum of two maps
788
789  /// This \ref concepts::ReadMap "read-only map" returns the sum
790  /// of the values of the two given maps.
791  /// Its \c Key and \c Value types are inherited from \c M1.
792  /// The \c Key and \c Value of \c M2 must be convertible to those of
793  /// \c M1.
794  ///
795  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
796  /// \code
797  ///   AddMap<M1,M2> am(m1,m2);
798  /// \endcode
799  /// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>.
800  ///
801  /// The simplest way of using this map is through the addMap()
802  /// function.
803  ///
804  /// \sa SubMap, MulMap, DivMap
805  /// \sa ShiftMap, ShiftWriteMap
806  template<typename M1, typename M2>
807  class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
808    const M1 &_m1;
809    const M2 &_m2;
810  public:
811    ///\e
812    typedef typename M1::Key Key;
813    ///\e
814    typedef typename M1::Value Value;
815
816    /// Constructor
817    AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
818    ///\e
819    Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
820  };
821
822  /// Returns an \c AddMap class
823
824  /// This function just returns an \c AddMap class.
825  ///
826  /// For example, if \c m1 and \c m2 are both maps with \c double
827  /// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to
828  /// <tt>m1[x]+m2[x]</tt>.
829  ///
830  /// \relates AddMap
831  template<typename M1, typename M2>
832  inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) {
833    return AddMap<M1, M2>(m1,m2);
834  }
835
836
837  /// Difference of two maps
838
839  /// This \ref concepts::ReadMap "read-only map" returns the difference
840  /// of the values of the two given maps.
841  /// Its \c Key and \c Value types are inherited from \c M1.
842  /// The \c Key and \c Value of \c M2 must be convertible to those of
843  /// \c M1.
844  ///
845  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
846  /// \code
847  ///   SubMap<M1,M2> sm(m1,m2);
848  /// \endcode
849  /// <tt>sm[x]</tt> will be equal to <tt>m1[x]-m2[x]</tt>.
850  ///
851  /// The simplest way of using this map is through the subMap()
852  /// function.
853  ///
854  /// \sa AddMap, MulMap, DivMap
855  template<typename M1, typename M2>
856  class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
857    const M1 &_m1;
858    const M2 &_m2;
859  public:
860    ///\e
861    typedef typename M1::Key Key;
862    ///\e
863    typedef typename M1::Value Value;
864
865    /// Constructor
866    SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
867    ///\e
868    Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
869  };
870
871  /// Returns a \c SubMap class
872
873  /// This function just returns a \c SubMap class.
874  ///
875  /// For example, if \c m1 and \c m2 are both maps with \c double
876  /// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to
877  /// <tt>m1[x]-m2[x]</tt>.
878  ///
879  /// \relates SubMap
880  template<typename M1, typename M2>
881  inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
882    return SubMap<M1, M2>(m1,m2);
883  }
884
885
886  /// Product of two maps
887
888  /// This \ref concepts::ReadMap "read-only map" returns the product
889  /// of the values of the two given maps.
890  /// Its \c Key and \c Value types are inherited from \c M1.
891  /// The \c Key and \c Value of \c M2 must be convertible to those of
892  /// \c M1.
893  ///
894  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
895  /// \code
896  ///   MulMap<M1,M2> mm(m1,m2);
897  /// \endcode
898  /// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>.
899  ///
900  /// The simplest way of using this map is through the mulMap()
901  /// function.
902  ///
903  /// \sa AddMap, SubMap, DivMap
904  /// \sa ScaleMap, ScaleWriteMap
905  template<typename M1, typename M2>
906  class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
907    const M1 &_m1;
908    const M2 &_m2;
909  public:
910    ///\e
911    typedef typename M1::Key Key;
912    ///\e
913    typedef typename M1::Value Value;
914
915    /// Constructor
916    MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
917    ///\e
918    Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
919  };
920
921  /// Returns a \c MulMap class
922
923  /// This function just returns a \c MulMap class.
924  ///
925  /// For example, if \c m1 and \c m2 are both maps with \c double
926  /// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to
927  /// <tt>m1[x]*m2[x]</tt>.
928  ///
929  /// \relates MulMap
930  template<typename M1, typename M2>
931  inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
932    return MulMap<M1, M2>(m1,m2);
933  }
934
935
936  /// Quotient of two maps
937
938  /// This \ref concepts::ReadMap "read-only map" returns the quotient
939  /// of the values of the two given maps.
940  /// Its \c Key and \c Value types are inherited from \c M1.
941  /// The \c Key and \c Value of \c M2 must be convertible to those of
942  /// \c M1.
943  ///
944  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
945  /// \code
946  ///   DivMap<M1,M2> dm(m1,m2);
947  /// \endcode
948  /// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>.
949  ///
950  /// The simplest way of using this map is through the divMap()
951  /// function.
952  ///
953  /// \sa AddMap, SubMap, MulMap
954  template<typename M1, typename M2>
955  class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
956    const M1 &_m1;
957    const M2 &_m2;
958  public:
959    ///\e
960    typedef typename M1::Key Key;
961    ///\e
962    typedef typename M1::Value Value;
963
964    /// Constructor
965    DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
966    ///\e
967    Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
968  };
969
970  /// Returns a \c DivMap class
971
972  /// This function just returns a \c DivMap class.
973  ///
974  /// For example, if \c m1 and \c m2 are both maps with \c double
975  /// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to
976  /// <tt>m1[x]/m2[x]</tt>.
977  ///
978  /// \relates DivMap
979  template<typename M1, typename M2>
980  inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
981    return DivMap<M1, M2>(m1,m2);
982  }
983
984
985  /// Shifts a map with a constant.
986
987  /// This \ref concepts::ReadMap "read-only map" returns the sum of
988  /// the given map and a constant value (i.e. it shifts the map with
989  /// the constant). Its \c Key and \c Value are inherited from \c M.
990  ///
991  /// Actually,
992  /// \code
993  ///   ShiftMap<M> sh(m,v);
994  /// \endcode
995  /// is equivalent to
996  /// \code
997  ///   ConstMap<M::Key, M::Value> cm(v);
998  ///   AddMap<M, ConstMap<M::Key, M::Value> > sh(m,cm);
999  /// \endcode
1000  ///
1001  /// The simplest way of using this map is through the shiftMap()
1002  /// function.
1003  ///
1004  /// \sa ShiftWriteMap
1005  template<typename M, typename C = typename M::Value>
1006  class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
1007    const M &_m;
1008    C _v;
1009  public:
1010    ///\e
1011    typedef typename M::Key Key;
1012    ///\e
1013    typedef typename M::Value Value;
1014
1015    /// Constructor
1016
1017    /// Constructor.
1018    /// \param m The undelying map.
1019    /// \param v The constant value.
1020    ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
1021    ///\e
1022    Value operator[](const Key &k) const { return _m[k]+_v; }
1023  };
1024
1025  /// Shifts a map with a constant (read-write version).
1026
1027  /// This \ref concepts::ReadWriteMap "read-write map" returns the sum
1028  /// of the given map and a constant value (i.e. it shifts the map with
1029  /// the constant). Its \c Key and \c Value are inherited from \c M.
1030  /// It makes also possible to write the map.
1031  ///
1032  /// The simplest way of using this map is through the shiftWriteMap()
1033  /// function.
1034  ///
1035  /// \sa ShiftMap
1036  template<typename M, typename C = typename M::Value>
1037  class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
1038    M &_m;
1039    C _v;
1040  public:
1041    ///\e
1042    typedef typename M::Key Key;
1043    ///\e
1044    typedef typename M::Value Value;
1045
1046    /// Constructor
1047
1048    /// Constructor.
1049    /// \param m The undelying map.
1050    /// \param v The constant value.
1051    ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
1052    ///\e
1053    Value operator[](const Key &k) const { return _m[k]+_v; }
1054    ///\e
1055    void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
1056  };
1057
1058  /// Returns a \c ShiftMap class
1059
1060  /// This function just returns a \c ShiftMap class.
1061  ///
1062  /// For example, if \c m is a map with \c double values and \c v is
1063  /// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to
1064  /// <tt>m[x]+v</tt>.
1065  ///
1066  /// \relates ShiftMap
1067  template<typename M, typename C>
1068  inline ShiftMap<M, C> shiftMap(const M &m, const C &v) {
1069    return ShiftMap<M, C>(m,v);
1070  }
1071
1072  /// Returns a \c ShiftWriteMap class
1073
1074  /// This function just returns a \c ShiftWriteMap class.
1075  ///
1076  /// For example, if \c m is a map with \c double values and \c v is
1077  /// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to
1078  /// <tt>m[x]+v</tt>.
1079  /// Moreover it makes also possible to write the map.
1080  ///
1081  /// \relates ShiftWriteMap
1082  template<typename M, typename C>
1083  inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) {
1084    return ShiftWriteMap<M, C>(m,v);
1085  }
1086
1087
1088  /// Scales a map with a constant.
1089
1090  /// This \ref concepts::ReadMap "read-only map" returns the value of
1091  /// the given map multiplied from the left side with a constant value.
1092  /// Its \c Key and \c Value are inherited from \c M.
1093  ///
1094  /// Actually,
1095  /// \code
1096  ///   ScaleMap<M> sc(m,v);
1097  /// \endcode
1098  /// is equivalent to
1099  /// \code
1100  ///   ConstMap<M::Key, M::Value> cm(v);
1101  ///   MulMap<ConstMap<M::Key, M::Value>, M> sc(cm,m);
1102  /// \endcode
1103  ///
1104  /// The simplest way of using this map is through the scaleMap()
1105  /// function.
1106  ///
1107  /// \sa ScaleWriteMap
1108  template<typename M, typename C = typename M::Value>
1109  class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
1110    const M &_m;
1111    C _v;
1112  public:
1113    ///\e
1114    typedef typename M::Key Key;
1115    ///\e
1116    typedef typename M::Value Value;
1117
1118    /// Constructor
1119
1120    /// Constructor.
1121    /// \param m The undelying map.
1122    /// \param v The constant value.
1123    ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
1124    ///\e
1125    Value operator[](const Key &k) const { return _v*_m[k]; }
1126  };
1127
1128  /// Scales a map with a constant (read-write version).
1129
1130  /// This \ref concepts::ReadWriteMap "read-write map" returns the value of
1131  /// the given map multiplied from the left side with a constant value.
1132  /// Its \c Key and \c Value are inherited from \c M.
1133  /// It can also be used as write map if the \c / operator is defined
1134  /// between \c Value and \c C and the given multiplier is not zero.
1135  ///
1136  /// The simplest way of using this map is through the scaleWriteMap()
1137  /// function.
1138  ///
1139  /// \sa ScaleMap
1140  template<typename M, typename C = typename M::Value>
1141  class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
1142    M &_m;
1143    C _v;
1144  public:
1145    ///\e
1146    typedef typename M::Key Key;
1147    ///\e
1148    typedef typename M::Value Value;
1149
1150    /// Constructor
1151
1152    /// Constructor.
1153    /// \param m The undelying map.
1154    /// \param v The constant value.
1155    ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
1156    ///\e
1157    Value operator[](const Key &k) const { return _v*_m[k]; }
1158    ///\e
1159    void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
1160  };
1161
1162  /// Returns a \c ScaleMap class
1163
1164  /// This function just returns a \c ScaleMap class.
1165  ///
1166  /// For example, if \c m is a map with \c double values and \c v is
1167  /// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to
1168  /// <tt>v*m[x]</tt>.
1169  ///
1170  /// \relates ScaleMap
1171  template<typename M, typename C>
1172  inline ScaleMap<M, C> scaleMap(const M &m, const C &v) {
1173    return ScaleMap<M, C>(m,v);
1174  }
1175
1176  /// Returns a \c ScaleWriteMap class
1177
1178  /// This function just returns a \c ScaleWriteMap class.
1179  ///
1180  /// For example, if \c m is a map with \c double values and \c v is
1181  /// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to
1182  /// <tt>v*m[x]</tt>.
1183  /// Moreover it makes also possible to write the map.
1184  ///
1185  /// \relates ScaleWriteMap
1186  template<typename M, typename C>
1187  inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) {
1188    return ScaleWriteMap<M, C>(m,v);
1189  }
1190
1191
1192  /// Negative of a map
1193
1194  /// This \ref concepts::ReadMap "read-only map" returns the negative
1195  /// of the values of the given map (using the unary \c - operator).
1196  /// Its \c Key and \c Value are inherited from \c M.
1197  ///
1198  /// If M::Value is \c int, \c double etc., then
1199  /// \code
1200  ///   NegMap<M> neg(m);
1201  /// \endcode
1202  /// is equivalent to
1203  /// \code
1204  ///   ScaleMap<M> neg(m,-1);
1205  /// \endcode
1206  ///
1207  /// The simplest way of using this map is through the negMap()
1208  /// function.
1209  ///
1210  /// \sa NegWriteMap
1211  template<typename M>
1212  class NegMap : public MapBase<typename M::Key, typename M::Value> {
1213    const M& _m;
1214  public:
1215    ///\e
1216    typedef typename M::Key Key;
1217    ///\e
1218    typedef typename M::Value Value;
1219
1220    /// Constructor
1221    NegMap(const M &m) : _m(m) {}
1222    ///\e
1223    Value operator[](const Key &k) const { return -_m[k]; }
1224  };
1225
1226  /// Negative of a map (read-write version)
1227
1228  /// This \ref concepts::ReadWriteMap "read-write map" returns the
1229  /// negative of the values of the given map (using the unary \c -
1230  /// operator).
1231  /// Its \c Key and \c Value are inherited from \c M.
1232  /// It makes also possible to write the map.
1233  ///
1234  /// If M::Value is \c int, \c double etc., then
1235  /// \code
1236  ///   NegWriteMap<M> neg(m);
1237  /// \endcode
1238  /// is equivalent to
1239  /// \code
1240  ///   ScaleWriteMap<M> neg(m,-1);
1241  /// \endcode
1242  ///
1243  /// The simplest way of using this map is through the negWriteMap()
1244  /// function.
1245  ///
1246  /// \sa NegMap
1247  template<typename M>
1248  class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
1249    M &_m;
1250  public:
1251    ///\e
1252    typedef typename M::Key Key;
1253    ///\e
1254    typedef typename M::Value Value;
1255
1256    /// Constructor
1257    NegWriteMap(M &m) : _m(m) {}
1258    ///\e
1259    Value operator[](const Key &k) const { return -_m[k]; }
1260    ///\e
1261    void set(const Key &k, const Value &v) { _m.set(k, -v); }
1262  };
1263
1264  /// Returns a \c NegMap class
1265
1266  /// This function just returns a \c NegMap class.
1267  ///
1268  /// For example, if \c m is a map with \c double values, then
1269  /// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
1270  ///
1271  /// \relates NegMap
1272  template <typename M>
1273  inline NegMap<M> negMap(const M &m) {
1274    return NegMap<M>(m);
1275  }
1276
1277  /// Returns a \c NegWriteMap class
1278
1279  /// This function just returns a \c NegWriteMap class.
1280  ///
1281  /// For example, if \c m is a map with \c double values, then
1282  /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
1283  /// Moreover it makes also possible to write the map.
1284  ///
1285  /// \relates NegWriteMap
1286  template <typename M>
1287  inline NegWriteMap<M> negWriteMap(M &m) {
1288    return NegWriteMap<M>(m);
1289  }
1290
1291
1292  /// Absolute value of a map
1293
1294  /// This \ref concepts::ReadMap "read-only map" returns the absolute
1295  /// value of the values of the given map.
1296  /// Its \c Key and \c Value are inherited from \c M.
1297  /// \c Value must be comparable to \c 0 and the unary \c -
1298  /// operator must be defined for it, of course.
1299  ///
1300  /// The simplest way of using this map is through the absMap()
1301  /// function.
1302  template<typename M>
1303  class AbsMap : public MapBase<typename M::Key, typename M::Value> {
1304    const M &_m;
1305  public:
1306    ///\e
1307    typedef typename M::Key Key;
1308    ///\e
1309    typedef typename M::Value Value;
1310
1311    /// Constructor
1312    AbsMap(const M &m) : _m(m) {}
1313    ///\e
1314    Value operator[](const Key &k) const {
1315      Value tmp = _m[k];
1316      return tmp >= 0 ? tmp : -tmp;
1317    }
1318
1319  };
1320
1321  /// Returns an \c AbsMap class
1322
1323  /// This function just returns an \c AbsMap class.
1324  ///
1325  /// For example, if \c m is a map with \c double values, then
1326  /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if
1327  /// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is
1328  /// negative.
1329  ///
1330  /// \relates AbsMap
1331  template<typename M>
1332  inline AbsMap<M> absMap(const M &m) {
1333    return AbsMap<M>(m);
1334  }
1335
1336  /// @}
1337
1338  // Logical maps and map adaptors:
1339
1340  /// \addtogroup maps
1341  /// @{
1342
1343  /// Constant \c true map.
1344
1345  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1346  /// each key.
1347  ///
1348  /// Note that
1349  /// \code
1350  ///   TrueMap<K> tm;
1351  /// \endcode
1352  /// is equivalent to
1353  /// \code
1354  ///   ConstMap<K,bool> tm(true);
1355  /// \endcode
1356  ///
1357  /// \sa FalseMap
1358  /// \sa ConstMap
1359  template <typename K>
1360  class TrueMap : public MapBase<K, bool> {
1361  public:
1362    ///\e
1363    typedef K Key;
1364    ///\e
1365    typedef bool Value;
1366
1367    /// Gives back \c true.
1368    Value operator[](const Key&) const { return true; }
1369  };
1370
1371  /// Returns a \c TrueMap class
1372
1373  /// This function just returns a \c TrueMap class.
1374  /// \relates TrueMap
1375  template<typename K>
1376  inline TrueMap<K> trueMap() {
1377    return TrueMap<K>();
1378  }
1379
1380
1381  /// Constant \c false map.
1382
1383  /// This \ref concepts::ReadMap "read-only map" assigns \c false to
1384  /// each key.
1385  ///
1386  /// Note that
1387  /// \code
1388  ///   FalseMap<K> fm;
1389  /// \endcode
1390  /// is equivalent to
1391  /// \code
1392  ///   ConstMap<K,bool> fm(false);
1393  /// \endcode
1394  ///
1395  /// \sa TrueMap
1396  /// \sa ConstMap
1397  template <typename K>
1398  class FalseMap : public MapBase<K, bool> {
1399  public:
1400    ///\e
1401    typedef K Key;
1402    ///\e
1403    typedef bool Value;
1404
1405    /// Gives back \c false.
1406    Value operator[](const Key&) const { return false; }
1407  };
1408
1409  /// Returns a \c FalseMap class
1410
1411  /// This function just returns a \c FalseMap class.
1412  /// \relates FalseMap
1413  template<typename K>
1414  inline FalseMap<K> falseMap() {
1415    return FalseMap<K>();
1416  }
1417
1418  /// @}
1419
1420  /// \addtogroup map_adaptors
1421  /// @{
1422
1423  /// Logical 'and' of two maps
1424
1425  /// This \ref concepts::ReadMap "read-only map" returns the logical
1426  /// 'and' of the values of the two given maps.
1427  /// Its \c Key type is inherited from \c M1 and its \c Value type is
1428  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1429  ///
1430  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1431  /// \code
1432  ///   AndMap<M1,M2> am(m1,m2);
1433  /// \endcode
1434  /// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>.
1435  ///
1436  /// The simplest way of using this map is through the andMap()
1437  /// function.
1438  ///
1439  /// \sa OrMap
1440  /// \sa NotMap, NotWriteMap
1441  template<typename M1, typename M2>
1442  class AndMap : public MapBase<typename M1::Key, bool> {
1443    const M1 &_m1;
1444    const M2 &_m2;
1445  public:
1446    ///\e
1447    typedef typename M1::Key Key;
1448    ///\e
1449    typedef bool Value;
1450
1451    /// Constructor
1452    AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1453    ///\e
1454    Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
1455  };
1456
1457  /// Returns an \c AndMap class
1458
1459  /// This function just returns an \c AndMap class.
1460  ///
1461  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
1462  /// then <tt>andMap(m1,m2)[x]</tt> will be equal to
1463  /// <tt>m1[x]&&m2[x]</tt>.
1464  ///
1465  /// \relates AndMap
1466  template<typename M1, typename M2>
1467  inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) {
1468    return AndMap<M1, M2>(m1,m2);
1469  }
1470
1471
1472  /// Logical 'or' of two maps
1473
1474  /// This \ref concepts::ReadMap "read-only map" returns the logical
1475  /// 'or' of the values of the two given maps.
1476  /// Its \c Key type is inherited from \c M1 and its \c Value type is
1477  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1478  ///
1479  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1480  /// \code
1481  ///   OrMap<M1,M2> om(m1,m2);
1482  /// \endcode
1483  /// <tt>om[x]</tt> will be equal to <tt>m1[x]||m2[x]</tt>.
1484  ///
1485  /// The simplest way of using this map is through the orMap()
1486  /// function.
1487  ///
1488  /// \sa AndMap
1489  /// \sa NotMap, NotWriteMap
1490  template<typename M1, typename M2>
1491  class OrMap : public MapBase<typename M1::Key, bool> {
1492    const M1 &_m1;
1493    const M2 &_m2;
1494  public:
1495    ///\e
1496    typedef typename M1::Key Key;
1497    ///\e
1498    typedef bool Value;
1499
1500    /// Constructor
1501    OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1502    ///\e
1503    Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
1504  };
1505
1506  /// Returns an \c OrMap class
1507
1508  /// This function just returns an \c OrMap class.
1509  ///
1510  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
1511  /// then <tt>orMap(m1,m2)[x]</tt> will be equal to
1512  /// <tt>m1[x]||m2[x]</tt>.
1513  ///
1514  /// \relates OrMap
1515  template<typename M1, typename M2>
1516  inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) {
1517    return OrMap<M1, M2>(m1,m2);
1518  }
1519
1520
1521  /// Logical 'not' of a map
1522
1523  /// This \ref concepts::ReadMap "read-only map" returns the logical
1524  /// negation of the values of the given map.
1525  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
1526  ///
1527  /// The simplest way of using this map is through the notMap()
1528  /// function.
1529  ///
1530  /// \sa NotWriteMap
1531  template <typename M>
1532  class NotMap : public MapBase<typename M::Key, bool> {
1533    const M &_m;
1534  public:
1535    ///\e
1536    typedef typename M::Key Key;
1537    ///\e
1538    typedef bool Value;
1539
1540    /// Constructor
1541    NotMap(const M &m) : _m(m) {}
1542    ///\e
1543    Value operator[](const Key &k) const { return !_m[k]; }
1544  };
1545
1546  /// Logical 'not' of a map (read-write version)
1547
1548  /// This \ref concepts::ReadWriteMap "read-write map" returns the
1549  /// logical negation of the values of the given map.
1550  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
1551  /// It makes also possible to write the map. When a value is set,
1552  /// the opposite value is set to the original map.
1553  ///
1554  /// The simplest way of using this map is through the notWriteMap()
1555  /// function.
1556  ///
1557  /// \sa NotMap
1558  template <typename M>
1559  class NotWriteMap : public MapBase<typename M::Key, bool> {
1560    M &_m;
1561  public:
1562    ///\e
1563    typedef typename M::Key Key;
1564    ///\e
1565    typedef bool Value;
1566
1567    /// Constructor
1568    NotWriteMap(M &m) : _m(m) {}
1569    ///\e
1570    Value operator[](const Key &k) const { return !_m[k]; }
1571    ///\e
1572    void set(const Key &k, bool v) { _m.set(k, !v); }
1573  };
1574
1575  /// Returns a \c NotMap class
1576
1577  /// This function just returns a \c NotMap class.
1578  ///
1579  /// For example, if \c m is a map with \c bool values, then
1580  /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
1581  ///
1582  /// \relates NotMap
1583  template <typename M>
1584  inline NotMap<M> notMap(const M &m) {
1585    return NotMap<M>(m);
1586  }
1587
1588  /// Returns a \c NotWriteMap class
1589
1590  /// This function just returns a \c NotWriteMap class.
1591  ///
1592  /// For example, if \c m is a map with \c bool values, then
1593  /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
1594  /// Moreover it makes also possible to write the map.
1595  ///
1596  /// \relates NotWriteMap
1597  template <typename M>
1598  inline NotWriteMap<M> notWriteMap(M &m) {
1599    return NotWriteMap<M>(m);
1600  }
1601
1602
1603  /// Combination of two maps using the \c == operator
1604
1605  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1606  /// the keys for which the corresponding values of the two maps are
1607  /// equal.
1608  /// Its \c Key type is inherited from \c M1 and its \c Value type is
1609  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1610  ///
1611  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1612  /// \code
1613  ///   EqualMap<M1,M2> em(m1,m2);
1614  /// \endcode
1615  /// <tt>em[x]</tt> will be equal to <tt>m1[x]==m2[x]</tt>.
1616  ///
1617  /// The simplest way of using this map is through the equalMap()
1618  /// function.
1619  ///
1620  /// \sa LessMap
1621  template<typename M1, typename M2>
1622  class EqualMap : public MapBase<typename M1::Key, bool> {
1623    const M1 &_m1;
1624    const M2 &_m2;
1625  public:
1626    ///\e
1627    typedef typename M1::Key Key;
1628    ///\e
1629    typedef bool Value;
1630
1631    /// Constructor
1632    EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1633    ///\e
1634    Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
1635  };
1636
1637  /// Returns an \c EqualMap class
1638
1639  /// This function just returns an \c EqualMap class.
1640  ///
1641  /// For example, if \c m1 and \c m2 are maps with keys and values of
1642  /// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to
1643  /// <tt>m1[x]==m2[x]</tt>.
1644  ///
1645  /// \relates EqualMap
1646  template<typename M1, typename M2>
1647  inline EqualMap<M1, M2> equalMap(const M1 &m1, const M2 &m2) {
1648    return EqualMap<M1, M2>(m1,m2);
1649  }
1650
1651
1652  /// Combination of two maps using the \c < operator
1653
1654  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1655  /// the keys for which the corresponding value of the first map is
1656  /// less then the value of the second map.
1657  /// Its \c Key type is inherited from \c M1 and its \c Value type is
1658  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1659  ///
1660  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1661  /// \code
1662  ///   LessMap<M1,M2> lm(m1,m2);
1663  /// \endcode
1664  /// <tt>lm[x]</tt> will be equal to <tt>m1[x]<m2[x]</tt>.
1665  ///
1666  /// The simplest way of using this map is through the lessMap()
1667  /// function.
1668  ///
1669  /// \sa EqualMap
1670  template<typename M1, typename M2>
1671  class LessMap : public MapBase<typename M1::Key, bool> {
1672    const M1 &_m1;
1673    const M2 &_m2;
1674  public:
1675    ///\e
1676    typedef typename M1::Key Key;
1677    ///\e
1678    typedef bool Value;
1679
1680    /// Constructor
1681    LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1682    ///\e
1683    Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
1684  };
1685
1686  /// Returns an \c LessMap class
1687
1688  /// This function just returns an \c LessMap class.
1689  ///
1690  /// For example, if \c m1 and \c m2 are maps with keys and values of
1691  /// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to
1692  /// <tt>m1[x]<m2[x]</tt>.
1693  ///
1694  /// \relates LessMap
1695  template<typename M1, typename M2>
1696  inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) {
1697    return LessMap<M1, M2>(m1,m2);
1698  }
1699
1700  namespace _maps_bits {
1701
1702    template <typename _Iterator, typename Enable = void>
1703    struct IteratorTraits {
1704      typedef typename std::iterator_traits<_Iterator>::value_type Value;
1705    };
1706
1707    template <typename _Iterator>
1708    struct IteratorTraits<_Iterator,
1709      typename exists<typename _Iterator::container_type>::type>
1710    {
1711      typedef typename _Iterator::container_type::value_type Value;
1712    };
1713
1714  }
1715
1716  /// @}
1717
1718  /// \addtogroup maps
1719  /// @{
1720
1721  /// \brief Writable bool map for logging each \c true assigned element
1722  ///
1723  /// A \ref concepts::WriteMap "writable" bool map for logging
1724  /// each \c true assigned element, i.e it copies subsequently each
1725  /// keys set to \c true to the given iterator.
1726  /// The most important usage of it is storing certain nodes or arcs
1727  /// that were marked \c true by an algorithm.
1728  ///
1729  /// There are several algorithms that provide solutions through bool
1730  /// maps and most of them assign \c true at most once for each key.
1731  /// In these cases it is a natural request to store each \c true
1732  /// assigned elements (in order of the assignment), which can be
1733  /// easily done with LoggerBoolMap.
1734  ///
1735  /// The simplest way of using this map is through the loggerBoolMap()
1736  /// function.
1737  ///
1738  /// \tparam IT The type of the iterator.
1739  /// \tparam KEY The key type of the map. The default value set
1740  /// according to the iterator type should work in most cases.
1741  ///
1742  /// \note The container of the iterator must contain enough space
1743  /// for the elements or the iterator should be an inserter iterator.
1744#ifdef DOXYGEN
1745  template <typename IT, typename KEY>
1746#else
1747  template <typename IT,
1748            typename KEY = typename _maps_bits::IteratorTraits<IT>::Value>
1749#endif
1750  class LoggerBoolMap : public MapBase<KEY, bool> {
1751  public:
1752
1753    ///\e
1754    typedef KEY Key;
1755    ///\e
1756    typedef bool Value;
1757    ///\e
1758    typedef IT Iterator;
1759
1760    /// Constructor
1761    LoggerBoolMap(Iterator it)
1762      : _begin(it), _end(it) {}
1763
1764    /// Gives back the given iterator set for the first key
1765    Iterator begin() const {
1766      return _begin;
1767    }
1768
1769    /// Gives back the the 'after the last' iterator
1770    Iterator end() const {
1771      return _end;
1772    }
1773
1774    /// The set function of the map
1775    void set(const Key& key, Value value) {
1776      if (value) {
1777        *_end++ = key;
1778      }
1779    }
1780
1781  private:
1782    Iterator _begin;
1783    Iterator _end;
1784  };
1785
1786  /// Returns a \c LoggerBoolMap class
1787
1788  /// This function just returns a \c LoggerBoolMap class.
1789  ///
1790  /// The most important usage of it is storing certain nodes or arcs
1791  /// that were marked \c true by an algorithm.
1792  /// For example, it makes easier to store the nodes in the processing
1793  /// order of Dfs algorithm, as the following examples show.
1794  /// \code
1795  ///   std::vector<Node> v;
1796  ///   dfs(g).processedMap(loggerBoolMap(std::back_inserter(v))).run(s);
1797  /// \endcode
1798  /// \code
1799  ///   std::vector<Node> v(countNodes(g));
1800  ///   dfs(g).processedMap(loggerBoolMap(v.begin())).run(s);
1801  /// \endcode
1802  ///
1803  /// \note The container of the iterator must contain enough space
1804  /// for the elements or the iterator should be an inserter iterator.
1805  ///
1806  /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
1807  /// it cannot be used when a readable map is needed, for example, as
1808  /// \c ReachedMap for \c Bfs, \c Dfs and \c Dijkstra algorithms.
1809  ///
1810  /// \relates LoggerBoolMap
1811  template<typename Iterator>
1812  inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
1813    return LoggerBoolMap<Iterator>(it);
1814  }
1815
1816  /// @}
1817
1818  /// \addtogroup graph_maps
1819  /// @{
1820
1821  /// \brief Provides an immutable and unique id for each item in a graph.
1822  ///
1823  /// IdMap provides a unique and immutable id for each item of the
1824  /// same type (\c Node, \c Arc or \c Edge) in a graph. This id is
1825  ///  - \b unique: different items get different ids,
1826  ///  - \b immutable: the id of an item does not change (even if you
1827  ///    delete other nodes).
1828  ///
1829  /// Using this map you get access (i.e. can read) the inner id values of
1830  /// the items stored in the graph, which is returned by the \c id()
1831  /// function of the graph. This map can be inverted with its member
1832  /// class \c InverseMap or with the \c operator()() member.
1833  ///
1834  /// \tparam GR The graph type.
1835  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
1836  /// \c GR::Edge).
1837  ///
1838  /// \see RangeIdMap
1839  template <typename GR, typename K>
1840  class IdMap : public MapBase<K, int> {
1841  public:
1842    /// The graph type of IdMap.
1843    typedef GR Graph;
1844    typedef GR Digraph;
1845    /// The key type of IdMap (\c Node, \c Arc or \c Edge).
1846    typedef K Item;
1847    /// The key type of IdMap (\c Node, \c Arc or \c Edge).
1848    typedef K Key;
1849    /// The value type of IdMap.
1850    typedef int Value;
1851
1852    /// \brief Constructor.
1853    ///
1854    /// Constructor of the map.
1855    explicit IdMap(const Graph& graph) : _graph(&graph) {}
1856
1857    /// \brief Gives back the \e id of the item.
1858    ///
1859    /// Gives back the immutable and unique \e id of the item.
1860    int operator[](const Item& item) const { return _graph->id(item);}
1861
1862    /// \brief Gives back the \e item by its id.
1863    ///
1864    /// Gives back the \e item by its id.
1865    Item operator()(int id) { return _graph->fromId(id, Item()); }
1866
1867  private:
1868    const Graph* _graph;
1869
1870  public:
1871
1872    /// \brief The inverse map type of IdMap.
1873    ///
1874    /// The inverse map type of IdMap. The subscript operator gives back
1875    /// an item by its id.
1876    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
1877    /// \see inverse()
1878    class InverseMap {
1879    public:
1880
1881      /// \brief Constructor.
1882      ///
1883      /// Constructor for creating an id-to-item map.
1884      explicit InverseMap(const Graph& graph) : _graph(&graph) {}
1885
1886      /// \brief Constructor.
1887      ///
1888      /// Constructor for creating an id-to-item map.
1889      explicit InverseMap(const IdMap& map) : _graph(map._graph) {}
1890
1891      /// \brief Gives back an item by its id.
1892      ///
1893      /// Gives back an item by its id.
1894      Item operator[](int id) const { return _graph->fromId(id, Item());}
1895
1896    private:
1897      const Graph* _graph;
1898    };
1899
1900    /// \brief Gives back the inverse of the map.
1901    ///
1902    /// Gives back the inverse of the IdMap.
1903    InverseMap inverse() const { return InverseMap(*_graph);}
1904  };
1905
1906  /// \brief Returns an \c IdMap class.
1907  ///
1908  /// This function just returns an \c IdMap class.
1909  /// \relates IdMap
1910  template <typename K, typename GR>
1911  inline IdMap<GR, K> idMap(const GR& graph) {
1912    return IdMap<GR, K>(graph);
1913  }
1914
1915  /// \brief General cross reference graph map type.
1916
1917  /// This class provides simple invertable graph maps.
1918  /// It wraps a standard graph map (\c NodeMap, \c ArcMap or \c EdgeMap)
1919  /// and if a key is set to a new value, then stores it in the inverse map.
1920  /// The graph items can be accessed by their values either using
1921  /// \c InverseMap or \c operator()(), and the values of the map can be
1922  /// accessed with an STL compatible forward iterator (\c ValueIt).
1923  ///
1924  /// This map is intended to be used when all associated values are
1925  /// different (the map is actually invertable) or there are only a few
1926  /// items with the same value.
1927  /// Otherwise consider to use \c IterableValueMap, which is more
1928  /// suitable and more efficient for such cases. It provides iterators
1929  /// to traverse the items with the same associated value, but
1930  /// it does not have \c InverseMap.
1931  ///
1932  /// This type is not reference map, so it cannot be modified with
1933  /// the subscript operator.
1934  ///
1935  /// \tparam GR The graph type.
1936  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
1937  /// \c GR::Edge).
1938  /// \tparam V The value type of the map.
1939  ///
1940  /// \see IterableValueMap
1941  template <typename GR, typename K, typename V>
1942  class CrossRefMap
1943    : protected ItemSetTraits<GR, K>::template Map<V>::Type {
1944  private:
1945
1946    typedef typename ItemSetTraits<GR, K>::
1947      template Map<V>::Type Map;
1948
1949    typedef std::multimap<V, K> Container;
1950    Container _inv_map;
1951
1952  public:
1953
1954    /// The graph type of CrossRefMap.
1955    typedef GR Graph;
1956    typedef GR Digraph;
1957    /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
1958    typedef K Item;
1959    /// The key type of CrossRefMap (\c Node, \c Arc or \c Edge).
1960    typedef K Key;
1961    /// The value type of CrossRefMap.
1962    typedef V Value;
1963
1964    /// \brief Constructor.
1965    ///
1966    /// Construct a new CrossRefMap for the given graph.
1967    explicit CrossRefMap(const Graph& graph) : Map(graph) {}
1968
1969    /// \brief Forward iterator for values.
1970    ///
1971    /// This iterator is an STL compatible forward
1972    /// iterator on the values of the map. The values can
1973    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
1974    /// They are considered with multiplicity, so each value is
1975    /// traversed for each item it is assigned to.
1976    class ValueIt
1977      : public std::iterator<std::forward_iterator_tag, Value> {
1978      friend class CrossRefMap;
1979    private:
1980      ValueIt(typename Container::const_iterator _it)
1981        : it(_it) {}
1982    public:
1983
1984      /// Constructor
1985      ValueIt() {}
1986
1987      /// \e
1988      ValueIt& operator++() { ++it; return *this; }
1989      /// \e
1990      ValueIt operator++(int) {
1991        ValueIt tmp(*this);
1992        operator++();
1993        return tmp;
1994      }
1995
1996      /// \e
1997      const Value& operator*() const { return it->first; }
1998      /// \e
1999      const Value* operator->() const { return &(it->first); }
2000
2001      /// \e
2002      bool operator==(ValueIt jt) const { return it == jt.it; }
2003      /// \e
2004      bool operator!=(ValueIt jt) const { return it != jt.it; }
2005
2006    private:
2007      typename Container::const_iterator it;
2008    };
2009
2010    /// Alias for \c ValueIt
2011    typedef ValueIt ValueIterator;
2012
2013    /// \brief Returns an iterator to the first value.
2014    ///
2015    /// Returns an STL compatible iterator to the
2016    /// first value of the map. The values of the
2017    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
2018    /// range.
2019    ValueIt beginValue() const {
2020      return ValueIt(_inv_map.begin());
2021    }
2022
2023    /// \brief Returns an iterator after the last value.
2024    ///
2025    /// Returns an STL compatible iterator after the
2026    /// last value of the map. The values of the
2027    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
2028    /// range.
2029    ValueIt endValue() const {
2030      return ValueIt(_inv_map.end());
2031    }
2032
2033    /// \brief Sets the value associated with the given key.
2034    ///
2035    /// Sets the value associated with the given key.
2036    void set(const Key& key, const Value& val) {
2037      Value oldval = Map::operator[](key);
2038      typename Container::iterator it;
2039      for (it = _inv_map.equal_range(oldval).first;
2040           it != _inv_map.equal_range(oldval).second; ++it) {
2041        if (it->second == key) {
2042          _inv_map.erase(it);
2043          break;
2044        }
2045      }
2046      _inv_map.insert(std::make_pair(val, key));
2047      Map::set(key, val);
2048    }
2049
2050    /// \brief Returns the value associated with the given key.
2051    ///
2052    /// Returns the value associated with the given key.
2053    typename MapTraits<Map>::ConstReturnValue
2054    operator[](const Key& key) const {
2055      return Map::operator[](key);
2056    }
2057
2058    /// \brief Gives back an item by its value.
2059    ///
2060    /// This function gives back an item that is assigned to
2061    /// the given value or \c INVALID if no such item exists.
2062    /// If there are more items with the same associated value,
2063    /// only one of them is returned.
2064    Key operator()(const Value& val) const {
2065      typename Container::const_iterator it = _inv_map.find(val);
2066      return it != _inv_map.end() ? it->second : INVALID;
2067    }
2068
2069    /// \brief Returns the number of items with the given value.
2070    ///
2071    /// This function returns the number of items with the given value
2072    /// associated with it.
2073    int count(const Value &val) const {
2074      return _inv_map.count(val);
2075    }
2076
2077  protected:
2078
2079    /// \brief Erase the key from the map and the inverse map.
2080    ///
2081    /// Erase the key from the map and the inverse map. It is called by the
2082    /// \c AlterationNotifier.
2083    virtual void erase(const Key& key) {
2084      Value val = Map::operator[](key);
2085      typename Container::iterator it;
2086      for (it = _inv_map.equal_range(val).first;
2087           it != _inv_map.equal_range(val).second; ++it) {
2088        if (it->second == key) {
2089          _inv_map.erase(it);
2090          break;
2091        }
2092      }
2093      Map::erase(key);
2094    }
2095
2096    /// \brief Erase more keys from the map and the inverse map.
2097    ///
2098    /// Erase more keys from the map and the inverse map. It is called by the
2099    /// \c AlterationNotifier.
2100    virtual void erase(const std::vector<Key>& keys) {
2101      for (int i = 0; i < int(keys.size()); ++i) {
2102        Value val = Map::operator[](keys[i]);
2103        typename Container::iterator it;
2104        for (it = _inv_map.equal_range(val).first;
2105             it != _inv_map.equal_range(val).second; ++it) {
2106          if (it->second == keys[i]) {
2107            _inv_map.erase(it);
2108            break;
2109          }
2110        }
2111      }
2112      Map::erase(keys);
2113    }
2114
2115    /// \brief Clear the keys from the map and the inverse map.
2116    ///
2117    /// Clear the keys from the map and the inverse map. It is called by the
2118    /// \c AlterationNotifier.
2119    virtual void clear() {
2120      _inv_map.clear();
2121      Map::clear();
2122    }
2123
2124  public:
2125
2126    /// \brief The inverse map type of CrossRefMap.
2127    ///
2128    /// The inverse map type of CrossRefMap. The subscript operator gives
2129    /// back an item by its value.
2130    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
2131    /// \see inverse()
2132    class InverseMap {
2133    public:
2134      /// \brief Constructor
2135      ///
2136      /// Constructor of the InverseMap.
2137      explicit InverseMap(const CrossRefMap& inverted)
2138        : _inverted(inverted) {}
2139
2140      /// The value type of the InverseMap.
2141      typedef typename CrossRefMap::Key Value;
2142      /// The key type of the InverseMap.
2143      typedef typename CrossRefMap::Value Key;
2144
2145      /// \brief Subscript operator.
2146      ///
2147      /// Subscript operator. It gives back an item
2148      /// that is assigned to the given value or \c INVALID
2149      /// if no such item exists.
2150      Value operator[](const Key& key) const {
2151        return _inverted(key);
2152      }
2153
2154    private:
2155      const CrossRefMap& _inverted;
2156    };
2157
2158    /// \brief Gives back the inverse of the map.
2159    ///
2160    /// Gives back the inverse of the CrossRefMap.
2161    InverseMap inverse() const {
2162      return InverseMap(*this);
2163    }
2164
2165  };
2166
2167  /// \brief Provides continuous and unique id for the
2168  /// items of a graph.
2169  ///
2170  /// RangeIdMap provides a unique and continuous
2171  /// id for each item of a given type (\c Node, \c Arc or
2172  /// \c Edge) in a graph. This id is
2173  ///  - \b unique: different items get different ids,
2174  ///  - \b continuous: the range of the ids is the set of integers
2175  ///    between 0 and \c n-1, where \c n is the number of the items of
2176  ///    this type (\c Node, \c Arc or \c Edge).
2177  ///  - So, the ids can change when deleting an item of the same type.
2178  ///
2179  /// Thus this id is not (necessarily) the same as what can get using
2180  /// the \c id() function of the graph or \ref IdMap.
2181  /// This map can be inverted with its member class \c InverseMap,
2182  /// or with the \c operator()() member.
2183  ///
2184  /// \tparam GR The graph type.
2185  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
2186  /// \c GR::Edge).
2187  ///
2188  /// \see IdMap
2189  template <typename GR, typename K>
2190  class RangeIdMap
2191    : protected ItemSetTraits<GR, K>::template Map<int>::Type {
2192
2193    typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Map;
2194
2195  public:
2196    /// The graph type of RangeIdMap.
2197    typedef GR Graph;
2198    typedef GR Digraph;
2199    /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge).
2200    typedef K Item;
2201    /// The key type of RangeIdMap (\c Node, \c Arc or \c Edge).
2202    typedef K Key;
2203    /// The value type of RangeIdMap.
2204    typedef int Value;
2205
2206    /// \brief Constructor.
2207    ///
2208    /// Constructor.
2209    explicit RangeIdMap(const Graph& gr) : Map(gr) {
2210      Item it;
2211      const typename Map::Notifier* nf = Map::notifier();
2212      for (nf->first(it); it != INVALID; nf->next(it)) {
2213        Map::set(it, _inv_map.size());
2214        _inv_map.push_back(it);
2215      }
2216    }
2217
2218  protected:
2219
2220    /// \brief Adds a new key to the map.
2221    ///
2222    /// Add a new key to the map. It is called by the
2223    /// \c AlterationNotifier.
2224    virtual void add(const Item& item) {
2225      Map::add(item);
2226      Map::set(item, _inv_map.size());
2227      _inv_map.push_back(item);
2228    }
2229
2230    /// \brief Add more new keys to the map.
2231    ///
2232    /// Add more new keys to the map. It is called by the
2233    /// \c AlterationNotifier.
2234    virtual void add(const std::vector<Item>& items) {
2235      Map::add(items);
2236      for (int i = 0; i < int(items.size()); ++i) {
2237        Map::set(items[i], _inv_map.size());
2238        _inv_map.push_back(items[i]);
2239      }
2240    }
2241
2242    /// \brief Erase the key from the map.
2243    ///
2244    /// Erase the key from the map. It is called by the
2245    /// \c AlterationNotifier.
2246    virtual void erase(const Item& item) {
2247      Map::set(_inv_map.back(), Map::operator[](item));
2248      _inv_map[Map::operator[](item)] = _inv_map.back();
2249      _inv_map.pop_back();
2250      Map::erase(item);
2251    }
2252
2253    /// \brief Erase more keys from the map.
2254    ///
2255    /// Erase more keys from the map. It is called by the
2256    /// \c AlterationNotifier.
2257    virtual void erase(const std::vector<Item>& items) {
2258      for (int i = 0; i < int(items.size()); ++i) {
2259        Map::set(_inv_map.back(), Map::operator[](items[i]));
2260        _inv_map[Map::operator[](items[i])] = _inv_map.back();
2261        _inv_map.pop_back();
2262      }
2263      Map::erase(items);
2264    }
2265
2266    /// \brief Build the unique map.
2267    ///
2268    /// Build the unique map. It is called by the
2269    /// \c AlterationNotifier.
2270    virtual void build() {
2271      Map::build();
2272      Item it;
2273      const typename Map::Notifier* nf = Map::notifier();
2274      for (nf->first(it); it != INVALID; nf->next(it)) {
2275        Map::set(it, _inv_map.size());
2276        _inv_map.push_back(it);
2277      }
2278    }
2279
2280    /// \brief Clear the keys from the map.
2281    ///
2282    /// Clear the keys from the map. It is called by the
2283    /// \c AlterationNotifier.
2284    virtual void clear() {
2285      _inv_map.clear();
2286      Map::clear();
2287    }
2288
2289  public:
2290
2291    /// \brief Returns the maximal value plus one.
2292    ///
2293    /// Returns the maximal value plus one in the map.
2294    unsigned int size() const {
2295      return _inv_map.size();
2296    }
2297
2298    /// \brief Swaps the position of the two items in the map.
2299    ///
2300    /// Swaps the position of the two items in the map.
2301    void swap(const Item& p, const Item& q) {
2302      int pi = Map::operator[](p);
2303      int qi = Map::operator[](q);
2304      Map::set(p, qi);
2305      _inv_map[qi] = p;
2306      Map::set(q, pi);
2307      _inv_map[pi] = q;
2308    }
2309
2310    /// \brief Gives back the \e range \e id of the item
2311    ///
2312    /// Gives back the \e range \e id of the item.
2313    int operator[](const Item& item) const {
2314      return Map::operator[](item);
2315    }
2316
2317    /// \brief Gives back the item belonging to a \e range \e id
2318    ///
2319    /// Gives back the item belonging to the given \e range \e id.
2320    Item operator()(int id) const {
2321      return _inv_map[id];
2322    }
2323
2324  private:
2325
2326    typedef std::vector<Item> Container;
2327    Container _inv_map;
2328
2329  public:
2330
2331    /// \brief The inverse map type of RangeIdMap.
2332    ///
2333    /// The inverse map type of RangeIdMap. The subscript operator gives
2334    /// back an item by its \e range \e id.
2335    /// This type conforms to the \ref concepts::ReadMap "ReadMap" concept.
2336    class InverseMap {
2337    public:
2338      /// \brief Constructor
2339      ///
2340      /// Constructor of the InverseMap.
2341      explicit InverseMap(const RangeIdMap& inverted)
2342        : _inverted(inverted) {}
2343
2344
2345      /// The value type of the InverseMap.
2346      typedef typename RangeIdMap::Key Value;
2347      /// The key type of the InverseMap.
2348      typedef typename RangeIdMap::Value Key;
2349
2350      /// \brief Subscript operator.
2351      ///
2352      /// Subscript operator. It gives back the item
2353      /// that the given \e range \e id currently belongs to.
2354      Value operator[](const Key& key) const {
2355        return _inverted(key);
2356      }
2357
2358      /// \brief Size of the map.
2359      ///
2360      /// Returns the size of the map.
2361      unsigned int size() const {
2362        return _inverted.size();
2363      }
2364
2365    private:
2366      const RangeIdMap& _inverted;
2367    };
2368
2369    /// \brief Gives back the inverse of the map.
2370    ///
2371    /// Gives back the inverse of the RangeIdMap.
2372    const InverseMap inverse() const {
2373      return InverseMap(*this);
2374    }
2375  };
2376
2377  /// \brief Returns a \c RangeIdMap class.
2378  ///
2379  /// This function just returns an \c RangeIdMap class.
2380  /// \relates RangeIdMap
2381  template <typename K, typename GR>
2382  inline RangeIdMap<GR, K> rangeIdMap(const GR& graph) {
2383    return RangeIdMap<GR, K>(graph);
2384  }
2385
2386  /// \brief Dynamic iterable \c bool map.
2387  ///
2388  /// This class provides a special graph map type which can store a
2389  /// \c bool value for graph items (\c Node, \c Arc or \c Edge).
2390  /// For both \c true and \c false values it is possible to iterate on
2391  /// the keys mapped to the value.
2392  ///
2393  /// This type is a reference map, so it can be modified with the
2394  /// subscript operator.
2395  ///
2396  /// \tparam GR The graph type.
2397  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
2398  /// \c GR::Edge).
2399  ///
2400  /// \see IterableIntMap, IterableValueMap
2401  /// \see CrossRefMap
2402  template <typename GR, typename K>
2403  class IterableBoolMap
2404    : protected ItemSetTraits<GR, K>::template Map<int>::Type {
2405  private:
2406    typedef GR Graph;
2407
2408    typedef typename ItemSetTraits<GR, K>::ItemIt KeyIt;
2409    typedef typename ItemSetTraits<GR, K>::template Map<int>::Type Parent;
2410
2411    std::vector<K> _array;
2412    int _sep;
2413
2414  public:
2415
2416    /// Indicates that the map is reference map.
2417    typedef True ReferenceMapTag;
2418
2419    /// The key type
2420    typedef K Key;
2421    /// The value type
2422    typedef bool Value;
2423    /// The const reference type.
2424    typedef const Value& ConstReference;
2425
2426  private:
2427
2428    int position(const Key& key) const {
2429      return Parent::operator[](key);
2430    }
2431
2432  public:
2433
2434    /// \brief Reference to the value of the map.
2435    ///
2436    /// This class is similar to the \c bool type. It can be converted to
2437    /// \c bool and it provides the same operators.
2438    class Reference {
2439      friend class IterableBoolMap;
2440    private:
2441      Reference(IterableBoolMap& map, const Key& key)
2442        : _key(key), _map(map) {}
2443    public:
2444
2445      Reference& operator=(const Reference& value) {
2446        _map.set(_key, static_cast<bool>(value));
2447         return *this;
2448      }
2449
2450      operator bool() const {
2451        return static_cast<const IterableBoolMap&>(_map)[_key];
2452      }
2453
2454      Reference& operator=(bool value) {
2455        _map.set(_key, value);
2456        return *this;
2457      }
2458      Reference& operator&=(bool value) {
2459        _map.set(_key, _map[_key] & value);
2460        return *this;
2461      }
2462      Reference& operator|=(bool value) {
2463        _map.set(_key, _map[_key] | value);
2464        return *this;
2465      }
2466      Reference& operator^=(bool value) {
2467        _map.set(_key, _map[_key] ^ value);
2468        return *this;
2469      }
2470    private:
2471      Key _key;
2472      IterableBoolMap& _map;
2473    };
2474
2475    /// \brief Constructor of the map with a default value.
2476    ///
2477    /// Constructor of the map with a default value.
2478    explicit IterableBoolMap(const Graph& graph, bool def = false)
2479      : Parent(graph) {
2480      typename Parent::Notifier* nf = Parent::notifier();
2481      Key it;
2482      for (nf->first(it); it != INVALID; nf->next(it)) {
2483        Parent::set(it, _array.size());
2484        _array.push_back(it);
2485      }
2486      _sep = (def ? _array.size() : 0);
2487    }
2488
2489    /// \brief Const subscript operator of the map.
2490    ///
2491    /// Const subscript operator of the map.
2492    bool operator[](const Key& key) const {
2493      return position(key) < _sep;
2494    }
2495
2496    /// \brief Subscript operator of the map.
2497    ///
2498    /// Subscript operator of the map.
2499    Reference operator[](const Key& key) {
2500      return Reference(*this, key);
2501    }
2502
2503    /// \brief Set operation of the map.
2504    ///
2505    /// Set operation of the map.
2506    void set(const Key& key, bool value) {
2507      int pos = position(key);
2508      if (value) {
2509        if (pos < _sep) return;
2510        Key tmp = _array[_sep];
2511        _array[_sep] = key;
2512        Parent::set(key, _sep);
2513        _array[pos] = tmp;
2514        Parent::set(tmp, pos);
2515        ++_sep;
2516      } else {
2517        if (pos >= _sep) return;
2518        --_sep;
2519        Key tmp = _array[_sep];
2520        _array[_sep] = key;
2521        Parent::set(key, _sep);
2522        _array[pos] = tmp;
2523        Parent::set(tmp, pos);
2524      }
2525    }
2526
2527    /// \brief Set all items.
2528    ///
2529    /// Set all items in the map.
2530    /// \note Constant time operation.
2531    void setAll(bool value) {
2532      _sep = (value ? _array.size() : 0);
2533    }
2534
2535    /// \brief Returns the number of the keys mapped to \c true.
2536    ///
2537    /// Returns the number of the keys mapped to \c true.
2538    int trueNum() const {
2539      return _sep;
2540    }
2541
2542    /// \brief Returns the number of the keys mapped to \c false.
2543    ///
2544    /// Returns the number of the keys mapped to \c false.
2545    int falseNum() const {
2546      return _array.size() - _sep;
2547    }
2548
2549    /// \brief Iterator for the keys mapped to \c true.
2550    ///
2551    /// Iterator for the keys mapped to \c true. It works
2552    /// like a graph item iterator, it can be converted to
2553    /// the key type of the map, incremented with \c ++ operator, and
2554    /// if the iterator leaves the last valid key, it will be equal to
2555    /// \c INVALID.
2556    class TrueIt : public Key {
2557    public:
2558      typedef Key Parent;
2559
2560      /// \brief Creates an iterator.
2561      ///
2562      /// Creates an iterator. It iterates on the
2563      /// keys mapped to \c true.
2564      /// \param map The IterableBoolMap.
2565      explicit TrueIt(const IterableBoolMap& map)
2566        : Parent(map._sep > 0 ? map._array[map._sep - 1] : INVALID),
2567          _map(&map) {}
2568
2569      /// \brief Invalid constructor \& conversion.
2570      ///
2571      /// This constructor initializes the iterator to be invalid.
2572      /// \sa Invalid for more details.
2573      TrueIt(Invalid) : Parent(INVALID), _map(0) {}
2574
2575      /// \brief Increment operator.
2576      ///
2577      /// Increment operator.
2578      TrueIt& operator++() {
2579        int pos = _map->position(*this);
2580        Parent::operator=(pos > 0 ? _map->_array[pos - 1] : INVALID);
2581        return *this;
2582      }
2583
2584    private:
2585      const IterableBoolMap* _map;
2586    };
2587
2588    /// \brief STL style iterator for the keys mapped to \c true.
2589    ///
2590    /// This is an STL style wrapper for \ref TrueIt.
2591    /// It can be used in range-based for loops, STL algorithms, etc.
2592    LemonRangeWrapper1<TrueIt, IterableBoolMap>
2593    trueKeys() {
2594      return LemonRangeWrapper1<TrueIt, IterableBoolMap>(*this);
2595    }
2596
2597
2598    /// \brief Iterator for the keys mapped to \c false.
2599    ///
2600    /// Iterator for the keys mapped to \c false. It works
2601    /// like a graph item iterator, it can be converted to
2602    /// the key type of the map, incremented with \c ++ operator, and
2603    /// if the iterator leaves the last valid key, it will be equal to
2604    /// \c INVALID.
2605    class FalseIt : public Key {
2606    public:
2607      typedef Key Parent;
2608
2609      /// \brief Creates an iterator.
2610      ///
2611      /// Creates an iterator. It iterates on the
2612      /// keys mapped to \c false.
2613      /// \param map The IterableBoolMap.
2614      explicit FalseIt(const IterableBoolMap& map)
2615        : Parent(map._sep < int(map._array.size()) ?
2616                 map._array.back() : INVALID), _map(&map) {}
2617
2618      /// \brief Invalid constructor \& conversion.
2619      ///
2620      /// This constructor initializes the iterator to be invalid.
2621      /// \sa Invalid for more details.
2622      FalseIt(Invalid) : Parent(INVALID), _map(0) {}
2623
2624      /// \brief Increment operator.
2625      ///
2626      /// Increment operator.
2627      FalseIt& operator++() {
2628        int pos = _map->position(*this);
2629        Parent::operator=(pos > _map->_sep ? _map->_array[pos - 1] : INVALID);
2630        return *this;
2631      }
2632
2633    private:
2634      const IterableBoolMap* _map;
2635    };
2636
2637    /// \brief STL style iterator for the keys mapped to \c false.
2638    ///
2639    /// This is an STL style wrapper for \ref FalseIt.
2640    /// It can be used in range-based for loops, STL algorithms, etc.
2641    LemonRangeWrapper1<FalseIt, IterableBoolMap>
2642    falseKeys() {
2643      return LemonRangeWrapper1<FalseIt, IterableBoolMap>(*this);
2644    }
2645
2646
2647    /// \brief Iterator for the keys mapped to a given value.
2648    ///
2649    /// Iterator for the keys mapped to a given value. It works
2650    /// like a graph item iterator, it can be converted to
2651    /// the key type of the map, incremented with \c ++ operator, and
2652    /// if the iterator leaves the last valid key, it will be equal to
2653    /// \c INVALID.
2654    class ItemIt : public Key {
2655    public:
2656      typedef Key Parent;
2657
2658      /// \brief Creates an iterator with a value.
2659      ///
2660      /// Creates an iterator with a value. It iterates on the
2661      /// keys mapped to the given value.
2662      /// \param map The IterableBoolMap.
2663      /// \param value The value.
2664      ItemIt(const IterableBoolMap& map, bool value)
2665        : Parent(value ?
2666                 (map._sep > 0 ?
2667                  map._array[map._sep - 1] : INVALID) :
2668                 (map._sep < int(map._array.size()) ?
2669                  map._array.back() : INVALID)), _map(&map) {}
2670
2671      /// \brief Invalid constructor \& conversion.
2672      ///
2673      /// This constructor initializes the iterator to be invalid.
2674      /// \sa Invalid for more details.
2675      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
2676
2677      /// \brief Increment operator.
2678      ///
2679      /// Increment operator.
2680      ItemIt& operator++() {
2681        int pos = _map->position(*this);
2682        int _sep = pos >= _map->_sep ? _map->_sep : 0;
2683        Parent::operator=(pos > _sep ? _map->_array[pos - 1] : INVALID);
2684        return *this;
2685      }
2686
2687    private:
2688      const IterableBoolMap* _map;
2689    };
2690
2691    /// \brief STL style iterator for the keys mapped to a given value.
2692    ///
2693    /// This is an STL style wrapper for \ref ItemIt.
2694    /// It can be used in range-based for loops, STL algorithms, etc.
2695    LemonRangeWrapper2<ItemIt, IterableBoolMap, bool>
2696    items(bool value) {
2697      return LemonRangeWrapper2<ItemIt, IterableBoolMap, bool>(*this, value);
2698    }
2699
2700  protected:
2701
2702    virtual void add(const Key& key) {
2703      Parent::add(key);
2704      Parent::set(key, _array.size());
2705      _array.push_back(key);
2706    }
2707
2708    virtual void add(const std::vector<Key>& keys) {
2709      Parent::add(keys);
2710      for (int i = 0; i < int(keys.size()); ++i) {
2711        Parent::set(keys[i], _array.size());
2712        _array.push_back(keys[i]);
2713      }
2714    }
2715
2716    virtual void erase(const Key& key) {
2717      int pos = position(key);
2718      if (pos < _sep) {
2719        --_sep;
2720        Parent::set(_array[_sep], pos);
2721        _array[pos] = _array[_sep];
2722        Parent::set(_array.back(), _sep);
2723        _array[_sep] = _array.back();
2724        _array.pop_back();
2725      } else {
2726        Parent::set(_array.back(), pos);
2727        _array[pos] = _array.back();
2728        _array.pop_back();
2729      }
2730      Parent::erase(key);
2731    }
2732
2733    virtual void erase(const std::vector<Key>& keys) {
2734      for (int i = 0; i < int(keys.size()); ++i) {
2735        int pos = position(keys[i]);
2736        if (pos < _sep) {
2737          --_sep;
2738          Parent::set(_array[_sep], pos);
2739          _array[pos] = _array[_sep];
2740          Parent::set(_array.back(), _sep);
2741          _array[_sep] = _array.back();
2742          _array.pop_back();
2743        } else {
2744          Parent::set(_array.back(), pos);
2745          _array[pos] = _array.back();
2746          _array.pop_back();
2747        }
2748      }
2749      Parent::erase(keys);
2750    }
2751
2752    virtual void build() {
2753      Parent::build();
2754      typename Parent::Notifier* nf = Parent::notifier();
2755      Key it;
2756      for (nf->first(it); it != INVALID; nf->next(it)) {
2757        Parent::set(it, _array.size());
2758        _array.push_back(it);
2759      }
2760      _sep = 0;
2761    }
2762
2763    virtual void clear() {
2764      _array.clear();
2765      _sep = 0;
2766      Parent::clear();
2767    }
2768
2769  };
2770
2771
2772  namespace _maps_bits {
2773    template <typename Item>
2774    struct IterableIntMapNode {
2775      IterableIntMapNode() : value(-1) {}
2776      IterableIntMapNode(int _value) : value(_value) {}
2777      Item prev, next;
2778      int value;
2779    };
2780  }
2781
2782  /// \brief Dynamic iterable integer map.
2783  ///
2784  /// This class provides a special graph map type which can store an
2785  /// integer value for graph items (\c Node, \c Arc or \c Edge).
2786  /// For each non-negative value it is possible to iterate on the keys
2787  /// mapped to the value.
2788  ///
2789  /// This map is intended to be used with small integer values, for which
2790  /// it is efficient, and supports iteration only for non-negative values.
2791  /// If you need large values and/or iteration for negative integers,
2792  /// consider to use \ref IterableValueMap instead.
2793  ///
2794  /// This type is a reference map, so it can be modified with the
2795  /// subscript operator.
2796  ///
2797  /// \note The size of the data structure depends on the largest
2798  /// value in the map.
2799  ///
2800  /// \tparam GR The graph type.
2801  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
2802  /// \c GR::Edge).
2803  ///
2804  /// \see IterableBoolMap, IterableValueMap
2805  /// \see CrossRefMap
2806  template <typename GR, typename K>
2807  class IterableIntMap
2808    : protected ItemSetTraits<GR, K>::
2809        template Map<_maps_bits::IterableIntMapNode<K> >::Type {
2810  public:
2811    typedef typename ItemSetTraits<GR, K>::
2812      template Map<_maps_bits::IterableIntMapNode<K> >::Type Parent;
2813
2814    /// The key type
2815    typedef K Key;
2816    /// The value type
2817    typedef int Value;
2818    /// The graph type
2819    typedef GR Graph;
2820
2821    /// \brief Constructor of the map.
2822    ///
2823    /// Constructor of the map. It sets all values to -1.
2824    explicit IterableIntMap(const Graph& graph)
2825      : Parent(graph) {}
2826
2827    /// \brief Constructor of the map with a given value.
2828    ///
2829    /// Constructor of the map with a given value.
2830    explicit IterableIntMap(const Graph& graph, int value)
2831      : Parent(graph, _maps_bits::IterableIntMapNode<K>(value)) {
2832      if (value >= 0) {
2833        for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
2834          lace(it);
2835        }
2836      }
2837    }
2838
2839  private:
2840
2841    void unlace(const Key& key) {
2842      typename Parent::Value& node = Parent::operator[](key);
2843      if (node.value < 0) return;
2844      if (node.prev != INVALID) {
2845        Parent::operator[](node.prev).next = node.next;
2846      } else {
2847        _first[node.value] = node.next;
2848      }
2849      if (node.next != INVALID) {
2850        Parent::operator[](node.next).prev = node.prev;
2851      }
2852      while (!_first.empty() && _first.back() == INVALID) {
2853        _first.pop_back();
2854      }
2855    }
2856
2857    void lace(const Key& key) {
2858      typename Parent::Value& node = Parent::operator[](key);
2859      if (node.value < 0) return;
2860      if (node.value >= int(_first.size())) {
2861        _first.resize(node.value + 1, INVALID);
2862      }
2863      node.prev = INVALID;
2864      node.next = _first[node.value];
2865      if (node.next != INVALID) {
2866        Parent::operator[](node.next).prev = key;
2867      }
2868      _first[node.value] = key;
2869    }
2870
2871  public:
2872
2873    /// Indicates that the map is reference map.
2874    typedef True ReferenceMapTag;
2875
2876    /// \brief Reference to the value of the map.
2877    ///
2878    /// This class is similar to the \c int type. It can
2879    /// be converted to \c int and it has the same operators.
2880    class Reference {
2881      friend class IterableIntMap;
2882    private:
2883      Reference(IterableIntMap& map, const Key& key)
2884        : _key(key), _map(map) {}
2885    public:
2886
2887      Reference& operator=(const Reference& value) {
2888        _map.set(_key, static_cast<const int&>(value));
2889         return *this;
2890      }
2891
2892      operator const int&() const {
2893        return static_cast<const IterableIntMap&>(_map)[_key];
2894      }
2895
2896      Reference& operator=(int value) {
2897        _map.set(_key, value);
2898        return *this;
2899      }
2900      Reference& operator++() {
2901        _map.set(_key, _map[_key] + 1);
2902        return *this;
2903      }
2904      int operator++(int) {
2905        int value = _map[_key];
2906        _map.set(_key, value + 1);
2907        return value;
2908      }
2909      Reference& operator--() {
2910        _map.set(_key, _map[_key] - 1);
2911        return *this;
2912      }
2913      int operator--(int) {
2914        int value = _map[_key];
2915        _map.set(_key, value - 1);
2916        return value;
2917      }
2918      Reference& operator+=(int value) {
2919        _map.set(_key, _map[_key] + value);
2920        return *this;
2921      }
2922      Reference& operator-=(int value) {
2923        _map.set(_key, _map[_key] - value);
2924        return *this;
2925      }
2926      Reference& operator*=(int value) {
2927        _map.set(_key, _map[_key] * value);
2928        return *this;
2929      }
2930      Reference& operator/=(int value) {
2931        _map.set(_key, _map[_key] / value);
2932        return *this;
2933      }
2934      Reference& operator%=(int value) {
2935        _map.set(_key, _map[_key] % value);
2936        return *this;
2937      }
2938      Reference& operator&=(int value) {
2939        _map.set(_key, _map[_key] & value);
2940        return *this;
2941      }
2942      Reference& operator|=(int value) {
2943        _map.set(_key, _map[_key] | value);
2944        return *this;
2945      }
2946      Reference& operator^=(int value) {
2947        _map.set(_key, _map[_key] ^ value);
2948        return *this;
2949      }
2950      Reference& operator<<=(int value) {
2951        _map.set(_key, _map[_key] << value);
2952        return *this;
2953      }
2954      Reference& operator>>=(int value) {
2955        _map.set(_key, _map[_key] >> value);
2956        return *this;
2957      }
2958
2959    private:
2960      Key _key;
2961      IterableIntMap& _map;
2962    };
2963
2964    /// The const reference type.
2965    typedef const Value& ConstReference;
2966
2967    /// \brief Gives back the maximal value plus one.
2968    ///
2969    /// Gives back the maximal value plus one.
2970    int size() const {
2971      return _first.size();
2972    }
2973
2974    /// \brief Set operation of the map.
2975    ///
2976    /// Set operation of the map.
2977    void set(const Key& key, const Value& value) {
2978      unlace(key);
2979      Parent::operator[](key).value = value;
2980      lace(key);
2981    }
2982
2983    /// \brief Const subscript operator of the map.
2984    ///
2985    /// Const subscript operator of the map.
2986    const Value& operator[](const Key& key) const {
2987      return Parent::operator[](key).value;
2988    }
2989
2990    /// \brief Subscript operator of the map.
2991    ///
2992    /// Subscript operator of the map.
2993    Reference operator[](const Key& key) {
2994      return Reference(*this, key);
2995    }
2996
2997    /// \brief Iterator for the keys with the same value.
2998    ///
2999    /// Iterator for the keys with the same value. It works
3000    /// like a graph item iterator, it can be converted to
3001    /// the item type of the map, incremented with \c ++ operator, and
3002    /// if the iterator leaves the last valid item, it will be equal to
3003    /// \c INVALID.
3004    class ItemIt : public Key {
3005    public:
3006      typedef Key Parent;
3007
3008      /// \brief Invalid constructor \& conversion.
3009      ///
3010      /// This constructor initializes the iterator to be invalid.
3011      /// \sa Invalid for more details.
3012      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
3013
3014      /// \brief Creates an iterator with a value.
3015      ///
3016      /// Creates an iterator with a value. It iterates on the
3017      /// keys mapped to the given value.
3018      /// \param map The IterableIntMap.
3019      /// \param value The value.
3020      ItemIt(const IterableIntMap& map, int value) : _map(&map) {
3021        if (value < 0 || value >= int(_map->_first.size())) {
3022          Parent::operator=(INVALID);
3023        } else {
3024          Parent::operator=(_map->_first[value]);
3025        }
3026      }
3027
3028      /// \brief Increment operator.
3029      ///
3030      /// Increment operator.
3031      ItemIt& operator++() {
3032        Parent::operator=(_map->IterableIntMap::Parent::
3033                          operator[](static_cast<Parent&>(*this)).next);
3034        return *this;
3035      }
3036
3037    private:
3038      const IterableIntMap* _map;
3039    };
3040
3041    /// \brief STL style iterator for the keys with the same value.
3042    ///
3043    /// This is an STL style wrapper for \ref ItemIt.
3044    /// It can be used in range-based for loops, STL algorithms, etc.
3045    LemonRangeWrapper2<ItemIt, IterableIntMap, int>
3046    items(int value) {
3047      return LemonRangeWrapper2<ItemIt, IterableIntMap, int>(*this, value);
3048    }
3049
3050
3051  protected:
3052
3053    virtual void erase(const Key& key) {
3054      unlace(key);
3055      Parent::erase(key);
3056    }
3057
3058    virtual void erase(const std::vector<Key>& keys) {
3059      for (int i = 0; i < int(keys.size()); ++i) {
3060        unlace(keys[i]);
3061      }
3062      Parent::erase(keys);
3063    }
3064
3065    virtual void clear() {
3066      _first.clear();
3067      Parent::clear();
3068    }
3069
3070  private:
3071    std::vector<Key> _first;
3072  };
3073
3074  namespace _maps_bits {
3075    template <typename Item, typename Value>
3076    struct IterableValueMapNode {
3077      IterableValueMapNode(Value _value = Value()) : value(_value) {}
3078      Item prev, next;
3079      Value value;
3080    };
3081  }
3082
3083  /// \brief Dynamic iterable map for comparable values.
3084  ///
3085  /// This class provides a special graph map type which can store a
3086  /// comparable value for graph items (\c Node, \c Arc or \c Edge).
3087  /// For each value it is possible to iterate on the keys mapped to
3088  /// the value (\c ItemIt), and the values of the map can be accessed
3089  /// with an STL compatible forward iterator (\c ValueIt).
3090  /// The map stores a linked list for each value, which contains
3091  /// the items mapped to the value, and the used values are stored
3092  /// in balanced binary tree (\c std::map).
3093  ///
3094  /// \ref IterableBoolMap and \ref IterableIntMap are similar classes
3095  /// specialized for \c bool and \c int values, respectively.
3096  ///
3097  /// This type is not reference map, so it cannot be modified with
3098  /// the subscript operator.
3099  ///
3100  /// \tparam GR The graph type.
3101  /// \tparam K The key type of the map (\c GR::Node, \c GR::Arc or
3102  /// \c GR::Edge).
3103  /// \tparam V The value type of the map. It can be any comparable
3104  /// value type.
3105  ///
3106  /// \see IterableBoolMap, IterableIntMap
3107  /// \see CrossRefMap
3108  template <typename GR, typename K, typename V>
3109  class IterableValueMap
3110    : protected ItemSetTraits<GR, K>::
3111        template Map<_maps_bits::IterableValueMapNode<K, V> >::Type {
3112  public:
3113    typedef typename ItemSetTraits<GR, K>::
3114      template Map<_maps_bits::IterableValueMapNode<K, V> >::Type Parent;
3115
3116    /// The key type
3117    typedef K Key;
3118    /// The value type
3119    typedef V Value;
3120    /// The graph type
3121    typedef GR Graph;
3122
3123  public:
3124
3125    /// \brief Constructor of the map with a given value.
3126    ///
3127    /// Constructor of the map with a given value.
3128    explicit IterableValueMap(const Graph& graph,
3129                              const Value& value = Value())
3130      : Parent(graph, _maps_bits::IterableValueMapNode<K, V>(value)) {
3131      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
3132        lace(it);
3133      }
3134    }
3135
3136  protected:
3137
3138    void unlace(const Key& key) {
3139      typename Parent::Value& node = Parent::operator[](key);
3140      if (node.prev != INVALID) {
3141        Parent::operator[](node.prev).next = node.next;
3142      } else {
3143        if (node.next != INVALID) {
3144          _first[node.value] = node.next;
3145        } else {
3146          _first.erase(node.value);
3147        }
3148      }
3149      if (node.next != INVALID) {
3150        Parent::operator[](node.next).prev = node.prev;
3151      }
3152    }
3153
3154    void lace(const Key& key) {
3155      typename Parent::Value& node = Parent::operator[](key);
3156      typename std::map<Value, Key>::iterator it = _first.find(node.value);
3157      if (it == _first.end()) {
3158        node.prev = node.next = INVALID;
3159        _first.insert(std::make_pair(node.value, key));
3160      } else {
3161        node.prev = INVALID;
3162        node.next = it->second;
3163        if (node.next != INVALID) {
3164          Parent::operator[](node.next).prev = key;
3165        }
3166        it->second = key;
3167      }
3168    }
3169
3170  public:
3171
3172    /// \brief Forward iterator for values.
3173    ///
3174    /// This iterator is an STL compatible forward
3175    /// iterator on the values of the map. The values can
3176    /// be accessed in the <tt>[beginValue, endValue)</tt> range.
3177    class ValueIt
3178      : public std::iterator<std::forward_iterator_tag, Value> {
3179      friend class IterableValueMap;
3180    private:
3181      ValueIt(typename std::map<Value, Key>::const_iterator _it)
3182        : it(_it) {}
3183    public:
3184
3185      /// Constructor
3186      ValueIt() {}
3187
3188      /// \e
3189      ValueIt& operator++() { ++it; return *this; }
3190      /// \e
3191      ValueIt operator++(int) {
3192        ValueIt tmp(*this);
3193        operator++();
3194        return tmp;
3195      }
3196
3197      /// \e
3198      const Value& operator*() const { return it->first; }
3199      /// \e
3200      const Value* operator->() const { return &(it->first); }
3201
3202      /// \e
3203      bool operator==(ValueIt jt) const { return it == jt.it; }
3204      /// \e
3205      bool operator!=(ValueIt jt) const { return it != jt.it; }
3206
3207    private:
3208      typename std::map<Value, Key>::const_iterator it;
3209    };
3210
3211    /// \brief Returns an iterator to the first value.
3212    ///
3213    /// Returns an STL compatible iterator to the
3214    /// first value of the map. The values of the
3215    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
3216    /// range.
3217    ValueIt beginValue() const {
3218      return ValueIt(_first.begin());
3219    }
3220
3221    /// \brief Returns an iterator after the last value.
3222    ///
3223    /// Returns an STL compatible iterator after the
3224    /// last value of the map. The values of the
3225    /// map can be accessed in the <tt>[beginValue, endValue)</tt>
3226    /// range.
3227    ValueIt endValue() const {
3228      return ValueIt(_first.end());
3229    }
3230
3231    /// \brief Set operation of the map.
3232    ///
3233    /// Set operation of the map.
3234    void set(const Key& key, const Value& value) {
3235      unlace(key);
3236      Parent::operator[](key).value = value;
3237      lace(key);
3238    }
3239
3240    /// \brief Const subscript operator of the map.
3241    ///
3242    /// Const subscript operator of the map.
3243    const Value& operator[](const Key& key) const {
3244      return Parent::operator[](key).value;
3245    }
3246
3247    /// \brief Iterator for the keys with the same value.
3248    ///
3249    /// Iterator for the keys with the same value. It works
3250    /// like a graph item iterator, it can be converted to
3251    /// the item type of the map, incremented with \c ++ operator, and
3252    /// if the iterator leaves the last valid item, it will be equal to
3253    /// \c INVALID.
3254    class ItemIt : public Key {
3255    public:
3256      typedef Key Parent;
3257
3258      /// \brief Invalid constructor \& conversion.
3259      ///
3260      /// This constructor initializes the iterator to be invalid.
3261      /// \sa Invalid for more details.
3262      ItemIt(Invalid) : Parent(INVALID), _map(0) {}
3263
3264      /// \brief Creates an iterator with a value.
3265      ///
3266      /// Creates an iterator with a value. It iterates on the
3267      /// keys which have the given value.
3268      /// \param map The IterableValueMap
3269      /// \param value The value
3270      ItemIt(const IterableValueMap& map, const Value& value) : _map(&map) {
3271        typename std::map<Value, Key>::const_iterator it =
3272          map._first.find(value);
3273        if (it == map._first.end()) {
3274          Parent::operator=(INVALID);
3275        } else {
3276          Parent::operator=(it->second);
3277        }
3278      }
3279
3280      /// \brief Increment operator.
3281      ///
3282      /// Increment Operator.
3283      ItemIt& operator++() {
3284        Parent::operator=(_map->IterableValueMap::Parent::
3285                          operator[](static_cast<Parent&>(*this)).next);
3286        return *this;
3287      }
3288
3289
3290    private:
3291      const IterableValueMap* _map;
3292    };
3293
3294    /// \brief STL style iterator for the keys with the same value.
3295    ///
3296    /// This is an STL style wrapper for \ref ItemIt.
3297    /// It can be used in range-based for loops, STL algorithms, etc.
3298    LemonRangeWrapper2<ItemIt, IterableValueMap, V>
3299    items(const V& value) {
3300      return LemonRangeWrapper2<ItemIt, IterableValueMap, V>(*this, value);
3301    }
3302
3303
3304  protected:
3305
3306    virtual void add(const Key& key) {
3307      Parent::add(key);
3308      lace(key);
3309    }
3310
3311    virtual void add(const std::vector<Key>& keys) {
3312      Parent::add(keys);
3313      for (int i = 0; i < int(keys.size()); ++i) {
3314        lace(keys[i]);
3315      }
3316    }
3317
3318    virtual void erase(const Key& key) {
3319      unlace(key);
3320      Parent::erase(key);
3321    }
3322
3323    virtual void erase(const std::vector<Key>& keys) {
3324      for (int i = 0; i < int(keys.size()); ++i) {
3325        unlace(keys[i]);
3326      }
3327      Parent::erase(keys);
3328    }
3329
3330    virtual void build() {
3331      Parent::build();
3332      for (typename Parent::ItemIt it(*this); it != INVALID; ++it) {
3333        lace(it);
3334      }
3335    }
3336
3337    virtual void clear() {
3338      _first.clear();
3339      Parent::clear();
3340    }
3341
3342  private:
3343    std::map<Value, Key> _first;
3344  };
3345
3346  /// \brief Map of the source nodes of arcs in a digraph.
3347  ///
3348  /// SourceMap provides access for the source node of each arc in a digraph,
3349  /// which is returned by the \c source() function of the digraph.
3350  /// \tparam GR The digraph type.
3351  /// \see TargetMap
3352  template <typename GR>
3353  class SourceMap {
3354  public:
3355
3356    /// The key type (the \c Arc type of the digraph).
3357    typedef typename GR::Arc Key;
3358    /// The value type (the \c Node type of the digraph).
3359    typedef typename GR::Node Value;
3360
3361    /// \brief Constructor
3362    ///
3363    /// Constructor.
3364    /// \param digraph The digraph that the map belongs to.
3365    explicit SourceMap(const GR& digraph) : _graph(digraph) {}
3366
3367    /// \brief Returns the source node of the given arc.
3368    ///
3369    /// Returns the source node of the given arc.
3370    Value operator[](const Key& arc) const {
3371      return _graph.source(arc);
3372    }
3373
3374  private:
3375    const GR& _graph;
3376  };
3377
3378  /// \brief Returns a \c SourceMap class.
3379  ///
3380  /// This function just returns an \c SourceMap class.
3381  /// \relates SourceMap
3382  template <typename GR>
3383  inline SourceMap<GR> sourceMap(const GR& graph) {
3384    return SourceMap<GR>(graph);
3385  }
3386
3387  /// \brief Map of the target nodes of arcs in a digraph.
3388  ///
3389  /// TargetMap provides access for the target node of each arc in a digraph,
3390  /// which is returned by the \c target() function of the digraph.
3391  /// \tparam GR The digraph type.
3392  /// \see SourceMap
3393  template <typename GR>
3394  class TargetMap {
3395  public:
3396
3397    /// The key type (the \c Arc type of the digraph).
3398    typedef typename GR::Arc Key;
3399    /// The value type (the \c Node type of the digraph).
3400    typedef typename GR::Node Value;
3401
3402    /// \brief Constructor
3403    ///
3404    /// Constructor.
3405    /// \param digraph The digraph that the map belongs to.
3406    explicit TargetMap(const GR& digraph) : _graph(digraph) {}
3407
3408    /// \brief Returns the target node of the given arc.
3409    ///
3410    /// Returns the target node of the given arc.
3411    Value operator[](const Key& e) const {
3412      return _graph.target(e);
3413    }
3414
3415  private:
3416    const GR& _graph;
3417  };
3418
3419  /// \brief Returns a \c TargetMap class.
3420  ///
3421  /// This function just returns a \c TargetMap class.
3422  /// \relates TargetMap
3423  template <typename GR>
3424  inline TargetMap<GR> targetMap(const GR& graph) {
3425    return TargetMap<GR>(graph);
3426  }
3427
3428  /// \brief Map of the "forward" directed arc view of edges in a graph.
3429  ///
3430  /// ForwardMap provides access for the "forward" directed arc view of
3431  /// each edge in a graph, which is returned by the \c direct() function
3432  /// of the graph with \c true parameter.
3433  /// \tparam GR The graph type.
3434  /// \see BackwardMap
3435  template <typename GR>
3436  class ForwardMap {
3437  public:
3438
3439    /// The key type (the \c Edge type of the digraph).
3440    typedef typename GR::Edge Key;
3441    /// The value type (the \c Arc type of the digraph).
3442    typedef typename GR::Arc Value;
3443
3444    /// \brief Constructor
3445    ///
3446    /// Constructor.
3447    /// \param graph The graph that the map belongs to.
3448    explicit ForwardMap(const GR& graph) : _graph(graph) {}
3449
3450    /// \brief Returns the "forward" directed arc view of the given edge.
3451    ///
3452    /// Returns the "forward" directed arc view of the given edge.
3453    Value operator[](const Key& key) const {
3454      return _graph.direct(key, true);
3455    }
3456
3457  private:
3458    const GR& _graph;
3459  };
3460
3461  /// \brief Returns a \c ForwardMap class.
3462  ///
3463  /// This function just returns an \c ForwardMap class.
3464  /// \relates ForwardMap
3465  template <typename GR>
3466  inline ForwardMap<GR> forwardMap(const GR& graph) {
3467    return ForwardMap<GR>(graph);
3468  }
3469
3470  /// \brief Map of the "backward" directed arc view of edges in a graph.
3471  ///
3472  /// BackwardMap provides access for the "backward" directed arc view of
3473  /// each edge in a graph, which is returned by the \c direct() function
3474  /// of the graph with \c false parameter.
3475  /// \tparam GR The graph type.
3476  /// \see ForwardMap
3477  template <typename GR>
3478  class BackwardMap {
3479  public:
3480
3481    /// The key type (the \c Edge type of the digraph).
3482    typedef typename GR::Edge Key;
3483    /// The value type (the \c Arc type of the digraph).
3484    typedef typename GR::Arc Value;
3485
3486    /// \brief Constructor
3487    ///
3488    /// Constructor.
3489    /// \param graph The graph that the map belongs to.
3490    explicit BackwardMap(const GR& graph) : _graph(graph) {}
3491
3492    /// \brief Returns the "backward" directed arc view of the given edge.
3493    ///
3494    /// Returns the "backward" directed arc view of the given edge.
3495    Value operator[](const Key& key) const {
3496      return _graph.direct(key, false);
3497    }
3498
3499  private:
3500    const GR& _graph;
3501  };
3502
3503  /// \brief Returns a \c BackwardMap class
3504
3505  /// This function just returns a \c BackwardMap class.
3506  /// \relates BackwardMap
3507  template <typename GR>
3508  inline BackwardMap<GR> backwardMap(const GR& graph) {
3509    return BackwardMap<GR>(graph);
3510  }
3511
3512  /// \brief Map of the in-degrees of nodes in a digraph.
3513  ///
3514  /// This map returns the in-degree of a node. Once it is constructed,
3515  /// the degrees are stored in a standard \c NodeMap, so each query is done
3516  /// in constant time. On the other hand, the values are updated automatically
3517  /// whenever the digraph changes.
3518  ///
3519  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
3520  /// may provide alternative ways to modify the digraph.
3521  /// The correct behavior of InDegMap is not guarantied if these additional
3522  /// features are used. For example, the functions
3523  /// \ref ListDigraph::changeSource() "changeSource()",
3524  /// \ref ListDigraph::changeTarget() "changeTarget()" and
3525  /// \ref ListDigraph::reverseArc() "reverseArc()"
3526  /// of \ref ListDigraph will \e not update the degree values correctly.
3527  ///
3528  /// \sa OutDegMap
3529  template <typename GR>
3530  class InDegMap
3531    : protected ItemSetTraits<GR, typename GR::Arc>
3532      ::ItemNotifier::ObserverBase {
3533
3534  public:
3535
3536    /// The graph type of InDegMap
3537    typedef GR Graph;
3538    typedef GR Digraph;
3539    /// The key type
3540    typedef typename Digraph::Node Key;
3541    /// The value type
3542    typedef int Value;
3543
3544    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
3545    ::ItemNotifier::ObserverBase Parent;
3546
3547  private:
3548
3549    class AutoNodeMap
3550      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
3551    public:
3552
3553      typedef typename ItemSetTraits<Digraph, Key>::
3554      template Map<int>::Type Parent;
3555
3556      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
3557
3558      virtual void add(const Key& key) {
3559        Parent::add(key);
3560        Parent::set(key, 0);
3561      }
3562
3563      virtual void add(const std::vector<Key>& keys) {
3564        Parent::add(keys);
3565        for (int i = 0; i < int(keys.size()); ++i) {
3566          Parent::set(keys[i], 0);
3567        }
3568      }
3569
3570      virtual void build() {
3571        Parent::build();
3572        Key it;
3573        typename Parent::Notifier* nf = Parent::notifier();
3574        for (nf->first(it); it != INVALID; nf->next(it)) {
3575          Parent::set(it, 0);
3576        }
3577      }
3578    };
3579
3580  public:
3581
3582    /// \brief Constructor.
3583    ///
3584    /// Constructor for creating an in-degree map.
3585    explicit InDegMap(const Digraph& graph)
3586      : _digraph(graph), _deg(graph) {
3587      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
3588
3589      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
3590        _deg[it] = countInArcs(_digraph, it);
3591      }
3592    }
3593
3594    /// \brief Gives back the in-degree of a Node.
3595    ///
3596    /// Gives back the in-degree of a Node.
3597    int operator[](const Key& key) const {
3598      return _deg[key];
3599    }
3600
3601  protected:
3602
3603    typedef typename Digraph::Arc Arc;
3604
3605    virtual void add(const Arc& arc) {
3606      ++_deg[_digraph.target(arc)];
3607    }
3608
3609    virtual void add(const std::vector<Arc>& arcs) {
3610      for (int i = 0; i < int(arcs.size()); ++i) {
3611        ++_deg[_digraph.target(arcs[i])];
3612      }
3613    }
3614
3615    virtual void erase(const Arc& arc) {
3616      --_deg[_digraph.target(arc)];
3617    }
3618
3619    virtual void erase(const std::vector<Arc>& arcs) {
3620      for (int i = 0; i < int(arcs.size()); ++i) {
3621        --_deg[_digraph.target(arcs[i])];
3622      }
3623    }
3624
3625    virtual void build() {
3626      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
3627        _deg[it] = countInArcs(_digraph, it);
3628      }
3629    }
3630
3631    virtual void clear() {
3632      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
3633        _deg[it] = 0;
3634      }
3635    }
3636  private:
3637
3638    const Digraph& _digraph;
3639    AutoNodeMap _deg;
3640  };
3641
3642  /// \brief Map of the out-degrees of nodes in a digraph.
3643  ///
3644  /// This map returns the out-degree of a node. Once it is constructed,
3645  /// the degrees are stored in a standard \c NodeMap, so each query is done
3646  /// in constant time. On the other hand, the values are updated automatically
3647  /// whenever the digraph changes.
3648  ///
3649  /// \warning Besides \c addNode() and \c addArc(), a digraph structure
3650  /// may provide alternative ways to modify the digraph.
3651  /// The correct behavior of OutDegMap is not guarantied if these additional
3652  /// features are used. For example, the functions
3653  /// \ref ListDigraph::changeSource() "changeSource()",
3654  /// \ref ListDigraph::changeTarget() "changeTarget()" and
3655  /// \ref ListDigraph::reverseArc() "reverseArc()"
3656  /// of \ref ListDigraph will \e not update the degree values correctly.
3657  ///
3658  /// \sa InDegMap
3659  template <typename GR>
3660  class OutDegMap
3661    : protected ItemSetTraits<GR, typename GR::Arc>
3662      ::ItemNotifier::ObserverBase {
3663
3664  public:
3665
3666    /// The graph type of OutDegMap
3667    typedef GR Graph;
3668    typedef GR Digraph;
3669    /// The key type
3670    typedef typename Digraph::Node Key;
3671    /// The value type
3672    typedef int Value;
3673
3674    typedef typename ItemSetTraits<Digraph, typename Digraph::Arc>
3675    ::ItemNotifier::ObserverBase Parent;
3676
3677  private:
3678
3679    class AutoNodeMap
3680      : public ItemSetTraits<Digraph, Key>::template Map<int>::Type {
3681    public:
3682
3683      typedef typename ItemSetTraits<Digraph, Key>::
3684      template Map<int>::Type Parent;
3685
3686      AutoNodeMap(const Digraph& digraph) : Parent(digraph, 0) {}
3687
3688      virtual void add(const Key& key) {
3689        Parent::add(key);
3690        Parent::set(key, 0);
3691      }
3692      virtual void add(const std::vector<Key>& keys) {
3693        Parent::add(keys);
3694        for (int i = 0; i < int(keys.size()); ++i) {
3695          Parent::set(keys[i], 0);
3696        }
3697      }
3698      virtual void build() {
3699        Parent::build();
3700        Key it;
3701        typename Parent::Notifier* nf = Parent::notifier();
3702        for (nf->first(it); it != INVALID; nf->next(it)) {
3703          Parent::set(it, 0);
3704        }
3705      }
3706    };
3707
3708  public:
3709
3710    /// \brief Constructor.
3711    ///
3712    /// Constructor for creating an out-degree map.
3713    explicit OutDegMap(const Digraph& graph)
3714      : _digraph(graph), _deg(graph) {
3715      Parent::attach(_digraph.notifier(typename Digraph::Arc()));
3716
3717      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
3718        _deg[it] = countOutArcs(_digraph, it);
3719      }
3720    }
3721
3722    /// \brief Gives back the out-degree of a Node.
3723    ///
3724    /// Gives back the out-degree of a Node.
3725    int operator[](const Key& key) const {
3726      return _deg[key];
3727    }
3728
3729  protected:
3730
3731    typedef typename Digraph::Arc Arc;
3732
3733    virtual void add(const Arc& arc) {
3734      ++_deg[_digraph.source(arc)];
3735    }
3736
3737    virtual void add(const std::vector<Arc>& arcs) {
3738      for (int i = 0; i < int(arcs.size()); ++i) {
3739        ++_deg[_digraph.source(arcs[i])];
3740      }
3741    }
3742
3743    virtual void erase(const Arc& arc) {
3744      --_deg[_digraph.source(arc)];
3745    }
3746
3747    virtual void erase(const std::vector<Arc>& arcs) {
3748      for (int i = 0; i < int(arcs.size()); ++i) {
3749        --_deg[_digraph.source(arcs[i])];
3750      }
3751    }
3752
3753    virtual void build() {
3754      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
3755        _deg[it] = countOutArcs(_digraph, it);
3756      }
3757    }
3758
3759    virtual void clear() {
3760      for(typename Digraph::NodeIt it(_digraph); it != INVALID; ++it) {
3761        _deg[it] = 0;
3762      }
3763    }
3764  private:
3765
3766    const Digraph& _digraph;
3767    AutoNodeMap _deg;
3768  };
3769
3770  /// \brief Potential difference map
3771  ///
3772  /// PotentialDifferenceMap returns the difference between the potentials of
3773  /// the source and target nodes of each arc in a digraph, i.e. it returns
3774  /// \code
3775  ///   potential[gr.target(arc)] - potential[gr.source(arc)].
3776  /// \endcode
3777  /// \tparam GR The digraph type.
3778  /// \tparam POT A node map storing the potentials.
3779  template <typename GR, typename POT>
3780  class PotentialDifferenceMap {
3781  public:
3782    /// Key type
3783    typedef typename GR::Arc Key;
3784    /// Value type
3785    typedef typename POT::Value Value;
3786
3787    /// \brief Constructor
3788    ///
3789    /// Contructor of the map.
3790    explicit PotentialDifferenceMap(const GR& gr,
3791                                    const POT& potential)
3792      : _digraph(gr), _potential(potential) {}
3793
3794    /// \brief Returns the potential difference for the given arc.
3795    ///
3796    /// Returns the potential difference for the given arc, i.e.
3797    /// \code
3798    ///   potential[gr.target(arc)] - potential[gr.source(arc)].
3799    /// \endcode
3800    Value operator[](const Key& arc) const {
3801      return _potential[_digraph.target(arc)] -
3802        _potential[_digraph.source(arc)];
3803    }
3804
3805  private:
3806    const GR& _digraph;
3807    const POT& _potential;
3808  };
3809
3810  /// \brief Returns a PotentialDifferenceMap.
3811  ///
3812  /// This function just returns a PotentialDifferenceMap.
3813  /// \relates PotentialDifferenceMap
3814  template <typename GR, typename POT>
3815  PotentialDifferenceMap<GR, POT>
3816  potentialDifferenceMap(const GR& gr, const POT& potential) {
3817    return PotentialDifferenceMap<GR, POT>(gr, potential);
3818  }
3819
3820
3821  /// \brief Copy the values of a graph map to another map.
3822  ///
3823  /// This function copies the values of a graph map to another graph map.
3824  /// \c To::Key must be equal or convertible to \c From::Key and
3825  /// \c From::Value must be equal or convertible to \c To::Value.
3826  ///
3827  /// For example, an edge map of \c int value type can be copied to
3828  /// an arc map of \c double value type in an undirected graph, but
3829  /// an arc map cannot be copied to an edge map.
3830  /// Note that even a \ref ConstMap can be copied to a standard graph map,
3831  /// but \ref mapFill() can also be used for this purpose.
3832  ///
3833  /// \param gr The graph for which the maps are defined.
3834  /// \param from The map from which the values have to be copied.
3835  /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
3836  /// \param to The map to which the values have to be copied.
3837  /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
3838  template <typename GR, typename From, typename To>
3839  void mapCopy(const GR& gr, const From& from, To& to) {
3840    typedef typename To::Key Item;
3841    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
3842
3843    for (ItemIt it(gr); it != INVALID; ++it) {
3844      to.set(it, from[it]);
3845    }
3846  }
3847
3848  /// \brief Compare two graph maps.
3849  ///
3850  /// This function compares the values of two graph maps. It returns
3851  /// \c true if the maps assign the same value for all items in the graph.
3852  /// The \c Key type of the maps (\c Node, \c Arc or \c Edge) must be equal
3853  /// and their \c Value types must be comparable using \c %operator==().
3854  ///
3855  /// \param gr The graph for which the maps are defined.
3856  /// \param map1 The first map.
3857  /// \param map2 The second map.
3858  template <typename GR, typename Map1, typename Map2>
3859  bool mapCompare(const GR& gr, const Map1& map1, const Map2& map2) {
3860    typedef typename Map2::Key Item;
3861    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
3862
3863    for (ItemIt it(gr); it != INVALID; ++it) {
3864      if (!(map1[it] == map2[it])) return false;
3865    }
3866    return true;
3867  }
3868
3869  /// \brief Return an item having minimum value of a graph map.
3870  ///
3871  /// This function returns an item (\c Node, \c Arc or \c Edge) having
3872  /// minimum value of the given graph map.
3873  /// If the item set is empty, it returns \c INVALID.
3874  ///
3875  /// \param gr The graph for which the map is defined.
3876  /// \param map The graph map.
3877  template <typename GR, typename Map>
3878  typename Map::Key mapMin(const GR& gr, const Map& map) {
3879    return mapMin(gr, map, std::less<typename Map::Value>());
3880  }
3881
3882  /// \brief Return an item having minimum value of a graph map.
3883  ///
3884  /// This function returns an item (\c Node, \c Arc or \c Edge) having
3885  /// minimum value of the given graph map.
3886  /// If the item set is empty, it returns \c INVALID.
3887  ///
3888  /// \param gr The graph for which the map is defined.
3889  /// \param map The graph map.
3890  /// \param comp Comparison function object.
3891  template <typename GR, typename Map, typename Comp>
3892  typename Map::Key mapMin(const GR& gr, const Map& map, const Comp& comp) {
3893    typedef typename Map::Key Item;
3894    typedef typename Map::Value Value;
3895    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
3896
3897    ItemIt min_item(gr);
3898    if (min_item == INVALID) return INVALID;
3899    Value min = map[min_item];
3900    for (ItemIt it(gr); it != INVALID; ++it) {
3901      if (comp(map[it], min)) {
3902        min = map[it];
3903        min_item = it;
3904      }
3905    }
3906    return min_item;
3907  }
3908
3909  /// \brief Return an item having maximum value of a graph map.
3910  ///
3911  /// This function returns an item (\c Node, \c Arc or \c Edge) having
3912  /// maximum value of the given graph map.
3913  /// If the item set is empty, it returns \c INVALID.
3914  ///
3915  /// \param gr The graph for which the map is defined.
3916  /// \param map The graph map.
3917  template <typename GR, typename Map>
3918  typename Map::Key mapMax(const GR& gr, const Map& map) {
3919    return mapMax(gr, map, std::less<typename Map::Value>());
3920  }
3921
3922  /// \brief Return an item having maximum value of a graph map.
3923  ///
3924  /// This function returns an item (\c Node, \c Arc or \c Edge) having
3925  /// maximum value of the given graph map.
3926  /// If the item set is empty, it returns \c INVALID.
3927  ///
3928  /// \param gr The graph for which the map is defined.
3929  /// \param map The graph map.
3930  /// \param comp Comparison function object.
3931  template <typename GR, typename Map, typename Comp>
3932  typename Map::Key mapMax(const GR& gr, const Map& map, const Comp& comp) {
3933    typedef typename Map::Key Item;
3934    typedef typename Map::Value Value;
3935    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
3936
3937    ItemIt max_item(gr);
3938    if (max_item == INVALID) return INVALID;
3939    Value max = map[max_item];
3940    for (ItemIt it(gr); it != INVALID; ++it) {
3941      if (comp(max, map[it])) {
3942        max = map[it];
3943        max_item = it;
3944      }
3945    }
3946    return max_item;
3947  }
3948
3949  /// \brief Return the minimum value of a graph map.
3950  ///
3951  /// This function returns the minimum value of the given graph map.
3952  /// The corresponding item set of the graph must not be empty.
3953  ///
3954  /// \param gr The graph for which the map is defined.
3955  /// \param map The graph map.
3956  template <typename GR, typename Map>
3957  typename Map::Value mapMinValue(const GR& gr, const Map& map) {
3958    return map[mapMin(gr, map, std::less<typename Map::Value>())];
3959  }
3960
3961  /// \brief Return the minimum value of a graph map.
3962  ///
3963  /// This function returns the minimum value of the given graph map.
3964  /// The corresponding item set of the graph must not be empty.
3965  ///
3966  /// \param gr The graph for which the map is defined.
3967  /// \param map The graph map.
3968  /// \param comp Comparison function object.
3969  template <typename GR, typename Map, typename Comp>
3970  typename Map::Value
3971  mapMinValue(const GR& gr, const Map& map, const Comp& comp) {
3972    return map[mapMin(gr, map, comp)];
3973  }
3974
3975  /// \brief Return the maximum value of a graph map.
3976  ///
3977  /// This function returns the maximum value of the given graph map.
3978  /// The corresponding item set of the graph must not be empty.
3979  ///
3980  /// \param gr The graph for which the map is defined.
3981  /// \param map The graph map.
3982  template <typename GR, typename Map>
3983  typename Map::Value mapMaxValue(const GR& gr, const Map& map) {
3984    return map[mapMax(gr, map, std::less<typename Map::Value>())];
3985  }
3986
3987  /// \brief Return the maximum value of a graph map.
3988  ///
3989  /// This function returns the maximum value of the given graph map.
3990  /// The corresponding item set of the graph must not be empty.
3991  ///
3992  /// \param gr The graph for which the map is defined.
3993  /// \param map The graph map.
3994  /// \param comp Comparison function object.
3995  template <typename GR, typename Map, typename Comp>
3996  typename Map::Value
3997  mapMaxValue(const GR& gr, const Map& map, const Comp& comp) {
3998    return map[mapMax(gr, map, comp)];
3999  }
4000
4001  /// \brief Return an item having a specified value in a graph map.
4002  ///
4003  /// This function returns an item (\c Node, \c Arc or \c Edge) having
4004  /// the specified assigned value in the given graph map.
4005  /// If no such item exists, it returns \c INVALID.
4006  ///
4007  /// \param gr The graph for which the map is defined.
4008  /// \param map The graph map.
4009  /// \param val The value that have to be found.
4010  template <typename GR, typename Map>
4011  typename Map::Key
4012  mapFind(const GR& gr, const Map& map, const typename Map::Value& val) {
4013    typedef typename Map::Key Item;
4014    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
4015
4016    for (ItemIt it(gr); it != INVALID; ++it) {
4017      if (map[it] == val) return it;
4018    }
4019    return INVALID;
4020  }
4021
4022  /// \brief Return an item having value for which a certain predicate is
4023  /// true in a graph map.
4024  ///
4025  /// This function returns an item (\c Node, \c Arc or \c Edge) having
4026  /// such assigned value for which the specified predicate is true
4027  /// in the given graph map.
4028  /// If no such item exists, it returns \c INVALID.
4029  ///
4030  /// \param gr The graph for which the map is defined.
4031  /// \param map The graph map.
4032  /// \param pred The predicate function object.
4033  template <typename GR, typename Map, typename Pred>
4034  typename Map::Key
4035  mapFindIf(const GR& gr, const Map& map, const Pred& pred) {
4036    typedef typename Map::Key Item;
4037    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
4038
4039    for (ItemIt it(gr); it != INVALID; ++it) {
4040      if (pred(map[it])) return it;
4041    }
4042    return INVALID;
4043  }
4044
4045  /// \brief Return the number of items having a specified value in a
4046  /// graph map.
4047  ///
4048  /// This function returns the number of items (\c Node, \c Arc or \c Edge)
4049  /// having the specified assigned value in the given graph map.
4050  ///
4051  /// \param gr The graph for which the map is defined.
4052  /// \param map The graph map.
4053  /// \param val The value that have to be counted.
4054  template <typename GR, typename Map>
4055  int mapCount(const GR& gr, const Map& map, const typename Map::Value& val) {
4056    typedef typename Map::Key Item;
4057    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
4058
4059    int cnt = 0;
4060    for (ItemIt it(gr); it != INVALID; ++it) {
4061      if (map[it] == val) ++cnt;
4062    }
4063    return cnt;
4064  }
4065
4066  /// \brief Return the number of items having values for which a certain
4067  /// predicate is true in a graph map.
4068  ///
4069  /// This function returns the number of items (\c Node, \c Arc or \c Edge)
4070  /// having such assigned values for which the specified predicate is true
4071  /// in the given graph map.
4072  ///
4073  /// \param gr The graph for which the map is defined.
4074  /// \param map The graph map.
4075  /// \param pred The predicate function object.
4076  template <typename GR, typename Map, typename Pred>
4077  int mapCountIf(const GR& gr, const Map& map, const Pred& pred) {
4078    typedef typename Map::Key Item;
4079    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
4080
4081    int cnt = 0;
4082    for (ItemIt it(gr); it != INVALID; ++it) {
4083      if (pred(map[it])) ++cnt;
4084    }
4085    return cnt;
4086  }
4087
4088  /// \brief Fill a graph map with a certain value.
4089  ///
4090  /// This function sets the specified value for all items (\c Node,
4091  /// \c Arc or \c Edge) in the given graph map.
4092  ///
4093  /// \param gr The graph for which the map is defined.
4094  /// \param map The graph map. It must conform to the
4095  /// \ref concepts::WriteMap "WriteMap" concept.
4096  /// \param val The value.
4097  template <typename GR, typename Map>
4098  void mapFill(const GR& gr, Map& map, const typename Map::Value& val) {
4099    typedef typename Map::Key Item;
4100    typedef typename ItemSetTraits<GR, Item>::ItemIt ItemIt;
4101
4102    for (ItemIt it(gr); it != INVALID; ++it) {
4103      map.set(it, val);
4104    }
4105  }
4106
4107  /// @}
4108}
4109
4110#endif // LEMON_MAPS_H
Note: See TracBrowser for help on using the repository browser.