BALL: hashMap.h Source File

00001 // -*- Mode: C++; tab-width: 2; -*-
00002 // vi: set ts=2:
00003 //
00004 
00005 #ifndef BALL_DATATYPE_HASHMAP_H
00006 #define BALL_DATATYPE_HASHMAP_H
00007 
00008 #ifndef BALL_COMMON_H
00009 # include <BALL/common.h>
00010 #endif
00011 
00012 #ifndef BALL_COMMON_HASH_H
00013 # include <BALL/COMMON/hash.h>
00014 #endif
00015 
00016 #ifndef BALL_DATATYPE_TRIPLE_H
00017 # include <BALL/DATATYPE/triple.h>
00018 #endif
00019 
00020 #ifndef BALL_DATATYPE_QUADRUPLE_H
00021 # include <BALL/DATATYPE/quadruple.h>
00022 #endif
00023 
00024 #include <utility>
00025 #include <algorithm>
00026 
00027 #ifdef BALL_HAS_UNORDERED_MAP
00028 
00029 #if defined(BALL_HAS_STD_UNORDERED_MAP)
00030 # include <unordered_map>
00031 #elif defined(BALL_HAS_TR1_UNORDERED_MAP)
00032 # include <tr1/unordered_map>
00033 #elif defined(BALL_HAS_BOOST_UNORDERED_MAP)
00034 # include <boost/unordered_map.hpp>
00035 #endif
00036 
00037 #elif defined(BALL_HAS_HASH_MAP)
00038 #if defined(BALL_EXT_INCLUDE_PREFIX)
00039 # include <ext/hash_map>
00040 # include <ext/hash_fun.h>
00041 #else
00042 # include <hash_map>
00043 # include <hash_fun.h>
00044 #endif
00045 #else
00046 # include <map>
00047 #endif
00048 
00049 #if defined(BALL_HAS_UNORDERED_MAP) && !defined(BALL_HAS_BOOST_UNORDERED_MAP)
00050 
00051 #ifdef BALL_EXTEND_HASH_IN_STD_NS
00052 namespace std
00053 {
00054 #endif // BALL_EXTEND_HASH_IN_STD_NS
00055 
00056 #ifdef BALL_HAS_TR1_UNORDERED_MAP
00057   namespace tr1
00058   {
00059 #endif // BALL_HAS_TR1_UNORDERED_MAP
00060     
00061     // borrowed from boost
00062     template<typename T> 
00063     void hash_combine_ala_boost(size_t & seed, T const & v)
00064     {
00065       hash<T> h;
00066       seed ^= h(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
00067     }
00068 
00069     template<class A, class B>
00070     struct hash<pair<A, B> > : public std::unary_function<pair<A,B>, size_t>
00071     {
00072       inline size_t
00073       operator()(pair<A, B> p) const
00074       {
00075         size_t seed = 0;
00076         hash_combine_ala_boost(seed, p.first);
00077         hash_combine_ala_boost(seed, p.second);
00078 
00079         return seed;
00080       }
00081     };
00082 
00083     template <class A, class B, class C>
00084     struct hash< ::BALL::Triple<A, B, C> > : public std::unary_function< ::BALL::Triple<A, B, C>, size_t>
00085     {
00086       inline size_t
00087       operator()(::BALL::Triple<A, B, C> t) const
00088       {
00089         size_t seed = 0;
00090         hash_combine_ala_boost(seed, t.first);
00091         hash_combine_ala_boost(seed, t.second);
00092         hash_combine_ala_boost(seed, t.third);
00093 
00094         return seed;
00095       }
00096     };
00097 
00098     template <class A, class B, class C, class D>
00099     struct hash< ::BALL::Quadruple<A, B, C, D> > : public std::unary_function< const ::BALL::Quadruple<A, B, C, D>, size_t> 
00100     {
00101       inline size_t
00102       operator()( ::BALL::Quadruple<A, B, C, D> q) const
00103       {
00104         size_t seed = 0;
00105         hash_combine_ala_boost(seed, q.first);
00106         hash_combine_ala_boost(seed, q.second);
00107         hash_combine_ala_boost(seed, q.third);
00108         hash_combine_ala_boost(seed, q.fourth);
00109 
00110         return seed;
00111       }
00112     };
00113 
00114 #ifndef BALL_COMPILER_MSVC
00115     template<>
00116     struct hash<const ::BALL::String&> : public std::unary_function<const ::BALL::String &, size_t>
00117     {
00118       inline size_t
00119       operator()(const ::BALL::String& s) const
00120       {
00121         hash<const string&> h;
00122         return h(s);
00123       }
00124     };
00125 #endif
00126 
00127     template<>
00128     struct hash< ::BALL::String > : public std::unary_function< ::BALL::String, size_t >
00129     {
00130       inline size_t
00131       operator()( ::BALL::String s) const
00132       {
00133         hash<string> h;
00134         return h(s);
00135       }
00136     };
00137 #ifdef BALL_HAS_TR1_UNORDERED_MAP
00138   }
00139 #endif // BALL_HAS_TR1_UNORDERED_MAP
00140 
00141 #ifdef BALL_EXTEND_HASH_IN_STD_NS
00142 }
00143 #endif // BALL_EXTEND_HASH_IN_STD_NS
00144 
00145 #endif // if defined(BALL_HAS_UNORDERED_MAP) && !defined(BALL_HAS_BOOST_UNORDERED_MAP)
00146 
00147 #ifdef BALL_HAS_HASH_MAP
00148 namespace BALL_MAP_NAMESPACE
00149 {
00150   template<class T>
00151   struct hash<T*>
00152   {
00153     size_t operator()(const T* x) const { return (size_t)x; }
00154   };
00155 
00156   template<>
00157   struct hash<BALL::String>
00158   {
00159     size_t operator () (const BALL::String& s) const {return __stl_hash_string(s.c_str());}
00160   };
00161 
00162 #ifdef BALL_NEEDS_LONGSIZE_HASH
00163   template<>
00164   struct hash<BALL::LongSize>
00165   {
00166     size_t operator()(BALL::LongSize x) const { return (size_t)x; }
00167   };
00168 #endif
00169 }
00170 #endif // BALL_HAS_HASH_MAP
00171 
00172 namespace BALL
00173 {
00179   template <class Key, class T>
00180   class HashMap
00181     : public BALL_MAP_NAME
00182   {
00183     public:
00184 
00190       class IllegalKey
00191         : public Exception::GeneralException
00192       {
00193         public:
00194         IllegalKey(const char* file, int line)
00195           : Exception::GeneralException(file, line)
00196         {
00197         }
00198       };
00199       
00201 
00202       typedef BALL_MAP_NAME Base;
00203       typedef typename Base::value_type ValueType;
00204       typedef Key KeyType;
00205       typedef typename Base::value_type* PointerType;
00206       typedef typename Base::iterator Iterator;
00207       typedef typename Base::const_iterator ConstIterator;
00209 
00211       inline bool has(const Key& key) const
00212       {
00213         return Base::find(key)!=Base::end();
00214       }
00215 
00221       const T& operator [] (const Key& key) const;
00222 
00224       T& operator [] (const Key& key);
00225       
00227       bool operator == (const HashMap<Key, T>& rhs) const;
00228       
00229       Size size() const { return BALL_MAP_NAME::size(); }
00230   };
00231   
00232   //******************************************************************************************
00233   // Implementations of template methods
00234   //******************************************************************************************
00235   
00236   template <class Key, class T>
00237   const T& HashMap<Key, T>::operator [] (const Key& key) const
00238   {
00239     ConstIterator it = find(key);
00240     if (it == Base::end())
00241     {
00242       throw IllegalKey(__FILE__, __LINE__);
00243     }
00244     else
00245     {
00246       return it->second;
00247     }
00248   }
00249 
00250 
00251   template <class Key, class T>
00252   bool HashMap<Key, T>::operator == (const HashMap<Key, T>& rhs) const
00253   {
00254     // No equality if sizes differ.
00255     if (size() != rhs.size()) 
00256     {
00257       return false; 
00258     }
00259 
00260     // Equality if bothe have the same size and every element of lhs is 
00261     // is contained in lhs. Testing the other way round is obviously
00262     // unnecessary.
00263     ConstIterator it(BALL_MAP_NAME::begin());
00264     for (; it != BALL_MAP_NAME::end(); ++it)
00265     {
00266       if (!rhs.has(it->first)) return false;
00267     }
00268     return true;
00269   }
00270   
00271   template <class Key, class T>
00272   T& HashMap<Key, T>::operator [] (const Key& key)
00273     
00274   {
00275     Iterator it = find(key);
00276     if (it == Base::end())
00277     {
00278       it = insert(ValueType(key, T())).first;
00279     }
00280     return it->second;
00281   }
00282 
00283 } // namespace BALL
00284 
00285 #endif // BALL_DATATYPE_HASHMAP_H