Go to most recent revision | Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
4680 | right-hear | 1 | /* |
2 | * |
||
3 | * Copyright (c) 1996,1997 |
||
4 | * Silicon Graphics Computer Systems, Inc. |
||
5 | * |
||
6 | * Permission to use, copy, modify, distribute and sell this software |
||
7 | * and its documentation for any purpose is hereby granted without fee, |
||
8 | * provided that the above copyright notice appear in all copies and |
||
9 | * that both that copyright notice and this permission notice appear |
||
10 | * in supporting documentation. Silicon Graphics makes no |
||
11 | * representations about the suitability of this software for any |
||
12 | * purpose. It is provided "as is" without express or implied warranty. |
||
13 | * |
||
14 | * |
||
15 | * Copyright (c) 1994 |
||
16 | * Hewlett-Packard Company |
||
17 | * |
||
18 | * Permission to use, copy, modify, distribute and sell this software |
||
19 | * and its documentation for any purpose is hereby granted without fee, |
||
20 | * provided that the above copyright notice appear in all copies and |
||
21 | * that both that copyright notice and this permission notice appear |
||
22 | * in supporting documentation. Hewlett-Packard Company makes no |
||
23 | * representations about the suitability of this software for any |
||
24 | * purpose. It is provided "as is" without express or implied warranty. |
||
25 | * |
||
26 | * |
||
27 | */ |
||
28 | |||
29 | /* NOTE: This is an internal header file, included by other STL headers. |
||
30 | * You should not attempt to use it directly. |
||
31 | */ |
||
32 | |||
33 | #ifndef __SGI_STL_INTERNAL_TREE_H |
||
34 | #define __SGI_STL_INTERNAL_TREE_H |
||
35 | |||
36 | /* |
||
37 | |||
38 | Red-black tree class, designed for use in implementing STL |
||
39 | associative containers (set, multiset, map, and multimap). The |
||
40 | insertion and deletion algorithms are based on those in Cormen, |
||
41 | Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990), |
||
42 | except that |
||
43 | |||
44 | (1) the header cell is maintained with links not only to the root |
||
45 | but also to the leftmost node of the tree, to enable constant time |
||
46 | begin(), and to the rightmost node of the tree, to enable linear time |
||
47 | performance when used with the generic set algorithms (set_union, |
||
48 | etc.); |
||
49 | |||
50 | (2) when a node being deleted has two children its successor node is |
||
51 | relinked into its place, rather than copied, so that the only |
||
52 | iterators invalidated are those referring to the deleted node. |
||
53 | |||
54 | */ |
||
55 | |||
56 | #include |
||
57 | #include |
||
58 | #include |
||
59 | #include |
||
60 | |||
61 | namespace std |
||
62 | { |
||
63 | |||
64 | typedef bool _Rb_tree_Color_type; |
||
65 | const _Rb_tree_Color_type _S_rb_tree_red = false; |
||
66 | const _Rb_tree_Color_type _S_rb_tree_black = true; |
||
67 | |||
68 | struct _Rb_tree_node_base |
||
69 | { |
||
70 | typedef _Rb_tree_Color_type _Color_type; |
||
71 | typedef _Rb_tree_node_base* _Base_ptr; |
||
72 | |||
73 | _Color_type _M_color; |
||
74 | _Base_ptr _M_parent; |
||
75 | _Base_ptr _M_left; |
||
76 | _Base_ptr _M_right; |
||
77 | |||
78 | static _Base_ptr _S_minimum(_Base_ptr __x) |
||
79 | { |
||
80 | while (__x->_M_left != 0) __x = __x->_M_left; |
||
81 | return __x; |
||
82 | } |
||
83 | |||
84 | static _Base_ptr _S_maximum(_Base_ptr __x) |
||
85 | { |
||
86 | while (__x->_M_right != 0) __x = __x->_M_right; |
||
87 | return __x; |
||
88 | } |
||
89 | }; |
||
90 | |||
91 | template |
||
92 | struct _Rb_tree_node : public _Rb_tree_node_base |
||
93 | { |
||
94 | typedef _Rb_tree_node<_Value>* _Link_type; |
||
95 | _Value _M_value_field; |
||
96 | }; |
||
97 | |||
98 | |||
99 | struct _Rb_tree_base_iterator |
||
100 | { |
||
101 | typedef _Rb_tree_node_base::_Base_ptr _Base_ptr; |
||
102 | typedef bidirectional_iterator_tag iterator_category; |
||
103 | typedef ptrdiff_t difference_type; |
||
104 | _Base_ptr _M_node; |
||
105 | |||
106 | void _M_increment() |
||
107 | { |
||
108 | if (_M_node->_M_right != 0) { |
||
109 | _M_node = _M_node->_M_right; |
||
110 | while (_M_node->_M_left != 0) |
||
111 | _M_node = _M_node->_M_left; |
||
112 | } |
||
113 | else { |
||
114 | _Base_ptr __y = _M_node->_M_parent; |
||
115 | while (_M_node == __y->_M_right) { |
||
116 | _M_node = __y; |
||
117 | __y = __y->_M_parent; |
||
118 | } |
||
119 | if (_M_node->_M_right != __y) |
||
120 | _M_node = __y; |
||
121 | } |
||
122 | } |
||
123 | |||
124 | void _M_decrement() |
||
125 | { |
||
126 | if (_M_node->_M_color == _S_rb_tree_red && |
||
127 | _M_node->_M_parent->_M_parent == _M_node) |
||
128 | _M_node = _M_node->_M_right; |
||
129 | else if (_M_node->_M_left != 0) { |
||
130 | _Base_ptr __y = _M_node->_M_left; |
||
131 | while (__y->_M_right != 0) |
||
132 | __y = __y->_M_right; |
||
133 | _M_node = __y; |
||
134 | } |
||
135 | else { |
||
136 | _Base_ptr __y = _M_node->_M_parent; |
||
137 | while (_M_node == __y->_M_left) { |
||
138 | _M_node = __y; |
||
139 | __y = __y->_M_parent; |
||
140 | } |
||
141 | _M_node = __y; |
||
142 | } |
||
143 | } |
||
144 | }; |
||
145 | |||
146 | template |
||
147 | struct _Rb_tree_iterator : public _Rb_tree_base_iterator |
||
148 | { |
||
149 | typedef _Value value_type; |
||
150 | typedef _Ref reference; |
||
151 | typedef _Ptr pointer; |
||
152 | typedef _Rb_tree_iterator<_Value, _Value&, _Value*> |
||
153 | iterator; |
||
154 | typedef _Rb_tree_iterator<_Value, const _Value&, const _Value*> |
||
155 | const_iterator; |
||
156 | typedef _Rb_tree_iterator<_Value, _Ref, _Ptr> |
||
157 | _Self; |
||
158 | typedef _Rb_tree_node<_Value>* _Link_type; |
||
159 | |||
160 | _Rb_tree_iterator() {} |
||
161 | _Rb_tree_iterator(_Link_type __x) { _M_node = __x; } |
||
162 | _Rb_tree_iterator(const iterator& __it) { _M_node = __it._M_node; } |
||
163 | |||
164 | reference operator*() const { return _Link_type(_M_node)->_M_value_field; } |
||
165 | pointer operator->() const { return &(operator*()); } |
||
166 | |||
167 | _Self& operator++() { _M_increment(); return *this; } |
||
168 | _Self operator++(int) { |
||
169 | _Self __tmp = *this; |
||
170 | _M_increment(); |
||
171 | return __tmp; |
||
172 | } |
||
173 | |||
174 | _Self& operator--() { _M_decrement(); return *this; } |
||
175 | _Self operator--(int) { |
||
176 | _Self __tmp = *this; |
||
177 | _M_decrement(); |
||
178 | return __tmp; |
||
179 | } |
||
180 | }; |
||
181 | |||
182 | template |
||
183 | inline bool operator==(const _Rb_tree_iterator<_Value, _Ref, _Ptr>& __x, |
||
184 | const _Rb_tree_iterator<_Value, _Ref, _Ptr>& __y) { |
||
185 | return __x._M_node == __y._M_node; |
||
186 | } |
||
187 | |||
188 | template |
||
189 | inline bool operator==(const _Rb_tree_iterator<_Value, const _Value&, const _Value*>& __x, |
||
190 | const _Rb_tree_iterator<_Value, _Value&, _Value*>& __y) { |
||
191 | return __x._M_node == __y._M_node; |
||
192 | } |
||
193 | |||
194 | template |
||
195 | inline bool operator==(const _Rb_tree_iterator<_Value, _Value&, _Value*>& __x, |
||
196 | const _Rb_tree_iterator<_Value, const _Value&, const _Value*>& __y) { |
||
197 | return __x._M_node == __y._M_node; |
||
198 | } |
||
199 | |||
200 | template |
||
201 | inline bool operator!=(const _Rb_tree_iterator<_Value, _Ref, _Ptr>& __x, |
||
202 | const _Rb_tree_iterator<_Value, _Ref, _Ptr>& __y) { |
||
203 | return __x._M_node != __y._M_node; |
||
204 | } |
||
205 | |||
206 | template |
||
207 | inline bool operator!=(const _Rb_tree_iterator<_Value, const _Value&, const _Value*>& __x, |
||
208 | const _Rb_tree_iterator<_Value, _Value&, _Value*>& __y) { |
||
209 | return __x._M_node != __y._M_node; |
||
210 | } |
||
211 | |||
212 | template |
||
213 | inline bool operator!=(const _Rb_tree_iterator<_Value, _Value&, _Value*>& __x, |
||
214 | const _Rb_tree_iterator<_Value, const _Value&, const _Value*>& __y) { |
||
215 | return __x._M_node != __y._M_node; |
||
216 | } |
||
217 | |||
218 | inline void |
||
219 | _Rb_tree_rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root) |
||
220 | { |
||
221 | _Rb_tree_node_base* __y = __x->_M_right; |
||
222 | __x->_M_right = __y->_M_left; |
||
223 | if (__y->_M_left !=0) |
||
224 | __y->_M_left->_M_parent = __x; |
||
225 | __y->_M_parent = __x->_M_parent; |
||
226 | |||
227 | if (__x == __root) |
||
228 | __root = __y; |
||
229 | else if (__x == __x->_M_parent->_M_left) |
||
230 | __x->_M_parent->_M_left = __y; |
||
231 | else |
||
232 | __x->_M_parent->_M_right = __y; |
||
233 | __y->_M_left = __x; |
||
234 | __x->_M_parent = __y; |
||
235 | } |
||
236 | |||
237 | inline void |
||
238 | _Rb_tree_rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root) |
||
239 | { |
||
240 | _Rb_tree_node_base* __y = __x->_M_left; |
||
241 | __x->_M_left = __y->_M_right; |
||
242 | if (__y->_M_right != 0) |
||
243 | __y->_M_right->_M_parent = __x; |
||
244 | __y->_M_parent = __x->_M_parent; |
||
245 | |||
246 | if (__x == __root) |
||
247 | __root = __y; |
||
248 | else if (__x == __x->_M_parent->_M_right) |
||
249 | __x->_M_parent->_M_right = __y; |
||
250 | else |
||
251 | __x->_M_parent->_M_left = __y; |
||
252 | __y->_M_right = __x; |
||
253 | __x->_M_parent = __y; |
||
254 | } |
||
255 | |||
256 | inline void |
||
257 | _Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root) |
||
258 | { |
||
259 | __x->_M_color = _S_rb_tree_red; |
||
260 | while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red) { |
||
261 | if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) { |
||
262 | _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right; |
||
263 | if (__y && __y->_M_color == _S_rb_tree_red) { |
||
264 | __x->_M_parent->_M_color = _S_rb_tree_black; |
||
265 | __y->_M_color = _S_rb_tree_black; |
||
266 | __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; |
||
267 | __x = __x->_M_parent->_M_parent; |
||
268 | } |
||
269 | else { |
||
270 | if (__x == __x->_M_parent->_M_right) { |
||
271 | __x = __x->_M_parent; |
||
272 | _Rb_tree_rotate_left(__x, __root); |
||
273 | } |
||
274 | __x->_M_parent->_M_color = _S_rb_tree_black; |
||
275 | __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; |
||
276 | _Rb_tree_rotate_right(__x->_M_parent->_M_parent, __root); |
||
277 | } |
||
278 | } |
||
279 | else { |
||
280 | _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left; |
||
281 | if (__y && __y->_M_color == _S_rb_tree_red) { |
||
282 | __x->_M_parent->_M_color = _S_rb_tree_black; |
||
283 | __y->_M_color = _S_rb_tree_black; |
||
284 | __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; |
||
285 | __x = __x->_M_parent->_M_parent; |
||
286 | } |
||
287 | else { |
||
288 | if (__x == __x->_M_parent->_M_left) { |
||
289 | __x = __x->_M_parent; |
||
290 | _Rb_tree_rotate_right(__x, __root); |
||
291 | } |
||
292 | __x->_M_parent->_M_color = _S_rb_tree_black; |
||
293 | __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; |
||
294 | _Rb_tree_rotate_left(__x->_M_parent->_M_parent, __root); |
||
295 | } |
||
296 | } |
||
297 | } |
||
298 | __root->_M_color = _S_rb_tree_black; |
||
299 | } |
||
300 | |||
301 | inline _Rb_tree_node_base* |
||
302 | _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* __z, |
||
303 | _Rb_tree_node_base*& __root, |
||
304 | _Rb_tree_node_base*& __leftmost, |
||
305 | _Rb_tree_node_base*& __rightmost) |
||
306 | { |
||
307 | _Rb_tree_node_base* __y = __z; |
||
308 | _Rb_tree_node_base* __x = 0; |
||
309 | _Rb_tree_node_base* __x_parent = 0; |
||
310 | if (__y->_M_left == 0) // __z has at most one non-null child. y == z. |
||
311 | __x = __y->_M_right; // __x might be null. |
||
312 | else |
||
313 | if (__y->_M_right == 0) // __z has exactly one non-null child. y == z. |
||
314 | __x = __y->_M_left; // __x is not null. |
||
315 | else { // __z has two non-null children. Set __y to |
||
316 | __y = __y->_M_right; // __z's successor. __x might be null. |
||
317 | while (__y->_M_left != 0) |
||
318 | __y = __y->_M_left; |
||
319 | __x = __y->_M_right; |
||
320 | } |
||
321 | if (__y != __z) { // relink y in place of z. y is z's successor |
||
322 | __z->_M_left->_M_parent = __y; |
||
323 | __y->_M_left = __z->_M_left; |
||
324 | if (__y != __z->_M_right) { |
||
325 | __x_parent = __y->_M_parent; |
||
326 | if (__x) __x->_M_parent = __y->_M_parent; |
||
327 | __y->_M_parent->_M_left = __x; // __y must be a child of _M_left |
||
328 | __y->_M_right = __z->_M_right; |
||
329 | __z->_M_right->_M_parent = __y; |
||
330 | } |
||
331 | else |
||
332 | __x_parent = __y; |
||
333 | if (__root == __z) |
||
334 | __root = __y; |
||
335 | else if (__z->_M_parent->_M_left == __z) |
||
336 | __z->_M_parent->_M_left = __y; |
||
337 | else |
||
338 | __z->_M_parent->_M_right = __y; |
||
339 | __y->_M_parent = __z->_M_parent; |
||
340 | std::swap(__y->_M_color, __z->_M_color); |
||
341 | __y = __z; |
||
342 | // __y now points to node to be actually deleted |
||
343 | } |
||
344 | else { // __y == __z |
||
345 | __x_parent = __y->_M_parent; |
||
346 | if (__x) __x->_M_parent = __y->_M_parent; |
||
347 | if (__root == __z) |
||
348 | __root = __x; |
||
349 | else |
||
350 | if (__z->_M_parent->_M_left == __z) |
||
351 | __z->_M_parent->_M_left = __x; |
||
352 | else |
||
353 | __z->_M_parent->_M_right = __x; |
||
354 | if (__leftmost == __z) |
||
355 | if (__z->_M_right == 0) // __z->_M_left must be null also |
||
356 | __leftmost = __z->_M_parent; |
||
357 | // makes __leftmost == _M_header if __z == __root |
||
358 | else |
||
359 | __leftmost = _Rb_tree_node_base::_S_minimum(__x); |
||
360 | if (__rightmost == __z) |
||
361 | if (__z->_M_left == 0) // __z->_M_right must be null also |
||
362 | __rightmost = __z->_M_parent; |
||
363 | // makes __rightmost == _M_header if __z == __root |
||
364 | else // __x == __z->_M_left |
||
365 | __rightmost = _Rb_tree_node_base::_S_maximum(__x); |
||
366 | } |
||
367 | if (__y->_M_color != _S_rb_tree_red) { |
||
368 | while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black)) |
||
369 | if (__x == __x_parent->_M_left) { |
||
370 | _Rb_tree_node_base* __w = __x_parent->_M_right; |
||
371 | if (__w->_M_color == _S_rb_tree_red) { |
||
372 | __w->_M_color = _S_rb_tree_black; |
||
373 | __x_parent->_M_color = _S_rb_tree_red; |
||
374 | _Rb_tree_rotate_left(__x_parent, __root); |
||
375 | __w = __x_parent->_M_right; |
||
376 | } |
||
377 | if ((__w->_M_left == 0 || |
||
378 | __w->_M_left->_M_color == _S_rb_tree_black) && |
||
379 | (__w->_M_right == 0 || |
||
380 | __w->_M_right->_M_color == _S_rb_tree_black)) { |
||
381 | __w->_M_color = _S_rb_tree_red; |
||
382 | __x = __x_parent; |
||
383 | __x_parent = __x_parent->_M_parent; |
||
384 | } else { |
||
385 | if (__w->_M_right == 0 || |
||
386 | __w->_M_right->_M_color == _S_rb_tree_black) { |
||
387 | if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black; |
||
388 | __w->_M_color = _S_rb_tree_red; |
||
389 | _Rb_tree_rotate_right(__w, __root); |
||
390 | __w = __x_parent->_M_right; |
||
391 | } |
||
392 | __w->_M_color = __x_parent->_M_color; |
||
393 | __x_parent->_M_color = _S_rb_tree_black; |
||
394 | if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black; |
||
395 | _Rb_tree_rotate_left(__x_parent, __root); |
||
396 | break; |
||
397 | } |
||
398 | } else { // same as above, with _M_right <-> _M_left. |
||
399 | _Rb_tree_node_base* __w = __x_parent->_M_left; |
||
400 | if (__w->_M_color == _S_rb_tree_red) { |
||
401 | __w->_M_color = _S_rb_tree_black; |
||
402 | __x_parent->_M_color = _S_rb_tree_red; |
||
403 | _Rb_tree_rotate_right(__x_parent, __root); |
||
404 | __w = __x_parent->_M_left; |
||
405 | } |
||
406 | if ((__w->_M_right == 0 || |
||
407 | __w->_M_right->_M_color == _S_rb_tree_black) && |
||
408 | (__w->_M_left == 0 || |
||
409 | __w->_M_left->_M_color == _S_rb_tree_black)) { |
||
410 | __w->_M_color = _S_rb_tree_red; |
||
411 | __x = __x_parent; |
||
412 | __x_parent = __x_parent->_M_parent; |
||
413 | } else { |
||
414 | if (__w->_M_left == 0 || |
||
415 | __w->_M_left->_M_color == _S_rb_tree_black) { |
||
416 | if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black; |
||
417 | __w->_M_color = _S_rb_tree_red; |
||
418 | _Rb_tree_rotate_left(__w, __root); |
||
419 | __w = __x_parent->_M_left; |
||
420 | } |
||
421 | __w->_M_color = __x_parent->_M_color; |
||
422 | __x_parent->_M_color = _S_rb_tree_black; |
||
423 | if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black; |
||
424 | _Rb_tree_rotate_right(__x_parent, __root); |
||
425 | break; |
||
426 | } |
||
427 | } |
||
428 | if (__x) __x->_M_color = _S_rb_tree_black; |
||
429 | } |
||
430 | return __y; |
||
431 | } |
||
432 | |||
433 | // Base class to encapsulate the differences between old SGI-style |
||
434 | // allocators and standard-conforming allocators. In order to avoid |
||
435 | // having an empty base class, we arbitrarily move one of rb_tree's |
||
436 | // data members into the base class. |
||
437 | |||
438 | // _Base for general standard-conforming allocators. |
||
439 | template |
||
440 | class _Rb_tree_alloc_base { |
||
441 | public: |
||
442 | typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type; |
||
443 | allocator_type get_allocator() const { return _M_node_allocator; } |
||
444 | |||
445 | _Rb_tree_alloc_base(const allocator_type& __a) |
||
446 | : _M_node_allocator(__a), _M_header(0) {} |
||
447 | |||
448 | protected: |
||
449 | typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::allocator_type |
||
450 | _M_node_allocator; |
||
451 | _Rb_tree_node<_Tp>* _M_header; |
||
452 | |||
453 | _Rb_tree_node<_Tp>* _M_get_node() |
||
454 | { return _M_node_allocator.allocate(1); } |
||
455 | void _M_put_node(_Rb_tree_node<_Tp>* __p) |
||
456 | { _M_node_allocator.deallocate(__p, 1); } |
||
457 | }; |
||
458 | |||
459 | // Specialization for instanceless allocators. |
||
460 | template |
||
461 | class _Rb_tree_alloc_base<_Tp, _Alloc, true> { |
||
462 | public: |
||
463 | typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type; |
||
464 | allocator_type get_allocator() const { return allocator_type(); } |
||
465 | |||
466 | _Rb_tree_alloc_base(const allocator_type&) : _M_header(0) {} |
||
467 | |||
468 | protected: |
||
469 | _Rb_tree_node<_Tp>* _M_header; |
||
470 | |||
471 | typedef typename _Alloc_traits<_Rb_tree_node<_Tp>, _Alloc>::_Alloc_type |
||
472 | _Alloc_type; |
||
473 | |||
474 | _Rb_tree_node<_Tp>* _M_get_node() |
||
475 | { return _Alloc_type::allocate(1); } |
||
476 | void _M_put_node(_Rb_tree_node<_Tp>* __p) |
||
477 | { _Alloc_type::deallocate(__p, 1); } |
||
478 | }; |
||
479 | |||
480 | template |
||
481 | struct _Rb_tree_base |
||
482 | : public _Rb_tree_alloc_base<_Tp, _Alloc, |
||
483 | _Alloc_traits<_Tp, _Alloc>::_S_instanceless> |
||
484 | { |
||
485 | typedef _Rb_tree_alloc_base<_Tp, _Alloc, |
||
486 | _Alloc_traits<_Tp, _Alloc>::_S_instanceless> |
||
487 | _Base; |
||
488 | typedef typename _Base::allocator_type allocator_type; |
||
489 | |||
490 | _Rb_tree_base(const allocator_type& __a) |
||
491 | : _Base(__a) { _M_header = _M_get_node(); } |
||
492 | ~_Rb_tree_base() { _M_put_node(_M_header); } |
||
493 | |||
494 | }; |
||
495 | |||
496 | |||
497 | template |
||
498 | class _Alloc = allocator<_Value> > |
||
499 | class _Rb_tree : protected _Rb_tree_base<_Value, _Alloc> { |
||
500 | typedef _Rb_tree_base<_Value, _Alloc> _Base; |
||
501 | protected: |
||
502 | typedef _Rb_tree_node_base* _Base_ptr; |
||
503 | typedef _Rb_tree_node<_Value> _Rb_tree_node; |
||
504 | typedef _Rb_tree_Color_type _Color_type; |
||
505 | public: |
||
506 | typedef _Key key_type; |
||
507 | typedef _Value value_type; |
||
508 | typedef value_type* pointer; |
||
509 | typedef const value_type* const_pointer; |
||
510 | typedef value_type& reference; |
||
511 | typedef const value_type& const_reference; |
||
512 | typedef _Rb_tree_node* _Link_type; |
||
513 | typedef size_t size_type; |
||
514 | typedef ptrdiff_t difference_type; |
||
515 | |||
516 | typedef typename _Base::allocator_type allocator_type; |
||
517 | allocator_type get_allocator() const { return _Base::get_allocator(); } |
||
518 | |||
519 | protected: |
||
520 | using _Base::_M_get_node; |
||
521 | using _Base::_M_put_node; |
||
522 | using _Base::_M_header; |
||
523 | |||
524 | protected: |
||
525 | |||
526 | _Link_type _M_create_node(const value_type& __x) |
||
527 | { |
||
528 | _Link_type __tmp = _M_get_node(); |
||
529 | __STL_TRY { |
||
530 | construct(&__tmp->_M_value_field, __x); |
||
531 | } |
||
532 | __STL_UNWIND(_M_put_node(__tmp)); |
||
533 | return __tmp; |
||
534 | } |
||
535 | |||
536 | _Link_type _M_clone_node(_Link_type __x) |
||
537 | { |
||
538 | _Link_type __tmp = _M_create_node(__x->_M_value_field); |
||
539 | __tmp->_M_color = __x->_M_color; |
||
540 | __tmp->_M_left = 0; |
||
541 | __tmp->_M_right = 0; |
||
542 | return __tmp; |
||
543 | } |
||
544 | |||
545 | void destroy_node(_Link_type __p) |
||
546 | { |
||
547 | destroy(&__p->_M_value_field); |
||
548 | _M_put_node(__p); |
||
549 | } |
||
550 | |||
551 | protected: |
||
552 | size_type _M_node_count; // keeps track of size of tree |
||
553 | _Compare _M_key_compare; |
||
554 | |||
555 | _Link_type& _M_root() const |
||
556 | { return (_Link_type&) _M_header->_M_parent; } |
||
557 | _Link_type& _M_leftmost() const |
||
558 | { return (_Link_type&) _M_header->_M_left; } |
||
559 | _Link_type& _M_rightmost() const |
||
560 | { return (_Link_type&) _M_header->_M_right; } |
||
561 | |||
562 | static _Link_type& _S_left(_Link_type __x) |
||
563 | { return (_Link_type&)(__x->_M_left); } |
||
564 | static _Link_type& _S_right(_Link_type __x) |
||
565 | { return (_Link_type&)(__x->_M_right); } |
||
566 | static _Link_type& _S_parent(_Link_type __x) |
||
567 | { return (_Link_type&)(__x->_M_parent); } |
||
568 | static reference _S_value(_Link_type __x) |
||
569 | { return __x->_M_value_field; } |
||
570 | static const _Key& _S_key(_Link_type __x) |
||
571 | { return _KeyOfValue()(_S_value(__x)); } |
||
572 | static _Color_type& _S_color(_Link_type __x) |
||
573 | { return (_Color_type&)(__x->_M_color); } |
||
574 | |||
575 | static _Link_type& _S_left(_Base_ptr __x) |
||
576 | { return (_Link_type&)(__x->_M_left); } |
||
577 | static _Link_type& _S_right(_Base_ptr __x) |
||
578 | { return (_Link_type&)(__x->_M_right); } |
||
579 | static _Link_type& _S_parent(_Base_ptr __x) |
||
580 | { return (_Link_type&)(__x->_M_parent); } |
||
581 | static reference _S_value(_Base_ptr __x) |
||
582 | { return ((_Link_type)__x)->_M_value_field; } |
||
583 | static const _Key& _S_key(_Base_ptr __x) |
||
584 | { return _KeyOfValue()(_S_value(_Link_type(__x)));} |
||
585 | static _Color_type& _S_color(_Base_ptr __x) |
||
586 | { return (_Color_type&)(_Link_type(__x)->_M_color); } |
||
587 | |||
588 | static _Link_type _S_minimum(_Link_type __x) |
||
589 | { return (_Link_type) _Rb_tree_node_base::_S_minimum(__x); } |
||
590 | |||
591 | static _Link_type _S_maximum(_Link_type __x) |
||
592 | { return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); } |
||
593 | |||
594 | public: |
||
595 | typedef _Rb_tree_iterator |
||
596 | typedef _Rb_tree_iterator |
||
597 | const_iterator; |
||
598 | |||
599 | typedef reverse_iterator |
||
600 | typedef reverse_iterator |
||
601 | |||
602 | private: |
||
603 | iterator _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v); |
||
604 | _Link_type _M_copy(_Link_type __x, _Link_type __p); |
||
605 | void _M_erase(_Link_type __x); |
||
606 | |||
607 | public: |
||
608 | // allocation/deallocation |
||
609 | _Rb_tree() |
||
610 | : _Base(allocator_type()), _M_node_count(0), _M_key_compare() |
||
611 | { _M_empty_initialize(); } |
||
612 | |||
613 | _Rb_tree(const _Compare& __comp) |
||
614 | : _Base(allocator_type()), _M_node_count(0), _M_key_compare(__comp) |
||
615 | { _M_empty_initialize(); } |
||
616 | |||
617 | _Rb_tree(const _Compare& __comp, const allocator_type& __a) |
||
618 | : _Base(__a), _M_node_count(0), _M_key_compare(__comp) |
||
619 | { _M_empty_initialize(); } |
||
620 | |||
621 | _Rb_tree(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x) |
||
622 | : _Base(__x.get_allocator()), |
||
623 | _M_node_count(0), _M_key_compare(__x._M_key_compare) |
||
624 | { |
||
625 | if (__x._M_root() == 0) |
||
626 | _M_empty_initialize(); |
||
627 | else { |
||
628 | _S_color(_M_header) = _S_rb_tree_red; |
||
629 | _M_root() = _M_copy(__x._M_root(), _M_header); |
||
630 | _M_leftmost() = _S_minimum(_M_root()); |
||
631 | _M_rightmost() = _S_maximum(_M_root()); |
||
632 | } |
||
633 | _M_node_count = __x._M_node_count; |
||
634 | } |
||
635 | ~_Rb_tree() { clear(); } |
||
636 | _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& |
||
637 | operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x); |
||
638 | |||
639 | private: |
||
640 | void _M_empty_initialize() { |
||
641 | _S_color(_M_header) = _S_rb_tree_red; // used to distinguish header from |
||
642 | // __root, in iterator.operator++ |
||
643 | _M_root() = 0; |
||
644 | _M_leftmost() = _M_header; |
||
645 | _M_rightmost() = _M_header; |
||
646 | } |
||
647 | |||
648 | public: |
||
649 | // accessors: |
||
650 | _Compare key_comp() const { return _M_key_compare; } |
||
651 | iterator begin() { return _M_leftmost(); } |
||
652 | const_iterator begin() const { return _M_leftmost(); } |
||
653 | iterator end() { return _M_header; } |
||
654 | const_iterator end() const { return _M_header; } |
||
655 | reverse_iterator rbegin() { return reverse_iterator(end()); } |
||
656 | const_reverse_iterator rbegin() const { |
||
657 | return const_reverse_iterator(end()); |
||
658 | } |
||
659 | reverse_iterator rend() { return reverse_iterator(begin()); } |
||
660 | const_reverse_iterator rend() const { |
||
661 | return const_reverse_iterator(begin()); |
||
662 | } |
||
663 | bool empty() const { return _M_node_count == 0; } |
||
664 | size_type size() const { return _M_node_count; } |
||
665 | size_type max_size() const { return size_type(-1); } |
||
666 | |||
667 | void swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __t) { |
||
668 | std::swap(_M_header, __t._M_header); |
||
669 | std::swap(_M_node_count, __t._M_node_count); |
||
670 | std::swap(_M_key_compare, __t._M_key_compare); |
||
671 | } |
||
672 | |||
673 | public: |
||
674 | // insert/erase |
||
675 | pair |
||
676 | iterator insert_equal(const value_type& __x); |
||
677 | |||
678 | iterator insert_unique(iterator __position, const value_type& __x); |
||
679 | iterator insert_equal(iterator __position, const value_type& __x); |
||
680 | |||
681 | template |
||
682 | void insert_unique(_InputIterator __first, _InputIterator __last); |
||
683 | template |
||
684 | void insert_equal(_InputIterator __first, _InputIterator __last); |
||
685 | |||
686 | void erase(iterator __position); |
||
687 | size_type erase(const key_type& __x); |
||
688 | void erase(iterator __first, iterator __last); |
||
689 | void erase(const key_type* __first, const key_type* __last); |
||
690 | void clear() { |
||
691 | if (_M_node_count != 0) { |
||
692 | _M_erase(_M_root()); |
||
693 | _M_leftmost() = _M_header; |
||
694 | _M_root() = 0; |
||
695 | _M_rightmost() = _M_header; |
||
696 | _M_node_count = 0; |
||
697 | } |
||
698 | } |
||
699 | |||
700 | public: |
||
701 | // set operations: |
||
702 | iterator find(const key_type& __x); |
||
703 | const_iterator find(const key_type& __x) const; |
||
704 | size_type count(const key_type& __x) const; |
||
705 | iterator lower_bound(const key_type& __x); |
||
706 | const_iterator lower_bound(const key_type& __x) const; |
||
707 | iterator upper_bound(const key_type& __x); |
||
708 | const_iterator upper_bound(const key_type& __x) const; |
||
709 | pair |
||
710 | pair |
||
711 | |||
712 | public: |
||
713 | // Debugging. |
||
714 | bool __rb_verify() const; |
||
715 | }; |
||
716 | |||
717 | template |
||
718 | class _Compare, class _Alloc> |
||
719 | inline bool |
||
720 | operator==(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, |
||
721 | const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) |
||
722 | { |
||
723 | return __x.size() == __y.size() && |
||
724 | equal(__x.begin(), __x.end(), __y.begin()); |
||
725 | } |
||
726 | |||
727 | template |
||
728 | class _Compare, class _Alloc> |
||
729 | inline bool |
||
730 | operator<(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, |
||
731 | const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) |
||
732 | { |
||
733 | return lexicographical_compare(__x.begin(), __x.end(), |
||
734 | __y.begin(), __y.end()); |
||
735 | } |
||
736 | |||
737 | template |
||
738 | class _Compare, class _Alloc> |
||
739 | inline bool |
||
740 | operator!=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, |
||
741 | const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) { |
||
742 | return !(__x == __y); |
||
743 | } |
||
744 | |||
745 | template |
||
746 | class _Compare, class _Alloc> |
||
747 | inline bool |
||
748 | operator>(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, |
||
749 | const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) { |
||
750 | return __y < __x; |
||
751 | } |
||
752 | |||
753 | template |
||
754 | class _Compare, class _Alloc> |
||
755 | inline bool |
||
756 | operator<=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, |
||
757 | const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) { |
||
758 | return !(__y < __x); |
||
759 | } |
||
760 | |||
761 | template |
||
762 | class _Compare, class _Alloc> |
||
763 | inline bool |
||
764 | operator>=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, |
||
765 | const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) { |
||
766 | return !(__x < __y); |
||
767 | } |
||
768 | |||
769 | |||
770 | template |
||
771 | class _Compare, class _Alloc> |
||
772 | inline void |
||
773 | swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, |
||
774 | _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) |
||
775 | { |
||
776 | __x.swap(__y); |
||
777 | } |
||
778 | |||
779 | |||
780 | template |
||
781 | class _Compare, class _Alloc> |
||
782 | _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& |
||
783 | _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> |
||
784 | ::operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x) |
||
785 | { |
||
786 | if (this != &__x) { |
||
787 | // Note that _Key may be a constant type. |
||
788 | clear(); |
||
789 | _M_node_count = 0; |
||
790 | _M_key_compare = __x._M_key_compare; |
||
791 | if (__x._M_root() == 0) { |
||
792 | _M_root() = 0; |
||
793 | _M_leftmost() = _M_header; |
||
794 | _M_rightmost() = _M_header; |
||
795 | } |
||
796 | else { |
||
797 | _M_root() = _M_copy(__x._M_root(), _M_header); |
||
798 | _M_leftmost() = _S_minimum(_M_root()); |
||
799 | _M_rightmost() = _S_maximum(_M_root()); |
||
800 | _M_node_count = __x._M_node_count; |
||
801 | } |
||
802 | } |
||
803 | return *this; |
||
804 | } |
||
805 | |||
806 | template |
||
807 | class _Compare, class _Alloc> |
||
808 | typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator |
||
809 | _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> |
||
810 | ::_M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Value& __v) |
||
811 | { |
||
812 | _Link_type __x = (_Link_type) __x_; |
||
813 | _Link_type __y = (_Link_type) __y_; |
||
814 | _Link_type __z; |
||
815 | |||
816 | if (__y == _M_header || __x != 0 || |
||
817 | _M_key_compare(_KeyOfValue()(__v), _S_key(__y))) { |
||
818 | __z = _M_create_node(__v); |
||
819 | _S_left(__y) = __z; // also makes _M_leftmost() = __z |
||
820 | // when __y == _M_header |
||
821 | if (__y == _M_header) { |
||
822 | _M_root() = __z; |
||
823 | _M_rightmost() = __z; |
||
824 | } |
||
825 | else if (__y == _M_leftmost()) |
||
826 | _M_leftmost() = __z; // maintain _M_leftmost() pointing to min node |
||
827 | } |
||
828 | else { |
||
829 | __z = _M_create_node(__v); |
||
830 | _S_right(__y) = __z; |
||
831 | if (__y == _M_rightmost()) |
||
832 | _M_rightmost() = __z; // maintain _M_rightmost() pointing to max node |
||
833 | } |
||
834 | _S_parent(__z) = __y; |
||
835 | _S_left(__z) = 0; |
||
836 | _S_right(__z) = 0; |
||
837 | _Rb_tree_rebalance(__z, _M_header->_M_parent); |
||
838 | ++_M_node_count; |
||
839 | return iterator(__z); |
||
840 | } |
||
841 | |||
842 | template |
||
843 | class _Compare, class _Alloc> |
||
844 | typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator |
||
845 | _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> |
||
846 | ::insert_equal(const _Value& __v) |
||
847 | { |
||
848 | _Link_type __y = _M_header; |
||
849 | _Link_type __x = _M_root(); |
||
850 | while (__x != 0) { |
||
851 | __y = __x; |
||
852 | __x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? |
||
853 | _S_left(__x) : _S_right(__x); |
||
854 | } |
||
855 | return _M_insert(__x, __y, __v); |
||
856 | } |
||
857 | |||
858 | |||
859 | template |
||
860 | class _Compare, class _Alloc> |
||
861 | pair |
||
862 | bool> |
||
863 | _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> |
||
864 | ::insert_unique(const _Value& __v) |
||
865 | { |
||
866 | _Link_type __y = _M_header; |
||
867 | _Link_type __x = _M_root(); |
||
868 | bool __comp = true; |
||
869 | while (__x != 0) { |
||
870 | __y = __x; |
||
871 | __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)); |
||
872 | __x = __comp ? _S_left(__x) : _S_right(__x); |
||
873 | } |
||
874 | iterator __j = iterator(__y); |
||
875 | if (__comp) |
||
876 | if (__j == begin()) |
||
877 | return pair |
||
878 | else |
||
879 | --__j; |
||
880 | if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) |
||
881 | return pair |
||
882 | return pair |
||
883 | } |
||
884 | |||
885 | |||
886 | template |
||
887 | class _Compare, class _Alloc> |
||
888 | typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator |
||
889 | _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc> |
||
890 | ::insert_unique(iterator __position, const _Val& __v) |
||
891 | { |
||
892 | if (__position._M_node == _M_header->_M_left) { // begin() |
||
893 | if (size() > 0 && |
||
894 | _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v))) |
||
895 | return _M_insert(__position._M_node, __position._M_node, __v); |
||
896 | // first argument just needs to be non-null |
||
897 | else |
||
898 | return insert_unique(__v).first; |
||
899 | } else if (__position._M_node == _M_header) { // end() |
||
900 | if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v))) |
||
901 | return _M_insert(0, _M_rightmost(), __v); |
||
902 | else |
||
903 | return insert_unique(__v).first; |
||
904 | } else { |
||
905 | iterator __before = __position; |
||
906 | --__before; |
||
907 | if (_M_key_compare(_S_key(__before._M_node), _KeyOfValue()(__v)) |
||
908 | && _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node))) { |
||
909 | if (_S_right(__before._M_node) == 0) |
||
910 | return _M_insert(0, __before._M_node, __v); |
||
911 | else |
||
912 | return _M_insert(__position._M_node, __position._M_node, __v); |
||
913 | // first argument just needs to be non-null |
||
914 | } else |
||
915 | return insert_unique(__v).first; |
||
916 | } |
||
917 | } |
||
918 | |||
919 | template |
||
920 | class _Compare, class _Alloc> |
||
921 | typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator |
||
922 | _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc> |
||
923 | ::insert_equal(iterator __position, const _Val& __v) |
||
924 | { |
||
925 | if (__position._M_node == _M_header->_M_left) { // begin() |
||
926 | if (size() > 0 && |
||
927 | !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v))) |
||
928 | return _M_insert(__position._M_node, __position._M_node, __v); |
||
929 | // first argument just needs to be non-null |
||
930 | else |
||
931 | return insert_equal(__v); |
||
932 | } else if (__position._M_node == _M_header) {// end() |
||
933 | if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost()))) |
||
934 | return _M_insert(0, _M_rightmost(), __v); |
||
935 | else |
||
936 | return insert_equal(__v); |
||
937 | } else { |
||
938 | iterator __before = __position; |
||
939 | --__before; |
||
940 | if (!_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node)) |
||
941 | && !_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v))) { |
||
942 | if (_S_right(__before._M_node) == 0) |
||
943 | return _M_insert(0, __before._M_node, __v); |
||
944 | else |
||
945 | return _M_insert(__position._M_node, __position._M_node, __v); |
||
946 | // first argument just needs to be non-null |
||
947 | } else |
||
948 | return insert_equal(__v); |
||
949 | } |
||
950 | } |
||
951 | |||
952 | template |
||
953 | template |
||
954 | void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc> |
||
955 | ::insert_equal(_II __first, _II __last) |
||
956 | { |
||
957 | for ( ; __first != __last; ++__first) |
||
958 | insert_equal(*__first); |
||
959 | } |
||
960 | |||
961 | template |
||
962 | template |
||
963 | void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc> |
||
964 | ::insert_unique(_II __first, _II __last) { |
||
965 | for ( ; __first != __last; ++__first) |
||
966 | insert_unique(*__first); |
||
967 | } |
||
968 | |||
969 | template |
||
970 | class _Compare, class _Alloc> |
||
971 | inline void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> |
||
972 | ::erase(iterator __position) |
||
973 | { |
||
974 | _Link_type __y = |
||
975 | (_Link_type) _Rb_tree_rebalance_for_erase(__position._M_node, |
||
976 | _M_header->_M_parent, |
||
977 | _M_header->_M_left, |
||
978 | _M_header->_M_right); |
||
979 | destroy_node(__y); |
||
980 | --_M_node_count; |
||
981 | } |
||
982 | |||
983 | template |
||
984 | class _Compare, class _Alloc> |
||
985 | typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::size_type |
||
986 | _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x) |
||
987 | { |
||
988 | pair |
||
989 | size_type __n = 0; |
||
990 | distance(__p.first, __p.second, __n); |
||
991 | erase(__p.first, __p.second); |
||
992 | return __n; |
||
993 | } |
||
994 | |||
995 | template |
||
996 | typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type |
||
997 | _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc> |
||
998 | ::_M_copy(_Link_type __x, _Link_type __p) |
||
999 | { |
||
1000 | // structural copy. __x and __p must be non-null. |
||
1001 | _Link_type __top = _M_clone_node(__x); |
||
1002 | __top->_M_parent = __p; |
||
1003 | |||
1004 | __STL_TRY { |
||
1005 | if (__x->_M_right) |
||
1006 | __top->_M_right = _M_copy(_S_right(__x), __top); |
||
1007 | __p = __top; |
||
1008 | __x = _S_left(__x); |
||
1009 | |||
1010 | while (__x != 0) { |
||
1011 | _Link_type __y = _M_clone_node(__x); |
||
1012 | __p->_M_left = __y; |
||
1013 | __y->_M_parent = __p; |
||
1014 | if (__x->_M_right) |
||
1015 | __y->_M_right = _M_copy(_S_right(__x), __y); |
||
1016 | __p = __y; |
||
1017 | __x = _S_left(__x); |
||
1018 | } |
||
1019 | } |
||
1020 | __STL_UNWIND(_M_erase(__top)); |
||
1021 | |||
1022 | return __top; |
||
1023 | } |
||
1024 | |||
1025 | template |
||
1026 | class _Compare, class _Alloc> |
||
1027 | void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> |
||
1028 | ::_M_erase(_Link_type __x) |
||
1029 | { |
||
1030 | // erase without rebalancing |
||
1031 | while (__x != 0) { |
||
1032 | _M_erase(_S_right(__x)); |
||
1033 | _Link_type __y = _S_left(__x); |
||
1034 | destroy_node(__x); |
||
1035 | __x = __y; |
||
1036 | } |
||
1037 | } |
||
1038 | |||
1039 | template |
||
1040 | class _Compare, class _Alloc> |
||
1041 | void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> |
||
1042 | ::erase(iterator __first, iterator __last) |
||
1043 | { |
||
1044 | if (__first == begin() && __last == end()) |
||
1045 | clear(); |
||
1046 | else |
||
1047 | while (__first != __last) erase(__first++); |
||
1048 | } |
||
1049 | |||
1050 | template |
||
1051 | class _Compare, class _Alloc> |
||
1052 | void _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> |
||
1053 | ::erase(const _Key* __first, const _Key* __last) |
||
1054 | { |
||
1055 | while (__first != __last) erase(*__first++); |
||
1056 | } |
||
1057 | |||
1058 | template |
||
1059 | class _Compare, class _Alloc> |
||
1060 | typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator |
||
1061 | _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k) |
||
1062 | { |
||
1063 | _Link_type __y = _M_header; // Last node which is not less than __k. |
||
1064 | _Link_type __x = _M_root(); // Current node. |
||
1065 | |||
1066 | while (__x != 0) |
||
1067 | if (!_M_key_compare(_S_key(__x), __k)) |
||
1068 | __y = __x, __x = _S_left(__x); |
||
1069 | else |
||
1070 | __x = _S_right(__x); |
||
1071 | |||
1072 | iterator __j = iterator(__y); |
||
1073 | return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ? |
||
1074 | end() : __j; |
||
1075 | } |
||
1076 | |||
1077 | template |
||
1078 | class _Compare, class _Alloc> |
||
1079 | typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator |
||
1080 | _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k) const |
||
1081 | { |
||
1082 | _Link_type __y = _M_header; /* Last node which is not less than __k. */ |
||
1083 | _Link_type __x = _M_root(); /* Current node. */ |
||
1084 | |||
1085 | while (__x != 0) { |
||
1086 | if (!_M_key_compare(_S_key(__x), __k)) |
||
1087 | __y = __x, __x = _S_left(__x); |
||
1088 | else |
||
1089 | __x = _S_right(__x); |
||
1090 | } |
||
1091 | const_iterator __j = const_iterator(__y); |
||
1092 | return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ? |
||
1093 | end() : __j; |
||
1094 | } |
||
1095 | |||
1096 | template |
||
1097 | class _Compare, class _Alloc> |
||
1098 | typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::size_type |
||
1099 | _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> |
||
1100 | ::count(const _Key& __k) const |
||
1101 | { |
||
1102 | pair |
||
1103 | size_type __n = 0; |
||
1104 | distance(__p.first, __p.second, __n); |
||
1105 | return __n; |
||
1106 | } |
||
1107 | |||
1108 | template |
||
1109 | class _Compare, class _Alloc> |
||
1110 | typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator |
||
1111 | _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> |
||
1112 | ::lower_bound(const _Key& __k) |
||
1113 | { |
||
1114 | _Link_type __y = _M_header; /* Last node which is not less than __k. */ |
||
1115 | _Link_type __x = _M_root(); /* Current node. */ |
||
1116 | |||
1117 | while (__x != 0) |
||
1118 | if (!_M_key_compare(_S_key(__x), __k)) |
||
1119 | __y = __x, __x = _S_left(__x); |
||
1120 | else |
||
1121 | __x = _S_right(__x); |
||
1122 | |||
1123 | return iterator(__y); |
||
1124 | } |
||
1125 | |||
1126 | template |
||
1127 | class _Compare, class _Alloc> |
||
1128 | typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator |
||
1129 | _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> |
||
1130 | ::lower_bound(const _Key& __k) const |
||
1131 | { |
||
1132 | _Link_type __y = _M_header; /* Last node which is not less than __k. */ |
||
1133 | _Link_type __x = _M_root(); /* Current node. */ |
||
1134 | |||
1135 | while (__x != 0) |
||
1136 | if (!_M_key_compare(_S_key(__x), __k)) |
||
1137 | __y = __x, __x = _S_left(__x); |
||
1138 | else |
||
1139 | __x = _S_right(__x); |
||
1140 | |||
1141 | return const_iterator(__y); |
||
1142 | } |
||
1143 | |||
1144 | template |
||
1145 | class _Compare, class _Alloc> |
||
1146 | typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator |
||
1147 | _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> |
||
1148 | ::upper_bound(const _Key& __k) |
||
1149 | { |
||
1150 | _Link_type __y = _M_header; /* Last node which is greater than __k. */ |
||
1151 | _Link_type __x = _M_root(); /* Current node. */ |
||
1152 | |||
1153 | while (__x != 0) |
||
1154 | if (_M_key_compare(__k, _S_key(__x))) |
||
1155 | __y = __x, __x = _S_left(__x); |
||
1156 | else |
||
1157 | __x = _S_right(__x); |
||
1158 | |||
1159 | return iterator(__y); |
||
1160 | } |
||
1161 | |||
1162 | template |
||
1163 | class _Compare, class _Alloc> |
||
1164 | typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::const_iterator |
||
1165 | _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> |
||
1166 | ::upper_bound(const _Key& __k) const |
||
1167 | { |
||
1168 | _Link_type __y = _M_header; /* Last node which is greater than __k. */ |
||
1169 | _Link_type __x = _M_root(); /* Current node. */ |
||
1170 | |||
1171 | while (__x != 0) |
||
1172 | if (_M_key_compare(__k, _S_key(__x))) |
||
1173 | __y = __x, __x = _S_left(__x); |
||
1174 | else |
||
1175 | __x = _S_right(__x); |
||
1176 | |||
1177 | return const_iterator(__y); |
||
1178 | } |
||
1179 | |||
1180 | template |
||
1181 | class _Compare, class _Alloc> |
||
1182 | inline |
||
1183 | pair |
||
1184 | typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator> |
||
1185 | _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> |
||
1186 | ::equal_range(const _Key& __k) |
||
1187 | { |
||
1188 | return pair |
||
1189 | } |
||
1190 | |||
1191 | template |
||
1192 | inline |
||
1193 | pair |
||
1194 | typename _Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc>::const_iterator> |
||
1195 | _Rb_tree<_Key, _Value, _KoV, _Compare, _Alloc> |
||
1196 | ::equal_range(const _Key& __k) const |
||
1197 | { |
||
1198 | return pair |
||
1199 | upper_bound(__k)); |
||
1200 | } |
||
1201 | |||
1202 | inline int |
||
1203 | __black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root) |
||
1204 | { |
||
1205 | if (__node == 0) |
||
1206 | return 0; |
||
1207 | int __sum = 0; |
||
1208 | do { |
||
1209 | if (__node->_M_color == _S_rb_tree_black) |
||
1210 | ++__sum; |
||
1211 | if (__node == __root) |
||
1212 | break; |
||
1213 | __node = __node->_M_parent; |
||
1214 | } while (1); |
||
1215 | return __sum; |
||
1216 | } |
||
1217 | |||
1218 | template |
||
1219 | class _Compare, class _Alloc> |
||
1220 | bool _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const |
||
1221 | { |
||
1222 | if (_M_node_count == 0 || begin() == end()) |
||
1223 | return _M_node_count == 0 && begin() == end() && |
||
1224 | _M_header->_M_left == _M_header && _M_header->_M_right == _M_header; |
||
1225 | |||
1226 | int __len = __black_count(_M_leftmost(), _M_root()); |
||
1227 | for (const_iterator __it = begin(); __it != end(); ++__it) { |
||
1228 | _Link_type __x = (_Link_type) __it._M_node; |
||
1229 | _Link_type __L = _S_left(__x); |
||
1230 | _Link_type __R = _S_right(__x); |
||
1231 | |||
1232 | if (__x->_M_color == _S_rb_tree_red) |
||
1233 | if ((__L && __L->_M_color == _S_rb_tree_red) || |
||
1234 | (__R && __R->_M_color == _S_rb_tree_red)) |
||
1235 | return false; |
||
1236 | |||
1237 | if (__L && _M_key_compare(_S_key(__x), _S_key(__L))) |
||
1238 | return false; |
||
1239 | if (__R && _M_key_compare(_S_key(__R), _S_key(__x))) |
||
1240 | return false; |
||
1241 | |||
1242 | if (!__L && !__R && __black_count(__x, _M_root()) != __len) |
||
1243 | return false; |
||
1244 | } |
||
1245 | |||
1246 | if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) |
||
1247 | return false; |
||
1248 | if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) |
||
1249 | return false; |
||
1250 | |||
1251 | return true; |
||
1252 | } |
||
1253 | |||
1254 | // Class rb_tree is not part of the C++ standard. It is provided for |
||
1255 | // compatibility with the HP STL. |
||
1256 | |||
1257 | template |
||
1258 | class _Alloc = allocator<_Value> > |
||
1259 | struct rb_tree : public _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> |
||
1260 | { |
||
1261 | typedef _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> _Base; |
||
1262 | typedef typename _Base::allocator_type allocator_type; |
||
1263 | |||
1264 | rb_tree(const _Compare& __comp = _Compare(), |
||
1265 | const allocator_type& __a = allocator_type()) |
||
1266 | : _Base(__comp, __a) {} |
||
1267 | |||
1268 | ~rb_tree() {} |
||
1269 | }; |
||
1270 | |||
1271 | } // namespace std |
||
1272 | |||
1273 | #endif /* __SGI_STL_INTERNAL_TREE_H */ |
||
1274 | |||
1275 | // Local Variables: |
||
1276 | // mode:C++ |
||
1277 | // End:>>=(const>>(const>-> |