Merge branch 'master' of ssh://crater.dragonflybsd.org/repository/git/dragonfly
[dragonfly.git] / contrib / gcc-3.4 / libstdc++-v3 / include / debug / set.h
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