1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> 2 <html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"> 3 <title>oscl_tree.h Source File</title> 4 <link href="doxygen.css" rel="stylesheet" type="text/css"> 5 </head><body> 6 <!-- Generated by Doxygen 1.2.18 --> 7 <center> 8 <a class="qindex" href="index.html">Main Page</a> <a class="qindex" href="modules.html">Modules</a> <a class="qindex" href="hierarchy.html">Class Hierarchy</a> <a class="qindex" href="annotated.html">Data Structures</a> <a class="qindex" href="files.html">File List</a> <a class="qindex" href="functions.html">Data Fields</a> <a class="qindex" href="globals.html">Globals</a> </center> 9 <hr><h1>oscl_tree.h</h1><a href="oscl__tree_8h.html">Go to the documentation of this file.</a><div class="fragment"><pre>00001 <span class="comment">// -*- c++ -*-</span> 10 00002 <span class="comment">// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =</span> 11 00003 12 00004 <span class="comment">// O S C L _ T R E E</span> 13 00005 14 00006 <span class="comment">// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =</span> 15 00007 16 00018 <span class="preprocessor">#ifndef OSCL_TREE_H_INCLUDED</span> 17 00019 <span class="preprocessor"></span><span class="preprocessor">#define OSCL_TREE_H_INCLUDED</span> 18 00020 <span class="preprocessor"></span> 19 00021 <span class="preprocessor">#ifndef OSCL_DEFALLOC_H_INCLUDED</span> 20 00022 <span class="preprocessor"></span><span class="preprocessor">#include "<a class="code" href="oscl__defalloc_8h.html">oscl_defalloc.h</a>"</span> 21 00023 <span class="preprocessor">#endif</span> 22 00024 <span class="preprocessor"></span> 23 00025 <span class="preprocessor">#ifndef OSCL_BASE_H_INCLUDED</span> 24 00026 <span class="preprocessor"></span><span class="preprocessor">#include "<a class="code" href="oscl__base_8h.html">oscl_base.h</a>"</span> 25 00027 <span class="preprocessor">#endif</span> 26 00028 <span class="preprocessor"></span> 27 <a name="l00029"></a><a class="code" href="oscl__tree_8h.html#a0">00029</a> <span class="preprocessor">#define OSCL_DISABLE_WARNING_TRUNCATE_DEBUG_MESSAGE</span> 28 00030 <span class="preprocessor"></span><span class="preprocessor">#include "<a class="code" href="osclconfig__compiler__warnings_8h.html">osclconfig_compiler_warnings.h</a>"</span> 29 00031 30 00032 <span class="keyword">template</span> <<span class="keyword">class</span> T1, <span class="keyword">class</span> T2> 31 <a name="l00033"></a><a class="code" href="structOscl__Pair.html">00033</a> <span class="keyword">struct </span><a class="code" href="structOscl__Pair.html">Oscl_Pair</a> 32 00034 { 33 <a name="l00035"></a><a class="code" href="structOscl__Pair.html#m0">00035</a> T1 <a class="code" href="structOscl__Pair.html#m0">first</a>; 34 <a name="l00036"></a><a class="code" href="structOscl__Pair.html#m1">00036</a> T2 <a class="code" href="structOscl__Pair.html#m1">second</a>; 35 <a name="l00037"></a><a class="code" href="structOscl__Pair.html#a0">00037</a> <a class="code" href="structOscl__Pair.html#a0">Oscl_Pair</a>() : <a class="code" href="structOscl__Pair.html#m0">first</a>(T1()), <a class="code" href="structOscl__Pair.html#m1">second</a>(T2()) {} 36 <a name="l00038"></a><a class="code" href="structOscl__Pair.html#a1">00038</a> <a class="code" href="structOscl__Pair.html#a0">Oscl_Pair</a>(<span class="keyword">const</span> T1& a, <span class="keyword">const</span> T2& b) : <a class="code" href="structOscl__Pair.html#m0">first</a>(a), <a class="code" href="structOscl__Pair.html#m1">second</a>(b) {} 37 00039 }; 38 00040 39 00041 40 <a name="l00042"></a><a class="code" href="structOscl__Rb__Tree__Node__Base.html">00042</a> <span class="keyword">struct </span><a class="code" href="structOscl__Rb__Tree__Node__Base.html">Oscl_Rb_Tree_Node_Base</a> 41 00043 { 42 <a name="l00044"></a><a class="code" href="structOscl__Rb__Tree__Node__Base.html#s0">00044</a> <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Node__Base.html">Oscl_Rb_Tree_Node_Base</a>* <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a>; 43 <a name="l00045"></a><a class="code" href="structOscl__Rb__Tree__Node__Base.html#s4">00045</a> <span class="keyword">typedef</span> <span class="keyword">enum</span> <a class="code" href="structOscl__Rb__Tree__Node__Base.html#s4">RedBl</a> {<a class="code" href="structOscl__Rb__Tree__Node__Base.html#s4s2">red</a>, <a class="code" href="structOscl__Rb__Tree__Node__Base.html#s4s3">black</a>} <a class="code" href="structOscl__Rb__Tree__Node__Base.html#s1">color_type</a>; 44 00046 45 <a name="l00047"></a><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m0">00047</a> <a class="code" href="structOscl__Rb__Tree__Node__Base.html#s1">color_type</a> <a class="code" href="structOscl__Rb__Tree__Node__Base.html#m0">color</a>; 46 <a name="l00048"></a><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">00048</a> base_link_type <a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>; 47 <a name="l00049"></a><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">00049</a> base_link_type <a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>; 48 <a name="l00050"></a><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">00050</a> base_link_type <a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>; 49 00051 50 <a name="l00052"></a><a class="code" href="structOscl__Rb__Tree__Node__Base.html#d0">00052</a> <span class="keyword">static</span> base_link_type <a class="code" href="structOscl__Rb__Tree__Node__Base.html#d0">minimum</a>(base_link_type x) 51 00053 { 52 00054 <span class="keywordflow">if</span> (x) 53 00055 { 54 00056 <span class="keywordflow">while</span> (x-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a> != 0) x = x-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>; 55 00057 } 56 00058 <span class="keywordflow">return</span> x; 57 00059 } 58 <a name="l00060"></a><a class="code" href="structOscl__Rb__Tree__Node__Base.html#d1">00060</a> <span class="keyword">static</span> base_link_type <a class="code" href="structOscl__Rb__Tree__Node__Base.html#d1">maximum</a>(base_link_type x) 59 00061 { 60 00062 <span class="keywordflow">if</span> (x) 61 00063 { 62 00064 <span class="keywordflow">while</span> (x-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a> != 0) x = x-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>; 63 00065 } 64 00066 <span class="keywordflow">return</span> x; 65 00067 } 66 00068 }; 67 00069 68 00070 <span class="keyword">template</span> <<span class="keyword">class</span> Value> 69 <a name="l00071"></a><a class="code" href="structOscl__Rb__Tree__Node.html">00071</a> <span class="keyword">struct </span><a class="code" href="structOscl__Rb__Tree__Node.html">Oscl_Rb_Tree_Node</a> : <span class="keyword">public</span> <a class="code" href="structOscl__Rb__Tree__Node__Base.html">Oscl_Rb_Tree_Node_Base</a> 70 00072 { 71 <a name="l00073"></a><a class="code" href="structOscl__Rb__Tree__Node.html#s0">00073</a> <span class="keyword">typedef</span> Value <a class="code" href="structOscl__Rb__Tree__Node.html#s0">value_type</a>; 72 <a name="l00074"></a><a class="code" href="structOscl__Rb__Tree__Node.html#s1">00074</a> <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Node.html">Oscl_Rb_Tree_Node<Value></a>* <a class="code" href="structOscl__Rb__Tree__Node.html">link_type</a>; 73 <a name="l00075"></a><a class="code" href="structOscl__Rb__Tree__Node.html#m0">00075</a> <a class="code" href="structOscl__Rb__Tree__Node.html#s0">value_type</a> <a class="code" href="structOscl__Rb__Tree__Node.html#m0">value</a>; 74 00076 }; 75 00077 76 00078 77 00079 <span class="keyword">template</span> <<span class="keyword">class</span> Value> 78 <a name="l00080"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html">00080</a> <span class="keyword">struct </span><a class="code" href="structOscl__Rb__Tree__Iterator.html">Oscl_Rb_Tree_Iterator</a> 79 00081 { 80 <a name="l00082"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#s0">00082</a> <span class="keyword">typedef</span> Value <a class="code" href="structOscl__Rb__Tree__Iterator.html#s0">value_type</a>; 81 <a name="l00083"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#s1">00083</a> <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html#s0">value_type</a>& <a class="code" href="structOscl__Rb__Tree__Iterator.html#s1">reference</a>; 82 <a name="l00084"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#s2">00084</a> <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html#s0">value_type</a>* <a class="code" href="structOscl__Rb__Tree__Iterator.html#s2">pointer</a>; 83 <a name="l00085"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#s3">00085</a> <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html">Oscl_Rb_Tree_Iterator<Value></a> <a class="code" href="structOscl__Rb__Tree__Iterator.html">iterator</a>; 84 <a name="l00086"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#s4">00086</a> <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html">Oscl_Rb_Tree_Iterator<Value></a> <a class="code" href="structOscl__Rb__Tree__Iterator.html">self</a>; 85 <a name="l00087"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#s5">00087</a> <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Node__Base.html">Oscl_Rb_Tree_Node_Base</a>* <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a>; 86 <a name="l00088"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#s6">00088</a> <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Node.html">Oscl_Rb_Tree_Node<Value></a>* <a class="code" href="structOscl__Rb__Tree__Node.html">link_type</a>; 87 00089 88 <a name="l00090"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">00090</a> base_link_type <a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>; 89 00091 90 <a name="l00092"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a0">00092</a> <a class="code" href="structOscl__Rb__Tree__Iterator.html#a0">Oscl_Rb_Tree_Iterator</a>() {} 91 <a name="l00093"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a1">00093</a> <a class="code" href="structOscl__Rb__Tree__Iterator.html#a0">Oscl_Rb_Tree_Iterator</a>(link_type x) 92 00094 { 93 00095 node = x; 94 00096 } 95 <a name="l00097"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a2">00097</a> <a class="code" href="structOscl__Rb__Tree__Iterator.html#a0">Oscl_Rb_Tree_Iterator</a>(<span class="keyword">const</span> iterator& it) 96 00098 { 97 00099 node = it.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>; 98 00100 } 99 00101 100 <a name="l00102"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a3">00102</a> <a class="code" href="structOscl__Rb__Tree__Iterator.html#s1">reference</a> <a class="code" href="structOscl__Rb__Tree__Iterator.html#a3">operator*</a>()<span class="keyword"> const</span> 101 00103 <span class="keyword"> </span>{ 102 00104 <span class="keywordflow">return</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html#s6">link_type</a>(node)->value; 103 00105 } 104 <a name="l00106"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a4">00106</a> <a class="code" href="structOscl__Rb__Tree__Iterator.html#s2">pointer</a> <a class="code" href="structOscl__Rb__Tree__Iterator.html#a4">operator-></a>()<span class="keyword"> const</span> 105 00107 <span class="keyword"> </span>{ 106 00108 <span class="keywordflow">return</span> &(<a class="code" href="structOscl__Rb__Tree__Iterator.html#a3">operator*</a>()); 107 00109 } 108 00110 109 <a name="l00111"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a5">00111</a> <span class="keywordtype">bool</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html#a5">operator==</a>(<span class="keyword">const</span> self& x) 110 00112 { 111 00113 <span class="keywordflow">return</span> node == x.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>; 112 00114 } 113 00115 114 <a name="l00116"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a6">00116</a> <span class="keywordtype">bool</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html#a6">operator!=</a>(<span class="keyword">const</span> self& x) 115 00117 { 116 00118 <span class="keywordflow">return</span> node != x.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>; 117 00119 } 118 00120 119 <a name="l00121"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a7">00121</a> self& <a class="code" href="structOscl__Rb__Tree__Iterator.html#a7">operator++</a>() 120 00122 { 121 00123 <span class="keywordflow">if</span> (node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a> != 0) 122 00124 { 123 00125 node = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>; 124 00126 <span class="keywordflow">while</span> (node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a> != 0) 125 00127 { 126 00128 node = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>; 127 00129 } 128 00130 } 129 00131 <span class="keywordflow">else</span> 130 00132 { 131 00133 base_link_type y = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>; 132 00134 <span class="keywordflow">while</span> (node == y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>) 133 00135 { 134 00136 node = y; 135 00137 y = y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>; 136 00138 } 137 00139 <span class="keywordflow">if</span> (node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a> != y) node = y; 138 00140 } 139 00141 <span class="keywordflow">return</span> *<span class="keyword">this</span>; 140 00142 } 141 00143 142 <a name="l00144"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a8">00144</a> self <a class="code" href="structOscl__Rb__Tree__Iterator.html#a7">operator++</a>(<span class="keywordtype">int</span>) 143 00145 { 144 00146 self tmp = *<span class="keyword">this</span>; 145 00147 ++*<span class="keyword">this</span>; 146 00148 <span class="keywordflow">return</span> tmp; 147 00149 } 148 00150 149 <a name="l00151"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a9">00151</a> self& <a class="code" href="structOscl__Rb__Tree__Iterator.html#a9">operator--</a>() 150 00152 { 151 00153 <span class="keywordflow">if</span> (node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m0">color</a> == <a class="code" href="structOscl__Rb__Tree__Node__Base.html#s4s2">Oscl_Rb_Tree_Node_Base::red</a> && (node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>)->parent == node) 152 00154 { 153 00155 node = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>; <span class="comment">// return rightmost</span> 154 00156 } 155 00157 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a> != 0) 156 00158 { 157 00159 base_link_type y = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>; 158 00160 <span class="keywordflow">while</span> (y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a> != 0) 159 00161 y = y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>; 160 00162 node = y; 161 00163 } 162 00164 <span class="keywordflow">else</span> 163 00165 { 164 00166 base_link_type y = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>; 165 00167 <span class="keywordflow">while</span> (node == y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>) 166 00168 { 167 00169 node = y; 168 00170 y = y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>; 169 00171 } 170 00172 node = y; 171 00173 } 172 00174 <span class="keywordflow">return</span> *<span class="keyword">this</span>; 173 00175 } 174 00176 175 <a name="l00177"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a10">00177</a> self <a class="code" href="structOscl__Rb__Tree__Iterator.html#a9">operator--</a>(<span class="keywordtype">int</span>) 176 00178 { 177 00179 self tmp = *<span class="keyword">this</span>; 178 00180 --*<span class="keyword">this</span>; 179 00181 <span class="keywordflow">return</span> tmp; 180 00182 } 181 00183 }; 182 00184 183 00185 184 00186 <span class="keyword">template</span> <<span class="keyword">class</span> Value> 185 <a name="l00187"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">00187</a> <span class="keyword">struct </span><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">Oscl_Rb_Tree_Const_Iterator</a> 186 00188 { 187 <a name="l00189"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#s0">00189</a> <span class="keyword">typedef</span> Value <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#s0">value_type</a>; 188 <a name="l00190"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#s1">00190</a> <span class="keyword">typedef</span> <span class="keyword">const</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#s0">value_type</a>& <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#s1">reference</a>; 189 <a name="l00191"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#s2">00191</a> <span class="keyword">typedef</span> <span class="keyword">const</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#s0">value_type</a>* <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#s2">pointer</a>; 190 <a name="l00192"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#s3">00192</a> <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">Oscl_Rb_Tree_Const_Iterator<Value></a> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">const_iterator</a>; 191 <a name="l00193"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#s4">00193</a> <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">Oscl_Rb_Tree_Const_Iterator<Value></a> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">self</a>; 192 <a name="l00194"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#s5">00194</a> <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Node__Base.html">Oscl_Rb_Tree_Node_Base</a>* <a class="code" href="structOscl__Rb__Tree__Node__Base.html">base_link_type</a>; 193 <a name="l00195"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#s6">00195</a> <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Node.html">Oscl_Rb_Tree_Node<Value></a>* <a class="code" href="structOscl__Rb__Tree__Node.html">link_type</a>; 194 00196 195 <a name="l00197"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#m0">00197</a> base_link_type <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#m0">node</a>; 196 00198 197 <a name="l00199"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a0">00199</a> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a0">Oscl_Rb_Tree_Const_Iterator</a>() {} 198 <a name="l00200"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a1">00200</a> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a0">Oscl_Rb_Tree_Const_Iterator</a>(link_type x) 199 00201 { 200 00202 node = x; 201 00203 } 202 <a name="l00204"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a2">00204</a> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a0">Oscl_Rb_Tree_Const_Iterator</a>(<span class="keyword">const</span> const_iterator& it) 203 00205 { 204 00206 node = it.<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#m0">node</a>; 205 00207 } 206 00208 207 <a name="l00209"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a3">00209</a> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#s1">reference</a> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a3">operator*</a>()<span class="keyword"> const</span> 208 00210 <span class="keyword"> </span>{ 209 00211 <span class="keywordflow">return</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#s6">link_type</a>(node)->value; 210 00212 } 211 <a name="l00213"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a4">00213</a> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#s2">pointer</a> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a4">operator-></a>()<span class="keyword"> const</span> 212 00214 <span class="keyword"> </span>{ 213 00215 <span class="keywordflow">return</span> &(<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a3">operator*</a>()); 214 00216 } 215 00217 216 <a name="l00218"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a5">00218</a> <span class="keywordtype">bool</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a5">operator==</a>(<span class="keyword">const</span> self& x) 217 00219 { 218 00220 <span class="keywordflow">return</span> node == x.<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#m0">node</a>; 219 00221 } 220 00222 221 <a name="l00223"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a6">00223</a> <span class="keywordtype">bool</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a6">operator!=</a>(<span class="keyword">const</span> self& x) 222 00224 { 223 00225 <span class="keywordflow">return</span> node != x.<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#m0">node</a>; 224 00226 } 225 00227 226 <a name="l00228"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a7">00228</a> self& <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a7">operator++</a>() 227 00229 { 228 00230 <span class="keywordflow">if</span> (node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a> != 0) 229 00231 { 230 00232 node = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>; 231 00233 <span class="keywordflow">while</span> (node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a> != 0) 232 00234 { 233 00235 node = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>; 234 00236 } 235 00237 } 236 00238 <span class="keywordflow">else</span> 237 00239 { 238 00240 base_link_type y = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>; 239 00241 <span class="keywordflow">while</span> (node == y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>) 240 00242 { 241 00243 node = y; 242 00244 y = y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>; 243 00245 } 244 00246 <span class="keywordflow">if</span> (node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a> != y) node = y; 245 00247 } 246 00248 <span class="keywordflow">return</span> *<span class="keyword">this</span>; 247 00249 } 248 00250 249 <a name="l00251"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a8">00251</a> self <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a7">operator++</a>(<span class="keywordtype">int</span>) 250 00252 { 251 00253 self tmp = *<span class="keyword">this</span>; 252 00254 ++*<span class="keyword">this</span>; 253 00255 <span class="keywordflow">return</span> tmp; 254 00256 } 255 00257 256 <a name="l00258"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a9">00258</a> self& <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a9">operator--</a>() 257 00259 { 258 00260 <span class="keywordflow">if</span> (node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m0">color</a> == <a class="code" href="structOscl__Rb__Tree__Node__Base.html#s4s2">Oscl_Rb_Tree_Node_Base::red</a> && (node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>)->parent == node) 259 00261 { 260 00262 node = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>; <span class="comment">// return rightmost</span> 261 00263 } 262 00264 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a> != 0) 263 00265 { 264 00266 base_link_type y = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>; 265 00267 <span class="keywordflow">while</span> (y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a> != 0) 266 00268 y = y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>; 267 00269 node = y; 268 00270 } 269 00271 <span class="keywordflow">else</span> 270 00272 { 271 00273 base_link_type y = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>; 272 00274 <span class="keywordflow">while</span> (node == y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>) 273 00275 { 274 00276 node = y; 275 00277 y = y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>; 276 00278 } 277 00279 node = y; 278 00280 } 279 00281 <span class="keywordflow">return</span> *<span class="keyword">this</span>; 280 00282 } 281 00283 282 <a name="l00284"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a10">00284</a> self <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a9">operator--</a>(<span class="keywordtype">int</span>) 283 00285 { 284 00286 self tmp = *<span class="keyword">this</span>; 285 00287 --*<span class="keyword">this</span>; 286 00288 <span class="keywordflow">return</span> tmp; 287 00289 } 288 00290 }; 289 00291 290 00292 291 <a name="l00293"></a><a class="code" href="classOscl__Rb__Tree__Base.html">00293</a> <span class="keyword">class </span><a class="code" href="classOscl__Rb__Tree__Base.html">Oscl_Rb_Tree_Base</a> 292 00294 { 293 00295 294 00296 <span class="keyword">public</span>: 295 <a name="l00297"></a><a class="code" href="classOscl__Rb__Tree__Base.html#s0">00297</a> <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Node__Base.html">Oscl_Rb_Tree_Node_Base::base_link_type</a> <a class="code" href="classOscl__Rb__Tree__Base.html#s0">base_link_type</a>; 296 00298 297 00299 OSCL_IMPORT_REF <span class="keywordtype">void</span> <a class="code" href="classOscl__Rb__Tree__Base.html#a0">rotate_left</a>(base_link_type x, base_link_type& root); 298 00300 OSCL_IMPORT_REF <span class="keywordtype">void</span> <a class="code" href="classOscl__Rb__Tree__Base.html#a1">rotate_right</a>(base_link_type x, base_link_type& root); 299 00301 OSCL_IMPORT_REF <span class="keywordtype">void</span> <a class="code" href="classOscl__Rb__Tree__Base.html#a2">rebalance</a>(base_link_type x, base_link_type& root); 300 00302 OSCL_IMPORT_REF base_link_type <a class="code" href="classOscl__Rb__Tree__Base.html#a3">rebalance_for_erase</a>(base_link_type z, 301 00303 base_link_type& root, 302 00304 base_link_type& leftmost, 303 00305 base_link_type& rightmost); 304 00306 }; 305 00307 306 00308 307 00309 <span class="keyword">template</span> <<span class="keyword">class</span> Key, <span class="keyword">class</span> Value, <span class="keyword">class</span> KeyOfValue, <span class="keyword">class</span> Compare, <span class="keyword">class</span> Alloc> 308 <a name="l00310"></a><a class="code" href="classOscl__Rb__Tree.html">00310</a> <span class="keyword">class </span><a class="code" href="classOscl__Rb__Tree.html">Oscl_Rb_Tree</a> : <span class="keyword">public</span> <a class="code" href="classOscl__Rb__Tree__Base.html">Oscl_Rb_Tree_Base</a> 309 00311 { 310 00312 311 00313 <span class="keyword">public</span>: 312 <a name="l00314"></a><a class="code" href="classOscl__Rb__Tree.html#s0">00314</a> <span class="keyword">typedef</span> Key <a class="code" href="classOscl__Rb__Tree.html#s0">key_type</a>; 313 <a name="l00315"></a><a class="code" href="classOscl__Rb__Tree.html#s1">00315</a> <span class="keyword">typedef</span> Value <a class="code" href="classOscl__Rb__Tree.html#s1">value_type</a>; 314 <a name="l00316"></a><a class="code" href="classOscl__Rb__Tree.html#s2">00316</a> <span class="keyword">typedef</span> <a class="code" href="classOscl__Rb__Tree.html#s1">value_type</a>* <a class="code" href="classOscl__Rb__Tree.html#s2">pointer</a>; 315 <a name="l00317"></a><a class="code" href="classOscl__Rb__Tree.html#s3">00317</a> <span class="keyword">typedef</span> <span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#s1">value_type</a>* <a class="code" href="classOscl__Rb__Tree.html#s3">const_pointer</a>; 316 <a name="l00318"></a><a class="code" href="classOscl__Rb__Tree.html#s4">00318</a> <span class="keyword">typedef</span> <a class="code" href="classOscl__Rb__Tree.html#s1">value_type</a>& <a class="code" href="classOscl__Rb__Tree.html#s4">reference</a>; 317 <a name="l00319"></a><a class="code" href="classOscl__Rb__Tree.html#s5">00319</a> <span class="keyword">typedef</span> <span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#s1">value_type</a>& <a class="code" href="classOscl__Rb__Tree.html#s5">const_reference</a>; 318 <a name="l00320"></a><a class="code" href="classOscl__Rb__Tree.html#s6">00320</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="structOscl__Rb__Tree__Node.html">Oscl_Rb_Tree_Node<Value></a><a class="code" href="structOscl__Rb__Tree__Node.html">::link_type</a> <a class="code" href="structOscl__Rb__Tree__Node.html">link_type</a>; 319 <a name="l00321"></a><a class="code" href="classOscl__Rb__Tree.html#s7">00321</a> <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html">Oscl_Rb_Tree_Iterator<value_type></a> <a class="code" href="structOscl__Rb__Tree__Iterator.html">iterator</a>; 320 <a name="l00322"></a><a class="code" href="classOscl__Rb__Tree.html#s8">00322</a> <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">Oscl_Rb_Tree_Const_Iterator<value_type></a> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">const_iterator</a>; 321 <a name="l00323"></a><a class="code" href="classOscl__Rb__Tree.html#s9">00323</a> <span class="keyword">typedef</span> uint32 <a class="code" href="classOscl__Rb__Tree.html#s9">size_type</a>; 322 <a name="l00324"></a><a class="code" href="classOscl__Rb__Tree.html#s10">00324</a> <span class="keyword">typedef</span> int32 <a class="code" href="classOscl__Rb__Tree.html#s10">difference_type</a>; 323 00325 <span class="keyword">private</span>: 324 00326 <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="structOscl__Rb__Tree__Node.html">Oscl_Rb_Tree_Node<Value></a><a class="code" href="structOscl__Rb__Tree__Node.html">::color_type</a> <a class="code" href="structOscl__Rb__Tree__Node.html">color_type</a>; 325 00327 <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Node.html">Oscl_Rb_Tree_Node<Value></a> <a class="code" href="structOscl__Rb__Tree__Node.html">node_type</a>; 326 00328 327 00329 <span class="keyword">private</span>: 328 00330 link_type header; 329 00331 <a class="code" href="classOscl__Rb__Tree.html#s9">size_type</a> node_count; 330 00332 Compare key_compare; 331 00333 <a class="code" href="classOscl__TAlloc.html">Oscl_TAlloc<node_type, Alloc></a> node_allocator; 332 00334 333 00335 <span class="keyword">public</span>: 334 <a name="l00336"></a><a class="code" href="classOscl__Rb__Tree.html#a0">00336</a> <a class="code" href="classOscl__Rb__Tree.html#a0">Oscl_Rb_Tree</a>(<span class="keyword">const</span> Compare& comp = Compare()) 335 00337 : node_count(0), key_compare(comp) 336 00338 { 337 00339 header = get_node(); 338 00340 header-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m0">color</a> = <a class="code" href="structOscl__Rb__Tree__Node__Base.html#s4s2">Oscl_Rb_Tree_Node_Base::red</a>; 339 00341 leftmost() = header; 340 00342 rightmost() = header; 341 00343 root() = 0; 342 00344 } 343 00345 344 <a name="l00346"></a><a class="code" href="classOscl__Rb__Tree.html#a1">00346</a> <a class="code" href="classOscl__Rb__Tree.html#a0">Oscl_Rb_Tree</a>(<span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html">Oscl_Rb_Tree<Key, Value, KeyOfValue, Compare, Alloc></a>& x) 345 00347 : node_count(0), key_compare(x.key_compare) 346 00348 { 347 00349 header = get_node(); 348 00350 header-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m0">color</a> = <a class="code" href="structOscl__Rb__Tree__Node__Base.html#s4s2">Oscl_Rb_Tree_Node_Base::red</a>; 349 00351 <span class="keywordflow">if</span> (x.root() == 0) 350 00352 { 351 00353 leftmost() = header; 352 00354 rightmost() = header; 353 00355 root() = 0; 354 00356 } 355 00357 <span class="keywordflow">else</span> 356 00358 { 357 00359 root() = copy(x.root(), header); 358 00360 leftmost() = minimum(root()); 359 00361 rightmost() = maximum(root()); 360 00362 } 361 00363 node_count = x.node_count; 362 00364 } 363 00365 364 <a name="l00366"></a><a class="code" href="classOscl__Rb__Tree.html#a2">00366</a> <a class="code" href="classOscl__Rb__Tree.html#a2">~Oscl_Rb_Tree</a>() 365 00367 { 366 00368 <a class="code" href="classOscl__Rb__Tree.html#a19">clear</a>(); 367 00369 release_node(header); 368 00370 } 369 00371 370 00372 <a class="code" href="classOscl__Rb__Tree.html">Oscl_Rb_Tree<Key, Value, KeyOfValue, Compare, Alloc></a>& 371 <a name="l00373"></a><a class="code" href="classOscl__Rb__Tree.html#a3">00373</a> <a class="code" href="classOscl__Rb__Tree.html#a3">operator=</a>(<span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html">Oscl_Rb_Tree<Key, Value, KeyOfValue, Compare, Alloc></a>& x) 372 00374 { 373 00375 <span class="keywordflow">if</span> (<span class="keyword">this</span> != &x) 374 00376 { 375 00377 <a class="code" href="classOscl__Rb__Tree.html#a19">clear</a>(); 376 00378 node_count = 0; 377 00379 key_compare = x.<a class="code" href="classOscl__Rb__Tree.html#o2">key_compare</a>; 378 00380 379 00381 <span class="keywordflow">if</span> (x.<a class="code" href="classOscl__Rb__Tree.html#c0">root</a>() == 0) 380 00382 { 381 00383 root() = 0; 382 00384 leftmost() = header; 383 00385 rightmost() = header; 384 00386 } 385 00387 <span class="keywordflow">else</span> 386 00388 { 387 00389 root() = copy(x.<a class="code" href="classOscl__Rb__Tree.html#c0">root</a>(), header); 388 00390 leftmost() = minimum(root()); 389 00391 rightmost() = maximum(root()); 390 00392 node_count = x.<a class="code" href="classOscl__Rb__Tree.html#o1">node_count</a>; 391 00393 } 392 00394 } 393 00395 <span class="keywordflow">return</span> *<span class="keyword">this</span>; 394 00396 } 395 00397 396 00398 <span class="keyword">public</span>: 397 <a name="l00399"></a><a class="code" href="classOscl__Rb__Tree.html#a4">00399</a> iterator <a class="code" href="classOscl__Rb__Tree.html#a4">begin</a>() 398 00400 { 399 00401 <span class="keywordflow">return</span> leftmost(); 400 00402 } 401 <a name="l00403"></a><a class="code" href="classOscl__Rb__Tree.html#a5">00403</a> const_iterator <a class="code" href="classOscl__Rb__Tree.html#a4">begin</a>()<span class="keyword"> const</span> 402 00404 <span class="keyword"> </span>{ 403 00405 <span class="keywordflow">return</span> leftmost(); 404 00406 } 405 <a name="l00407"></a><a class="code" href="classOscl__Rb__Tree.html#a6">00407</a> iterator <a class="code" href="classOscl__Rb__Tree.html#a6">end</a>() 406 00408 { 407 00409 <span class="keywordflow">return</span> header; 408 00410 } 409 <a name="l00411"></a><a class="code" href="classOscl__Rb__Tree.html#a7">00411</a> const_iterator <a class="code" href="classOscl__Rb__Tree.html#a6">end</a>()<span class="keyword"> const</span> 410 00412 <span class="keyword"> </span>{ 411 00413 <span class="keywordflow">return</span> header; 412 00414 } 413 <a name="l00415"></a><a class="code" href="classOscl__Rb__Tree.html#a8">00415</a> <span class="keywordtype">bool</span> <a class="code" href="classOscl__Rb__Tree.html#a8">empty</a>()<span class="keyword"> const</span> 414 00416 <span class="keyword"> </span>{ 415 00417 <span class="keywordflow">return</span> node_count == 0; 416 00418 } 417 <a name="l00419"></a><a class="code" href="classOscl__Rb__Tree.html#a9">00419</a> <a class="code" href="classOscl__Rb__Tree.html#s9">size_type</a> <a class="code" href="classOscl__Rb__Tree.html#a9">size</a>()<span class="keyword"> const</span> 418 00420 <span class="keyword"> </span>{ 419 00421 <span class="keywordflow">return</span> node_count; 420 00422 } 421 <a name="l00423"></a><a class="code" href="classOscl__Rb__Tree.html#a10">00423</a> <a class="code" href="classOscl__Rb__Tree.html#s9">size_type</a> <a class="code" href="classOscl__Rb__Tree.html#a10">max_size</a>()<span class="keyword"> const</span> 422 00424 <span class="keyword"> </span>{ 423 00425 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#s9">size_type</a>(-1); 424 00426 } 425 00427 426 <a name="l00428"></a><a class="code" href="classOscl__Rb__Tree.html#a11">00428</a> <a class="code" href="structOscl__Pair.html">Oscl_Pair<iterator, bool></a> <a class="code" href="classOscl__Rb__Tree.html#a11">insert_unique</a>(<span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#s1">value_type</a>& v) 427 00429 { 428 00430 link_type y = header; 429 00431 link_type x = root(); 430 00432 <span class="keywordtype">bool</span> comp = <span class="keyword">true</span>; 431 00433 <span class="keywordflow">while</span> (x != 0) 432 00434 { 433 00435 y = x; 434 00436 comp = key_compare(KeyOfValue()(v), key(x)); 435 00437 x = comp ? left(x) : right(x); 436 00438 } 437 00439 iterator j = <a class="code" href="classOscl__Rb__Tree.html#s7">iterator</a>(y); 438 00440 <span class="keywordflow">if</span> (comp) 439 00441 { 440 00442 <span class="keywordflow">if</span> (j == <a class="code" href="classOscl__Rb__Tree.html#a4">begin</a>()) 441 00443 <span class="keywordflow">return</span> <a class="code" href="structOscl__Pair.html">Oscl_Pair<iterator, bool></a>(insert(x, y, v), <span class="keyword">true</span>); 442 00444 <span class="keywordflow">else</span> 443 00445 --j; 444 00446 } 445 00447 <span class="keywordflow">if</span> (key_compare(key(j.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>), KeyOfValue()(v))) 446 00448 <span class="keywordflow">return</span> <a class="code" href="structOscl__Pair.html">Oscl_Pair<iterator, bool></a>(insert(x, y, v), <span class="keyword">true</span>); 447 00449 448 00450 <span class="keywordflow">return</span> <a class="code" href="structOscl__Pair.html">Oscl_Pair<iterator, bool></a>(j, <span class="keyword">false</span>); 449 00451 } 450 00452 451 <a name="l00453"></a><a class="code" href="classOscl__Rb__Tree.html#a12">00453</a> iterator <a class="code" href="classOscl__Rb__Tree.html#a11">insert_unique</a>(iterator position, <span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#s1">value_type</a>& v) 452 00454 { 453 00455 <span class="keywordflow">if</span> (position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a> == header-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>) <span class="comment">// begin()</span> 454 00456 { 455 00457 <span class="keywordflow">if</span> (<a class="code" href="classOscl__Rb__Tree.html#a9">size</a>() > 0 && key_compare(KeyOfValue()(v), key(position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>))) 456 00458 <span class="keywordflow">return</span> insert((link_type)position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>, (link_type)position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>, v); 457 00459 <span class="comment">// first argument just needs to be non-null</span> 458 00460 <span class="keywordflow">else</span> 459 00461 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#a11">insert_unique</a>(v).first; 460 00462 } 461 00463 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a> == header) <span class="comment">// end()</span> 462 00464 { 463 00465 <span class="keywordflow">if</span> (key_compare(key(rightmost()), KeyOfValue()(v))) 464 00466 <span class="keywordflow">return</span> insert(0, rightmost(), v); 465 00467 <span class="keywordflow">else</span> 466 00468 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#a11">insert_unique</a>(v).first; 467 00469 } 468 00470 <span class="keywordflow">else</span> 469 00471 { 470 00472 iterator before = position; 471 00473 --before; 472 00474 <span class="keywordflow">if</span> (key_compare(key(before.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>), KeyOfValue()(v)) 473 00475 && key_compare(KeyOfValue()(v), key(position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>))) 474 00476 { 475 00477 <span class="keywordflow">if</span> (right(before.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>) == 0) 476 00478 <span class="keywordflow">return</span> insert(0, (link_type)before.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>, v); 477 00479 <span class="keywordflow">else</span> 478 00480 <span class="keywordflow">return</span> insert((link_type)position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>, (link_type)position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>, v); 479 00481 <span class="comment">// first argument just needs to be non-null</span> 480 00482 } 481 00483 <span class="keywordflow">else</span> 482 00484 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#a11">insert_unique</a>(v).first; 483 00485 } 484 00486 } 485 00487 486 <a name="l00488"></a><a class="code" href="classOscl__Rb__Tree.html#a13">00488</a> <span class="keywordtype">void</span> <a class="code" href="classOscl__Rb__Tree.html#a11">insert_unique</a>(const_iterator first, const_iterator last) 487 00489 { 488 00490 <span class="keywordflow">for</span> (; first != last; ++first) 489 00491 <a class="code" href="classOscl__Rb__Tree.html#a11">insert_unique</a>(*first); 490 00492 } 491 00493 492 <a name="l00494"></a><a class="code" href="classOscl__Rb__Tree.html#a14">00494</a> <span class="keywordtype">void</span> <a class="code" href="classOscl__Rb__Tree.html#a11">insert_unique</a>(<span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#s1">value_type</a>* first, <span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#s1">value_type</a>* last) 493 00495 { 494 00496 <span class="keywordflow">for</span> (; first != last; ++first) 495 00497 <a class="code" href="classOscl__Rb__Tree.html#a11">insert_unique</a>(*first); 496 00498 } 497 00499 498 <a name="l00500"></a><a class="code" href="classOscl__Rb__Tree.html#a15">00500</a> <span class="keywordtype">void</span> <a class="code" href="classOscl__Rb__Tree.html#a15">erase</a>(iterator position) 499 00501 { 500 00502 link_type y = (link_type) <a class="code" href="classOscl__Rb__Tree__Base.html#a3">rebalance_for_erase</a>(position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>, 501 00503 header-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>, 502 00504 header-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>, 503 00505 header-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>); 504 00506 505 00507 destroy_node(y); 506 00508 --node_count; 507 00509 } 508 00510 509 <a name="l00511"></a><a class="code" href="classOscl__Rb__Tree.html#a16">00511</a> <a class="code" href="classOscl__Rb__Tree.html#s9">size_type</a> <a class="code" href="classOscl__Rb__Tree.html#a15">erase</a>(<span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#s0">key_type</a>& x) 510 00512 { 511 00513 <a class="code" href="structOscl__Pair.html">Oscl_Pair<iterator, iterator></a> p = <a class="code" href="classOscl__Rb__Tree.html#a27">equal_range</a>(x); 512 00514 <a class="code" href="classOscl__Rb__Tree.html#s9">size_type</a> n = 0; 513 00515 distance(p.<a class="code" href="structOscl__Pair.html#m0">first</a>, p.<a class="code" href="structOscl__Pair.html#m1">second</a>, n); 514 00516 <a class="code" href="classOscl__Rb__Tree.html#a15">erase</a>(p.<a class="code" href="structOscl__Pair.html#m0">first</a>, p.<a class="code" href="structOscl__Pair.html#m1">second</a>); 515 00517 <span class="keywordflow">return</span> n; 516 00518 } 517 00519 518 <a name="l00520"></a><a class="code" href="classOscl__Rb__Tree.html#a17">00520</a> <span class="keywordtype">void</span> <a class="code" href="classOscl__Rb__Tree.html#a15">erase</a>(iterator first, iterator last) 519 00521 { 520 00522 <span class="keywordflow">if</span> (first == <a class="code" href="classOscl__Rb__Tree.html#a4">begin</a>() && last == <a class="code" href="classOscl__Rb__Tree.html#a6">end</a>()) 521 00523 <a class="code" href="classOscl__Rb__Tree.html#a19">clear</a>(); 522 00524 <span class="keywordflow">else</span> 523 00525 <span class="keywordflow">while</span> (first != last) <a class="code" href="classOscl__Rb__Tree.html#a15">erase</a>(first++); 524 00526 } 525 00527 526 <a name="l00528"></a><a class="code" href="classOscl__Rb__Tree.html#a18">00528</a> <span class="keywordtype">void</span> <a class="code" href="classOscl__Rb__Tree.html#a15">erase</a>(<span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#s0">key_type</a>* first, <span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#s0">key_type</a>* last) 527 00529 { 528 00530 <span class="keywordflow">while</span> (first != last) <a class="code" href="classOscl__Rb__Tree.html#a15">erase</a>(*first++); 529 00531 } 530 00532 531 <a name="l00533"></a><a class="code" href="classOscl__Rb__Tree.html#a19">00533</a> <span class="keywordtype">void</span> <a class="code" href="classOscl__Rb__Tree.html#a19">clear</a>() 532 00534 { 533 00535 <span class="keywordflow">if</span> (node_count != 0) 534 00536 { 535 00537 erase_without_rebalance(root()); 536 00538 leftmost() = header; 537 00539 root() = 0; 538 00540 rightmost() = header; 539 00541 node_count = 0; 540 00542 } 541 00543 } 542 00544 543 <a name="l00545"></a><a class="code" href="classOscl__Rb__Tree.html#a20">00545</a> iterator <a class="code" href="classOscl__Rb__Tree.html#a20">find</a>(<span class="keyword">const</span> Key& k) 544 00546 { 545 00547 link_type y = header; <span class="comment">// Last node which is not less than k.</span> 546 00548 link_type x = root(); <span class="comment">// Current node.</span> 547 00549 548 00550 <span class="keywordflow">while</span> (x != 0) 549 00551 { 550 00552 <span class="keywordflow">if</span> (!key_compare(key(x), k)) 551 00553 y = x, x = left(x); 552 00554 <span class="keywordflow">else</span> 553 00555 x = right(x); 554 00556 } 555 00557 iterator j = <a class="code" href="classOscl__Rb__Tree.html#s7">iterator</a>(y); 556 00558 <span class="keywordflow">return</span> (j == <a class="code" href="classOscl__Rb__Tree.html#a6">end</a>() || key_compare(k, key(j.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>))) ? <a class="code" href="classOscl__Rb__Tree.html#a6">end</a>() : j; 557 00559 } 558 00560 559 <a name="l00561"></a><a class="code" href="classOscl__Rb__Tree.html#a21">00561</a> const_iterator <a class="code" href="classOscl__Rb__Tree.html#a20">find</a>(<span class="keyword">const</span> Key& k)<span class="keyword"> const</span> 560 00562 <span class="keyword"> </span>{ 561 00563 link_type y = header; <span class="comment">/* Last node which is not less than k. */</span> 562 00564 link_type x = root(); <span class="comment">/* Current node. */</span> 563 00565 564 00566 <span class="keywordflow">while</span> (x != 0) 565 00567 { 566 00568 <span class="keywordflow">if</span> (!key_compare(key(x), k)) 567 00569 y = x, x = left(x); 568 00570 <span class="keywordflow">else</span> 569 00571 x = right(x); 570 00572 } 571 00573 const_iterator j = <a class="code" href="classOscl__Rb__Tree.html#s8">const_iterator</a>(y); 572 00574 <span class="keywordflow">return</span> (j == <a class="code" href="classOscl__Rb__Tree.html#a6">end</a>() || key_compare(k, key(j.<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#m0">node</a>))) ? <a class="code" href="classOscl__Rb__Tree.html#a6">end</a>() : j; 573 00575 } 574 00576 575 <a name="l00577"></a><a class="code" href="classOscl__Rb__Tree.html#a22">00577</a> <a class="code" href="classOscl__Rb__Tree.html#s9">size_type</a> <a class="code" href="classOscl__Rb__Tree.html#a22">count</a>(<span class="keyword">const</span> Key& k)<span class="keyword"> const</span> 576 00578 <span class="keyword"> </span>{ 577 00579 <a class="code" href="structOscl__Pair.html">Oscl_Pair<const_iterator, const_iterator></a> p = <a class="code" href="classOscl__Rb__Tree.html#a27">equal_range</a>(k); 578 00580 <a class="code" href="classOscl__Rb__Tree.html#s9">size_type</a> n = 0; 579 00581 distance(p.<a class="code" href="structOscl__Pair.html#m0">first</a>, p.<a class="code" href="structOscl__Pair.html#m1">second</a>, n); 580 00582 <span class="keywordflow">return</span> n; 581 00583 } 582 00584 583 <a name="l00585"></a><a class="code" href="classOscl__Rb__Tree.html#a23">00585</a> iterator <a class="code" href="classOscl__Rb__Tree.html#a23">lower_bound</a>(<span class="keyword">const</span> Key& k) 584 00586 { 585 00587 link_type y = header; <span class="comment">/* Last node which is not less than k. */</span> 586 00588 link_type x = root(); <span class="comment">/* Current node. */</span> 587 00589 588 00590 <span class="keywordflow">while</span> (x != 0) 589 00591 { 590 00592 <span class="keywordflow">if</span> (!key_compare(key(x), k)) 591 00593 { 592 00594 y = x; 593 00595 x = left(x); 594 00596 } 595 00597 <span class="keywordflow">else</span> 596 00598 x = right(x); 597 00599 } 598 00600 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#s7">iterator</a>(y); 599 00601 } 600 00602 601 <a name="l00603"></a><a class="code" href="classOscl__Rb__Tree.html#a24">00603</a> const_iterator <a class="code" href="classOscl__Rb__Tree.html#a23">lower_bound</a>(<span class="keyword">const</span> Key& k)<span class="keyword"> const</span> 602 00604 <span class="keyword"> </span>{ 603 00605 link_type y = header; <span class="comment">/* Last node which is not less than k. */</span> 604 00606 link_type x = root(); <span class="comment">/* Current node. */</span> 605 00607 606 00608 <span class="keywordflow">while</span> (x != 0) 607 00609 { 608 00610 <span class="keywordflow">if</span> (!key_compare(key(x), k)) 609 00611 { 610 00612 y = x; 611 00613 x = left(x); 612 00614 } 613 00615 <span class="keywordflow">else</span> 614 00616 x = right(x); 615 00617 } 616 00618 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#s8">const_iterator</a>(y); 617 00619 } 618 00620 619 <a name="l00621"></a><a class="code" href="classOscl__Rb__Tree.html#a25">00621</a> iterator <a class="code" href="classOscl__Rb__Tree.html#a25">upper_bound</a>(<span class="keyword">const</span> Key& k) 620 00622 { 621 00623 link_type y = header; <span class="comment">/* Last node which is greater than k. */</span> 622 00624 link_type x = root(); <span class="comment">/* Current node. */</span> 623 00625 624 00626 <span class="keywordflow">while</span> (x != 0) 625 00627 { 626 00628 <span class="keywordflow">if</span> (key_compare(k, key(x))) 627 00629 { 628 00630 y = x; 629 00631 x = left(x); 630 00632 } 631 00633 <span class="keywordflow">else</span> 632 00634 x = right(x); 633 00635 } 634 00636 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#s7">iterator</a>(y); 635 00637 } 636 00638 637 <a name="l00639"></a><a class="code" href="classOscl__Rb__Tree.html#a26">00639</a> const_iterator <a class="code" href="classOscl__Rb__Tree.html#a25">upper_bound</a>(<span class="keyword">const</span> Key& k)<span class="keyword"> const</span> 638 00640 <span class="keyword"> </span>{ 639 00641 link_type y = header; <span class="comment">/* Last node which is greater than k. */</span> 640 00642 link_type x = root(); <span class="comment">/* Current node. */</span> 641 00643 642 00644 <span class="keywordflow">while</span> (x != 0) 643 00645 { 644 00646 <span class="keywordflow">if</span> (key_compare(k, key(x))) 645 00647 { 646 00648 y = x; 647 00649 x = left(x); 648 00650 } 649 00651 <span class="keywordflow">else</span> 650 00652 x = right(x); 651 00653 } 652 00654 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#s8">const_iterator</a>(y); 653 00655 } 654 00656 655 <a name="l00657"></a><a class="code" href="classOscl__Rb__Tree.html#a27">00657</a> <a class="code" href="structOscl__Pair.html">Oscl_Pair<iterator, iterator></a> <a class="code" href="classOscl__Rb__Tree.html#a27">equal_range</a>(<span class="keyword">const</span> Key& k) 656 00658 { 657 00659 <span class="keywordflow">return</span> <a class="code" href="structOscl__Pair.html">Oscl_Pair<iterator, iterator></a>(<a class="code" href="classOscl__Rb__Tree.html#a23">lower_bound</a>(k), <a class="code" href="classOscl__Rb__Tree.html#a25">upper_bound</a>(k)); 658 00660 } 659 00661 660 <a name="l00662"></a><a class="code" href="classOscl__Rb__Tree.html#a28">00662</a> <a class="code" href="structOscl__Pair.html">Oscl_Pair<const_iterator, const_iterator></a> <a class="code" href="classOscl__Rb__Tree.html#a27">equal_range</a>(<span class="keyword">const</span> Key& k)<span class="keyword"> const</span> 661 00663 <span class="keyword"> </span>{ 662 00664 <span class="keywordflow">return</span> <a class="code" href="structOscl__Pair.html">Oscl_Pair<const_iterator, const_iterator></a>(<a class="code" href="classOscl__Rb__Tree.html#a23">lower_bound</a>(k), <a class="code" href="classOscl__Rb__Tree.html#a25">upper_bound</a>(k)); 663 00665 } 664 00666 665 00667 <span class="keyword">private</span>: 666 00668 <span class="comment">// this helper function performs a downcast from base_link_type& to link_type&</span> 667 00669 <span class="comment">// under C99 (gcc 3.x) this breaks aliasing rules so we have to go via a void** instead</span> 668 00670 <span class="keyword">inline</span> <span class="keyword">static</span> link_type& cast_to_link_type(<a class="code" href="classOscl__Rb__Tree__Base.html#s0">base_link_type</a> &node) 669 00671 { 670 00672 <span class="keywordtype">void</span>** ptr = (<span class="keywordtype">void</span>**) & node; 671 00673 link_type* base = (link_type*) ptr; 672 00674 <span class="keywordflow">return</span> *base; 673 00675 } 674 00676 675 00677 link_type& root()<span class="keyword"> const</span> 676 00678 <span class="keyword"> </span>{ 677 00679 <span class="keywordflow">return</span> cast_to_link_type(header-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>); 678 00680 } 679 00681 link_type& leftmost()<span class="keyword"> const</span> 680 00682 <span class="keyword"> </span>{ 681 00683 <span class="keywordflow">return</span> cast_to_link_type(header-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>); 682 00684 } 683 00685 link_type& rightmost()<span class="keyword"> const</span> 684 00686 <span class="keyword"> </span>{ 685 00687 <span class="keywordflow">return</span> cast_to_link_type(header-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>); 686 00688 } 687 00689 688 00690 <span class="keyword">const</span> Key& key(link_type x)<span class="keyword"> const</span> 689 00691 <span class="keyword"> </span>{ 690 00692 <span class="keywordflow">return</span> KeyOfValue()(value(x)); 691 00693 } 692 00694 <span class="keyword">static</span> <a class="code" href="classOscl__Rb__Tree.html#s4">reference</a> value(link_type x) 693 00695 { 694 00696 <span class="keywordflow">return</span> x->value; 695 00697 } 696 00698 <span class="keyword">static</span> link_type& left(link_type x) 697 00699 { 698 00700 <span class="keywordflow">return</span> cast_to_link_type(x->left); 699 00701 } 700 00702 <span class="keyword">static</span> link_type& right(link_type x) 701 00703 { 702 00704 <span class="keywordflow">return</span> cast_to_link_type(x->right); 703 00705 } 704 00706 <span class="keyword">static</span> link_type& parent(link_type x) 705 00707 { 706 00708 <span class="keywordflow">return</span> cast_to_link_type(x->parent); 707 00709 } 708 00710 709 00711 <span class="keyword">const</span> Key& key(<a class="code" href="classOscl__Rb__Tree__Base.html#s0">base_link_type</a> x)<span class="keyword"> const</span> 710 00712 <span class="keyword"> </span>{ 711 00713 <span class="keywordflow">return</span> KeyOfValue()(value(x)); 712 00714 } 713 00715 <span class="keyword">static</span> <a class="code" href="classOscl__Rb__Tree.html#s4">reference</a> value(<a class="code" href="classOscl__Rb__Tree__Base.html#s0">base_link_type</a> x) 714 00716 { 715 00717 <span class="keywordflow">return</span> ((link_type)x)->value; 716 00718 } 717 00719 <span class="keyword">static</span> link_type& left(<a class="code" href="classOscl__Rb__Tree__Base.html#s0">base_link_type</a> x) 718 00720 { 719 00721 <span class="keywordflow">return</span> cast_to_link_type(x->left); 720 00722 } 721 00723 <span class="keyword">static</span> link_type& right(<a class="code" href="classOscl__Rb__Tree__Base.html#s0">base_link_type</a> x) 722 00724 { 723 00725 <span class="keywordflow">return</span> cast_to_link_type(x->right); 724 00726 } 725 00727 <span class="keyword">static</span> link_type& parent(<a class="code" href="classOscl__Rb__Tree__Base.html#s0">base_link_type</a> x) 726 00728 { 727 00729 <span class="keywordflow">return</span> cast_to_link_type(x->parent); 728 00730 } 729 00731 730 00732 <span class="keyword">static</span> link_type minimum(link_type x) 731 00733 { 732 00734 <span class="keywordflow">return</span> (link_type) <a class="code" href="structOscl__Rb__Tree__Node__Base.html#d0">Oscl_Rb_Tree_Node_Base::minimum</a>(x); 733 00735 } 734 00736 <span class="keyword">static</span> link_type maximum(link_type x) 735 00737 { 736 00738 <span class="keywordflow">return</span> (link_type) <a class="code" href="structOscl__Rb__Tree__Node__Base.html#d1">Oscl_Rb_Tree_Node_Base::maximum</a>(x); 737 00739 } 738 00740 739 00741 iterator insert(link_type x, link_type y, <span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#s1">value_type</a>& v) 740 00742 { 741 00743 link_type z; 742 00744 743 00745 <span class="keywordflow">if</span> (y == header || x != 0 || key_compare(KeyOfValue()(v), key(y))) 744 00746 { 745 00747 z = create_node(v); 746 00748 left(y) = z; <span class="comment">// also makes leftmost() = z when y == header</span> 747 00749 <span class="keywordflow">if</span> (y == header) 748 00750 { 749 00751 root() = z; 750 00752 rightmost() = z; 751 00753 } 752 00754 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (y == leftmost()) 753 00755 leftmost() = z; <span class="comment">// maintain leftmost() pointing to min node</span> 754 00756 } 755 00757 <span class="keywordflow">else</span> 756 00758 { 757 00759 z = create_node(v); 758 00760 right(y) = z; 759 00761 <span class="keywordflow">if</span> (y == rightmost()) 760 00762 rightmost() = z; <span class="comment">// maintain rightmost() pointing to max node</span> 761 00763 } 762 00764 parent(z) = y; 763 00765 left(z) = 0; 764 00766 right(z) = 0; 765 00767 <a class="code" href="classOscl__Rb__Tree__Base.html#a2">rebalance</a>(z, header-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>); 766 00768 ++node_count; 767 00769 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#s7">iterator</a>(z); 768 00770 769 00771 } 770 00772 771 00773 <span class="keywordtype">void</span> erase_without_rebalance(link_type x) 772 00774 { 773 00775 <span class="keywordflow">while</span> (x != 0) 774 00776 { 775 00777 erase_without_rebalance((link_type)x->right); 776 00778 link_type y = (link_type)x-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>; 777 00779 destroy_node(x); 778 00780 x = y; 779 00781 } 780 00782 } 781 00783 782 00784 link_type copy(link_type x, link_type p) 783 00785 { 784 00786 <span class="comment">// structural copy. x and p must be non-null.</span> 785 00787 link_type top = clone_node(x); 786 00788 top->parent = p; 787 00789 788 00790 <span class="keywordflow">if</span> (x->right) 789 00791 { 790 00792 top->right = copy(right(x), top); 791 00793 } 792 00794 p = top; 793 00795 x = left(x); 794 00796 795 00797 <span class="keywordflow">while</span> (x != 0) 796 00798 { 797 00799 link_type y = clone_node(x); 798 00800 p->left = y; 799 00801 y->parent = p; 800 00802 <span class="keywordflow">if</span> (x->right) 801 00803 { 802 00804 y->right = copy(right(x), y); 803 00805 } 804 00806 p = y; 805 00807 x = left(x); 806 00808 } 807 00809 808 00810 <span class="keywordflow">return</span> top; 809 00811 } 810 00812 811 00813 link_type get_node() 812 00814 { 813 00815 <span class="keywordflow">return</span> node_allocator.ALLOCATE(1); 814 00816 } 815 00817 <span class="keywordtype">void</span> release_node(link_type node) 816 00818 { 817 00819 node_allocator.<a class="code" href="classOscl__TAlloc.html#a5">deallocate</a>(node); 818 00820 } 819 00821 820 00822 link_type create_node(<span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#s1">value_type</a>& v) 821 00823 { 822 00824 link_type x = get_node(); 823 00825 <span class="keyword">new</span>(&x->value) <a class="code" href="classOscl__Rb__Tree.html#s1">value_type</a>(v); 824 00826 <span class="keywordflow">return</span> x; 825 00827 } 826 00828 827 00829 <span class="keywordtype">void</span> destroy_node(link_type x) 828 00830 { 829 00831 x->value.~Value(); 830 00832 release_node(x); 831 00833 } 832 00834 833 00835 link_type clone_node(link_type x) 834 00836 { 835 00837 link_type tmp = create_node(x->value); 836 00838 tmp->color = x->color; 837 00839 tmp->left = 0; 838 00840 tmp->right = 0; 839 00841 <span class="keywordflow">return</span> tmp; 840 00842 } 841 00843 842 00844 <span class="keywordtype">void</span> distance(const_iterator first, const_iterator last, <a class="code" href="classOscl__Rb__Tree.html#s9">size_type</a>& n)<span class="keyword"> const</span> 843 00845 <span class="keyword"> </span>{ 844 00846 <span class="keywordflow">while</span> (first != last) 845 00847 { 846 00848 n++; 847 00849 first++; 848 00850 } 849 00851 } 850 00852 851 00853 <span class="keywordtype">void</span> distance(iterator first, iterator last, <a class="code" href="classOscl__Rb__Tree.html#s9">size_type</a>& n)<span class="keyword"> const</span> 852 00854 <span class="keyword"> </span>{ 853 00855 <span class="keywordflow">while</span> (first != last) 854 00856 { 855 00857 n++; 856 00858 first++; 857 00859 } 858 00860 } 859 00861 }; 860 00862 861 00863 862 00867 <span class="preprocessor">#endif</span> 863 00868 <span class="preprocessor"></span> 864 </pre></div><hr size="1"><img src="pvlogo_small.jpg"><address style="align: right;"><small>OSCL API</small> 865 <address style="align: left;"><small>Posting Version: OPENCORE_20090310 </small> 866 </small></address> 867 </body> 868 </html> 869
