1// Debugging multiset implementation -*- C++ -*-
2
3// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009, 2010, 2011
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/** @file debug/multiset.h
27 *  This file is a GNU debug extension to the Standard C++ Library.
28 */
29
30#ifndef _GLIBCXX_DEBUG_MULTISET_H
31#define _GLIBCXX_DEBUG_MULTISET_H 1
32
33#include <debug/safe_sequence.h>
34#include <debug/safe_iterator.h>
35#include <utility>
36
37namespace std _GLIBCXX_VISIBILITY(default)
38{
39namespace __debug
40{
41  /// Class std::multiset with safety/checking/debug instrumentation.
42  template<typename _Key, typename _Compare = std::less<_Key>,
43	   typename _Allocator = std::allocator<_Key> >
44    class multiset
45    : public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>,
46      public __gnu_debug::_Safe_sequence<multiset<_Key, _Compare, _Allocator> >
47    {
48      typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> _Base;
49
50      typedef typename _Base::const_iterator _Base_const_iterator;
51      typedef typename _Base::iterator _Base_iterator;
52      typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
53    public:
54      // types:
55      typedef _Key				     key_type;
56      typedef _Key				     value_type;
57      typedef _Compare				     key_compare;
58      typedef _Compare				     value_compare;
59      typedef _Allocator			     allocator_type;
60      typedef typename _Base::reference	             reference;
61      typedef typename _Base::const_reference        const_reference;
62
63      typedef __gnu_debug::_Safe_iterator<_Base_iterator, multiset>
64      iterator;
65      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
66					  multiset> const_iterator;
67
68      typedef typename _Base::size_type              size_type;
69      typedef typename _Base::difference_type        difference_type;
70      typedef typename _Base::pointer                pointer;
71      typedef typename _Base::const_pointer          const_pointer;
72      typedef std::reverse_iterator<iterator>        reverse_iterator;
73      typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
74
75      // 23.3.3.1 construct/copy/destroy:
76      explicit multiset(const _Compare& __comp = _Compare(),
77			const _Allocator& __a = _Allocator())
78      : _Base(__comp, __a) { }
79
80      template<typename _InputIterator>
81        multiset(_InputIterator __first, _InputIterator __last,
82		 const _Compare& __comp = _Compare(),
83		 const _Allocator& __a = _Allocator())
84	: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
85								     __last)),
86		__gnu_debug::__base(__last),
87		__comp, __a) { }
88
89      multiset(const multiset& __x)
90      : _Base(__x) { }
91
92      multiset(const _Base& __x)
93      : _Base(__x) { }
94
95#ifdef __GXX_EXPERIMENTAL_CXX0X__
96      multiset(multiset&& __x)
97      noexcept(is_nothrow_copy_constructible<_Compare>::value)
98      : _Base(std::move(__x))
99      { this->_M_swap(__x); }
100
101      multiset(initializer_list<value_type> __l,
102	       const _Compare& __comp = _Compare(),
103	       const allocator_type& __a = allocator_type())
104      : _Base(__l, __comp, __a) { }
105#endif
106
107      ~multiset() _GLIBCXX_NOEXCEPT { }
108
109      multiset&
110      operator=(const multiset& __x)
111      {
112	*static_cast<_Base*>(this) = __x;
113	this->_M_invalidate_all();
114	return *this;
115      }
116
117#ifdef __GXX_EXPERIMENTAL_CXX0X__
118      multiset&
119      operator=(multiset&& __x)
120      {
121	// NB: DR 1204.
122	// NB: DR 675.
123	clear();
124	swap(__x);
125	return *this;
126      }
127
128      multiset&
129      operator=(initializer_list<value_type> __l)
130      {
131	this->clear();
132	this->insert(__l);
133	return *this;
134      }
135#endif
136
137      using _Base::get_allocator;
138
139      // iterators:
140      iterator
141      begin() _GLIBCXX_NOEXCEPT
142      { return iterator(_Base::begin(), this); }
143
144      const_iterator
145      begin() const _GLIBCXX_NOEXCEPT
146      { return const_iterator(_Base::begin(), this); }
147
148      iterator
149      end() _GLIBCXX_NOEXCEPT
150      { return iterator(_Base::end(), this); }
151
152      const_iterator
153      end() const _GLIBCXX_NOEXCEPT
154      { return const_iterator(_Base::end(), this); }
155
156      reverse_iterator
157      rbegin() _GLIBCXX_NOEXCEPT
158      { return reverse_iterator(end()); }
159
160      const_reverse_iterator
161      rbegin() const _GLIBCXX_NOEXCEPT
162      { return const_reverse_iterator(end()); }
163
164      reverse_iterator
165      rend() _GLIBCXX_NOEXCEPT
166      { return reverse_iterator(begin()); }
167
168      const_reverse_iterator
169      rend() const _GLIBCXX_NOEXCEPT
170      { return const_reverse_iterator(begin()); }
171
172#ifdef __GXX_EXPERIMENTAL_CXX0X__
173      const_iterator
174      cbegin() const noexcept
175      { return const_iterator(_Base::begin(), this); }
176
177      const_iterator
178      cend() const noexcept
179      { return const_iterator(_Base::end(), this); }
180
181      const_reverse_iterator
182      crbegin() const noexcept
183      { return const_reverse_iterator(end()); }
184
185      const_reverse_iterator
186      crend() const noexcept
187      { return const_reverse_iterator(begin()); }
188#endif
189
190      // capacity:
191      using _Base::empty;
192      using _Base::size;
193      using _Base::max_size;
194
195      // modifiers:
196      iterator
197      insert(const value_type& __x)
198      { return iterator(_Base::insert(__x), this); }
199
200#ifdef __GXX_EXPERIMENTAL_CXX0X__
201      iterator
202      insert(value_type&& __x)
203      { return iterator(_Base::insert(std::move(__x)), this); }
204#endif
205
206      iterator
207      insert(const_iterator __position, const value_type& __x)
208      {
209	__glibcxx_check_insert(__position);
210	return iterator(_Base::insert(__position.base(), __x), this);
211      }
212
213#ifdef __GXX_EXPERIMENTAL_CXX0X__
214      iterator
215      insert(const_iterator __position, value_type&& __x)
216      {
217	__glibcxx_check_insert(__position);
218	return iterator(_Base::insert(__position.base(), std::move(__x)),
219			this);
220      }
221#endif
222
223      template<typename _InputIterator>
224	void
225	insert(_InputIterator __first, _InputIterator __last)
226	{
227	  __glibcxx_check_valid_range(__first, __last);
228	  _Base::insert(__gnu_debug::__base(__first),
229			__gnu_debug::__base(__last));
230	}
231
232#ifdef __GXX_EXPERIMENTAL_CXX0X__
233      void
234      insert(initializer_list<value_type> __l)
235      { _Base::insert(__l); }
236#endif
237
238#ifdef __GXX_EXPERIMENTAL_CXX0X__
239      iterator
240      erase(const_iterator __position)
241      {
242	__glibcxx_check_erase(__position);
243	this->_M_invalidate_if(_Equal(__position.base()));
244	return iterator(_Base::erase(__position.base()), this);
245      }
246#else
247      void
248      erase(iterator __position)
249      {
250	__glibcxx_check_erase(__position);
251	this->_M_invalidate_if(_Equal(__position.base()));
252	_Base::erase(__position.base());
253      }
254#endif
255
256      size_type
257      erase(const key_type& __x)
258      {
259	std::pair<_Base_iterator, _Base_iterator> __victims =
260	  _Base::equal_range(__x);
261	size_type __count = 0;
262	_Base_iterator __victim = __victims.first;
263	while (__victim != __victims.second)
264	  {
265	    this->_M_invalidate_if(_Equal(__victim));
266	    _Base::erase(__victim++);
267	    ++__count;
268	  }
269	return __count;
270      }
271
272#ifdef __GXX_EXPERIMENTAL_CXX0X__
273      iterator
274      erase(const_iterator __first, const_iterator __last)
275      {
276	// _GLIBCXX_RESOLVE_LIB_DEFECTS
277	// 151. can't currently clear() empty container
278	__glibcxx_check_erase_range(__first, __last);
279	for (_Base_const_iterator __victim = __first.base();
280	     __victim != __last.base(); ++__victim)
281	  {
282	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
283				  _M_message(__gnu_debug::__msg_valid_range)
284				  ._M_iterator(__first, "first")
285				  ._M_iterator(__last, "last"));
286	    this->_M_invalidate_if(_Equal(__victim));
287	  }
288	return iterator(_Base::erase(__first.base(), __last.base()), this);
289      }
290#else
291      void
292      erase(iterator __first, iterator __last)
293      {
294	// _GLIBCXX_RESOLVE_LIB_DEFECTS
295	// 151. can't currently clear() empty container
296	__glibcxx_check_erase_range(__first, __last);
297	for (_Base_iterator __victim = __first.base();
298	     __victim != __last.base(); ++__victim)
299	  {
300	    _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
301				  _M_message(__gnu_debug::__msg_valid_range)
302				  ._M_iterator(__first, "first")
303				  ._M_iterator(__last, "last"));
304	    this->_M_invalidate_if(_Equal(__victim));
305	  }
306	_Base::erase(__first.base(), __last.base());
307      }
308#endif
309
310      void
311      swap(multiset& __x)
312      {
313	_Base::swap(__x);
314	this->_M_swap(__x);
315      }
316
317      void
318      clear() _GLIBCXX_NOEXCEPT
319      {
320	this->_M_invalidate_all();
321	_Base::clear();
322      }
323
324      // observers:
325      using _Base::key_comp;
326      using _Base::value_comp;
327
328      // multiset operations:
329      iterator
330      find(const key_type& __x)
331      { return iterator(_Base::find(__x), this); }
332
333      // _GLIBCXX_RESOLVE_LIB_DEFECTS
334      // 214. set::find() missing const overload
335      const_iterator
336      find(const key_type& __x) const
337      { return const_iterator(_Base::find(__x), this); }
338
339      using _Base::count;
340
341      iterator
342      lower_bound(const key_type& __x)
343      { return iterator(_Base::lower_bound(__x), this); }
344
345      // _GLIBCXX_RESOLVE_LIB_DEFECTS
346      // 214. set::find() missing const overload
347      const_iterator
348      lower_bound(const key_type& __x) const
349      { return const_iterator(_Base::lower_bound(__x), this); }
350
351      iterator
352      upper_bound(const key_type& __x)
353      { return iterator(_Base::upper_bound(__x), this); }
354
355      // _GLIBCXX_RESOLVE_LIB_DEFECTS
356      // 214. set::find() missing const overload
357      const_iterator
358      upper_bound(const key_type& __x) const
359      { return const_iterator(_Base::upper_bound(__x), this); }
360
361      std::pair<iterator,iterator>
362      equal_range(const key_type& __x)
363      {
364	std::pair<_Base_iterator, _Base_iterator> __res =
365	  _Base::equal_range(__x);
366	return std::make_pair(iterator(__res.first, this),
367			      iterator(__res.second, this));
368      }
369
370      // _GLIBCXX_RESOLVE_LIB_DEFECTS
371      // 214. set::find() missing const overload
372      std::pair<const_iterator,const_iterator>
373      equal_range(const key_type& __x) const
374      {
375	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
376	  _Base::equal_range(__x);
377	return std::make_pair(const_iterator(__res.first, this),
378			      const_iterator(__res.second, this));
379      }
380
381      _Base&
382      _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
383
384      const _Base&
385      _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
386
387    private:
388      void
389      _M_invalidate_all()
390      {
391	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
392	this->_M_invalidate_if(_Not_equal(_Base::end()));
393      }
394    };
395
396  template<typename _Key, typename _Compare, typename _Allocator>
397    inline bool
398    operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
399	       const multiset<_Key, _Compare, _Allocator>& __rhs)
400    { return __lhs._M_base() == __rhs._M_base(); }
401
402  template<typename _Key, typename _Compare, typename _Allocator>
403    inline bool
404    operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
405	       const multiset<_Key, _Compare, _Allocator>& __rhs)
406    { return __lhs._M_base() != __rhs._M_base(); }
407
408  template<typename _Key, typename _Compare, typename _Allocator>
409    inline bool
410    operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
411	      const multiset<_Key, _Compare, _Allocator>& __rhs)
412    { return __lhs._M_base() < __rhs._M_base(); }
413
414  template<typename _Key, typename _Compare, typename _Allocator>
415    inline bool
416    operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
417	       const multiset<_Key, _Compare, _Allocator>& __rhs)
418    { return __lhs._M_base() <= __rhs._M_base(); }
419
420  template<typename _Key, typename _Compare, typename _Allocator>
421    inline bool
422    operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
423	       const multiset<_Key, _Compare, _Allocator>& __rhs)
424    { return __lhs._M_base() >= __rhs._M_base(); }
425
426  template<typename _Key, typename _Compare, typename _Allocator>
427    inline bool
428    operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
429	      const multiset<_Key, _Compare, _Allocator>& __rhs)
430    { return __lhs._M_base() > __rhs._M_base(); }
431
432  template<typename _Key, typename _Compare, typename _Allocator>
433    void
434    swap(multiset<_Key, _Compare, _Allocator>& __x,
435	 multiset<_Key, _Compare, _Allocator>& __y)
436    { return __x.swap(__y); }
437
438} // namespace __debug
439} // namespace std
440
441#endif
442