ITK: itk_hash_map.h Source File

00001 /*========================================================================= 00002 00003 Program: Insight Segmentation & Registration Toolkit 00004 Module: $RCSfile: itk_hash_map.h,v $ 00005 Language: C++ 00006 Date: $Date: 2003/09/15 20:40:36 $ 00007 Version: $Revision: 1.8 $ 00008 00009 Copyright (c) Insight Software Consortium. All rights reserved. 00010 See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details. 00011 00012 This software is distributed WITHOUT ANY WARRANTY; without even 00013 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 00014 PURPOSE. See the above copyright notices for more information. 00015 00016 =========================================================================*/ 00017 /* 00018 * Copyright (c) 1996 00019 * Silicon Graphics Computer Systems, Inc. 00020 * 00021 * Permission to use, copy, modify, distribute and sell this software 00022 * and its documentation for any purpose is hereby granted without fee, 00023 * provided that the above copyright notice appear in all copies and 00024 * that both that copyright notice and this permission notice appear 00025 * in supporting documentation. Silicon Graphics makes no 00026 * representations about the suitability of this software for any 00027 * purpose. It is provided "as is" without express or implied warranty. 00028 * 00029 * 00030 * Copyright (c) 1994 00031 * Hewlett-Packard Company 00032 * 00033 * Permission to use, copy, modify, distribute and sell this software 00034 * and its documentation for any purpose is hereby granted without fee, 00035 * provided that the above copyright notice appear in all copies and 00036 * that both that copyright notice and this permission notice appear 00037 * in supporting documentation. Hewlett-Packard Company makes no 00038 * representations about the suitability of this software for any 00039 * purpose. It is provided "as is" without express or implied warranty. 00040 * 00041 * Copyright (c) 1997 00042 * Moscow Center for SPARC Technology 00043 * 00044 * Permission to use, copy, modify, distribute and sell this software 00045 * and its documentation for any purpose is hereby granted without fee, 00046 * provided that the above copyright notice appear in all copies and 00047 * that both that copyright notice and this permission notice appear 00048 * in supporting documentation. Moscow Center for SPARC Technology makes no 00049 * representations about the suitability of this software for any 00050 * purpose. It is provided "as is" without express or implied warranty. 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)) 00062 #include <ext/hash_map> 00063 00064 namespace itk 00065 { 00066 using __gnu_cxx::hash; 00067 using __gnu_cxx::hash_map; 00068 using __gnu_cxx::hash_multimap; 00069 } 00070 00071 #else 00072 00073 #include "itk_hashtable.h" 00074 #include "itk_alloc.h" 00075 00076 00077 // The following is required for CodeWarrior 00078 #if defined(__MWERKS__) 00079 #include "vcl_functional.h" 00080 #endif 00081 00082 00083 namespace itk 00084 { 00085 00086 # define VCL_IMPORT_CONTAINER_TYPEDEFS(super) \ 00087 typedef typename super::value_type value_type; \ 00088 typedef typename super::reference reference; \ 00089 typedef typename super::size_type size_type; \ 00090 typedef typename super::const_reference const_reference; \ 00091 typedef typename super::difference_type difference_type; 00092 00093 # define VCL_IMPORT_ITERATORS(super) \ 00094 typedef typename super::iterator iterator; \ 00095 typedef typename super::const_iterator const_iterator; 00096 00097 # define VCL_IMPORT_REVERSE_ITERATORS(super) \ 00098 typedef typename super::const_reverse_iterator const_reverse_iterator; \ 00099 typedef typename super::reverse_iterator reverse_iterator; 00100 00101 00105 template <class Key, class T, 00106 VCL_DFL_TMPL_PARAM_STLDECL(HashFcn,hash<Key>), 00107 VCL_DFL_TMPL_PARAM_STLDECL(EqualKey,std::equal_to<Key>), 00108 VCL_DFL_TYPE_PARAM_STLDECL(Alloc,std::allocator<char> ) > 00109 class hash_map 00110 { 00111 private: 00112 typedef std::select1st<std::pair<const Key, T> > sel1st; 00113 typedef hashtable<std::pair<const Key, T>, Key, HashFcn, sel1st, EqualKey, Alloc> ht; 00114 typedef hash_map<Key, T, HashFcn, EqualKey, Alloc> self; 00115 public: 00116 VCL_IMPORT_CONTAINER_TYPEDEFS(ht) 00117 VCL_IMPORT_ITERATORS(ht) 00118 typedef typename ht::key_type key_type; 00119 typedef typename ht::hasher hasher; 00120 typedef typename ht::key_equal key_equal; 00121 typedef T data_type; 00122 typedef typename ht::pointer pointer; 00123 typedef typename ht::const_pointer const_pointer; 00124 private: 00125 ht rep; 00126 00127 public: 00128 hasher hash_funct() const { return rep.hash_funct(); } 00129 key_equal key_eq() const { return rep.key_eq(); } 00130 00131 public: 00132 hash_map() : rep(100, hasher(), key_equal()) {} 00133 hash_map(size_type n) : rep(n, hasher(), key_equal()) {} 00134 hash_map(size_type n, const hasher& hf) : rep(n, hf, key_equal()) {} 00135 hash_map(size_type n, const hasher& hf, const key_equal& eql) 00136 : rep(n, hf, eql) {} 00137 00138 hash_map(const value_type* f, const value_type* l) 00139 : rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); } 00140 hash_map(const value_type* f, const value_type* l, size_type n) 00141 : rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); } 00142 hash_map(const value_type* f, const value_type* l, size_type n, 00143 const hasher& hf) 00144 : rep(n, hf, key_equal()) { rep.insert_unique(f, l); } 00145 hash_map(const value_type* f, const value_type* l, size_type n, 00146 const hasher& hf, const key_equal& eql) 00147 : rep(n, hf, eql) { rep.insert_unique(f, l); } 00148 00149 hash_map(const_iterator f, const_iterator l) 00150 : rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); } 00151 hash_map(const_iterator f, const_iterator l, size_type n) 00152 : rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); } 00153 hash_map(const_iterator f, const_iterator l, size_type n, 00154 const hasher& hf) 00155 : rep(n, hf, key_equal()) { rep.insert_unique(f, l); } 00156 hash_map(const_iterator f, const_iterator l, size_type n, 00157 const hasher& hf, const key_equal& eql) 00158 : rep(n, hf, eql) { rep.insert_unique(f, l); } 00159 00160 public: 00161 size_type size() const { return rep.size(); } 00162 size_type max_size() const { return rep.max_size(); } 00163 bool empty() const { return rep.empty(); } 00164 void swap(self& hs) { rep.swap(hs.rep); } 00165 friend bool operator==VCL_NULL_TMPL_ARGS(const hash_map<Key,T,HashFcn,EqualKey,Alloc>&, 00166 const hash_map<Key,T,HashFcn,EqualKey,Alloc>&); 00167 00168 iterator begin() { return rep.begin(); } 00169 iterator end() { return rep.end(); } 00170 const_iterator begin() const { return rep.begin(); } 00171 const_iterator end() const { return rep.end(); } 00172 00173 public: 00174 std::pair<iterator, bool> insert(const value_type& obj) 00175 { return rep.insert_unique(obj); } 00176 void insert(const value_type* f, const value_type* l) { rep.insert_unique(f,l); } 00177 void insert(const_iterator f, const_iterator l) { rep.insert_unique(f, l); } 00178 std::pair<iterator, bool> insert_noresize(const value_type& obj) 00179 { return rep.insert_unique_noresize(obj); } 00180 00181 iterator find(const key_type& key) { return rep.find(key); } 00182 const_iterator find(const key_type& key) const { return rep.find(key); } 00183 00184 T& operator[](const key_type& key) 00185 { 00186 value_type val(key, T()); 00187 return rep.find_or_insert(val).second; 00188 } 00189 00190 size_type count(const key_type& key) const { return rep.count(key); } 00191 00192 std::pair<iterator, iterator> equal_range(const key_type& key) 00193 { return rep.equal_range(key); } 00194 std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const 00195 { return rep.equal_range(key); } 00196 00197 size_type erase(const key_type& key) {return rep.erase(key); } 00198 void erase(iterator it) { rep.erase(it); } 00199 void erase(iterator f, iterator l) { rep.erase(f, l); } 00200 void clear() { rep.clear(); } 00201 00202 public: 00203 void resize(size_type hint) { rep.resize(hint); } 00204 size_type bucket_count() const { return rep.bucket_count(); } 00205 size_type max_bucket_count() const { return rep.max_bucket_count(); } 00206 size_type elems_in_bucket(size_type n) const 00207 { return rep.elems_in_bucket(n); } 00208 }; 00209 00210 00211 template <class Key, class T, VCL_DFL_TMPL_PARAM_STLDECL(HashFcn,hash<Key>), 00212 VCL_DFL_TMPL_PARAM_STLDECL(EqualKey,std::equal_to<Key>), 00213 VCL_DFL_TYPE_PARAM_STLDECL(Alloc,std::allocator<char> ) > 00214 class hash_multimap 00215 { 00216 private: 00217 typedef hashtable<std::pair<const Key, T>, Key, HashFcn, 00218 std::select1st<std::pair<const Key, T> >, EqualKey, Alloc> ht; 00219 typedef hash_multimap<Key, T, HashFcn, EqualKey, Alloc> self; 00220 public: 00221 VCL_IMPORT_CONTAINER_TYPEDEFS(ht) 00222 VCL_IMPORT_ITERATORS(ht) 00223 typedef typename ht::key_type key_type; 00224 typedef typename ht::hasher hasher; 00225 typedef typename ht::key_equal key_equal; 00226 typedef T data_type; 00227 typedef typename ht::pointer pointer; 00228 typedef typename ht::const_pointer const_pointer; 00229 00230 hasher hash_funct() const { return rep.hash_funct(); } 00231 key_equal key_eq() const { return rep.key_eq(); } 00232 private: 00233 ht rep; 00234 00235 public: 00236 hash_multimap() : rep(100, hasher(), key_equal()) {} 00237 hash_multimap(size_type n) : rep(n, hasher(), key_equal()) {} 00238 hash_multimap(size_type n, const hasher& hf) : rep(n, hf, key_equal()) {} 00239 hash_multimap(size_type n, const hasher& hf, const key_equal& eql) 00240 : rep(n, hf, eql) {} 00241 00242 hash_multimap(const value_type* f, const value_type* l) 00243 : rep(100, hasher(), key_equal()) { rep.insert_equal(f, l); } 00244 hash_multimap(const value_type* f, const value_type* l, size_type n) 00245 : rep(n, hasher(), key_equal()) { rep.insert_equal(f, l); } 00246 hash_multimap(const value_type* f, const value_type* l, size_type n, 00247 const hasher& hf) 00248 : rep(n, hf, key_equal()) { rep.insert_equal(f, l); } 00249 hash_multimap(const value_type* f, const value_type* l, size_type n, 00250 const hasher& hf, const key_equal& eql) 00251 : rep(n, hf, eql) { rep.insert_equal(f, l); } 00252 00253 hash_multimap(const_iterator f, const_iterator l) 00254 : rep(100, hasher(), key_equal()) { rep.insert_equal(f, l); } 00255 hash_multimap(const_iterator f, const_iterator l, size_type n) 00256 : rep(n, hasher(), key_equal()) { rep.insert_equal(f, l); } 00257 hash_multimap(const_iterator f, const_iterator l, size_type n, 00258 const hasher& hf) 00259 : rep(n, hf, key_equal()) { rep.insert_equal(f, l); } 00260 hash_multimap(const_iterator f, const_iterator l, size_type n, 00261 const hasher& hf, const key_equal& eql) 00262 : rep(n, hf, eql) { rep.insert_equal(f, l); } 00263 00264 public: 00265 size_type size() const { return rep.size(); } 00266 size_type max_size() const { return rep.max_size(); } 00267 bool empty() const { return rep.empty(); } 00268 void swap(self& hs) { rep.swap(hs.rep); } 00269 friend bool operator==VCL_NULL_TMPL_ARGS(const hash_multimap<Key,T,HashFcn,EqualKey,Alloc>&, 00270 const hash_multimap<Key,T,HashFcn,EqualKey,Alloc>&); 00271 00272 iterator begin() { return rep.begin(); } 00273 iterator end() { return rep.end(); } 00274 const_iterator begin() const { return rep.begin(); } 00275 const_iterator end() const { return rep.end(); } 00276 00277 public: 00278 iterator insert(const value_type& obj) { return rep.insert_equal(obj); } 00279 void insert(const value_type* f, const value_type* l) { rep.insert_equal(f,l); } 00280 void insert(const_iterator f, const_iterator l) { rep.insert_equal(f, l); } 00281 iterator insert_noresize(const value_type& obj) 00282 { return rep.insert_equal_noresize(obj); } 00283 00284 iterator find(const key_type& key) { return rep.find(key); } 00285 const_iterator find(const key_type& key) const { return rep.find(key); } 00286 00287 size_type count(const key_type& key) const { return rep.count(key); } 00288 00289 std::pair<iterator, iterator> equal_range(const key_type& key) 00290 { return rep.equal_range(key); } 00291 std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const 00292 { return rep.equal_range(key); } 00293 00294 size_type erase(const key_type& key) {return rep.erase(key); } 00295 void erase(iterator it) { rep.erase(it); } 00296 void erase(iterator f, iterator l) { rep.erase(f, l); } 00297 void clear() { rep.clear(); } 00298 00299 public: 00300 void resize(size_type hint) { rep.resize(hint); } 00301 size_type bucket_count() const { return rep.bucket_count(); } 00302 size_type max_bucket_count() const { return rep.max_bucket_count(); } 00303 size_type elems_in_bucket(size_type n) const 00304 { return rep.elems_in_bucket(n); } 00305 }; 00306 00307 template <class Key, class T, class HashFcn, class EqualKey, class Alloc> 00308 inline bool operator==(const hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm1, 00309 const hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm2) 00310 { 00311 return hm1.rep == hm2.rep; 00312 } 00313 00314 template <class Key, class T, class HashFcn, class EqualKey, class Alloc> 00315 inline bool operator==(const hash_multimap<Key, T, HashFcn, EqualKey, Alloc>& hm1, 00316 const hash_multimap<Key, T, HashFcn, EqualKey, Alloc>& hm2) 00317 { 00318 return hm1.rep == hm2.rep; 00319 } 00320 00321 00322 #define HASH_MAP_INSTANTIATE \ 00323 extern "please include emulation/hash_map.txx instead" 00324 00325 } // end namespace itk 00326 00327 #endif 00328 00329 #endif // itk_emulation_hash_map_h