← Back to branch summary

~ubuntu-branches/ubuntu/hardy/libterralib/hardy

« back to all changes in this revision

Viewing changes to src/STLport/stl/_tree.h

  • Committer: Bazaar Package Importer
  • Author(s): Daniel T Chen
  • Date: 2005-11-25 22:32:59 UTC
  • Revision ID: james.westby@ubuntu.com-20051125223259-3zubal8ux4ki4fjg
Tags: upstream-3.0.3b2
Import upstream version 3.0.3b2

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/STLport/stl/_tree.h
 
1
/*
 
2
 *
 
3
 * Copyright (c) 1994
 
4
 * Hewlett-Packard Company
 
5
 *
 
6
 * Copyright (c) 1996,1997
 
7
 * Silicon Graphics Computer Systems, Inc.
 
8
 *
 
9
 * Copyright (c) 1997
 
10
 * Moscow Center for SPARC Technology
 
11
 *
 
12
 * Copyright (c) 1999 
 
13
 * Boris Fomitchev
 
14
 *
 
15
 * This material is provided "as is", with absolutely no warranty expressed
 
16
 * or implied. Any use is at your own risk.
 
17
 *
 
18
 * Permission to use or copy this software for any purpose is hereby granted 
 
19
 * without fee, provided the above notices are retained on all copies.
 
20
 * Permission to modify the code and to distribute modified code is granted,
 
21
 * provided the above notices are retained, and a notice that the code was
 
22
 * modified is included with the above copyright notice.
 
23
 *
 
24
 */
 
25
 
 
26
/* NOTE: This is an internal header file, included by other STL headers.
 
27
 *   You should not attempt to use it directly.
 
28
 */
 
29
 
 
30
#ifndef _STLP_INTERNAL_TREE_H
 
31
#define _STLP_INTERNAL_TREE_H
 
32
 
 
33
/*
 
34
 
 
35
Red-black tree class, designed for use in implementing STL
 
36
associative containers (set, multiset, map, and multimap). The
 
37
insertion and deletion algorithms are based on those in Cormen,
 
38
Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
 
39
except that
 
40
 
 
41
(1) the header cell is maintained with links not only to the root
 
42
but also to the leftmost node of the tree, to enable constant time
 
43
begin(), and to the rightmost node of the tree, to enable linear time
 
44
performance when used with the generic set algorithms (set_union,
 
45
etc.);
 
46
 
 
47
(2) when a node being deleted has two children its successor node is
 
48
relinked into its place, rather than copied, so that the only
 
49
iterators invalidated are those referring to the deleted node.
 
50
 
 
51
*/
 
52
 
 
53
# ifndef _STLP_INTERNAL_ALGOBASE_H
 
54
#  include <stl/_algobase.h> 
 
55
# endif
 
56
 
 
57
# ifndef _STLP_INTERNAL_ALLOC_H
 
58
#  include <stl/_alloc.h> 
 
59
# endif
 
60
 
 
61
# ifndef _STLP_INTERNAL_ITERATOR_H
 
62
#  include <stl/_iterator.h> 
 
63
# endif
 
64
 
 
65
# ifndef _STLP_INTERNAL_CONSTRUCT_H
 
66
#  include <stl/_construct.h> 
 
67
# endif
 
68
 
 
69
# ifndef _STLP_INTERNAL_FUNCTION_H
 
70
#  include <stl/_function_base.h> 
 
71
# endif
 
72
 
 
73
#if defined ( _STLP_DEBUG)
 
74
#  define _Rb_tree __WORKAROUND_DBG_RENAME(Rb_tree)
 
75
#endif
 
76
 
 
77
_STLP_BEGIN_NAMESPACE
 
78
 
 
79
typedef bool _Rb_tree_Color_type;
 
80
//const _Rb_tree_Color_type _S_rb_tree_red = false;
 
81
//const _Rb_tree_Color_type _S_rb_tree_black = true;
 
82
 
 
83
#define _S_rb_tree_red false
 
84
#define _S_rb_tree_black true
 
85
 
 
86
struct _Rb_tree_node_base
 
87
{
 
88
  typedef _Rb_tree_Color_type _Color_type;
 
89
  typedef _Rb_tree_node_base* _Base_ptr;
 
90
 
 
91
  _Color_type _M_color; 
 
92
  _Base_ptr _M_parent;
 
93
  _Base_ptr _M_left;
 
94
  _Base_ptr _M_right;
 
95
 
 
96
  static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x)
 
