COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/maps.h @ 104:cdbba181b786

Last change on this file since 104:cdbba181b786 was 104:cdbba181b786, checked in by Alpar Juttner <alpar@…>, 12 years ago

Restored (and modified) StoreBoolMap? (it was removed in 7ff1c348ae0c)

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