maps.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
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   //\todo to document later
00127   template<typename T, T v>
00128   struct Const { };
00129 
00130   //\todo to document later
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       //FIXME; 
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     //    void set(Key k, const Value &v) {m1.set(k,v); m2.set(k,v);}
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   /* ************* BOOL MAPS ******************* */
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

Generated on Fri Feb 3 18:39:12 2006 for LEMON by  doxygen 1.4.6