Merge branch 'vendor/GCC44'
[dragonfly.git] / contrib / gcc-4.4 / libstdc++-v3 / include / backward / hash_set
CommitLineData
c251ad9e
SS
1// Hashing set implementation -*- C++ -*-
2
4b1e227d
SW
3// Copyright (C) 2001, 2002, 2004, 2005, 2006, 2009, 2010
4// Free Software Foundation, Inc.
c251ad9e
SS
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
4b1e227d
SW
57#ifndef _BACKWARD_HASH_SET
58#define _BACKWARD_HASH_SET 1
c251ad9e
SS
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