BALL
1.4.1
|
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