1 // Debugging set implementation -*- C++ -*-
2 
3 // Copyright (C) 2003, 2004
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 _GLIBCXX_STD::set<_Key,_Compare,_Allocator>,
44       public __gnu_debug::_Safe_sequence<set<_Key, _Compare, _Allocator> >
45     {
46       typedef _GLIBCXX_STD::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
326