prebuilt/linux-x86/toolchain/i686-linux-glibc2.7-4.4.3/i686-linux/include/c++/4.4.3/backward/hash_set

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