97
  {
 
98
    while (__x->_M_left != 0) __x = __x->_M_left;
 
99
    return __x;
 
100
  }
 
101
 
 
102
  static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x)
 
103
  {
 
104
    while (__x->_M_right != 0) __x = __x->_M_right;
 
105
    return __x;
 
106
  }
 
107
};
 
108
 
 
109
template <class _Value> struct _Rb_tree_node : public _Rb_tree_node_base
 
110
{
 
111
  _Value _M_value_field;
 
112
  __TRIVIAL_STUFF(_Rb_tree_node)
 
113
};
 
114
 
 
115
struct _Rb_tree_base_iterator;
 
116
 
 
117
template <class _Dummy> class _Rb_global {
 
118
public:
 
119
  typedef _Rb_tree_node_base* _Base_ptr;
 
120
  // those used to be global functions 
 
121
  static void _STLP_CALL _Rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root);
 
122
  static _Rb_tree_node_base* _STLP_CALL _Rebalance_for_erase(_Rb_tree_node_base* __z,
 
123
                                                             _Rb_tree_node_base*& __root,
 
124
                                                             _Rb_tree_node_base*& __leftmost,
 
125
                                                             _Rb_tree_node_base*& __rightmost);
 
126
  // those are from _Rb_tree_base_iterator - moved here to reduce code bloat
 
127
  // moved here to reduce code bloat without templatizing _Rb_tree_base_iterator
 
128
  static _Rb_tree_node_base*  _STLP_CALL _M_increment(_Rb_tree_node_base*);
 
129
  static _Rb_tree_node_base*  _STLP_CALL _M_decrement(_Rb_tree_node_base*);
 
130
  static void _STLP_CALL _Rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root);
 
131
  static void _STLP_CALL _Rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root); 
 
132
};
 
133
 
 
134
# if defined (_STLP_USE_TEMPLATE_EXPORT) 
 
135
_STLP_EXPORT_TEMPLATE_CLASS _Rb_global<bool>;
 
136
# endif
 
137
 
 
138
typedef _Rb_global<bool> _Rb_global_inst;
 
139
 
 
140
struct _Rb_tree_base_iterator
 
141
{
 
142
  typedef _Rb_tree_node_base*        _Base_ptr;
 
143
  typedef bidirectional_iterator_tag iterator_category;
 
144
  typedef ptrdiff_t                  difference_type;
 
145
  _Base_ptr _M_node;
 
146
  bool operator==(const _Rb_tree_base_iterator& __y) const {
 
147
    return _M_node == __y._M_node;
 
148
  }
 
149
  bool operator!=(const _Rb_tree_base_iterator& __y) const {
 
150
    return _M_node != __y._M_node;
 
151
  }
 
152
};
 
153
 
 
154
 
 
155
template <class _Value, class _Traits> struct _Rb_tree_iterator : public _Rb_tree_base_iterator
 
156
{
 
157
  typedef _Value value_type;
 
158
  typedef typename _Traits::reference  reference;
 
159
  typedef typename _Traits::pointer    pointer;
 
160
  typedef _Rb_tree_iterator<_Value, _Traits> _Self;
 
161
  typedef _Rb_tree_node<_Value>* _Link_type;
 
162
 
 
163
  _Rb_tree_iterator() { _M_node = 0; }
 
164
  _Rb_tree_iterator(_Link_type __x) { _M_node = __x; }
 
165
  _Rb_tree_iterator(const _Rb_tree_iterator<_Value, 
 
166
                    _Nonconst_traits<_Value> >& __it) { _M_node = __it._M_node; }
 
167
 
 
168
  reference operator*() const { 
 
169
    return _Link_type(_M_node)->_M_value_field; 
 
170
  }
 
171
  
 
172
  _STLP_DEFINE_ARROW_OPERATOR
 
173
 
 
174
  _Self& operator++() { _M_node = _Rb_global_inst::_M_increment(_M_node); return *this; }
 
175
  _Self operator++(int) {
 
176
    _Self __tmp = *this;
 
177
    _M_node = _Rb_global_inst::_M_increment(_M_node);
 
178
    return __tmp;
 
179
  }
 
180
    
 
181
  _Self& operator--() { _M_node = _Rb_global_inst::_M_decrement(_M_node); return *this; }
 
182
  _Self operator--(int) {
 
183
    _Self __tmp = *this;
 
184
    _M_node = _Rb_global_inst::_M_decrement(_M_node);
 
185
    return __tmp;
 
186
  }
 
187
};
 
