COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/maps.h @ 2505:1bb471764ab8

Last change on this file since 2505:1bb471764ab8 was 2489:48dddc283cfc, checked in by Balazs Dezso, 16 years ago

Bug fix and redesign StdMap?
Improving map adaptors documentations

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