1/*
2 * Copyright (c) 1996
3 * Silicon Graphics Computer Systems, Inc.
4 *
5 * Permission to use, copy, modify, distribute and sell this software
6 * and its documentation for any purpose is hereby granted without fee,
7 * provided that the above copyright notice appear in all copies and
8 * that both that copyright notice and this permission notice appear
9 * in supporting documentation.  Silicon Graphics makes no
10 * representations about the suitability of this software for any
11 * purpose.  It is provided "as is" without express or implied warranty.
12 *
13 *
14 * Copyright (c) 1994
15 * Hewlett-Packard Company
16 *
17 * Permission to use, copy, modify, distribute and sell this software
18 * and its documentation for any purpose is hereby granted without fee,
19 * provided that the above copyright notice appear in all copies and
20 * that both that copyright notice and this permission notice appear
21 * in supporting documentation.  Hewlett-Packard Company makes no
22 * representations about the suitability of this software for any
23 * purpose.  It is provided "as is" without express or implied warranty.
24 *
25 */
26
27/* NOTE: This is an internal header file, included by other STL headers.
28 *   You should not attempt to use it directly.
29 */
30
31#ifndef __SGI_STL_INTERNAL_HASH_SET_H
32#define __SGI_STL_INTERNAL_HASH_SET_H
33
34__STL_BEGIN_NAMESPACE
35
36#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
37#pragma set woff 1174
38#pragma set woff 1375
39#endif
40
41#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
42template <class _Value, class _HashFcn = hash<_Value>,
43          class _EqualKey = equal_to<_Value>,
44          class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
45#else
46template <class _Value, class _HashFcn, class _EqualKey,
47          class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
48#endif
49class hash_set
50{
51private:
52  typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
53                    _EqualKey, _Alloc> _Ht;
54  _Ht _M_ht;
55
56public:
57  typedef typename _Ht::key_type key_type;
58  typedef typename _Ht::value_type value_type;
59  typedef typename _Ht::hasher hasher;
60  typedef typename _Ht::key_equal key_equal;
61
62  typedef typename _Ht::size_type size_type;
63  typedef typename _Ht::difference_type difference_type;
64  typedef typename _Ht::const_pointer pointer;
65  typedef typename _Ht::const_pointer const_pointer;
66  typedef typename _Ht::const_reference reference;
67  typedef typename _Ht::const_reference const_reference;
68
69  typedef typename _Ht::const_iterator iterator;
70  typedef typename _Ht::const_iterator const_iterator;
71
72  typedef typename _Ht::allocator_type allocator_type;
73
74  hasher hash_funct() const { return _M_ht.hash_funct(); }
75  key_equal key_eq() const { return _M_ht.key_eq(); }
76  allocator_type get_allocator() const { return _M_ht.get_allocator(); }
77
78public:
79  hash_set()
80    : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
81  explicit hash_set(size_type __n)
82    : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
83  hash_set(size_type __n, const hasher& __hf)
84    : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
85  hash_set(size_type __n, const hasher& __hf, const key_equal& __eql,
86           const allocator_type& __a = allocator_type())
87    : _M_ht(__n, __hf, __eql, __a) {}
88
89#ifdef __STL_MEMBER_TEMPLATES
90  template <class _InputIterator>
91  hash_set(_InputIterator __f, _InputIterator __l)
92    : _M_ht(100, hasher(), key_equal(), allocator_type())
93    { _M_ht.insert_unique(__f, __l); }
94  template <class _InputIterator>
95  hash_set(_InputIterator __f, _InputIterator __l, size_type __n)
96    : _M_ht(__n, hasher(), key_equal(), allocator_type())
97    { _M_ht.insert_unique(__f, __l); }
98  template <class _InputIterator>
99  hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
100           const hasher& __hf)
101    : _M_ht(__n, __hf, key_equal(), allocator_type())
102    { _M_ht.insert_unique(__f, __l); }
103  template <class _InputIterator>
104  hash_set(_InputIterator __f, _InputIterator __l, size_type __n,
105           const hasher& __hf, const key_equal& __eql,
106           const allocator_type& __a = allocator_type())
107    : _M_ht(__n, __hf, __eql, __a)
108    { _M_ht.insert_unique(__f, __l); }
109#else
110
111  hash_set(const value_type* __f, const value_type* __l)
112    : _M_ht(100, hasher(), key_equal(), allocator_type())
113    { _M_ht.insert_unique(__f, __l); }
114  hash_set(const value_type* __f, const value_type* __l, size_type __n)
115    : _M_ht(__n, hasher(), key_equal(), allocator_type())
116    { _M_ht.insert_unique(__f, __l); }
117  hash_set(const value_type* __f, const value_type* __l, size_type __n,
118           const hasher& __hf)
119    : _M_ht(__n, __hf, key_equal(), allocator_type())
120    { _M_ht.insert_unique(__f, __l); }
121  hash_set(const value_type* __f, const value_type* __l, size_type __n,
122           const hasher& __hf, const key_equal& __eql,
123           const allocator_type& __a = allocator_type())
124    : _M_ht(__n, __hf, __eql, __a)
125    { _M_ht.insert_unique(__f, __l); }
126
127  hash_set(const_iterator __f, const_iterator __l)
128    : _M_ht(100, hasher(), key_equal(), allocator_type())
129    { _M_ht.insert_unique(__f, __l); }
130  hash_set(const_iterator __f, const_iterator __l, size_type __n)
131    : _M_ht(__n, hasher(), key_equal(), allocator_type())
132    { _M_ht.insert_unique(__f, __l); }
133  hash_set(const_iterator __f, const_iterator __l, size_type __n,
134           const hasher& __hf)
135    : _M_ht(__n, __hf, key_equal(), allocator_type())
136    { _M_ht.insert_unique(__f, __l); }
137  hash_set(const_iterator __f, const_iterator __l, size_type __n,
138           const hasher& __hf, const key_equal& __eql,
139           const allocator_type& __a = allocator_type())
140    : _M_ht(__n, __hf, __eql, __a)
141    { _M_ht.insert_unique(__f, __l); }
142#endif /*__STL_MEMBER_TEMPLATES */
143
144public:
145  size_type size() const { return _M_ht.size(); }
146  size_type max_size() const { return _M_ht.max_size(); }
147  bool empty() const { return _M_ht.empty(); }
148  void swap(hash_set& __hs) { _M_ht.swap(__hs._M_ht); }
149  friend bool operator== __STL_NULL_TMPL_ARGS (const hash_set&,
150                                               const hash_set&);
151
152  iterator begin() const { return _M_ht.begin(); }
153  iterator end() const { return _M_ht.end(); }
154
155public:
156  pair<iterator, bool> insert(const value_type& __obj)
157    {
158      pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj);
159      return pair<iterator,bool>(__p.first, __p.second);
160    }
161#ifdef __STL_MEMBER_TEMPLATES
162  template <class _InputIterator>
163  void insert(_InputIterator __f, _InputIterator __l)
164    { _M_ht.insert_unique(__f,__l); }
165#else
166  void insert(const value_type* __f, const value_type* __l) {
167    _M_ht.insert_unique(__f,__l);
168  }
169  void insert(const_iterator __f, const_iterator __l)
170    {_M_ht.insert_unique(__f, __l); }
171#endif /*__STL_MEMBER_TEMPLATES */
172  pair<iterator, bool> insert_noresize(const value_type& __obj)
173  {
174    pair<typename _Ht::iterator, bool> __p =
175      _M_ht.insert_unique_noresize(__obj);
176    return pair<iterator, bool>(__p.first, __p.second);
177  }
178
179  iterator find(const key_type& __key) const { return _M_ht.find(__key); }
180
181  size_type count(const key_type& __key) const { return _M_ht.count(__key); }
182
183  pair<iterator, iterator> equal_range(const key_type& __key) const
184    { return _M_ht.equal_range(__key); }
185
186  size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
187  void erase(iterator __it) { _M_ht.erase(__it); }
188  void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
189  void clear() { _M_ht.clear(); }
190
191public:
192  void resize(size_type __hint) { _M_ht.resize(__hint); }
193  size_type bucket_count() const { return _M_ht.bucket_count(); }
194  size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
195  size_type elems_in_bucket(size_type __n) const
196    { return _M_ht.elems_in_bucket(__n); }
197};
198
199template <class _Value, class _HashFcn, class _EqualKey, class _Alloc>
200inline bool
201operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1,
202           const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2)
203{
204  return __hs1._M_ht == __hs2._M_ht;
205}
206
207#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
208
209template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
210inline void
211swap(hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
212     hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2)
213{
214  __hs1.swap(__hs2);
215}
216
217#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
218
219
220#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
221template <class _Value, class _HashFcn = hash<_Value>,
222          class _EqualKey = equal_to<_Value>,
223          class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
224#else
225template <class _Value, class _HashFcn, class _EqualKey,
226          class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
227#endif
228class hash_multiset
229{
230private:
231  typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
232                    _EqualKey, _Alloc> _Ht;
233  _Ht _M_ht;
234
235public:
236  typedef typename _Ht::key_type key_type;
237  typedef typename _Ht::value_type value_type;
238  typedef typename _Ht::hasher hasher;
239  typedef typename _Ht::key_equal key_equal;
240
241  typedef typename _Ht::size_type size_type;
242  typedef typename _Ht::difference_type difference_type;
243  typedef typename _Ht::const_pointer pointer;
244  typedef typename _Ht::const_pointer const_pointer;
245  typedef typename _Ht::const_reference reference;
246  typedef typename _Ht::const_reference const_reference;
247
248  typedef typename _Ht::const_iterator iterator;
249  typedef typename _Ht::const_iterator const_iterator;
250
251  typedef typename _Ht::allocator_type allocator_type;
252
253  hasher hash_funct() const { return _M_ht.hash_funct(); }
254  key_equal key_eq() const { return _M_ht.key_eq(); }
255  allocator_type get_allocator() const { return _M_ht.get_allocator(); }
256
257public:
258  hash_multiset()
259    : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
260  explicit hash_multiset(size_type __n)
261    : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
262  hash_multiset(size_type __n, const hasher& __hf)
263    : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
264  hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql,
265                const allocator_type& __a = allocator_type())
266    : _M_ht(__n, __hf, __eql, __a) {}
267
268#ifdef __STL_MEMBER_TEMPLATES
269  template <class _InputIterator>
270  hash_multiset(_InputIterator __f, _InputIterator __l)
271    : _M_ht(100, hasher(), key_equal(), allocator_type())
272    { _M_ht.insert_equal(__f, __l); }
273  template <class _InputIterator>
274  hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n)
275    : _M_ht(__n, hasher(), key_equal(), allocator_type())
276    { _M_ht.insert_equal(__f, __l); }
277  template <class _InputIterator>
278  hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
279                const hasher& __hf)
280    : _M_ht(__n, __hf, key_equal(), allocator_type())
281    { _M_ht.insert_equal(__f, __l); }
282  template <class _InputIterator>
283  hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n,
284                const hasher& __hf, const key_equal& __eql,
285                const allocator_type& __a = allocator_type())
286    : _M_ht(__n, __hf, __eql, __a)
287    { _M_ht.insert_equal(__f, __l); }
288#else
289
290  hash_multiset(const value_type* __f, const value_type* __l)
291    : _M_ht(100, hasher(), key_equal(), allocator_type())
292    { _M_ht.insert_equal(__f, __l); }
293  hash_multiset(const value_type* __f, const value_type* __l, size_type __n)
294    : _M_ht(__n, hasher(), key_equal(), allocator_type())
295    { _M_ht.insert_equal(__f, __l); }
296  hash_multiset(const value_type* __f, const value_type* __l, size_type __n,
297                const hasher& __hf)
298    : _M_ht(__n, __hf, key_equal(), allocator_type())
299    { _M_ht.insert_equal(__f, __l); }
300  hash_multiset(const value_type* __f, const value_type* __l, size_type __n,
301                const hasher& __hf, const key_equal& __eql,
302                const allocator_type& __a = allocator_type())
303    : _M_ht(__n, __hf, __eql, __a)
304    { _M_ht.insert_equal(__f, __l); }
305
306  hash_multiset(const_iterator __f, const_iterator __l)
307    : _M_ht(100, hasher(), key_equal(), allocator_type())
308    { _M_ht.insert_equal(__f, __l); }
309  hash_multiset(const_iterator __f, const_iterator __l, size_type __n)
310    : _M_ht(__n, hasher(), key_equal(), allocator_type())
311    { _M_ht.insert_equal(__f, __l); }
312  hash_multiset(const_iterator __f, const_iterator __l, size_type __n,
313                const hasher& __hf)
314    : _M_ht(__n, __hf, key_equal(), allocator_type())
315    { _M_ht.insert_equal(__f, __l); }
316  hash_multiset(const_iterator __f, const_iterator __l, size_type __n,
317                const hasher& __hf, const key_equal& __eql,
318                const allocator_type& __a = allocator_type())
319    : _M_ht(__n, __hf, __eql, __a)
320    { _M_ht.insert_equal(__f, __l); }
321#endif /*__STL_MEMBER_TEMPLATES */
322
323public:
324  size_type size() const { return _M_ht.size(); }
325  size_type max_size() const { return _M_ht.max_size(); }
326  bool empty() const { return _M_ht.empty(); }
327  void swap(hash_multiset& hs) { _M_ht.swap(hs._M_ht); }
328  friend bool operator== __STL_NULL_TMPL_ARGS (const hash_multiset&,
329                                               const hash_multiset&);
330
331  iterator begin() const { return _M_ht.begin(); }
332  iterator end() const { return _M_ht.end(); }
333
334public:
335  iterator insert(const value_type& __obj)
336    { return _M_ht.insert_equal(__obj); }
337#ifdef __STL_MEMBER_TEMPLATES
338  template <class _InputIterator>
339  void insert(_InputIterator __f, _InputIterator __l)
340    { _M_ht.insert_equal(__f,__l); }
341#else
342  void insert(const value_type* __f, const value_type* __l) {
343    _M_ht.insert_equal(__f,__l);
344  }
345  void insert(const_iterator __f, const_iterator __l)
346    { _M_ht.insert_equal(__f, __l); }
347#endif /*__STL_MEMBER_TEMPLATES */
348  iterator insert_noresize(const value_type& __obj)
349    { return _M_ht.insert_equal_noresize(__obj); }
350
351  iterator find(const key_type& __key) const { return _M_ht.find(__key); }
352
353  size_type count(const key_type& __key) const { return _M_ht.count(__key); }
354
355  pair<iterator, iterator> equal_range(const key_type& __key) const
356    { return _M_ht.equal_range(__key); }
357
358  size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
359  void erase(iterator __it) { _M_ht.erase(__it); }
360  void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
361  void clear() { _M_ht.clear(); }
362
363public:
364  void resize(size_type __hint) { _M_ht.resize(__hint); }
365  size_type bucket_count() const { return _M_ht.bucket_count(); }
366  size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
367  size_type elems_in_bucket(size_type __n) const
368    { return _M_ht.elems_in_bucket(__n); }
369};
370
371template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
372inline bool
373operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
374           const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2)
375{
376  return __hs1._M_ht == __hs2._M_ht;
377}
378
379#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
380
381template <class _Val, class _HashFcn, class _EqualKey, class _Alloc>
382inline void
383swap(hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1,
384     hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) {
385  __hs1.swap(__hs2);
386}
387
388#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
389
390#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
391#pragma reset woff 1174
392#pragma reset woff 1375
393#endif
394
395__STL_END_NAMESPACE
396
397#endif /* __SGI_STL_INTERNAL_HASH_SET_H */
398
399// Local Variables:
400// mode:C++
401// End:
402