188
 
 
189
# ifdef _STLP_USE_OLD_HP_ITERATOR_QUERIES
 
190
template <class _Value, class _Traits> inline _Value* value_type(const _Rb_tree_iterator<_Value, _Traits>&) { return (_Value*)0; }
 
191
inline bidirectional_iterator_tag iterator_category(const _Rb_tree_base_iterator&) { return bidirectional_iterator_tag(); }
 
192
inline ptrdiff_t* distance_type(const _Rb_tree_base_iterator&) { return (ptrdiff_t*) 0; }
 
193
#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
 
194
 
 
195
// Base class to help EH
 
196
 
 
197
template <class _Tp, class _Alloc> struct _Rb_tree_base
 
198
{
 
199
  typedef _Rb_tree_node<_Tp> _Node;
 
200
  _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
 
201
  typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
 
202
 
 
203
  _Rb_tree_base(const allocator_type& __a) : 
 
204
    _M_header(_STLP_CONVERT_ALLOCATOR(__a, _Node), (_Node*)0) { 
 
205
      _M_header._M_data = _M_header.allocate(1); 
 
206
  }
 
207
  ~_Rb_tree_base() { 
 
208
    _M_header.deallocate(_M_header._M_data,1); 
 
209
  }
 
210
  allocator_type get_allocator() const { 
 
211
    return _STLP_CONVERT_ALLOCATOR(_M_header, _Tp); 
 
212
  }
 
213
protected:
 
214
  typedef typename _Alloc_traits<_Node, _Alloc>::allocator_type _M_node_allocator_type;
 
215
  _STLP_alloc_proxy<_Node*, _Node, _M_node_allocator_type> _M_header;
 
216
};
 
217
 
 
218
 
 
219
template <class _Key, class _Value, class _KeyOfValue, class _Compare,
 
