1// Debugging set implementation -*- C++ -*-
2
3// Copyright (C) 2003, 2004, 2005
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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
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/** @file debug/set.h
32 *  This file is a GNU debug extension to the Standard C++ Library.
33 */
34
35#ifndef _GLIBCXX_DEBUG_SET_H
36#define _GLIBCXX_DEBUG_SET_H 1
37
38#include <debug/safe_sequence.h>
39#include <debug/safe_iterator.h>
40#include <utility>
41
42namespace std
43{
44namespace __debug
45{
46  template<typename _Key, typename _Compare = std::less<_Key>,
47	   typename _Allocator = std::allocator<_Key> >
48    class set
49    : public _GLIBCXX_STD::set<_Key,_Compare,_Allocator>,
50      public __gnu_debug::_Safe_sequence<set<_Key, _Compare, _Allocator> >
51    {
52      typedef _GLIBCXX_STD::set<_Key,_Compare,_Allocator> _Base;
53      typedef __gnu_debug::_Safe_sequence<set> _Safe_base;
54
55    public:
56      // types:
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;
62      typedef typename _Base::reference             reference;
63      typedef typename _Base::const_reference       const_reference;
64
65      typedef __gnu_debug::_Safe_iterator<typename _Base::iterator, set>
66                                                    iterator;
67      typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator, set>
68                                                    const_iterator;
69
70      typedef typename _Base::size_type             size_type;
71      typedef typename _Base::difference_type       difference_type;
72      typedef typename _Base::pointer               pointer;
73      typedef typename _Base::const_pointer         const_pointer;
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 set(const _Compare& __comp = _Compare(),
79		   const _Allocator& __a = _Allocator())
80      : _Base(__comp, __a) { }
81
82      template<typename _InputIterator>
83        set(_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
89      set(const set<_Key,_Compare,_Allocator>& __x)
90      : _Base(__x), _Safe_base() { }
91
92      set(const _Base& __x) : _Base(__x), _Safe_base() { }
93
94      ~set() { }
95
96      set<_Key,_Compare,_Allocator>&
97      operator=(const set<_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
111      const_iterator
112      begin() const
113      { return const_iterator(_Base::begin(), this); }
114
115      iterator
116      end()
117      { return iterator(_Base::end(), this); }
118
119      const_iterator
120      end() const
121      { return const_iterator(_Base::end(), this); }
122
123      reverse_iterator
124      rbegin()
125      { return reverse_iterator(end()); }
126
127      const_reverse_iterator
128      rbegin() const
129      { return const_reverse_iterator(end()); }
130
131      reverse_iterator
132      rend()
133      { return reverse_iterator(begin()); }
134
135      const_reverse_iterator
136      rend() const
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:
145      std::pair<iterator, bool>
146      insert(const value_type& __x)
147      {
148	typedef typename _Base::iterator _Base_iterator;
149	std::pair<_Base_iterator, bool> __res = _Base::insert(__x);
150	return std::pair<iterator, bool>(iterator(__res.first, this),
151					 __res.second);
152      }
153
154      iterator
155      insert(iterator __position, const value_type& __x)
156      {
157	__glibcxx_check_insert(__position);
158	return iterator(_Base::insert(__position.base(), __x), this);
159      }
160
161      template <typename _InputIterator>
162        void
163        insert(_InputIterator __first, _InputIterator __last)
164        {
165	  __glibcxx_check_valid_range(__first, __last);
166	  _Base::insert(__first, __last);
167	}
168
169      void
170      erase(iterator __position)
171      {
172	__glibcxx_check_erase(__position);
173	__position._M_invalidate();
174	_Base::erase(__position.base());
175      }
176
177      size_type
178      erase(const key_type& __x)
179      {
180	iterator __victim = find(__x);
181	if (__victim == end())
182          return 0;
183	else
184        {
185	  __victim._M_invalidate();
186	  _Base::erase(__victim.base());
187	  return 1;
188        }
189      }
190
191      void
192      erase(iterator __first, iterator __last)
193      {
194	// _GLIBCXX_RESOLVE_LIB_DEFECTS
195	// 151. can't currently clear() empty container
196	__glibcxx_check_erase_range(__first, __last);
197
198	while (__first != __last)
199        this->erase(__first++);
200      }
201
202      void
203      swap(set<_Key,_Compare,_Allocator>& __x)
204      {
205	_Base::swap(__x);
206	this->_M_swap(__x);
207      }
208
209      void
210      clear()
211      { this->erase(begin(), end()); }
212
213      // observers:
214      using _Base::key_comp;
215      using _Base::value_comp;
216
217      // set operations:
218      iterator
219      find(const key_type& __x)
220      { return iterator(_Base::find(__x), this); }
221
222      // _GLIBCXX_RESOLVE_LIB_DEFECTS
223      // 214. set::find() missing const overload
224      const_iterator
225      find(const key_type& __x) const
226      { return const_iterator(_Base::find(__x), this); }
227
228      using _Base::count;
229
230      iterator
231      lower_bound(const key_type& __x)
232      { return iterator(_Base::lower_bound(__x), this); }
233
234      // _GLIBCXX_RESOLVE_LIB_DEFECTS
235      // 214. set::find() missing const overload
236      const_iterator
237      lower_bound(const key_type& __x) const
238      { return const_iterator(_Base::lower_bound(__x), this); }
239
240      iterator
241      upper_bound(const key_type& __x)
242      { return iterator(_Base::upper_bound(__x), this); }
243
244      // _GLIBCXX_RESOLVE_LIB_DEFECTS
245      // 214. set::find() missing const overload
246      const_iterator
247      upper_bound(const key_type& __x) const
248      { return const_iterator(_Base::upper_bound(__x), this); }
249
250      std::pair<iterator,iterator>
251      equal_range(const key_type& __x)
252      {
253	typedef typename _Base::iterator _Base_iterator;
254	std::pair<_Base_iterator, _Base_iterator> __res =
255        _Base::equal_range(__x);
256	return std::make_pair(iterator(__res.first, this),
257			      iterator(__res.second, this));
258      }
259
260      // _GLIBCXX_RESOLVE_LIB_DEFECTS
261      // 214. set::find() missing const overload
262      std::pair<const_iterator,const_iterator>
263      equal_range(const key_type& __x) const
264      {
265	typedef typename _Base::const_iterator _Base_iterator;
266	std::pair<_Base_iterator, _Base_iterator> __res =
267        _Base::equal_range(__x);
268	return std::make_pair(const_iterator(__res.first, this),
269			      const_iterator(__res.second, this));
270      }
271
272      _Base&
273      _M_base() { return *this; }
274
275      const _Base&
276      _M_base() const { return *this; }
277
278    private:
279      void
280      _M_invalidate_all()
281      {
282	typedef typename _Base::const_iterator _Base_const_iterator;
283	typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
284	this->_M_invalidate_if(_Not_equal(_M_base().end()));
285      }
286    };
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    inline bool
320    operator>(const set<_Key,_Compare,_Allocator>& __lhs,
321	      const set<_Key,_Compare,_Allocator>& __rhs)
322    { return __lhs._M_base() > __rhs._M_base(); }
323
324  template<typename _Key, typename _Compare, typename _Allocator>
325    void
326    swap(set<_Key,_Compare,_Allocator>& __x,
327	 set<_Key,_Compare,_Allocator>& __y)
328    { return __x.swap(__y); }
329} // namespace __debug
330} // namespace std
331
332#endif
333