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