[thirdparty/gcc.git] / libstdc++-v3 / include / debug / multiset.h

// Debugging multiset implementation -*- C++ -*-

// Copyright (C) 2003, 2004, 2005
// Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/** @file debug/multiset.h
 *  This file is a GNU debug extension to the Standard C++ Library.
 */

#ifndef _GLIBCXX_DEBUG_MULTISET_H
#define _GLIBCXX_DEBUG_MULTISET_H 1

#include <debug/safe_sequence.h>
#include <debug/safe_iterator.h>
#include <utility>

namespace std
{
namespace __debug
{
  template<typename _Key, typename _Compare = std::less<_Key>,
	   typename _Allocator = std::allocator<_Key> >
    class multiset
    : public _GLIBCXX_STD_D::multiset<_Key, _Compare, _Allocator>,
      public __gnu_debug::_Safe_sequence<multiset<_Key, _Compare, _Allocator> >
    {
      typedef _GLIBCXX_STD_D::multiset<_Key, _Compare, _Allocator> _Base;
      typedef __gnu_debug::_Safe_sequence<multiset> _Safe_base;

    public:
      // types:
      typedef _Key				     key_type;
      typedef _Key				     value_type;
      typedef _Compare				     key_compare;
      typedef _Compare				     value_compare;
      typedef _Allocator			     allocator_type;
      typedef typename _Base::reference	             reference;
      typedef typename _Base::const_reference        const_reference;

      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, multiset>
      iterator;
      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
					  multiset> const_iterator;

      typedef typename _Base::size_type              size_type;
      typedef typename _Base::difference_type        difference_type;
      typedef typename _Base::pointer                pointer;
      typedef typename _Base::const_pointer          const_pointer;
      typedef std::reverse_iterator<iterator>        reverse_iterator;
      typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;

      // 23.3.3.1 construct/copy/destroy:
      explicit multiset(const _Compare& __comp = _Compare(),
			const _Allocator& __a = _Allocator())
      : _Base(__comp, __a) { }

      template<typename _InputIterator>
        multiset(_InputIterator __first, _InputIterator __last,
		 const _Compare& __comp = _Compare(),
		 const _Allocator& __a = _Allocator())
	: _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
		__comp, __a) { }

      multiset(const multiset<_Key,_Compare,_Allocator>& __x)
      : _Base(__x), _Safe_base() { }

      multiset(const _Base& __x) : _Base(__x), _Safe_base() { }

      ~multiset() { }

      multiset<_Key,_Compare,_Allocator>&
      operator=(const multiset<_Key,_Compare,_Allocator>& __x)
      {
	*static_cast<_Base*>(this) = __x;
	this->_M_invalidate_all();
	return *this;
      }

      using _Base::get_allocator;

      // iterators:
      iterator
      begin()
      { return iterator(_Base::begin(), this); }

      const_iterator
      begin() const
      { return const_iterator(_Base::begin(), this); }

      iterator
      end()
      { return iterator(_Base::end(), this); }

      const_iterator
      end() const
      { return const_iterator(_Base::end(), this); }

      reverse_iterator
      rbegin()
      { return reverse_iterator(end()); }

      const_reverse_iterator
      rbegin() const
      { return const_reverse_iterator(end()); }

      reverse_iterator
      rend()
      { return reverse_iterator(begin()); }

      const_reverse_iterator
      rend() const
      { return const_reverse_iterator(begin()); }

      // capacity:
      using _Base::empty;
      using _Base::size;
      using _Base::max_size;

      // modifiers:
      iterator
      insert(const value_type& __x)
      { return iterator(_Base::insert(__x), this); }

      iterator
      insert(iterator __position, const value_type& __x)
      {
	__glibcxx_check_insert(__position);
	return iterator(_Base::insert(__position.base(), __x), this);
      }

      template<typename _InputIterator>
      void
      insert(_InputIterator __first, _InputIterator __last)
      {
	__glibcxx_check_valid_range(__first, __last);
	_Base::insert(__first, __last);
      }

