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