220
          _STLP_DEFAULT_ALLOCATOR_SELECT(_Value) > class _Rb_tree : public _Rb_tree_base<_Value, _Alloc> {
 
221
  typedef _Rb_tree_base<_Value, _Alloc> _Base;
 
222
protected:
 
223
  typedef _Rb_tree_node_base* _Base_ptr;
 
224
  typedef _Rb_tree_node<_Value> _Node;
 
225
  typedef _Rb_tree_Color_type _Color_type;
 
226
public:
 
227
  typedef _Key key_type;
 
228
  typedef _Value value_type;
 
229
  typedef value_type* pointer;
 
230
  typedef const value_type* const_pointer;
 
231
  typedef value_type& reference;
 
232
  typedef const value_type& const_reference;
 
233
  typedef _Rb_tree_node<_Value>* _Link_type;
 
234
  typedef size_t size_type;
 
235
  typedef ptrdiff_t difference_type;
 
236
  typedef bidirectional_iterator_tag _Iterator_category;
 
237
  typedef typename _Base::allocator_type allocator_type;
 
238
  
 
239
protected:
 
240
 
 
241
  _Link_type _M_create_node(const value_type& __x)
 
242
  {
 
243
    _Link_type __tmp = this->_M_header.allocate(1);
 
244
    _STLP_TRY {
 
245
      _Construct(&__tmp->_M_value_field, __x);
 
246
    }
 
247
    _STLP_UNWIND(this->_M_header.deallocate(__tmp,1));
 
248
    return __tmp;
 
249
  }
 
250
 
 
251
  _Link_type _M_clone_node(_Link_type __x)
 
252
  {
 
253
    _Link_type __tmp = _M_create_node(__x->_M_value_field);
 
254
    __tmp->_M_color = __x->_M_color;
 
255
    __tmp->_M_left = 0;
 
256
    __tmp->_M_right = 0;
 
257
    return __tmp;
 
258
  }
 
259
 
 
260
protected:
 
261
  size_type _M_node_count; // keeps track of size of tree
 
262
  _Compare _M_key_compare;
 
263
 
 
264
  _Link_type& _M_root() const 
 
265
    { return (_Link_type&) this->_M_header._M_data->_M_parent; }
 
266
  _Link_type& _M_leftmost() const 
 
267
    { return (_Link_type&) this->_M_header._M_data->_M_left; }
 
268
  _Link_type& _M_rightmost() const 
 
269
    { return (_Link_type&) this->_M_header._M_data->_M_right; }
 
270
 
 
271
  static _Link_type& _STLP_CALL _S_left(_Link_type __x)
 
272
    { return (_Link_type&)(__x->_M_left); }
 
273
  static _Link_type& _STLP_CALL _S_right(_Link_type __x)
 
274
    { return (_Link_type&)(__x->_M_right); }
 
275
  static _Link_type& _STLP_CALL _S_parent(_Link_type __x)
 
276
    { return (_Link_type&)(__x->_M_parent); }
 
277
  static reference  _STLP_CALL _S_value(_Link_type __x)
 
278
    { return __x->_M_value_field; }
 
279
  static const _Key& _STLP_CALL _S_key(_Link_type __x)
 
280
    { return _KeyOfValue()(_S_value(__x)); }
 
281
  static _Color_type& _STLP_CALL _S_color(_Link_type __x)
 
282
    { return (_Color_type&)(__x->_M_color); }
 
283
 
 
284
  static _Link_type& _STLP_CALL _S_left(_Base_ptr __x)
 
285
    { return (_Link_type&)(__x->_M_left); }
 
286
  static _Link_type& _STLP_CALL _S_right(_Base_ptr __x)
 
287
    { return (_Link_type&)(__x->_M_right); }
 
288
  static _Link_type& _STLP_CALL _S_parent(_Base_ptr __x)
 
289
    { return (_Link_type&)(__x->_M_parent); }
 
290
  static reference  _STLP_CALL _S_value(_Base_ptr __x)
 
291
    { return ((_Link_type)__x)->_M_value_field; }
 
292
  static const _Key& _STLP_CALL _S_key(_Base_ptr __x)
 
293
    { return _KeyOfValue()(_S_value(_Link_type(__x)));} 
 
294
  static _Color_type& _STLP_CALL _S_color(_Base_ptr __x)
 
295
    { return (_Color_type&)(_Link_type(__x)->_M_color); }
 
296
 
 
297
  static _Link_type  _STLP_CALL _S_minimum(_Link_type __x) 
 
298
    { return (_Link_type)  _Rb_tree_node_base::_S_minimum(__x); }
 
299
 
 
300
  static _Link_type  _STLP_CALL _S_maximum(_Link_type __x)
 
301
    { return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); }
 
302
 
 
303
public:
 
304
  typedef _Rb_tree_iterator<value_type, _Nonconst_traits<value_type> > iterator;
 
305
  typedef _Rb_tree_iterator<value_type, _Const_traits<value_type> > const_iterator;
 
306
  _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS;
 
307
 
 
308
private:
 
309
  iterator _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v, _Base_ptr __w = 0);
 
310
  _Link_type _M_copy(_Link_type __x, _Link_type __p);
 
311
  void _M_erase(_Link_type __x);
 
312
 
 
313
public:
 
314
                                // allocation/deallocation
 
315
  _Rb_tree()
 
316
    : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(_Compare())
 
317
    { _M_empty_initialize(); }
 
318
 
 
319
  _Rb_tree(const _Compare& __comp)
 
320
    : _Rb_tree_base<_Value, _Alloc>(allocator_type()), _M_node_count(0), _M_key_compare(__comp) 
 
321
    { _M_empty_initialize(); }
 
322
 
 
323
  _Rb_tree(const _Compare& __comp, const allocator_type& __a)
 
324
    : _Rb_tree_base<_Value, _Alloc>(__a), _M_node_count(0), _M_key_compare(__comp) 
 
325
    { _M_empty_initialize(); }
 
326
 
 
327
  _Rb_tree(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x) 
 
328
    : _Rb_tree_base<_Value, _Alloc>(__x.get_allocator()),
 
329
      _M_node_count(0), _M_key_compare(__x._M_key_compare)
 
330
  { 
 
331
    if (__x._M_root() == 0)
 
332
      _M_empty_initialize();
 
333
    else {
 
334
      _S_color(this->_M_header._M_data) = _S_rb_tree_red;
 
335
      _M_root() = _M_copy(__x._M_root(), this->_M_header._M_data);
 
336
      _M_leftmost() = _S_minimum(_M_root());
 
337
      _M_rightmost() = _S_maximum(_M_root());
 
338
    }
 
339
    _M_node_count = __x._M_node_count;
 
340
  }
 