      void
      erase(iterator __position)
      {
	__glibcxx_check_erase(__position);
	__position._M_invalidate();
	_Base::erase(__position.base());
      }

      size_type
      erase(const key_type& __x)
      {
	std::pair<iterator, iterator> __victims = this->equal_range(__x);
	size_type __count = 0;
	while (__victims.first != __victims.second)
	{
	  iterator __victim = __victims.first++;
	  __victim._M_invalidate();
	  _Base::erase(__victim.base());
	  ++__count;
	}
	return __count;
      }

      void
      erase(iterator __first, iterator __last)
      {
	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	// 151. can't currently clear() empty container
	__glibcxx_check_erase_range(__first, __last);
	while (__first != __last)
	this->erase(__first++);
      }

      void
      swap(multiset<_Key,_Compare,_Allocator>& __x)
      {
	_Base::swap(__x);
	this->_M_swap(__x);
      }

      void
      clear()
      { this->erase(begin(), end()); }

      // observers:
      using _Base::key_comp;
      using _Base::value_comp;

      // multiset operations:
      iterator
      find(const key_type& __x)
      { return iterator(_Base::find(__x), this); }

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 214. set::find() missing const overload
      const_iterator
      find(const key_type& __x) const
      { return const_iterator(_Base::find(__x), this); }

      using _Base::count;

      iterator
      lower_bound(const key_type& __x)
      { return iterator(_Base::lower_bound(__x), this); }

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 214. set::find() missing const overload
      const_iterator
      lower_bound(const key_type& __x) const
      { return const_iterator(_Base::lower_bound(__x), this); }

      iterator
      upper_bound(const key_type& __x)
      { return iterator(_Base::upper_bound(__x), this); }

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 214. set::find() missing const overload
      const_iterator
      upper_bound(const key_type& __x) const
      { return const_iterator(_Base::upper_bound(__x), this); }

      std::pair<iterator,iterator>
      equal_range(const key_type& __x)
      {
	typedef typename _Base::iterator _Base_iterator;
	std::pair<_Base_iterator, _Base_iterator> __res =
        _Base::equal_range(__x);
	return std::make_pair(iterator(__res.first, this),
			      iterator(__res.second, this));
      }

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 214. set::find() missing const overload
      std::pair<const_iterator,const_iterator>
      equal_range(const key_type& __x) const
      {
	typedef typename _Base::const_iterator _Base_iterator;
	std::pair<_Base_iterator, _Base_iterator> __res =
        _Base::equal_range(__x);
	return std::make_pair(const_iterator(__res.first, this),
			      const_iterator(__res.second, this));
      }

      _Base&
      _M_base() { return *this; }

      const _Base&
      _M_base() const { return *this; }

    private:
      void
      _M_invalidate_all()
      {
	typedef typename _Base::const_iterator _Base_const_iterator;
	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
	this->_M_invalidate_if(_Not_equal(_M_base().end()));
      }
    };

  template<typename _Key, typename _Compare, typename _Allocator>
    inline bool
    operator==(const multiset<_Key,_Compare,_Allocator>& __lhs,
	       const multiset<_Key,_Compare,_Allocator>& __rhs)
    { return __lhs._M_base() == __rhs._M_base(); }

  template<typename _Key, typename _Compare, typename _Allocator>
    inline bool
    operator!=(const multiset<_Key,_Compare,_Allocator>& __lhs,
	       const multiset<_Key,_Compare,_Allocator>& __rhs)
    { return __lhs._M_base() != __rhs._M_base(); }

  template<typename _Key, typename _Compare, typename _Allocator>
    inline bool
    operator<(const multiset<_Key,_Compare,_Allocator>& __lhs,
	      const multiset<_Key,_Compare,_Allocator>& __rhs)
    { return __lhs._M_base() < __rhs._M_base(); }

  template<typename _Key, typename _Compare, typename _Allocator>
    inline bool
    operator<=(const multiset<_Key,_Compare,_Allocator>& __lhs,
	       const multiset<_Key,_Compare,_Allocator>& __rhs)
    { return __lhs._M_base() <= __rhs._M_base(); }

