l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.3.3/include/backward/hash_set

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