00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054 #ifndef itk_emulation_hash_map_h
00055 #define itk_emulation_hash_map_h
00056
00057 #if defined(_MSC_VER)
00058 #pragma warning ( disable : 4786 )
00059 #endif
00060
00061 #if (defined(__GNUC__) && (((__GNUC__==3) && (__GNUC_MINOR__>=1) || (__GNUC__>3) ) || ( (__GNUC__==4) && defined(__INTEL_COMPILER) ) )) || (defined(__IBMCPP__) && __IBMCPP__ >= 600)
00062
00063
00064 #include <ext/hash_map>
00065
00066 namespace itk
00067 {
00068 using __gnu_cxx::hash;
00069 using __gnu_cxx::hash_map;
00070 using __gnu_cxx::hash_multimap;
00071 }
00072
00073 #else
00074
00075 #include "itk_hashtable.h"
00076 #include "itk_alloc.h"
00077
00078
00079
00080 #if defined(__MWERKS__)
00081 #include "vcl_functional.h"
00082 #endif
00083
00084 #include "vcl_compiler.h"
00085
00086
00087 namespace itk
00088 {
00089
00090 # define VCL_IMPORT_CONTAINER_TYPEDEFS(super) \
00091 typedef typename super::value_type value_type; \
00092 typedef typename super::reference reference; \
00093 typedef typename super::size_type size_type; \
00094 typedef typename super::const_reference const_reference; \
00095 typedef typename super::difference_type difference_type;
00096
00097 # define VCL_IMPORT_ITERATORS(super) \
00098 typedef typename super::iterator iterator; \
00099 typedef typename super::const_iterator const_iterator;
00100
00101 # define VCL_IMPORT_REVERSE_ITERATORS(super) \
00102 typedef typename super::const_reverse_iterator const_reverse_iterator; \
00103 typedef typename super::reverse_iterator reverse_iterator;
00104
00105 template <class Key, class T, class HashFcn, class EqualKey, class Alloc>
00106 class hash_map;
00107 template <class Key, class T, class HashFcn, class EqualKey, class Alloc>
00108 class hash_multimap;
00109
00110 template <class Key, class T, class HashFcn, class EqualKey, class Alloc>
00111 bool operator==(const hash_map<Key, T, HashFcn, EqualKey, Alloc>&,
00112 const hash_map<Key, T, HashFcn, EqualKey, Alloc>&);
00113 template <class Key, class T, class HashFcn, class EqualKey, class Alloc>
00114 bool operator==(const hash_multimap<Key, T, HashFcn, EqualKey, Alloc>&,
00115 const hash_multimap<Key, T, HashFcn, EqualKey, Alloc>&);
00116
00120 template <class Key, class T,
00121 VCL_DFL_TMPL_PARAM_STLDECL(HashFcn,hash<Key>),
00122 VCL_DFL_TMPL_PARAM_STLDECL(EqualKey,std::equal_to<Key>),
00123 VCL_DFL_TYPE_PARAM_STLDECL(Alloc,std::allocator<char> ) >
00124 class hash_map
00125 {
00126 private:
00127 typedef std::select1st<std::pair<const Key, T> > sel1st;
00128 typedef hashtable<std::pair<const Key, T>, Key, HashFcn, sel1st, EqualKey, Alloc> ht;
00129 typedef hash_map<Key, T, HashFcn, EqualKey, Alloc> self;
00130 public:
00131 VCL_IMPORT_CONTAINER_TYPEDEFS(ht)
00132 VCL_IMPORT_ITERATORS(ht)
00133 typedef typename ht::key_type key_type;
00134 typedef typename ht::hasher hasher;
00135 typedef typename ht::key_equal key_equal;
00136 typedef T data_type;
00137 typedef typename ht::pointer pointer;
00138 typedef typename ht::const_pointer const_pointer;
00139 private:
00140 ht rep;
00141
00142 public:
00143 hasher hash_funct() const { return rep.hash_funct(); }
00144 key_equal key_eq() const { return rep.key_eq(); }
00145
00146 public:
00147 hash_map() : rep(100, hasher(), key_equal()) {}
00148 hash_map(size_type n) : rep(n, hasher(), key_equal()) {}
00149 hash_map(size_type n, const hasher& hf) : rep(n, hf, key_equal()) {}
00150 hash_map(size_type n, const hasher& hf, const key_equal& eql)
00151 : rep(n, hf, eql) {}
00152
00153 hash_map(const value_type* f, const value_type* l)
00154 : rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); }
00155 hash_map(const value_type* f, const value_type* l, size_type n)
00156 : rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); }
00157 hash_map(const value_type* f, const value_type* l, size_type n,
00158 const hasher& hf)
00159 : rep(n, hf, key_equal()) { rep.insert_unique(f, l); }
00160 hash_map(const value_type* f, const value_type* l, size_type n,
00161 const hasher& hf, const key_equal& eql)
00162 : rep(n, hf, eql) { rep.insert_unique(f, l); }
00163
00164 hash_map(const_iterator f, const_iterator l)
00165 : rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); }
00166 hash_map(const_iterator f, const_iterator l, size_type n)
00167 : rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); }
00168 hash_map(const_iterator f, const_iterator l, size_type n,
00169 const hasher& hf)
00170 : rep(n, hf, key_equal()) { rep.insert_unique(f, l); }
00171 hash_map(const_iterator f, const_iterator l, size_type n,
00172 const hasher& hf, const key_equal& eql)
00173 : rep(n, hf, eql) { rep.insert_unique(f, l); }
00174
00175 public:
00176 size_type size() const { return rep.size(); }
00177 size_type max_size() const { return rep.max_size(); }
00178 bool empty() const { return rep.empty(); }
00179 void swap(self& hs) { rep.swap(hs.rep); }
00180 #ifndef __BORLANDC__
00181 friend bool operator==VCL_NULL_TMPL_ARGS(const hash_map<Key,T,HashFcn,EqualKey,Alloc>&,
00182 const hash_map<Key,T,HashFcn,EqualKey,Alloc>&);
00183 #endif
00184 iterator begin() { return rep.begin(); }
00185 iterator end() { return rep.end(); }
00186 const_iterator begin() const { return rep.begin(); }
00187 const_iterator end() const { return rep.end(); }
00188
00189 public:
00190 std::pair<iterator, bool> insert(const value_type& obj)
00191 { return rep.insert_unique(obj); }
00192 void insert(const value_type* f, const value_type* l) { rep.insert_unique(f,l); }
00193 void insert(const_iterator f, const_iterator l) { rep.insert_unique(f, l); }
00194 std::pair<iterator, bool> insert_noresize(const value_type& obj)
00195 { return rep.insert_unique_noresize(obj); }
00196
00197 iterator find(const key_type& key) { return rep.find(key); }
00198 const_iterator find(const key_type& key) const { return rep.find(key); }
00199
00200 T& operator[](const key_type& key)
00201 {
00202 value_type val(key, T());
00203 return rep.find_or_insert(val).second;
00204 }
00205
00206 size_type count(const key_type& key) const { return rep.count(key); }
00207
00208 std::pair<iterator, iterator> equal_range(const key_type& key)
00209 { return rep.equal_range(key); }
00210 std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
00211 { return rep.equal_range(key); }
00212
00213 size_type erase(const key_type& key) {return rep.erase(key); }
00214 void erase(iterator it) { rep.erase(it); }
00215 void erase(iterator f, iterator l) { rep.erase(f, l); }
00216 void clear() { rep.clear(); }
00217
00218 public:
00219 void resize(size_type hint) { rep.resize(hint); }
00220 size_type bucket_count() const { return rep.bucket_count(); }
00221 size_type max_bucket_count() const { return rep.max_bucket_count(); }
00222 size_type elems_in_bucket(size_type n) const
00223 { return rep.elems_in_bucket(n); }
00224 };
00225
00226
00227 template <class Key, class T, VCL_DFL_TMPL_PARAM_STLDECL(HashFcn,hash<Key>),
00228 VCL_DFL_TMPL_PARAM_STLDECL(EqualKey,std::equal_to<Key>),
00229 VCL_DFL_TYPE_PARAM_STLDECL(Alloc,std::allocator<char> ) >
00230 class hash_multimap
00231 {
00232 private:
00233 typedef hashtable<std::pair<const Key, T>, Key, HashFcn,
00234 std::select1st<std::pair<const Key, T> >, EqualKey, Alloc> ht;
00235 typedef hash_multimap<Key, T, HashFcn, EqualKey, Alloc> self;
00236 public:
00237 VCL_IMPORT_CONTAINER_TYPEDEFS(ht)
00238 VCL_IMPORT_ITERATORS(ht)
00239 typedef typename ht::key_type key_type;
00240 typedef typename ht::hasher hasher;
00241 typedef typename ht::key_equal key_equal;
00242 typedef T data_type;
00243 typedef typename ht::pointer pointer;
00244 typedef typename ht::const_pointer const_pointer;
00245
00246 hasher hash_funct() const { return rep.hash_funct(); }
00247 key_equal key_eq() const { return rep.key_eq(); }
00248 private:
00249 ht rep;
00250
00251 public:
00252 hash_multimap() : rep(100, hasher(), key_equal()) {}
00253 hash_multimap(size_type n) : rep(n, hasher(), key_equal()) {}
00254 hash_multimap(size_type n, const hasher& hf) : rep(n, hf, key_equal()) {}
00255 hash_multimap(size_type n, const hasher& hf, const key_equal& eql)
00256 : rep(n, hf, eql) {}
00257
00258 hash_multimap(const value_type* f, const value_type* l)
00259 : rep(100, hasher(), key_equal()) { rep.insert_equal(f, l); }
00260 hash_multimap(const value_type* f, const value_type* l, size_type n)
00261 : rep(n, hasher(), key_equal()) { rep.insert_equal(f, l); }
00262 hash_multimap(const value_type* f, const value_type* l, size_type n,
00263 const hasher& hf)
00264 : rep(n, hf, key_equal()) { rep.insert_equal(f, l); }
00265 hash_multimap(const value_type* f, const value_type* l, size_type n,
00266 const hasher& hf, const key_equal& eql)
00267 : rep(n, hf, eql) { rep.insert_equal(f, l); }
00268
00269 hash_multimap(const_iterator f, const_iterator l)
00270 : rep(100, hasher(), key_equal()) { rep.insert_equal(f, l); }
00271 hash_multimap(const_iterator f, const_iterator l, size_type n)
00272 : rep(n, hasher(), key_equal()) { rep.insert_equal(f, l); }
00273 hash_multimap(const_iterator f, const_iterator l, size_type n,
00274 const hasher& hf)
00275 : rep(n, hf, key_equal()) { rep.insert_equal(f, l); }
00276 hash_multimap(const_iterator f, const_iterator l, size_type n,
00277 const hasher& hf, const key_equal& eql)
00278 : rep(n, hf, eql) { rep.insert_equal(f, l); }
00279
00280 public:
00281 size_type size() const { return rep.size(); }
00282 size_type max_size() const { return rep.max_size(); }
00283 bool empty() const { return rep.empty(); }
00284 void swap(self& hs) { rep.swap(hs.rep); }
00285 friend bool operator==VCL_NULL_TMPL_ARGS(const hash_multimap<Key,T,HashFcn,EqualKey,Alloc>&,
00286 const hash_multimap<Key,T,HashFcn,EqualKey,Alloc>&);
00287
00288 iterator begin() { return rep.begin(); }
00289 iterator end() { return rep.end(); }
00290 const_iterator begin() const { return rep.begin(); }
00291 const_iterator end() const { return rep.end(); }
00292
00293 public:
00294 iterator insert(const value_type& obj) { return rep.insert_equal(obj); }
00295 void insert(const value_type* f, const value_type* l) { rep.insert_equal(f,l); }
00296 void insert(const_iterator f, const_iterator l) { rep.insert_equal(f, l); }
00297 iterator insert_noresize(const value_type& obj)
00298 { return rep.insert_equal_noresize(obj); }
00299
00300 iterator find(const key_type& key) { return rep.find(key); }
00301 const_iterator find(const key_type& key) const { return rep.find(key); }
00302
00303 size_type count(const key_type& key) const { return rep.count(key); }
00304
00305 std::pair<iterator, iterator> equal_range(const key_type& key)
00306 { return rep.equal_range(key); }
00307 std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
00308 { return rep.equal_range(key); }
00309
00310 size_type erase(const key_type& key) {return rep.erase(key); }
00311 void erase(iterator it) { rep.erase(it); }
00312 void erase(iterator f, iterator l) { rep.erase(f, l); }
00313 void clear() { rep.clear(); }
00314
00315 public:
00316 void resize(size_type hint) { rep.resize(hint); }
00317 size_type bucket_count() const { return rep.bucket_count(); }
00318 size_type max_bucket_count() const { return rep.max_bucket_count(); }
00319 size_type elems_in_bucket(size_type n) const
00320 { return rep.elems_in_bucket(n); }
00321 };
00322
00323 template <class Key, class T, class HashFcn, class EqualKey, class Alloc>
00324 inline bool operator==(const hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm1,
00325 const hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm2)
00326 {
00327 return hm1.rep == hm2.rep;
00328 }
00329
00330 template <class Key, class T, class HashFcn, class EqualKey, class Alloc>
00331 inline bool operator==(const hash_multimap<Key, T, HashFcn, EqualKey, Alloc>& hm1,
00332 const hash_multimap<Key, T, HashFcn, EqualKey, Alloc>& hm2)
00333 {
00334 return hm1.rep == hm2.rep;
00335 }
00336
00337
00338 #define HASH_MAP_INSTANTIATE \
00339 extern "please include emulation/hash_map.txx instead"
00340
00341 }
00342
00343 #endif
00344
00345 #endif // itk_emulation_hash_map_h
00346