COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/maps.h @ 1993:2115143eceea

Last change on this file since 1993:2115143eceea was 1993:2115143eceea, checked in by Balazs Dezso, 14 years ago

utility, invalid and traits moved to bits

File size: 29.3 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
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
24#include <lemon/bits/utility.h>
25#include <lemon/bits/traits.h>
26
27///\file
28///\ingroup maps
29///\brief Miscellaneous property maps
30///
31///\todo This file has the same name as the concept file in concept/,
32/// and this is not easily detectable in docs...
33
34#include <map>
35
36namespace lemon {
37
38  /// \addtogroup maps
39  /// @{
40
41  /// Base class of maps.
42
43  /// Base class of maps.
44  /// It provides the necessary <tt>typedef</tt>s required by the map concept.
45  template<typename K, typename T>
46  class MapBase {
47  public:
48    ///\e
49    typedef K Key;
50    ///\e
51    typedef T Value;
52  };
53
54  /// Null map. (a.k.a. DoNothingMap)
55
56  /// If you have to provide a map only for its type definitions,
57  /// or if you have to provide a writable map, but
58  /// data written to it will sent to <tt>/dev/null</tt>...
59  template<typename K, typename T>
60  class NullMap : public MapBase<K, T> {
61  public:
62    typedef MapBase<K, T> Parent;
63    typedef typename Parent::Key Key;
64    typedef typename Parent::Value Value;
65   
66    /// Gives back a default constructed element.
67    T operator[](const K&) const { return T(); }
68    /// Absorbs the value.
69    void set(const K&, const T&) {}
70  };
71
72  template <typename K, typename V>
73  NullMap<K, V> nullMap() {
74    return NullMap<K, V>();
75  }
76
77
78  /// Constant map.
79
80  /// This is a readable map which assigns a specified value to each key.
81  /// In other aspects it is equivalent to the \ref NullMap.
82  /// \todo set could be used to set the value.
83  template<typename K, typename T>
84  class ConstMap : public MapBase<K, T> {
85  private:
86    T v;
87  public:
88
89    typedef MapBase<K, T> Parent;
90    typedef typename Parent::Key Key;
91    typedef typename Parent::Value Value;
92
93    /// Default constructor
94
95    /// The value of the map will be uninitialized.
96    /// (More exactly it will be default constructed.)
97    ConstMap() {}
98    ///\e
99
100    /// \param _v The initial value of the map.
101    ///
102    ConstMap(const T &_v) : v(_v) {}
103
104    T operator[](const K&) const { return v; }
105    void set(const K&, const T&) {}
106
107    template<typename T1>
108    struct rebind {
109      typedef ConstMap<K, T1> other;
110    };
111
112    template<typename T1>
113    ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
114  };
115
116  ///Returns a \ref ConstMap class
117
118  ///This function just returns a \ref ConstMap class.
119  ///\relates ConstMap
120  template<typename K, typename V>
121  inline ConstMap<K, V> constMap(const V &v) {
122    return ConstMap<K, V>(v);
123  }
124
125
126  //\todo to document later
127  template<typename T, T v>
128  struct Const { };
129
130  //\todo to document later
131  template<typename K, typename V, V v>
132  class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
133  public:
134    typedef MapBase<K, V> Parent;
135    typedef typename Parent::Key Key;
136    typedef typename Parent::Value Value;
137
138    ConstMap() { }
139    V operator[](const K&) const { return v; }
140    void set(const K&, const V&) { }
141  };
142
143  ///Returns a \ref ConstMap class
144
145  ///This function just returns a \ref ConstMap class.
146  ///\relates ConstMap
147  template<typename K, typename V, V v>
148  inline ConstMap<K, Const<V, v> > constMap() {
149    return ConstMap<K, Const<V, v> >();
150  }
151
152  /// \c std::map wrapper
153
154  /// This is essentially a wrapper for \c std::map. With addition that
155  /// you can specify a default value different from \c Value() .
156  ///
157  /// \todo Provide allocator parameter...
158  template <typename K, typename T, typename Compare = std::less<K> >
159  class StdMap : public std::map<K, T, Compare> {
160    typedef std::map<K, T, Compare> parent;
161    T v;
162    typedef typename parent::value_type PairType;
163
164  public:
165    ///\e
166    typedef K Key;
167    ///\e
168    typedef T Value;
169    ///\e
170    typedef T& Reference;
171    ///\e
172    typedef const T& ConstReference;
173
174
175    StdMap() : v() {}
176    /// Constructor with specified default value
177    StdMap(const T& _v) : v(_v) {}
178
179    /// \brief Constructs the map from an appropriate std::map.
180    ///
181    /// \warning Inefficient: copies the content of \c m !
182    StdMap(const parent &m) : parent(m) {}
183    /// \brief Constructs the map from an appropriate std::map, and explicitly
184    /// specifies a default value.
185    ///
186    /// \warning Inefficient: copies the content of \c m !
187    StdMap(const parent &m, const T& _v) : parent(m), v(_v) {}
188   
189    template<typename T1, typename Comp1>
190    StdMap(const StdMap<Key, T1,Comp1> &m, const T &_v) {
191      //FIXME;
192    }
193
194    Reference operator[](const Key &k) {
195      return insert(PairType(k,v)).first -> second;
196    }
197
198    ConstReference operator[](const Key &k) const {
199      typename parent::iterator i = lower_bound(k);
200      if (i == parent::end() || parent::key_comp()(k, (*i).first))
201        return v;
202      return (*i).second;
203    }
204    void set(const Key &k, const T &t) {
205      parent::operator[](k) = t;
206    }
207
208    /// Changes the default value of the map.
209    /// \return Returns the previous default value.
210    ///
211    /// \warning The value of some keys (which has already been queried, but
212    /// the value has been unchanged from the default) may change!
213    T setDefault(const T &_v) { T old=v; v=_v; return old; }
214
215    template<typename T1>
216    struct rebind {
217      typedef StdMap<Key, T1,Compare> other;
218    };
219  };
220
221  /// @}
222
223  /// \addtogroup map_adaptors
224  /// @{
225
226  /// \brief Identity mapping.
227  ///
228  /// This mapping gives back the given key as value without any
229  /// modification.
230  template <typename T>
231  class IdentityMap : public MapBase<T, T> {
232  public:
233    typedef MapBase<T, T> Parent;
234    typedef typename Parent::Key Key;
235    typedef typename Parent::Value Value;
236
237    const T& operator[](const T& t) const {
238      return t;
239    }
240  };
241
242  ///Returns an \ref IdentityMap class
243
244  ///This function just returns an \ref IdentityMap class.
245  ///\relates IdentityMap
246  template<typename T>
247  inline IdentityMap<T> identityMap() {
248    return IdentityMap<T>();
249  }
250 
251
252  ///Convert the \c Value of a map to another type.
253
254  ///This \ref concept::ReadMap "read only map"
255  ///converts the \c Value of a maps to type \c T.
256  ///Its \c Key is inherited from \c M.
257  template <typename M, typename T>
258  class ConvertMap : public MapBase<typename M::Key, T> {
259    const M& m;
260  public:
261    typedef MapBase<typename M::Key, T> Parent;
262    typedef typename Parent::Key Key;
263    typedef typename Parent::Value Value;
264
265    ///Constructor
266
267    ///Constructor
268    ///\param _m is the underlying map
269    ConvertMap(const M &_m) : m(_m) {};
270
271    /// \brief The subscript operator.
272    ///
273    /// The subscript operator.
274    /// \param k The key
275    /// \return The target of the edge
276    Value operator[](const Key& k) const {return m[k];}
277  };
278 
279  ///Returns an \ref ConvertMap class
280
281  ///This function just returns an \ref ConvertMap class.
282  ///\relates ConvertMap
283  ///\todo The order of the template parameters are changed.
284  template<typename T, typename M>
285  inline ConvertMap<M, T> convertMap(const M &m) {
286    return ConvertMap<M, T>(m);
287  }
288
289  ///Sum of two maps
290
291  ///This \ref concept::ReadMap "read only map" returns the sum of the two
292  ///given maps. Its \c Key and \c Value will be inherited from \c M1.
293  ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
294
295  template<typename M1, typename M2>
296  class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
297    const M1& m1;
298    const M2& m2;
299
300  public:
301    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
302    typedef typename Parent::Key Key;
303    typedef typename Parent::Value Value;
304
305    ///Constructor
306    AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
307    Value operator[](Key k) const {return m1[k]+m2[k];}
308  };
309 
310  ///Returns an \ref AddMap class
311
312  ///This function just returns an \ref AddMap class.
313  ///\todo How to call these type of functions?
314  ///
315  ///\relates AddMap
316  ///\todo Wrong scope in Doxygen when \c \\relates is used
317  template<typename M1, typename M2>
318  inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
319    return AddMap<M1, M2>(m1,m2);
320  }
321
322  ///Shift a map with a constant.
323
324  ///This \ref concept::ReadMap "read only map" returns the sum of the
325  ///given map and a constant value.
326  ///Its \c Key and \c Value is inherited from \c M.
327  ///
328  ///Actually,
329  ///\code
330  ///  ShiftMap<X> sh(x,v);
331  ///\endcode
332  ///is equivalent with
333  ///\code
334  ///  ConstMap<X::Key, X::Value> c_tmp(v);
335  ///  AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
336  ///\endcode
337  template<typename M, typename C = typename M::Value>
338  class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
339    const M& m;
340    C v;
341  public:
342    typedef MapBase<typename M::Key, typename M::Value> Parent;
343    typedef typename Parent::Key Key;
344    typedef typename Parent::Value Value;
345
346    ///Constructor
347
348    ///Constructor
349    ///\param _m is the undelying map
350    ///\param _v is the shift value
351    ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
352    Value operator[](Key k) const {return m[k] + v;}
353  };
354 
355  ///Returns an \ref ShiftMap class
356
357  ///This function just returns an \ref ShiftMap class.
358  ///\relates ShiftMap
359  ///\todo A better name is required.
360  template<typename M, typename C>
361  inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
362    return ShiftMap<M, C>(m,v);
363  }
364
365  ///Difference of two maps
366
367  ///This \ref concept::ReadMap "read only map" returns the difference
368  ///of the values of the two
369  ///given maps. Its \c Key and \c Value will be inherited from \c M1.
370  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
371
372  template<typename M1, typename M2>
373  class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
374    const M1& m1;
375    const M2& m2;
376  public:
377    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
378    typedef typename Parent::Key Key;
379    typedef typename Parent::Value Value;
380
381    ///Constructor
382    SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
383    Value operator[](Key k) const {return m1[k]-m2[k];}
384  };
385 
386  ///Returns a \ref SubMap class
387
388  ///This function just returns a \ref SubMap class.
389  ///
390  ///\relates SubMap
391  template<typename M1, typename M2>
392  inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
393    return SubMap<M1, M2>(m1, m2);
394  }
395
396  ///Product of two maps
397
398  ///This \ref concept::ReadMap "read only map" returns the product of the
399  ///values of the two
400  ///given
401  ///maps. Its \c Key and \c Value will be inherited from \c M1.
402  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
403
404  template<typename M1, typename M2>
405  class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
406    const M1& m1;
407    const M2& m2;
408  public:
409    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
410    typedef typename Parent::Key Key;
411    typedef typename Parent::Value Value;
412
413    ///Constructor
414    MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
415    Value operator[](Key k) const {return m1[k]*m2[k];}
416  };
417 
418  ///Returns a \ref MulMap class
419
420  ///This function just returns a \ref MulMap class.
421  ///\relates MulMap
422  template<typename M1, typename M2>
423  inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
424    return MulMap<M1, M2>(m1,m2);
425  }
426 
427  ///Scales a maps with a constant.
428
429  ///This \ref concept::ReadMap "read only map" returns the value of the
430  ///given map multiplied from the left side with a constant value.
431  ///Its \c Key and \c Value is inherited from \c M.
432  ///
433  ///Actually,
434  ///\code
435  ///  ScaleMap<X> sc(x,v);
436  ///\endcode
437  ///is equivalent with
438  ///\code
439  ///  ConstMap<X::Key, X::Value> c_tmp(v);
440  ///  MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
441  ///\endcode
442  template<typename M, typename C = typename M::Value>
443  class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
444    const M& m;
445    C v;
446  public:
447    typedef MapBase<typename M::Key, typename M::Value> Parent;
448    typedef typename Parent::Key Key;
449    typedef typename Parent::Value Value;
450
451    ///Constructor
452
453    ///Constructor
454    ///\param _m is the undelying map
455    ///\param _v is the scaling value
456    ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
457    Value operator[](Key k) const {return v * m[k];}
458  };
459 
460  ///Returns an \ref ScaleMap class
461
462  ///This function just returns an \ref ScaleMap class.
463  ///\relates ScaleMap
464  ///\todo A better name is required.
465  template<typename M, typename C>
466  inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
467    return ScaleMap<M, C>(m,v);
468  }
469
470  ///Quotient of two maps
471
472  ///This \ref concept::ReadMap "read only map" returns the quotient of the
473  ///values of the two
474  ///given maps. Its \c Key and \c Value will be inherited from \c M1.
475  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
476
477  template<typename M1, typename M2>
478  class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
479    const M1& m1;
480    const M2& m2;
481  public:
482    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
483    typedef typename Parent::Key Key;
484    typedef typename Parent::Value Value;
485
486    ///Constructor
487    DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
488    Value operator[](Key k) const {return m1[k]/m2[k];}
489  };
490 
491  ///Returns a \ref DivMap class
492
493  ///This function just returns a \ref DivMap class.
494  ///\relates DivMap
495  template<typename M1, typename M2>
496  inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
497    return DivMap<M1, M2>(m1,m2);
498  }
499 
500  ///Composition of two maps
501
502  ///This \ref concept::ReadMap "read only map" returns the composition of
503  ///two
504  ///given maps. That is to say, if \c m1 is of type \c M1 and \c m2 is
505  ///of \c M2,
506  ///then for
507  ///\code
508  ///  ComposeMap<M1, M2> cm(m1,m2);
509  ///\endcode
510  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>
511  ///
512  ///Its \c Key is inherited from \c M2 and its \c Value is from
513  ///\c M1.
514  ///The \c M2::Value must be convertible to \c M1::Key.
515  ///\todo Check the requirements.
516
517  template <typename M1, typename M2>
518  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
519    const M1& m1;
520    const M2& m2;
521  public:
522    typedef MapBase<typename M2::Key, typename M1::Value> Parent;
523    typedef typename Parent::Key Key;
524    typedef typename Parent::Value Value;
525
526    ///Constructor
527    ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
528   
529    typename MapTraits<M1>::ConstReturnValue
530    operator[](Key k) const {return m1[m2[k]];}
531  };
532  ///Returns a \ref ComposeMap class
533
534  ///This function just returns a \ref ComposeMap class.
535  ///
536  ///\relates ComposeMap
537  template <typename M1, typename M2>
538  inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
539    return ComposeMap<M1, M2>(m1,m2);
540  }
541 
542  ///Combines of two maps using an STL (binary) functor.
543
544  ///Combines of two maps using an STL (binary) functor.
545  ///
546  ///
547  ///This \ref concept::ReadMap "read only map" takes two maps and a
548  ///binary functor and returns the composition of
549  ///the two
550  ///given maps unsing the functor.
551  ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
552  ///and \c f is of \c F,
553  ///then for
554  ///\code
555  ///  CombineMap<M1, M2,F,V> cm(m1,m2,f);
556  ///\endcode
557  /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
558  ///
559  ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
560  ///The \c M2::Value and \c M1::Value must be convertible to the corresponding
561  ///input parameter of \c F and the return type of \c F must be convertible
562  ///to \c V.
563  ///\todo Check the requirements.
564
565  template<typename M1, typename M2, typename F,
566           typename V = typename F::result_type,
567           typename NC = False>
568  class CombineMap : public MapBase<typename M1::Key, V> {
569    const M1& m1;
570    const M2& m2;
571    F f;
572  public:
573    typedef MapBase<typename M1::Key, V> Parent;
574    typedef typename Parent::Key Key;
575    typedef typename Parent::Value Value;
576
577    ///Constructor
578    CombineMap(const M1 &_m1,const M2 &_m2,const F &_f)
579      : m1(_m1), m2(_m2), f(_f) {};
580    Value operator[](Key k) const {return f(m1[k],m2[k]);}
581  };
582 
583  ///Returns a \ref CombineMap class
584
585  ///This function just returns a \ref CombineMap class.
586  ///
587  ///Only the first template parameter (the value type) must be given.
588  ///
589  ///For example if \c m1 and \c m2 are both \c double valued maps, then
590  ///\code
591  ///combineMap<double>(m1,m2,std::plus<double>)
592  ///\endcode
593  ///is equivalent with
594  ///\code
595  ///addMap(m1,m2)
596  ///\endcode
597  ///
598  ///\relates CombineMap
599  template<typename M1, typename M2, typename F, typename V>
600  inline CombineMap<M1, M2, F, V>
601  combineMap(const M1& m1,const M2& m2, const F& f) {
602    return CombineMap<M1, M2, F, V>(m1,m2,f);
603  }
604
605  template<typename M1, typename M2, typename F>
606  inline CombineMap<M1, M2, F, typename F::result_type>
607  combineMap(const M1& m1, const M2& m2, const F& f) {
608    return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
609  }
610
611  template<typename M1, typename M2, typename K1, typename K2, typename V>
612  inline CombineMap<M1, M2, V (*)(K1, K2), V>
613  combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
614    return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
615  }
616
617  ///Negative value of a map
618
619  ///This \ref concept::ReadMap "read only map" returns the negative
620  ///value of the
621  ///value returned by the
622  ///given map. Its \c Key and \c Value will be inherited from \c M.
623  ///The unary \c - operator must be defined for \c Value, of course.
624
625  template<typename M>
626  class NegMap : public MapBase<typename M::Key, typename M::Value> {
627    const M& m;
628  public:
629    typedef MapBase<typename M::Key, typename M::Value> Parent;
630    typedef typename Parent::Key Key;
631    typedef typename Parent::Value Value;
632
633    ///Constructor
634    NegMap(const M &_m) : m(_m) {};
635    Value operator[](Key k) const {return -m[k];}
636  };
637 
638  ///Returns a \ref NegMap class
639
640  ///This function just returns a \ref NegMap class.
641  ///\relates NegMap
642  template <typename M>
643  inline NegMap<M> negMap(const M &m) {
644    return NegMap<M>(m);
645  }
646
647
648  ///Absolute value of a map
649
650  ///This \ref concept::ReadMap "read only map" returns the absolute value
651  ///of the
652  ///value returned by the
653  ///given map. Its \c Key and \c Value will be inherited
654  ///from <tt>M</tt>. <tt>Value</tt>
655  ///must be comparable to <tt>0</tt> and the unary <tt>-</tt>
656  ///operator must be defined for it, of course.
657  ///
658  ///\bug We need a unified way to handle the situation below:
659  ///\code
660  ///  struct _UnConvertible {};
661  ///  template<class A> inline A t_abs(A a) {return _UnConvertible();}
662  ///  template<> inline int t_abs<>(int n) {return abs(n);}
663  ///  template<> inline long int t_abs<>(long int n) {return labs(n);}
664  ///  template<> inline long long int t_abs<>(long long int n) {return ::llabs(n);}
665  ///  template<> inline float t_abs<>(float n) {return fabsf(n);}
666  ///  template<> inline double t_abs<>(double n) {return fabs(n);}
667  ///  template<> inline long double t_abs<>(long double n) {return fabsl(n);}
668  ///\endcode
669 
670
671  template<typename M>
672  class AbsMap : public MapBase<typename M::Key, typename M::Value> {
673    const M& m;
674  public:
675    typedef MapBase<typename M::Key, typename M::Value> Parent;
676    typedef typename Parent::Key Key;
677    typedef typename Parent::Value Value;
678
679    ///Constructor
680    AbsMap(const M &_m) : m(_m) {};
681    Value operator[](Key k) const {
682      Value tmp = m[k];
683      return tmp >= 0 ? tmp : -tmp;
684    }
685
686  };
687 
688  ///Returns a \ref AbsMap class
689
690  ///This function just returns a \ref AbsMap class.
691  ///\relates AbsMap
692  template<typename M>
693  inline AbsMap<M> absMap(const M &m) {
694    return AbsMap<M>(m);
695  }
696
697  ///Converts an STL style functor to a map
698
699  ///This \ref concept::ReadMap "read only map" returns the value
700  ///of a
701  ///given map.
702  ///
703  ///Template parameters \c K and \c V will become its
704  ///\c Key and \c Value. They must be given explicitely
705  ///because a functor does not provide such typedefs.
706  ///
707  ///Parameter \c F is the type of the used functor.
708 
709
710  template<typename F,
711           typename K = typename F::argument_type,
712           typename V = typename F::result_type,
713           typename NC = False>
714  class FunctorMap : public MapBase<K, V> {
715    F f;
716  public:
717    typedef MapBase<K, V> Parent;
718    typedef typename Parent::Key Key;
719    typedef typename Parent::Value Value;
720
721    ///Constructor
722    FunctorMap(const F &_f) : f(_f) {}
723
724    Value operator[](Key k) const { return f(k);}
725  };
726 
727  ///Returns a \ref FunctorMap class
728
729  ///This function just returns a \ref FunctorMap class.
730  ///
731  ///The third template parameter isn't necessary to be given.
732  ///\relates FunctorMap
733  template<typename K, typename V, typename F> inline
734  FunctorMap<F, K, V> functorMap(const F &f) {
735    return FunctorMap<F, K, V>(f);
736  }
737
738  template <typename F> inline
739  FunctorMap<F, typename F::argument_type, typename F::result_type>
740  functorMap(const F &f) {
741    return FunctorMap<F, typename F::argument_type,
742      typename F::result_type>(f);
743  }
744
745  template <typename K, typename V> inline
746  FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
747    return FunctorMap<V (*)(K), K, V>(f);
748  }
749
750
751  ///Converts a map to an STL style (unary) functor
752
753  ///This class Converts a map to an STL style (unary) functor.
754  ///that is it provides an <tt>operator()</tt> to read its values.
755  ///
756  ///For the sake of convenience it also works as
757  ///a ususal \ref concept::ReadMap "readable map",
758  ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
759
760  template <typename M>
761  class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
762    const M& m;
763  public:
764    typedef MapBase<typename M::Key, typename M::Value> Parent;
765    typedef typename Parent::Key Key;
766    typedef typename Parent::Value Value;
767
768    ///\e
769    typedef typename M::Key argument_type;
770    ///\e
771    typedef typename M::Value result_type;
772
773    ///Constructor
774    MapFunctor(const M &_m) : m(_m) {};
775    ///Returns a value of the map
776    Value operator()(Key k) const {return m[k];}
777    ///\e
778    Value operator[](Key k) const {return m[k];}
779  };
780 
781  ///Returns a \ref MapFunctor class
782
783  ///This function just returns a \ref MapFunctor class.
784  ///\relates MapFunctor
785  template<typename M>
786  inline MapFunctor<M> mapFunctor(const M &m) {
787    return MapFunctor<M>(m);
788  }
789
790
791  ///Applies all map setting operations to two maps
792
793  ///This map has two \ref concept::WriteMap "writable map"
794  ///parameters and each write request will be passed to both of them.
795  ///If \c M1 is also \ref concept::ReadMap "readable",
796  ///then the read operations will return the
797  ///corresponding values of \c M1.
798  ///
799  ///The \c Key and \c Value will be inherited from \c M1.
800  ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
801
802  template<typename  M1, typename M2>
803  class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
804    const M1& m1;
805    const M2& m2;
806  public:
807    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
808    typedef typename Parent::Key Key;
809    typedef typename Parent::Value Value;
810
811    ///Constructor
812    ForkMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
813    Value operator[](Key k) const {return m1[k];}
814    //    void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
815  };
816 
817  ///Returns an \ref ForkMap class
818
819  ///This function just returns an \ref ForkMap class.
820  ///\todo How to call these type of functions?
821  ///
822  ///\relates ForkMap
823  ///\todo Wrong scope in Doxygen when \c \\relates is used
824  template <typename M1, typename M2>
825  inline ForkMap<M1, M2> forkMap(const M1 &m1,const M2 &m2) {
826    return ForkMap<M1, M2>(m1,m2);
827  }
828
829
830 
831  /* ************* BOOL MAPS ******************* */
832 
833  ///Logical 'not' of a map
834 
835  ///This bool \ref concept::ReadMap "read only map" returns the
836  ///logical negation of
837  ///value returned by the
838  ///given map. Its \c Key and will be inherited from \c M,
839  ///its Value is <tt>bool</tt>.
840
841  template <typename M>
842  class NotMap : public MapBase<typename M::Key, bool> {
843    const M& m;
844  public:
845    typedef MapBase<typename M::Key, bool> Parent;
846    typedef typename Parent::Key Key;
847    typedef typename Parent::Value Value;
848
849    /// Constructor
850    NotMap(const M &_m) : m(_m) {};
851    Value operator[](Key k) const {return !m[k];}
852  };
853 
854  ///Returns a \ref NotMap class
855 
856  ///This function just returns a \ref NotMap class.
857  ///\relates NotMap
858  template <typename M>
859  inline NotMap<M> notMap(const M &m) {
860    return NotMap<M>(m);
861  }
862
863  /// \brief Writable bool map for store each true assigned elements.
864  ///
865  /// Writable bool map for store each true assigned elements. It will
866  /// copies all the true setted keys to the given iterator.
867  ///
868  /// \note The container of the iterator should contain for each element.
869  template <typename _Iterator>
870  class StoreBoolMap {
871  public:
872    typedef _Iterator Iterator;
873
874    typedef typename std::iterator_traits<Iterator>::value_type Key;
875    typedef bool Value;
876
877    /// Constructor
878    StoreBoolMap(Iterator it) : _begin(it), _end(it) {}
879
880    /// Gives back the given first setted iterator.
881    Iterator begin() const {
882      return _begin;
883    }
884 
885    /// Gives back the iterator after the last setted.
886    Iterator end() const {
887      return _end;
888    }
889
890    /// Setter function of the map
891    void set(const Key& key, Value value) {
892      if (value) {
893        *_end++ = key;
894      }
895    }
896   
897  private:
898    Iterator _begin, _end;
899  };
900
901  /// \brief Writable bool map for store each true assigned elements in
902  /// a back insertable container.
903  ///
904  /// Writable bool map for store each true assigned elements in a back
905  /// insertable container. It will push back all the true setted keys into
906  /// the container.
907  template <typename Container>
908  class BackInserterBoolMap {
909  public:
910    typedef typename Container::value_type Key;
911    typedef bool Value;
912
913    /// Constructor
914    BackInserterBoolMap(Container& _container) : container(_container) {}
915
916    /// Setter function of the map
917    void set(const Key& key, Value value) {
918      if (value) {
919        container.push_back(key);
920      }
921    }
922   
923  private:
924    Container& container;   
925  };
926
927  /// \brief Writable bool map for store each true assigned elements in
928  /// a front insertable container.
929  ///
930  /// Writable bool map for store each true assigned elements in a front
931  /// insertable container. It will push front all the true setted keys into
932  /// the container.
933  template <typename Container>
934  class FrontInserterBoolMap {
935  public:
936    typedef typename Container::value_type Key;
937    typedef bool Value;
938
939    /// Constructor
940    FrontInserterBoolMap(Container& _container) : container(_container) {}
941
942    /// Setter function of the map
943    void set(const Key& key, Value value) {
944      if (value) {
945        container.push_front(key);
946      }
947    }
948   
949  private:
950    Container& container;   
951  };
952
953  /// \brief Writable bool map for store each true assigned elements in
954  /// an insertable container.
955  ///
956  /// Writable bool map for store each true assigned elements in an
957  /// insertable container. It will insert all the true setted keys into
958  /// the container.
959  template <typename Container>
960  class InserterBoolMap {
961  public:
962    typedef typename Container::value_type Key;
963    typedef bool Value;
964
965    /// Constructor
966    InserterBoolMap(Container& _container) : container(_container) {}
967
968    /// Setter function of the map
969    void set(const Key& key, Value value) {
970      if (value) {
971        container.insert(key);
972      }
973    }
974   
975  private:
976    Container& container;   
977  };
978
979  /// \brief Fill the true setted elements with a given value.
980  ///
981  /// Writable bool map for fill the true setted elements with a given value.
982  /// The value can be setted
983  /// the container.
984  template <typename Map>
985  class FillBoolMap {
986  public:
987    typedef typename Map::Key Key;
988    typedef bool Value;
989
990    /// Constructor
991    FillBoolMap(Map& _map, const typename Map::Value& _fill)
992      : map(_map), fill(_fill) {}
993
994    /// Constructor
995    FillBoolMap(Map& _map)
996      : map(_map), fill() {}
997
998    /// Gives back the current fill value
999    typename Map::Value fillValue() const {
1000      return fill;
1001    }
1002
1003    /// Sets the current fill value
1004    void fillValue(const typename Map::Value& _fill) {
1005      fill = _fill;
1006    }
1007
1008    /// Setter function of the map
1009    void set(const Key& key, Value value) {
1010      if (value) {
1011        map.set(key, fill);
1012      }
1013    }
1014   
1015  private:
1016    Map& map;
1017    typename Map::Value fill;
1018  };
1019
1020
1021  /// \brief Writable bool map which stores for each true assigned elements 
1022  /// the setting order number.
1023  ///
1024  /// Writable bool map which stores for each true assigned elements 
1025  /// the setting order number.
1026  template <typename Map>
1027  class SettingOrderBoolMap {
1028  public:
1029    typedef typename Map::Key Key;
1030    typedef bool Value;
1031
1032    /// Constructor
1033    SettingOrderBoolMap(Map& _map)
1034      : map(_map), counter(0) {}
1035
1036    /// Number of setted keys.
1037    int num() const {
1038      return counter;
1039    }
1040
1041    /// Setter function of the map
1042    void set(const Key& key, Value value) {
1043      if (value) {
1044        map.set(key, counter++);
1045      }
1046    }
1047   
1048  private:
1049    Map& map;
1050    int counter;
1051  };
1052
1053  /// @}
1054}
1055
1056#endif // LEMON_MAPS_H
Note: See TracBrowser for help on using the repository browser.