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
00109 template <class Key, class T,
00110 VCL_DFL_TMPL_PARAM_STLDECL(HashFcn,hash<Key>),
00111 VCL_DFL_TMPL_PARAM_STLDECL(EqualKey,std::equal_to<Key>),
00112 VCL_DFL_TYPE_PARAM_STLDECL(Alloc,std::allocator<char> ) >
00113 class hash_map
00114 {
00115 private:
00116 typedef std::select1st<std::pair<const Key, T> > sel1st;
00117 typedef hashtable<std::pair<const Key, T>, Key, HashFcn, sel1st, EqualKey, Alloc> ht;
00118 typedef hash_map<Key, T, HashFcn, EqualKey, Alloc> self;
00119 public:
00120 VCL_IMPORT_CONTAINER_TYPEDEFS(ht)
00121 VCL_IMPORT_ITERATORS(ht)
00122 typedef typename ht::key_type key_type;
00123 typedef typename ht::hasher hasher;
00124 typedef typename ht::key_equal key_equal;
00125 typedef T data_type;
00126 typedef typename ht::pointer pointer;
00127 typedef typename ht::const_pointer const_pointer;
00128 private:
00129 ht rep;
00130
00131 public:
00132 hasher hash_funct() const { return rep.hash_funct(); }
00133 key_equal key_eq() const { return rep.key_eq(); }
00134
00135 public:
00136 hash_map() : rep(100, hasher(), key_equal()) {}
00137 hash_map(size_type n) : rep(n, hasher(), key_equal()) {}
00138 hash_map(size_type n, const hasher& hf) : rep(n, hf, key_equal()) {}
00139 hash_map(size_type n, const hasher& hf, const key_equal& eql)
00140 : rep(n, hf, eql) {}
00141
00142 hash_map(const value_type* f, const value_type* l)
00143 : rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); }
00144 hash_map(const value_type* f, const value_type* l, size_type n)
00145 : rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); }
00146 hash_map(const value_type* f, const value_type* l, size_type n,
00147 const hasher& hf)
00148 : rep(n, hf, key_equal()) { rep.insert_unique(f, l); }
00149 hash_map(const value_type* f, const value_type* l, size_type n,
00150 const hasher& hf, const key_equal& eql)
00151 : rep(n, hf, eql) { rep.insert_unique(f, l); }
00152
00153 hash_map(const_iterator f, const_iterator l)
00154 : rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); }
00155 hash_map(const_iterator f, const_iterator l, size_type n)
00156 : rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); }
00157 hash_map(const_iterator f, const_iterator l, size_type n,
00158 const hasher& hf)
00159 : rep(n, hf, key_equal()) { rep.insert_unique(f, l); }
00160 hash_map(const_iterator f, const_iterator l, size_type n,
00161 const hasher& hf, const key_equal& eql)
00162 : rep(n, hf, eql) { rep.insert_unique(f, l); }
00163
00164 public:
00165 size_type size() const { return rep.size(); }
00166 size_type max_size() const { return rep.max_size(); }
00167 bool empty() const { return rep.empty(); }
00168 void swap(self& hs) { rep.swap(hs.rep); }
00169 #ifndef __BORLANDC__
00170 friend bool operator==VCL_NULL_TMPL_ARGS(const hash_map<Key,T,HashFcn,EqualKey,Alloc>&,
00171 const hash_map<Key,T,HashFcn,EqualKey,Alloc>&);
00172 #endif
00173 iterator begin() { return rep.begin(); }
00174 iterator end() { return rep.end(); }
00175 const_iterator begin() const { return rep.begin(); }
00176 const_iterator end() const { return rep.end(); }
00177
00178 public:
00179 std::pair<iterator, bool> insert(const value_type& obj)
00180 { return rep.insert_unique(obj); }
00181 void insert(const value_type* f, const value_type* l) { rep.insert_unique(f,l); }
00182 void insert(const_iterator f, const_iterator l) { rep.insert_unique(f, l); }
00183 std::pair<iterator, bool> insert_noresize(const value_type& obj)
00184 { return rep.insert_unique_noresize(obj); }
00185
00186 iterator find(const key_type& key) { return rep.find(key); }
00187 const_iterator find(const key_type& key) const { return rep.find(key); }
00188
00189 T& operator[](const key_type& key)
00190 {
00191 value_type val(key, T());
00192 return rep.find_or_insert(val).second;
00193 }
00194
00195 size_type count(const key_type& key) const { return rep.count(key); }
00196
00197 std::pair<iterator, iterator> equal_range(const key_type& key)
00198 { return rep.equal_range(key); }
00199 std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
00200 { return rep.equal_range(key); }
00201
00202 size_type erase(const key_type& key) {return rep.erase(key); }
00203 void erase(iterator it) { rep.erase(it); }
00204 void erase(iterator f, iterator l) { rep.erase(f, l); }
00205 void clear() { rep.clear(); }
00206
00207 public:
00208 void resize(size_type hint) { rep.resize(hint); }
00209 size_type bucket_count() const { return rep.bucket_count(); }
00210 size_type max_bucket_count() const { return rep.max_bucket_count(); }
00211 size_type elems_in_bucket(size_type n) const
00212 { return rep.elems_in_bucket(n); }
00213 };
00214
00215
00216 template <class Key, class T, VCL_DFL_TMPL_PARAM_STLDECL(HashFcn,hash<Key>),
00217 VCL_DFL_TMPL_PARAM_STLDECL(EqualKey,std::equal_to<Key>),
00218 VCL_DFL_TYPE_PARAM_STLDECL(Alloc,std::allocator<char> ) >
00219 class hash_multimap
00220 {
00221 private:
00222 typedef hashtable<std::pair<const Key, T>, Key, HashFcn,
00223 std::select1st<std::pair<const Key, T> >, EqualKey, Alloc> ht;
00224 typedef hash_multimap<Key, T, HashFcn, EqualKey, Alloc> self;
00225 public:
00226 VCL_IMPORT_CONTAINER_TYPEDEFS(ht)
00227 VCL_IMPORT_ITERATORS(ht)
00228 typedef typename ht::key_type key_type;
00229 typedef typename ht::hasher hasher;
00230 typedef typename ht::key_equal key_equal;
00231 typedef T data_type;
00232 typedef typename ht::pointer pointer;
00233 typedef typename ht::const_pointer const_pointer;
00234
00235 hasher hash_funct() const { return rep.hash_funct(); }
00236 key_equal key_eq() const { return rep.key_eq(); }
00237 private:
00238 ht rep;
00239
00240 public:
00241 hash_multimap() : rep(100, hasher(), key_equal()) {}
00242 hash_multimap(size_type n) : rep(n, hasher(), key_equal()) {}
00243 hash_multimap(size_type n, const hasher& hf) : rep(n, hf, key_equal()) {}
00244 hash_multimap(size_type n, const hasher& hf, const key_equal& eql)
00245 : rep(n, hf, eql) {}
00246
00247 hash_multimap(const value_type* f, const value_type* l)
00248 : rep(100, hasher(), key_equal()) { rep.insert_equal(f, l); }
00249 hash_multimap(const value_type* f, const value_type* l, size_type n)
00250 : rep(n, hasher(), key_equal()) { rep.insert_equal(f, l); }
00251 hash_multimap(const value_type* f, const value_type* l, size_type n,
00252 const hasher& hf)
00253 : rep(n, hf, key_equal()) { rep.insert_equal(f, l); }
00254 hash_multimap(const value_type* f, const value_type* l, size_type n,
00255 const hasher& hf, const key_equal& eql)
00256 : rep(n, hf, eql) { rep.insert_equal(f, l); }
00257
00258 hash_multimap(const_iterator f, const_iterator l)
00259 : rep(100, hasher(), key_equal()) { rep.insert_equal(f, l); }
00260 hash_multimap(const_iterator f, const_iterator l, size_type n)
00261 : rep(n, hasher(), key_equal()) { rep.insert_equal(f, l); }
00262 hash_multimap(const_iterator f, const_iterator l, size_type n,
00263 const hasher& hf)
00264 : rep(n, hf, key_equal()) { rep.insert_equal(f, l); }
00265 hash_multimap(const_iterator f, const_iterator l, size_type n,
00266 const hasher& hf, const key_equal& eql)
00267 : rep(n, hf, eql) { rep.insert_equal(f, l); }
00268
00269 public:
00270 size_type size() const { return rep.size(); }
00271 size_type max_size() const { return rep.max_size(); }
00272 bool empty() const { return rep.empty(); }
00273 void swap(self& hs) { rep.swap(hs.rep); }
00274 friend bool operator==VCL_NULL_TMPL_ARGS(const hash_multimap<Key,T,HashFcn,EqualKey,Alloc>&,
00275 const hash_multimap<Key,T,HashFcn,EqualKey,Alloc>&);
00276
00277 iterator begin() { return rep.begin(); }
00278 iterator end() { return rep.end(); }
00279 const_iterator begin() const { return rep.begin(); }
00280 const_iterator end() const { return rep.end(); }
00281
00282 public:
00283 iterator insert(const value_type& obj) { return rep.insert_equal(obj); }
00284 void insert(const value_type* f, const value_type* l) { rep.insert_equal(f,l); }
00285 void insert(const_iterator f, const_iterator l) { rep.insert_equal(f, l); }
00286 iterator insert_noresize(const value_type& obj)
00287 { return rep.insert_equal_noresize(obj); }
00288
00289 iterator find(const key_type& key) { return rep.find(key); }
00290 const_iterator find(const key_type& key) const { return rep.find(key); }
00291
00292 size_type count(const key_type& key) const { return rep.count(key); }
00293
00294 std::pair<iterator, iterator> equal_range(const key_type& key)
00295 { return rep.equal_range(key); }
00296 std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
00297 { return rep.equal_range(key); }
00298
00299 size_type erase(const key_type& key) {return rep.erase(key); }
00300 void erase(iterator it) { rep.erase(it); }
00301 void erase(iterator f, iterator l) { rep.erase(f, l); }
00302 void clear() { rep.clear(); }
00303
00304 public:
00305 void resize(size_type hint) { rep.resize(hint); }
00306 size_type bucket_count() const { return rep.bucket_count(); }
00307 size_type max_bucket_count() const { return rep.max_bucket_count(); }
00308 size_type elems_in_bucket(size_type n) const
00309 { return rep.elems_in_bucket(n); }
00310 };
00311
00312 template <class Key, class T, class HashFcn, class EqualKey, class Alloc>
00313 inline bool operator==(const hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm1,
00314 const hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm2)
00315 {
00316 return hm1.rep == hm2.rep;
00317 }
00318
00319 template <class Key, class T, class HashFcn, class EqualKey, class Alloc>
00320 inline bool operator==(const hash_multimap<Key, T, HashFcn, EqualKey, Alloc>& hm1,
00321 const hash_multimap<Key, T, HashFcn, EqualKey, Alloc>& hm2)
00322 {
00323 return hm1.rep == hm2.rep;
00324 }
00325
00326
00327 #define HASH_MAP_INSTANTIATE \
00328 extern "please include emulation/hash_map.txx instead"
00329
00330 }
00331
00332 #endif
00333
00334 #endif // itk_emulation_hash_map_h
00335