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