author | William Roberts <williamr@symbian.org> |
Wed, 31 Mar 2010 12:33:34 +0100 | |
branch | Symbian3 |
changeset 4 | 837f303aceeb |
permissions | -rw-r--r-- |
4
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
1 |
/* |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
2 |
* |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
3 |
* |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
4 |
* Copyright (c) 1994 |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
5 |
* Hewlett-Packard Company |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
6 |
* |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
7 |
* Copyright (c) 1996,1997 |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
8 |
* Silicon Graphics Computer Systems, Inc. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
9 |
* |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
10 |
* Copyright (c) 1997 |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
11 |
* Moscow Center for SPARC Technology |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
12 |
* |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
13 |
* Copyright (c) 1999 |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
14 |
* Boris Fomitchev |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
15 |
* |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
16 |
* This material is provided "as is", with absolutely no warranty expressed |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
17 |
* or implied. Any use is at your own risk. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
18 |
* |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
19 |
* Permission to use or copy this software for any purpose is hereby granted |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
20 |
* without fee, provided the above notices are retained on all copies. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
21 |
* Permission to modify the code and to distribute modified code is granted, |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
22 |
* provided the above notices are retained, and a notice that the code was |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
23 |
* modified is included with the above copyright notice. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
24 |
* |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
25 |
* Modified CRP 7/10/00 for improved conformance / efficiency on insert_unique / |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
26 |
* insert_equal with valid hint -- efficiency is improved all around, and it is |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
27 |
* should now be standard conforming for complexity on insert point immediately |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
28 |
* after hint (amortized constant time). |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
29 |
* |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
30 |
*/ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
31 |
#ifndef _STLP_TREE_C |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
32 |
#define _STLP_TREE_C |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
33 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
34 |
#ifndef _STLP_INTERNAL_TREE_H |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
35 |
# include <stl/_tree.h> |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
36 |
#endif |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
37 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
38 |
// fbp: these defines are for outline methods definitions. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
39 |
// needed for definitions to be portable. Should not be used in method bodies. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
40 |
# if defined ( _STLP_NESTED_TYPE_PARAM_BUG ) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
41 |
# define __iterator__ _Rb_tree_iterator<_Value, _Nonconst_traits<_Value> > |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
42 |
# define __size_type__ size_t |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
43 |
# define iterator __iterator__ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
44 |
# else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
45 |
# define __iterator__ _STLP_TYPENAME_ON_RETURN_TYPE _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>::iterator |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
46 |
# define __size_type__ _STLP_TYPENAME_ON_RETURN_TYPE _Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc>::size_type |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
47 |
# endif |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
48 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
49 |
#if defined ( _STLP_DEBUG) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
50 |
# define _Rb_tree __WORKAROUND_DBG_RENAME(Rb_tree) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
51 |
#endif |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
52 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
53 |
_STLP_BEGIN_NAMESPACE |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
54 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
55 |
# if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
56 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
57 |
template <class _Dummy> void _STLP_CALL |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
58 |
_Rb_global<_Dummy>::_Rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
59 |
{ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
60 |
_Rb_tree_node_base* __y = __x->_M_right; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
61 |
__x->_M_right = __y->_M_left; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
62 |
if (__y->_M_left !=0) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
63 |
__y->_M_left->_M_parent = __x; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
64 |
__y->_M_parent = __x->_M_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
65 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
66 |
if (__x == __root) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
67 |
__root = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
68 |
else if (__x == __x->_M_parent->_M_left) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
69 |
__x->_M_parent->_M_left = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
70 |
else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
71 |
__x->_M_parent->_M_right = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
72 |
__y->_M_left = __x; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
73 |
__x->_M_parent = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
74 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
75 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
76 |
template <class _Dummy> void _STLP_CALL |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
77 |
_Rb_global<_Dummy>::_Rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
78 |
{ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
79 |
_Rb_tree_node_base* __y = __x->_M_left; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
80 |
__x->_M_left = __y->_M_right; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
81 |
if (__y->_M_right != 0) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
82 |
__y->_M_right->_M_parent = __x; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
83 |
__y->_M_parent = __x->_M_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
84 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
85 |
if (__x == __root) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
86 |
__root = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
87 |
else if (__x == __x->_M_parent->_M_right) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
88 |
__x->_M_parent->_M_right = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
89 |
else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
90 |
__x->_M_parent->_M_left = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
91 |
__y->_M_right = __x; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
92 |
__x->_M_parent = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
93 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
94 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
95 |
template <class _Dummy> void _STLP_CALL |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
96 |
_Rb_global<_Dummy>::_Rebalance(_Rb_tree_node_base* __x, |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
97 |
_Rb_tree_node_base*& __root) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
98 |
{ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
99 |
__x->_M_color = _S_rb_tree_red; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
100 |
while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
101 |
if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
102 |
_Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
103 |
if (__y && __y->_M_color == _S_rb_tree_red) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
104 |
__x->_M_parent->_M_color = _S_rb_tree_black; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
105 |
__y->_M_color = _S_rb_tree_black; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
106 |
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
107 |
__x = __x->_M_parent->_M_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
108 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
109 |
else { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
110 |
if (__x == __x->_M_parent->_M_right) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
111 |
__x = __x->_M_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
112 |
_Rotate_left(__x, __root); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
113 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
114 |
__x->_M_parent->_M_color = _S_rb_tree_black; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
115 |
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
116 |
_Rotate_right(__x->_M_parent->_M_parent, __root); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
117 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
118 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
119 |
else { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
120 |
_Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
121 |
if (__y && __y->_M_color == _S_rb_tree_red) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
122 |
__x->_M_parent->_M_color = _S_rb_tree_black; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
123 |
__y->_M_color = _S_rb_tree_black; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
124 |
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
125 |
__x = __x->_M_parent->_M_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
126 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
127 |
else { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
128 |
if (__x == __x->_M_parent->_M_left) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
129 |
__x = __x->_M_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
130 |
_Rotate_right(__x, __root); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
131 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
132 |
__x->_M_parent->_M_color = _S_rb_tree_black; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
133 |
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
134 |
_Rotate_left(__x->_M_parent->_M_parent, __root); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
135 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
136 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
137 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
138 |
__root->_M_color = _S_rb_tree_black; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
139 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
140 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
141 |
template <class _Dummy> _Rb_tree_node_base* _STLP_CALL |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
142 |
_Rb_global<_Dummy>::_Rebalance_for_erase(_Rb_tree_node_base* __z, |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
143 |
_Rb_tree_node_base*& __root, |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
144 |
_Rb_tree_node_base*& __leftmost, |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
145 |
_Rb_tree_node_base*& __rightmost) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
146 |
{ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
147 |
_Rb_tree_node_base* __y = __z; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
148 |
_Rb_tree_node_base* __x = 0; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
149 |
_Rb_tree_node_base* __x_parent = 0; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
150 |
if (__y->_M_left == 0) // __z has at most one non-null child. y == z. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
151 |
__x = __y->_M_right; // __x might be null. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
152 |
else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
153 |
if (__y->_M_right == 0) // __z has exactly one non-null child. y == z. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
154 |
__x = __y->_M_left; // __x is not null. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
155 |
else { // __z has two non-null children. Set __y to |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
156 |
__y = __y->_M_right; // __z's successor. __x might be null. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
157 |
while (__y->_M_left != 0) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
158 |
__y = __y->_M_left; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
159 |
__x = __y->_M_right; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
160 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
161 |
if (__y != __z) { // relink y in place of z. y is z's successor |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
162 |
__z->_M_left->_M_parent = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
163 |
__y->_M_left = __z->_M_left; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
164 |
if (__y != __z->_M_right) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
165 |
__x_parent = __y->_M_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
166 |
if (__x) __x->_M_parent = __y->_M_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
167 |
__y->_M_parent->_M_left = __x; // __y must be a child of _M_left |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
168 |
__y->_M_right = __z->_M_right; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
169 |
__z->_M_right->_M_parent = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
170 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
171 |
else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
172 |
__x_parent = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
173 |
if (__root == __z) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
174 |
__root = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
175 |
else if (__z->_M_parent->_M_left == __z) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
176 |
__z->_M_parent->_M_left = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
177 |
else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
178 |
__z->_M_parent->_M_right = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
179 |
__y->_M_parent = __z->_M_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
180 |
_STLP_STD::swap(__y->_M_color, __z->_M_color); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
181 |
__y = __z; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
182 |
// __y now points to node to be actually deleted |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
183 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
184 |
else { // __y == __z |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
185 |
__x_parent = __y->_M_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
186 |
if (__x) __x->_M_parent = __y->_M_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
187 |
if (__root == __z) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
188 |
__root = __x; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
189 |
else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
190 |
if (__z->_M_parent->_M_left == __z) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
191 |
__z->_M_parent->_M_left = __x; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
192 |
else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
193 |
__z->_M_parent->_M_right = __x; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
194 |
if (__leftmost == __z) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
195 |
if (__z->_M_right == 0) // __z->_M_left must be null also |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
196 |
__leftmost = __z->_M_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
197 |
// makes __leftmost == _M_header if __z == __root |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
198 |
else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
199 |
__leftmost = _Rb_tree_node_base::_S_minimum(__x); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
200 |
if (__rightmost == __z) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
201 |
if (__z->_M_left == 0) // __z->_M_right must be null also |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
202 |
__rightmost = __z->_M_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
203 |
// makes __rightmost == _M_header if __z == __root |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
204 |
else // __x == __z->_M_left |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
205 |
__rightmost = _Rb_tree_node_base::_S_maximum(__x); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
206 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
207 |
if (__y->_M_color != _S_rb_tree_red) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
208 |
while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black)) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
209 |
if (__x == __x_parent->_M_left) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
210 |
_Rb_tree_node_base* __w = __x_parent->_M_right; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
211 |
if (__w->_M_color == _S_rb_tree_red) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
212 |
__w->_M_color = _S_rb_tree_black; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
213 |
__x_parent->_M_color = _S_rb_tree_red; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
214 |
_Rotate_left(__x_parent, __root); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
215 |
__w = __x_parent->_M_right; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
216 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
217 |
if ((__w->_M_left == 0 || |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
218 |
__w->_M_left->_M_color == _S_rb_tree_black) && (__w->_M_right == 0 || |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
219 |
__w->_M_right->_M_color == _S_rb_tree_black)) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
220 |
__w->_M_color = _S_rb_tree_red; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
221 |
__x = __x_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
222 |
__x_parent = __x_parent->_M_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
223 |
} else { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
224 |
if (__w->_M_right == 0 || |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
225 |
__w->_M_right->_M_color == _S_rb_tree_black) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
226 |
if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
227 |
__w->_M_color = _S_rb_tree_red; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
228 |
_Rotate_right(__w, __root); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
229 |
__w = __x_parent->_M_right; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
230 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
231 |
__w->_M_color = __x_parent->_M_color; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
232 |
__x_parent->_M_color = _S_rb_tree_black; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
233 |
if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
234 |
_Rotate_left(__x_parent, __root); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
235 |
break; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
236 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
237 |
} else { // same as above, with _M_right <-> _M_left. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
238 |
_Rb_tree_node_base* __w = __x_parent->_M_left; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
239 |
if (__w->_M_color == _S_rb_tree_red) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
240 |
__w->_M_color = _S_rb_tree_black; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
241 |
__x_parent->_M_color = _S_rb_tree_red; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
242 |
_Rotate_right(__x_parent, __root); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
243 |
__w = __x_parent->_M_left; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
244 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
245 |
if ((__w->_M_right == 0 || |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
246 |
__w->_M_right->_M_color == _S_rb_tree_black) && (__w->_M_left == 0 || |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
247 |
__w->_M_left->_M_color == _S_rb_tree_black)) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
248 |
__w->_M_color = _S_rb_tree_red; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
249 |
__x = __x_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
250 |
__x_parent = __x_parent->_M_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
251 |
} else { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
252 |
if (__w->_M_left == 0 || |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
253 |
__w->_M_left->_M_color == _S_rb_tree_black) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
254 |
if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
255 |
__w->_M_color = _S_rb_tree_red; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
256 |
_Rotate_left(__w, __root); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
257 |
__w = __x_parent->_M_left; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
258 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
259 |
__w->_M_color = __x_parent->_M_color; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
260 |
__x_parent->_M_color = _S_rb_tree_black; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
261 |
if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
262 |
_Rotate_right(__x_parent, __root); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
263 |
break; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
264 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
265 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
266 |
if (__x) __x->_M_color = _S_rb_tree_black; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
267 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
268 |
return __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
269 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
270 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
271 |
template <class _Dummy> _Rb_tree_node_base* _STLP_CALL |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
272 |
_Rb_global<_Dummy>::_M_decrement(_Rb_tree_node_base* _M_node) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
273 |
{ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
274 |
if (_M_node->_M_color == _S_rb_tree_red && _M_node->_M_parent->_M_parent == _M_node) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
275 |
_M_node = _M_node->_M_right; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
276 |
else if (_M_node->_M_left != 0) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
277 |
_Base_ptr __y = _M_node->_M_left; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
278 |
while (__y->_M_right != 0) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
279 |
__y = __y->_M_right; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
280 |
_M_node = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
281 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
282 |
else { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
283 |
_Base_ptr __y = _M_node->_M_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
284 |
while (_M_node == __y->_M_left) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
285 |
_M_node = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
286 |
__y = __y->_M_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
287 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
288 |
_M_node = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
289 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
290 |
return _M_node; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
291 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
292 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
293 |
template <class _Dummy> _Rb_tree_node_base* _STLP_CALL |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
294 |
_Rb_global<_Dummy>::_M_increment(_Rb_tree_node_base* _M_node) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
295 |
{ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
296 |
if (_M_node->_M_right != 0) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
297 |
_M_node = _M_node->_M_right; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
298 |
while (_M_node->_M_left != 0) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
299 |
_M_node = _M_node->_M_left; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
300 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
301 |
else { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
302 |
_Base_ptr __y = _M_node->_M_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
303 |
while (_M_node == __y->_M_right) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
304 |
_M_node = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
305 |
__y = __y->_M_parent; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
306 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
307 |
if (_M_node->_M_right != __y) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
308 |
_M_node = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
309 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
310 |
return _M_node; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
311 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
312 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
313 |
#endif /* defined (__BUILDING_STLPORT) || ! defined (_STLP_OWN_IOSTREAMS) */ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
314 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
315 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
316 |
template <class _Key, class _Value, class _KeyOfValue, |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
317 |
class _Compare, class _Alloc> _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::operator=(const _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>& __x) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
318 |
{ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
319 |
if (this != &__x) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
320 |
// Note that _Key may be a constant type. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
321 |
clear(); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
322 |
_M_node_count = 0; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
323 |
_M_key_compare = __x._M_key_compare; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
324 |
if (__x._M_root() == 0) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
325 |
_M_root() = 0; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
326 |
_M_leftmost() = this->_M_header._M_data; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
327 |
_M_rightmost() = this->_M_header._M_data; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
328 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
329 |
else { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
330 |
_M_root() = _M_copy(__x._M_root(), this->_M_header._M_data); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
331 |
_M_leftmost() = _S_minimum(_M_root()); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
332 |
_M_rightmost() = _S_maximum(_M_root()); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
333 |
_M_node_count = __x._M_node_count; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
334 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
335 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
336 |
return *this; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
337 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
338 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
339 |
// CRP 7/10/00 inserted argument __w_, which is another hint (meant to |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
340 |
// act like __x_ and ignore a portion of the if conditions -- specify |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
341 |
// __w_ != 0 to bypass comparison as false or __x_ != 0 to bypass |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
342 |
// comparison as true) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
343 |
template <class _Key, class _Value, class _KeyOfValue, |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
344 |
class _Compare, class _Alloc> __iterator__ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
345 |
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::_M_insert(_Rb_tree_node_base* __x_, _Rb_tree_node_base* __y_, const _Value& __v, |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
346 |
_Rb_tree_node_base* __w_) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
347 |
{ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
348 |
_Link_type __w = (_Link_type) __w_; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
349 |
_Link_type __x = (_Link_type) __x_; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
350 |
_Link_type __y = (_Link_type) __y_; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
351 |
_Link_type __z; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
352 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
353 |
if ( __y == this->_M_header._M_data || |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
354 |
( __w == 0 && // If w != 0, the remainder fails to false |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
355 |
( __x != 0 || // If x != 0, the remainder succeeds to true |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
356 |
_M_key_compare( _KeyOfValue()(__v), _S_key(__y) ) ) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
357 |
) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
358 |
) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
359 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
360 |
__z = _M_create_node(__v); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
361 |
_S_left(__y) = __z; // also makes _M_leftmost() = __z |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
362 |
// when __y == _M_header |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
363 |
if (__y == this->_M_header._M_data) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
364 |
_M_root() = __z; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
365 |
_M_rightmost() = __z; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
366 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
367 |
else if (__y == _M_leftmost()) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
368 |
_M_leftmost() = __z; // maintain _M_leftmost() pointing to min node |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
369 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
370 |
else { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
371 |
__z = _M_create_node(__v); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
372 |
_S_right(__y) = __z; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
373 |
if (__y == _M_rightmost()) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
374 |
_M_rightmost() = __z; // maintain _M_rightmost() pointing to max node |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
375 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
376 |
_S_parent(__z) = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
377 |
_S_left(__z) = 0; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
378 |
_S_right(__z) = 0; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
379 |
_Rb_global_inst::_Rebalance(__z, this->_M_header._M_data->_M_parent); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
380 |
++_M_node_count; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
381 |
return iterator(__z); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
382 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
383 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
384 |
template <class _Key, class _Value, class _KeyOfValue, |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
385 |
class _Compare, class _Alloc> __iterator__ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
386 |
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::insert_equal(const _Value& __v) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
387 |
{ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
388 |
_Link_type __y = this->_M_header._M_data; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
389 |
_Link_type __x = _M_root(); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
390 |
while (__x != 0) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
391 |
__y = __x; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
392 |
__x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ? |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
393 |
_S_left(__x) : _S_right(__x); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
394 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
395 |
return _M_insert(__x, __y, __v); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
396 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
397 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
398 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
399 |
template <class _Key, class _Value, class _KeyOfValue, |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
400 |
class _Compare, class _Alloc> pair< _Rb_tree_iterator<_Value, _Nonconst_traits<_Value> >, bool> _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::insert_unique(const _Value& __v) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
401 |
{ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
402 |
_Link_type __y = this->_M_header._M_data; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
403 |
_Link_type __x = _M_root(); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
404 |
bool __comp = true; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
405 |
while (__x != 0) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
406 |
__y = __x; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
407 |
__comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
408 |
__x = __comp ? _S_left(__x) : _S_right(__x); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
409 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
410 |
iterator __j = iterator(__y); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
411 |
if (__comp) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
412 |
if (__j == begin()) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
413 |
return pair<iterator,bool>(_M_insert(/* __x*/ __y, __y, __v), true); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
414 |
else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
415 |
--__j; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
416 |
if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v))) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
417 |
return pair<iterator,bool>(_M_insert(__x, __y, __v), true); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
418 |
return pair<iterator,bool>(__j, false); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
419 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
420 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
421 |
// Modifications CRP 7/10/00 as noted to improve conformance and |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
422 |
// efficiency. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
423 |
template <class _Key, class _Value, class _KeyOfValue, |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
424 |
class _Compare, class _Alloc> __iterator__ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
425 |
_Rb_tree<_Key, _Value, _KeyOfValue, _Compare, _Alloc> ::insert_unique(iterator __position, const _Value& __v) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
426 |
{ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
427 |
if (__position._M_node == this->_M_header._M_data->_M_left) { // begin() |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
428 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
429 |
// if the container is empty, fall back on insert_unique. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
430 |
if (size() <= 0) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
431 |
return insert_unique(__v).first; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
432 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
433 |
if ( _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node))) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
434 |
return _M_insert(__position._M_node, __position._M_node, __v); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
435 |
// first argument just needs to be non-null |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
436 |
else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
437 |
{ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
438 |
bool __comp_pos_v = _M_key_compare( _S_key(__position._M_node), _KeyOfValue()(__v) ); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
439 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
440 |
if (__comp_pos_v == false) // compare > and compare < both false so compare equal |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
441 |
return __position; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
442 |
//Below __comp_pos_v == true |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
443 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
444 |
// Standard-conformance - does the insertion point fall immediately AFTER |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
445 |
// the hint? |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
446 |
iterator __after = __position; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
447 |
++__after; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
448 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
449 |
// Check for only one member -- in that case, __position points to itself, |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
450 |
// and attempting to increment will cause an infinite loop. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
451 |
if (__after._M_node == this->_M_header._M_data) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
452 |
// Check guarantees exactly one member, so comparison was already |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
453 |
// performed and we know the result; skip repeating it in _M_insert |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
454 |
// by specifying a non-zero fourth argument. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
455 |
return _M_insert(0, __position._M_node, __v, __position._M_node); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
456 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
457 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
458 |
// All other cases: |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
459 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
460 |
// Optimization to catch insert-equivalent -- save comparison results, |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
461 |
// and we get this for free. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
462 |
if(_M_key_compare( _KeyOfValue()(__v), _S_key(__after._M_node) )) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
463 |
if (_S_right(__position._M_node) == 0) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
464 |
return _M_insert(0, __position._M_node, __v, __position._M_node); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
465 |
else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
466 |
return _M_insert(__after._M_node, __after._M_node, __v); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
467 |
} else { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
468 |
return insert_unique(__v).first; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
469 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
470 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
471 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
472 |
} else if (__position._M_node == this->_M_header._M_data) { // end() |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
473 |
if (_M_key_compare(_S_key(_M_rightmost()), _KeyOfValue()(__v))) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
474 |
// pass along to _M_insert that it can skip comparing |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
475 |
// v, Key ; since compare Key, v was true, compare v, Key must be false. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
476 |
return _M_insert(0, _M_rightmost(), __v, __position._M_node); // Last argument only needs to be non-null |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
477 |
else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
478 |
return insert_unique(__v).first; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
479 |
} else { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
480 |
iterator __before = __position; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
481 |
--__before; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
482 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
483 |
bool __comp_v_pos = _M_key_compare(_KeyOfValue()(__v), _S_key(__position._M_node)); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
484 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
485 |
if (__comp_v_pos |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
486 |
&& _M_key_compare( _S_key(__before._M_node), _KeyOfValue()(__v) )) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
487 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
488 |
if (_S_right(__before._M_node) == 0) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
489 |
return _M_insert(0, __before._M_node, __v, __before._M_node); // Last argument only needs to be non-null |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
490 |
else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
491 |
return _M_insert(__position._M_node, __position._M_node, __v); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
492 |
// first argument just needs to be non-null |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
493 |
} else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
494 |
{ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
495 |
// Does the insertion point fall immediately AFTER the hint? |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
496 |
iterator __after = __position; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
497 |
++__after; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
498 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
499 |
// Optimization to catch equivalent cases and avoid unnecessary comparisons |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
500 |
bool __comp_pos_v = !__comp_v_pos; // Stored this result earlier |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
501 |
// If the earlier comparison was true, this comparison doesn't need to be |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
502 |
// performed because it must be false. However, if the earlier comparison |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
503 |
// was false, we need to perform this one because in the equal case, both will |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
504 |
// be false. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
505 |
if (!__comp_v_pos) __comp_pos_v = _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v)); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
506 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
507 |
if ( (!__comp_v_pos) // comp_v_pos true implies comp_v_pos false |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
508 |
&& __comp_pos_v |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
509 |
&& (__after._M_node == this->_M_header._M_data || |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
510 |
_M_key_compare( _KeyOfValue()(__v), _S_key(__after._M_node) ))) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
511 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
512 |
if (_S_right(__position._M_node) == 0) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
513 |
return _M_insert(0, __position._M_node, __v, __position._M_node); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
514 |
else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
515 |
return _M_insert(__after._M_node, __after._M_node, __v); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
516 |
} else { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
517 |
// Test for equivalent case |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
518 |
if (__comp_v_pos == __comp_pos_v) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
519 |
return __position; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
520 |
else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
521 |
return insert_unique(__v).first; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
522 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
523 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
524 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
525 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
526 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
527 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
528 |
template <class _Key, class _Value, class _KeyOfValue, |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
529 |
class _Compare, class _Alloc> __iterator__ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
530 |
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::insert_equal(iterator __position, const _Value& __v) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
531 |
{ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
532 |
if (__position._M_node == this->_M_header._M_data->_M_left) { // begin() |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
533 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
534 |
// Check for zero members |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
535 |
if (size() <= 0) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
536 |
return insert_equal(__v); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
537 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
538 |
if (!_M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v))) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
539 |
return _M_insert(__position._M_node, __position._M_node, __v); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
540 |
else { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
541 |
// Check for only one member |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
542 |
if (__position._M_node->_M_left == __position._M_node) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
543 |
// Unlike insert_unique, can't avoid doing a comparison here. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
544 |
return _M_insert(0, __position._M_node, __v); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
545 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
546 |
// All other cases: |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
547 |
// Standard-conformance - does the insertion point fall immediately AFTER |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
548 |
// the hint? |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
549 |
iterator __after = __position; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
550 |
++__after; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
551 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
552 |
// Already know that compare(pos, v) must be true! |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
553 |
// Therefore, we want to know if compare(after, v) is false. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
554 |
// (i.e., we now pos < v, now we want to know if v <= after) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
555 |
// If not, invalid hint. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
556 |
if ( __after._M_node==this->_M_header._M_data || |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
557 |
!_M_key_compare( _S_key(__after._M_node), _KeyOfValue()(__v) ) ) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
558 |
if (_S_right(__position._M_node) == 0) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
559 |
return _M_insert(0, __position._M_node, __v, __position._M_node); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
560 |
else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
561 |
return _M_insert(__after._M_node, __after._M_node, __v); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
562 |
} else // Invalid hint |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
563 |
return insert_equal(__v); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
564 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
565 |
} else if (__position._M_node == this->_M_header._M_data) {// end() |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
566 |
if (!_M_key_compare(_KeyOfValue()(__v), _S_key(_M_rightmost()))) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
567 |
return _M_insert(0, _M_rightmost(), __v, __position._M_node); // Last argument only needs to be non-null |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
568 |
else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
569 |
return insert_equal(__v); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
570 |
} else { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
571 |
iterator __before = __position; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
572 |
--__before; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
573 |
// store the result of the comparison between pos and v so |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
574 |
// that we don't have to do it again later. Note that this reverses the shortcut |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
575 |
// on the if, possibly harming efficiency in comparisons; I think the harm will |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
576 |
// be negligible, and to do what I want to do (save the result of a comparison so |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
577 |
// that it can be re-used) there is no alternative. Test here is for before <= v <= pos. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
578 |
bool __comp_pos_v = _M_key_compare(_S_key(__position._M_node), _KeyOfValue()(__v)); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
579 |
if (!__comp_pos_v |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
580 |
&& !_M_key_compare(_KeyOfValue()(__v), _S_key(__before._M_node))) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
581 |
if (_S_right(__before._M_node) == 0) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
582 |
return _M_insert(0, __before._M_node, __v, __before._M_node); // Last argument only needs to be non-null |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
583 |
else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
584 |
return _M_insert(__position._M_node, __position._M_node, __v); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
585 |
} else { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
586 |
// Does the insertion point fall immediately AFTER the hint? |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
587 |
// Test for pos < v <= after |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
588 |
iterator __after = __position; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
589 |
++__after; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
590 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
591 |
if (__comp_pos_v |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
592 |
&& ( __after._M_node==this->_M_header._M_data |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
593 |
|| !_M_key_compare( _S_key(__after._M_node), _KeyOfValue()(__v) ) ) ) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
594 |
if (_S_right(__position._M_node) == 0) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
595 |
return _M_insert(0, __position._M_node, __v, __position._M_node); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
596 |
else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
597 |
return _M_insert(__after._M_node, __after._M_node, __v); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
598 |
} else // Invalid hint |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
599 |
return insert_equal(__v); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
600 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
601 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
602 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
603 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
604 |
template <class _Key, class _Value, class _KeyOfValue, class _Compare, class _Alloc> _Rb_tree_node<_Value>* |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
605 |
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::_M_copy(_Rb_tree_node<_Value>* __x, _Rb_tree_node<_Value>* __p) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
606 |
{ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
607 |
// structural copy. __x and __p must be non-null. |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
608 |
_STLP_LEAVE_VOLATILE _Link_type __top = _M_clone_node(__x); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
609 |
__top->_M_parent = __p; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
610 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
611 |
_STLP_TRY { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
612 |
if (__x->_M_right) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
613 |
__top->_M_right = _M_copy(_S_right(__x), __top); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
614 |
__p = __top; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
615 |
__x = _S_left(__x); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
616 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
617 |
while (__x != 0) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
618 |
_Link_type __y = _M_clone_node(__x); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
619 |
__p->_M_left = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
620 |
__y->_M_parent = __p; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
621 |
if (__x->_M_right) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
622 |
__y->_M_right = _M_copy(_S_right(__x), __y); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
623 |
__p = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
624 |
__x = _S_left(__x); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
625 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
626 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
627 |
_STLP_UNWIND(_M_erase(__top)); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
628 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
629 |
return __top; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
630 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
631 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
632 |
// this has to stay out-of-line : it's recursive |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
633 |
template <class _Key, class _Value, class _KeyOfValue, |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
634 |
class _Compare, class _Alloc> void |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
635 |
_Rb_tree<_Key,_Value,_KeyOfValue, |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
636 |
_Compare,_Alloc>::_M_erase(_Rb_tree_node<_Value>* __x) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
637 |
{ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
638 |
// erase without rebalancing |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
639 |
while (__x != 0) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
640 |
_M_erase(_S_right(__x)); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
641 |
_Link_type __y = _S_left(__x); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
642 |
_STLP_STD::_Destroy(&__x->_M_value_field); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
643 |
this->_M_header.deallocate(__x,1); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
644 |
__x = __y; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
645 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
646 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
647 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
648 |
template <class _Key, class _Value, class _KeyOfValue, |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
649 |
class _Compare, class _Alloc> __size_type__ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
650 |
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc> ::count(const _Key& __k) const |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
651 |
{ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
652 |
pair<const_iterator, const_iterator> __p = equal_range(__k); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
653 |
size_type __n = distance(__p.first, __p.second); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
654 |
return __n; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
655 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
656 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
657 |
inline int |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
658 |
__black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
659 |
{ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
660 |
if (__node == 0) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
661 |
return 0; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
662 |
else { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
663 |
int __bc = __node->_M_color == _S_rb_tree_black ? 1 : 0; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
664 |
if (__node == __root) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
665 |
return __bc; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
666 |
else |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
667 |
return __bc + __black_count(__node->_M_parent, __root); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
668 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
669 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
670 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
671 |
template <class _Key, class _Value, class _KeyOfValue, |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
672 |
class _Compare, class _Alloc> bool _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
673 |
{ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
674 |
if (_M_node_count == 0 || begin() == end()) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
675 |
return _M_node_count == 0 && begin() == end() && this->_M_header._M_data->_M_left == this->_M_header._M_data |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
676 |
&& this->_M_header._M_data->_M_right == this->_M_header._M_data; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
677 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
678 |
int __len = __black_count(_M_leftmost(), _M_root()); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
679 |
for (const_iterator __it = begin(); __it != end(); ++__it) { |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
680 |
_Link_type __x = (_Link_type) __it._M_node; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
681 |
_Link_type __L = _S_left(__x); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
682 |
_Link_type __R = _S_right(__x); |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
683 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
684 |
if (__x->_M_color == _S_rb_tree_red) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
685 |
if ((__L && __L->_M_color == _S_rb_tree_red) || |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
686 |
(__R && __R->_M_color == _S_rb_tree_red)) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
687 |
return false; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
688 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
689 |
if (__L && _M_key_compare(_S_key(__x), _S_key(__L))) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
690 |
return false; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
691 |
if (__R && _M_key_compare(_S_key(__R), _S_key(__x))) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
692 |
return false; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
693 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
694 |
if (!__L && !__R && __black_count(__x, _M_root()) != __len) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
695 |
return false; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
696 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
697 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
698 |
if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root())) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
699 |
return false; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
700 |
if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root())) |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
701 |
return false; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
702 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
703 |
return true; |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
704 |
} |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
705 |
_STLP_END_NAMESPACE |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
706 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
707 |
# undef __iterator__ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
708 |
# undef iterator |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
709 |
# undef __size_type__ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
710 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
711 |
#endif /* _STLP_TREE_C */ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
712 |
|
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
713 |
// Local Variables: |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
714 |
// mode:C++ |
837f303aceeb
Current Symbian^3 public API header files (from PDK 3.0.h)
William Roberts <williamr@symbian.org>
parents:
diff
changeset
|
715 |
// End: |