1 // Debugging multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2003, 2004
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 2, 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 // You should have received a copy of the GNU General Public License along
18 // with this library; see the file COPYING.  If not, write to the Free
19 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
20 // USA.
21 
22 // As a special exception, you may use this file as part of a free software
23 // library without restriction.  Specifically, if other files instantiate
24 // templates or use macros or inline functions from this file, or you compile
25 // this file and link it with other files to produce an executable, this
26 // file does not by itself cause the resulting executable to be covered by
27 // the GNU General Public License.  This exception does not however
28 // invalidate any other reasons why the executable file might be covered by
29 // the GNU General Public License.
30 
31 #ifndef _GLIBCXX_DEBUG_MULTISET_H
32 #define _GLIBCXX_DEBUG_MULTISET_H 1
33 
34 #include <debug/safe_sequence.h>
35 #include <debug/safe_iterator.h>
36 #include <utility>
37 
38 namespace __gnu_debug_def
39 {
40   template<typename _Key, typename _Compare = std::less<_Key>,
41 	   typename _Allocator = std::allocator<_Key> >
42     class multiset
43     : public _GLIBCXX_STD::multiset<_Key, _Compare, _Allocator>,
44       public __gnu_debug::_Safe_sequence<multiset<_Key, _Compare, _Allocator> >
45     {
46       typedef _GLIBCXX_STD::multiset<_Key, _Compare, _Allocator> _Base;
47       typedef __gnu_debug::_Safe_sequence<multiset> _Safe_base;
48 
49     public:
50       // types:
51       typedef _Key				     key_type;
52       typedef _Key				     value_type;
53       typedef _Compare				     key_compare;
54       typedef _Compare				     value_compare;
55       typedef _Allocator			     allocator_type;
56       typedef typename _Allocator::reference	     reference;
57       typedef typename _Allocator::const_reference   const_reference;
58 
59       typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, multiset>
60       iterator;
61       typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
62 					  multiset> const_iterator;
63 
64       typedef typename _Base::size_type              size_type;
65       typedef typename _Base::difference_type        difference_type;
66       typedef typename _Allocator::pointer           pointer;
67       typedef typename _Allocator::const_pointer     const_pointer;
68       typedef std::reverse_iterator<iterator>        reverse_iterator;
69       typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
70 
71       // 23.3.3.1 construct/copy/destroy:
72       explicit multiset(const _Compare& __comp = _Compare(),
73 			const _Allocator& __a = _Allocator())
74       : _Base(__comp, __a) { }
75 
76       template<typename _InputIterator>
77         multiset(_InputIterator __first, _InputIterator __last,
78 		 const _Compare& __comp = _Compare(),
79 		 const _Allocator& __a = _Allocator())
80 	: _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
81 		__comp, __a) { }
82 
83       multiset(const multiset<_Key,_Compare,_Allocator>& __x)
84       : _Base(__x), _Safe_base() { }
85 
86       multiset(const _Base& __x) : _Base(__x), _Safe_base() { }
87 
88       ~multiset() { }
89 
90       multiset<_Key,_Compare,_Allocator>&
91       operator=(const multiset<_Key,_Compare,_Allocator>& __x)
92       {
93 	*static_cast<_Base*>(this) = __x;
94 	this->_M_invalidate_all();
95 	return *this;
96       }
97 
98       using _Base::get_allocator;
99 
100       // iterators:
101       iterator
102       begin()
103       { return iterator(_Base::begin(), this); }
104 
105       const_iterator
106       begin() const
107       { return const_iterator(_Base::begin(), this); }
108 
109       iterator
110       end()
111       { return iterator(_Base::end(), this); }
112 
113       const_iterator
114       end() const
115       { return const_iterator(_Base::end(), this); }
116 
117       reverse_iterator
118       rbegin()
119       { return reverse_iterator(end()); }
120 
121       const_reverse_iterator
122       rbegin() const
123       { return const_reverse_iterator(end()); }
124 
125       reverse_iterator
126       rend()
127       { return reverse_iterator(begin()); }
128 
129       const_reverse_iterator
130       rend() const
131       { return const_reverse_iterator(begin()); }
132 
133       // capacity:
134       using _Base::empty;
135       using _Base::size;
136       using _Base::max_size;
137 
138       // modifiers:
139       iterator
140       insert(const value_type& __x)
141       { return iterator(_Base::insert(__x), this); }
142 
143       iterator
144       insert(iterator __position, const value_type& __x)
145       {
146 	__glibcxx_check_insert(__position);
147 	return iterator(_Base::insert(__position.base(), __x), this);
148       }
149 
150       template<typename _InputIterator>
151       void
152       insert(_InputIterator __first, _InputIterator __last)
153       {
154 	__glibcxx_check_valid_range(__first, __last);
155 	_Base::insert(__first, __last);
156       }
157 
158       void
159       erase(iterator __position)
160       {
161 	__glibcxx_check_erase(__position);
162 	__position._M_invalidate();
163 	_Base::erase(__position.base());
164       }
165 
166       size_type
167       erase(const key_type& __x)
168       {
169 	std::pair<iterator, iterator> __victims = this->equal_range(__x);
170 	size_type __count = 0;
171 	while (__victims.first != __victims.second)
172 	{
173 	  iterator __victim = __victims.first++;
174 	  __victim._M_invalidate();
175 	  _Base::erase(__victim.base());
176 	  ++__count;
177 	}
178 	return __count;
179       }
180 
181       void
182       erase(iterator __first, iterator __last)
183       {
184 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
185 	// 151. can't currently clear() empty container
186 	__glibcxx_check_erase_range(__first, __last);
187 	while (__first != __last)
188 	this->erase(__first++);
189       }
190 
191       void
192       swap(multiset<_Key,_Compare,_Allocator>& __x)
193       {
194 	_Base::swap(__x);
195 	this->_M_swap(__x);
196       }
197 
198       void
199       clear()
200       { this->erase(begin(), end()); }
201 
202       // observers:
203       using _Base::key_comp;
204       using _Base::value_comp;
205 
206       // multiset operations:
207       iterator
208       find(const key_type& __x)
209       { return iterator(_Base::find(__x), this); }
210 
211       // _GLIBCXX_RESOLVE_LIB_DEFECTS
212       // 214. set::find() missing const overload
213       const_iterator
214       find(const key_type& __x) const
215       { return const_iterator(_Base::find(__x), this); }
216 
217       using _Base::count;
218 
219       iterator
220       lower_bound(const key_type& __x)
221       { return iterator(_Base::lower_bound(__x), this); }
222 
223       // _GLIBCXX_RESOLVE_LIB_DEFECTS
224       // 214. set::find() missing const overload
225       const_iterator
226       lower_bound(const key_type& __x) const
227       { return const_iterator(_Base::lower_bound(__x), this); }
228 
229       iterator
230       upper_bound(const key_type& __x)
231       { return iterator(_Base::upper_bound(__x), this); }
232 
233       // _GLIBCXX_RESOLVE_LIB_DEFECTS
234       // 214. set::find() missing const overload
235       const_iterator
236       upper_bound(const key_type& __x) const
237       { return const_iterator(_Base::upper_bound(__x), this); }
238 
239       std::pair<iterator,iterator>
240       equal_range(const key_type& __x)
241       {
242 	typedef typename _Base::iterator _Base_iterator;
243 	std::pair<_Base_iterator, _Base_iterator> __res =
244         _Base::equal_range(__x);
245 	return std::make_pair(iterator(__res.first, this),
246 			      iterator(__res.second, this));
247       }
248 
249       // _GLIBCXX_RESOLVE_LIB_DEFECTS
250       // 214. set::find() missing const overload
251       std::pair<const_iterator,const_iterator>
252       equal_range(const key_type& __x) const
253       {
254 	typedef typename _Base::const_iterator _Base_iterator;
255 	std::pair<_Base_iterator, _Base_iterator> __res =
256         _Base::equal_range(__x);
257 	return std::make_pair(const_iterator(__res.first, this),
258 			      const_iterator(__res.second, this));
259       }
260 
261       _Base&
262       _M_base() { return *this; }
263 
264       const _Base&
265       _M_base() const { return *this; }
266 
267     private:
268       void
269       _M_invalidate_all()
270       {
271 	typedef typename _Base::const_iterator _Base_const_iterator;
272 	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
273 	this->_M_invalidate_if(_Not_equal(_M_base().end()));
274       }
275     };
276 
277   template<typename _Key, typename _Compare, typename _Allocator>
278     inline bool
279     operator==(const multiset<_Key,_Compare,_Allocator>& __lhs,
280 	       const multiset<_Key,_Compare,_Allocator>& __rhs)
281     { return __lhs._M_base() == __rhs._M_base(); }
282 
283   template<typename _Key, typename _Compare, typename _Allocator>
284     inline bool
285     operator!=(const multiset<_Key,_Compare,_Allocator>& __lhs,
286 	       const multiset<_Key,_Compare,_Allocator>& __rhs)
287     { return __lhs._M_base() != __rhs._M_base(); }
288 
289   template<typename _Key, typename _Compare, typename _Allocator>
290     inline bool
291     operator<(const multiset<_Key,_Compare,_Allocator>& __lhs,
292 	      const multiset<_Key,_Compare,_Allocator>& __rhs)
293     { return __lhs._M_base() < __rhs._M_base(); }
294 
295   template<typename _Key, typename _Compare, typename _Allocator>
296     inline bool
297     operator<=(const multiset<_Key,_Compare,_Allocator>& __lhs,
298 	       const multiset<_Key,_Compare,_Allocator>& __rhs)
299     { return __lhs._M_base() <= __rhs._M_base(); }
300 
301   template<typename _Key, typename _Compare, typename _Allocator>
302     inline bool
303     operator>=(const multiset<_Key,_Compare,_Allocator>& __lhs,
304 	       const multiset<_Key,_Compare,_Allocator>& __rhs)
305     { return __lhs._M_base() >= __rhs._M_base(); }
306 
307   template<typename _Key, typename _Compare, typename _Allocator>
308     inline bool
309     operator>(const multiset<_Key,_Compare,_Allocator>& __lhs,
310 	      const multiset<_Key,_Compare,_Allocator>& __rhs)
311     { return __lhs._M_base() > __rhs._M_base(); }
312 
313   template<typename _Key, typename _Compare, typename _Allocator>
314     void
315     swap(multiset<_Key,_Compare,_Allocator>& __x,
316 	 multiset<_Key,_Compare,_Allocator>& __y)
317     { return __x.swap(__y); }
318 } // namespace __gnu_debug_def
319 
320 #endif
321