COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/maps.h @ 2190:dd887831e9c1

Last change on this file since 2190:dd887831e9c1 was 2093:ff241247e157, checked in by Balazs Dezso, 18 years ago

Erasing some code from the examples

File size: 38.7 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#include <functional>
24
25#include <lemon/bits/utility.h>
26#include <lemon/bits/traits.h>
27
28///\file
29///\ingroup maps
30///\brief Miscellaneous property maps
31///
32///\todo This file has the same name as the concept file in concept/,
33/// and this is not easily detectable in docs...
34
35#include <map>
36
37namespace lemon {
38
39  /// \addtogroup maps
40  /// @{
41
42  /// Base class of maps.
43
44  /// Base class of maps.
45  /// It provides the necessary <tt>typedef</tt>s required by the map concept.
46  template<typename K, typename T>
47  class MapBase {
48  public:
49    ///\e
50    typedef K Key;
51    ///\e
52    typedef T Value;
53  };
54
55  /// Null map. (a.k.a. DoNothingMap)
56
57  /// If you have to provide a map only for its type definitions,
58  /// or if you have to provide a writable map, but
59  /// data written to it will sent to <tt>/dev/null</tt>...
60  template<typename K, typename T>
61  class NullMap : public MapBase<K, T> {
62  public:
63    typedef MapBase<K, T> Parent;
64    typedef typename Parent::Key Key;
65    typedef typename Parent::Value Value;
66   
67    /// Gives back a default constructed element.
68    T operator[](const K&) const { return T(); }
69    /// Absorbs the value.
70    void set(const K&, const T&) {}
71  };
72
73  template <typename K, typename V>
74  NullMap<K, V> nullMap() {
75    return NullMap<K, V>();
76  }
77
78
79  /// Constant map.
80
81  /// This is a readable map which assigns a specified value to each key.
82  /// In other aspects it is equivalent to the \ref NullMap.
83  /// \todo set could be used to set the value.
84  template<typename K, typename T>
85  class ConstMap : public MapBase<K, T> {
86  private:
87    T v;
88  public:
89
90    typedef MapBase<K, T> Parent;
91    typedef typename Parent::Key Key;
92    typedef typename Parent::Value Value;
93
94    /// Default constructor
95
96    /// The value of the map will be uninitialized.
97    /// (More exactly it will be default constructed.)
98    ConstMap() {}
99    ///\e
100
101    /// \param _v The initial value of the map.
102    ///
103    ConstMap(const T &_v) : v(_v) {}
104
105    T operator[](const K&) const { return v; }
106    void set(const K&, const T&) {}
107
108    template<typename T1>
109    struct rebind {
110      typedef ConstMap<K, T1> other;
111    };
112
113    template<typename T1>
114    ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
115  };
116
117  ///Returns a \ref ConstMap class
118
119  ///This function just returns a \ref ConstMap class.
120  ///\relates ConstMap
121  template<typename K, typename V>
122  inline ConstMap<K, V> constMap(const V &v) {
123    return ConstMap<K, V>(v);
124  }
125
126
127  //\todo to document later
128  template<typename T, T v>
129  struct Const { };
130
131  //\todo to document later
132  template<typename K, typename V, V v>
133  class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
134  public:
135    typedef MapBase<K, V> Parent;
136    typedef typename Parent::Key Key;
137    typedef typename Parent::Value Value;
138
139    ConstMap() { }
140    V operator[](const K&) const { return v; }
141    void set(const K&, const V&) { }
142  };
143
144  ///Returns a \ref ConstMap class
145
146  ///This function just returns a \ref ConstMap class.
147  ///\relates ConstMap
148  template<typename K, typename V, V v>
149  inline ConstMap<K, Const<V, v> > constMap() {
150    return ConstMap<K, Const<V, v> >();
151  }
152
153  /// \c std::map wrapper
154
155  /// This is essentially a wrapper for \c std::map. With addition that
156  /// you can specify a default value different from \c Value() .
157  ///
158  /// \todo Provide allocator parameter...
159  template <typename K, typename T, typename Compare = std::less<K> >
160  class StdMap : public std::map<K, T, Compare> {
161    typedef std::map<K, T, Compare> parent;
162    T v;
163    typedef typename parent::value_type PairType;
164
165  public:
166    ///\e
167    typedef K Key;
168    ///\e
169    typedef T Value;
170    ///\e
171    typedef T& Reference;
172    ///\e
173    typedef const T& ConstReference;
174
175
176    StdMap() : v() {}
177    /// Constructor with specified default value
178    StdMap(const T& _v) : v(_v) {}
179
180    /// \brief Constructs the map from an appropriate std::map.
181    ///
182    /// \warning Inefficient: copies the content of \c m !
183    StdMap(const parent &m) : parent(m) {}
184    /// \brief Constructs the map from an appropriate std::map, and explicitly
185    /// specifies a default value.
186    ///
187    /// \warning Inefficient: copies the content of \c m !
188    StdMap(const parent &m, const T& _v) : parent(m), v(_v) {}
189   
190    template<typename T1, typename Comp1>
191    StdMap(const StdMap<Key, T1,Comp1> &m, const T &_v) {
192      //FIXME;
193    }
194
195    Reference operator[](const Key &k) {
196      return insert(PairType(k,v)).first -> second;
197    }
198
199    ConstReference operator[](const Key &k) const {
200      typename parent::iterator i = lower_bound(k);
201      if (i == parent::end() || parent::key_comp()(k, (*i).first))
202        return v;
203      return (*i).second;
204    }
205    void set(const Key &k, const T &t) {
206      parent::operator[](k) = t;
207    }
208
209    /// Changes the default value of the map.
210    /// \return Returns the previous default value.
211    ///
212    /// \warning The value of some keys (which has already been queried, but
213    /// the value has been unchanged from the default) may change!
214    T setDefault(const T &_v) { T old=v; v=_v; return old; }
215
216    template<typename T1>
217    struct rebind {
218      typedef StdMap<Key, T1,Compare> other;
219    };
220  };
221
222  /// @}
223
224  /// \addtogroup map_adaptors
225  /// @{
226
227  /// \brief Identity mapping.
228  ///
229  /// This mapping gives back the given key as value without any
230  /// modification.
231  template <typename T>
232  class IdentityMap : public MapBase<T, T> {
233  public:
234    typedef MapBase<T, T> Parent;
235    typedef typename Parent::Key Key;
236    typedef typename Parent::Value Value;
237
238    const T& operator[](const T& t) const {
239      return t;
240    }
241  };
242
243  ///Returns an \ref IdentityMap class
244
245  ///This function just returns an \ref IdentityMap class.
246  ///\relates IdentityMap
247  template<typename T>
248  inline IdentityMap<T> identityMap() {
249    return IdentityMap<T>();
250  }
251 
252
253  ///Convert the \c Value of a map to another type.
254
255  ///This \ref concept::ReadMap "read only map"
256  ///converts the \c Value of a maps to type \c T.
257  ///Its \c Key is inherited from \c M.
258  template <typename M, typename T>
259  class ConvertMap : public MapBase<typename M::Key, T> {
260    const M& m;
261  public:
262    typedef MapBase<typename M::Key, T> Parent;
263    typedef typename Parent::Key Key;
264    typedef typename Parent::Value Value;
265
266    ///Constructor
267
268    ///Constructor
269    ///\param _m is the underlying map
270    ConvertMap(const M &_m) : m(_m) {};
271
272    /// \brief The subscript operator.
273    ///
274    /// The subscript operator.
275    /// \param k The key
276    /// \return The target of the edge
277    Value operator[](const Key& k) const {return m[k];}
278  };
279 
280  ///Returns an \ref ConvertMap class
281
282  ///This function just returns an \ref ConvertMap class.
283  ///\relates ConvertMap
284  ///\todo The order of the template parameters are changed.
285  template<typename T, typename M>
286  inline ConvertMap<M, T> convertMap(const M &m) {
287    return ConvertMap<M, T>(m);
288  }
289
290  ///Sum of two maps
291
292  ///This \ref concept::ReadMap "read only map" returns the sum of the two
293  ///given maps. Its \c Key and \c Value will be inherited from \c M1.
294  ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
295
296  template<typename M1, typename M2>
297  class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
298    const M1& m1;
299    const M2& m2;
300
301  public:
302    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
303    typedef typename Parent::Key Key;
304    typedef typename Parent::Value Value;
305
306    ///Constructor
307    AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
308    Value operator[](Key k) const {return m1[k]+m2[k];}
309  };
310 
311  ///Returns an \ref AddMap class
312
313  ///This function just returns an \ref AddMap class.
314  ///\todo How to call these type of functions?
315  ///
316  ///\relates AddMap
317  ///\todo Wrong scope in Doxygen when \c \\relates is used
318  template<typename M1, typename M2>
319  inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
320    return AddMap<M1, M2>(m1,m2);
321  }
322
323  ///Shift a map with a constant.
324
325  ///This \ref concept::ReadMap "read only map" returns the sum of the
326  ///given map and a constant value.
327  ///Its \c Key and \c Value is inherited from \c M.
328  ///
329  ///Actually,
330  ///\code
331  ///  ShiftMap<X> sh(x,v);
332  ///\endcode
333  ///is equivalent with
334  ///\code
335  ///  ConstMap<X::Key, X::Value> c_tmp(v);
336  ///  AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
337  ///\endcode
338  template<typename M, typename C = typename M::Value>
339  class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
340    const M& m;
341    C v;
342  public:
343    typedef MapBase<typename M::Key, typename M::Value> Parent;
344    typedef typename Parent::Key Key;
345    typedef typename Parent::Value Value;
346
347    ///Constructor
348
349    ///Constructor
350    ///\param _m is the undelying map
351    ///\param _v is the shift value
352    ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
353    Value operator[](Key k) const {return m[k] + v;}
354  };
355
356  ///Shift a map with a constant.
357
358  ///This \ref concept::ReadWriteMap "read-write map" returns the sum of the
359  ///given map and a constant value. It makes also possible to write the map.
360  ///Its \c Key and \c Value is inherited from \c M.
361  ///
362  ///Actually,
363  ///\code
364  ///  ShiftMap<X> sh(x,v);
365  ///\endcode
366  ///is equivalent with
367  ///\code
368  ///  ConstMap<X::Key, X::Value> c_tmp(v);
369  ///  AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
370  ///\endcode
371  template<typename M, typename C = typename M::Value>
372  class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
373    M& m;
374    C v;
375  public:
376    typedef MapBase<typename M::Key, typename M::Value> Parent;
377    typedef typename Parent::Key Key;
378    typedef typename Parent::Value Value;
379
380    ///Constructor
381
382    ///Constructor
383    ///\param _m is the undelying map
384    ///\param _v is the shift value
385    ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
386    Value operator[](Key k) const {return m[k] + v;}
387    void set(Key k, const Value& c) { m.set(k, c - v); }
388  };
389 
390  ///Returns an \ref ShiftMap class
391
392  ///This function just returns an \ref ShiftMap class.
393  ///\relates ShiftMap
394  ///\todo A better name is required.
395  template<typename M, typename C>
396  inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
397    return ShiftMap<M, C>(m,v);
398  }
399
400  template<typename M, typename C>
401  inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) {
402    return ShiftWriteMap<M, C>(m,v);
403  }
404
405  ///Difference of two maps
406
407  ///This \ref concept::ReadMap "read only map" returns the difference
408  ///of the values of the two
409  ///given maps. Its \c Key and \c Value will be inherited from \c M1.
410  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
411
412  template<typename M1, typename M2>
413  class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
414    const M1& m1;
415    const M2& m2;
416  public:
417    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
418    typedef typename Parent::Key Key;
419    typedef typename Parent::Value Value;
420
421    ///Constructor
422    SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
423    Value operator[](Key k) const {return m1[k]-m2[k];}
424  };
425 
426  ///Returns a \ref SubMap class
427
428  ///This function just returns a \ref SubMap class.
429  ///
430  ///\relates SubMap
431  template<typename M1, typename M2>
432  inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
433    return SubMap<M1, M2>(m1, m2);
434  }
435
436  ///Product of two maps
437
438  ///This \ref concept::ReadMap "read only map" returns the product of the
439  ///values of the two
440  ///given
441  ///maps. Its \c Key and \c Value will be inherited from \c M1.
442  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
443
444  template<typename M1, typename M2>
445  class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
446    const M1& m1;
447    const M2& m2;
448  public:
449    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
450    typedef typename Parent::Key Key;
451    typedef typename Parent::Value Value;
452
453    ///Constructor
454    MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
455    Value operator[](Key k) const {return m1[k]*m2[k];}
456  };
457 
458  ///Returns a \ref MulMap class
459
460  ///This function just returns a \ref MulMap class.
461  ///\relates MulMap
462  template<typename M1, typename M2>
463  inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
464    return MulMap<M1, M2>(m1,m2);
465  }
466 
467  ///Scales a maps with a constant.
468
469  ///This \ref concept::ReadMap "read only map" returns the value of the
470  ///given map multiplied from the left side with a constant value.
471  ///Its \c Key and \c Value is inherited from \c M.
472  ///
473  ///Actually,
474  ///\code
475  ///  ScaleMap<X> sc(x,v);
476  ///\endcode
477  ///is equivalent with
478  ///\code
479  ///  ConstMap<X::Key, X::Value> c_tmp(v);
480  ///  MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
481  ///\endcode
482  template<typename M, typename C = typename M::Value>
483  class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
484    const M& m;
485    C v;
486  public:
487    typedef MapBase<typename M::Key, typename M::Value> Parent;
488    typedef typename Parent::Key Key;
489    typedef typename Parent::Value Value;
490
491    ///Constructor
492
493    ///Constructor
494    ///\param _m is the undelying map
495    ///\param _v is the scaling value
496    ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
497    Value operator[](Key k) const {return v * m[k];}
498  };
499
500  ///Scales a maps with a constant.
501
502  ///This \ref concept::ReadWriteMap "read-write map" returns the value of the
503  ///given map multiplied from the left side with a constant value. It can
504  ///be used as write map also if the given multiplier is not zero.
505  ///Its \c Key and \c Value is inherited from \c M.
506  template<typename M, typename C = typename M::Value>
507  class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
508    M& m;
509    C v;
510  public:
511    typedef MapBase<typename M::Key, typename M::Value> Parent;
512    typedef typename Parent::Key Key;
513    typedef typename Parent::Value Value;
514
515    ///Constructor
516
517    ///Constructor
518    ///\param _m is the undelying map
519    ///\param _v is the scaling value
520    ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
521    Value operator[](Key k) const {return v * m[k];}
522    void set(Key k, const Value& c) { m.set(k, c / v);}
523  };
524 
525  ///Returns an \ref ScaleMap class
526
527  ///This function just returns an \ref ScaleMap class.
528  ///\relates ScaleMap
529  ///\todo A better name is required.
530  template<typename M, typename C>
531  inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
532    return ScaleMap<M, C>(m,v);
533  }
534
535  template<typename M, typename C>
536  inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) {
537    return ScaleWriteMap<M, C>(m,v);
538  }
539
540  ///Quotient of two maps
541
542  ///This \ref concept::ReadMap "read only map" returns the quotient of the
543  ///values of the two
544  ///given maps. Its \c Key and \c Value will be inherited from \c M1.
545  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
546
547  template<typename M1, typename M2>
548  class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
549    const M1& m1;
550    const M2& m2;
551  public:
552    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
553    typedef typename Parent::Key Key;
554    typedef typename Parent::Value Value;
555
556    ///Constructor
557    DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
558    Value operator[](Key k) const {return m1[k]/m2[k];}
559  };
560 
561  ///Returns a \ref DivMap class
562
563  ///This function just returns a \ref DivMap class.
564  ///\relates DivMap
565  template<typename M1, typename M2>
566  inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
567    return DivMap<M1, M2>(m1,m2);
568  }
569 
570  ///Composition of two maps
571
572  ///This \ref concept::ReadMap "read only map" returns the composition of
573  ///two
574  ///given maps. That is to say, if \c m1 is of type \c M1 and \c m2 is
575  ///of \c M2,
576  ///then for
577  ///\code
578  ///  ComposeMap<M1, M2> cm(m1,m2);
579  ///\endcode
580  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>
581  ///
582  ///Its \c Key is inherited from \c M2 and its \c Value is from
583  ///\c M1.
584  ///The \c M2::Value must be convertible to \c M1::Key.
585  ///\todo Check the requirements.
586
587  template <typename M1, typename M2>
588  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
589    const M1& m1;
590    const M2& m2;
591  public:
592    typedef MapBase<typename M2::Key, typename M1::Value> Parent;
593    typedef typename Parent::Key Key;
594    typedef typename Parent::Value Value;
595
596    ///Constructor
597    ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
598   
599    typename MapTraits<M1>::ConstReturnValue
600    operator[](Key k) const {return m1[m2[k]];}
601  };
602  ///Returns a \ref ComposeMap class
603
604  ///This function just returns a \ref ComposeMap class.
605  ///
606  ///\relates ComposeMap
607  template <typename M1, typename M2>
608  inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
609    return ComposeMap<M1, M2>(m1,m2);
610  }
611 
612  ///Combines of two maps using an STL (binary) functor.
613
614  ///Combines of two maps using an STL (binary) functor.
615  ///
616  ///
617  ///This \ref concept::ReadMap "read only map" takes two maps and a
618  ///binary functor and returns the composition of
619  ///the two
620  ///given maps unsing the functor.
621  ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
622  ///and \c f is of \c F,
623  ///then for
624  ///\code
625  ///  CombineMap<M1, M2,F,V> cm(m1,m2,f);
626  ///\endcode
627  /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
628  ///
629  ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
630  ///The \c M2::Value and \c M1::Value must be convertible to the corresponding
631  ///input parameter of \c F and the return type of \c F must be convertible
632  ///to \c V.
633  ///\todo Check the requirements.
634
635  template<typename M1, typename M2, typename F,
636           typename V = typename F::result_type,
637           typename NC = False>
638  class CombineMap : public MapBase<typename M1::Key, V> {
639    const M1& m1;
640    const M2& m2;
641    F f;
642  public:
643    typedef MapBase<typename M1::Key, V> Parent;
644    typedef typename Parent::Key Key;
645    typedef typename Parent::Value Value;
646
647    ///Constructor
648    CombineMap(const M1 &_m1,const M2 &_m2,const F &_f)
649      : m1(_m1), m2(_m2), f(_f) {};
650    Value operator[](Key k) const {return f(m1[k],m2[k]);}
651  };
652 
653  ///Returns a \ref CombineMap class
654
655  ///This function just returns a \ref CombineMap class.
656  ///
657  ///Only the first template parameter (the value type) must be given.
658  ///
659  ///For example if \c m1 and \c m2 are both \c double valued maps, then
660  ///\code
661  ///combineMap<double>(m1,m2,std::plus<double>)
662  ///\endcode
663  ///is equivalent with
664  ///\code
665  ///addMap(m1,m2)
666  ///\endcode
667  ///
668  ///\relates CombineMap
669  template<typename M1, typename M2, typename F, typename V>
670  inline CombineMap<M1, M2, F, V>
671  combineMap(const M1& m1,const M2& m2, const F& f) {
672    return CombineMap<M1, M2, F, V>(m1,m2,f);
673  }
674
675  template<typename M1, typename M2, typename F>
676  inline CombineMap<M1, M2, F, typename F::result_type>
677  combineMap(const M1& m1, const M2& m2, const F& f) {
678    return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
679  }
680
681  template<typename M1, typename M2, typename K1, typename K2, typename V>
682  inline CombineMap<M1, M2, V (*)(K1, K2), V>
683  combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
684    return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
685  }
686
687  ///Negative value of a map
688
689  ///This \ref concept::ReadMap "read only map" returns the negative
690  ///value of the
691  ///value returned by the
692  ///given map. Its \c Key and \c Value will be inherited from \c M.
693  ///The unary \c - operator must be defined for \c Value, of course.
694
695  template<typename M>
696  class NegMap : public MapBase<typename M::Key, typename M::Value> {
697    const M& m;
698  public:
699    typedef MapBase<typename M::Key, typename M::Value> Parent;
700    typedef typename Parent::Key Key;
701    typedef typename Parent::Value Value;
702
703    ///Constructor
704    NegMap(const M &_m) : m(_m) {};
705    Value operator[](Key k) const {return -m[k];}
706  };
707 
708  ///Negative value of a map
709
710  ///This \ref concept::ReadWriteMap "read-write map" returns the negative
711  ///value of the value returned by the
712  ///given map. Its \c Key and \c Value will be inherited from \c M.
713  ///The unary \c - operator must be defined for \c Value, of course.
714
715  template<typename M>
716  class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
717    M& m;
718  public:
719    typedef MapBase<typename M::Key, typename M::Value> Parent;
720    typedef typename Parent::Key Key;
721    typedef typename Parent::Value Value;
722
723    ///Constructor
724    NegWriteMap(M &_m) : m(_m) {};
725    Value operator[](Key k) const {return -m[k];}
726    void set(Key k, const Value& v) { m.set(k, -v); }
727  };
728
729  ///Returns a \ref NegMap class
730
731  ///This function just returns a \ref NegMap class.
732  ///\relates NegMap
733  template <typename M>
734  inline NegMap<M> negMap(const M &m) {
735    return NegMap<M>(m);
736  }
737
738  template <typename M>
739  inline NegWriteMap<M> negMap(M &m) {
740    return NegWriteMap<M>(m);
741  }
742
743  ///Absolute value of a map
744
745  ///This \ref concept::ReadMap "read only map" returns the absolute value
746  ///of the
747  ///value returned by the
748  ///given map. Its \c Key and \c Value will be inherited
749  ///from <tt>M</tt>. <tt>Value</tt>
750  ///must be comparable to <tt>0</tt> and the unary <tt>-</tt>
751  ///operator must be defined for it, of course.
752  ///
753  ///\bug We need a unified way to handle the situation below:
754  ///\code
755  ///  struct _UnConvertible {};
756  ///  template<class A> inline A t_abs(A a) {return _UnConvertible();}
757  ///  template<> inline int t_abs<>(int n) {return abs(n);}
758  ///  template<> inline long int t_abs<>(long int n) {return labs(n);}
759  ///  template<> inline long long int t_abs<>(long long int n) {return ::llabs(n);}
760  ///  template<> inline float t_abs<>(float n) {return fabsf(n);}
761  ///  template<> inline double t_abs<>(double n) {return fabs(n);}
762  ///  template<> inline long double t_abs<>(long double n) {return fabsl(n);}
763  ///\endcode
764 
765
766  template<typename M>
767  class AbsMap : public MapBase<typename M::Key, typename M::Value> {
768    const M& m;
769  public:
770    typedef MapBase<typename M::Key, typename M::Value> Parent;
771    typedef typename Parent::Key Key;
772    typedef typename Parent::Value Value;
773
774    ///Constructor
775    AbsMap(const M &_m) : m(_m) {};
776    Value operator[](Key k) const {
777      Value tmp = m[k];
778      return tmp >= 0 ? tmp : -tmp;
779    }
780
781  };
782 
783  ///Returns a \ref AbsMap class
784
785  ///This function just returns a \ref AbsMap class.
786  ///\relates AbsMap
787  template<typename M>
788  inline AbsMap<M> absMap(const M &m) {
789    return AbsMap<M>(m);
790  }
791
792  ///Converts an STL style functor to a map
793
794  ///This \ref concept::ReadMap "read only map" returns the value
795  ///of a
796  ///given map.
797  ///
798  ///Template parameters \c K and \c V will become its
799  ///\c Key and \c Value. They must be given explicitely
800  ///because a functor does not provide such typedefs.
801  ///
802  ///Parameter \c F is the type of the used functor.
803 
804
805  template<typename F,
806           typename K = typename F::argument_type,
807           typename V = typename F::result_type,
808           typename NC = False>
809  class FunctorMap : public MapBase<K, V> {
810    F f;
811  public:
812    typedef MapBase<K, V> Parent;
813    typedef typename Parent::Key Key;
814    typedef typename Parent::Value Value;
815
816    ///Constructor
817    FunctorMap(const F &_f) : f(_f) {}
818
819    Value operator[](Key k) const { return f(k);}
820  };
821 
822  ///Returns a \ref FunctorMap class
823
824  ///This function just returns a \ref FunctorMap class.
825  ///
826  ///The third template parameter isn't necessary to be given.
827  ///\relates FunctorMap
828  template<typename K, typename V, typename F> inline
829  FunctorMap<F, K, V> functorMap(const F &f) {
830    return FunctorMap<F, K, V>(f);
831  }
832
833  template <typename F> inline
834  FunctorMap<F, typename F::argument_type, typename F::result_type>
835  functorMap(const F &f) {
836    return FunctorMap<F, typename F::argument_type,
837      typename F::result_type>(f);
838  }
839
840  template <typename K, typename V> inline
841  FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
842    return FunctorMap<V (*)(K), K, V>(f);
843  }
844
845
846  ///Converts a map to an STL style (unary) functor
847
848  ///This class Converts a map to an STL style (unary) functor.
849  ///that is it provides an <tt>operator()</tt> to read its values.
850  ///
851  ///For the sake of convenience it also works as
852  ///a ususal \ref concept::ReadMap "readable map",
853  ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
854
855  template <typename M>
856  class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
857    const M& m;
858  public:
859    typedef MapBase<typename M::Key, typename M::Value> Parent;
860    typedef typename Parent::Key Key;
861    typedef typename Parent::Value Value;
862
863    ///\e
864    typedef typename M::Key argument_type;
865    ///\e
866    typedef typename M::Value result_type;
867
868    ///Constructor
869    MapFunctor(const M &_m) : m(_m) {};
870    ///Returns a value of the map
871    Value operator()(Key k) const {return m[k];}
872    ///\e
873    Value operator[](Key k) const {return m[k];}
874  };
875 
876  ///Returns a \ref MapFunctor class
877
878  ///This function just returns a \ref MapFunctor class.
879  ///\relates MapFunctor
880  template<typename M>
881  inline MapFunctor<M> mapFunctor(const M &m) {
882    return MapFunctor<M>(m);
883  }
884
885  ///Applies all map setting operations to two maps
886
887  ///This map has two \ref concept::ReadMap "readable map"
888  ///parameters and each read request will be passed just to the
889  ///first map. This class is the just readable map type of the ForkWriteMap.
890  ///
891  ///The \c Key and \c Value will be inherited from \c M1.
892  ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
893
894  template<typename  M1, typename M2>
895  class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
896    const M1& m1;
897    const M2& m2;
898  public:
899    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
900    typedef typename Parent::Key Key;
901    typedef typename Parent::Value Value;
902
903    ///Constructor
904    ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {};
905    Value operator[](Key k) const {return m1[k];}
906  };
907
908
909  ///Applies all map setting operations to two maps
910
911  ///This map has two \ref concept::WriteMap "writable map"
912  ///parameters and each write request will be passed to both of them.
913  ///If \c M1 is also \ref concept::ReadMap "readable",
914  ///then the read operations will return the
915  ///corresponding values of \c M1.
916  ///
917  ///The \c Key and \c Value will be inherited from \c M1.
918  ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
919
920  template<typename  M1, typename M2>
921  class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
922    M1& m1;
923    M2& m2;
924  public:
925    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
926    typedef typename Parent::Key Key;
927    typedef typename Parent::Value Value;
928
929    ///Constructor
930    ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {};
931    Value operator[](Key k) const {return m1[k];}
932    void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
933  };
934 
935  ///Returns an \ref ForkMap class
936
937  ///This function just returns an \ref ForkMap class.
938  ///\todo How to call these type of functions?
939  ///
940  ///\relates ForkMap
941  ///\todo Wrong scope in Doxygen when \c \\relates is used
942  template <typename M1, typename M2>
943  inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) {
944    return ForkMap<M1, M2>(m1,m2);
945  }
946
947  template <typename M1, typename M2>
948  inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) {
949    return ForkWriteMap<M1, M2>(m1,m2);
950  }
951
952
953 
954  /* ************* BOOL MAPS ******************* */
955 
956  ///Logical 'not' of a map
957 
958  ///This bool \ref concept::ReadMap "read only map" returns the
959  ///logical negation of
960  ///value returned by the
961  ///given map. Its \c Key and will be inherited from \c M,
962  ///its Value is <tt>bool</tt>.
963
964  template <typename M>
965  class NotMap : public MapBase<typename M::Key, bool> {
966    const M& m;
967  public:
968    typedef MapBase<typename M::Key, bool> Parent;
969    typedef typename Parent::Key Key;
970    typedef typename Parent::Value Value;
971
972    /// Constructor
973    NotMap(const M &_m) : m(_m) {};
974    Value operator[](Key k) const {return !m[k];}
975  };
976
977  ///Logical 'not' of a map with writing possibility
978 
979  ///This bool \ref concept::ReadWriteMap "read-write map" returns the
980  ///logical negation of value returned by the given map. It is setted
981  ///then the negation of the value be setted to the original map.
982  ///Its \c Key and will be inherited from \c M,
983  ///its Value is <tt>bool</tt>.
984  template <typename M>
985  class NotWriteMap : public MapBase<typename M::Key, bool> {
986    M& m;
987  public:
988    typedef MapBase<typename M::Key, bool> Parent;
989    typedef typename Parent::Key Key;
990    typedef typename Parent::Value Value;
991
992    /// Constructor
993    NotWriteMap(M &_m) : m(_m) {};
994    Value operator[](Key k) const {return !m[k];}
995    void set(Key k, bool v) { m.set(k, !v); }
996  };
997 
998  ///Returns a \ref NotMap class
999 
1000  ///This function just returns a \ref NotMap class.
1001  ///\relates NotMap
1002  template <typename M>
1003  inline NotMap<M> notMap(const M &m) {
1004    return NotMap<M>(m);
1005  }
1006
1007  template <typename M>
1008  inline NotWriteMap<M> notMap(M &m) {
1009    return NotWriteMap<M>(m);
1010  }
1011
1012  namespace _maps_bits {
1013    template <typename Value>
1014    struct Identity {
1015      typedef Value argument_type;
1016      typedef Value result_type;
1017      Value operator()(const Value& val) {
1018        return val;
1019      }
1020    };
1021  }
1022 
1023
1024  /// \brief Writable bool map for store each true assigned elements.
1025  ///
1026  /// Writable bool map for store each true assigned elements. It will
1027  /// copies all the true setted keys to the given iterator.
1028  ///
1029  /// \note The container of the iterator should contain space
1030  /// for each element.
1031  ///
1032  /// The next example shows how can you write the nodes directly
1033  /// to the standard output.
1034  ///\code
1035  /// typedef IdMap<UGraph, UEdge> UEdgeIdMap;
1036  /// UEdgeIdMap uedgeId(ugraph);
1037  ///
1038  /// typedef MapFunctor<UEdgeIdMap> UEdgeIdFunctor;
1039  /// UEdgeIdFunctor uedgeIdFunctor(uedgeId);
1040  ///
1041  /// StoreBoolMap<ostream_iterator<int>, UEdgeIdFunctor>
1042  ///   writerMap(ostream_iterator<int>(cout, " "), uedgeIdFunctor);
1043  ///
1044  /// prim(ugraph, cost, writerMap);
1045  ///\endcode
1046  template <typename _Iterator,
1047            typename _Functor =
1048            _maps_bits::Identity<typename std::iterator_traits<_Iterator>::value_type> >
1049  class StoreBoolMap {
1050  public:
1051    typedef _Iterator Iterator;
1052
1053    typedef typename _Functor::argument_type Key;
1054    typedef bool Value;
1055
1056    typedef _Functor Functor;
1057
1058    /// Constructor
1059    StoreBoolMap(Iterator it, const Functor& functor = Functor())
1060      : _begin(it), _end(it), _functor(functor) {}
1061
1062    /// Gives back the given first setted iterator.
1063    Iterator begin() const {
1064      return _begin;
1065    }
1066 
1067    /// Gives back the iterator after the last setted.
1068    Iterator end() const {
1069      return _end;
1070    }
1071
1072    /// Setter function of the map
1073    void set(const Key& key, Value value) {
1074      if (value) {
1075        *_end++ = _functor(key);
1076      }
1077    }
1078   
1079  private:
1080    Iterator _begin, _end;
1081    Functor _functor;
1082  };
1083
1084  /// \brief Writable bool map for store each true assigned elements in
1085  /// a back insertable container.
1086  ///
1087  /// Writable bool map for store each true assigned elements in a back
1088  /// insertable container. It will push back all the true setted keys into
1089  /// the container. It can be used to retrieve the items into a standard
1090  /// container. The next example shows how can you store the undirected
1091  /// edges in a vector with prim algorithm.
1092  ///
1093  ///\code
1094  /// vector<UEdge> span_tree_uedges;
1095  /// BackInserterBoolMap<vector<UEdge> > inserter_map(span_tree_uedges);
1096  /// prim(ugraph, cost, inserter_map);
1097  ///\endcode
1098  template <typename Container,
1099            typename Functor =
1100            _maps_bits::Identity<typename Container::value_type> >
1101  class BackInserterBoolMap {
1102  public:
1103    typedef typename Container::value_type Key;
1104    typedef bool Value;
1105
1106    /// Constructor
1107    BackInserterBoolMap(Container& _container,
1108                        const Functor& _functor = Functor())
1109      : container(_container), functor(_functor) {}
1110
1111    /// Setter function of the map
1112    void set(const Key& key, Value value) {
1113      if (value) {
1114        container.push_back(functor(key));
1115      }
1116    }
1117   
1118  private:
1119    Container& container;
1120    Functor functor;
1121  };
1122
1123  /// \brief Writable bool map for store each true assigned elements in
1124  /// a front insertable container.
1125  ///
1126  /// Writable bool map for store each true assigned elements in a front
1127  /// insertable container. It will push front all the true setted keys into
1128  /// the container. For example see the BackInserterBoolMap.
1129  template <typename Container,
1130            typename Functor =
1131            _maps_bits::Identity<typename Container::value_type> >
1132  class FrontInserterBoolMap {
1133  public:
1134    typedef typename Container::value_type Key;
1135    typedef bool Value;
1136
1137    /// Constructor
1138    FrontInserterBoolMap(Container& _container,
1139                         const Functor& _functor = Functor())
1140      : container(_container), functor(_functor) {}
1141
1142    /// Setter function of the map
1143    void set(const Key& key, Value value) {
1144      if (value) {
1145        container.push_front(key);
1146      }
1147    }
1148   
1149  private:
1150    Container& container;   
1151    Functor functor;
1152  };
1153
1154  /// \brief Writable bool map for store each true assigned elements in
1155  /// an insertable container.
1156  ///
1157  /// Writable bool map for store each true assigned elements in an
1158  /// insertable container. It will insert all the true setted keys into
1159  /// the container. If you want to store the cut edges of the strongly
1160  /// connected components in a set you can use the next code:
1161  ///
1162  ///\code
1163  /// set<Edge> cut_edges;
1164  /// InserterBoolMap<set<Edge> > inserter_map(cut_edges);
1165  /// stronglyConnectedCutEdges(graph, cost, inserter_map);
1166  ///\endcode
1167  template <typename Container,
1168            typename Functor =
1169            _maps_bits::Identity<typename Container::value_type> >
1170  class InserterBoolMap {
1171  public:
1172    typedef typename Container::value_type Key;
1173    typedef bool Value;
1174
1175    /// Constructor
1176    InserterBoolMap(Container& _container, typename Container::iterator _it,
1177                    const Functor& _functor = Functor())
1178      : container(_container), it(_it), functor(_functor) {}
1179
1180    /// Constructor
1181    InserterBoolMap(Container& _container, const Functor& _functor = Functor())
1182      : container(_container), it(_container.end()), functor(_functor) {}
1183
1184    /// Setter function of the map
1185    void set(const Key& key, Value value) {
1186      if (value) {
1187        it = container.insert(it, key);
1188        ++it;
1189      }
1190    }
1191   
1192  private:
1193    Container& container;
1194    typename Container::iterator it;
1195    Functor functor;
1196  };
1197
1198  /// \brief Fill the true setted elements with a given value.
1199  ///
1200  /// Writable bool map for fill the true setted elements with a given value.
1201  /// The value can be setted
1202  /// the container.
1203  ///
1204  /// The next code finds the connected components of the undirected graph
1205  /// and stores it in the \c comp map:
1206  ///\code
1207  /// typedef UGraph::NodeMap<int> ComponentMap;
1208  /// ComponentMap comp(ugraph);
1209  /// typedef FillBoolMap<UGraph::NodeMap<int> > ComponentFillerMap;
1210  /// ComponentFillerMap filler(comp, 0);
1211  ///
1212  /// Dfs<UGraph>::DefProcessedMap<ComponentFillerMap>::Create dfs(ugraph);
1213  /// dfs.processedMap(filler);
1214  /// dfs.init();
1215  /// for (NodeIt it(ugraph); it != INVALID; ++it) {
1216  ///   if (!dfs.reached(it)) {
1217  ///     dfs.addSource(it);
1218  ///     dfs.start();
1219  ///     ++filler.fillValue();
1220  ///   }
1221  /// }
1222  ///\endcode
1223
1224  template <typename Map>
1225  class FillBoolMap {
1226  public:
1227    typedef typename Map::Key Key;
1228    typedef bool Value;
1229
1230    /// Constructor
1231    FillBoolMap(Map& _map, const typename Map::Value& _fill)
1232      : map(_map), fill(_fill) {}
1233
1234    /// Constructor
1235    FillBoolMap(Map& _map)
1236      : map(_map), fill() {}
1237
1238    /// Gives back the current fill value
1239    const typename Map::Value& fillValue() const {
1240      return fill;
1241    }
1242
1243    /// Gives back the current fill value
1244    typename Map::Value& fillValue() {
1245      return fill;
1246    }
1247
1248    /// Sets the current fill value
1249    void fillValue(const typename Map::Value& _fill) {
1250      fill = _fill;
1251    }
1252
1253    /// Setter function of the map
1254    void set(const Key& key, Value value) {
1255      if (value) {
1256        map.set(key, fill);
1257      }
1258    }
1259   
1260  private:
1261    Map& map;
1262    typename Map::Value fill;
1263  };
1264
1265
1266  /// \brief Writable bool map which stores for each true assigned elements 
1267  /// the setting order number.
1268  ///
1269  /// Writable bool map which stores for each true assigned elements 
1270  /// the setting order number. It make easy to calculate the leaving
1271  /// order of the nodes in the \ref dfs "Dfs" algorithm.
1272  ///
1273  ///\code
1274  /// typedef Graph::NodeMap<int> OrderMap;
1275  /// OrderMap order(graph);
1276  /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1277  /// OrderSetterMap setter(order);
1278  /// Dfs<Graph>::DefProcessedMap<OrderSetterMap>::Create dfs(graph);
1279  /// dfs.processedMap(setter);
1280  /// dfs.init();
1281  /// for (NodeIt it(graph); it != INVALID; ++it) {
1282  ///   if (!dfs.reached(it)) {
1283  ///     dfs.addSource(it);
1284  ///     dfs.start();
1285  ///   }
1286  /// }
1287  ///\endcode
1288  ///
1289  /// The discovering order can be stored a little harder because the
1290  /// ReachedMap should be readable in the dfs algorithm but the setting
1291  /// order map is not readable. Now we should use the fork map:
1292  ///
1293  ///\code
1294  /// typedef Graph::NodeMap<int> OrderMap;
1295  /// OrderMap order(graph);
1296  /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1297  /// OrderSetterMap setter(order);
1298  /// typedef Graph::NodeMap<bool> StoreMap;
1299  /// StoreMap store(graph);
1300  ///
1301  /// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap;
1302  /// ReachedMap reached(store, setter);
1303  ///
1304  /// Dfs<Graph>::DefReachedMap<ReachedMap>::Create dfs(graph);
1305  /// dfs.reachedMap(reached);
1306  /// dfs.init();
1307  /// for (NodeIt it(graph); it != INVALID; ++it) {
1308  ///   if (!dfs.reached(it)) {
1309  ///     dfs.addSource(it);
1310  ///     dfs.start();
1311  ///   }
1312  /// }
1313  ///\endcode
1314  template <typename Map>
1315  class SettingOrderBoolMap {
1316  public:
1317    typedef typename Map::Key Key;
1318    typedef bool Value;
1319
1320    /// Constructor
1321    SettingOrderBoolMap(Map& _map)
1322      : map(_map), counter(0) {}
1323
1324    /// Number of setted keys.
1325    int num() const {
1326      return counter;
1327    }
1328
1329    /// Setter function of the map
1330    void set(const Key& key, Value value) {
1331      if (value) {
1332        map.set(key, counter++);
1333      }
1334    }
1335   
1336  private:
1337    Map& map;
1338    int counter;
1339  };
1340
1341  /// @}
1342}
1343
1344#endif // LEMON_MAPS_H
Note: See TracBrowser for help on using the repository browser.