00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef LEMON_MAPS_H
00018 #define LEMON_MAPS_H
00019
00020 #include<math.h>
00021
00028
00029 #include <map>
00030
00031 namespace lemon {
00032
00035
00037
00040 template<typename K, typename T>
00041 class MapBase
00042 {
00043 public:
00045 typedef K Key;
00047 typedef T Value;
00048 };
00049
00051
00055 template<typename K, typename T>
00056 class NullMap : public MapBase<K,T>
00057 {
00058 public:
00059
00061 T operator[](const K&) const { return T(); }
00063 void set(const K&, const T&) {}
00064 };
00065
00066
00068
00072 template<typename K, typename T>
00073 class ConstMap : public MapBase<K,T>
00074 {
00075 T v;
00076 public:
00077
00079
00082 ConstMap() {}
00084
00087 ConstMap(const T &_v) : v(_v) {}
00088
00089 T operator[](const K&) const { return v; }
00090 void set(const K&, const T&) {}
00091
00092 template<typename T1>
00093 struct rebind {
00094 typedef ConstMap<K,T1> other;
00095 };
00096
00097 template<typename T1>
00098 ConstMap(const ConstMap<K,T1> &, const T &_v) : v(_v) {}
00099 };
00100
00102
00105 template<class V,class K>
00106 inline ConstMap<V,K> constMap(const K &k)
00107 {
00108 return ConstMap<V,K>(k);
00109 }
00110
00111
00112
00113 template<typename T, T v>
00114 struct Const { };
00115
00116 template<typename K, typename V, V v>
00117 class ConstMap<K, Const<V, v> > : public MapBase<K, V>
00118 {
00119 public:
00120 ConstMap() { }
00121 V operator[](const K&) const { return v; }
00122 void set(const K&, const V&) { }
00123 };
00124
00126
00131 template <typename K, typename T, typename Compare = std::less<K> >
00132 class StdMap : public std::map<K,T,Compare> {
00133 typedef std::map<K,T,Compare> parent;
00134 T v;
00135 typedef typename parent::value_type PairType;
00136
00137 public:
00138 typedef K Key;
00139 typedef T Value;
00140 typedef T& Reference;
00141 typedef const T& ConstReference;
00142
00143
00144 StdMap() : v() {}
00146 StdMap(const T& _v) : v(_v) {}
00147
00151 StdMap(const parent &m) : parent(m) {}
00156 StdMap(const parent &m, const T& _v) : parent(m), v(_v) {}
00157
00158 template<typename T1, typename Comp1>
00159 StdMap(const StdMap<Key,T1,Comp1> &m, const T &_v) {
00160
00161 }
00162
00163 Reference operator[](const Key &k) {
00164 return insert(PairType(k,v)).first -> second;
00165 }
00166 ConstReference operator[](const Key &k) const {
00167 typename parent::iterator i = lower_bound(k);
00168 if (i == parent::end() || parent::key_comp()(k, (*i).first))
00169 return v;
00170 return (*i).second;
00171 }
00172 void set(const Key &k, const T &t) {
00173 parent::operator[](k) = t;
00174 }
00175
00181 T setDefault(const T &_v) { T old=v; v=_v; return old; }
00182
00183 template<typename T1>
00184 struct rebind {
00185 typedef StdMap<Key,T1,Compare> other;
00186 };
00187 };
00188
00189
00191
00195
00196 template<class M1,class M2>
00197 class AddMap
00198 {
00199 const M1 &m1;
00200 const M2 &m2;
00201 public:
00202 typedef typename M1::Key Key;
00203 typedef typename M1::Value Value;
00204
00206
00209 AddMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
00210 Value operator[](Key k) const {return m1[k]+m2[k];}
00211 };
00212
00214
00220 template<class M1,class M2>
00221 inline AddMap<M1,M2> addMap(const M1 &m1,const M2 &m2)
00222 {
00223 return AddMap<M1,M2>(m1,m2);
00224 }
00225
00227
00241 template<class M>
00242 class ShiftMap
00243 {
00244 const M &m;
00245 typename M::Value v;
00246 public:
00247 typedef typename M::Key Key;
00248 typedef typename M::Value Value;
00249
00251
00255 ShiftMap(const M &_m,const Value &_v ) : m(_m), v(_v) {};
00256 Value operator[](Key k) const {return m[k]+v;}
00257 };
00258
00260
00264 template<class M>
00265 inline ShiftMap<M> shiftMap(const M &m,const typename M::Value &v)
00266 {
00267 return ShiftMap<M>(m,v);
00268 }
00269
00271
00276
00277 template<class M1,class M2>
00278 class SubMap
00279 {
00280 const M1 &m1;
00281 const M2 &m2;
00282 public:
00283 typedef typename M1::Key Key;
00284 typedef typename M1::Value Value;
00285
00287
00290 SubMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
00291 Value operator[](Key k) const {return m1[k]-m2[k];}
00292 };
00293
00295
00299 template<class M1,class M2>
00300 inline SubMap<M1,M2> subMap(const M1 &m1,const M2 &m2)
00301 {
00302 return SubMap<M1,M2>(m1,m2);
00303 }
00304
00306
00312
00313 template<class M1,class M2>
00314 class MulMap
00315 {
00316 const M1 &m1;
00317 const M2 &m2;
00318 public:
00319 typedef typename M1::Key Key;
00320 typedef typename M1::Value Value;
00321
00323
00326 MulMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
00327 Value operator[](Key k) const {return m1[k]*m2[k];}
00328 };
00329
00331
00334 template<class M1,class M2>
00335 inline MulMap<M1,M2> mulMap(const M1 &m1,const M2 &m2)
00336 {
00337 return MulMap<M1,M2>(m1,m2);
00338 }
00339
00341
00355 template<class M>
00356 class ScaleMap
00357 {
00358 const M &m;
00359 typename M::Value v;
00360 public:
00361 typedef typename M::Key Key;
00362 typedef typename M::Value Value;
00363
00365
00369 ScaleMap(const M &_m,const Value &_v ) : m(_m), v(_v) {};
00370 Value operator[](Key k) const {return m[k]*v;}
00371 };
00372
00374
00378 template<class M>
00379 inline ScaleMap<M> scaleMap(const M &m,const typename M::Value &v)
00380 {
00381 return ScaleMap<M>(m,v);
00382 }
00383
00385
00390
00391 template<class M1,class M2>
00392 class DivMap
00393 {
00394 const M1 &m1;
00395 const M2 &m2;
00396 public:
00397 typedef typename M1::Key Key;
00398 typedef typename M1::Value Value;
00399
00401
00404 DivMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
00405 Value operator[](Key k) const {return m1[k]/m2[k];}
00406 };
00407
00409
00412 template<class M1,class M2>
00413 inline DivMap<M1,M2> divMap(const M1 &m1,const M2 &m2)
00414 {
00415 return DivMap<M1,M2>(m1,m2);
00416 }
00417
00419
00434
00435 template<class M1,class M2>
00436 class ComposeMap
00437 {
00438 const M1 &m1;
00439 const M2 &m2;
00440 public:
00441 typedef typename M2::Key Key;
00442 typedef typename M1::Value Value;
00443
00445
00448 ComposeMap(const M1 &_m1,const M2 &_m2) : m1(_m1), m2(_m2) {};
00449 Value operator[](Key k) const {return m1[m2[k]];}
00450 };
00451
00453
00456 template<class M1,class M2>
00457 inline ComposeMap<M1,M2> composeMap(const M1 &m1,const M2 &m2)
00458 {
00459 return ComposeMap<M1,M2>(m1,m2);
00460 }
00461
00463
00469
00470 template<class M>
00471 class NegMap
00472 {
00473 const M &m;
00474 public:
00475 typedef typename M::Key Key;
00476 typedef typename M::Value Value;
00477
00479
00482 NegMap(const M &_m) : m(_m) {};
00483 Value operator[](Key k) const {return -m[k];}
00484 };
00485
00487
00490 template<class M>
00491 inline NegMap<M> negMap(const M &m)
00492 {
00493 return NegMap<M>(m);
00494 }
00495
00496
00498
00518
00519
00520 template<class M>
00521 class AbsMap
00522 {
00523 const M &m;
00524 public:
00525 typedef typename M::Key Key;
00526 typedef typename M::Value Value;
00527
00529
00532 AbsMap(const M &_m) : m(_m) {};
00533 Value operator[](Key k) const {Value tmp=m[k]; return tmp>=0?tmp:-tmp;}
00534 };
00535
00537
00540 template<class M>
00541 inline AbsMap<M> absMap(const M &m)
00542 {
00543 return AbsMap<M>(m);
00544 }
00545
00547
00557
00558
00559 template<class K,class V,class F>
00560 class FunctorMap
00561 {
00562 const F &f;
00563 public:
00564 typedef K Key;
00565 typedef V Value;
00566
00568
00571 FunctorMap(const F &_f) : f(_f) {};
00572 Value operator[](Key k) const {return f(k);}
00573 };
00574
00576
00581 template<class K,class V, class F>
00582 inline FunctorMap<K,V,F> functorMap(const F &f)
00583 {
00584 return FunctorMap<K,V,F>(f);
00585 }
00586
00588
00594
00595 template<class M>
00596 class MapFunctor
00597 {
00598 const M &m;
00599 public:
00600 typedef typename M::Key Key;
00601 typedef typename M::Value Value;
00602
00604
00607 MapFunctor(const M &_m) : m(_m) {};
00609
00612 Value operator()(Key k) const {return m[k];}
00615 Value operator[](Key k) const {return m[k];}
00616 };
00617
00619
00622 template<class M>
00623 inline MapFunctor<M> mapFunctor(const M &m)
00624 {
00625 return MapFunctor<M>(m);
00626 }
00627
00628
00630
00631 }
00632
00633
00634 #endif // LEMON_MAPS_H