00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_MAPS_H
00020 #define LEMON_MAPS_H
00021
00022 #include <iterator>
00023
00024 #include <lemon/utility.h>
00025 #include <lemon/traits.h>
00026
00033
00034 #include <map>
00035
00036 namespace lemon {
00037
00040
00042
00045 template<typename K, typename T>
00046 class MapBase {
00047 public:
00049 typedef K Key;
00051 typedef T Value;
00052 };
00053
00055
00059 template<typename K, typename T>
00060 class NullMap : public MapBase<K, T> {
00061 public:
00062 typedef MapBase<K, T> Parent;
00063 typedef typename Parent::Key Key;
00064 typedef typename Parent::Value Value;
00065
00067 T operator[](const K&) const { return T(); }
00069 void set(const K&, const T&) {}
00070 };
00071
00072 template <typename K, typename V>
00073 NullMap<K, V> nullMap() {
00074 return NullMap<K, V>();
00075 }
00076
00077
00079
00083 template<typename K, typename T>
00084 class ConstMap : public MapBase<K, T> {
00085 private:
00086 T v;
00087 public:
00088
00089 typedef MapBase<K, T> Parent;
00090 typedef typename Parent::Key Key;
00091 typedef typename Parent::Value Value;
00092
00094
00097 ConstMap() {}
00099
00102 ConstMap(const T &_v) : v(_v) {}
00103
00104 T operator[](const K&) const { return v; }
00105 void set(const K&, const T&) {}
00106
00107 template<typename T1>
00108 struct rebind {
00109 typedef ConstMap<K, T1> other;
00110 };
00111
00112 template<typename T1>
00113 ConstMap(const ConstMap<K, T1> &, const T &_v) : v(_v) {}
00114 };
00115
00117
00120 template<typename K, typename V>
00121 inline ConstMap<K, V> constMap(const V &v) {
00122 return ConstMap<K, V>(v);
00123 }
00124
00125
00126
00127 template<typename T, T v>
00128 struct Const { };
00129
00130
00131 template<typename K, typename V, V v>
00132 class ConstMap<K, Const<V, v> > : public MapBase<K, V> {
00133 public:
00134 typedef MapBase<K, V> Parent;
00135 typedef typename Parent::Key Key;
00136 typedef typename Parent::Value Value;
00137
00138 ConstMap() { }
00139 V operator[](const K&) const { return v; }
00140 void set(const K&, const V&) { }
00141 };
00142
00144
00147 template<typename K, typename V, V v>
00148 inline ConstMap<K, Const<V, v> > constMap() {
00149 return ConstMap<K, Const<V, v> >();
00150 }
00151
00153
00158 template <typename K, typename T, typename Compare = std::less<K> >
00159 class StdMap : public std::map<K, T, Compare> {
00160 typedef std::map<K, T, Compare> parent;
00161 T v;
00162 typedef typename parent::value_type PairType;
00163
00164 public:
00166 typedef K Key;
00168 typedef T Value;
00170 typedef T& Reference;
00172 typedef const T& ConstReference;
00173
00174
00175 StdMap() : v() {}
00177 StdMap(const T& _v) : v(_v) {}
00178
00182 StdMap(const parent &m) : parent(m) {}
00187 StdMap(const parent &m, const T& _v) : parent(m), v(_v) {}
00188
00189 template<typename T1, typename Comp1>
00190 StdMap(const StdMap<Key, T1,Comp1> &m, const T &_v) {
00191
00192 }
00193
00194 Reference operator[](const Key &k) {
00195 return insert(PairType(k,v)).first -> second;
00196 }
00197
00198 ConstReference operator[](const Key &k) const {
00199 typename parent::iterator i = lower_bound(k);
00200 if (i == parent::end() || parent::key_comp()(k, (*i).first))
00201 return v;
00202 return (*i).second;
00203 }
00204 void set(const Key &k, const T &t) {
00205 parent::operator[](k) = t;
00206 }
00207
00213 T setDefault(const T &_v) { T old=v; v=_v; return old; }
00214
00215 template<typename T1>
00216 struct rebind {
00217 typedef StdMap<Key, T1,Compare> other;
00218 };
00219 };
00220
00222
00225
00230 template <typename T>
00231 class IdentityMap : public MapBase<T, T> {
00232 public:
00233 typedef MapBase<T, T> Parent;
00234 typedef typename Parent::Key Key;
00235 typedef typename Parent::Value Value;
00236
00237 const T& operator[](const T& t) const {
00238 return t;
00239 }
00240 };
00241
00243
00246 template<typename T>
00247 inline IdentityMap<T> identityMap() {
00248 return IdentityMap<T>();
00249 }
00250
00251
00253
00257 template <typename M, typename T>
00258 class ConvertMap : public MapBase<typename M::Key, T> {
00259 const M& m;
00260 public:
00261 typedef MapBase<typename M::Key, T> Parent;
00262 typedef typename Parent::Key Key;
00263 typedef typename Parent::Value Value;
00264
00266
00269 ConvertMap(const M &_m) : m(_m) {};
00270
00276 Value operator[](const Key& k) const {return m[k];}
00277 };
00278
00280
00284 template<typename T, typename M>
00285 inline ConvertMap<M, T> convertMap(const M &m) {
00286 return ConvertMap<M, T>(m);
00287 }
00288
00290
00294
00295 template<typename M1, typename M2>
00296 class AddMap : public MapBase<typename M1::Key, typename M1::Value> {
00297 const M1& m1;
00298 const M2& m2;
00299
00300 public:
00301 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
00302 typedef typename Parent::Key Key;
00303 typedef typename Parent::Value Value;
00304
00306 AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
00307 Value operator[](Key k) const {return m1[k]+m2[k];}
00308 };
00309
00311
00317 template<typename M1, typename M2>
00318 inline AddMap<M1, M2> addMap(const M1 &m1,const M2 &m2) {
00319 return AddMap<M1, M2>(m1,m2);
00320 }
00321
00323
00337 template<typename M, typename C = typename M::Value>
00338 class ShiftMap : public MapBase<typename M::Key, typename M::Value> {
00339 const M& m;
00340 C v;
00341 public:
00342 typedef MapBase<typename M::Key, typename M::Value> Parent;
00343 typedef typename Parent::Key Key;
00344 typedef typename Parent::Value Value;
00345
00347
00351 ShiftMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
00352 Value operator[](Key k) const {return m[k] + v;}
00353 };
00354
00356
00360 template<typename M, typename C>
00361 inline ShiftMap<M, C> shiftMap(const M &m,const C &v) {
00362 return ShiftMap<M, C>(m,v);
00363 }
00364
00366
00371
00372 template<typename M1, typename M2>
00373 class SubMap : public MapBase<typename M1::Key, typename M1::Value> {
00374 const M1& m1;
00375 const M2& m2;
00376 public:
00377 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
00378 typedef typename Parent::Key Key;
00379 typedef typename Parent::Value Value;
00380
00382 SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
00383 Value operator[](Key k) const {return m1[k]-m2[k];}
00384 };
00385
00387
00391 template<typename M1, typename M2>
00392 inline SubMap<M1, M2> subMap(const M1 &m1, const M2 &m2) {
00393 return SubMap<M1, M2>(m1, m2);
00394 }
00395
00397
00403
00404 template<typename M1, typename M2>
00405 class MulMap : public MapBase<typename M1::Key, typename M1::Value> {
00406 const M1& m1;
00407 const M2& m2;
00408 public:
00409 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
00410 typedef typename Parent::Key Key;
00411 typedef typename Parent::Value Value;
00412
00414 MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
00415 Value operator[](Key k) const {return m1[k]*m2[k];}
00416 };
00417
00419
00422 template<typename M1, typename M2>
00423 inline MulMap<M1, M2> mulMap(const M1 &m1,const M2 &m2) {
00424 return MulMap<M1, M2>(m1,m2);
00425 }
00426
00428
00442 template<typename M, typename C = typename M::Value>
00443 class ScaleMap : public MapBase<typename M::Key, typename M::Value> {
00444 const M& m;
00445 C v;
00446 public:
00447 typedef MapBase<typename M::Key, typename M::Value> Parent;
00448 typedef typename Parent::Key Key;
00449 typedef typename Parent::Value Value;
00450
00452
00456 ScaleMap(const M &_m, const C &_v ) : m(_m), v(_v) {};
00457 Value operator[](Key k) const {return v * m[k];}
00458 };
00459
00461
00465 template<typename M, typename C>
00466 inline ScaleMap<M, C> scaleMap(const M &m,const C &v) {
00467 return ScaleMap<M, C>(m,v);
00468 }
00469
00471
00476
00477 template<typename M1, typename M2>
00478 class DivMap : public MapBase<typename M1::Key, typename M1::Value> {
00479 const M1& m1;
00480 const M2& m2;
00481 public:
00482 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
00483 typedef typename Parent::Key Key;
00484 typedef typename Parent::Value Value;
00485
00487 DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
00488 Value operator[](Key k) const {return m1[k]/m2[k];}
00489 };
00490
00492
00495 template<typename M1, typename M2>
00496 inline DivMap<M1, M2> divMap(const M1 &m1,const M2 &m2) {
00497 return DivMap<M1, M2>(m1,m2);
00498 }
00499
00501
00516
00517 template <typename M1, typename M2>
00518 class ComposeMap : public MapBase<typename M2::Key, typename M1::Value> {
00519 const M1& m1;
00520 const M2& m2;
00521 public:
00522 typedef MapBase<typename M2::Key, typename M1::Value> Parent;
00523 typedef typename Parent::Key Key;
00524 typedef typename Parent::Value Value;
00525
00527 ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
00528
00529 typename MapTraits<M1>::ConstReturnValue
00530 operator[](Key k) const {return m1[m2[k]];}
00531 };
00533
00537 template <typename M1, typename M2>
00538 inline ComposeMap<M1, M2> composeMap(const M1 &m1,const M2 &m2) {
00539 return ComposeMap<M1, M2>(m1,m2);
00540 }
00541
00543
00564
00565 template<typename M1, typename M2, typename F,
00566 typename V = typename F::result_type,
00567 typename NC = False>
00568 class CombineMap : public MapBase<typename M1::Key, V> {
00569 const M1& m1;
00570 const M2& m2;
00571 F f;
00572 public:
00573 typedef MapBase<typename M1::Key, V> Parent;
00574 typedef typename Parent::Key Key;
00575 typedef typename Parent::Value Value;
00576
00578 CombineMap(const M1 &_m1,const M2 &_m2,const F &_f)
00579 : m1(_m1), m2(_m2), f(_f) {};
00580 Value operator[](Key k) const {return f(m1[k],m2[k]);}
00581 };
00582
00584
00599 template<typename M1, typename M2, typename F, typename V>
00600 inline CombineMap<M1, M2, F, V>
00601 combineMap(const M1& m1,const M2& m2, const F& f) {
00602 return CombineMap<M1, M2, F, V>(m1,m2,f);
00603 }
00604
00605 template<typename M1, typename M2, typename F>
00606 inline CombineMap<M1, M2, F, typename F::result_type>
00607 combineMap(const M1& m1, const M2& m2, const F& f) {
00608 return combineMap<M1, M2, F, typename F::result_type>(m1,m2,f);
00609 }
00610
00611 template<typename M1, typename M2, typename K1, typename K2, typename V>
00612 inline CombineMap<M1, M2, V (*)(K1, K2), V>
00613 combineMap(const M1 &m1, const M2 &m2, V (*f)(K1, K2)) {
00614 return combineMap<M1, M2, V (*)(K1, K2), V>(m1,m2,f);
00615 }
00616
00618
00624
00625 template<typename M>
00626 class NegMap : public MapBase<typename M::Key, typename M::Value> {
00627 const M& m;
00628 public:
00629 typedef MapBase<typename M::Key, typename M::Value> Parent;
00630 typedef typename Parent::Key Key;
00631 typedef typename Parent::Value Value;
00632
00634 NegMap(const M &_m) : m(_m) {};
00635 Value operator[](Key k) const {return -m[k];}
00636 };
00637
00639
00642 template <typename M>
00643 inline NegMap<M> negMap(const M &m) {
00644 return NegMap<M>(m);
00645 }
00646
00647
00649
00669
00670
00671 template<typename M>
00672 class AbsMap : public MapBase<typename M::Key, typename M::Value> {
00673 const M& m;
00674 public:
00675 typedef MapBase<typename M::Key, typename M::Value> Parent;
00676 typedef typename Parent::Key Key;
00677 typedef typename Parent::Value Value;
00678
00680 AbsMap(const M &_m) : m(_m) {};
00681 Value operator[](Key k) const {
00682 Value tmp = m[k];
00683 return tmp >= 0 ? tmp : -tmp;
00684 }
00685
00686 };
00687
00689
00692 template<typename M>
00693 inline AbsMap<M> absMap(const M &m) {
00694 return AbsMap<M>(m);
00695 }
00696
00698
00708
00709
00710 template<typename F,
00711 typename K = typename F::argument_type,
00712 typename V = typename F::result_type,
00713 typename NC = False>
00714 class FunctorMap : public MapBase<K, V> {
00715 F f;
00716 public:
00717 typedef MapBase<K, V> Parent;
00718 typedef typename Parent::Key Key;
00719 typedef typename Parent::Value Value;
00720
00722 FunctorMap(const F &_f) : f(_f) {}
00723
00724 Value operator[](Key k) const { return f(k);}
00725 };
00726
00728
00733 template<typename K, typename V, typename F> inline
00734 FunctorMap<F, K, V> functorMap(const F &f) {
00735 return FunctorMap<F, K, V>(f);
00736 }
00737
00738 template <typename F> inline
00739 FunctorMap<F, typename F::argument_type, typename F::result_type>
00740 functorMap(const F &f) {
00741 return FunctorMap<F, typename F::argument_type,
00742 typename F::result_type>(f);
00743 }
00744
00745 template <typename K, typename V> inline
00746 FunctorMap<V (*)(K), K, V> functorMap(V (*f)(K)) {
00747 return FunctorMap<V (*)(K), K, V>(f);
00748 }
00749
00750
00752
00759
00760 template <typename M>
00761 class MapFunctor : public MapBase<typename M::Key, typename M::Value> {
00762 const M& m;
00763 public:
00764 typedef MapBase<typename M::Key, typename M::Value> Parent;
00765 typedef typename Parent::Key Key;
00766 typedef typename Parent::Value Value;
00767
00769 typedef typename M::Key argument_type;
00771 typedef typename M::Value result_type;
00772
00774 MapFunctor(const M &_m) : m(_m) {};
00776 Value operator()(Key k) const {return m[k];}
00778 Value operator[](Key k) const {return m[k];}
00779 };
00780
00782
00785 template<typename M>
00786 inline MapFunctor<M> mapFunctor(const M &m) {
00787 return MapFunctor<M>(m);
00788 }
00789
00790
00792
00801
00802 template<typename M1, typename M2>
00803 class ForkMap : public MapBase<typename M1::Key, typename M1::Value> {
00804 const M1& m1;
00805 const M2& m2;
00806 public:
00807 typedef MapBase<typename M1::Key, typename M1::Value> Parent;
00808 typedef typename Parent::Key Key;
00809 typedef typename Parent::Value Value;
00810
00812 ForkMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
00813 Value operator[](Key k) const {return m1[k];}
00814
00815 };
00816
00818
00824 template <typename M1, typename M2>
00825 inline ForkMap<M1, M2> forkMap(const M1 &m1,const M2 &m2) {
00826 return ForkMap<M1, M2>(m1,m2);
00827 }
00828
00829
00830
00831
00832
00834
00840
00841 template <typename M>
00842 class NotMap : public MapBase<typename M::Key, bool> {
00843 const M& m;
00844 public:
00845 typedef MapBase<typename M::Key, bool> Parent;
00846 typedef typename Parent::Key Key;
00847 typedef typename Parent::Value Value;
00848
00850 NotMap(const M &_m) : m(_m) {};
00851 Value operator[](Key k) const {return !m[k];}
00852 };
00853
00855
00858 template <typename M>
00859 inline NotMap<M> notMap(const M &m) {
00860 return NotMap<M>(m);
00861 }
00862
00869 template <typename _Iterator>
00870 class StoreBoolMap {
00871 public:
00872 typedef _Iterator Iterator;
00873
00874 typedef typename std::iterator_traits<Iterator>::value_type Key;
00875 typedef bool Value;
00876
00878 StoreBoolMap(Iterator it) : _begin(it), _end(it) {}
00879
00881 Iterator begin() const {
00882 return _begin;
00883 }
00884
00886 Iterator end() const {
00887 return _end;
00888 }
00889
00891 void set(const Key& key, Value value) {
00892 if (value) {
00893 *_end++ = key;
00894 }
00895 }
00896
00897 private:
00898 Iterator _begin, _end;
00899 };
00900
00907 template <typename Container>
00908 class BackInserterBoolMap {
00909 public:
00910 typedef typename Container::value_type Key;
00911 typedef bool Value;
00912
00914 BackInserterBoolMap(Container& _container) : container(_container) {}
00915
00917 void set(const Key& key, Value value) {
00918 if (value) {
00919 container.push_back(key);
00920 }
00921 }
00922
00923 private:
00924 Container& container;
00925 };
00926
00933 template <typename Container>
00934 class FrontInserterBoolMap {
00935 public:
00936 typedef typename Container::value_type Key;
00937 typedef bool Value;
00938
00940 FrontInserterBoolMap(Container& _container) : container(_container) {}
00941
00943 void set(const Key& key, Value value) {
00944 if (value) {
00945 container.push_front(key);
00946 }
00947 }
00948
00949 private:
00950 Container& container;
00951 };
00952
00959 template <typename Container>
00960 class InserterBoolMap {
00961 public:
00962 typedef typename Container::value_type Key;
00963 typedef bool Value;
00964
00966 InserterBoolMap(Container& _container) : container(_container) {}
00967
00969 void set(const Key& key, Value value) {
00970 if (value) {
00971 container.insert(key);
00972 }
00973 }
00974
00975 private:
00976 Container& container;
00977 };
00978
00984 template <typename Map>
00985 class FillBoolMap {
00986 public:
00987 typedef typename Map::Key Key;
00988 typedef bool Value;
00989
00991 FillBoolMap(Map& _map, const typename Map::Value& _fill)
00992 : map(_map), fill(_fill) {}
00993
00995 FillBoolMap(Map& _map)
00996 : map(_map), fill() {}
00997
00999 typename Map::Value fillValue() const {
01000 return fill;
01001 }
01002
01004 void fillValue(const typename Map::Value& _fill) {
01005 fill = _fill;
01006 }
01007
01009 void set(const Key& key, Value value) {
01010 if (value) {
01011 map.set(key, fill);
01012 }
01013 }
01014
01015 private:
01016 Map& map;
01017 typename Map::Value fill;
01018 };
01019
01020
01026 template <typename Map>
01027 class SettingOrderBoolMap {
01028 public:
01029 typedef typename Map::Key Key;
01030 typedef bool Value;
01031
01033 SettingOrderBoolMap(Map& _map)
01034 : map(_map), counter(0) {}
01035
01037 int num() const {
01038 return counter;
01039 }
01040
01042 void set(const Key& key, Value value) {
01043 if (value) {
01044 map.set(key, counter++);
01045 }
01046 }
01047
01048 private:
01049 Map& map;
01050 int counter;
01051 };
01052
01054 }
01055
01056 #endif // LEMON_MAPS_H