  template<typename _Key, typename _Compare, typename _Allocator>
    inline bool
    operator>=(const multiset<_Key,_Compare,_Allocator>& __lhs,
	       const multiset<_Key,_Compare,_Allocator>& __rhs)
    { return __lhs._M_base() >= __rhs._M_base(); }

  template<typename _Key, typename _Compare, typename _Allocator>
    inline bool
    operator>(const multiset<_Key,_Compare,_Allocator>& __lhs,
	      const multiset<_Key,_Compare,_Allocator>& __rhs)
    { return __lhs._M_base() > __rhs._M_base(); }

  template<typename _Key, typename _Compare, typename _Allocator>
    void
    swap(multiset<_Key,_Compare,_Allocator>& __x,
	 multiset<_Key,_Compare,_Allocator>& __y)
    { return __x.swap(__y); }
} // namespace __debug
} // namespace std

#endif
Commit	Line	Data
285b36d6 BK	1	// Debugging multiset implementation -- C++ --
285b36d6 BK	2
09952acc	3	// Copyright (C) 2003, 2004, 2005
285b36d6 BK	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
83f51799	19	// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
285b36d6 BK	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
78a53887 BK	31	/** @file debug/multiset.h
	32	* This file is a GNU debug extension to the Standard C++ Library.
	33	*/
	34
285b36d6 BK	35	#ifndef _GLIBCXX_DEBUG_MULTISET_H
	36	#define _GLIBCXX_DEBUG_MULTISET_H 1
	37
	38	#include <debug/safe_sequence.h>
	39	#include <debug/safe_iterator.h>
	40	#include <utility>
	41
