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

// Debugging set implementation -*- C++ -*-

// Copyright (C) 2003
// 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
// 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.

#ifndef _GLIBCXX_DEBUG_SET_H
#define _GLIBCXX_DEBUG_SET_H 1

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

namespace __gnu_debug_def
{
  template<typename _Key, typename _Compare = std::less<_Key>,
	   typename _Allocator = std::allocator<_Key> >
    class set
    : public __gnu_norm::set<_Key,_Compare,_Allocator>,
      public __gnu_debug::_Safe_sequence<set<_Key, _Compare, _Allocator> >
    {
      typedef __gnu_norm::set<_Key,_Compare,_Allocator> _Base;
      typedef __gnu_debug::_Safe_sequence<set> _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 _Allocator::reference        reference;
      typedef typename _Allocator::const_reference  const_reference;
      
      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, set> 
                                                    iterator;
      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, set>
                                                    const_iterator;

      typedef typename _Base::size_type             size_type;
      typedef typename _Base::difference_type       difference_type;
      typedef typename _Allocator::pointer          pointer;
      typedef typename _Allocator::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 set(const _Compare& __comp = _Compare(),
		   const _Allocator& __a = _Allocator())
      : _Base(__comp, __a) { }
      
      template<typename _InputIterator>
        set(_InputIterator __first, _InputIterator __last,
	    const _Compare& __comp = _Compare(),
	    const _Allocator& __a = _Allocator())
	: _Base(__gnu_debug::__check_valid_range(__first, __last), __last,
		__comp, __a) { }

      set(const set<_Key,_Compare,_Allocator>& __x) 
      : _Base(__x), _Safe_base() { }
    
      set(const _Base& __x) : _Base(__x), _Safe_base() { }
      
      ~set() { }
      
      set<_Key,_Compare,_Allocator>& 
      operator=(const set<_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:
      std::pair<iterator, bool> 
      insert(const value_type& __x)
      {
	typedef typename _Base::iterator _Base_iterator;
	std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
	return std::pair<iterator, bool>(iterator(__res.first, this),
					 __res.second);
      }
      
      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)
      {
	iterator __victim = find(__x);
	if (__victim == end())
          return 0;
	else
        {
	  __victim._M_invalidate();
	  _Base::erase(__victim.base());
	  return 1;
        }
      }
      
      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(set<_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;
      
      // set 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 set<_Key,_Compare,_Allocator>& __lhs,
	       const set<_Key,_Compare,_Allocator>& __rhs)
    { return __lhs._M_base() == __rhs._M_base(); }

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

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

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

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

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

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

#endif
Commit	Line	Data
285b36d6 BK	1	// Debugging set implementation -- C++ --
	2
	3	// Copyright (C) 2003
	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_SET_H
	32	#define _GLIBCXX_DEBUG_SET_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 set
	43	: public __gnu_norm::set<_Key,_Compare,_Allocator>,
	44	public __gnu_debug::_Safe_sequence<set<_Key, _Compare, _Allocator> >
	45	{
	46	typedef __gnu_norm::set<_Key,_Compare,_Allocator> _Base;
	47	typedef __gnu_debug::_Safe_sequence<set> _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, set>
	60	iterator;
	61	typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, set>
	62	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 set(const _Compare& __comp = _Compare(),
73	const _Allocator& __a = _Allocator())
74	: _Base(__comp, __a) { }
75
76	template<typename _InputIterator>
77	set(_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	set(const set<_Key,_Compare,_Allocator>& __x)
84	: _Base(__x), _Safe_base() { }
85
86	set(const _Base& __x) : _Base(__x), _Safe_base() { }
87
88	~set() { }
89
90	set<_Key,_Compare,_Allocator>&
91	operator=(const set<_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	std::pair<iterator, bool>
140	insert(const value_type& __x)
141	{
142	typedef typename _Base::iterator _Base_iterator;
143	std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
144	return std::pair<iterator, bool>(iterator(__res.first, this),
145	__res.second);
146	}
147
148	iterator
149	insert(iterator __position, const value_type& __x)
150	{
151	__glibcxx_check_insert(__position);
152	return iterator(_Base::insert(__position.base(), __x), this);
153	}
154
155	template <typename _InputIterator>
156	void
157	insert(_InputIterator __first, _InputIterator __last)
158	{
159	__glibcxx_check_valid_range(__first, __last);
160	_Base::insert(__first, __last);
161	}
162
163	void
164	erase(iterator __position)
165	{
166	__glibcxx_check_erase(__position);
167	__position._M_invalidate();
168	_Base::erase(__position.base());
169	}
170
171	size_type
172	erase(const key_type& __x)
173	{
174	iterator __victim = find(__x);
175	if (__victim == end())
176	return 0;
177	else
178	{
179	__victim._M_invalidate();
180	_Base::erase(__victim.base());
181	return 1;
182	}
183	}
184
185	void
186	erase(iterator __first, iterator __last)
187	{
188	// _GLIBCXX_RESOLVE_LIB_DEFECTS
189	// 151. can't currently clear() empty container
190	__glibcxx_check_erase_range(__first, __last);
191
192	while (__first != __last)
193	this->erase(__first++);
194	}
195
196	void
197	swap(set<_Key,_Compare,_Allocator>& __x)
198	{
199	_Base::swap(__x);
200	this->_M_swap(__x);
201	}
202
203	void
204	clear()
205	{ this->erase(begin(), end()); }
206
207	// observers:
208	using _Base::key_comp;
209	using _Base::value_comp;
210
211	// set operations:
212	iterator
213	find(const key_type& __x)
214	{ return iterator(_Base::find(__x), this); }
215
216	// _GLIBCXX_RESOLVE_LIB_DEFECTS
217	// 214. set::find() missing const overload
218	const_iterator
219	find(const key_type& __x) const
220	{ return const_iterator(_Base::find(__x), this); }
221
222	using _Base::count;
223
224	iterator
225	lower_bound(const key_type& __x)
226	{ return iterator(_Base::lower_bound(__x), this); }
227
228	// _GLIBCXX_RESOLVE_LIB_DEFECTS
229	// 214. set::find() missing const overload
230	const_iterator
231	lower_bound(const key_type& __x) const
232	{ return const_iterator(_Base::lower_bound(__x), this); }
233
234	iterator
235	upper_bound(const key_type& __x)
236	{ return iterator(_Base::upper_bound(__x), this); }
237
238	// _GLIBCXX_RESOLVE_LIB_DEFECTS
239	// 214. set::find() missing const overload
240	const_iterator
241	upper_bound(const key_type& __x) const
242	{ return const_iterator(_Base::upper_bound(__x), this); }
243
244	std::pair<iterator,iterator>
245	equal_range(const key_type& __x)
246	{
247	typedef typename _Base::iterator _Base_iterator;
248	std::pair<_Base_iterator, _Base_iterator> __res =
249	_Base::equal_range(__x);
250	return std::make_pair(iterator(__res.first, this),
251	iterator(__res.second, this));
252	}
253
254	// _GLIBCXX_RESOLVE_LIB_DEFECTS
255	// 214. set::find() missing const overload
256	std::pair<const_iterator,const_iterator>
257	equal_range(const key_type& __x) const
258	{
259	typedef typename _Base::const_iterator _Base_iterator;
260	std::pair<_Base_iterator, _Base_iterator> __res =
261	_Base::equal_range(__x);
262	return std::make_pair(const_iterator(__res.first, this),
263	const_iterator(__res.second, this));
264	}
265
266	_Base&
267	_M_base() { return *this; }
268
269	const _Base&
270	_M_base() const { return *this; }
271
272	private:
273	void
274	_M_invalidate_all()
275	{
276	typedef typename _Base::const_iterator _Base_const_iterator;
277	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
278	this->_M_invalidate_if(_Not_equal(_M_base().end()));
279	}
280	};
281
282	template<typename _Key, typename _Compare, typename _Allocator>
283	inline bool
284	operator==(const set<_Key,_Compare,_Allocator>& __lhs,
285	const set<_Key,_Compare,_Allocator>& __rhs)
286	{ return __lhs._M_base() == __rhs._M_base(); }
287
288	template<typename _Key, typename _Compare, typename _Allocator>
289	inline bool
290	operator!=(const set<_Key,_Compare,_Allocator>& __lhs,
291	const set<_Key,_Compare,_Allocator>& __rhs)
292	{ return __lhs._M_base() != __rhs._M_base(); }
293
294	template<typename _Key, typename _Compare, typename _Allocator>
295	inline bool
296	operator<(const set<_Key,_Compare,_Allocator>& __lhs,
297	const set<_Key,_Compare,_Allocator>& __rhs)
298	{ return __lhs._M_base() < __rhs._M_base(); }
299
300	template<typename _Key, typename _Compare, typename _Allocator>
301	inline bool
302	operator<=(const set<_Key,_Compare,_Allocator>& __lhs,
303	const set<_Key,_Compare,_Allocator>& __rhs)
304	{ return __lhs._M_base() <= __rhs._M_base(); }
305
306	template<typename _Key, typename _Compare, typename _Allocator>
307	inline bool
308	operator>=(const set<_Key,_Compare,_Allocator>& __lhs,
309	const set<_Key,_Compare,_Allocator>& __rhs)
310	{ return __lhs._M_base() >= __rhs._M_base(); }
311
312	template<typename _Key, typename _Compare, typename _Allocator>
313	inline bool
314	operator>(const set<_Key,_Compare,_Allocator>& __lhs,
315	const set<_Key,_Compare,_Allocator>& __rhs)
316	{ return __lhs._M_base() > __rhs._M_base(); }
317
318	template<typename _Key, typename _Compare, typename _Allocator>
319	void
320	swap(set<_Key,_Compare,_Allocator>& __x,
321	set<_Key,_Compare,_Allocator>& __y)
322	{ return __x.swap(__y); }
323	} // namespace __gnu_debug_def
324
325	#endif