COIN-OR::LEMON - Graph Library

source: lemon/lemon/maps.h @ 740:7bda7860e0a8

Last change on this file since 740:7bda7860e0a8 was 740:7bda7860e0a8, checked in by Balazs Dezso <deba@…>, 10 years ago

Port iterable maps from SVN 3509 (#73)

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