341
  ~_Rb_tree() { clear(); }
 
342
  _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x);
 
343
 
 
344
private:
 
345
  void _M_empty_initialize() {
 
346
    _S_color(this->_M_header._M_data) = _S_rb_tree_red; // used to distinguish header from 
 
347
                                          // __root, in iterator.operator++
 
348
    _M_root() = 0;
 
349
    _M_leftmost() = this->_M_header._M_data;
 
350
    _M_rightmost() = this->_M_header._M_data;
 
351
  }
 
352
 
 
353
public:    
 
354
                                // accessors:
 
355
  _Compare key_comp() const { return _M_key_compare; }
 
356
 
 
357
  iterator begin() { return iterator(_M_leftmost()); }
 
358
  const_iterator begin() const { return const_iterator(_M_leftmost()); }
 
359
  iterator end() { return iterator(this->_M_header._M_data); }
 
360
  const_iterator end() const { return const_iterator(this->_M_header._M_data); }
 
361
 
 
362
  reverse_iterator rbegin() { return reverse_iterator(end()); }
 
363
  const_reverse_iterator rbegin() const { 
 
364
    return const_reverse_iterator(end()); 
 
365
  }
 
366
  reverse_iterator rend() { return reverse_iterator(begin()); }
 
367
  const_reverse_iterator rend() const { 
 
368
    return const_reverse_iterator(begin());
 
369
  } 
 
370
  bool empty() const { return _M_node_count == 0; }
 
371
  size_type size() const { return _M_node_count; }
 
372
  size_type max_size() const { return size_type(-1); }
 
373
 
 
374
  void swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __t) {
 
375
    _STLP_STD::swap(this->_M_header, __t._M_header);
 
376
    _STLP_STD::swap(_M_node_count, __t._M_node_count);
 
377
    _STLP_STD::swap(_M_key_compare, __t._M_key_compare);
 
378
  }
 
379
    
 
380
public:
 
381
                                // insert/erase
 
382
  pair<iterator,bool> insert_unique(const value_type& __x);
 
383
  iterator insert_equal(const value_type& __x);
 
384
 
 
385
  iterator insert_unique(iterator __position, const value_type& __x);
 
386
  iterator insert_equal(iterator __position, const value_type& __x);
 
387
 
 
388
#ifdef _STLP_MEMBER_TEMPLATES  
 
389
  template<class _II> void insert_equal(_II __first, _II __last) {
 
390
    for ( ; __first != __last; ++__first)
 
391
      insert_equal(*__first);
 
392
  }
 
393
  template<class _II> void insert_unique(_II __first, _II __last) {
 
394
    for ( ; __first != __last; ++__first)
 
395
      insert_unique(*__first);
 
396
  }
 
397
#else /* _STLP_MEMBER_TEMPLATES */
 
398
  void insert_unique(const_iterator __first, const_iterator __last) {
 
399
    for ( ; __first != __last; ++__first)
 
400
      insert_unique(*__first);
 
401
  }
 
402
  void insert_unique(const value_type* __first, const value_type* __last) {
 
403
    for ( ; __first != __last; ++__first)
 
404
      insert_unique(*__first);
 
405
  }
 
406
  void insert_equal(const_iterator __first, const_iterator __last) {
 
407
    for ( ; __first != __last; ++__first)
 
408
      insert_equal(*__first);
 
409
  }
 
410
  void insert_equal(const value_type* __first, const value_type* __last) {
 
411
    for ( ; __first != __last; ++__first)
 
412
      insert_equal(*__first);
 
413
  }
 
414
#endif /* _STLP_MEMBER_TEMPLATES */
 
415
 
 
416
  void erase(iterator __position) {
 
417
    _Link_type __y = 
 
418
      (_Link_type) _Rb_global_inst::_Rebalance_for_erase(__position._M_node,
 
419
                                                         this->_M_header._M_data->_M_parent,
 
420
                                                         this->_M_header._M_data->_M_left,
 
421
                                                         this->_M_header._M_data->_M_right);
 
422
    _STLP_STD::_Destroy(&__y->_M_value_field);
 
423
    this->_M_header.deallocate(__y,1);
 
424
    --_M_node_count;
 
425
  }
 
