contrib/gcc-3.4/libstdc++-v3/include/ext/hash_set

   1 // Hashing set implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /*
  31  * Copyright (c) 1996
  32  * Silicon Graphics Computer Systems, Inc.
  33  *
  34  * Permission to use, copy, modify, distribute and sell this software
  35  * and its documentation for any purpose is hereby granted without fee,
  36  * provided that the above copyright notice appear in all copies and
  37  * that both that copyright notice and this permission notice appear
  38  * in supporting documentation.  Silicon Graphics makes no
  39  * representations about the suitability of this software for any
  40  * purpose.  It is provided "as is" without express or implied warranty.
  41  *
  42  *
  43  * Copyright (c) 1994
  44  * Hewlett-Packard Company
  45  *
  46  * Permission to use, copy, modify, distribute and sell this software
  47  * and its documentation for any purpose is hereby granted without fee,
  48  * provided that the above copyright notice appear in all copies and
  49  * that both that copyright notice and this permission notice appear
  50  * in supporting documentation.  Hewlett-Packard Company makes no
  51  * representations about the suitability of this software for any
  52  * purpose.  It is provided "as is" without express or implied warranty.
  53  *
  54  */
  55
  56 /** @file ext/hash_set
  57  *  This file is a GNU extension to the Standard C++ Library (possibly
  58  *  containing extensions from the HP/SGI STL subset).  You should only
  59  *  include this header if you are using GCC 3 or later.
  60  */
  61
  62 #ifndef _HASH_SET
  63 #define _HASH_SET 1
  64
  65 #include <ext/hashtable.h>
  66 #include <bits/concept_check.h>
  67
  68 namespace __gnu_cxx
  69 {
  70   using std::equal_to;
  71   using std::allocator;
  72   using std::pair;
  73   using std::_Identity;
  74
  75   // Forward declaration of equality operator; needed for friend
  76   // declaration.
  77   template <class _Value, class _HashFcn  = hash<_Value>,
  78             class _EqualKey = equal_to<_Value>,
  79             class _Alloc =  allocator<_Value> >
  80   class hash_set;
  81
  82   template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  83     inline bool
  84     operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
  85                const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2);
  86
  87 /**
  88  *  This is an SGI extension.
  89  *  @ingroup SGIextensions
  90  *  @doctodo
  91 */
  92 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  93 class hash_set
  94 {
  95   // concept requirements
  96   __glibcxx_class_requires(_Value, _SGIAssignableConcept)
  97   __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
  98   __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
  99
 100 private:
 101   typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
 102                     _EqualKey, _Alloc> _Ht;
 103   _Ht _M_ht;
 104
 105 public:
 106   typedef typename _Ht::key_type key_type;
 107   typedef typename _Ht::value_type value_type;
 108   typedef typename _Ht::hasher hasher;
 109   typedef typename _Ht::key_equal key_equal;
 110
 111   typedef typename _Ht::size_type size_type;
 112   typedef typename _Ht::difference_type difference_type;
 113   typedef typename _Alloc::pointer pointer;
 114   typedef typename _Alloc::const_pointer const_pointer;
 115   typedef typename _Alloc::reference reference;
 116   typedef typename _Alloc::const_reference const_reference;
 117
 118   typedef typename _Ht::const_iterator iterator;
 119   typedef typename _Ht::const_iterator const_iterator;
 120
 121   typedef typename _Ht::allocator_type allocator_type;
 122
 123   hasher hash_funct() const { return _M_ht.hash_funct(); }
 124   key_equal key_eq() const { return _M_ht.key_eq(); }
 125   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
 126
 127 public:
 128   hash_set()
 129     : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 130   explicit hash_set(size_type __n)
 131     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 132   hash_set(size_type __n, const hasher& __hf)
 133     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 134   hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
 135            const allocator_type& __a = allocator_type())
 136     : _M_ht(__n, __hf, __eql, __a) {}
 137
 138   template <class _InputIterator>
 139   hash_set(_InputIterator __f, _InputIterator __l)
 140     : _M_ht(100, hasher(), key_equal(), allocator_type())
 141     { _M_ht.insert_unique(__f, __l); }
 142   template <class _InputIterator>
 143   hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
 144     : _M_ht(__n, hasher(), key_equal(), allocator_type())
 145     { _M_ht.insert_unique(__f, __l); }
 146   template <class _InputIterator>
 147   hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
 148            const hasher& __hf)
 149     : _M_ht(__n, __hf, key_equal(), allocator_type())
 150     { _M_ht.insert_unique(__f, __l); }
 151   template <class _InputIterator>
 152   hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
 153            const hasher& __hf, const key_equal& __eql,
 154            const allocator_type& __a = allocator_type())
 155     : _M_ht(__n, __hf, __eql, __a)
 156     { _M_ht.insert_unique(__f, __l); }
 157
 158 public:
 159   size_type size() const { return _M_ht.size(); }
 160   size_type max_size() const { return _M_ht.max_size(); }
 161   bool empty() const { return _M_ht.empty(); }
 162   void swap(hash_set& __hs) { _M_ht.swap(__hs._M_ht); }
 163
 164   template <class _Val, class _HF, class _EqK, class _Al>
 165   friend bool operator== (const hash_set<_Val, _HF, _EqK, _Al>&,
 166                           const hash_set<_Val, _HF, _EqK, _Al>&);
 167
 168   iterator begin() const { return _M_ht.begin(); }
 169   iterator end() const { return _M_ht.end(); }
 170
 171 public:
 172   pair<iterator, bool> insert(const value_type& __obj)
 173     {
 174       pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
 175       return pair<iterator,bool>(__p.first, __p.second);
 176     }
 177   template <class _InputIterator>
 178   void insert(_InputIterator __f, _InputIterator __l)
 179     { _M_ht.insert_unique(__f,__l); }
 180   pair<iterator, bool> insert_noresize(const value_type& __obj)
 181   {
 182     pair<typename _Ht::iterator, bool> __p =
 183       _M_ht.insert_unique_noresize(__obj);
 184     return pair<iterator, bool>(__p.first, __p.second);
 185   }
 186
 187   iterator find(const key_type& __key) const { return _M_ht.find(__key); }
 188
 189   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
 190
 191   pair<iterator, iterator> equal_range(const key_type& __key) const
 192     { return _M_ht.equal_range(__key); }
 193
 194   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
 195   void erase(iterator __it) { _M_ht.erase(__it); }
 196   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
 197   void clear() { _M_ht.clear(); }
 198
 199 public:
 200   void resize(size_type __hint) { _M_ht.resize(__hint); }
 201   size_type bucket_count() const { return _M_ht.bucket_count(); }
 202   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
 203   size_type elems_in_bucket(size_type __n) const
 204     { return _M_ht.elems_in_bucket(__n); }
 205 };
 206
 207 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 208 inline bool
 209 operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
 210            const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2)
 211 {
 212   return __hs1._M_ht == __hs2._M_ht;
 213 }
 214
 215 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 216 inline bool
 217 operator!=(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
 218            const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2) {
 219   return !(__hs1 == __hs2);
 220 }
 221
 222 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 223 inline void
 224 swap(hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
 225      hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2)
 226 {
 227   __hs1.swap(__hs2);
 228 }
 229
 230
 231 template <class _Value,
 232           class _HashFcn  = hash<_Value>,
 233           class _EqualKey = equal_to<_Value>,
 234           class _Alloc =  allocator<_Value> >
 235 class hash_multiset;
 236
 237 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 238 inline bool
 239 operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
 240            const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2);
 241
 242
 243 /**
 244  *  This is an SGI extension.
 245  *  @ingroup SGIextensions
 246  *  @doctodo
 247 */
 248 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 249 class hash_multiset
 250 {
 251   // concept requirements
 252   __glibcxx_class_requires(_Value, _SGIAssignableConcept)
 253   __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
 254   __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
 255
 256 private:
 257   typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
 258                     _EqualKey, _Alloc> _Ht;
 259   _Ht _M_ht;
 260
 261 public:
 262   typedef typename _Ht::key_type key_type;
 263   typedef typename _Ht::value_type value_type;
 264   typedef typename _Ht::hasher hasher;
 265   typedef typename _Ht::key_equal key_equal;
 266
 267   typedef typename _Ht::size_type size_type;
 268   typedef typename _Ht::difference_type difference_type;
 269   typedef typename _Alloc::pointer pointer;
 270   typedef typename _Alloc::const_pointer const_pointer;
 271   typedef typename _Alloc::reference reference;
 272   typedef typename _Alloc::const_reference const_reference;
 273
 274   typedef typename _Ht::const_iterator iterator;
 275   typedef typename _Ht::const_iterator const_iterator;
 276
 277   typedef typename _Ht::allocator_type allocator_type;
 278
 279   hasher hash_funct() const { return _M_ht.hash_funct(); }
 280   key_equal key_eq() const { return _M_ht.key_eq(); }
 281   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
 282
 283 public:
 284   hash_multiset()
 285     : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 286   explicit hash_multiset(size_type __n)
 287     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 288   hash_multiset(size_type __n, const hasher& __hf)
 289     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 290   hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
 291                 const allocator_type& __a = allocator_type())
 292     : _M_ht(__n, __hf, __eql, __a) {}
 293
 294   template <class _InputIterator>
 295   hash_multiset(_InputIterator __f, _InputIterator __l)
 296     : _M_ht(100, hasher(), key_equal(), allocator_type())
 297     { _M_ht.insert_equal(__f, __l); }
 298   template <class _InputIterator>
 299   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
 300     : _M_ht(__n, hasher(), key_equal(), allocator_type())
 301     { _M_ht.insert_equal(__f, __l); }
 302   template <class _InputIterator>
 303   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
 304                 const hasher& __hf)
 305     : _M_ht(__n, __hf, key_equal(), allocator_type())
 306     { _M_ht.insert_equal(__f, __l); }
 307   template <class _InputIterator>
 308   hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
 309                 const hasher& __hf, const key_equal& __eql,
 310                 const allocator_type& __a = allocator_type())
 311     : _M_ht(__n, __hf, __eql, __a)
 312     { _M_ht.insert_equal(__f, __l); }
 313
 314 public:
 315   size_type size() const { return _M_ht.size(); }
 316   size_type max_size() const { return _M_ht.max_size(); }
 317   bool empty() const { return _M_ht.empty(); }
 318   void swap(hash_multiset& hs) { _M_ht.swap(hs._M_ht); }
 319
 320   template <class _Val, class _HF, class _EqK, class _Al>
 321   friend bool operator== (const hash_multiset<_Val, _HF, _EqK, _Al>&,
 322                           const hash_multiset<_Val, _HF, _EqK, _Al>&);
 323
 324   iterator begin() const { return _M_ht.begin(); }
 325   iterator end() const { return _M_ht.end(); }
 326
 327 public:
 328   iterator insert(const value_type& __obj)
 329     { return _M_ht.insert_equal(__obj); }
 330   template <class _InputIterator>
 331   void insert(_InputIterator __f, _InputIterator __l)
 332     { _M_ht.insert_equal(__f,__l); }
 333   iterator insert_noresize(const value_type& __obj)
 334     { return _M_ht.insert_equal_noresize(__obj); }
 335
 336   iterator find(const key_type& __key) const { return _M_ht.find(__key); }
 337
 338   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
 339
 340   pair<iterator, iterator> equal_range(const key_type& __key) const
 341     { return _M_ht.equal_range(__key); }
 342
 343   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
 344   void erase(iterator __it) { _M_ht.erase(__it); }
 345   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
 346   void clear() { _M_ht.clear(); }
 347
 348 public:
 349   void resize(size_type __hint) { _M_ht.resize(__hint); }
 350   size_type bucket_count() const { return _M_ht.bucket_count(); }
 351   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
 352   size_type elems_in_bucket(size_type __n) const
 353     { return _M_ht.elems_in_bucket(__n); }
 354 };
 355
 356 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 357 inline bool
 358 operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
 359            const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2)
 360 {
 361   return __hs1._M_ht == __hs2._M_ht;
 362 }
 363
 364 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 365 inline bool
 366 operator!=(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
 367            const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) {
 368   return !(__hs1 == __hs2);
 369 }
 370
 371 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 372 inline void
 373 swap(hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
 374      hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) {
 375   __hs1.swap(__hs2);
 376 }
 377
 378 } // namespace __gnu_cxx
 379
 380 namespace std
 381 {
 382 // Specialization of insert_iterator so that it will work for hash_set
 383 // and hash_multiset.
 384
 385 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 386 class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> > {
 387 protected:
 388   typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
 389   _Container* container;
 390 public:
 391   typedef _Container          container_type;
 392   typedef output_iterator_tag iterator_category;
 393   typedef void                value_type;
 394   typedef void                difference_type;
 395   typedef void                pointer;
 396   typedef void                reference;
 397
 398   insert_iterator(_Container& __x) : container(&__x) {}
 399   insert_iterator(_Container& __x, typename _Container::iterator)
 400     : container(&__x) {}
 401   insert_iterator<_Container>&
 402   operator=(const typename _Container::value_type& __value) {
 403     container->insert(__value);
 404     return *this;
 405   }
 406   insert_iterator<_Container>& operator*() { return *this; }
 407   insert_iterator<_Container>& operator++() { return *this; }
 408   insert_iterator<_Container>& operator++(int) { return *this; }
 409 };
 410
 411 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 412 class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > {
 413 protected:
 414   typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Container;
 415   _Container* container;
 416   typename _Container::iterator iter;
 417 public:
 418   typedef _Container          container_type;
 419   typedef output_iterator_tag iterator_category;
 420   typedef void                value_type;
 421   typedef void                difference_type;
 422   typedef void                pointer;
 423   typedef void                reference;
 424
 425   insert_iterator(_Container& __x) : container(&__x) {}
 426   insert_iterator(_Container& __x, typename _Container::iterator)
 427     : container(&__x) {}
 428   insert_iterator<_Container>&
 429   operator=(const typename _Container::value_type& __value) {
 430     container->insert(__value);
 431     return *this;
 432   }
 433   insert_iterator<_Container>& operator*() { return *this; }
 434   insert_iterator<_Container>& operator++() { return *this; }
 435   insert_iterator<_Container>& operator++(int) { return *this; }
 436 };
 437 } // namespace std
 438
 439 #endif