1 /*
2 *
3 * Copyright (c) 1994
4 * Hewlett-Packard Company
5 *
6 * Copyright (c) 1996,1997
7 * Silicon Graphics Computer Systems, Inc.
8 *
9 * Copyright (c) 1997
10 * Moscow Center for SPARC Technology
11 *
12 * Copyright (c) 1999
13 * Boris Fomitchev
14 *
15 * This material is provided "as is", with absolutely no warranty expressed
16 * or implied. Any use is at your own risk.
17 *
18 * Permission to use or copy this software for any purpose is hereby granted
19 * without fee, provided the above notices are retained on all copies.
20 * Permission to modify the code and to distribute modified code is granted,
21 * provided the above notices are retained, and a notice that the code was
22 * modified is included with the above copyright notice.
23 *
24 */
25
26 /* NOTE: This is an internal header file, included by other STL headers.
27 * You should not attempt to use it directly.
28 */
29
30 #ifndef _STLP_INTERNAL_SET_H
31 #define _STLP_INTERNAL_SET_H
32
33 #ifndef _STLP_INTERNAL_TREE_H
34 # include <stl/_tree.h>
35 #endif
36
37 #if !defined (_STLP_USE_PTR_SPECIALIZATIONS)
38
39 _STLP_BEGIN_NAMESPACE
40
41 //Specific iterator traits creation
_STLP_CREATE_ITERATOR_TRAITS(SetTraitsT,Const_traits)42 _STLP_CREATE_ITERATOR_TRAITS(SetTraitsT, Const_traits)
43
44 template <class _Key, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key>),
45 _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Key>) >
46 class set
47 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
48 : public __stlport_class<set<_Key, _Compare, _Alloc> >
49 #endif
50 {
51 typedef set<_Key, _Compare, _Alloc> _Self;
52 public:
53 // typedefs:
54 typedef _Key key_type;
55 typedef _Key value_type;
56 typedef _Compare key_compare;
57 typedef _Compare value_compare;
58
59 private:
60 //Specific iterator traits creation
61 typedef _STLP_PRIV _SetTraitsT<value_type> _SetTraits;
62
63 public:
64 //Following typedef have to be public for __move_traits specialization.
65 typedef _STLP_PRIV _Rb_tree<key_type, key_compare,
66 value_type, _STLP_PRIV _Identity<value_type>,
67 _SetTraits, _Alloc> _Rep_type;
68
69 typedef typename _Rep_type::pointer pointer;
70 typedef typename _Rep_type::const_pointer const_pointer;
71 typedef typename _Rep_type::reference reference;
72 typedef typename _Rep_type::const_reference const_reference;
73 typedef typename _Rep_type::iterator iterator;
74 typedef typename _Rep_type::const_iterator const_iterator;
75 typedef typename _Rep_type::reverse_iterator reverse_iterator;
76 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
77 typedef typename _Rep_type::size_type size_type;
78 typedef typename _Rep_type::difference_type difference_type;
79 typedef typename _Rep_type::allocator_type allocator_type;
80
81 private:
82 _Rep_type _M_t; // red-black tree representing set
83 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
84
85 public:
86
87 // allocation/deallocation
88 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
89 explicit set(const _Compare& __comp = _Compare(),
90 const allocator_type& __a = allocator_type())
91 #else
92 set()
93 : _M_t(_Compare(), allocator_type()) {}
94 explicit set(const _Compare& __comp)
95 : _M_t(__comp, allocator_type()) {}
96 set(const _Compare& __comp, const allocator_type& __a)
97 #endif
98 : _M_t(__comp, __a) {}
99
100 #if defined (_STLP_MEMBER_TEMPLATES)
101 template <class _InputIterator>
102 set(_InputIterator __first, _InputIterator __last)
103 : _M_t(_Compare(), allocator_type())
104 { _M_t.insert_unique(__first, __last); }
105
106 # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
107 template <class _InputIterator>
108 set(_InputIterator __first, _InputIterator __last, const _Compare& __comp)
109 : _M_t(__comp, allocator_type()) { _M_t.insert_unique(__first, __last); }
110 # endif
111 template <class _InputIterator>
112 set(_InputIterator __first, _InputIterator __last, const _Compare& __comp,
113 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
114 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
115 #else
116 set(const value_type* __first, const value_type* __last)
117 : _M_t(_Compare(), allocator_type())
118 { _M_t.insert_unique(__first, __last); }
119
120 set(const value_type* __first,
121 const value_type* __last, const _Compare& __comp,
122 const allocator_type& __a = allocator_type())
123 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
124
125 set(const_iterator __first, const_iterator __last)
126 : _M_t(_Compare(), allocator_type())
127 { _M_t.insert_unique(__first, __last); }
128
129 set(const_iterator __first, const_iterator __last, const _Compare& __comp,
130 const allocator_type& __a = allocator_type())
131 : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
132 #endif /* _STLP_MEMBER_TEMPLATES */
133
134 set(const _Self& __x) : _M_t(__x._M_t) {}
135
136 #if !defined (_STLP_NO_MOVE_SEMANTIC)
137 set(__move_source<_Self> src)
138 : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {}
139 #endif
140
141 _Self& operator=(const _Self& __x) {
142 _M_t = __x._M_t;
143 return *this;
144 }
145
146 // accessors:
147 key_compare key_comp() const { return _M_t.key_comp(); }
148 value_compare value_comp() const { return _M_t.key_comp(); }
149 allocator_type get_allocator() const { return _M_t.get_allocator(); }
150
151 iterator begin() { return _M_t.begin(); }
152 iterator end() { return _M_t.end(); }
153 const_iterator begin() const { return _M_t.begin(); }
154 const_iterator end() const { return _M_t.end(); }
155 reverse_iterator rbegin() { return _M_t.rbegin(); }
156 reverse_iterator rend() { return _M_t.rend(); }
157 const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
158 const_reverse_iterator rend() const { return _M_t.rend(); }
159 bool empty() const { return _M_t.empty(); }
160 size_type size() const { return _M_t.size(); }
161 size_type max_size() const { return _M_t.max_size(); }
162 void swap(_Self& __x) { _M_t.swap(__x._M_t); }
163 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
164 void _M_swap_workaround(_Self& __x) { swap(__x); }
165 #endif
166
167 // insert/erase
168 pair<iterator,bool> insert(const value_type& __x)
169 { return _M_t.insert_unique(__x); }
170 iterator insert(iterator __pos, const value_type& __x)
171 { return _M_t.insert_unique( __pos , __x); }
172 #if defined (_STLP_MEMBER_TEMPLATES)
173 template <class _InputIterator>
174 void insert(_InputIterator __first, _InputIterator __last)
175 { _M_t.insert_unique(__first, __last); }
176 #else
177 void insert(const_iterator __first, const_iterator __last)
178 { _M_t.insert_unique(__first, __last); }
179 void insert(const value_type* __first, const value_type* __last)
180 { _M_t.insert_unique(__first, __last); }
181 #endif /* _STLP_MEMBER_TEMPLATES */
182 void erase(iterator __pos) { _M_t.erase( __pos ); }
183 size_type erase(const key_type& __x) { return _M_t.erase_unique(__x); }
184 void erase(iterator __first, iterator __last) { _M_t.erase(__first, __last ); }
185 void clear() { _M_t.clear(); }
186
187 // set operations:
188 _STLP_TEMPLATE_FOR_CONT_EXT
189 const_iterator find(const _KT& __x) const { return _M_t.find(__x); }
190 _STLP_TEMPLATE_FOR_CONT_EXT
191 iterator find(const _KT& __x) { return _M_t.find(__x); }
192 _STLP_TEMPLATE_FOR_CONT_EXT
193 size_type count(const _KT& __x) const
194 { return _M_t.find(__x) == _M_t.end() ? 0 : 1 ; }
195 _STLP_TEMPLATE_FOR_CONT_EXT
196 iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); }
197 _STLP_TEMPLATE_FOR_CONT_EXT
198 const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); }
199 _STLP_TEMPLATE_FOR_CONT_EXT
200 iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); }
201 _STLP_TEMPLATE_FOR_CONT_EXT
202 const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); }
203 _STLP_TEMPLATE_FOR_CONT_EXT
204 pair<iterator, iterator> equal_range(const _KT& __x)
205 { return _M_t.equal_range_unique(__x); }
206 _STLP_TEMPLATE_FOR_CONT_EXT
207 pair<const_iterator, const_iterator> equal_range(const _KT& __x) const
208 { return _M_t.equal_range_unique(__x); }
209 };
210
211 //Specific iterator traits creation
_STLP_CREATE_ITERATOR_TRAITS(MultisetTraitsT,Const_traits)212 _STLP_CREATE_ITERATOR_TRAITS(MultisetTraitsT, Const_traits)
213
214 template <class _Key, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key>),
215 _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Key>) >
216 class multiset
217 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
218 : public __stlport_class<multiset<_Key, _Compare, _Alloc> >
219 #endif
220 {
221 typedef multiset<_Key, _Compare, _Alloc> _Self;
222 public:
223 // typedefs:
224
225 typedef _Key key_type;
226 typedef _Key value_type;
227 typedef _Compare key_compare;
228 typedef _Compare value_compare;
229
230 private:
231 //Specific iterator traits creation
232 typedef _STLP_PRIV _MultisetTraitsT<value_type> _MultisetTraits;
233
234 public:
235 //Following typedef have to be public for __move_traits specialization.
236 typedef _STLP_PRIV _Rb_tree<key_type, key_compare,
237 value_type, _STLP_PRIV _Identity<value_type>,
238 _MultisetTraits, _Alloc> _Rep_type;
239
240 typedef typename _Rep_type::pointer pointer;
241 typedef typename _Rep_type::const_pointer const_pointer;
242 typedef typename _Rep_type::reference reference;
243 typedef typename _Rep_type::const_reference const_reference;
244 typedef typename _Rep_type::iterator iterator;
245 typedef typename _Rep_type::const_iterator const_iterator;
246 typedef typename _Rep_type::reverse_iterator reverse_iterator;
247 typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
248 typedef typename _Rep_type::size_type size_type;
249 typedef typename _Rep_type::difference_type difference_type;
250 typedef typename _Rep_type::allocator_type allocator_type;
251
252 private:
253 _Rep_type _M_t; // red-black tree representing multiset
254 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
255
256 public:
257 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
258 explicit multiset(const _Compare& __comp = _Compare(),
259 const allocator_type& __a = allocator_type())
260 #else
261 multiset()
262 : _M_t(_Compare(), allocator_type()) {}
263 explicit multiset(const _Compare& __comp)
264 : _M_t(__comp, allocator_type()) {}
265 multiset(const _Compare& __comp, const allocator_type& __a)
266 #endif
267 : _M_t(__comp, __a) {}
268
269 #if defined (_STLP_MEMBER_TEMPLATES)
270 template <class _InputIterator>
271 multiset(_InputIterator __first, _InputIterator __last)
272 : _M_t(_Compare(), allocator_type())
273 { _M_t.insert_equal(__first, __last); }
274
275 template <class _InputIterator>
276 multiset(_InputIterator __first, _InputIterator __last,
277 const _Compare& __comp,
278 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
279 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
280 # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
281 template <class _InputIterator>
282 multiset(_InputIterator __first, _InputIterator __last,
283 const _Compare& __comp)
284 : _M_t(__comp, allocator_type()) { _M_t.insert_equal(__first, __last); }
285 # endif
286 #else
287 multiset(const value_type* __first, const value_type* __last)
288 : _M_t(_Compare(), allocator_type())
289 { _M_t.insert_equal(__first, __last); }
290
291 multiset(const value_type* __first, const value_type* __last,
292 const _Compare& __comp,
293 const allocator_type& __a = allocator_type())
294 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
295
296 multiset(const_iterator __first, const_iterator __last)
297 : _M_t(_Compare(), allocator_type())
298 { _M_t.insert_equal(__first, __last); }
299
300 multiset(const_iterator __first, const_iterator __last,
301 const _Compare& __comp,
302 const allocator_type& __a = allocator_type())
303 : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
304 #endif /* _STLP_MEMBER_TEMPLATES */
305
306 multiset(const _Self& __x) : _M_t(__x._M_t) {}
307 _Self& operator=(const _Self& __x) {
308 _M_t = __x._M_t;
309 return *this;
310 }
311
312 #if !defined (_STLP_NO_MOVE_SEMANTIC)
313 multiset(__move_source<_Self> src)
314 : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {}
315 #endif
316
317 // accessors:
318 key_compare key_comp() const { return _M_t.key_comp(); }
319 value_compare value_comp() const { return _M_t.key_comp(); }
320 allocator_type get_allocator() const { return _M_t.get_allocator(); }
321
322 iterator begin() { return _M_t.begin(); }
323 iterator end() { return _M_t.end(); }
324 const_iterator begin() const { return _M_t.begin(); }
325 const_iterator end() const { return _M_t.end(); }
326 reverse_iterator rbegin() { return _M_t.rbegin(); }
327 reverse_iterator rend() { return _M_t.rend(); }
328 const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
329 const_reverse_iterator rend() const { return _M_t.rend(); }
330 bool empty() const { return _M_t.empty(); }
331 size_type size() const { return _M_t.size(); }
332 size_type max_size() const { return _M_t.max_size(); }
333 void swap(_Self& __x) { _M_t.swap(__x._M_t); }
334 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
335 void _M_swap_workaround(_Self& __x) { swap(__x); }
336 #endif
337
338 // insert/erase
339 iterator insert(const value_type& __x)
340 { return _M_t.insert_equal(__x); }
341 iterator insert(iterator __pos, const value_type& __x)
342 { return _M_t.insert_equal(__pos, __x); }
343
344 #if defined (_STLP_MEMBER_TEMPLATES)
345 template <class _InputIterator>
346 void insert(_InputIterator __first, _InputIterator __last)
347 { _M_t.insert_equal(__first, __last); }
348 #else
349 void insert(const value_type* __first, const value_type* __last)
350 { _M_t.insert_equal(__first, __last); }
351 void insert(const_iterator __first, const_iterator __last)
352 { _M_t.insert_equal(__first, __last); }
353 #endif /* _STLP_MEMBER_TEMPLATES */
354 void erase(iterator __pos) { _M_t.erase( __pos ); }
355 size_type erase(const key_type& __x) { return _M_t.erase(__x); }
356 void erase(iterator __first, iterator __last) { _M_t.erase( __first, __last ); }
357 void clear() { _M_t.clear(); }
358
359 // multiset operations:
360 _STLP_TEMPLATE_FOR_CONT_EXT
361 iterator find(const _KT& __x) { return _M_t.find(__x); }
362 _STLP_TEMPLATE_FOR_CONT_EXT
363 const_iterator find(const _KT& __x) const { return _M_t.find(__x); }
364 _STLP_TEMPLATE_FOR_CONT_EXT
365 size_type count(const _KT& __x) const { return _M_t.count(__x); }
366 _STLP_TEMPLATE_FOR_CONT_EXT
367 iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); }
368 _STLP_TEMPLATE_FOR_CONT_EXT
369 const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); }
370 _STLP_TEMPLATE_FOR_CONT_EXT
371 iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); }
372 _STLP_TEMPLATE_FOR_CONT_EXT
373 const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); }
374 _STLP_TEMPLATE_FOR_CONT_EXT
375 pair<iterator, iterator> equal_range(const _KT& __x) { return _M_t.equal_range(__x); }
376 _STLP_TEMPLATE_FOR_CONT_EXT
377 pair<const_iterator, const_iterator> equal_range(const _KT& __x) const { return _M_t.equal_range(__x); }
378 };
379
380 #else
381 # include <stl/pointers/_set.h>
382 _STLP_BEGIN_NAMESPACE
383 #endif /* _STLP_USE_PTR_SPECIALIZATIONS */
384
385 #define _STLP_TEMPLATE_HEADER template <class _Key, class _Compare, class _Alloc>
386 #define _STLP_TEMPLATE_CONTAINER set<_Key,_Compare,_Alloc>
387 #include <stl/_relops_cont.h>
388 #undef _STLP_TEMPLATE_CONTAINER
389 #define _STLP_TEMPLATE_CONTAINER multiset<_Key,_Compare,_Alloc>
390 #include <stl/_relops_cont.h>
391 #undef _STLP_TEMPLATE_CONTAINER
392 #undef _STLP_TEMPLATE_HEADER
393
394 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC)
395 template <class _Key, class _Compare, class _Alloc>
396 struct __move_traits<set<_Key,_Compare,_Alloc> > :
397 _STLP_PRIV __move_traits_aux<typename set<_Key,_Compare,_Alloc>::_Rep_type>
398 {};
399
400 template <class _Key, class _Compare, class _Alloc>
401 struct __move_traits<multiset<_Key,_Compare,_Alloc> > :
402 _STLP_PRIV __move_traits_aux<typename multiset<_Key,_Compare,_Alloc>::_Rep_type>
403 {};
404 #endif
405
406 _STLP_END_NAMESPACE
407
408 #endif /* _STLP_INTERNAL_SET_H */
409
410 // Local Variables:
411 // mode:C++
412 // End:
413