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> 1000002 <span class="comment">// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =</span> 1100003 1200004 <span class="comment">// O S C L _ T R E E</span> 1300005 1400006 <span class="comment">// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =</span> 1500007 1600018 <span class="preprocessor">#ifndef OSCL_TREE_H_INCLUDED</span> 1700019 <span class="preprocessor"></span><span class="preprocessor">#define OSCL_TREE_H_INCLUDED</span> 1800020 <span class="preprocessor"></span> 1900021 <span class="preprocessor">#ifndef OSCL_DEFALLOC_H_INCLUDED</span> 2000022 <span class="preprocessor"></span><span class="preprocessor">#include "<a class="code" href="oscl__defalloc_8h.html">oscl_defalloc.h</a>"</span> 2100023 <span class="preprocessor">#endif</span> 2200024 <span class="preprocessor"></span> 2300025 <span class="preprocessor">#ifndef OSCL_BASE_H_INCLUDED</span> 2400026 <span class="preprocessor"></span><span class="preprocessor">#include "<a class="code" href="oscl__base_8h.html">oscl_base.h</a>"</span> 2500027 <span class="preprocessor">#endif</span> 2600028 <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> 2800030 <span class="preprocessor"></span><span class="preprocessor">#include "<a class="code" href="osclconfig__compiler__warnings_8h.html">osclconfig_compiler_warnings.h</a>"</span> 2900031 3000032 <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> 3200034 { 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) {} 3700039 }; 3800040 3900041 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> 4100043 { 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>; 4400046 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>; 4900051 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) 5100053 { 5200054 <span class="keywordflow">if</span> (x) 5300055 { 5400056 <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>; 5500057 } 5600058 <span class="keywordflow">return</span> x; 5700059 } 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) 5900061 { 6000062 <span class="keywordflow">if</span> (x) 6100063 { 6200064 <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>; 6300065 } 6400066 <span class="keywordflow">return</span> x; 6500067 } 6600068 }; 6700069 6800070 <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> 7000072 { 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>; 7400076 }; 7500077 7600078 7700079 <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> 7900081 { 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>; 8700089 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>; 8900091 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) 9200094 { 9300095 node = x; 9400096 } 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) 9600098 { 9700099 node = it.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>; 9800100 } 9900101 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> 10100103 <span class="keyword"> </span>{ 10200104 <span class="keywordflow">return</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html#s6">link_type</a>(node)->value; 10300105 } 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> 10500107 <span class="keyword"> </span>{ 10600108 <span class="keywordflow">return</span> &(<a class="code" href="structOscl__Rb__Tree__Iterator.html#a3">operator*</a>()); 10700109 } 10800110 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) 11000112 { 11100113 <span class="keywordflow">return</span> node == x.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>; 11200114 } 11300115 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) 11500117 { 11600118 <span class="keywordflow">return</span> node != x.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>; 11700119 } 11800120 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>() 12000122 { 12100123 <span class="keywordflow">if</span> (node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a> != 0) 12200124 { 12300125 node = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>; 12400126 <span class="keywordflow">while</span> (node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a> != 0) 12500127 { 12600128 node = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>; 12700129 } 12800130 } 12900131 <span class="keywordflow">else</span> 13000132 { 13100133 base_link_type y = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>; 13200134 <span class="keywordflow">while</span> (node == y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>) 13300135 { 13400136 node = y; 13500137 y = y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>; 13600138 } 13700139 <span class="keywordflow">if</span> (node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a> != y) node = y; 13800140 } 13900141 <span class="keywordflow">return</span> *<span class="keyword">this</span>; 14000142 } 14100143 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>) 14300145 { 14400146 self tmp = *<span class="keyword">this</span>; 14500147 ++*<span class="keyword">this</span>; 14600148 <span class="keywordflow">return</span> tmp; 14700149 } 14800150 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>() 15000152 { 15100153 <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) 15200154 { 15300155 node = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>; <span class="comment">// return rightmost</span> 15400156 } 15500157 <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) 15600158 { 15700159 base_link_type y = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>; 15800160 <span class="keywordflow">while</span> (y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a> != 0) 15900161 y = y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>; 16000162 node = y; 16100163 } 16200164 <span class="keywordflow">else</span> 16300165 { 16400166 base_link_type y = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>; 16500167 <span class="keywordflow">while</span> (node == y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>) 16600168 { 16700169 node = y; 16800170 y = y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>; 16900171 } 17000172 node = y; 17100173 } 17200174 <span class="keywordflow">return</span> *<span class="keyword">this</span>; 17300175 } 17400176 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>) 17600178 { 17700179 self tmp = *<span class="keyword">this</span>; 17800180 --*<span class="keyword">this</span>; 17900181 <span class="keywordflow">return</span> tmp; 18000182 } 18100183 }; 18200184 18300185 18400186 <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> 18600188 { 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>; 19400196 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>; 19600198 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) 19900201 { 20000202 node = x; 20100203 } 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) 20300205 { 20400206 node = it.<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#m0">node</a>; 20500207 } 20600208 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> 20800210 <span class="keyword"> </span>{ 20900211 <span class="keywordflow">return</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#s6">link_type</a>(node)->value; 21000212 } 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> 21200214 <span class="keyword"> </span>{ 21300215 <span class="keywordflow">return</span> &(<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a3">operator*</a>()); 21400216 } 21500217 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) 21700219 { 21800220 <span class="keywordflow">return</span> node == x.<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#m0">node</a>; 21900221 } 22000222 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) 22200224 { 22300225 <span class="keywordflow">return</span> node != x.<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#m0">node</a>; 22400226 } 22500227 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>() 22700229 { 22800230 <span class="keywordflow">if</span> (node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a> != 0) 22900231 { 23000232 node = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>; 23100233 <span class="keywordflow">while</span> (node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a> != 0) 23200234 { 23300235 node = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>; 23400236 } 23500237 } 23600238 <span class="keywordflow">else</span> 23700239 { 23800240 base_link_type y = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>; 23900241 <span class="keywordflow">while</span> (node == y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>) 24000242 { 24100243 node = y; 24200244 y = y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>; 24300245 } 24400246 <span class="keywordflow">if</span> (node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a> != y) node = y; 24500247 } 24600248 <span class="keywordflow">return</span> *<span class="keyword">this</span>; 24700249 } 24800250 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>) 25000252 { 25100253 self tmp = *<span class="keyword">this</span>; 25200254 ++*<span class="keyword">this</span>; 25300255 <span class="keywordflow">return</span> tmp; 25400256 } 25500257 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>() 25700259 { 25800260 <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) 25900261 { 26000262 node = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>; <span class="comment">// return rightmost</span> 26100263 } 26200264 <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) 26300265 { 26400266 base_link_type y = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>; 26500267 <span class="keywordflow">while</span> (y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a> != 0) 26600268 y = y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>; 26700269 node = y; 26800270 } 26900271 <span class="keywordflow">else</span> 27000272 { 27100273 base_link_type y = node-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>; 27200274 <span class="keywordflow">while</span> (node == y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>) 27300275 { 27400276 node = y; 27500277 y = y-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>; 27600278 } 27700279 node = y; 27800280 } 27900281 <span class="keywordflow">return</span> *<span class="keyword">this</span>; 28000282 } 28100283 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>) 28300285 { 28400286 self tmp = *<span class="keyword">this</span>; 28500287 --*<span class="keyword">this</span>; 28600288 <span class="keywordflow">return</span> tmp; 28700289 } 28800290 }; 28900291 29000292 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> 29200294 { 29300295 29400296 <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>; 29600298 29700299 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); 29800300 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); 29900301 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); 30000302 OSCL_IMPORT_REF base_link_type <a class="code" href="classOscl__Rb__Tree__Base.html#a3">rebalance_for_erase</a>(base_link_type z, 30100303 base_link_type& root, 30200304 base_link_type& leftmost, 30300305 base_link_type& rightmost); 30400306 }; 30500307 30600308 30700309 <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> 30900311 { 31000312 31100313 <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>; 32300325 <span class="keyword">private</span>: 32400326 <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>; 32500327 <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>; 32600328 32700329 <span class="keyword">private</span>: 32800330 link_type header; 32900331 <a class="code" href="classOscl__Rb__Tree.html#s9">size_type</a> node_count; 33000332 Compare key_compare; 33100333 <a class="code" href="classOscl__TAlloc.html">Oscl_TAlloc<node_type, Alloc></a> node_allocator; 33200334 33300335 <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()) 33500337 : node_count(0), key_compare(comp) 33600338 { 33700339 header = get_node(); 33800340 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>; 33900341 leftmost() = header; 34000342 rightmost() = header; 34100343 root() = 0; 34200344 } 34300345 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) 34500347 : node_count(0), key_compare(x.key_compare) 34600348 { 34700349 header = get_node(); 34800350 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>; 34900351 <span class="keywordflow">if</span> (x.root() == 0) 35000352 { 35100353 leftmost() = header; 35200354 rightmost() = header; 35300355 root() = 0; 35400356 } 35500357 <span class="keywordflow">else</span> 35600358 { 35700359 root() = copy(x.root(), header); 35800360 leftmost() = minimum(root()); 35900361 rightmost() = maximum(root()); 36000362 } 36100363 node_count = x.node_count; 36200364 } 36300365 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>() 36500367 { 36600368 <a class="code" href="classOscl__Rb__Tree.html#a19">clear</a>(); 36700369 release_node(header); 36800370 } 36900371 37000372 <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) 37200374 { 37300375 <span class="keywordflow">if</span> (<span class="keyword">this</span> != &x) 37400376 { 37500377 <a class="code" href="classOscl__Rb__Tree.html#a19">clear</a>(); 37600378 node_count = 0; 37700379 key_compare = x.<a class="code" href="classOscl__Rb__Tree.html#o2">key_compare</a>; 37800380 37900381 <span class="keywordflow">if</span> (x.<a class="code" href="classOscl__Rb__Tree.html#c0">root</a>() == 0) 38000382 { 38100383 root() = 0; 38200384 leftmost() = header; 38300385 rightmost() = header; 38400386 } 38500387 <span class="keywordflow">else</span> 38600388 { 38700389 root() = copy(x.<a class="code" href="classOscl__Rb__Tree.html#c0">root</a>(), header); 38800390 leftmost() = minimum(root()); 38900391 rightmost() = maximum(root()); 39000392 node_count = x.<a class="code" href="classOscl__Rb__Tree.html#o1">node_count</a>; 39100393 } 39200394 } 39300395 <span class="keywordflow">return</span> *<span class="keyword">this</span>; 39400396 } 39500397 39600398 <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>() 39800400 { 39900401 <span class="keywordflow">return</span> leftmost(); 40000402 } 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> 40200404 <span class="keyword"> </span>{ 40300405 <span class="keywordflow">return</span> leftmost(); 40400406 } 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>() 40600408 { 40700409 <span class="keywordflow">return</span> header; 40800410 } 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> 41000412 <span class="keyword"> </span>{ 41100413 <span class="keywordflow">return</span> header; 41200414 } 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> 41400416 <span class="keyword"> </span>{ 41500417 <span class="keywordflow">return</span> node_count == 0; 41600418 } 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> 41800420 <span class="keyword"> </span>{ 41900421 <span class="keywordflow">return</span> node_count; 42000422 } 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> 42200424 <span class="keyword"> </span>{ 42300425 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#s9">size_type</a>(-1); 42400426 } 42500427 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) 42700429 { 42800430 link_type y = header; 42900431 link_type x = root(); 43000432 <span class="keywordtype">bool</span> comp = <span class="keyword">true</span>; 43100433 <span class="keywordflow">while</span> (x != 0) 43200434 { 43300435 y = x; 43400436 comp = key_compare(KeyOfValue()(v), key(x)); 43500437 x = comp ? left(x) : right(x); 43600438 } 43700439 iterator j = <a class="code" href="classOscl__Rb__Tree.html#s7">iterator</a>(y); 43800440 <span class="keywordflow">if</span> (comp) 43900441 { 44000442 <span class="keywordflow">if</span> (j == <a class="code" href="classOscl__Rb__Tree.html#a4">begin</a>()) 44100443 <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>); 44200444 <span class="keywordflow">else</span> 44300445 --j; 44400446 } 44500447 <span class="keywordflow">if</span> (key_compare(key(j.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>), KeyOfValue()(v))) 44600448 <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>); 44700449 44800450 <span class="keywordflow">return</span> <a class="code" href="structOscl__Pair.html">Oscl_Pair<iterator, bool></a>(j, <span class="keyword">false</span>); 44900451 } 45000452 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) 45200454 { 45300455 <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> 45400456 { 45500457 <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>))) 45600458 <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); 45700459 <span class="comment">// first argument just needs to be non-null</span> 45800460 <span class="keywordflow">else</span> 45900461 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#a11">insert_unique</a>(v).first; 46000462 } 46100463 <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> 46200464 { 46300465 <span class="keywordflow">if</span> (key_compare(key(rightmost()), KeyOfValue()(v))) 46400466 <span class="keywordflow">return</span> insert(0, rightmost(), v); 46500467 <span class="keywordflow">else</span> 46600468 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#a11">insert_unique</a>(v).first; 46700469 } 46800470 <span class="keywordflow">else</span> 46900471 { 47000472 iterator before = position; 47100473 --before; 47200474 <span class="keywordflow">if</span> (key_compare(key(before.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>), KeyOfValue()(v)) 47300475 && key_compare(KeyOfValue()(v), key(position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>))) 47400476 { 47500477 <span class="keywordflow">if</span> (right(before.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>) == 0) 47600478 <span class="keywordflow">return</span> insert(0, (link_type)before.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>, v); 47700479 <span class="keywordflow">else</span> 47800480 <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); 47900481 <span class="comment">// first argument just needs to be non-null</span> 48000482 } 48100483 <span class="keywordflow">else</span> 48200484 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#a11">insert_unique</a>(v).first; 48300485 } 48400486 } 48500487 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) 48700489 { 48800490 <span class="keywordflow">for</span> (; first != last; ++first) 48900491 <a class="code" href="classOscl__Rb__Tree.html#a11">insert_unique</a>(*first); 49000492 } 49100493 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) 49300495 { 49400496 <span class="keywordflow">for</span> (; first != last; ++first) 49500497 <a class="code" href="classOscl__Rb__Tree.html#a11">insert_unique</a>(*first); 49600498 } 49700499 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) 49900501 { 50000502 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>, 50100503 header-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>, 50200504 header-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>, 50300505 header-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>); 50400506 50500507 destroy_node(y); 50600508 --node_count; 50700509 } 50800510 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) 51000512 { 51100513 <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); 51200514 <a class="code" href="classOscl__Rb__Tree.html#s9">size_type</a> n = 0; 51300515 distance(p.<a class="code" href="structOscl__Pair.html#m0">first</a>, p.<a class="code" href="structOscl__Pair.html#m1">second</a>, n); 51400516 <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>); 51500517 <span class="keywordflow">return</span> n; 51600518 } 51700519 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) 51900521 { 52000522 <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>()) 52100523 <a class="code" href="classOscl__Rb__Tree.html#a19">clear</a>(); 52200524 <span class="keywordflow">else</span> 52300525 <span class="keywordflow">while</span> (first != last) <a class="code" href="classOscl__Rb__Tree.html#a15">erase</a>(first++); 52400526 } 52500527 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) 52700529 { 52800530 <span class="keywordflow">while</span> (first != last) <a class="code" href="classOscl__Rb__Tree.html#a15">erase</a>(*first++); 52900531 } 53000532 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>() 53200534 { 53300535 <span class="keywordflow">if</span> (node_count != 0) 53400536 { 53500537 erase_without_rebalance(root()); 53600538 leftmost() = header; 53700539 root() = 0; 53800540 rightmost() = header; 53900541 node_count = 0; 54000542 } 54100543 } 54200544 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) 54400546 { 54500547 link_type y = header; <span class="comment">// Last node which is not less than k.</span> 54600548 link_type x = root(); <span class="comment">// Current node.</span> 54700549 54800550 <span class="keywordflow">while</span> (x != 0) 54900551 { 55000552 <span class="keywordflow">if</span> (!key_compare(key(x), k)) 55100553 y = x, x = left(x); 55200554 <span class="keywordflow">else</span> 55300555 x = right(x); 55400556 } 55500557 iterator j = <a class="code" href="classOscl__Rb__Tree.html#s7">iterator</a>(y); 55600558 <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; 55700559 } 55800560 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> 56000562 <span class="keyword"> </span>{ 56100563 link_type y = header; <span class="comment">/* Last node which is not less than k. */</span> 56200564 link_type x = root(); <span class="comment">/* Current node. */</span> 56300565 56400566 <span class="keywordflow">while</span> (x != 0) 56500567 { 56600568 <span class="keywordflow">if</span> (!key_compare(key(x), k)) 56700569 y = x, x = left(x); 56800570 <span class="keywordflow">else</span> 56900571 x = right(x); 57000572 } 57100573 const_iterator j = <a class="code" href="classOscl__Rb__Tree.html#s8">const_iterator</a>(y); 57200574 <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; 57300575 } 57400576 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> 57600578 <span class="keyword"> </span>{ 57700579 <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); 57800580 <a class="code" href="classOscl__Rb__Tree.html#s9">size_type</a> n = 0; 57900581 distance(p.<a class="code" href="structOscl__Pair.html#m0">first</a>, p.<a class="code" href="structOscl__Pair.html#m1">second</a>, n); 58000582 <span class="keywordflow">return</span> n; 58100583 } 58200584 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) 58400586 { 58500587 link_type y = header; <span class="comment">/* Last node which is not less than k. */</span> 58600588 link_type x = root(); <span class="comment">/* Current node. */</span> 58700589 58800590 <span class="keywordflow">while</span> (x != 0) 58900591 { 59000592 <span class="keywordflow">if</span> (!key_compare(key(x), k)) 59100593 { 59200594 y = x; 59300595 x = left(x); 59400596 } 59500597 <span class="keywordflow">else</span> 59600598 x = right(x); 59700599 } 59800600 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#s7">iterator</a>(y); 59900601 } 60000602 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> 60200604 <span class="keyword"> </span>{ 60300605 link_type y = header; <span class="comment">/* Last node which is not less than k. */</span> 60400606 link_type x = root(); <span class="comment">/* Current node. */</span> 60500607 60600608 <span class="keywordflow">while</span> (x != 0) 60700609 { 60800610 <span class="keywordflow">if</span> (!key_compare(key(x), k)) 60900611 { 61000612 y = x; 61100613 x = left(x); 61200614 } 61300615 <span class="keywordflow">else</span> 61400616 x = right(x); 61500617 } 61600618 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#s8">const_iterator</a>(y); 61700619 } 61800620 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) 62000622 { 62100623 link_type y = header; <span class="comment">/* Last node which is greater than k. */</span> 62200624 link_type x = root(); <span class="comment">/* Current node. */</span> 62300625 62400626 <span class="keywordflow">while</span> (x != 0) 62500627 { 62600628 <span class="keywordflow">if</span> (key_compare(k, key(x))) 62700629 { 62800630 y = x; 62900631 x = left(x); 63000632 } 63100633 <span class="keywordflow">else</span> 63200634 x = right(x); 63300635 } 63400636 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#s7">iterator</a>(y); 63500637 } 63600638 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> 63800640 <span class="keyword"> </span>{ 63900641 link_type y = header; <span class="comment">/* Last node which is greater than k. */</span> 64000642 link_type x = root(); <span class="comment">/* Current node. */</span> 64100643 64200644 <span class="keywordflow">while</span> (x != 0) 64300645 { 64400646 <span class="keywordflow">if</span> (key_compare(k, key(x))) 64500647 { 64600648 y = x; 64700649 x = left(x); 64800650 } 64900651 <span class="keywordflow">else</span> 65000652 x = right(x); 65100653 } 65200654 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#s8">const_iterator</a>(y); 65300655 } 65400656 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) 65600658 { 65700659 <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)); 65800660 } 65900661 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> 66100663 <span class="keyword"> </span>{ 66200664 <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)); 66300665 } 66400666 66500667 <span class="keyword">private</span>: 66600668 <span class="comment">// this helper function performs a downcast from base_link_type& to link_type&</span> 66700669 <span class="comment">// under C99 (gcc 3.x) this breaks aliasing rules so we have to go via a void** instead</span> 66800670 <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) 66900671 { 67000672 <span class="keywordtype">void</span>** ptr = (<span class="keywordtype">void</span>**) & node; 67100673 link_type* base = (link_type*) ptr; 67200674 <span class="keywordflow">return</span> *base; 67300675 } 67400676 67500677 link_type& root()<span class="keyword"> const</span> 67600678 <span class="keyword"> </span>{ 67700679 <span class="keywordflow">return</span> cast_to_link_type(header-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>); 67800680 } 67900681 link_type& leftmost()<span class="keyword"> const</span> 68000682 <span class="keyword"> </span>{ 68100683 <span class="keywordflow">return</span> cast_to_link_type(header-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>); 68200684 } 68300685 link_type& rightmost()<span class="keyword"> const</span> 68400686 <span class="keyword"> </span>{ 68500687 <span class="keywordflow">return</span> cast_to_link_type(header-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>); 68600688 } 68700689 68800690 <span class="keyword">const</span> Key& key(link_type x)<span class="keyword"> const</span> 68900691 <span class="keyword"> </span>{ 69000692 <span class="keywordflow">return</span> KeyOfValue()(value(x)); 69100693 } 69200694 <span class="keyword">static</span> <a class="code" href="classOscl__Rb__Tree.html#s4">reference</a> value(link_type x) 69300695 { 69400696 <span class="keywordflow">return</span> x->value; 69500697 } 69600698 <span class="keyword">static</span> link_type& left(link_type x) 69700699 { 69800700 <span class="keywordflow">return</span> cast_to_link_type(x->left); 69900701 } 70000702 <span class="keyword">static</span> link_type& right(link_type x) 70100703 { 70200704 <span class="keywordflow">return</span> cast_to_link_type(x->right); 70300705 } 70400706 <span class="keyword">static</span> link_type& parent(link_type x) 70500707 { 70600708 <span class="keywordflow">return</span> cast_to_link_type(x->parent); 70700709 } 70800710 70900711 <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> 71000712 <span class="keyword"> </span>{ 71100713 <span class="keywordflow">return</span> KeyOfValue()(value(x)); 71200714 } 71300715 <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) 71400716 { 71500717 <span class="keywordflow">return</span> ((link_type)x)->value; 71600718 } 71700719 <span class="keyword">static</span> link_type& left(<a class="code" href="classOscl__Rb__Tree__Base.html#s0">base_link_type</a> x) 71800720 { 71900721 <span class="keywordflow">return</span> cast_to_link_type(x->left); 72000722 } 72100723 <span class="keyword">static</span> link_type& right(<a class="code" href="classOscl__Rb__Tree__Base.html#s0">base_link_type</a> x) 72200724 { 72300725 <span class="keywordflow">return</span> cast_to_link_type(x->right); 72400726 } 72500727 <span class="keyword">static</span> link_type& parent(<a class="code" href="classOscl__Rb__Tree__Base.html#s0">base_link_type</a> x) 72600728 { 72700729 <span class="keywordflow">return</span> cast_to_link_type(x->parent); 72800730 } 72900731 73000732 <span class="keyword">static</span> link_type minimum(link_type x) 73100733 { 73200734 <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); 73300735 } 73400736 <span class="keyword">static</span> link_type maximum(link_type x) 73500737 { 73600738 <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); 73700739 } 73800740 73900741 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) 74000742 { 74100743 link_type z; 74200744 74300745 <span class="keywordflow">if</span> (y == header || x != 0 || key_compare(KeyOfValue()(v), key(y))) 74400746 { 74500747 z = create_node(v); 74600748 left(y) = z; <span class="comment">// also makes leftmost() = z when y == header</span> 74700749 <span class="keywordflow">if</span> (y == header) 74800750 { 74900751 root() = z; 75000752 rightmost() = z; 75100753 } 75200754 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (y == leftmost()) 75300755 leftmost() = z; <span class="comment">// maintain leftmost() pointing to min node</span> 75400756 } 75500757 <span class="keywordflow">else</span> 75600758 { 75700759 z = create_node(v); 75800760 right(y) = z; 75900761 <span class="keywordflow">if</span> (y == rightmost()) 76000762 rightmost() = z; <span class="comment">// maintain rightmost() pointing to max node</span> 76100763 } 76200764 parent(z) = y; 76300765 left(z) = 0; 76400766 right(z) = 0; 76500767 <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>); 76600768 ++node_count; 76700769 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#s7">iterator</a>(z); 76800770 76900771 } 77000772 77100773 <span class="keywordtype">void</span> erase_without_rebalance(link_type x) 77200774 { 77300775 <span class="keywordflow">while</span> (x != 0) 77400776 { 77500777 erase_without_rebalance((link_type)x->right); 77600778 link_type y = (link_type)x-><a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>; 77700779 destroy_node(x); 77800780 x = y; 77900781 } 78000782 } 78100783 78200784 link_type copy(link_type x, link_type p) 78300785 { 78400786 <span class="comment">// structural copy. x and p must be non-null.</span> 78500787 link_type top = clone_node(x); 78600788 top->parent = p; 78700789 78800790 <span class="keywordflow">if</span> (x->right) 78900791 { 79000792 top->right = copy(right(x), top); 79100793 } 79200794 p = top; 79300795 x = left(x); 79400796 79500797 <span class="keywordflow">while</span> (x != 0) 79600798 { 79700799 link_type y = clone_node(x); 79800800 p->left = y; 79900801 y->parent = p; 80000802 <span class="keywordflow">if</span> (x->right) 80100803 { 80200804 y->right = copy(right(x), y); 80300805 } 80400806 p = y; 80500807 x = left(x); 80600808 } 80700809 80800810 <span class="keywordflow">return</span> top; 80900811 } 81000812 81100813 link_type get_node() 81200814 { 81300815 <span class="keywordflow">return</span> node_allocator.ALLOCATE(1); 81400816 } 81500817 <span class="keywordtype">void</span> release_node(link_type node) 81600818 { 81700819 node_allocator.<a class="code" href="classOscl__TAlloc.html#a5">deallocate</a>(node); 81800820 } 81900821 82000822 link_type create_node(<span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#s1">value_type</a>& v) 82100823 { 82200824 link_type x = get_node(); 82300825 <span class="keyword">new</span>(&x->value) <a class="code" href="classOscl__Rb__Tree.html#s1">value_type</a>(v); 82400826 <span class="keywordflow">return</span> x; 82500827 } 82600828 82700829 <span class="keywordtype">void</span> destroy_node(link_type x) 82800830 { 82900831 x->value.~Value(); 83000832 release_node(x); 83100833 } 83200834 83300835 link_type clone_node(link_type x) 83400836 { 83500837 link_type tmp = create_node(x->value); 83600838 tmp->color = x->color; 83700839 tmp->left = 0; 83800840 tmp->right = 0; 83900841 <span class="keywordflow">return</span> tmp; 84000842 } 84100843 84200844 <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> 84300845 <span class="keyword"> </span>{ 84400846 <span class="keywordflow">while</span> (first != last) 84500847 { 84600848 n++; 84700849 first++; 84800850 } 84900851 } 85000852 85100853 <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> 85200854 <span class="keyword"> </span>{ 85300855 <span class="keywordflow">while</span> (first != last) 85400856 { 85500857 n++; 85600858 first++; 85700859 } 85800860 } 85900861 }; 86000862 86100863 86200867 <span class="preprocessor">#endif</span> 86300868 <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
