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

   1 // Hashing set implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2004, 2005 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  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).
  59  */
  60
  61 #ifndef _HASH_SET
  62 #define _HASH_SET 1
  63
  64 #include <ext/hashtable.h>
  65 #include <bits/concept_check.h>
  66
  67 namespace __gnu_cxx
  68 {
  69   using std::equal_to;
  70   using std::allocator;
  71   using std::pair;
  72   using std::_Identity;
  73
  74   // Forward declaration of equality operator; needed for friend
  75   // declaration.
  76   template <class _Value, class _HashFcn  = hash<_Value>,
  77             class _EqualKey = equal_to<_Value>,
  78             class _Alloc = allocator<_Value> >
  79     class hash_set;
  80
  81   template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  82     inline bool
  83     operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
  84                const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2);
  85
  86   /**
  87    *  This is an SGI extension.
  88    *  @ingroup SGIextensions
  89    *  @doctodo
  90    */
  91   template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
  92     class hash_set
  93     {
  94       // concept requirements
  95       __glibcxx_class_requires(_Value, _SGIAssignableConcept)
  96       __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
  97       __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
  98
  99     private:
 100       typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
 101                         _EqualKey, _Alloc> _Ht;
 102       _Ht _M_ht;
 103
 104     public:
 105       typedef typename _Ht::key_type key_type;
 106       typedef typename _Ht::value_type value_type;
 107       typedef typename _Ht::hasher hasher;
 108       typedef typename _Ht::key_equal key_equal;
 109
 110       typedef typename _Ht::size_type size_type;
 111       typedef typename _Ht::difference_type difference_type;
 112       typedef typename _Alloc::pointer pointer;
 113       typedef typename _Alloc::const_pointer const_pointer;
 114       typedef typename _Alloc::reference reference;
 115       typedef typename _Alloc::const_reference const_reference;
 116
 117       typedef typename _Ht::const_iterator iterator;
 118       typedef typename _Ht::const_iterator const_iterator;
 119
 120       typedef typename _Ht::allocator_type allocator_type;
 121
 122       hasher
 123       hash_funct() const
 124       { return _M_ht.hash_funct(); }
 125
 126       key_equal
 127       key_eq() const
 128       { return _M_ht.key_eq(); }
 129
 130       allocator_type
 131       get_allocator() const
 132       { return _M_ht.get_allocator(); }
 133
 134     public:
 135       hash_set()
 136       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 137
 138       explicit
 139       hash_set(size_type __n)
 140       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 141
 142       hash_set(size_type __n, const hasher& __hf)
 143       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 144
 145       hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
 146                const allocator_type& __a = allocator_type())
 147       : _M_ht(__n, __hf, __eql, __a) {}
 148
 149       template <class _InputIterator>
 150         hash_set(_InputIterator __f, _InputIterator __l)
 151         : _M_ht(100, hasher(), key_equal(), allocator_type())
 152         { _M_ht.insert_unique(__f, __l); }
 153
 154       template <class _InputIterator>
 155         hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
 156         : _M_ht(__n, hasher(), key_equal(), allocator_type())
 157         { _M_ht.insert_unique(__f, __l); }
 158
 159       template <class _InputIterator>
 160         hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
 161                  const hasher& __hf)
 162         : _M_ht(__n, __hf, key_equal(), allocator_type())
 163         { _M_ht.insert_unique(__f, __l); }
 164
 165       template <class _InputIterator>
 166         hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
 167                  const hasher& __hf, const key_equal& __eql,
 168                  const allocator_type& __a = allocator_type())
 169         : _M_ht(__n, __hf, __eql, __a)
 170         { _M_ht.insert_unique(__f, __l); }
 171
 172     public:
 173       size_type
 174       size() const
 175       { return _M_ht.size(); }
 176
 177       size_type
 178       max_size() const
 179       { return _M_ht.max_size(); }
 180
 181       bool
 182       empty() const
 183       { return _M_ht.empty(); }
 184
 185       void
 186       swap(hash_set& __hs)
 187       { _M_ht.swap(__hs._M_ht); }
 188
 189       template <class _Val, class _HF, class _EqK, class _Al>
 190         friend bool
 191         operator==(const hash_set<_Val, _HF, _EqK, _Al>&,
 192                    const hash_set<_Val, _HF, _EqK, _Al>&);
 193
 194       iterator
 195       begin() const
 196       { return _M_ht.begin(); }
 197
 198       iterator
 199       end() const
 200       { return _M_ht.end(); }
 201
 202     public:
 203       pair<iterator, bool>
 204       insert(const value_type& __obj)
 205       {
 206         pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
 207         return pair<iterator,bool>(__p.first, __p.second);
 208       }
 209
 210       template <class _InputIterator>
 211         void
 212         insert(_InputIterator __f, _InputIterator __l)
 213         { _M_ht.insert_unique(__f, __l); }
 214
 215       pair<iterator, bool>
 216       insert_noresize(const value_type& __obj)
 217       {
 218         pair<typename _Ht::iterator, bool> __p
 219           = _M_ht.insert_unique_noresize(__obj);
 220         return pair<iterator, bool>(__p.first, __p.second);
 221       }
 222
 223       iterator
 224       find(const key_type& __key) const
 225       { return _M_ht.find(__key); }
 226
 227       size_type
 228       count(const key_type& __key) const
 229       { return _M_ht.count(__key); }
 230
 231       pair<iterator, iterator>
 232       equal_range(const key_type& __key) const
 233       { return _M_ht.equal_range(__key); }
 234
 235       size_type
 236       erase(const key_type& __key)
 237       {return _M_ht.erase(__key); }
 238
 239       void
 240       erase(iterator __it)
 241       { _M_ht.erase(__it); }
 242
 243       void
 244       erase(iterator __f, iterator __l)
 245       { _M_ht.erase(__f, __l); }
 246
 247       void
 248       clear()
 249       { _M_ht.clear(); }
 250
 251 public:
 252       void
 253       resize(size_type __hint)
 254       { _M_ht.resize(__hint); }
 255
 256       size_type
 257       bucket_count() const
 258       { return _M_ht.bucket_count(); }
 259
 260       size_type
 261       max_bucket_count() const
 262       { return _M_ht.max_bucket_count(); }
 263
 264       size_type
 265       elems_in_bucket(size_type __n) const
 266       { return _M_ht.elems_in_bucket(__n); }
 267     };
 268
 269   template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 270     inline bool
 271     operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
 272                const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
 273     { return __hs1._M_ht == __hs2._M_ht; }
 274
 275   template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 276     inline bool
 277     operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
 278                const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
 279     { return !(__hs1 == __hs2); }
 280
 281   template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 282     inline void
 283     swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
 284          hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
 285     { __hs1.swap(__hs2); }
 286
 287   template <class _Value,
 288             class _HashFcn = hash<_Value>,
 289             class _EqualKey = equal_to<_Value>,
 290             class _Alloc = allocator<_Value> >
 291     class hash_multiset;
 292
 293   template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 294     inline bool
 295     operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
 296                const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2);
 297
 298
 299   /**
 300    *  This is an SGI extension.
 301    *  @ingroup SGIextensions
 302    *  @doctodo
 303    */
 304   template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 305     class hash_multiset
 306     {
 307       // concept requirements
 308       __glibcxx_class_requires(_Value, _SGIAssignableConcept)
 309       __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
 310       __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
 311
 312     private:
 313       typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
 314                         _EqualKey, _Alloc> _Ht;
 315       _Ht _M_ht;
 316
 317     public:
 318       typedef typename _Ht::key_type key_type;
 319       typedef typename _Ht::value_type value_type;
 320       typedef typename _Ht::hasher hasher;
 321       typedef typename _Ht::key_equal key_equal;
 322
 323       typedef typename _Ht::size_type size_type;
 324       typedef typename _Ht::difference_type difference_type;
 325       typedef typename _Alloc::pointer pointer;
 326       typedef typename _Alloc::const_pointer const_pointer;
 327       typedef typename _Alloc::reference reference;
 328       typedef typename _Alloc::const_reference const_reference;
 329
 330       typedef typename _Ht::const_iterator iterator;
 331       typedef typename _Ht::const_iterator const_iterator;
 332
 333       typedef typename _Ht::allocator_type allocator_type;
 334
 335       hasher
 336       hash_funct() const
 337       { return _M_ht.hash_funct(); }
 338
 339       key_equal
 340       key_eq() const
 341       { return _M_ht.key_eq(); }
 342
 343       allocator_type
 344       get_allocator() const
 345       { return _M_ht.get_allocator(); }
 346
 347     public:
 348       hash_multiset()
 349       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 350
 351       explicit
 352       hash_multiset(size_type __n)
 353       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 354
 355       hash_multiset(size_type __n, const hasher& __hf)
 356       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 357
 358       hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
 359                     const allocator_type& __a = allocator_type())
 360       : _M_ht(__n, __hf, __eql, __a) {}
 361
 362       template <class _InputIterator>
 363         hash_multiset(_InputIterator __f, _InputIterator __l)
 364         : _M_ht(100, hasher(), key_equal(), allocator_type())
 365         { _M_ht.insert_equal(__f, __l); }
 366
 367       template <class _InputIterator>
 368         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
 369         : _M_ht(__n, hasher(), key_equal(), allocator_type())
 370         { _M_ht.insert_equal(__f, __l); }
 371
 372       template <class _InputIterator>
 373         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
 374                       const hasher& __hf)
 375         : _M_ht(__n, __hf, key_equal(), allocator_type())
 376         { _M_ht.insert_equal(__f, __l); }
 377
 378       template <class _InputIterator>
 379         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
 380                       const hasher& __hf, const key_equal& __eql,
 381                       const allocator_type& __a = allocator_type())
 382         : _M_ht(__n, __hf, __eql, __a)
 383         { _M_ht.insert_equal(__f, __l); }
 384
 385     public:
 386       size_type
 387       size() const
 388       { return _M_ht.size(); }
 389
 390       size_type
 391       max_size() const
 392       { return _M_ht.max_size(); }
 393
 394       bool
 395       empty() const
 396       { return _M_ht.empty(); }
 397
 398       void
 399       swap(hash_multiset& hs)
 400       { _M_ht.swap(hs._M_ht); }
 401
 402       template <class _Val, class _HF, class _EqK, class _Al>
 403         friend bool
 404         operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&,
 405                    const hash_multiset<_Val, _HF, _EqK, _Al>&);
 406
 407       iterator
 408       begin() const
 409       { return _M_ht.begin(); }
 410
 411       iterator
 412       end() const
 413       { return _M_ht.end(); }
 414
 415 public:
 416       iterator
 417       insert(const value_type& __obj)
 418       { return _M_ht.insert_equal(__obj); }
 419
 420       template <class _InputIterator>
 421         void
 422         insert(_InputIterator __f, _InputIterator __l)
 423         { _M_ht.insert_equal(__f,__l); }
 424
 425       iterator
 426       insert_noresize(const value_type& __obj)
 427       { return _M_ht.insert_equal_noresize(__obj); }
 428
 429       iterator
 430       find(const key_type& __key) const
 431       { return _M_ht.find(__key); }
 432
 433       size_type
 434       count(const key_type& __key) const
 435       { return _M_ht.count(__key); }
 436
 437       pair<iterator, iterator>
 438       equal_range(const key_type& __key) const
 439       { return _M_ht.equal_range(__key); }
 440
 441       size_type
 442       erase(const key_type& __key)
 443       { return _M_ht.erase(__key); }
 444
 445       void
 446       erase(iterator __it)
 447       { _M_ht.erase(__it); }
 448
 449       void
 450       erase(iterator __f, iterator __l)
 451       { _M_ht.erase(__f, __l); }
 452
 453       void
 454       clear()
 455       { _M_ht.clear(); }
 456
 457     public:
 458       void
 459       resize(size_type __hint)
 460       { _M_ht.resize(__hint); }
 461
 462       size_type
 463       bucket_count() const
 464       { return _M_ht.bucket_count(); }
 465
 466       size_type
 467       max_bucket_count() const
 468       { return _M_ht.max_bucket_count(); }
 469
 470       size_type
 471       elems_in_bucket(size_type __n) const
 472       { return _M_ht.elems_in_bucket(__n); }
 473     };
 474
 475   template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 476     inline bool
 477     operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
 478                const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
 479     { return __hs1._M_ht == __hs2._M_ht; }
 480
 481   template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 482     inline bool
 483     operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
 484                const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
 485     { return !(__hs1 == __hs2); }
 486
 487   template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 488     inline void
 489     swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
 490          hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
 491     { __hs1.swap(__hs2); }
 492
 493 } // namespace __gnu_cxx
 494
 495 namespace std
 496 {
 497   // Specialization of insert_iterator so that it will work for hash_set
 498   // and hash_multiset.
 499
 500   template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 501     class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn,
 502                                               _EqualKey, _Alloc> >
 503     {
 504     protected:
 505       typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc>
 506         _Container;
 507       _Container* container;
 508
 509     public:
 510       typedef _Container          container_type;
 511       typedef output_iterator_tag iterator_category;
 512       typedef void                value_type;
 513       typedef void                difference_type;
 514       typedef void                pointer;
 515       typedef void                reference;
 516
 517       insert_iterator(_Container& __x)
 518       : container(&__x) {}
 519
 520       insert_iterator(_Container& __x, typename _Container::iterator)
 521       : container(&__x) {}
 522
 523       insert_iterator<_Container>&
 524       operator=(const typename _Container::value_type& __value)
 525       {
 526         container->insert(__value);
 527         return *this;
 528       }
 529
 530       insert_iterator<_Container>&
 531       operator*()
 532       { return *this; }
 533
 534       insert_iterator<_Container>&
 535       operator++()
 536       { return *this; }
 537
 538       insert_iterator<_Container>&
 539       operator++(int)
 540       { return *this; }
 541     };
 542
 543   template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 544     class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn,
 545                                                    _EqualKey, _Alloc> >
 546     {
 547     protected:
 548       typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>
 549         _Container;
 550       _Container* container;
 551       typename _Container::iterator iter;
 552
 553     public:
 554       typedef _Container          container_type;
 555       typedef output_iterator_tag iterator_category;
 556       typedef void                value_type;
 557       typedef void                difference_type;
 558       typedef void                pointer;
 559       typedef void                reference;
 560
 561       insert_iterator(_Container& __x)
 562       : container(&__x) {}
 563
 564       insert_iterator(_Container& __x, typename _Container::iterator)
 565       : container(&__x) {}
 566
 567       insert_iterator<_Container>&
 568       operator=(const typename _Container::value_type& __value)
 569       {
 570         container->insert(__value);
 571         return *this;
 572       }
 573
 574       insert_iterator<_Container>&
 575       operator*()
 576       { return *this; }
 577
 578       insert_iterator<_Container>&
 579       operator++()
 580       { return *this; }
 581
 582       insert_iterator<_Container>&
 583       operator++(int) { return *this; }
 584     };
 585 } // namespace std
 586
 587 #ifdef _GLIBCXX_DEBUG
 588 # include <debug/hash_set>
 589 #endif
 590
 591 #endif