COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/maps.h @ 2258:741995f3dbc4

Last change on this file since 2258:741995f3dbc4 was 2258:741995f3dbc4, checked in by Alpar Juttner, 18 years ago

Docfix.
maps.h is still very fuzzy.

File size: 40.1 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  ///Simple wrapping of the map
291
292  ///This \ref concept::ReadMap "read only map" returns the simple
293  ///wrapping of the given map. Sometimes the reference maps cannot be
294  ///combined with simple read maps. This map adaptor wraps the given
295  ///map to simple read map.
296  template<typename M>
297  class SimpleMap : public MapBase<typename M::Key, typename M::Value> {
298    const M& m;
299
300  public:
301    typedef MapBase<typename M::Key, typename M::Value> Parent;
302    typedef typename Parent::Key Key;
303    typedef typename Parent::Value Value;
304
305    ///Constructor
306    SimpleMap(const M &_m) : m(_m) {};
307    Value operator[](Key k) const {return m[k];}
308  };
309
310  ///Simple writeable wrapping of the map
311
312  ///This \ref concept::ReadMap "read only map" returns the simple
313  ///wrapping of the given map. Sometimes the reference maps cannot be
314  ///combined with simple read-write maps. This map adaptor wraps the
315  ///given map to simple read-write map.
316  template<typename M>
317  class SimpleWriteMap : public MapBase<typename M::Key, typename M::Value> {
318    M& m;
319
320  public:
321    typedef MapBase<typename M::Key, typename M::Value> Parent;
322    typedef typename Parent::Key Key;
323    typedef typename Parent::Value Value;
324
325    ///Constructor
326    SimpleWriteMap(M &_m) : m(_m) {};
327    Value operator[](Key k) const {return m[k];}
328    void set(Key k, const Value& c) { m.set(k, c); }
329  };
330
331  ///Sum of two maps
332
333  ///This \ref concept::ReadMap "read only map" returns the sum of the two
334  ///given maps. Its \c Key and \c Value will be inherited from \c M1.
335  ///The \c Key and \c Value of M2 must be convertible to those of \c M1.
336
337  template<typename M1, typename M2>
338  class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
339    const M1& m1;
340    const M2& m2;
341
342  public:
343    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
344    typedef typename Parent::Key Key;
345    typedef typename Parent::Value Value;
346
347    ///Constructor
348    AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
349    Value operator[](Key k) const {return m1[k]+m2[k];}
350  };
351 
352  ///Returns an \ref AddMap class
353
354  ///This function just returns an \ref AddMap class.
355  ///\todo How to call these type of functions?
356  ///
357  ///\relates AddMap
358  ///\todo Wrong scope in Doxygen when \c \\relates is used
359  template<typename M1, typename M2>
360  inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
361    return AddMap<M1, M2>(m1,m2);
362  }
363
364  ///Shift a map with a constant.
365
366  ///This \ref concept::ReadMap "read only map" returns the sum of the
367  ///given map and a constant value.
368  ///Its \c Key and \c Value is inherited from \c M.
369  ///
370  ///Actually,
371  ///\code
372  ///  ShiftMap<X> sh(x,v);
373  ///\endcode
374  ///is equivalent with
375  ///\code
376  ///  ConstMap<X::Key, X::Value> c_tmp(v);
377  ///  AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
378  ///\endcode
379  template<typename M, typename C = typename M::Value>
380  class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
381    const M& m;
382    C v;
383  public:
384    typedef MapBase<typename M::Key, typename M::Value> Parent;
385    typedef typename Parent::Key Key;
386    typedef typename Parent::Value Value;
387
388    ///Constructor
389
390    ///Constructor
391    ///\param _m is the undelying map
392    ///\param _v is the shift value
393    ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
394    Value operator[](Key k) const {return m[k] + v;}
395  };
396
397  ///Shift a map with a constant.
398
399  ///This \ref concept::ReadWriteMap "read-write map" returns the sum of the
400  ///given map and a constant value. It makes also possible to write the map.
401  ///Its \c Key and \c Value is inherited from \c M.
402  ///
403  ///Actually,
404  ///\code
405  ///  ShiftMap<X> sh(x,v);
406  ///\endcode
407  ///is equivalent with
408  ///\code
409  ///  ConstMap<X::Key, X::Value> c_tmp(v);
410  ///  AddMap<X, ConstMap<X::Key, X::Value> > sh(x,v);
411  ///\endcode
412  template<typename M, typename C = typename M::Value>
413  class ShiftWriteMap : public MapBase<typename M::Key, typename M::Value> {
414    M& m;
415    C v;
416  public:
417    typedef MapBase<typename M::Key, typename M::Value> Parent;
418    typedef typename Parent::Key Key;
419    typedef typename Parent::Value Value;
420
421    ///Constructor
422
423    ///Constructor
424    ///\param _m is the undelying map
425    ///\param _v is the shift value
426    ShiftWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
427    Value operator[](Key k) const {return m[k] + v;}
428    void set(Key k, const Value& c) { m.set(k, c - v); }
429  };
430 
431  ///Returns an \ref ShiftMap class
432
433  ///This function just returns an \ref ShiftMap class.
434  ///\relates ShiftMap
435  ///\todo A better name is required.
436  template<typename M, typename C>
437  inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
438    return ShiftMap<M, C>(m,v);
439  }
440
441  template<typename M, typename C>
442  inline ShiftWriteMap<M, C> shiftMap(M &m,const C &v) {
443    return ShiftWriteMap<M, C>(m,v);
444  }
445
446  ///Difference of two maps
447
448  ///This \ref concept::ReadMap "read only map" returns the difference
449  ///of the values of the two
450  ///given maps. Its \c Key and \c Value will be inherited from \c M1.
451  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
452
453  template<typename M1, typename M2>
454  class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
455    const M1& m1;
456    const M2& m2;
457  public:
458    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
459    typedef typename Parent::Key Key;
460    typedef typename Parent::Value Value;
461
462    ///Constructor
463    SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
464    Value operator[](Key k) const {return m1[k]-m2[k];}
465  };
466 
467  ///Returns a \ref SubMap class
468
469  ///This function just returns a \ref SubMap class.
470  ///
471  ///\relates SubMap
472  template<typename M1, typename M2>
473  inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
474    return SubMap<M1, M2>(m1, m2);
475  }
476
477  ///Product of two maps
478
479  ///This \ref concept::ReadMap "read only map" returns the product of the
480  ///values of the two
481  ///given
482  ///maps. Its \c Key and \c Value will be inherited from \c M1.
483  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
484
485  template<typename M1, typename M2>
486  class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
487    const M1& m1;
488    const M2& m2;
489  public:
490    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
491    typedef typename Parent::Key Key;
492    typedef typename Parent::Value Value;
493
494    ///Constructor
495    MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
496    Value operator[](Key k) const {return m1[k]*m2[k];}
497  };
498 
499  ///Returns a \ref MulMap class
500
501  ///This function just returns a \ref MulMap class.
502  ///\relates MulMap
503  template<typename M1, typename M2>
504  inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
505    return MulMap<M1, M2>(m1,m2);
506  }
507 
508  ///Scales a maps with a constant.
509
510  ///This \ref concept::ReadMap "read only map" returns the value of the
511  ///given map multiplied from the left side with a constant value.
512  ///Its \c Key and \c Value is inherited from \c M.
513  ///
514  ///Actually,
515  ///\code
516  ///  ScaleMap<X> sc(x,v);
517  ///\endcode
518  ///is equivalent with
519  ///\code
520  ///  ConstMap<X::Key, X::Value> c_tmp(v);
521  ///  MulMap<X, ConstMap<X::Key, X::Value> > sc(x,v);
522  ///\endcode
523  template<typename M, typename C = typename M::Value>
524  class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
525    const M& m;
526    C v;
527  public:
528    typedef MapBase<typename M::Key, typename M::Value> Parent;
529    typedef typename Parent::Key Key;
530    typedef typename Parent::Value Value;
531
532    ///Constructor
533
534    ///Constructor
535    ///\param _m is the undelying map
536    ///\param _v is the scaling value
537    ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
538    Value operator[](Key k) const {return v * m[k];}
539  };
540
541  ///Scales a maps with a constant.
542
543  ///This \ref concept::ReadWriteMap "read-write map" returns the value of the
544  ///given map multiplied from the left side with a constant value. It can
545  ///be used as write map also if the given multiplier is not zero.
546  ///Its \c Key and \c Value is inherited from \c M.
547  template<typename M, typename C = typename M::Value>
548  class ScaleWriteMap : public MapBase<typename M::Key, typename M::Value> {
549    M& m;
550    C v;
551  public:
552    typedef MapBase<typename M::Key, typename M::Value> Parent;
553    typedef typename Parent::Key Key;
554    typedef typename Parent::Value Value;
555
556    ///Constructor
557
558    ///Constructor
559    ///\param _m is the undelying map
560    ///\param _v is the scaling value
561    ScaleWriteMap(M &_m, const C &_v ) : m(_m), v(_v) {};
562    Value operator[](Key k) const {return v * m[k];}
563    void set(Key k, const Value& c) { m.set(k, c / v);}
564  };
565 
566  ///Returns an \ref ScaleMap class
567
568  ///This function just returns an \ref ScaleMap class.
569  ///\relates ScaleMap
570  ///\todo A better name is required.
571  template<typename M, typename C>
572  inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
573    return ScaleMap<M, C>(m,v);
574  }
575
576  template<typename M, typename C>
577  inline ScaleWriteMap<M, C> scaleMap(M &m,const C &v) {
578    return ScaleWriteMap<M, C>(m,v);
579  }
580
581  ///Quotient of two maps
582
583  ///This \ref concept::ReadMap "read only map" returns the quotient of the
584  ///values of the two
585  ///given maps. Its \c Key and \c Value will be inherited from \c M1.
586  ///The \c Key and \c Value of \c M2 must be convertible to those of \c M1.
587
588  template<typename M1, typename M2>
589  class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
590    const M1& m1;
591    const M2& m2;
592  public:
593    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
594    typedef typename Parent::Key Key;
595    typedef typename Parent::Value Value;
596
597    ///Constructor
598    DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
599    Value operator[](Key k) const {return m1[k]/m2[k];}
600  };
601 
602  ///Returns a \ref DivMap class
603
604  ///This function just returns a \ref DivMap class.
605  ///\relates DivMap
606  template<typename M1, typename M2>
607  inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
608    return DivMap<M1, M2>(m1,m2);
609  }
610 
611  ///Composition of two maps
612
613  ///This \ref concept::ReadMap "read only map" returns the composition of
614  ///two
615  ///given maps. That is to say, if \c m1 is of type \c M1 and \c m2 is
616  ///of \c M2,
617  ///then for
618  ///\code
619  ///  ComposeMap<M1, M2> cm(m1,m2);
620  ///\endcode
621  /// <tt>cm[x]</tt> will be equal to <tt>m1[m2[x]]</tt>
622  ///
623  ///Its \c Key is inherited from \c M2 and its \c Value is from
624  ///\c M1.
625  ///The \c M2::Value must be convertible to \c M1::Key.
626  ///\todo Check the requirements.
627
628  template <typename M1, typename M2>
629  class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
630    const M1& m1;
631    const M2& m2;
632  public:
633    typedef MapBase<typename M2::Key, typename M1::Value> Parent;
634    typedef typename Parent::Key Key;
635    typedef typename Parent::Value Value;
636
637    ///Constructor
638    ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
639   
640    typename MapTraits<M1>::ConstReturnValue
641    operator[](Key k) const {return m1[m2[k]];}
642  };
643  ///Returns a \ref ComposeMap class
644
645  ///This function just returns a \ref ComposeMap class.
646  ///
647  ///\relates ComposeMap
648  template <typename M1, typename M2>
649  inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
650    return ComposeMap<M1, M2>(m1,m2);
651  }
652 
653  ///Combines of two maps using an STL (binary) functor.
654
655  ///Combines of two maps using an STL (binary) functor.
656  ///
657  ///
658  ///This \ref concept::ReadMap "read only map" takes two maps and a
659  ///binary functor and returns the composition of
660  ///the two
661  ///given maps unsing the functor.
662  ///That is to say, if \c m1 and \c m2 is of type \c M1 and \c M2
663  ///and \c f is of \c F,
664  ///then for
665  ///\code
666  ///  CombineMap<M1, M2,F,V> cm(m1,m2,f);
667  ///\endcode
668  /// <tt>cm[x]</tt> will be equal to <tt>f(m1[x],m2[x])</tt>
669  ///
670  ///Its \c Key is inherited from \c M1 and its \c Value is \c V.
671  ///The \c M2::Value and \c M1::Value must be convertible to the corresponding
672  ///input parameter of \c F and the return type of \c F must be convertible
673  ///to \c V.
674  ///\todo Check the requirements.
675
676  template<typename M1, typename M2, typename F,
677           typename V = typename F::result_type,
678           typename NC = False>
679  class CombineMap : public MapBase<typename M1::Key, V> {
680    const M1& m1;
681    const M2& m2;
682    F f;
683  public:
684    typedef MapBase<typename M1::Key, V> Parent;
685    typedef typename Parent::Key Key;
686    typedef typename Parent::Value Value;
687
688    ///Constructor
689    CombineMap(const M1 &_m1,const M2 &_m2,const F &_f)
690      : m1(_m1), m2(_m2), f(_f) {};
691    Value operator[](Key k) const {return f(m1[k],m2[k]);}
692  };
693 
694  ///Returns a \ref CombineMap class
695
696  ///This function just returns a \ref CombineMap class.
697  ///
698  ///Only the first template parameter (the value type) must be given.
699  ///
700  ///For example if \c m1 and \c m2 are both \c double valued maps, then
701  ///\code
702  ///combineMap<double>(m1,m2,std::plus<double>)
703  ///\endcode
704  ///is equivalent with
705  ///\code
706  ///addMap(m1,m2)
707  ///\endcode
708  ///
709  ///\relates CombineMap
710  template<typename M1, typename M2, typename F, typename V>
711  inline CombineMap<M1, M2, F, V>
712  combineMap(const M1& m1,const M2& m2, const F& f) {
713    return CombineMap<M1, M2, F, V>(m1,m2,f);
714  }
715
716  template<typename M1, typename M2, typename F>
717  inline CombineMap<M1, M2, F, typename F::result_type>
718  combineMap(const M1& m1, const M2& m2, const F& f) {
719    return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
720  }
721
722  template<typename M1, typename M2, typename K1, typename K2, typename V>
723  inline CombineMap<M1, M2, V (*)(K1, K2), V>
724  combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
725    return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
726  }
727
728  ///Negative value of a map
729
730  ///This \ref concept::ReadMap "read only map" returns the negative
731  ///value of the
732  ///value returned by the
733  ///given map. Its \c Key and \c Value will be inherited from \c M.
734  ///The unary \c - operator must be defined for \c Value, of course.
735
736  template<typename M>
737  class NegMap : public MapBase<typename M::Key, typename M::Value> {
738    const M& m;
739  public:
740    typedef MapBase<typename M::Key, typename M::Value> Parent;
741    typedef typename Parent::Key Key;
742    typedef typename Parent::Value Value;
743
744    ///Constructor
745    NegMap(const M &_m) : m(_m) {};
746    Value operator[](Key k) const {return -m[k];}
747  };
748 
749  ///Negative value of a map
750
751  ///This \ref concept::ReadWriteMap "read-write map" returns the negative
752  ///value of the value returned by the
753  ///given map. Its \c Key and \c Value will be inherited from \c M.
754  ///The unary \c - operator must be defined for \c Value, of course.
755
756  template<typename M>
757  class NegWriteMap : public MapBase<typename M::Key, typename M::Value> {
758    M& m;
759  public:
760    typedef MapBase<typename M::Key, typename M::Value> Parent;
761    typedef typename Parent::Key Key;
762    typedef typename Parent::Value Value;
763
764    ///Constructor
765    NegWriteMap(M &_m) : m(_m) {};
766    Value operator[](Key k) const {return -m[k];}
767    void set(Key k, const Value& v) { m.set(k, -v); }
768  };
769
770  ///Returns a \ref NegMap class
771
772  ///This function just returns a \ref NegMap class.
773  ///\relates NegMap
774  template <typename M>
775  inline NegMap<M> negMap(const M &m) {
776    return NegMap<M>(m);
777  }
778
779  template <typename M>
780  inline NegWriteMap<M> negMap(M &m) {
781    return NegWriteMap<M>(m);
782  }
783
784  ///Absolute value of a map
785
786  ///This \ref concept::ReadMap "read only map" returns the absolute value
787  ///of the
788  ///value returned by the
789  ///given map. Its \c Key and \c Value will be inherited
790  ///from <tt>M</tt>. <tt>Value</tt>
791  ///must be comparable to <tt>0</tt> and the unary <tt>-</tt>
792  ///operator must be defined for it, of course.
793  ///
794  ///\bug We need a unified way to handle the situation below:
795  ///\code
796  ///  struct _UnConvertible {};
797  ///  template<class A> inline A t_abs(A a) {return _UnConvertible();}
798  ///  template<> inline int t_abs<>(int n) {return abs(n);}
799  ///  template<> inline long int t_abs<>(long int n) {return labs(n);}
800  ///  template<> inline long long int t_abs<>(long long int n) {return ::llabs(n);}
801  ///  template<> inline float t_abs<>(float n) {return fabsf(n);}
802  ///  template<> inline double t_abs<>(double n) {return fabs(n);}
803  ///  template<> inline long double t_abs<>(long double n) {return fabsl(n);}
804  ///\endcode
805 
806
807  template<typename M>
808  class AbsMap : public MapBase<typename M::Key, typename M::Value> {
809    const M& m;
810  public:
811    typedef MapBase<typename M::Key, typename M::Value> Parent;
812    typedef typename Parent::Key Key;
813    typedef typename Parent::Value Value;
814
815    ///Constructor
816    AbsMap(const M &_m) : m(_m) {};
817    Value operator[](Key k) const {
818      Value tmp = m[k];
819      return tmp >= 0 ? tmp : -tmp;
820    }
821
822  };
823 
824  ///Returns a \ref AbsMap class
825
826  ///This function just returns a \ref AbsMap class.
827  ///\relates AbsMap
828  template<typename M>
829  inline AbsMap<M> absMap(const M &m) {
830    return AbsMap<M>(m);
831  }
832
833  ///Converts an STL style functor to a map
834
835  ///This \ref concept::ReadMap "read only map" returns the value
836  ///of a
837  ///given map.
838  ///
839  ///Template parameters \c K and \c V will become its
840  ///\c Key and \c Value. They must be given explicitely
841  ///because a functor does not provide such typedefs.
842  ///
843  ///Parameter \c F is the type of the used functor.
844 
845
846  template<typename F,
847           typename K = typename F::argument_type,
848           typename V = typename F::result_type,
849           typename NC = False>
850  class FunctorMap : public MapBase<K, V> {
851    F f;
852  public:
853    typedef MapBase<K, V> Parent;
854    typedef typename Parent::Key Key;
855    typedef typename Parent::Value Value;
856
857    ///Constructor
858    FunctorMap(const F &_f) : f(_f) {}
859
860    Value operator[](Key k) const { return f(k);}
861  };
862 
863  ///Returns a \ref FunctorMap class
864
865  ///This function just returns a \ref FunctorMap class.
866  ///
867  ///The third template parameter isn't necessary to be given.
868  ///\relates FunctorMap
869  template<typename K, typename V, typename F> inline
870  FunctorMap<F, K, V> functorMap(const F &f) {
871    return FunctorMap<F, K, V>(f);
872  }
873
874  template <typename F> inline
875  FunctorMap<F, typename F::argument_type, typename F::result_type>
876  functorMap(const F &f) {
877    return FunctorMap<F, typename F::argument_type,
878      typename F::result_type>(f);
879  }
880
881  template <typename K, typename V> inline
882  FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
883    return FunctorMap<V (*)(K), K, V>(f);
884  }
885
886
887  ///Converts a map to an STL style (unary) functor
888
889  ///This class Converts a map to an STL style (unary) functor.
890  ///that is it provides an <tt>operator()</tt> to read its values.
891  ///
892  ///For the sake of convenience it also works as
893  ///a ususal \ref concept::ReadMap "readable map",
894  ///i.e. <tt>operator[]</tt> and the \c Key and \c Value typedefs also exist.
895
896  template <typename M>
897  class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
898    const M& m;
899  public:
900    typedef MapBase<typename M::Key, typename M::Value> Parent;
901    typedef typename Parent::Key Key;
902    typedef typename Parent::Value Value;
903
904    ///\e
905    typedef typename M::Key argument_type;
906    ///\e
907    typedef typename M::Value result_type;
908
909    ///Constructor
910    MapFunctor(const M &_m) : m(_m) {};
911    ///Returns a value of the map
912    Value operator()(Key k) const {return m[k];}
913    ///\e
914    Value operator[](Key k) const {return m[k];}
915  };
916 
917  ///Returns a \ref MapFunctor class
918
919  ///This function just returns a \ref MapFunctor class.
920  ///\relates MapFunctor
921  template<typename M>
922  inline MapFunctor<M> mapFunctor(const M &m) {
923    return MapFunctor<M>(m);
924  }
925
926  ///Applies all map setting operations to two maps
927
928  ///This map has two \ref concept::ReadMap "readable map"
929  ///parameters and each read request will be passed just to the
930  ///first map. This class is the just readable map type of the ForkWriteMap.
931  ///
932  ///The \c Key and \c Value will be inherited from \c M1.
933  ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
934
935  template<typename  M1, typename M2>
936  class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
937    const M1& m1;
938    const M2& m2;
939  public:
940    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
941    typedef typename Parent::Key Key;
942    typedef typename Parent::Value Value;
943
944    ///Constructor
945    ForkMap(const M1 &_m1, const M2 &_m2) : m1(_m1), m2(_m2) {};
946    Value operator[](Key k) const {return m1[k];}
947  };
948
949
950  ///Applies all map setting operations to two maps
951
952  ///This map has two \ref concept::WriteMap "writable map"
953  ///parameters and each write request will be passed to both of them.
954  ///If \c M1 is also \ref concept::ReadMap "readable",
955  ///then the read operations will return the
956  ///corresponding values of \c M1.
957  ///
958  ///The \c Key and \c Value will be inherited from \c M1.
959  ///The \c Key and \c Value of M2 must be convertible from those of \c M1.
960
961  template<typename  M1, typename M2>
962  class ForkWriteMap : public MapBase<typename M1::Key, typename M1::Value> {
963    M1& m1;
964    M2& m2;
965  public:
966    typedef MapBase<typename M1::Key, typename M1::Value> Parent;
967    typedef typename Parent::Key Key;
968    typedef typename Parent::Value Value;
969
970    ///Constructor
971    ForkWriteMap(M1 &_m1, M2 &_m2) : m1(_m1), m2(_m2) {};
972    Value operator[](Key k) const {return m1[k];}
973    void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
974  };
975 
976  ///Returns an \ref ForkMap class
977
978  ///This function just returns an \ref ForkMap class.
979  ///\todo How to call these type of functions?
980  ///
981  ///\relates ForkMap
982  ///\todo Wrong scope in Doxygen when \c \\relates is used
983  template <typename M1, typename M2>
984  inline ForkMap<M1, M2> forkMap(const M1 &m1, const M2 &m2) {
985    return ForkMap<M1, M2>(m1,m2);
986  }
987
988  template <typename M1, typename M2>
989  inline ForkWriteMap<M1, M2> forkMap(M1 &m1, M2 &m2) {
990    return ForkWriteMap<M1, M2>(m1,m2);
991  }
992
993
994 
995  /* ************* BOOL MAPS ******************* */
996 
997  ///Logical 'not' of a map
998 
999  ///This bool \ref concept::ReadMap "read only map" returns the
1000  ///logical negation of
1001  ///value returned by the
1002  ///given map. Its \c Key and will be inherited from \c M,
1003  ///its Value is <tt>bool</tt>.
1004
1005  template <typename M>
1006  class NotMap : public MapBase<typename M::Key, bool> {
1007    const M& m;
1008  public:
1009    typedef MapBase<typename M::Key, bool> Parent;
1010    typedef typename Parent::Key Key;
1011    typedef typename Parent::Value Value;
1012
1013    /// Constructor
1014    NotMap(const M &_m) : m(_m) {};
1015    Value operator[](Key k) const {return !m[k];}
1016  };
1017
1018  ///Logical 'not' of a map with writing possibility
1019 
1020  ///This bool \ref concept::ReadWriteMap "read-write map" returns the
1021  ///logical negation of value returned by the given map. When it is set,
1022  ///the opposite value is set to the original map.
1023  ///Its \c Key and will be inherited from \c M,
1024  ///its Value is <tt>bool</tt>.
1025  template <typename M>
1026  class NotWriteMap : public MapBase<typename M::Key, bool> {
1027    M& m;
1028  public:
1029    typedef MapBase<typename M::Key, bool> Parent;
1030    typedef typename Parent::Key Key;
1031    typedef typename Parent::Value Value;
1032
1033    /// Constructor
1034    NotWriteMap(M &_m) : m(_m) {};
1035    Value operator[](Key k) const {return !m[k];}
1036    void set(Key k, bool v) { m.set(k, !v); }
1037  };
1038 
1039  ///Returns a \ref NotMap class
1040 
1041  ///This function just returns a \ref NotMap class.
1042  ///\relates NotMap
1043  template <typename M>
1044  inline NotMap<M> notMap(const M &m) {
1045    return NotMap<M>(m);
1046  }
1047
1048  template <typename M>
1049  inline NotWriteMap<M> notMap(M &m) {
1050    return NotWriteMap<M>(m);
1051  }
1052
1053  namespace _maps_bits {
1054    template <typename Value>
1055    struct Identity {
1056      typedef Value argument_type;
1057      typedef Value result_type;
1058      Value operator()(const Value& val) {
1059        return val;
1060      }
1061    };
1062  }
1063 
1064
1065  /// \brief Writable bool map for store each true assigned elements.
1066  ///
1067  /// Writable bool map to store each true assigned elements. It will
1068  /// copies all the keys set to true to the given iterator.
1069  ///
1070  /// \note The container of the iterator should contain space
1071  /// for each element.
1072  ///
1073  /// The next example shows how can you write the nodes directly
1074  /// to the standard output.
1075  ///\code
1076  /// typedef IdMap<UGraph, UEdge> UEdgeIdMap;
1077  /// UEdgeIdMap uedgeId(ugraph);
1078  ///
1079  /// typedef MapFunctor<UEdgeIdMap> UEdgeIdFunctor;
1080  /// UEdgeIdFunctor uedgeIdFunctor(uedgeId);
1081  ///
1082  /// StoreBoolMap<ostream_iterator<int>, UEdgeIdFunctor>
1083  ///   writerMap(ostream_iterator<int>(cout, " "), uedgeIdFunctor);
1084  ///
1085  /// prim(ugraph, cost, writerMap);
1086  ///\endcode
1087  template <typename _Iterator,
1088            typename _Functor =
1089            _maps_bits::Identity<typename std::iterator_traits<_Iterator>::value_type> >
1090  class StoreBoolMap {
1091  public:
1092    typedef _Iterator Iterator;
1093
1094    typedef typename _Functor::argument_type Key;
1095    typedef bool Value;
1096
1097    typedef _Functor Functor;
1098
1099    /// Constructor
1100    StoreBoolMap(Iterator it, const Functor& functor = Functor())
1101      : _begin(it), _end(it), _functor(functor) {}
1102
1103    /// Gives back the given iterator set for the first time.
1104    Iterator begin() const {
1105      return _begin;
1106    }
1107 
1108    /// Gives back the iterator after the last set operation.
1109    Iterator end() const {
1110      return _end;
1111    }
1112
1113    /// Setter function of the map
1114    void set(const Key& key, Value value) {
1115      if (value) {
1116        *_end++ = _functor(key);
1117      }
1118    }
1119   
1120  private:
1121    Iterator _begin, _end;
1122    Functor _functor;
1123  };
1124
1125  /// \brief Writable bool map for store each true assigned elements in
1126  /// a back insertable container.
1127  ///
1128  /// Writable bool map for store each true assigned elements in a back
1129  /// insertable container. It will push back all the keys set to true into
1130  /// the container. It can be used to retrieve the items into a standard
1131  /// container. The next example shows how can you store the undirected
1132  /// edges in a vector with prim algorithm.
1133  ///
1134  ///\code
1135  /// vector<UEdge> span_tree_uedges;
1136  /// BackInserterBoolMap<vector<UEdge> > inserter_map(span_tree_uedges);
1137  /// prim(ugraph, cost, inserter_map);
1138  ///\endcode
1139  template <typename Container,
1140            typename Functor =
1141            _maps_bits::Identity<typename Container::value_type> >
1142  class BackInserterBoolMap {
1143  public:
1144    typedef typename Container::value_type Key;
1145    typedef bool Value;
1146
1147    /// Constructor
1148    BackInserterBoolMap(Container& _container,
1149                        const Functor& _functor = Functor())
1150      : container(_container), functor(_functor) {}
1151
1152    /// Setter function of the map
1153    void set(const Key& key, Value value) {
1154      if (value) {
1155        container.push_back(functor(key));
1156      }
1157    }
1158   
1159  private:
1160    Container& container;
1161    Functor functor;
1162  };
1163
1164  /// \brief Writable bool map for store each true assigned elements in
1165  /// a front insertable container.
1166  ///
1167  /// Writable bool map for store each true assigned elements in a front
1168  /// insertable container. It will push front all the keys set to \c true into
1169  /// the container. For example see the BackInserterBoolMap.
1170  template <typename Container,
1171            typename Functor =
1172            _maps_bits::Identity<typename Container::value_type> >
1173  class FrontInserterBoolMap {
1174  public:
1175    typedef typename Container::value_type Key;
1176    typedef bool Value;
1177
1178    /// Constructor
1179    FrontInserterBoolMap(Container& _container,
1180                         const Functor& _functor = Functor())
1181      : container(_container), functor(_functor) {}
1182
1183    /// Setter function of the map
1184    void set(const Key& key, Value value) {
1185      if (value) {
1186        container.push_front(key);
1187      }
1188    }
1189   
1190  private:
1191    Container& container;   
1192    Functor functor;
1193  };
1194
1195  /// \brief Writable bool map for store each true assigned elements in
1196  /// an insertable container.
1197  ///
1198  /// Writable bool map for store each true assigned elements in an
1199  /// insertable container. It will insert all the keys set to \c true into
1200  /// the container. If you want to store the cut edges of the strongly
1201  /// connected components in a set you can use the next code:
1202  ///
1203  ///\code
1204  /// set<Edge> cut_edges;
1205  /// InserterBoolMap<set<Edge> > inserter_map(cut_edges);
1206  /// stronglyConnectedCutEdges(graph, cost, inserter_map);
1207  ///\endcode
1208  template <typename Container,
1209            typename Functor =
1210            _maps_bits::Identity<typename Container::value_type> >
1211  class InserterBoolMap {
1212  public:
1213    typedef typename Container::value_type Key;
1214    typedef bool Value;
1215
1216    /// Constructor
1217    InserterBoolMap(Container& _container, typename Container::iterator _it,
1218                    const Functor& _functor = Functor())
1219      : container(_container), it(_it), functor(_functor) {}
1220
1221    /// Constructor
1222    InserterBoolMap(Container& _container, const Functor& _functor = Functor())
1223      : container(_container), it(_container.end()), functor(_functor) {}
1224
1225    /// Setter function of the map
1226    void set(const Key& key, Value value) {
1227      if (value) {
1228        it = container.insert(it, key);
1229        ++it;
1230      }
1231    }
1232   
1233  private:
1234    Container& container;
1235    typename Container::iterator it;
1236    Functor functor;
1237  };
1238
1239  /// \brief Fill the true set elements with a given value.
1240  ///
1241  /// Writable bool map to fill the elements set to \c true with a given value.
1242  /// The value can set
1243  /// the container.
1244  ///
1245  /// The next code finds the connected components of the undirected graph
1246  /// and stores it in the \c comp map:
1247  ///\code
1248  /// typedef UGraph::NodeMap<int> ComponentMap;
1249  /// ComponentMap comp(ugraph);
1250  /// typedef FillBoolMap<UGraph::NodeMap<int> > ComponentFillerMap;
1251  /// ComponentFillerMap filler(comp, 0);
1252  ///
1253  /// Dfs<UGraph>::DefProcessedMap<ComponentFillerMap>::Create dfs(ugraph);
1254  /// dfs.processedMap(filler);
1255  /// dfs.init();
1256  /// for (NodeIt it(ugraph); it != INVALID; ++it) {
1257  ///   if (!dfs.reached(it)) {
1258  ///     dfs.addSource(it);
1259  ///     dfs.start();
1260  ///     ++filler.fillValue();
1261  ///   }
1262  /// }
1263  ///\endcode
1264
1265  template <typename Map>
1266  class FillBoolMap {
1267  public:
1268    typedef typename Map::Key Key;
1269    typedef bool Value;
1270
1271    /// Constructor
1272    FillBoolMap(Map& _map, const typename Map::Value& _fill)
1273      : map(_map), fill(_fill) {}
1274
1275    /// Constructor
1276    FillBoolMap(Map& _map)
1277      : map(_map), fill() {}
1278
1279    /// Gives back the current fill value
1280    const typename Map::Value& fillValue() const {
1281      return fill;
1282    }
1283
1284    /// Gives back the current fill value
1285    typename Map::Value& fillValue() {
1286      return fill;
1287    }
1288
1289    /// Sets the current fill value
1290    void fillValue(const typename Map::Value& _fill) {
1291      fill = _fill;
1292    }
1293
1294    /// Setter function of the map
1295    void set(const Key& key, Value value) {
1296      if (value) {
1297        map.set(key, fill);
1298      }
1299    }
1300   
1301  private:
1302    Map& map;
1303    typename Map::Value fill;
1304  };
1305
1306
1307  /// \brief Writable bool map which stores for each true assigned elements 
1308  /// the setting order number.
1309  ///
1310  /// Writable bool map which stores for each true assigned elements 
1311  /// the setting order number. It make easy to calculate the leaving
1312  /// order of the nodes in the \ref dfs "Dfs" algorithm.
1313  ///
1314  ///\code
1315  /// typedef Graph::NodeMap<int> OrderMap;
1316  /// OrderMap order(graph);
1317  /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1318  /// OrderSetterMap setter(order);
1319  /// Dfs<Graph>::DefProcessedMap<OrderSetterMap>::Create dfs(graph);
1320  /// dfs.processedMap(setter);
1321  /// dfs.init();
1322  /// for (NodeIt it(graph); it != INVALID; ++it) {
1323  ///   if (!dfs.reached(it)) {
1324  ///     dfs.addSource(it);
1325  ///     dfs.start();
1326  ///   }
1327  /// }
1328  ///\endcode
1329  ///
1330  /// The discovering order can be stored a little harder because the
1331  /// ReachedMap should be readable in the dfs algorithm but the setting
1332  /// order map is not readable. Now we should use the fork map:
1333  ///
1334  ///\code
1335  /// typedef Graph::NodeMap<int> OrderMap;
1336  /// OrderMap order(graph);
1337  /// typedef SettingOrderBoolMap<OrderMap> OrderSetterMap;
1338  /// OrderSetterMap setter(order);
1339  /// typedef Graph::NodeMap<bool> StoreMap;
1340  /// StoreMap store(graph);
1341  ///
1342  /// typedef ForkWriteMap<StoreMap, OrderSetterMap> ReachedMap;
1343  /// ReachedMap reached(store, setter);
1344  ///
1345  /// Dfs<Graph>::DefReachedMap<ReachedMap>::Create dfs(graph);
1346  /// dfs.reachedMap(reached);
1347  /// dfs.init();
1348  /// for (NodeIt it(graph); it != INVALID; ++it) {
1349  ///   if (!dfs.reached(it)) {
1350  ///     dfs.addSource(it);
1351  ///     dfs.start();
1352  ///   }
1353  /// }
1354  ///\endcode
1355  template <typename Map>
1356  class SettingOrderBoolMap {
1357  public:
1358    typedef typename Map::Key Key;
1359    typedef bool Value;
1360
1361    /// Constructor
1362    SettingOrderBoolMap(Map& _map)
1363      : map(_map), counter(0) {}
1364
1365    /// Number of set operations.
1366    int num() const {
1367      return counter;
1368    }
1369
1370    /// Setter function of the map
1371    void set(const Key& key, Value value) {
1372      if (value) {
1373        map.set(key, counter++);
1374      }
1375    }
1376   
1377  private:
1378    Map& map;
1379    int counter;
1380  };
1381
1382  /// @}
1383}
1384
1385#endif // LEMON_MAPS_H
Note: See TracBrowser for help on using the repository browser.