426
  
 
427
  size_type erase(const key_type& __x) {
 
428
    pair<iterator,iterator> __p = equal_range(__x);
 
429
    size_type __n = distance(__p.first, __p.second);
 
430
    erase(__p.first, __p.second);
 
431
    return __n;
 
432
  }
 
433
  
 
434
  void erase(iterator __first, iterator __last) {
 
435
    if (__first == begin() && __last == end())
 
436
      clear();
 
437
    else
 
438
      while (__first != __last) erase(__first++);
 
439
  }
 
440
 
 
441
  void erase(const key_type* __first, const key_type* __last) {
 
442
    while (__first != __last) erase(*__first++);
 
443
  }
 
444
 
 
445
  void clear() {
 
446
    if (_M_node_count != 0) {
 
447
      _M_erase(_M_root());
 
448
      _M_leftmost() = this->_M_header._M_data;
 
449
      _M_root() = 0;
 
450
      _M_rightmost() = this->_M_header._M_data;
 
451
      _M_node_count = 0;
 
452
    }
 
453
  }      
 
454
 
 
455
public:
 
456
                                // set operations:
 
457
# if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS ) && !defined(__MRC__) && !(defined(__SC__) && !defined(__DMC__))
 
458
  template <class _KT> iterator find(const _KT& __x) { return iterator(_M_find(__x)); }
 
459
  template <class _KT> const_iterator find(const _KT& __x) const { return const_iterator(_M_find(__x)); }
 
460
private:
 
461
  template <class _KT> _Rb_tree_node<_Value>* _M_find(const _KT& __k) const
 
462
# else
 
463
  iterator find(const key_type& __x) { return iterator(_M_find(__x)); }
 
464
  const_iterator find(const key_type& __x) const { return const_iterator(_M_find(__x)); }
 
465
private:
 
466
  _Rb_tree_node<_Value>* _M_find(const key_type& __k) const
 
467
# endif
 
468
  {
 
469
    _Link_type __y = this->_M_header._M_data;      // Last node which is not less than __k. 
 
470
    _Link_type __x = _M_root();      // Current node. 
 
471
    
 
472
    while (__x != 0) 
 
473
      if (!_M_key_compare(_S_key(__x), __k))
 
474
        __y = __x, __x = _S_left(__x);
 
475
      else
 
476
        __x = _S_right(__x);
 
477
    if (__y == this->_M_header._M_data || _M_key_compare(__k, _S_key(__y)))
 
478
      __y = this->_M_header._M_data;
 
479
    return __y;
 
480
  }
 
481
  
 
482
  _Link_type _M_lower_bound(const key_type& __k) const {
 
483
    _Link_type __y = this->_M_header._M_data; /* Last node which is not less than __k. */
 
484
    _Link_type __x = _M_root(); /* Current node. */
 
485
    
 
486
    while (__x != 0) 
 
487
      if (!_M_key_compare(_S_key(__x), __k))
 
488
        __y = __x, __x = _S_left(__x);
 
489
      else
 
490
        __x = _S_right(__x);
 
491
    
 
492
    return __y;
 
493
  }
 
494
 
 
495
  _Link_type _M_upper_bound(const key_type& __k) const {
 
496
    _Link_type __y = this->_M_header._M_data; /* Last node which is greater than __k. */
 
497
    _Link_type __x = _M_root(); /* Current node. */
 
498
    
 
499
    while (__x != 0) 
 
500
      if (_M_key_compare(__k, _S_key(__x)))
 
501
        __y = __x, __x = _S_left(__x);
 
502
      else
 
503
        __x = _S_right(__x);
 
504
    
 
505
    return __y;
 
506
  }
 
507
  
 
508
public:  
 
509
  size_type count(const key_type& __x) const;
 
510
  iterator lower_bound(const key_type& __x) { return iterator(_M_lower_bound(__x)); }
 
511
  const_iterator lower_bound(const key_type& __x) const { return const_iterator(_M_lower_bound(__x)); }
 
512
  iterator upper_bound(const key_type& __x) { return iterator(_M_upper_bound(__x)); }
 
513
  const_iterator upper_bound(const key_type& __x) const { return const_iterator(_M_upper_bound(__x)); }
 
514
  pair<iterator,iterator> equal_range(const key_type& __x) {
 
515
    return pair<iterator, iterator>(lower_bound(__x), upper_bound(__x));
 
516
  }
 
