00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00054 #ifndef __itk_hash_set_h
00055 #define __itk_hash_set_h
00056
00057 #if (defined(__GNUC__) && (((__GNUC__==3) && (__GNUC_MINOR__>=1) || (__GNUC__>3) ) || ( (__GNUC__==4) && defined(__INTEL_COMPILER) ) )) || (defined(__IBMCPP__) && __IBMCPP__ >= 600)
00058
00059 #include <ext/hash_set>
00060
00061 namespace itk
00062 {
00063 using __gnu_cxx::hash;
00064 using __gnu_cxx::hash_set;
00065 using __gnu_cxx::hash_multiset;
00066 }
00067
00068 #else
00069
00070 #include "itk_hashtable.h"
00071 #include <functional>
00072
00073
00074
00075 namespace itk
00076 {
00077
00082 template <class Value, VCL_DFL_TMPL_PARAM_STLDECL(HashFcn,hash<Value>),
00083 VCL_DFL_TMPL_PARAM_STLDECL(EqualKey,std::equal_to<Value>),
00084 VCL_DFL_TYPE_PARAM_STLDECL(Alloc,std::allocator<char> ) >
00085 class hash_set
00086 {
00087 private:
00088 typedef hashtable<Value, Value, HashFcn, std::identity<Value>,
00089 EqualKey, Alloc> ht;
00090 typedef hash_set<Value, HashFcn, EqualKey, Alloc> self;
00091 public:
00092 typedef typename ht::key_type key_type;
00093 typedef typename ht::value_type value_type;
00094 typedef typename ht::hasher hasher;
00095 typedef typename ht::key_equal key_equal;
00096
00097 typedef typename ht::size_type size_type;
00098 typedef typename ht::difference_type difference_type;
00099 typedef typename ht::const_pointer pointer;
00100 typedef typename ht::const_pointer const_pointer;
00101 typedef typename ht::const_reference reference;
00102 typedef typename ht::const_reference const_reference;
00103
00104 typedef typename ht::const_iterator const_iterator;
00105 typedef const_iterator iterator;
00106
00107
00108 typedef typename ht::iterator ht_iterator;
00109
00110 hasher hash_funct() const { return rep.hash_funct(); }
00111 key_equal key_eq() const { return rep.key_eq(); }
00112
00113 private:
00114 ht rep;
00115
00116 public:
00117 hash_set() : rep(100, hasher(), key_equal()) {}
00118 hash_set(size_type n) : rep(n, hasher(), key_equal()) {}
00119 hash_set(size_type n, const hasher& hf) : rep(n, hf, key_equal()) {}
00120 hash_set(size_type n, const hasher& hf, const key_equal& eql)
00121 : rep(n, hf, eql) {}
00122
00123 hash_set(const value_type* f, const value_type* l)
00124 : rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); }
00125 hash_set(const value_type* f, const value_type* l, size_type n)
00126 : rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); }
00127 hash_set(const value_type* f, const value_type* l, size_type n,
00128 const hasher& hf)
00129 : rep(n, hf, key_equal()) { rep.insert_unique(f, l); }
00130 hash_set(const value_type* f, const value_type* l, size_type n,
00131 const hasher& hf, const key_equal& eql)
00132 : rep(n, hf, eql) { rep.insert_unique(f, l); }
00133
00134 hash_set(const_iterator f, const_iterator l)
00135 : rep(100, hasher(), key_equal()) { rep.insert_unique(f, l); }
00136 hash_set(const_iterator f, const_iterator l, size_type n)
00137 : rep(n, hasher(), key_equal()) { rep.insert_unique(f, l); }
00138 hash_set(const_iterator f, const_iterator l, size_type n,
00139 const hasher& hf)
00140 : rep(n, hf, key_equal()) { rep.insert_unique(f, l); }
00141 hash_set(const_iterator f, const_iterator l, size_type n,
00142 const hasher& hf, const key_equal& eql)
00143 : rep(n, hf, eql) { rep.insert_unique(f, l); }
00144
00145 public:
00146 size_type size() const { return rep.size(); }
00147 size_type max_size() const { return rep.max_size(); }
00148 bool empty() const { return rep.empty(); }
00149 void swap(self& hs) { rep.swap(hs.rep); }
00150
00151 friend bool operator==ITK_FRIEND_TEMPLATE_FUNCTION_ARGUMENT(self)(const self &, const self &);
00152
00153 iterator begin() const { return rep.begin(); }
00154 iterator end() const { return rep.end(); }
00155
00156 public:
00157 std::pair<iterator, bool> insert(const value_type& obj)
00158 {
00159 #ifdef _MSC_VER
00160 std::pair< ht::iterator, bool> p = rep.insert_unique(obj);
00161 #else
00162 std::pair<typename ht::iterator, bool> p = rep.insert_unique(obj);
00163 #endif
00164 return std::pair<iterator, bool>(p.first, p.second);
00165 }
00166 void insert(const value_type* f, const value_type* l) { rep.insert_unique(f,l); }
00167 void insert(const_iterator f, const_iterator l) { rep.insert_unique(f, l); }
00168 std::pair<iterator, bool> insert_noresize(const value_type& obj)
00169 {
00170 #ifdef _MSC_VER
00171 std::pair<ht::iterator, bool> p = rep.insert_unique_noresize(obj);
00172 #else
00173 std::pair<typename ht::iterator, bool> p = rep.insert_unique_noresize(obj);
00174 #endif
00175 return std::pair<iterator, bool>(p.first, p.second);
00176 }
00177
00178 iterator find(const key_type& key) const { return rep.find(key); }
00179
00180 size_type count(const key_type& key) const { return rep.count(key); }
00181
00182 std::pair<iterator, iterator> equal_range(const key_type& key) const
00183 { return rep.equal_range(key); }
00184
00185 size_type erase(const key_type& key) {return rep.erase(key); }
00186 void erase(iterator it) { rep.erase(it); }
00187 void erase(iterator f, iterator l) { rep.erase(f, l); }
00188 void clear() { rep.clear(); }
00189
00190 public:
00191 void resize(size_type hint) { rep.resize(hint); }
00192 size_type bucket_count() const { return rep.bucket_count(); }
00193 size_type max_bucket_count() const { return rep.max_bucket_count(); }
00194 size_type elems_in_bucket(size_type n) const
00195 { return rep.elems_in_bucket(n); }
00196 };
00197
00198
00199 template <class Value, VCL_DFL_TMPL_PARAM_STLDECL(HashFcn,hash<Value>),
00200 VCL_DFL_TMPL_PARAM_STLDECL(EqualKey,std::equal_to<Value>),
00201 VCL_DFL_TYPE_PARAM_STLDECL(Alloc,std::allocator<char> ) >
00202 class hash_multiset
00203 {
00204 private:
00205 typedef hashtable<Value, Value, HashFcn, std::identity<Value>,
00206 EqualKey, Alloc> ht;
00207 typedef hash_multiset<Value, HashFcn, EqualKey, Alloc> self;
00208 public:
00209 typedef typename ht::key_type key_type;
00210 typedef typename ht::value_type value_type;
00211 typedef typename ht::hasher hasher;
00212 typedef typename ht::key_equal key_equal;
00213
00214 typedef typename ht::size_type size_type;
00215 typedef typename ht::difference_type difference_type;
00216 typedef typename ht::const_pointer pointer;
00217 typedef typename ht::const_pointer const_pointer;
00218 typedef typename ht::const_reference reference;
00219 typedef typename ht::const_reference const_reference;
00220
00221 typedef typename ht::const_iterator const_iterator;
00222
00223 typedef const_iterator iterator;
00224
00225 hasher hash_funct() const { return rep.hash_funct(); }
00226 key_equal key_eq() const { return rep.key_eq(); }
00227 private:
00228 ht rep;
00229
00230 public:
00231 hash_multiset() : rep(100, hasher(), key_equal()) {}
00232 hash_multiset(size_type n) : rep(n, hasher(), key_equal()) {}
00233 hash_multiset(size_type n, const hasher& hf) : rep(n, hf, key_equal()) {}
00234 hash_multiset(size_type n, const hasher& hf, const key_equal& eql)
00235 : rep(n, hf, eql) {}
00236
00237 hash_multiset(const value_type* f, const value_type* l)
00238 : rep(100, hasher(), key_equal()) { rep.insert_equal(f, l); }
00239 hash_multiset(const value_type* f, const value_type* l, size_type n)
00240 : rep(n, hasher(), key_equal()) { rep.insert_equal(f, l); }
00241 hash_multiset(const value_type* f, const value_type* l, size_type n,
00242 const hasher& hf)
00243 : rep(n, hf, key_equal()) { rep.insert_equal(f, l); }
00244 hash_multiset(const value_type* f, const value_type* l, size_type n,
00245 const hasher& hf, const key_equal& eql)
00246 : rep(n, hf, eql) { rep.insert_equal(f, l); }
00247
00248 hash_multiset(const_iterator f, const_iterator l)
00249 : rep(100, hasher(), key_equal()) { rep.insert_equal(f, l); }
00250 hash_multiset(const_iterator f, const_iterator l, size_type n)
00251 : rep(n, hasher(), key_equal()) { rep.insert_equal(f, l); }
00252 hash_multiset(const_iterator f, const_iterator l, size_type n,
00253 const hasher& hf)
00254 : rep(n, hf, key_equal()) { rep.insert_equal(f, l); }
00255 hash_multiset(const_iterator f, const_iterator l, size_type n,
00256 const hasher& hf, const key_equal& eql)
00257 : rep(n, hf, eql) { rep.insert_equal(f, l); }
00258
00259 public:
00260 size_type size() const { return rep.size(); }
00261 size_type max_size() const { return rep.max_size(); }
00262 bool empty() const { return rep.empty(); }
00263 void swap(self& hs) { rep.swap(hs.rep); }
00264
00265 friend bool operator==ITK_FRIEND_TEMPLATE_FUNCTION_ARGUMENT(self)(const self &, const self &);
00266
00267 iterator begin() const { return rep.begin(); }
00268 iterator end() const { return rep.end(); }
00269
00270 public:
00271 iterator insert(const value_type& obj) { return rep.insert_equal(obj); }
00272 void insert(const value_type* f, const value_type* l) { rep.insert_equal(f,l); }
00273 void insert(const_iterator f, const_iterator l) { rep.insert_equal(f, l); }
00274 iterator insert_noresize(const value_type& obj)
00275 { return rep.insert_equal_noresize(obj); }
00276
00277 iterator find(const key_type& key) const { return rep.find(key); }
00278
00279 size_type count(const key_type& key) const { return rep.count(key); }
00280
00281 std::pair<iterator, iterator> equal_range(const key_type& key) const
00282 { return rep.equal_range(key); }
00283
00284 size_type erase(const key_type& key) {return rep.erase(key); }
00285 void erase(iterator it) { rep.erase(it); }
00286 void erase(iterator f, iterator l) { rep.erase(f, l); }
00287 void clear() { rep.clear(); }
00288
00289 public:
00290 void resize(size_type hint) { rep.resize(hint); }
00291 size_type bucket_count() const { return rep.bucket_count(); }
00292 size_type max_bucket_count() const { return rep.max_bucket_count(); }
00293 size_type elems_in_bucket(size_type n) const
00294 { return rep.elems_in_bucket(n); }
00295 };
00296
00297
00300 template <class Value, class HashFcn, class EqualKey, class Alloc>
00301 bool operator==(const hash_set<Value, HashFcn, EqualKey, Alloc>& hs1,
00302 const hash_set<Value, HashFcn, EqualKey, Alloc>& hs2)
00303 {
00304 return hs1.rep == hs2.rep;
00305 }
00306
00309 template <class Value, class HashFcn, class EqualKey, class Alloc>
00310 bool operator==(const hash_multiset<Value, HashFcn, EqualKey, Alloc>& hs1,
00311 const hash_multiset<Value, HashFcn, EqualKey, Alloc>& hs2)
00312 {
00313 return hs1.rep == hs2.rep;
00314 }
00315
00316 # if defined (__STL_CLASS_PARTIAL_SPECIALIZATION )
00317 template <class Value, class HashFcn, class EqualKey, class Alloc>
00318 inline void swap(hash_multiset<Value, HashFcn, EqualKey, Alloc>& a,
00319 hash_multiset<Value, HashFcn, EqualKey, Alloc>& b) { a.swap(b); }
00320 template <class Value, class HashFcn, class EqualKey, class Alloc>
00321 inline void swap(hash_set<Value, HashFcn, EqualKey, Alloc>& a,
00322 hash_set<Value, HashFcn, EqualKey, Alloc>& b) { a.swap(b); }
00323 # endif
00324
00325 }
00326
00327 #endif
00328 #endif // itk_emulation_hash_set_h
00329