COIN-OR::LEMON - Graph Library

source: lemon-1.0/lemon/maps.h @ 217:b67149f0e675

Last change on this file since 217:b67149f0e675 was 209:765619b7cbb2, checked in by Alpar Juttner <alpar@…>, 11 years ago

Apply unify-sources.sh to the source tree

File size: 52.0 KB
RevLine 
[209]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
[25]2 *
[209]3 * This file is a part of LEMON, a generic C++ optimization library.
[25]4 *
[39]5 * Copyright (C) 2003-2008
[25]6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_MAPS_H
20#define LEMON_MAPS_H
21
22#include <iterator>
23#include <functional>
24#include <vector>
25
26#include <lemon/bits/utility.h>
[80]27#include <lemon/bits/traits.h>
[25]28
29///\file
30///\ingroup maps
31///\brief Miscellaneous property maps
[80]32
[25]33#include <map>
34
35namespace lemon {
36
37  /// \addtogroup maps
38  /// @{
39
40  /// Base class of maps.
41
[80]42  /// Base class of maps. It provides the necessary type definitions
43  /// required by the map %concepts.
44  template<typename K, typename V>
[25]45  class MapBase {
46  public:
[80]47    /// \biref The key type of the map.
[25]48    typedef K Key;
[80]49    /// \brief The value type of the map.
50    /// (The type of objects associated with the keys).
51    typedef V Value;
[25]52  };
53
[80]54
[25]55  /// Null map. (a.k.a. DoNothingMap)
56
[29]57  /// This map can be used if you have to provide a map only for
[80]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
[29]60  /// <tt>/dev/null</tt>).
[80]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> {
[25]66  public:
[80]67    typedef MapBase<K, V> Parent;
[25]68    typedef typename Parent::Key Key;
69    typedef typename Parent::Value Value;
[80]70
[25]71    /// Gives back a default constructed element.
[80]72    Value operator[](const Key&) const { return Value(); }
[25]73    /// Absorbs the value.
[80]74    void set(const Key&, const Value&) {}
[25]75  };
76
[80]77  /// Returns a \ref NullMap class
[29]78
[80]79  /// This function just returns a \ref NullMap class.
80  /// \relates NullMap
81  template <typename K, typename V>
[25]82  NullMap<K, V> nullMap() {
83    return NullMap<K, V>();
84  }
85
86
87  /// Constant map.
88
[82]89  /// This \ref concepts::ReadMap "readable map" assigns a specified
90  /// value to each key.
[80]91  ///
92  /// In other aspects it is equivalent to \ref NullMap.
93  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
94  /// concept, but it absorbs the data written to it.
95  ///
96  /// The simplest way of using this map is through the constMap()
97  /// function.
98  ///
99  /// \sa NullMap
100  /// \sa IdentityMap
101  template<typename K, typename V>
102  class ConstMap : public MapBase<K, V> {
[25]103  private:
[80]104    V _value;
[25]105  public:
[80]106    typedef MapBase<K, V> Parent;
[25]107    typedef typename Parent::Key Key;
108    typedef typename Parent::Value Value;
109
110    /// Default constructor
111
[29]112    /// Default constructor.
[80]113    /// The value of the map will be default constructed.
[25]114    ConstMap() {}
[80]115
[29]116    /// Constructor with specified initial value
[25]117
[29]118    /// Constructor with specified initial value.
[123]119    /// \param v The initial value of the map.
[80]120    ConstMap(const Value &v) : _value(v) {}
[25]121
[80]122    /// Gives back the specified value.
123    Value operator[](const Key&) const { return _value; }
[25]124
[80]125    /// Absorbs the value.
126    void set(const Key&, const Value&) {}
127
128    /// Sets the value that is assigned to each key.
129    void setAll(const Value &v) {
130      _value = v;
131    }
132
133    template<typename V1>
134    ConstMap(const ConstMap<K, V1> &, const Value &v) : _value(v) {}
[25]135  };
136
[80]137  /// Returns a \ref ConstMap class
[25]138
[80]139  /// This function just returns a \ref ConstMap class.
140  /// \relates ConstMap
141  template<typename K, typename V>
[25]142  inline ConstMap<K, V> constMap(const V &v) {
143    return ConstMap<K, V>(v);
144  }
145
[123]146  template<typename K, typename V>
147  inline ConstMap<K, V> constMap() {
148    return ConstMap<K, V>();
149  }
150
[25]151
152  template<typename T, T v>
[80]153  struct Const {};
[25]154
155  /// Constant map with inlined constant value.
156
[82]157  /// This \ref concepts::ReadMap "readable map" assigns a specified
158  /// value to each key.
[80]159  ///
160  /// In other aspects it is equivalent to \ref NullMap.
161  /// So it conforms the \ref concepts::ReadWriteMap "ReadWriteMap"
162  /// concept, but it absorbs the data written to it.
163  ///
164  /// The simplest way of using this map is through the constMap()
165  /// function.
166  ///
167  /// \sa NullMap
168  /// \sa IdentityMap
[25]169  template<typename K, typename V, V v>
170  class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
171  public:
172    typedef MapBase<K, V> Parent;
173    typedef typename Parent::Key Key;
174    typedef typename Parent::Value Value;
175
[80]176    /// Constructor.
177    ConstMap() {}
178
179    /// Gives back the specified value.
180    Value operator[](const Key&) const { return v; }
181
182    /// Absorbs the value.
183    void set(const Key&, const Value&) {}
[25]184  };
185
[80]186  /// Returns a \ref ConstMap class with inlined constant value
[25]187
[80]188  /// This function just returns a \ref ConstMap class with inlined
189  /// constant value.
190  /// \relates ConstMap
191  template<typename K, typename V, V v>
[25]192  inline ConstMap<K, Const<V, v> > constMap() {
193    return ConstMap<K, Const<V, v> >();
194  }
195
196
[82]197  /// Identity map.
198
199  /// This \ref concepts::ReadMap "read-only map" gives back the given
200  /// key as value without any modification.
[80]201  ///
202  /// \sa ConstMap
203  template <typename T>
204  class IdentityMap : public MapBase<T, T> {
205  public:
206    typedef MapBase<T, T> Parent;
207    typedef typename Parent::Key Key;
208    typedef typename Parent::Value Value;
209
210    /// Gives back the given value without any modification.
[82]211    Value operator[](const Key &k) const {
212      return k;
[80]213    }
214  };
215
216  /// Returns an \ref IdentityMap class
217
218  /// This function just returns an \ref IdentityMap class.
219  /// \relates IdentityMap
220  template<typename T>
221  inline IdentityMap<T> identityMap() {
222    return IdentityMap<T>();
223  }
224
225
226  /// \brief Map for storing values for integer keys from the range
227  /// <tt>[0..size-1]</tt>.
228  ///
229  /// This map is essentially a wrapper for \c std::vector. It assigns
230  /// values to integer keys from the range <tt>[0..size-1]</tt>.
231  /// It can be used with some data structures, for example
232  /// \ref UnionFind, \ref BinHeap, when the used items are small
233  /// integers. This map conforms the \ref concepts::ReferenceMap
234  /// "ReferenceMap" concept.
235  ///
236  /// The simplest way of using this map is through the rangeMap()
237  /// function.
238  template <typename V>
239  class RangeMap : public MapBase<int, V> {
240    template <typename V1>
241    friend class RangeMap;
242  private:
243
244    typedef std::vector<V> Vector;
245    Vector _vector;
246
[25]247  public:
248
[80]249    typedef MapBase<int, V> Parent;
250    /// Key type
[45]251    typedef typename Parent::Key Key;
[80]252    /// Value type
[45]253    typedef typename Parent::Value Value;
[80]254    /// Reference type
255    typedef typename Vector::reference Reference;
256    /// Const reference type
257    typedef typename Vector::const_reference ConstReference;
258
259    typedef True ReferenceMapTag;
260
261  public:
262
263    /// Constructor with specified default value.
264    RangeMap(int size = 0, const Value &value = Value())
265      : _vector(size, value) {}
266
267    /// Constructs the map from an appropriate \c std::vector.
268    template <typename V1>
269    RangeMap(const std::vector<V1>& vector)
270      : _vector(vector.begin(), vector.end()) {}
271
272    /// Constructs the map from another \ref RangeMap.
273    template <typename V1>
274    RangeMap(const RangeMap<V1> &c)
275      : _vector(c._vector.begin(), c._vector.end()) {}
276
277    /// Returns the size of the map.
278    int size() {
279      return _vector.size();
280    }
281
282    /// Resizes the map.
283
284    /// Resizes the underlying \c std::vector container, so changes the
285    /// keyset of the map.
286    /// \param size The new size of the map. The new keyset will be the
287    /// range <tt>[0..size-1]</tt>.
288    /// \param value The default value to assign to the new keys.
289    void resize(int size, const Value &value = Value()) {
290      _vector.resize(size, value);
291    }
292
293  private:
294
295    RangeMap& operator=(const RangeMap&);
296
297  public:
298
299    ///\e
300    Reference operator[](const Key &k) {
301      return _vector[k];
302    }
303
304    ///\e
305    ConstReference operator[](const Key &k) const {
306      return _vector[k];
307    }
308
309    ///\e
310    void set(const Key &k, const Value &v) {
311      _vector[k] = v;
312    }
313  };
314
315  /// Returns a \ref RangeMap class
316
317  /// This function just returns a \ref RangeMap class.
318  /// \relates RangeMap
319  template<typename V>
320  inline RangeMap<V> rangeMap(int size = 0, const V &value = V()) {
321    return RangeMap<V>(size, value);
322  }
323
324  /// \brief Returns a \ref RangeMap class created from an appropriate
325  /// \c std::vector
326
327  /// This function just returns a \ref RangeMap class created from an
328  /// appropriate \c std::vector.
329  /// \relates RangeMap
330  template<typename V>
331  inline RangeMap<V> rangeMap(const std::vector<V> &vector) {
332    return RangeMap<V>(vector);
333  }
334
335
336  /// Map type based on \c std::map
337
338  /// This map is essentially a wrapper for \c std::map with addition
339  /// that you can specify a default value for the keys that are not
340  /// stored actually. This value can be different from the default
341  /// contructed value (i.e. \c %Value()).
342  /// This type conforms the \ref concepts::ReferenceMap "ReferenceMap"
343  /// concept.
344  ///
345  /// This map is useful if a default value should be assigned to most of
346  /// the keys and different values should be assigned only to a few
347  /// keys (i.e. the map is "sparse").
348  /// The name of this type also refers to this important usage.
349  ///
350  /// Apart form that this map can be used in many other cases since it
351  /// is based on \c std::map, which is a general associative container.
352  /// However keep in mind that it is usually not as efficient as other
353  /// maps.
354  ///
355  /// The simplest way of using this map is through the sparseMap()
356  /// function.
357  template <typename K, typename V, typename Compare = std::less<K> >
358  class SparseMap : public MapBase<K, V> {
359    template <typename K1, typename V1, typename C1>
360    friend class SparseMap;
361  public:
362
363    typedef MapBase<K, V> Parent;
364    /// Key type
365    typedef typename Parent::Key Key;
366    /// Value type
367    typedef typename Parent::Value Value;
368    /// Reference type
369    typedef Value& Reference;
370    /// Const reference type
371    typedef const Value& ConstReference;
[25]372
[45]373    typedef True ReferenceMapTag;
374
[25]375  private:
[80]376
377    typedef std::map<K, V, Compare> Map;
378    Map _map;
[25]379    Value _value;
380
381  public:
382
[80]383    /// \brief Constructor with specified default value.
384    SparseMap(const Value &value = Value()) : _value(value) {}
385    /// \brief Constructs the map from an appropriate \c std::map, and
[47]386    /// explicitly specifies a default value.
[80]387    template <typename V1, typename Comp1>
388    SparseMap(const std::map<Key, V1, Comp1> &map,
389              const Value &value = Value())
[25]390      : _map(map.begin(), map.end()), _value(value) {}
[80]391
392    /// \brief Constructs the map from another \ref SparseMap.
393    template<typename V1, typename Comp1>
394    SparseMap(const SparseMap<Key, V1, Comp1> &c)
[25]395      : _map(c._map.begin(), c._map.end()), _value(c._value) {}
396
397  private:
398
[80]399    SparseMap& operator=(const SparseMap&);
[25]400
401  public:
402
403    ///\e
404    Reference operator[](const Key &k) {
405      typename Map::iterator it = _map.lower_bound(k);
406      if (it != _map.end() && !_map.key_comp()(k, it->first))
[209]407        return it->second;
[25]408      else
[209]409        return _map.insert(it, std::make_pair(k, _value))->second;
[25]410    }
411
[80]412    ///\e
[25]413    ConstReference operator[](const Key &k) const {
414      typename Map::const_iterator it = _map.find(k);
415      if (it != _map.end())
[209]416        return it->second;
[25]417      else
[209]418        return _value;
[25]419    }
420
[80]421    ///\e
422    void set(const Key &k, const Value &v) {
[25]423      typename Map::iterator it = _map.lower_bound(k);
424      if (it != _map.end() && !_map.key_comp()(k, it->first))
[209]425        it->second = v;
[25]426      else
[209]427        _map.insert(it, std::make_pair(k, v));
[25]428    }
429
[80]430    ///\e
431    void setAll(const Value &v) {
432      _value = v;
[25]433      _map.clear();
[80]434    }
435  };
[25]436
[80]437  /// Returns a \ref SparseMap class
[45]438
[80]439  /// This function just returns a \ref SparseMap class with specified
440  /// default value.
441  /// \relates SparseMap
442  template<typename K, typename V, typename Compare>
443  inline SparseMap<K, V, Compare> sparseMap(const V& value = V()) {
444    return SparseMap<K, V, Compare>(value);
[54]445  }
[45]446
[80]447  template<typename K, typename V>
448  inline SparseMap<K, V, std::less<K> > sparseMap(const V& value = V()) {
449    return SparseMap<K, V, std::less<K> >(value);
[45]450  }
[25]451
[80]452  /// \brief Returns a \ref SparseMap class created from an appropriate
453  /// \c std::map
[25]454
[80]455  /// This function just returns a \ref SparseMap class created from an
456  /// appropriate \c std::map.
457  /// \relates SparseMap
458  template<typename K, typename V, typename Compare>
459  inline SparseMap<K, V, Compare>
460    sparseMap(const std::map<K, V, Compare> &map, const V& value = V())
461  {
462    return SparseMap<K, V, Compare>(map, value);
[45]463  }
[25]464
465  /// @}
466
467  /// \addtogroup map_adaptors
468  /// @{
469
[80]470  /// Composition of two maps
471
[82]472  /// This \ref concepts::ReadMap "read-only map" returns the
[80]473  /// composition of two given maps. That is to say, if \c m1 is of
474  /// type \c M1 and \c m2 is of \c M2, then for
475  /// \code
476  ///   ComposeMap<M1, M2> cm(m1,m2);
477  /// \endcode
478  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>.
[25]479  ///
[80]480  /// The \c Key type of the map is inherited from \c M2 and the
481  /// \c Value type is from \c M1.
482  /// \c M2::Value must be convertible to \c M1::Key.
483  ///
484  /// The simplest way of using this map is through the composeMap()
485  /// function.
486  ///
487  /// \sa CombineMap
488  ///
489  /// \todo Check the requirements.
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;
[25]494  public:
[80]495    typedef MapBase<typename M2::Key, typename M1::Value> Parent;
[25]496    typedef typename Parent::Key Key;
497    typedef typename Parent::Value Value;
498
[80]499    /// Constructor
500    ComposeMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
501
[25]502    /// \e
[80]503    typename MapTraits<M1>::ConstReturnValue
504    operator[](const Key &k) const { return _m1[_m2[k]]; }
[25]505  };
506
[80]507  /// Returns a \ref ComposeMap class
[25]508
[80]509  /// This function just returns a \ref ComposeMap class.
510  ///
511  /// If \c m1 and \c m2 are maps and the \c Value type of \c m2 is
512  /// convertible to the \c Key of \c m1, then <tt>composeMap(m1,m2)[x]</tt>
513  /// will be equal to <tt>m1[m2[x]]</tt>.
514  ///
515  /// \relates ComposeMap
516  template <typename M1, typename M2>
517  inline ComposeMap<M1, M2> composeMap(const M1 &m1, const M2 &m2) {
518    return ComposeMap<M1, M2>(m1, m2);
[25]519  }
520
[80]521
522  /// Combination of two maps using an STL (binary) functor.
523
[82]524  /// This \ref concepts::ReadMap "read-only map" takes two maps and a
[80]525  /// binary functor and returns the combination of the two given maps
526  /// using the functor.
527  /// That is to say, if \c m1 is of type \c M1 and \c m2 is of \c M2
528  /// and \c f is of \c F, then for
529  /// \code
530  ///   CombineMap<M1,M2,F,V> cm(m1,m2,f);
531  /// \endcode
532  /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>.
[26]533  ///
[80]534  /// The \c Key type of the map is inherited from \c M1 (\c M1::Key
535  /// must be convertible to \c M2::Key) and the \c Value type is \c V.
536  /// \c M2::Value and \c M1::Value must be convertible to the
537  /// corresponding input parameter of \c F and the return type of \c F
538  /// must be convertible to \c V.
539  ///
540  /// The simplest way of using this map is through the combineMap()
541  /// function.
542  ///
543  /// \sa ComposeMap
544  ///
545  /// \todo Check the requirements.
546  template<typename M1, typename M2, typename F,
[209]547           typename V = typename F::result_type>
[80]548  class CombineMap : public MapBase<typename M1::Key, V> {
549    const M1 &_m1;
550    const M2 &_m2;
551    F _f;
[25]552  public:
[80]553    typedef MapBase<typename M1::Key, V> Parent;
[25]554    typedef typename Parent::Key Key;
555    typedef typename Parent::Value Value;
556
[80]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  };
[25]563
[80]564  /// Returns a \ref CombineMap class
[25]565
[80]566  /// This function just returns a \ref 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);
[25]586  }
587
[80]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  }
[25]593
[80]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
[82]603  /// This \ref concepts::ReadMap "read-only map" returns the value
[80]604  /// of a given functor. Actually, it just wraps the functor and
605  /// provides the \c Key and \c Value typedefs.
[26]606  ///
[80]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.
[29]612  ///
[80]613  /// The simplest way of using this map is through the functorToMap()
614  /// function.
615  ///
616  /// \sa MapToFunctor
617  template<typename F,
[209]618           typename K = typename F::argument_type,
619           typename V = typename F::result_type>
[80]620  class FunctorToMap : public MapBase<K, V> {
[123]621    F _f;
[80]622  public:
623    typedef MapBase<K, V> Parent;
624    typedef typename Parent::Key Key;
625    typedef typename Parent::Value Value;
[25]626
[80]627    /// Constructor
628    FunctorToMap(const F &f = F()) : _f(f) {}
629    /// \e
630    Value operator[](const Key &k) const { return _f(k); }
631  };
632
633  /// Returns a \ref FunctorToMap class
634
635  /// This function just returns a \ref FunctorToMap class.
636  ///
637  /// This function is specialized for adaptable binary function
638  /// classes and C++ functions.
639  ///
640  /// \relates FunctorToMap
641  template<typename K, typename V, typename F>
642  inline FunctorToMap<F, K, V> functorToMap(const F &f) {
643    return FunctorToMap<F, K, V>(f);
644  }
645
646  template <typename F>
647  inline FunctorToMap<F, typename F::argument_type, typename F::result_type>
648    functorToMap(const F &f)
649  {
650    return FunctorToMap<F, typename F::argument_type,
651      typename F::result_type>(f);
652  }
653
654  template <typename K, typename V>
655  inline FunctorToMap<V (*)(K), K, V> functorToMap(V (*f)(K)) {
656    return FunctorToMap<V (*)(K), K, V>(f);
657  }
658
659
660  /// Converts a map to an STL style (unary) functor
661
662  /// This class converts a map to an STL style (unary) functor.
663  /// That is it provides an <tt>operator()</tt> to read its values.
664  ///
665  /// For the sake of convenience it also works as a usual
666  /// \ref concepts::ReadMap "readable map", i.e. <tt>operator[]</tt>
667  /// and the \c Key and \c Value typedefs also exist.
668  ///
669  /// The simplest way of using this map is through the mapToFunctor()
670  /// function.
671  ///
672  ///\sa FunctorToMap
673  template <typename M>
674  class MapToFunctor : public MapBase<typename M::Key, typename M::Value> {
675    const M &_m;
[25]676  public:
677    typedef MapBase<typename M::Key, typename M::Value> Parent;
678    typedef typename Parent::Key Key;
679    typedef typename Parent::Value Value;
680
[80]681    typedef typename Parent::Key argument_type;
682    typedef typename Parent::Value result_type;
683
684    /// Constructor
685    MapToFunctor(const M &m) : _m(m) {}
686    /// \e
687    Value operator()(const Key &k) const { return _m[k]; }
688    /// \e
689    Value operator[](const Key &k) const { return _m[k]; }
[25]690  };
[45]691
[80]692  /// Returns a \ref MapToFunctor class
693
694  /// This function just returns a \ref MapToFunctor class.
695  /// \relates MapToFunctor
[45]696  template<typename M>
[80]697  inline MapToFunctor<M> mapToFunctor(const M &m) {
698    return MapToFunctor<M>(m);
[45]699  }
[25]700
701
[80]702  /// \brief Map adaptor to convert the \c Value type of a map to
703  /// another type using the default conversion.
704
705  /// Map adaptor to convert the \c Value type of a \ref concepts::ReadMap
706  /// "readable map" to another type using the default conversion.
707  /// The \c Key type of it is inherited from \c M and the \c Value
708  /// type is \c V.
709  /// This type conforms the \ref concepts::ReadMap "ReadMap" concept.
[26]710  ///
[80]711  /// The simplest way of using this map is through the convertMap()
712  /// function.
713  template <typename M, typename V>
714  class ConvertMap : public MapBase<typename M::Key, V> {
715    const M &_m;
716  public:
717    typedef MapBase<typename M::Key, V> Parent;
718    typedef typename Parent::Key Key;
719    typedef typename Parent::Value Value;
720
721    /// Constructor
722
723    /// Constructor.
724    /// \param m The underlying map.
725    ConvertMap(const M &m) : _m(m) {}
726
727    /// \e
728    Value operator[](const Key &k) const { return _m[k]; }
729  };
730
731  /// Returns a \ref ConvertMap class
732
733  /// This function just returns a \ref ConvertMap class.
734  /// \relates ConvertMap
735  template<typename V, typename M>
736  inline ConvertMap<M, V> convertMap(const M &map) {
737    return ConvertMap<M, V>(map);
738  }
739
740
741  /// Applies all map setting operations to two maps
742
743  /// This map has two \ref concepts::WriteMap "writable map" parameters
744  /// and each write request will be passed to both of them.
745  /// If \c M1 is also \ref concepts::ReadMap "readable", then the read
746  /// operations will return the corresponding values of \c M1.
[29]747  ///
[80]748  /// The \c Key and \c Value types are inherited from \c M1.
749  /// The \c Key and \c Value of \c M2 must be convertible from those
750  /// of \c M1.
751  ///
752  /// The simplest way of using this map is through the forkMap()
753  /// function.
754  template<typename  M1, typename M2>
755  class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
756    M1 &_m1;
757    M2 &_m2;
758  public:
759    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
760    typedef typename Parent::Key Key;
761    typedef typename Parent::Value Value;
[25]762
[80]763    /// Constructor
764    ForkMap(M1 &m1, M2 &m2) : _m1(m1), _m2(m2) {}
765    /// Returns the value associated with the given key in the first map.
766    Value operator[](const Key &k) const { return _m1[k]; }
767    /// Sets the value associated with the given key in both maps.
768    void set(const Key &k, const Value &v) { _m1.set(k,v); _m2.set(k,v); }
769  };
770
771  /// Returns a \ref ForkMap class
772
773  /// This function just returns a \ref ForkMap class.
774  /// \relates ForkMap
775  template <typename M1, typename M2>
776  inline ForkMap<M1,M2> forkMap(M1 &m1, M2 &m2) {
777    return ForkMap<M1,M2>(m1,m2);
778  }
779
780
781  /// Sum of two maps
782
[82]783  /// This \ref concepts::ReadMap "read-only map" returns the sum
[80]784  /// of the values of the two given maps.
785  /// Its \c Key and \c Value types are inherited from \c M1.
786  /// The \c Key and \c Value of \c M2 must be convertible to those of
787  /// \c M1.
788  ///
789  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
790  /// \code
791  ///   AddMap<M1,M2> am(m1,m2);
792  /// \endcode
793  /// <tt>am[x]</tt> will be equal to <tt>m1[x]+m2[x]</tt>.
794  ///
795  /// The simplest way of using this map is through the addMap()
796  /// function.
797  ///
798  /// \sa SubMap, MulMap, DivMap
799  /// \sa ShiftMap, ShiftWriteMap
800  template<typename M1, typename M2>
[25]801  class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
[80]802    const M1 &_m1;
803    const M2 &_m2;
[25]804  public:
805    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
806    typedef typename Parent::Key Key;
807    typedef typename Parent::Value Value;
808
[80]809    /// Constructor
810    AddMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
811    /// \e
812    Value operator[](const Key &k) const { return _m1[k]+_m2[k]; }
[25]813  };
814
[80]815  /// Returns an \ref AddMap class
816
817  /// This function just returns an \ref AddMap class.
[25]818  ///
[80]819  /// For example, if \c m1 and \c m2 are both maps with \c double
820  /// values, then <tt>addMap(m1,m2)[x]</tt> will be equal to
821  /// <tt>m1[x]+m2[x]</tt>.
822  ///
823  /// \relates AddMap
824  template<typename M1, typename M2>
825  inline AddMap<M1, M2> addMap(const M1 &m1, const M2 &m2) {
[25]826    return AddMap<M1, M2>(m1,m2);
827  }
828
829
[80]830  /// Difference of two maps
831
[82]832  /// This \ref concepts::ReadMap "read-only map" returns the difference
[80]833  /// of the values of the two given maps.
834  /// Its \c Key and \c Value types are inherited from \c M1.
835  /// The \c Key and \c Value of \c M2 must be convertible to those of
836  /// \c M1.
[25]837  ///
[80]838  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
839  /// \code
840  ///   SubMap<M1,M2> sm(m1,m2);
841  /// \endcode
842  /// <tt>sm[x]</tt> will be equal to <tt>m1[x]-m2[x]</tt>.
[29]843  ///
[80]844  /// The simplest way of using this map is through the subMap()
845  /// function.
846  ///
847  /// \sa AddMap, MulMap, DivMap
848  template<typename M1, typename M2>
849  class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
850    const M1 &_m1;
851    const M2 &_m2;
852  public:
853    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
854    typedef typename Parent::Key Key;
855    typedef typename Parent::Value Value;
856
857    /// Constructor
858    SubMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
859    /// \e
860    Value operator[](const Key &k) const { return _m1[k]-_m2[k]; }
861  };
862
863  /// Returns a \ref SubMap class
864
865  /// This function just returns a \ref SubMap class.
866  ///
867  /// For example, if \c m1 and \c m2 are both maps with \c double
868  /// values, then <tt>subMap(m1,m2)[x]</tt> will be equal to
869  /// <tt>m1[x]-m2[x]</tt>.
870  ///
871  /// \relates SubMap
872  template<typename M1, typename M2>
873  inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
874    return SubMap<M1, M2>(m1,m2);
875  }
876
877
878  /// Product of two maps
879
[82]880  /// This \ref concepts::ReadMap "read-only map" returns the product
[80]881  /// of the values of the two given maps.
882  /// Its \c Key and \c Value types are inherited from \c M1.
883  /// The \c Key and \c Value of \c M2 must be convertible to those of
884  /// \c M1.
885  ///
886  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
887  /// \code
888  ///   MulMap<M1,M2> mm(m1,m2);
889  /// \endcode
890  /// <tt>mm[x]</tt> will be equal to <tt>m1[x]*m2[x]</tt>.
891  ///
892  /// The simplest way of using this map is through the mulMap()
893  /// function.
894  ///
895  /// \sa AddMap, SubMap, DivMap
896  /// \sa ScaleMap, ScaleWriteMap
897  template<typename M1, typename M2>
898  class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
899    const M1 &_m1;
900    const M2 &_m2;
901  public:
902    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
903    typedef typename Parent::Key Key;
904    typedef typename Parent::Value Value;
905
906    /// Constructor
907    MulMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
908    /// \e
909    Value operator[](const Key &k) const { return _m1[k]*_m2[k]; }
910  };
911
912  /// Returns a \ref MulMap class
913
914  /// This function just returns a \ref MulMap class.
915  ///
916  /// For example, if \c m1 and \c m2 are both maps with \c double
917  /// values, then <tt>mulMap(m1,m2)[x]</tt> will be equal to
918  /// <tt>m1[x]*m2[x]</tt>.
919  ///
920  /// \relates MulMap
921  template<typename M1, typename M2>
922  inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
923    return MulMap<M1, M2>(m1,m2);
924  }
925
926
927  /// Quotient of two maps
928
[82]929  /// This \ref concepts::ReadMap "read-only map" returns the quotient
[80]930  /// of the values of the two given maps.
931  /// Its \c Key and \c Value types are inherited from \c M1.
932  /// The \c Key and \c Value of \c M2 must be convertible to those of
933  /// \c M1.
934  ///
935  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
936  /// \code
937  ///   DivMap<M1,M2> dm(m1,m2);
938  /// \endcode
939  /// <tt>dm[x]</tt> will be equal to <tt>m1[x]/m2[x]</tt>.
940  ///
941  /// The simplest way of using this map is through the divMap()
942  /// function.
943  ///
944  /// \sa AddMap, SubMap, MulMap
945  template<typename M1, typename M2>
946  class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
947    const M1 &_m1;
948    const M2 &_m2;
949  public:
950    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
951    typedef typename Parent::Key Key;
952    typedef typename Parent::Value Value;
953
954    /// Constructor
955    DivMap(const M1 &m1,const M2 &m2) : _m1(m1), _m2(m2) {}
956    /// \e
957    Value operator[](const Key &k) const { return _m1[k]/_m2[k]; }
958  };
959
960  /// Returns a \ref DivMap class
961
962  /// This function just returns a \ref DivMap class.
963  ///
964  /// For example, if \c m1 and \c m2 are both maps with \c double
965  /// values, then <tt>divMap(m1,m2)[x]</tt> will be equal to
966  /// <tt>m1[x]/m2[x]</tt>.
967  ///
968  /// \relates DivMap
969  template<typename M1, typename M2>
970  inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
971    return DivMap<M1, M2>(m1,m2);
972  }
973
974
975  /// Shifts a map with a constant.
976
[82]977  /// This \ref concepts::ReadMap "read-only map" returns the sum of
[80]978  /// the given map and a constant value (i.e. it shifts the map with
979  /// the constant). Its \c Key and \c Value are inherited from \c M.
980  ///
981  /// Actually,
982  /// \code
983  ///   ShiftMap<M> sh(m,v);
984  /// \endcode
985  /// is equivalent to
986  /// \code
987  ///   ConstMap<M::Key, M::Value> cm(v);
988  ///   AddMap<M, ConstMap<M::Key, M::Value> > sh(m,cm);
989  /// \endcode
990  ///
991  /// The simplest way of using this map is through the shiftMap()
992  /// function.
993  ///
994  /// \sa ShiftWriteMap
995  template<typename M, typename C = typename M::Value>
[25]996  class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
[80]997    const M &_m;
998    C _v;
[25]999  public:
1000    typedef MapBase<typename M::Key, typename M::Value> Parent;
1001    typedef typename Parent::Key Key;
1002    typedef typename Parent::Value Value;
1003
[80]1004    /// Constructor
[25]1005
[80]1006    /// Constructor.
1007    /// \param m The undelying map.
1008    /// \param v The constant value.
1009    ShiftMap(const M &m, const C &v) : _m(m), _v(v) {}
1010    /// \e
1011    Value operator[](const Key &k) const { return _m[k]+_v; }
[25]1012  };
1013
[80]1014  /// Shifts a map with a constant (read-write version).
[25]1015
[80]1016  /// This \ref concepts::ReadWriteMap "read-write map" returns the sum
1017  /// of the given map and a constant value (i.e. it shifts the map with
1018  /// the constant). Its \c Key and \c Value are inherited from \c M.
1019  /// It makes also possible to write the map.
[25]1020  ///
[80]1021  /// The simplest way of using this map is through the shiftWriteMap()
1022  /// function.
1023  ///
1024  /// \sa ShiftMap
1025  template<typename M, typename C = typename M::Value>
[25]1026  class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
[80]1027    M &_m;
1028    C _v;
[25]1029  public:
1030    typedef MapBase<typename M::Key, typename M::Value> Parent;
1031    typedef typename Parent::Key Key;
1032    typedef typename Parent::Value Value;
1033
[80]1034    /// Constructor
[25]1035
[80]1036    /// Constructor.
1037    /// \param m The undelying map.
1038    /// \param v The constant value.
1039    ShiftWriteMap(M &m, const C &v) : _m(m), _v(v) {}
[25]1040    /// \e
[80]1041    Value operator[](const Key &k) const { return _m[k]+_v; }
[25]1042    /// \e
[80]1043    void set(const Key &k, const Value &v) { _m.set(k, v-_v); }
[25]1044  };
1045
[80]1046  /// Returns a \ref ShiftMap class
1047
1048  /// This function just returns a \ref ShiftMap class.
1049  ///
1050  /// For example, if \c m is a map with \c double values and \c v is
1051  /// \c double, then <tt>shiftMap(m,v)[x]</tt> will be equal to
1052  /// <tt>m[x]+v</tt>.
1053  ///
1054  /// \relates ShiftMap
1055  template<typename M, typename C>
1056  inline ShiftMap<M, C> shiftMap(const M &m, const C &v) {
[25]1057    return ShiftMap<M, C>(m,v);
1058  }
1059
[80]1060  /// Returns a \ref ShiftWriteMap class
[29]1061
[80]1062  /// This function just returns a \ref ShiftWriteMap class.
1063  ///
1064  /// For example, if \c m is a map with \c double values and \c v is
1065  /// \c double, then <tt>shiftWriteMap(m,v)[x]</tt> will be equal to
1066  /// <tt>m[x]+v</tt>.
1067  /// Moreover it makes also possible to write the map.
1068  ///
1069  /// \relates ShiftWriteMap
1070  template<typename M, typename C>
1071  inline ShiftWriteMap<M, C> shiftWriteMap(M &m, const C &v) {
[25]1072    return ShiftWriteMap<M, C>(m,v);
1073  }
1074
1075
[80]1076  /// Scales a map with a constant.
1077
[82]1078  /// This \ref concepts::ReadMap "read-only map" returns the value of
[80]1079  /// the given map multiplied from the left side with a constant value.
1080  /// Its \c Key and \c Value are inherited from \c M.
[26]1081  ///
[80]1082  /// Actually,
1083  /// \code
1084  ///   ScaleMap<M> sc(m,v);
1085  /// \endcode
1086  /// is equivalent to
1087  /// \code
1088  ///   ConstMap<M::Key, M::Value> cm(v);
1089  ///   MulMap<ConstMap<M::Key, M::Value>, M> sc(cm,m);
1090  /// \endcode
[25]1091  ///
[80]1092  /// The simplest way of using this map is through the scaleMap()
1093  /// function.
[25]1094  ///
[80]1095  /// \sa ScaleWriteMap
1096  template<typename M, typename C = typename M::Value>
[25]1097  class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
[80]1098    const M &_m;
1099    C _v;
[25]1100  public:
1101    typedef MapBase<typename M::Key, typename M::Value> Parent;
1102    typedef typename Parent::Key Key;
1103    typedef typename Parent::Value Value;
1104
[80]1105    /// Constructor
[25]1106
[80]1107    /// Constructor.
1108    /// \param m The undelying map.
1109    /// \param v The constant value.
1110    ScaleMap(const M &m, const C &v) : _m(m), _v(v) {}
[25]1111    /// \e
[80]1112    Value operator[](const Key &k) const { return _v*_m[k]; }
[25]1113  };
1114
[80]1115  /// Scales a map with a constant (read-write version).
[25]1116
[80]1117  /// This \ref concepts::ReadWriteMap "read-write map" returns the value of
1118  /// the given map multiplied from the left side with a constant value.
1119  /// Its \c Key and \c Value are inherited from \c M.
1120  /// It can also be used as write map if the \c / operator is defined
1121  /// between \c Value and \c C and the given multiplier is not zero.
[29]1122  ///
[80]1123  /// The simplest way of using this map is through the scaleWriteMap()
1124  /// function.
1125  ///
1126  /// \sa ScaleMap
1127  template<typename M, typename C = typename M::Value>
[25]1128  class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
[80]1129    M &_m;
1130    C _v;
[25]1131  public:
1132    typedef MapBase<typename M::Key, typename M::Value> Parent;
1133    typedef typename Parent::Key Key;
1134    typedef typename Parent::Value Value;
1135
[80]1136    /// Constructor
[25]1137
[80]1138    /// Constructor.
1139    /// \param m The undelying map.
1140    /// \param v The constant value.
1141    ScaleWriteMap(M &m, const C &v) : _m(m), _v(v) {}
[25]1142    /// \e
[80]1143    Value operator[](const Key &k) const { return _v*_m[k]; }
[25]1144    /// \e
[80]1145    void set(const Key &k, const Value &v) { _m.set(k, v/_v); }
[25]1146  };
1147
[80]1148  /// Returns a \ref ScaleMap class
1149
1150  /// This function just returns a \ref ScaleMap class.
1151  ///
1152  /// For example, if \c m is a map with \c double values and \c v is
1153  /// \c double, then <tt>scaleMap(m,v)[x]</tt> will be equal to
1154  /// <tt>v*m[x]</tt>.
1155  ///
1156  /// \relates ScaleMap
1157  template<typename M, typename C>
1158  inline ScaleMap<M, C> scaleMap(const M &m, const C &v) {
[25]1159    return ScaleMap<M, C>(m,v);
1160  }
1161
[80]1162  /// Returns a \ref ScaleWriteMap class
[29]1163
[80]1164  /// This function just returns a \ref ScaleWriteMap class.
1165  ///
1166  /// For example, if \c m is a map with \c double values and \c v is
1167  /// \c double, then <tt>scaleWriteMap(m,v)[x]</tt> will be equal to
1168  /// <tt>v*m[x]</tt>.
1169  /// Moreover it makes also possible to write the map.
1170  ///
1171  /// \relates ScaleWriteMap
1172  template<typename M, typename C>
1173  inline ScaleWriteMap<M, C> scaleWriteMap(M &m, const C &v) {
[25]1174    return ScaleWriteMap<M, C>(m,v);
1175  }
1176
1177
[80]1178  /// Negative of a map
[25]1179
[82]1180  /// This \ref concepts::ReadMap "read-only map" returns the negative
[80]1181  /// of the values of the given map (using the unary \c - operator).
1182  /// Its \c Key and \c Value are inherited from \c M.
[25]1183  ///
[80]1184  /// If M::Value is \c int, \c double etc., then
1185  /// \code
1186  ///   NegMap<M> neg(m);
1187  /// \endcode
1188  /// is equivalent to
1189  /// \code
1190  ///   ScaleMap<M> neg(m,-1);
1191  /// \endcode
[29]1192  ///
[80]1193  /// The simplest way of using this map is through the negMap()
1194  /// function.
[29]1195  ///
[80]1196  /// \sa NegWriteMap
1197  template<typename M>
[25]1198  class NegMap : public MapBase<typename M::Key, typename M::Value> {
[80]1199    const M& _m;
[25]1200  public:
1201    typedef MapBase<typename M::Key, typename M::Value> Parent;
1202    typedef typename Parent::Key Key;
1203    typedef typename Parent::Value Value;
1204
[80]1205    /// Constructor
1206    NegMap(const M &m) : _m(m) {}
[25]1207    /// \e
[80]1208    Value operator[](const Key &k) const { return -_m[k]; }
[25]1209  };
1210
[80]1211  /// Negative of a map (read-write version)
1212
1213  /// This \ref concepts::ReadWriteMap "read-write map" returns the
1214  /// negative of the values of the given map (using the unary \c -
1215  /// operator).
1216  /// Its \c Key and \c Value are inherited from \c M.
1217  /// It makes also possible to write the map.
1218  ///
1219  /// If M::Value is \c int, \c double etc., then
1220  /// \code
1221  ///   NegWriteMap<M> neg(m);
1222  /// \endcode
1223  /// is equivalent to
1224  /// \code
1225  ///   ScaleWriteMap<M> neg(m,-1);
1226  /// \endcode
1227  ///
1228  /// The simplest way of using this map is through the negWriteMap()
1229  /// function.
[29]1230  ///
1231  /// \sa NegMap
[80]1232  template<typename M>
[25]1233  class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
[80]1234    M &_m;
[25]1235  public:
1236    typedef MapBase<typename M::Key, typename M::Value> Parent;
1237    typedef typename Parent::Key Key;
1238    typedef typename Parent::Value Value;
1239
[80]1240    /// Constructor
1241    NegWriteMap(M &m) : _m(m) {}
[25]1242    /// \e
[80]1243    Value operator[](const Key &k) const { return -_m[k]; }
[25]1244    /// \e
[80]1245    void set(const Key &k, const Value &v) { _m.set(k, -v); }
[25]1246  };
1247
[80]1248  /// Returns a \ref NegMap class
[25]1249
[80]1250  /// This function just returns a \ref NegMap class.
1251  ///
1252  /// For example, if \c m is a map with \c double values, then
1253  /// <tt>negMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
1254  ///
1255  /// \relates NegMap
1256  template <typename M>
[25]1257  inline NegMap<M> negMap(const M &m) {
1258    return NegMap<M>(m);
1259  }
1260
[80]1261  /// Returns a \ref NegWriteMap class
[29]1262
[80]1263  /// This function just returns a \ref NegWriteMap class.
1264  ///
1265  /// For example, if \c m is a map with \c double values, then
1266  /// <tt>negWriteMap(m)[x]</tt> will be equal to <tt>-m[x]</tt>.
1267  /// Moreover it makes also possible to write the map.
1268  ///
1269  /// \relates NegWriteMap
1270  template <typename M>
1271  inline NegWriteMap<M> negWriteMap(M &m) {
[25]1272    return NegWriteMap<M>(m);
1273  }
1274
1275
[80]1276  /// Absolute value of a map
1277
[82]1278  /// This \ref concepts::ReadMap "read-only map" returns the absolute
[80]1279  /// value of the values of the given map.
1280  /// Its \c Key and \c Value are inherited from \c M.
1281  /// \c Value must be comparable to \c 0 and the unary \c -
1282  /// operator must be defined for it, of course.
1283  ///
1284  /// The simplest way of using this map is through the absMap()
1285  /// function.
1286  template<typename M>
[25]1287  class AbsMap : public MapBase<typename M::Key, typename M::Value> {
[80]1288    const M &_m;
[25]1289  public:
1290    typedef MapBase<typename M::Key, typename M::Value> Parent;
1291    typedef typename Parent::Key Key;
1292    typedef typename Parent::Value Value;
1293
[80]1294    /// Constructor
1295    AbsMap(const M &m) : _m(m) {}
[25]1296    /// \e
[80]1297    Value operator[](const Key &k) const {
1298      Value tmp = _m[k];
[25]1299      return tmp >= 0 ? tmp : -tmp;
1300    }
1301
1302  };
1303
[80]1304  /// Returns an \ref AbsMap class
1305
1306  /// This function just returns an \ref AbsMap class.
1307  ///
1308  /// For example, if \c m is a map with \c double values, then
1309  /// <tt>absMap(m)[x]</tt> will be equal to <tt>m[x]</tt> if
1310  /// it is positive or zero and <tt>-m[x]</tt> if <tt>m[x]</tt> is
1311  /// negative.
1312  ///
1313  /// \relates AbsMap
1314  template<typename M>
[25]1315  inline AbsMap<M> absMap(const M &m) {
1316    return AbsMap<M>(m);
1317  }
1318
[82]1319  /// @}
[209]1320
[82]1321  // Logical maps and map adaptors:
1322
1323  /// \addtogroup maps
1324  /// @{
1325
1326  /// Constant \c true map.
1327
1328  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1329  /// each key.
1330  ///
1331  /// Note that
1332  /// \code
1333  ///   TrueMap<K> tm;
1334  /// \endcode
1335  /// is equivalent to
1336  /// \code
1337  ///   ConstMap<K,bool> tm(true);
1338  /// \endcode
1339  ///
1340  /// \sa FalseMap
1341  /// \sa ConstMap
1342  template <typename K>
1343  class TrueMap : public MapBase<K, bool> {
1344  public:
1345    typedef MapBase<K, bool> Parent;
1346    typedef typename Parent::Key Key;
1347    typedef typename Parent::Value Value;
1348
1349    /// Gives back \c true.
1350    Value operator[](const Key&) const { return true; }
1351  };
1352
1353  /// Returns a \ref TrueMap class
1354
1355  /// This function just returns a \ref TrueMap class.
1356  /// \relates TrueMap
1357  template<typename K>
1358  inline TrueMap<K> trueMap() {
1359    return TrueMap<K>();
1360  }
1361
1362
1363  /// Constant \c false map.
1364
1365  /// This \ref concepts::ReadMap "read-only map" assigns \c false to
1366  /// each key.
1367  ///
1368  /// Note that
1369  /// \code
1370  ///   FalseMap<K> fm;
1371  /// \endcode
1372  /// is equivalent to
1373  /// \code
1374  ///   ConstMap<K,bool> fm(false);
1375  /// \endcode
1376  ///
1377  /// \sa TrueMap
1378  /// \sa ConstMap
1379  template <typename K>
1380  class FalseMap : public MapBase<K, bool> {
1381  public:
1382    typedef MapBase<K, bool> Parent;
1383    typedef typename Parent::Key Key;
1384    typedef typename Parent::Value Value;
1385
1386    /// Gives back \c false.
1387    Value operator[](const Key&) const { return false; }
1388  };
1389
1390  /// Returns a \ref FalseMap class
1391
1392  /// This function just returns a \ref FalseMap class.
1393  /// \relates FalseMap
1394  template<typename K>
1395  inline FalseMap<K> falseMap() {
1396    return FalseMap<K>();
1397  }
1398
1399  /// @}
1400
1401  /// \addtogroup map_adaptors
1402  /// @{
1403
1404  /// Logical 'and' of two maps
1405
1406  /// This \ref concepts::ReadMap "read-only map" returns the logical
1407  /// 'and' of the values of the two given maps.
1408  /// Its \c Key type is inherited from \c M1 and its \c Value type is
1409  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1410  ///
1411  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1412  /// \code
1413  ///   AndMap<M1,M2> am(m1,m2);
1414  /// \endcode
1415  /// <tt>am[x]</tt> will be equal to <tt>m1[x]&&m2[x]</tt>.
1416  ///
1417  /// The simplest way of using this map is through the andMap()
1418  /// function.
1419  ///
1420  /// \sa OrMap
1421  /// \sa NotMap, NotWriteMap
1422  template<typename M1, typename M2>
1423  class AndMap : public MapBase<typename M1::Key, bool> {
1424    const M1 &_m1;
1425    const M2 &_m2;
1426  public:
1427    typedef MapBase<typename M1::Key, bool> Parent;
1428    typedef typename Parent::Key Key;
1429    typedef typename Parent::Value Value;
1430
1431    /// Constructor
1432    AndMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1433    /// \e
1434    Value operator[](const Key &k) const { return _m1[k]&&_m2[k]; }
1435  };
1436
1437  /// Returns an \ref AndMap class
1438
1439  /// This function just returns an \ref AndMap class.
1440  ///
1441  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
1442  /// then <tt>andMap(m1,m2)[x]</tt> will be equal to
1443  /// <tt>m1[x]&&m2[x]</tt>.
1444  ///
1445  /// \relates AndMap
1446  template<typename M1, typename M2>
1447  inline AndMap<M1, M2> andMap(const M1 &m1, const M2 &m2) {
1448    return AndMap<M1, M2>(m1,m2);
1449  }
1450
1451
1452  /// Logical 'or' of two maps
1453
1454  /// This \ref concepts::ReadMap "read-only map" returns the logical
1455  /// 'or' of the values of the two given maps.
1456  /// Its \c Key type is inherited from \c M1 and its \c Value type is
1457  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1458  ///
1459  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1460  /// \code
1461  ///   OrMap<M1,M2> om(m1,m2);
1462  /// \endcode
1463  /// <tt>om[x]</tt> will be equal to <tt>m1[x]||m2[x]</tt>.
1464  ///
1465  /// The simplest way of using this map is through the orMap()
1466  /// function.
1467  ///
1468  /// \sa AndMap
1469  /// \sa NotMap, NotWriteMap
1470  template<typename M1, typename M2>
1471  class OrMap : public MapBase<typename M1::Key, bool> {
1472    const M1 &_m1;
1473    const M2 &_m2;
1474  public:
1475    typedef MapBase<typename M1::Key, bool> Parent;
1476    typedef typename Parent::Key Key;
1477    typedef typename Parent::Value Value;
1478
1479    /// Constructor
1480    OrMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1481    /// \e
1482    Value operator[](const Key &k) const { return _m1[k]||_m2[k]; }
1483  };
1484
1485  /// Returns an \ref OrMap class
1486
1487  /// This function just returns an \ref OrMap class.
1488  ///
1489  /// For example, if \c m1 and \c m2 are both maps with \c bool values,
1490  /// then <tt>orMap(m1,m2)[x]</tt> will be equal to
1491  /// <tt>m1[x]||m2[x]</tt>.
1492  ///
1493  /// \relates OrMap
1494  template<typename M1, typename M2>
1495  inline OrMap<M1, M2> orMap(const M1 &m1, const M2 &m2) {
1496    return OrMap<M1, M2>(m1,m2);
1497  }
1498
[25]1499
[80]1500  /// Logical 'not' of a map
1501
[82]1502  /// This \ref concepts::ReadMap "read-only map" returns the logical
[80]1503  /// negation of the values of the given map.
1504  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
[25]1505  ///
[80]1506  /// The simplest way of using this map is through the notMap()
1507  /// function.
[25]1508  ///
[80]1509  /// \sa NotWriteMap
1510  template <typename M>
[25]1511  class NotMap : public MapBase<typename M::Key, bool> {
[80]1512    const M &_m;
[25]1513  public:
1514    typedef MapBase<typename M::Key, bool> Parent;
1515    typedef typename Parent::Key Key;
1516    typedef typename Parent::Value Value;
1517
1518    /// Constructor
[80]1519    NotMap(const M &m) : _m(m) {}
1520    /// \e
1521    Value operator[](const Key &k) const { return !_m[k]; }
[25]1522  };
1523
[80]1524  /// Logical 'not' of a map (read-write version)
1525
1526  /// This \ref concepts::ReadWriteMap "read-write map" returns the
1527  /// logical negation of the values of the given map.
1528  /// Its \c Key is inherited from \c M and its \c Value is \c bool.
1529  /// It makes also possible to write the map. When a value is set,
1530  /// the opposite value is set to the original map.
[29]1531  ///
[80]1532  /// The simplest way of using this map is through the notWriteMap()
1533  /// function.
1534  ///
1535  /// \sa NotMap
1536  template <typename M>
[25]1537  class NotWriteMap : public MapBase<typename M::Key, bool> {
[80]1538    M &_m;
[25]1539  public:
1540    typedef MapBase<typename M::Key, bool> Parent;
1541    typedef typename Parent::Key Key;
1542    typedef typename Parent::Value Value;
1543
1544    /// Constructor
[80]1545    NotWriteMap(M &m) : _m(m) {}
1546    /// \e
1547    Value operator[](const Key &k) const { return !_m[k]; }
1548    /// \e
1549    void set(const Key &k, bool v) { _m.set(k, !v); }
[25]1550  };
[80]1551
1552  /// Returns a \ref NotMap class
1553
1554  /// This function just returns a \ref NotMap class.
1555  ///
1556  /// For example, if \c m is a map with \c bool values, then
1557  /// <tt>notMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
1558  ///
1559  /// \relates NotMap
1560  template <typename M>
[25]1561  inline NotMap<M> notMap(const M &m) {
1562    return NotMap<M>(m);
1563  }
[80]1564
1565  /// Returns a \ref NotWriteMap class
1566
1567  /// This function just returns a \ref NotWriteMap class.
1568  ///
1569  /// For example, if \c m is a map with \c bool values, then
1570  /// <tt>notWriteMap(m)[x]</tt> will be equal to <tt>!m[x]</tt>.
1571  /// Moreover it makes also possible to write the map.
1572  ///
1573  /// \relates NotWriteMap
1574  template <typename M>
1575  inline NotWriteMap<M> notWriteMap(M &m) {
[25]1576    return NotWriteMap<M>(m);
1577  }
1578
[82]1579
1580  /// Combination of two maps using the \c == operator
1581
1582  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1583  /// the keys for which the corresponding values of the two maps are
1584  /// equal.
1585  /// Its \c Key type is inherited from \c M1 and its \c Value type is
1586  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1587  ///
1588  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1589  /// \code
1590  ///   EqualMap<M1,M2> em(m1,m2);
1591  /// \endcode
1592  /// <tt>em[x]</tt> will be equal to <tt>m1[x]==m2[x]</tt>.
1593  ///
1594  /// The simplest way of using this map is through the equalMap()
1595  /// function.
1596  ///
1597  /// \sa LessMap
1598  template<typename M1, typename M2>
1599  class EqualMap : public MapBase<typename M1::Key, bool> {
1600    const M1 &_m1;
1601    const M2 &_m2;
1602  public:
1603    typedef MapBase<typename M1::Key, bool> Parent;
1604    typedef typename Parent::Key Key;
1605    typedef typename Parent::Value Value;
1606
1607    /// Constructor
1608    EqualMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1609    /// \e
1610    Value operator[](const Key &k) const { return _m1[k]==_m2[k]; }
1611  };
1612
1613  /// Returns an \ref EqualMap class
1614
1615  /// This function just returns an \ref EqualMap class.
1616  ///
1617  /// For example, if \c m1 and \c m2 are maps with keys and values of
1618  /// the same type, then <tt>equalMap(m1,m2)[x]</tt> will be equal to
1619  /// <tt>m1[x]==m2[x]</tt>.
1620  ///
1621  /// \relates EqualMap
1622  template<typename M1, typename M2>
1623  inline EqualMap<M1, M2> equalMap(const M1 &m1, const M2 &m2) {
1624    return EqualMap<M1, M2>(m1,m2);
1625  }
1626
1627
1628  /// Combination of two maps using the \c < operator
1629
1630  /// This \ref concepts::ReadMap "read-only map" assigns \c true to
1631  /// the keys for which the corresponding value of the first map is
1632  /// less then the value of the second map.
1633  /// Its \c Key type is inherited from \c M1 and its \c Value type is
1634  /// \c bool. \c M2::Key must be convertible to \c M1::Key.
1635  ///
1636  /// If \c m1 is of type \c M1 and \c m2 is of \c M2, then for
1637  /// \code
1638  ///   LessMap<M1,M2> lm(m1,m2);
1639  /// \endcode
1640  /// <tt>lm[x]</tt> will be equal to <tt>m1[x]<m2[x]</tt>.
1641  ///
1642  /// The simplest way of using this map is through the lessMap()
1643  /// function.
1644  ///
1645  /// \sa EqualMap
1646  template<typename M1, typename M2>
1647  class LessMap : public MapBase<typename M1::Key, bool> {
1648    const M1 &_m1;
1649    const M2 &_m2;
1650  public:
1651    typedef MapBase<typename M1::Key, bool> Parent;
1652    typedef typename Parent::Key Key;
1653    typedef typename Parent::Value Value;
1654
1655    /// Constructor
1656    LessMap(const M1 &m1, const M2 &m2) : _m1(m1), _m2(m2) {}
1657    /// \e
1658    Value operator[](const Key &k) const { return _m1[k]<_m2[k]; }
1659  };
1660
1661  /// Returns an \ref LessMap class
1662
1663  /// This function just returns an \ref LessMap class.
1664  ///
1665  /// For example, if \c m1 and \c m2 are maps with keys and values of
1666  /// the same type, then <tt>lessMap(m1,m2)[x]</tt> will be equal to
1667  /// <tt>m1[x]<m2[x]</tt>.
1668  ///
1669  /// \relates LessMap
1670  template<typename M1, typename M2>
1671  inline LessMap<M1, M2> lessMap(const M1 &m1, const M2 &m2) {
1672    return LessMap<M1, M2>(m1,m2);
1673  }
1674
[104]1675  namespace _maps_bits {
1676
1677    template <typename _Iterator, typename Enable = void>
1678    struct IteratorTraits {
1679      typedef typename std::iterator_traits<_Iterator>::value_type Value;
1680    };
1681
1682    template <typename _Iterator>
1683    struct IteratorTraits<_Iterator,
1684      typename exists<typename _Iterator::container_type>::type>
1685    {
1686      typedef typename _Iterator::container_type::value_type Value;
1687    };
1688
1689  }
1690
1691  /// \brief Writable bool map for logging each \c true assigned element
1692  ///
[159]1693  /// A \ref concepts::WriteMap "writable" bool map for logging
[104]1694  /// each \c true assigned element, i.e it copies subsequently each
1695  /// keys set to \c true to the given iterator.
[159]1696  /// The most important usage of it is storing certain nodes or arcs
1697  /// that were marked \c true by an algorithm.
[104]1698  ///
[159]1699  /// There are several algorithms that provide solutions through bool
1700  /// maps and most of them assign \c true at most once for each key.
1701  /// In these cases it is a natural request to store each \c true
1702  /// assigned elements (in order of the assignment), which can be
[167]1703  /// easily done with LoggerBoolMap.
[159]1704  ///
[167]1705  /// The simplest way of using this map is through the loggerBoolMap()
[159]1706  /// function.
1707  ///
1708  /// \tparam It The type of the iterator.
1709  /// \tparam Ke The key type of the map. The default value set
1710  /// according to the iterator type should work in most cases.
[104]1711  ///
1712  /// \note The container of the iterator must contain enough space
[159]1713  /// for the elements or the iterator should be an inserter iterator.
1714#ifdef DOXYGEN
1715  template <typename It, typename Ke>
1716#else
[104]1717  template <typename It,
[209]1718            typename Ke=typename _maps_bits::IteratorTraits<It>::Value>
[159]1719#endif
[167]1720  class LoggerBoolMap {
[104]1721  public:
1722    typedef It Iterator;
1723
1724    typedef Ke Key;
1725    typedef bool Value;
1726
1727    /// Constructor
[167]1728    LoggerBoolMap(Iterator it)
[104]1729      : _begin(it), _end(it) {}
1730
1731    /// Gives back the given iterator set for the first key
1732    Iterator begin() const {
1733      return _begin;
1734    }
1735
1736    /// Gives back the the 'after the last' iterator
1737    Iterator end() const {
1738      return _end;
1739    }
1740
1741    /// The set function of the map
[159]1742    void set(const Key& key, Value value) {
[104]1743      if (value) {
[209]1744        *_end++ = key;
[104]1745      }
1746    }
1747
1748  private:
1749    Iterator _begin;
[159]1750    Iterator _end;
[104]1751  };
[209]1752
[167]1753  /// Returns a \ref LoggerBoolMap class
[159]1754
[167]1755  /// This function just returns a \ref LoggerBoolMap class.
[159]1756  ///
1757  /// The most important usage of it is storing certain nodes or arcs
1758  /// that were marked \c true by an algorithm.
1759  /// For example it makes easier to store the nodes in the processing
1760  /// order of Dfs algorithm, as the following examples show.
1761  /// \code
1762  ///   std::vector<Node> v;
[167]1763  ///   dfs(g,s).processedMap(loggerBoolMap(std::back_inserter(v))).run();
[159]1764  /// \endcode
1765  /// \code
1766  ///   std::vector<Node> v(countNodes(g));
[167]1767  ///   dfs(g,s).processedMap(loggerBoolMap(v.begin())).run();
[159]1768  /// \endcode
1769  ///
1770  /// \note The container of the iterator must contain enough space
1771  /// for the elements or the iterator should be an inserter iterator.
1772  ///
[167]1773  /// \note LoggerBoolMap is just \ref concepts::WriteMap "writable", so
[159]1774  /// it cannot be used when a readable map is needed, for example as
[167]1775  /// \c ReachedMap for \ref Bfs, \ref Dfs and \ref Dijkstra algorithms.
[159]1776  ///
[167]1777  /// \relates LoggerBoolMap
[159]1778  template<typename Iterator>
[167]1779  inline LoggerBoolMap<Iterator> loggerBoolMap(Iterator it) {
1780    return LoggerBoolMap<Iterator>(it);
[159]1781  }
[104]1782
[25]1783  /// @}
1784}
1785
1786#endif // LEMON_MAPS_H
Note: See TracBrowser for help on using the repository browser.