517
  pair<const_iterator, const_iterator> equal_range(const key_type& __x) const {
 
518
    return pair<const_iterator,const_iterator>(lower_bound(__x),
 
519
                                               upper_bound(__x));
 
520
  }
 
521
 
 
522
public:
 
523
                                // Debugging.
 
524
  bool __rb_verify() const;
 
525
};
 
526
 
 
527
template <class _Key, class _Value, class _KeyOfValue, 
 
528
          class _Compare, class _Alloc> inline bool _STLP_CALL 
 
529
operator==(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
 
530
           const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
 
531
{
 
532
  return __x.size() == __y.size() && equal(__x.begin(), __x.end(), __y.begin());
 
533
}
 
534
 
 
535
template <class _Key, class _Value, class _KeyOfValue, 
 
536
          class _Compare, class _Alloc> inline bool _STLP_CALL 
 
537
operator<(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
 
538
          const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
 
539
{
 
540
  return lexicographical_compare(__x.begin(), __x.end(), 
 
541
                                 __y.begin(), __y.end());
 
542
}
 
543
 
 
544
#ifdef _STLP_USE_SEPARATE_RELOPS_NAMESPACE
 
545
 
 
546
template <class _Key, class _Value, class _KeyOfValue, 
 
547
          class _Compare, class _Alloc> inline bool _STLP_CALL 
 
548
operator!=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
 
549
           const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
 
550
  return !(__x == __y);
 
551
}
 
552
 
 
553
template <class _Key, class _Value, class _KeyOfValue, 
 
554
          class _Compare, class _Alloc> inline bool _STLP_CALL 
 
555
operator>(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
 
556
          const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
 
557
  return __y < __x;
 
558
}
 
559
 
 
560
template <class _Key, class _Value, class _KeyOfValue, 
 
561
          class _Compare, class _Alloc> inline bool _STLP_CALL 
 
562
operator<=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
 
563
           const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
 
564
  return !(__y < __x);
 
565
}
 
566
 
 
567
template <class _Key, class _Value, class _KeyOfValue, 
 
568
          class _Compare, class _Alloc> inline bool _STLP_CALL 
 
569
operator>=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
 
570
           const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y) {
 
571
  return !(__x < __y);
 
572
}
 
573
 
 
574
#endif /* _STLP_USE_SEPARATE_RELOPS_NAMESPACE */
 
575
 
 
576
#ifdef _STLP_FUNCTION_TMPL_PARTIAL_ORDER
 
577
 
 
578
template <class _Key, class _Value, class _KeyOfValue, 
 
579
          class _Compare, class _Alloc> inline void _STLP_CALL 
 
580
swap(_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x, 
 
581
     _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __y)
 
582
{
 
583
  __x.swap(__y);
 
584
}
 
585
 
 
586
#endif /* _STLP_FUNCTION_TMPL_PARTIAL_ORDER */
 
587
         
 
588
_STLP_END_NAMESPACE
 
589
 
 
590
# if !defined (_STLP_LINK_TIME_INSTANTIATION)
 
591
#  include <stl/_tree.c> 
 
592
# endif
 
593
 
 
594
# undef _Rb_tree
 
595
 
 
596
#if defined (_STLP_DEBUG)
 
597
# include <stl/debug/_tree.h> 
 
598
#endif
 
599
 
 
600
_STLP_BEGIN_NAMESPACE
 
601
// Class rb_tree is not part of the C++ standard.  It is provided for
 
602
// compatibility with the HP STL.
 
603
 
 
604
template <class _Key, class _Value, class _KeyOfValue, class _Compare,
 
605
          _STLP_DEFAULT_ALLOCATOR_SELECT(_Value) > struct rb_tree : public _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> {
 
606
  typedef _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> _Base;
 
607
  typedef typename _Base::allocator_type allocator_type;
 
608
 
 
609
  rb_tree()
 
610
     : _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>(_Compare(), allocator_type()) {}
 
611
  rb_tree(const _Compare& __comp,
 
612
          const allocator_type& __a = allocator_type())
 
613
    : _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>(__comp, __a) {} 
 
614
  ~rb_tree() {}
 
615
};
 
616
_STLP_END_NAMESPACE
 
617
 
 
618
#endif /* _STLP_INTERNAL_TREE_H */
 
619
 
 
620
// Local Variables:
 
621
// mode:C++
 
622
// End: