COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/maps.h @ 2090:923f69c38d55

Last change on this file since 2090:923f69c38d55 was 2080:630a5e16dc12, checked in by Balazs Dezso, 18 years ago

Bug fix

File size: 34.0 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  ///Shift a map with a constant.
356
357  ///This \ref concept::ReadWriteMap "read-write map" returns the sum of the
358  ///given map and a constant value. It makes also possible to write the map.
359  ///Its \c Key and \c Value is inherited from \c M.
360  ///
361  ///Actually,
362  ///\code
363  ///  ShiftMap<X> sh(x,v);
364  ///\endcode
365  ///is equivalent with
366  ///\code
367  ///  ConstMap<X::Key, X::Value> c_tmp(v);
368  ///  AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
369  ///\endcode
370  template<typename M, typename C = typename M::Value>
371  class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
372    M& m;
373    C v;
374  public:
375    typedef MapBase<typename M::Key, typename M::Value> Parent;
376    typedef typename Parent::Key Key;
377    typedef typename Parent::Value Value;
378
379    ///Constructor
380
381    ///Constructor
382    ///\param _m is the undelying map
383    ///\param _v is the shift value
384    ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
385    Value operator[](Key k) const {return m[k] + v;}
386    void set(Key k, const Value& c) { m.set(k, c - v); }
387  };
388 
389  ///Returns an \ref ShiftMap class
390
391  ///This function just returns an \ref ShiftMap class.
392  ///\relates ShiftMap
393  ///\todo A better name is required.
394  template<typename M, typename C>
395  inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
396    return ShiftMap<M, C>(m,v);
397  }
398
399  template<typename M, typename C>
400  inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) {
401    return ShiftWriteMap<M, C>(m,v);
402  }
403
404  ///Difference of two maps
405
406  ///This \ref concept::ReadMap "read only map" returns the difference
407  ///of the values of the two
408  ///given maps. Its \c Key and \c Value will be inherited from \c M1.
409  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
410
411  template<typename M1, typename M2>
412  class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
413    const M1& m1;
414    const M2& m2;
415  public:
416    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
417    typedef typename Parent::Key Key;
418    typedef typename Parent::Value Value;
419
420    ///Constructor
421    SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
422    Value operator[](Key k) const {return m1[k]-m2[k];}
423  };
424 
425  ///Returns a \ref SubMap class
426
427  ///This function just returns a \ref SubMap class.
428  ///
429  ///\relates SubMap
430  template<typename M1, typename M2>
431  inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
432    return SubMap<M1, M2>(m1, m2);
433  }
434
435  ///Product of two maps
436
437  ///This \ref concept::ReadMap "read only map" returns the product of the
438  ///values of the two
439  ///given
440  ///maps. Its \c Key and \c Value will be inherited from \c M1.
441  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
442
443  template<typename M1, typename M2>
444  class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
445    const M1& m1;
446    const M2& m2;
447  public:
448    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
449    typedef typename Parent::Key Key;
450    typedef typename Parent::Value Value;
451
452    ///Constructor
453    MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
454    Value operator[](Key k) const {return m1[k]*m2[k];}
455  };
456 
457  ///Returns a \ref MulMap class
458
459  ///This function just returns a \ref MulMap class.
460  ///\relates MulMap
461  template<typename M1, typename M2>
462  inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
463    return MulMap<M1, M2>(m1,m2);
464  }
465 
466  ///Scales a maps with a constant.
467
468  ///This \ref concept::ReadMap "read only map" returns the value of the
469  ///given map multiplied from the left side with a constant value.
470  ///Its \c Key and \c Value is inherited from \c M.
471  ///
472  ///Actually,
473  ///\code
474  ///  ScaleMap<X> sc(x,v);
475  ///\endcode
476  ///is equivalent with
477  ///\code
478  ///  ConstMap<X::Key, X::Value> c_tmp(v);
479  ///  MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
480  ///\endcode
481  template<typename M, typename C = typename M::Value>
482  class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
483    const M& m;
484    C v;
485  public:
486    typedef MapBase<typename M::Key, typename M::Value> Parent;
487    typedef typename Parent::Key Key;
488    typedef typename Parent::Value Value;
489
490    ///Constructor
491
492    ///Constructor
493    ///\param _m is the undelying map
494    ///\param _v is the scaling value
495    ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
496    Value operator[](Key k) const {return v * m[k];}
497  };
498
499  ///Scales a maps with a constant.
500
501  ///This \ref concept::ReadWriteMap "read-write map" returns the value of the
502  ///given map multiplied from the left side with a constant value. It can
503  ///be used as write map also if the given multiplier is not zero.
504  ///Its \c Key and \c Value is inherited from \c M.
505  template<typename M, typename C = typename M::Value>
506  class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
507    M& m;
508    C v;
509  public:
510    typedef MapBase<typename M::Key, typename M::Value> Parent;
511    typedef typename Parent::Key Key;
512    typedef typename Parent::Value Value;
513
514    ///Constructor
515
516    ///Constructor
517    ///\param _m is the undelying map
518    ///\param _v is the scaling value
519    ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
520    Value operator[](Key k) const {return v * m[k];}
521    void set(Key k, const Value& c) { m.set(k, c / v);}
522  };
523 
524  ///Returns an \ref ScaleMap class
525
526  ///This function just returns an \ref ScaleMap class.
527  ///\relates ScaleMap
528  ///\todo A better name is required.
529  template<typename M, typename C>
530  inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
531    return ScaleMap<M, C>(m,v);
532  }
533
534  template<typename M, typename C>
535  inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) {
536    return ScaleWriteMap<M, C>(m,v);
537  }
538
539  ///Quotient of two maps
540
541  ///This \ref concept::ReadMap "read only map" returns the quotient of the
542  ///values of the two
543  ///given maps. Its \c Key and \c Value will be inherited from \c M1.
544  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
545
546  template<typename M1, typename M2>
547  class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
548    const M1& m1;
549    const M2& m2;
550  public:
551    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
552    typedef typename Parent::Key Key;
553    typedef typename Parent::Value Value;
554
555    ///Constructor
556    DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
557    Value operator[](Key k) const {return m1[k]/m2[k];}
558  };
559 
560  ///Returns a \ref DivMap class
561
562  ///This function just returns a \ref DivMap class.
563  ///\relates DivMap
564  template<typename M1, typename M2>
565  inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
566    return DivMap<M1, M2>(m1,m2);
567  }
568 
569  ///Composition of two maps
570
571  ///This \ref concept::ReadMap "read only map" returns the composition of
572  ///two
573  ///given maps. That is to say, if \c m1 is of type \c M1 and \c m2 is
574  ///of \c M2,
575  ///then for
576  ///\code
577  ///  ComposeMap<M1, M2> cm(m1,m2);
578  ///\endcode
579  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>
580  ///
581  ///Its \c Key is inherited from \c M2 and its \c Value is from
582  ///\c M1.
583  ///The \c M2::Value must be convertible to \c M1::Key.
584  ///\todo Check the requirements.
585
586  template <typename M1, typename M2>
587  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
588    const M1& m1;
589    const M2& m2;
590  public:
591    typedef MapBase<typename M2::Key, typename M1::Value> Parent;
592    typedef typename Parent::Key Key;
593    typedef typename Parent::Value Value;
594
595    ///Constructor
596    ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
597   
598    typename MapTraits<M1>::ConstReturnValue
599    operator[](Key k) const {return m1[m2[k]];}
600  };
601  ///Returns a \ref ComposeMap class
602
603  ///This function just returns a \ref ComposeMap class.
604  ///
605  ///\relates ComposeMap
606  template <typename M1, typename M2>
607  inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
608    return ComposeMap<M1, M2>(m1,m2);
609  }
610 
611  ///Combines of two maps using an STL (binary) functor.
612
613  ///Combines of two maps using an STL (binary) functor.
614  ///
615  ///
616  ///This \ref concept::ReadMap "read only map" takes two maps and a
617  ///binary functor and returns the composition of
618  ///the two
619  ///given maps unsing the functor.
620  ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
621  ///and \c f is of \c F,
622  ///then for
623  ///\code
624  ///  CombineMap<M1, M2,F,V> cm(m1,m2,f);
625  ///\endcode
626  /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
627  ///
628  ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
629  ///The \c M2::Value and \c M1::Value must be convertible to the corresponding
630  ///input parameter of \c F and the return type of \c F must be convertible
631  ///to \c V.
632  ///\todo Check the requirements.
633
634  template<typename M1, typename M2, typename F,
635           typename V = typename F::result_type,
636           typename NC = False>
637  class CombineMap : public MapBase<typename M1::Key, V> {
638    const M1& m1;
639    const M2& m2;
640    F f;
641  public:
642    typedef MapBase<typename M1::Key, V> Parent;
643    typedef typename Parent::Key Key;
644    typedef typename Parent::Value Value;
645
646    ///Constructor
647    CombineMap(const M1 &_m1,const M2 &_m2,const F &_f)
648      : m1(_m1), m2(_m2), f(_f) {};
649    Value operator[](Key k) const {return f(m1[k],m2[k]);}
650  };
651 
652  ///Returns a \ref CombineMap class
653
654  ///This function just returns a \ref CombineMap class.
655  ///
656  ///Only the first template parameter (the value type) must be given.
657  ///
658  ///For example if \c m1 and \c m2 are both \c double valued maps, then
659  ///\code
660  ///combineMap<double>(m1,m2,std::plus<double>)
661  ///\endcode
662  ///is equivalent with
663  ///\code
664  ///addMap(m1,m2)
665  ///\endcode
666  ///
667  ///\relates CombineMap
668  template<typename M1, typename M2, typename F, typename V>
669  inline CombineMap<M1, M2, F, V>
670  combineMap(const M1& m1,const M2& m2, const F& f) {
671    return CombineMap<M1, M2, F, V>(m1,m2,f);
672  }
673
674  template<typename M1, typename M2, typename F>
675  inline CombineMap<M1, M2, F, typename F::result_type>
676  combineMap(const M1& m1, const M2& m2, const F& f) {
677    return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
678  }
679
680  template<typename M1, typename M2, typename K1, typename K2, typename V>
681  inline CombineMap<M1, M2, V (*)(K1, K2), V>
682  combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
683    return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
684  }
685
686  ///Negative value of a map
687
688  ///This \ref concept::ReadMap "read only map" returns the negative
689  ///value of the
690  ///value returned by the
691  ///given map. Its \c Key and \c Value will be inherited from \c M.
692  ///The unary \c - operator must be defined for \c Value, of course.
693
694  template<typename M>
695  class NegMap : public MapBase<typename M::Key, typename M::Value> {
696    const M& m;
697  public:
698    typedef MapBase<typename M::Key, typename M::Value> Parent;
699    typedef typename Parent::Key Key;
700    typedef typename Parent::Value Value;
701
702    ///Constructor
703    NegMap(const M &_m) : m(_m) {};
704    Value operator[](Key k) const {return -m[k];}
705  };
706 
707  ///Negative value of a map
708
709  ///This \ref concept::ReadWriteMap "read-write map" returns the negative
710  ///value of the value returned by the
711  ///given map. Its \c Key and \c Value will be inherited from \c M.
712  ///The unary \c - operator must be defined for \c Value, of course.
713
714  template<typename M>
715  class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
716    M& m;
717  public:
718    typedef MapBase<typename M::Key, typename M::Value> Parent;
719    typedef typename Parent::Key Key;
720    typedef typename Parent::Value Value;
721
722    ///Constructor
723    NegWriteMap(M &_m) : m(_m) {};
724    Value operator[](Key k) const {return -m[k];}
725    void set(Key k, const Value& v) { m.set(k, -v); }
726  };
727
728  ///Returns a \ref NegMap class
729
730  ///This function just returns a \ref NegMap class.
731  ///\relates NegMap
732  template <typename M>
733  inline NegMap<M> negMap(const M &m) {
734    return NegMap<M>(m);
735  }
736
737  template <typename M>
738  inline NegWriteMap<M> negMap(M &m) {
739    return NegWriteMap<M>(m);
740  }
741
742  ///Absolute value of a map
743
744  ///This \ref concept::ReadMap "read only map" returns the absolute value
745  ///of the
746  ///value returned by the
747  ///given map. Its \c Key and \c Value will be inherited
748  ///from <tt>M</tt>. <tt>Value</tt>
749  ///must be comparable to <tt>0</tt> and the unary <tt>-</tt>
750  ///operator must be defined for it, of course.
751  ///
752  ///\bug We need a unified way to handle the situation below:
753  ///\code
754  ///  struct _UnConvertible {};
755  ///  template<class A> inline A t_abs(A a) {return _UnConvertible();}
756  ///  template<> inline int t_abs<>(int n) {return abs(n);}
757  ///  template<> inline long int t_abs<>(long int n) {return labs(n);}
758  ///  template<> inline long long int t_abs<>(long long int n) {return ::llabs(n);}
759  ///  template<> inline float t_abs<>(float n) {return fabsf(n);}
760  ///  template<> inline double t_abs<>(double n) {return fabs(n);}
761  ///  template<> inline long double t_abs<>(long double n) {return fabsl(n);}
762  ///\endcode
763 
764
765  template<typename M>
766  class AbsMap : public MapBase<typename M::Key, typename M::Value> {
767    const M& m;
768  public:
769    typedef MapBase<typename M::Key, typename M::Value> Parent;
770    typedef typename Parent::Key Key;
771    typedef typename Parent::Value Value;
772
773    ///Constructor
774    AbsMap(const M &_m) : m(_m) {};
775    Value operator[](Key k) const {
776      Value tmp = m[k];
777      return tmp >= 0 ? tmp : -tmp;
778    }
779
780  };
781 
782  ///Returns a \ref AbsMap class
783
784  ///This function just returns a \ref AbsMap class.
785  ///\relates AbsMap
786  template<typename M>
787  inline AbsMap<M> absMap(const M &m) {
788    return AbsMap<M>(m);
789  }
790
791  ///Converts an STL style functor to a map
792
793  ///This \ref concept::ReadMap "read only map" returns the value
794  ///of a
795  ///given map.
796  ///
797  ///Template parameters \c K and \c V will become its
798  ///\c Key and \c Value. They must be given explicitely
799  ///because a functor does not provide such typedefs.
800  ///
801  ///Parameter \c F is the type of the used functor.
802 
803
804  template<typename F,
805           typename K = typename F::argument_type,
806           typename V = typename F::result_type,
807           typename NC = False>
808  class FunctorMap : public MapBase<K, V> {
809    F f;
810  public:
811    typedef MapBase<K, V> Parent;
812    typedef typename Parent::Key Key;
813    typedef typename Parent::Value Value;
814
815    ///Constructor
816    FunctorMap(const F &_f) : f(_f) {}
817
818    Value operator[](Key k) const { return f(k);}
819  };
820 
821  ///Returns a \ref FunctorMap class
822
823  ///This function just returns a \ref FunctorMap class.
824  ///
825  ///The third template parameter isn't necessary to be given.
826  ///\relates FunctorMap
827  template<typename K, typename V, typename F> inline
828  FunctorMap<F, K, V> functorMap(const F &f) {
829    return FunctorMap<F, K, V>(f);
830  }
831
832  template <typename F> inline
833  FunctorMap<F, typename F::argument_type, typename F::result_type>
834  functorMap(const F &f) {
835    return FunctorMap<F, typename F::argument_type,
836      typename F::result_type>(f);
837  }
838
839  template <typename K, typename V> inline
840  FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
841    return FunctorMap<V (*)(K), K, V>(f);
842  }
843
844
845  ///Converts a map to an STL style (unary) functor
846
847  ///This class Converts a map to an STL style (unary) functor.
848  ///that is it provides an <tt>operator()</tt> to read its values.
849  ///
850  ///For the sake of convenience it also works as
851  ///a ususal \ref concept::ReadMap "readable map",
852  ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
853
854  template <typename M>
855  class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
856    const M& m;
857  public:
858    typedef MapBase<typename M::Key, typename M::Value> Parent;
859    typedef typename Parent::Key Key;
860    typedef typename Parent::Value Value;
861
862    ///\e
863    typedef typename M::Key argument_type;
864    ///\e
865    typedef typename M::Value result_type;
866
867    ///Constructor
868    MapFunctor(const M &_m) : m(_m) {};
869    ///Returns a value of the map
870    Value operator()(Key k) const {return m[k];}
871    ///\e
872    Value operator[](Key k) const {return m[k];}
873  };
874 
875  ///Returns a \ref MapFunctor class
876
877  ///This function just returns a \ref MapFunctor class.
878  ///\relates MapFunctor
879  template<typename M>
880  inline MapFunctor<M> mapFunctor(const M &m) {
881    return MapFunctor<M>(m);
882  }
883
884  ///Applies all map setting operations to two maps
885
886  ///This map has two \ref concept::ReadMap "readable map"
887  ///parameters and each read request will be passed just to the
888  ///first map. This class is the just readable map type of the ForkWriteMap.
889  ///
890  ///The \c Key and \c Value will be inherited from \c M1.
891  ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
892
893  template<typename  M1, typename M2>
894  class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
895    const M1& m1;
896    const M2& m2;
897  public:
898    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
899    typedef typename Parent::Key Key;
900    typedef typename Parent::Value Value;
901
902    ///Constructor
903    ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {};
904    Value operator[](Key k) const {return m1[k];}
905  };
906
907
908  ///Applies all map setting operations to two maps
909
910  ///This map has two \ref concept::WriteMap "writable map"
911  ///parameters and each write request will be passed to both of them.
912  ///If \c M1 is also \ref concept::ReadMap "readable",
913  ///then the read operations will return the
914  ///corresponding values of \c M1.
915  ///
916  ///The \c Key and \c Value will be inherited from \c M1.
917  ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
918
919  template<typename  M1, typename M2>
920  class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
921    M1& m1;
922    M2& m2;
923  public:
924    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
925    typedef typename Parent::Key Key;
926    typedef typename Parent::Value Value;
927
928    ///Constructor
929    ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {};
930    Value operator[](Key k) const {return m1[k];}
931    void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
932  };
933 
934  ///Returns an \ref ForkMap class
935
936  ///This function just returns an \ref ForkMap class.
937  ///\todo How to call these type of functions?
938  ///
939  ///\relates ForkMap
940  ///\todo Wrong scope in Doxygen when \c \\relates is used
941  template <typename M1, typename M2>
942  inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) {
943    return ForkMap<M1, M2>(m1,m2);
944  }
945
946  template <typename M1, typename M2>
947  inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) {
948    return ForkWriteMap<M1, M2>(m1,m2);
949  }
950
951
952 
953  /* ************* BOOL MAPS ******************* */
954 
955  ///Logical 'not' of a map
956 
957  ///This bool \ref concept::ReadMap "read only map" returns the
958  ///logical negation of
959  ///value returned by the
960  ///given map. Its \c Key and will be inherited from \c M,
961  ///its Value is <tt>bool</tt>.
962
963  template <typename M>
964  class NotMap : public MapBase<typename M::Key, bool> {
965    const M& m;
966  public:
967    typedef MapBase<typename M::Key, bool> Parent;
968    typedef typename Parent::Key Key;
969    typedef typename Parent::Value Value;
970
971    /// Constructor
972    NotMap(const M &_m) : m(_m) {};
973    Value operator[](Key k) const {return !m[k];}
974  };
975
976  ///Logical 'not' of a map with writing possibility
977 
978  ///This bool \ref concept::ReadWriteMap "read-write map" returns the
979  ///logical negation of value returned by the given map. It is setted
980  ///then the negation of the value be setted to the original map.
981  ///Its \c Key and will be inherited from \c M,
982  ///its Value is <tt>bool</tt>.
983  template <typename M>
984  class NotWriteMap : public MapBase<typename M::Key, bool> {
985    M& m;
986  public:
987    typedef MapBase<typename M::Key, bool> Parent;
988    typedef typename Parent::Key Key;
989    typedef typename Parent::Value Value;
990
991    /// Constructor
992    NotWriteMap(M &_m) : m(_m) {};
993    Value operator[](Key k) const {return !m[k];}
994    void set(Key k, bool v) { m.set(k, !v); }
995  };
996 
997  ///Returns a \ref NotMap class
998 
999  ///This function just returns a \ref NotMap class.
1000  ///\relates NotMap
1001  template <typename M>
1002  inline NotMap<M> notMap(const M &m) {
1003    return NotMap<M>(m);
1004  }
1005
1006  template <typename M>
1007  inline NotWriteMap<M> notMap(M &m) {
1008    return NotWriteMap<M>(m);
1009  }
1010
1011  /// \brief Writable bool map for store each true assigned elements.
1012  ///
1013  /// Writable bool map for store each true assigned elements. It will
1014  /// copies all the true setted keys to the given iterator.
1015  ///
1016  /// \note The container of the iterator should contain for each element.
1017  template <typename _Iterator>
1018  class StoreBoolMap {
1019  public:
1020    typedef _Iterator Iterator;
1021
1022    typedef typename std::iterator_traits<Iterator>::value_type Key;
1023    typedef bool Value;
1024
1025    /// Constructor
1026    StoreBoolMap(Iterator it) : _begin(it), _end(it) {}
1027
1028    /// Gives back the given first setted iterator.
1029    Iterator begin() const {
1030      return _begin;
1031    }
1032 
1033    /// Gives back the iterator after the last setted.
1034    Iterator end() const {
1035      return _end;
1036    }
1037
1038    /// Setter function of the map
1039    void set(const Key& key, Value value) {
1040      if (value) {
1041        *_end++ = key;
1042      }
1043    }
1044   
1045  private:
1046    Iterator _begin, _end;
1047  };
1048
1049  /// \brief Writable bool map for store each true assigned elements in
1050  /// a back insertable container.
1051  ///
1052  /// Writable bool map for store each true assigned elements in a back
1053  /// insertable container. It will push back all the true setted keys into
1054  /// the container.
1055  template <typename Container>
1056  class BackInserterBoolMap {
1057  public:
1058    typedef typename Container::value_type Key;
1059    typedef bool Value;
1060
1061    /// Constructor
1062    BackInserterBoolMap(Container& _container) : container(_container) {}
1063
1064    /// Setter function of the map
1065    void set(const Key& key, Value value) {
1066      if (value) {
1067        container.push_back(key);
1068      }
1069    }
1070   
1071  private:
1072    Container& container;   
1073  };
1074
1075  /// \brief Writable bool map for store each true assigned elements in
1076  /// a front insertable container.
1077  ///
1078  /// Writable bool map for store each true assigned elements in a front
1079  /// insertable container. It will push front all the true setted keys into
1080  /// the container.
1081  template <typename Container>
1082  class FrontInserterBoolMap {
1083  public:
1084    typedef typename Container::value_type Key;
1085    typedef bool Value;
1086
1087    /// Constructor
1088    FrontInserterBoolMap(Container& _container) : container(_container) {}
1089
1090    /// Setter function of the map
1091    void set(const Key& key, Value value) {
1092      if (value) {
1093        container.push_front(key);
1094      }
1095    }
1096   
1097  private:
1098    Container& container;   
1099  };
1100
1101  /// \brief Writable bool map for store each true assigned elements in
1102  /// an insertable container.
1103  ///
1104  /// Writable bool map for store each true assigned elements in an
1105  /// insertable container. It will insert all the true setted keys into
1106  /// the container.
1107  template <typename Container>
1108  class InserterBoolMap {
1109  public:
1110    typedef typename Container::value_type Key;
1111    typedef bool Value;
1112
1113    /// Constructor
1114    InserterBoolMap(Container& _container) : container(_container) {}
1115
1116    /// Setter function of the map
1117    void set(const Key& key, Value value) {
1118      if (value) {
1119        container.insert(key);
1120      }
1121    }
1122   
1123  private:
1124    Container& container;   
1125  };
1126
1127  /// \brief Fill the true setted elements with a given value.
1128  ///
1129  /// Writable bool map for fill the true setted elements with a given value.
1130  /// The value can be setted
1131  /// the container.
1132  template <typename Map>
1133  class FillBoolMap {
1134  public:
1135    typedef typename Map::Key Key;
1136    typedef bool Value;
1137
1138    /// Constructor
1139    FillBoolMap(Map& _map, const typename Map::Value& _fill)
1140      : map(_map), fill(_fill) {}
1141
1142    /// Constructor
1143    FillBoolMap(Map& _map)
1144      : map(_map), fill() {}
1145
1146    /// Gives back the current fill value
1147    typename Map::Value fillValue() const {
1148      return fill;
1149    }
1150
1151    /// Sets the current fill value
1152    void fillValue(const typename Map::Value& _fill) {
1153      fill = _fill;
1154    }
1155
1156    /// Setter function of the map
1157    void set(const Key& key, Value value) {
1158      if (value) {
1159        map.set(key, fill);
1160      }
1161    }
1162   
1163  private:
1164    Map& map;
1165    typename Map::Value fill;
1166  };
1167
1168
1169  /// \brief Writable bool map which stores for each true assigned elements 
1170  /// the setting order number.
1171  ///
1172  /// Writable bool map which stores for each true assigned elements 
1173  /// the setting order number.
1174  template <typename Map>
1175  class SettingOrderBoolMap {
1176  public:
1177    typedef typename Map::Key Key;
1178    typedef bool Value;
1179
1180    /// Constructor
1181    SettingOrderBoolMap(Map& _map)
1182      : map(_map), counter(0) {}
1183
1184    /// Number of setted keys.
1185    int num() const {
1186      return counter;
1187    }
1188
1189    /// Setter function of the map
1190    void set(const Key& key, Value value) {
1191      if (value) {
1192        map.set(key, counter++);
1193      }
1194    }
1195   
1196  private:
1197    Map& map;
1198    int counter;
1199  };
1200
1201  /// @}
1202}
1203
1204#endif // LEMON_MAPS_H
Note: See TracBrowser for help on using the repository browser.