contrib/gcc-4.7/libstdc++-v3/include/backward/hash_set

   1 // Hashing set implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2004, 2005, 2006, 2009, 2010
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 3, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 /*
  27  * Copyright (c) 1996
  28  * Silicon Graphics Computer Systems, Inc.
  29  *
  30  * Permission to use, copy, modify, distribute and sell this software
  31  * and its documentation for any purpose is hereby granted without fee,
  32  * provided that the above copyright notice appear in all copies and
  33  * that both that copyright notice and this permission notice appear
  34  * in supporting documentation.  Silicon Graphics makes no
  35  * representations about the suitability of this software for any
  36  * purpose.  It is provided "as is" without express or implied warranty.
  37  *
  38  *
  39  * Copyright (c) 1994
  40  * Hewlett-Packard Company
  41  *
  42  * Permission to use, copy, modify, distribute and sell this software
  43  * and its documentation for any purpose is hereby granted without fee,
  44  * provided that the above copyright notice appear in all copies and
  45  * that both that copyright notice and this permission notice appear
  46  * in supporting documentation.  Hewlett-Packard Company makes no
  47  * representations about the suitability of this software for any
  48  * purpose.  It is provided "as is" without express or implied warranty.
  49  *
  50  */
  51
  52 /** @file backward/hash_set
  53  *  This file is a GNU extension to the Standard C++ Library (possibly
  54  *  containing extensions from the HP/SGI STL subset).
  55  */
  56
  57 #ifndef _BACKWARD_HASH_SET
  58 #define _BACKWARD_HASH_SET 1
  59
  60 #ifndef _GLIBCXX_PERMIT_BACKWARD_HASH
  61 #include "backward_warning.h"
  62 #endif
  63
  64 #include <bits/c++config.h>
  65 #include <backward/hashtable.h>
  66 #include <bits/concept_check.h>
  67
  68 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
  69 {
  70 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  71
  72   using std::equal_to;
  73   using std::allocator;
  74   using std::pair;
  75   using std::_Identity;
  76
  77   /**
  78    *  This is an SGI extension.
  79    *  @ingroup SGIextensions
  80    *  @doctodo
  81    */
  82   template<class _Value, class _HashFcn  = hash<_Value>,
  83            class _EqualKey = equal_to<_Value>,
  84            class _Alloc = allocator<_Value> >
  85     class hash_set
  86     {
  87       // concept requirements
  88       __glibcxx_class_requires(_Value, _SGIAssignableConcept)
  89       __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
  90       __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
  91
  92     private:
  93       typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
  94                         _EqualKey, _Alloc> _Ht;
  95       _Ht _M_ht;
  96
  97     public:
  98       typedef typename _Ht::key_type key_type;
  99       typedef typename _Ht::value_type value_type;
 100       typedef typename _Ht::hasher hasher;
 101       typedef typename _Ht::key_equal key_equal;
 102
 103       typedef typename _Ht::size_type size_type;
 104       typedef typename _Ht::difference_type difference_type;
 105       typedef typename _Alloc::pointer pointer;
 106       typedef typename _Alloc::const_pointer const_pointer;
 107       typedef typename _Alloc::reference reference;
 108       typedef typename _Alloc::const_reference const_reference;
 109
 110       typedef typename _Ht::const_iterator iterator;
 111       typedef typename _Ht::const_iterator const_iterator;
 112
 113       typedef typename _Ht::allocator_type allocator_type;
 114
 115       hasher
 116       hash_funct() const
 117       { return _M_ht.hash_funct(); }
 118
 119       key_equal
 120       key_eq() const
 121       { return _M_ht.key_eq(); }
 122
 123       allocator_type
 124       get_allocator() const
 125       { return _M_ht.get_allocator(); }
 126
 127       hash_set()
 128       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 129
 130       explicit
 131       hash_set(size_type __n)
 132       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 133
 134       hash_set(size_type __n, const hasher& __hf)
 135       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 136
 137       hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
 138                const allocator_type& __a = allocator_type())
 139       : _M_ht(__n, __hf, __eql, __a) {}
 140
 141       template<class _InputIterator>
 142         hash_set(_InputIterator __f, _InputIterator __l)
 143         : _M_ht(100, hasher(), key_equal(), allocator_type())
 144         { _M_ht.insert_unique(__f, __l); }
 145
 146       template<class _InputIterator>
 147         hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
 148         : _M_ht(__n, hasher(), key_equal(), allocator_type())
 149         { _M_ht.insert_unique(__f, __l); }
 150
 151       template<class _InputIterator>
 152         hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
 153                  const hasher& __hf)
 154         : _M_ht(__n, __hf, key_equal(), allocator_type())
 155         { _M_ht.insert_unique(__f, __l); }
 156
 157       template<class _InputIterator>
 158         hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
 159                  const hasher& __hf, const key_equal& __eql,
 160                  const allocator_type& __a = allocator_type())
 161         : _M_ht(__n, __hf, __eql, __a)
 162         { _M_ht.insert_unique(__f, __l); }
 163
 164       size_type
 165       size() const
 166       { return _M_ht.size(); }
 167
 168       size_type
 169       max_size() const
 170       { return _M_ht.max_size(); }
 171
 172       bool
 173       empty() const
 174       { return _M_ht.empty(); }
 175
 176       void
 177       swap(hash_set& __hs)
 178       { _M_ht.swap(__hs._M_ht); }
 179
 180       template<class _Val, class _HF, class _EqK, class _Al>
 181         friend bool
 182         operator==(const hash_set<_Val, _HF, _EqK, _Al>&,
 183                    const hash_set<_Val, _HF, _EqK, _Al>&);
 184
 185       iterator
 186       begin() const
 187       { return _M_ht.begin(); }
 188
 189       iterator
 190       end() const
 191       { return _M_ht.end(); }
 192
 193       pair<iterator, bool>
 194       insert(const value_type& __obj)
 195       {
 196         pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
 197         return pair<iterator,bool>(__p.first, __p.second);
 198       }
 199
 200       template<class _InputIterator>
 201         void
 202         insert(_InputIterator __f, _InputIterator __l)
 203         { _M_ht.insert_unique(__f, __l); }
 204
 205       pair<iterator, bool>
 206       insert_noresize(const value_type& __obj)
 207       {
 208         pair<typename _Ht::iterator, bool> __p
 209           = _M_ht.insert_unique_noresize(__obj);
 210         return pair<iterator, bool>(__p.first, __p.second);
 211       }
 212
 213       iterator
 214       find(const key_type& __key) const
 215       { return _M_ht.find(__key); }
 216
 217       size_type
 218       count(const key_type& __key) const
 219       { return _M_ht.count(__key); }
 220
 221       pair<iterator, iterator>
 222       equal_range(const key_type& __key) const
 223       { return _M_ht.equal_range(__key); }
 224
 225       size_type
 226       erase(const key_type& __key)
 227       {return _M_ht.erase(__key); }
 228
 229       void
 230       erase(iterator __it)
 231       { _M_ht.erase(__it); }
 232
 233       void
 234       erase(iterator __f, iterator __l)
 235       { _M_ht.erase(__f, __l); }
 236
 237       void
 238       clear()
 239       { _M_ht.clear(); }
 240
 241       void
 242       resize(size_type __hint)
 243       { _M_ht.resize(__hint); }
 244
 245       size_type
 246       bucket_count() const
 247       { return _M_ht.bucket_count(); }
 248
 249       size_type
 250       max_bucket_count() const
 251       { return _M_ht.max_bucket_count(); }
 252
 253       size_type
 254       elems_in_bucket(size_type __n) const
 255       { return _M_ht.elems_in_bucket(__n); }
 256     };
 257
 258   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 259     inline bool
 260     operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
 261                const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
 262     { return __hs1._M_ht == __hs2._M_ht; }
 263
 264   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 265     inline bool
 266     operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1,
 267                const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2)
 268     { return !(__hs1 == __hs2); }
 269
 270   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 271     inline void
 272     swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
 273          hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
 274     { __hs1.swap(__hs2); }
 275
 276
 277   /**
 278    *  This is an SGI extension.
 279    *  @ingroup SGIextensions
 280    *  @doctodo
 281    */
 282   template<class _Value,
 283            class _HashFcn = hash<_Value>,
 284            class _EqualKey = equal_to<_Value>,
 285            class _Alloc = allocator<_Value> >
 286     class hash_multiset
 287     {
 288       // concept requirements
 289       __glibcxx_class_requires(_Value, _SGIAssignableConcept)
 290       __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept)
 291       __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept)
 292
 293     private:
 294       typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
 295                         _EqualKey, _Alloc> _Ht;
 296       _Ht _M_ht;
 297
 298     public:
 299       typedef typename _Ht::key_type key_type;
 300       typedef typename _Ht::value_type value_type;
 301       typedef typename _Ht::hasher hasher;
 302       typedef typename _Ht::key_equal key_equal;
 303
 304       typedef typename _Ht::size_type size_type;
 305       typedef typename _Ht::difference_type difference_type;
 306       typedef typename _Alloc::pointer pointer;
 307       typedef typename _Alloc::const_pointer const_pointer;
 308       typedef typename _Alloc::reference reference;
 309       typedef typename _Alloc::const_reference const_reference;
 310
 311       typedef typename _Ht::const_iterator iterator;
 312       typedef typename _Ht::const_iterator const_iterator;
 313
 314       typedef typename _Ht::allocator_type allocator_type;
 315
 316       hasher
 317       hash_funct() const
 318       { return _M_ht.hash_funct(); }
 319
 320       key_equal
 321       key_eq() const
 322       { return _M_ht.key_eq(); }
 323
 324       allocator_type
 325       get_allocator() const
 326       { return _M_ht.get_allocator(); }
 327
 328       hash_multiset()
 329       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 330
 331       explicit
 332       hash_multiset(size_type __n)
 333       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 334
 335       hash_multiset(size_type __n, const hasher& __hf)
 336       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 337
 338       hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
 339                     const allocator_type& __a = allocator_type())
 340       : _M_ht(__n, __hf, __eql, __a) {}
 341
 342       template<class _InputIterator>
 343         hash_multiset(_InputIterator __f, _InputIterator __l)
 344         : _M_ht(100, hasher(), key_equal(), allocator_type())
 345         { _M_ht.insert_equal(__f, __l); }
 346
 347       template<class _InputIterator>
 348         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
 349         : _M_ht(__n, hasher(), key_equal(), allocator_type())
 350         { _M_ht.insert_equal(__f, __l); }
 351
 352       template<class _InputIterator>
 353         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
 354                       const hasher& __hf)
 355         : _M_ht(__n, __hf, key_equal(), allocator_type())
 356         { _M_ht.insert_equal(__f, __l); }
 357
 358       template<class _InputIterator>
 359         hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
 360                       const hasher& __hf, const key_equal& __eql,
 361                       const allocator_type& __a = allocator_type())
 362         : _M_ht(__n, __hf, __eql, __a)
 363         { _M_ht.insert_equal(__f, __l); }
 364
 365       size_type
 366       size() const
 367       { return _M_ht.size(); }
 368
 369       size_type
 370       max_size() const
 371       { return _M_ht.max_size(); }
 372
 373       bool
 374       empty() const
 375       { return _M_ht.empty(); }
 376
 377       void
 378       swap(hash_multiset& hs)
 379       { _M_ht.swap(hs._M_ht); }
 380
 381       template<class _Val, class _HF, class _EqK, class _Al>
 382         friend bool
 383         operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&,
 384                    const hash_multiset<_Val, _HF, _EqK, _Al>&);
 385
 386       iterator
 387       begin() const
 388       { return _M_ht.begin(); }
 389
 390       iterator
 391       end() const
 392       { return _M_ht.end(); }
 393
 394       iterator
 395       insert(const value_type& __obj)
 396       { return _M_ht.insert_equal(__obj); }
 397
 398       template<class _InputIterator>
 399         void
 400         insert(_InputIterator __f, _InputIterator __l)
 401         { _M_ht.insert_equal(__f,__l); }
 402
 403       iterator
 404       insert_noresize(const value_type& __obj)
 405       { return _M_ht.insert_equal_noresize(__obj); }
 406
 407       iterator
 408       find(const key_type& __key) const
 409       { return _M_ht.find(__key); }
 410
 411       size_type
 412       count(const key_type& __key) const
 413       { return _M_ht.count(__key); }
 414
 415       pair<iterator, iterator>
 416       equal_range(const key_type& __key) const
 417       { return _M_ht.equal_range(__key); }
 418
 419       size_type
 420       erase(const key_type& __key)
 421       { return _M_ht.erase(__key); }
 422
 423       void
 424       erase(iterator __it)
 425       { _M_ht.erase(__it); }
 426
 427       void
 428       erase(iterator __f, iterator __l)
 429       { _M_ht.erase(__f, __l); }
 430
 431       void
 432       clear()
 433       { _M_ht.clear(); }
 434
 435       void
 436       resize(size_type __hint)
 437       { _M_ht.resize(__hint); }
 438
 439       size_type
 440       bucket_count() const
 441       { return _M_ht.bucket_count(); }
 442
 443       size_type
 444       max_bucket_count() const
 445       { return _M_ht.max_bucket_count(); }
 446
 447       size_type
 448       elems_in_bucket(size_type __n) const
 449       { return _M_ht.elems_in_bucket(__n); }
 450     };
 451
 452   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 453     inline bool
 454     operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
 455                const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
 456     { return __hs1._M_ht == __hs2._M_ht; }
 457
 458   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 459     inline bool
 460     operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
 461                const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
 462     { return !(__hs1 == __hs2); }
 463
 464   template<class _Val, class _HashFcn, class _EqualKey, class _Alloc>
 465     inline void
 466     swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1,
 467          hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2)
 468     { __hs1.swap(__hs2); }
 469
 470 _GLIBCXX_END_NAMESPACE_VERSION
 471 } // namespace
 472
 473 namespace std _GLIBCXX_VISIBILITY(default)
 474 {
 475 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 476
 477   // Specialization of insert_iterator so that it will work for hash_set
 478   // and hash_multiset.
 479   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 480     class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn,
 481                                               _EqualKey, _Alloc> >
 482     {
 483     protected:
 484       typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc>
 485         _Container;
 486       _Container* container;
 487
 488     public:
 489       typedef _Container          container_type;
 490       typedef output_iterator_tag iterator_category;
 491       typedef void                value_type;
 492       typedef void                difference_type;
 493       typedef void                pointer;
 494       typedef void                reference;
 495
 496       insert_iterator(_Container& __x)
 497       : container(&__x) {}
 498
 499       insert_iterator(_Container& __x, typename _Container::iterator)
 500       : container(&__x) {}
 501
 502       insert_iterator<_Container>&
 503       operator=(const typename _Container::value_type& __value)
 504       {
 505         container->insert(__value);
 506         return *this;
 507       }
 508
 509       insert_iterator<_Container>&
 510       operator*()
 511       { return *this; }
 512
 513       insert_iterator<_Container>&
 514       operator++()
 515       { return *this; }
 516
 517       insert_iterator<_Container>&
 518       operator++(int)
 519       { return *this; }
 520     };
 521
 522   template<class _Value, class _HashFcn, class _EqualKey, class _Alloc>
 523     class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn,
 524                                                    _EqualKey, _Alloc> >
 525     {
 526     protected:
 527       typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc>
 528         _Container;
 529       _Container* container;
 530       typename _Container::iterator iter;
 531
 532     public:
 533       typedef _Container          container_type;
 534       typedef output_iterator_tag iterator_category;
 535       typedef void                value_type;
 536       typedef void                difference_type;
 537       typedef void                pointer;
 538       typedef void                reference;
 539
 540       insert_iterator(_Container& __x)
 541       : container(&__x) {}
 542
 543       insert_iterator(_Container& __x, typename _Container::iterator)
 544       : container(&__x) {}
 545
 546       insert_iterator<_Container>&
 547       operator=(const typename _Container::value_type& __value)
 548       {
 549         container->insert(__value);
 550         return *this;
 551       }
 552
 553       insert_iterator<_Container>&
 554       operator*()
 555       { return *this; }
 556
 557       insert_iterator<_Container>&
 558       operator++()
 559       { return *this; }
 560
 561       insert_iterator<_Container>&
 562       operator++(int) { return *this; }
 563     };
 564
 565 _GLIBCXX_END_NAMESPACE_VERSION
 566 } // namespace
 567
 568 #endif