COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/maps.h @ 1948:9e9c035a08be

Last change on this file since 1948:9e9c035a08be was 1875:98698b69a902, checked in by Alpar Juttner, 18 years ago

Happy new year to LEMON

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