3cbc7af0 BK	42	namespace std
3cbc7af0 BK	43	{
45f388bb	44	namespace __debug
285b36d6 BK	45	{
	46	template<typename _Key, typename _Compare = std::less<_Key>,
	47	typename _Allocator = std::allocator<_Key> >
526da49c	48	class multiset
c2ba9709	49	: public _GLIBCXX_STD_D::multiset<_Key, _Compare, _Allocator>,
285b36d6 BK	50	public __gnu_debug::_Safe_sequence<multiset<_Key, _Compare, _Allocator> >
285b36d6 BK	51	{
c2ba9709	52	typedef _GLIBCXX_STD_D::multiset<_Key, _Compare, _Allocator> _Base;
285b36d6 BK	53	typedef __gnu_debug::_Safe_sequence<multiset> _Safe_base;
	54
	55	public:
	56	// types:
526da49c BI	57	typedef _Key key_type;
	58	typedef _Key value_type;
	59	typedef _Compare key_compare;
	60	typedef _Compare value_compare;
	61	typedef _Allocator allocator_type;
09952acc PC	62	typedef typename _Base::reference reference;
09952acc PC	63	typedef typename _Base::const_reference const_reference;
285b36d6	64
526da49c	65	typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, multiset>
285b36d6 BK	66	iterator;
	67	typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,
	68	multiset> const_iterator;
	69
	70	typedef typename _Base::size_type size_type;
	71	typedef typename _Base::difference_type difference_type;
09952acc PC	72	typedef typename _Base::pointer pointer;
09952acc PC	73	typedef typename _Base::const_pointer const_pointer;
285b36d6 BK	74	typedef std::reverse_iterator<iterator> reverse_iterator;
	75	typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
	76
	77	// 23.3.3.1 construct/copy/destroy:
	78	explicit multiset(const _Compare& __comp = _Compare(),
	79	const _Allocator& __a = _Allocator())
	80	: _Base(__comp, __a) { }
	81
	82	template<typename _InputIterator>
	83	multiset(_InputIterator __first, _InputIterator __last,
	84	const _Compare& __comp = _Compare(),
	85	const _Allocator& __a = _Allocator())
	86	: _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
	87	__comp, __a) { }
	88
526da49c	89	multiset(const multiset<_Key,_Compare,_Allocator>& __x)
285b36d6	90	: _Base(__x), _Safe_base() { }
526da49c	91
285b36d6 BK	92	multiset(const _Base& __x) : _Base(__x), _Safe_base() { }
	93
	94	~multiset() { }
	95
526da49c	96	multiset<_Key,_Compare,_Allocator>&
285b36d6 BK	97	operator=(const multiset<_Key,_Compare,_Allocator>& __x)
	98	{
	99	static_cast<_Base>(this) = __x;
	100	this->_M_invalidate_all();
	101	return *this;
	102	}
	103
	104	using _Base::get_allocator;
	105
	106	// iterators:
	107	iterator
	108	begin()
	109	{ return iterator(_Base::begin(), this); }
	110
526da49c BI	111	const_iterator
526da49c BI	112	begin() const
285b36d6 BK	113	{ return const_iterator(_Base::begin(), this); }
285b36d6 BK	114
526da49c	115	iterator
285b36d6 BK	116	end()
	117	{ return iterator(_Base::end(), this); }
	118
526da49c BI	119	const_iterator
526da49c BI	120	end() const
285b36d6 BK	121	{ return const_iterator(_Base::end(), this); }
285b36d6 BK	122
526da49c BI	123	reverse_iterator
526da49c BI	124	rbegin()
285b36d6 BK	125	{ return reverse_iterator(end()); }
285b36d6 BK	126
526da49c	127	const_reverse_iterator
285b36d6 BK	128	rbegin() const
	129	{ return const_reverse_iterator(end()); }
	130
526da49c BI	131	reverse_iterator
526da49c BI	132	rend()
285b36d6 BK	133	{ return reverse_iterator(begin()); }
285b36d6 BK	134
526da49c BI	135	const_reverse_iterator
526da49c BI	136	rend() const
285b36d6 BK	137	{ return const_reverse_iterator(begin()); }
	138
	139	// capacity:
	140	using _Base::empty;
	141	using _Base::size;
	142	using _Base::max_size;
	143
	144	// modifiers:
526da49c	145	iterator
285b36d6 BK	146	insert(const value_type& __x)
	147	{ return iterator(_Base::insert(__x), this); }
	148
526da49c	149	iterator
285b36d6 BK	150	insert(iterator __position, const value_type& __x)
	151	{
	152	__glibcxx_check_insert(__position);
	153	return iterator(_Base::insert(__position.base(), __x), this);
	154	}
	155
	156	template<typename _InputIterator>
526da49c	157	void
285b36d6 BK	158	insert(_InputIterator __first, _InputIterator __last)
	159	{
	160	__glibcxx_check_valid_range(__first, __last);
	161	_Base::insert(__first, __last);
	162	}
	163
526da49c	164	void
285b36d6 BK	165	erase(iterator __position)
	166	{
	167	__glibcxx_check_erase(__position);
	168	__position._M_invalidate();
	169	_Base::erase(__position.base());
	170	}
	171
	172	size_type
	173	erase(const key_type& __x)
	174	{
	175	std::pair<iterator, iterator> __victims = this->equal_range(__x);
	176	size_type __count = 0;
	177	while (__victims.first != __victims.second)
	178	{
	179	iterator __victim = __victims.first++;
	180	__victim._M_invalidate();
	181	_Base::erase(__victim.base());
	182	++__count;
	183	}
	184	return __count;
	185	}
	186
526da49c	187	void
285b36d6 BK	188	erase(iterator __first, iterator __last)
	189	{
	190	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	191	// 151. can't currently clear() empty container
	192	__glibcxx_check_erase_range(__first, __last);
	193	while (__first != __last)
	194	this->erase(__first++);
	195	}
	196
526da49c	197	void
285b36d6 BK	198	swap(multiset<_Key,_Compare,_Allocator>& __x)
	199	{
	200	_Base::swap(__x);
	201	this->_M_swap(__x);
	202	}
	203
526da49c	204	void
285b36d6 BK	205	clear()
	206	{ this->erase(begin(), end()); }
	207
	208	// observers:
	209	using _Base::key_comp;
	210	using _Base::value_comp;
	211
	212	// multiset operations:
526da49c	213	iterator
285b36d6 BK	214	find(const key_type& __x)
	215	{ return iterator(_Base::find(__x), this); }
	216
	217	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	218	// 214. set::find() missing const overload
526da49c	219	const_iterator
285b36d6 BK	220	find(const key_type& __x) const
	221	{ return const_iterator(_Base::find(__x), this); }
	222
	223	using _Base::count;
	224
526da49c	225	iterator
285b36d6 BK	226	lower_bound(const key_type& __x)
	227	{ return iterator(_Base::lower_bound(__x), this); }
	228
	229	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	230	// 214. set::find() missing const overload
526da49c	231	const_iterator
285b36d6 BK	232	lower_bound(const key_type& __x) const
	233	{ return const_iterator(_Base::lower_bound(__x), this); }
	234
526da49c	235	iterator
285b36d6 BK	236	upper_bound(const key_type& __x)
	237	{ return iterator(_Base::upper_bound(__x), this); }
	238
	239	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	240	// 214. set::find() missing const overload
526da49c	241	const_iterator
285b36d6 BK	242	upper_bound(const key_type& __x) const
	243	{ return const_iterator(_Base::upper_bound(__x), this); }
	244
	245	std::pair<iterator,iterator>
	246	equal_range(const key_type& __x)
	247	{
	248	typedef typename _Base::iterator _Base_iterator;
	249	std::pair<_Base_iterator, _Base_iterator> __res =
	250	_Base::equal_range(__x);
	251	return std::make_pair(iterator(__res.first, this),
	252	iterator(__res.second, this));
	253	}
	254
	255	// _GLIBCXX_RESOLVE_LIB_DEFECTS
	256	// 214. set::find() missing const overload
	257	std::pair<const_iterator,const_iterator>
	258	equal_range(const key_type& __x) const
	259	{
	260	typedef typename _Base::const_iterator _Base_iterator;
	261	std::pair<_Base_iterator, _Base_iterator> __res =
	262	_Base::equal_range(__x);
	263	return std::make_pair(const_iterator(__res.first, this),
	264	const_iterator(__res.second, this));
	265	}
	266
526da49c	267	_Base&
285b36d6 BK	268	_M_base() { return *this; }
285b36d6 BK	269
526da49c	270	const _Base&
285b36d6	271	_M_base() const { return *this; }
526da49c	272
285b36d6	273	private:
526da49c	274	void
285b36d6 BK	275	_M_invalidate_all()
	276	{
	277	typedef typename _Base::const_iterator _Base_const_iterator;
	278	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
	279	this->_M_invalidate_if(_Not_equal(_M_base().end()));
	280	}
	281	};
	282
	283	template<typename _Key, typename _Compare, typename _Allocator>
526da49c	284	inline bool
285b36d6 BK	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>
526da49c	290	inline bool
285b36d6 BK	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>
526da49c	296	inline bool
285b36d6 BK	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>
526da49c	302	inline bool
285b36d6 BK	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>
526da49c	308	inline bool
285b36d6 BK	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>
526da49c	314	inline bool
285b36d6 BK	315	operator>(const multiset<_Key,_Compare,_Allocator>& __lhs,
	316	const multiset<_Key,_Compare,_Allocator>& __rhs)
	317	{ return __lhs._M_base() > __rhs._M_base(); }
	318
	319	template<typename _Key, typename _Compare, typename _Allocator>
	320	void
	321	swap(multiset<_Key,_Compare,_Allocator>& __x,
	322	multiset<_Key,_Compare,_Allocator>& __y)
	323	{ return __x.swap(__y); }
45f388bb	324	} // namespace __debug
3cbc7af0	325	} // namespace std
285b36d6 BK	326
285b36d6 BK	327	#endif