Google Git
Sign in
android / platform / external / opencore / refs/heads/eclair-sholes-release2 / . / doc / oscl_html / oscl__tree_8h-source.html
blob: 8237d43f15b02e9b4de4a3fbd599560d3e6b6836 [file] [log] [blame]
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
<title>oscl_tree.h Source File</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.2.18 -->
<center>
<a class="qindex" href="index.html">Main Page</a> &nbsp; <a class="qindex" href="modules.html">Modules</a> &nbsp; <a class="qindex" href="hierarchy.html">Class Hierarchy</a> &nbsp; <a class="qindex" href="annotated.html">Data Structures</a> &nbsp; <a class="qindex" href="files.html">File List</a> &nbsp; <a class="qindex" href="functions.html">Data Fields</a> &nbsp; <a class="qindex" href="globals.html">Globals</a> &nbsp; </center>
<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>
00002 <span class="comment">// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =</span>
00003
00004 <span class="comment">// O S C L _ T R E E</span>
00005
00006 <span class="comment">// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =</span>
00007
00018 <span class="preprocessor">#ifndef OSCL_TREE_H_INCLUDED</span>
00019 <span class="preprocessor"></span><span class="preprocessor">#define OSCL_TREE_H_INCLUDED</span>
00020 <span class="preprocessor"></span>
00021 <span class="preprocessor">#ifndef OSCL_DEFALLOC_H_INCLUDED</span>
00022 <span class="preprocessor"></span><span class="preprocessor">#include "<a class="code" href="oscl__defalloc_8h.html">oscl_defalloc.h</a>"</span>
00023 <span class="preprocessor">#endif</span>
00024 <span class="preprocessor"></span>
00025 <span class="preprocessor">#ifndef OSCL_BASE_H_INCLUDED</span>
00026 <span class="preprocessor"></span><span class="preprocessor">#include "<a class="code" href="oscl__base_8h.html">oscl_base.h</a>"</span>
00027 <span class="preprocessor">#endif</span>
00028 <span class="preprocessor"></span>
<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>
00030 <span class="preprocessor"></span><span class="preprocessor">#include "<a class="code" href="osclconfig__compiler__warnings_8h.html">osclconfig_compiler_warnings.h</a>"</span>
00031
00032 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T1, <span class="keyword">class</span> T2&gt;
<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>
00034 {
<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>;
<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>;
<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()) {}
<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&amp; a, <span class="keyword">const</span> T2&amp; b) : <a class="code" href="structOscl__Pair.html#m0">first</a>(a), <a class="code" href="structOscl__Pair.html#m1">second</a>(b) {}
00039 };
00040
00041
<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>
00043 {
<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>;
<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>;
00046
<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>;
<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>;
<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>;
<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>;
00051
<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)
00053 {
00054 <span class="keywordflow">if</span> (x)
00055 {
00056 <span class="keywordflow">while</span> (x-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a> != 0) x = x-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>;
00057 }
00058 <span class="keywordflow">return</span> x;
00059 }
<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)
00061 {
00062 <span class="keywordflow">if</span> (x)
00063 {
00064 <span class="keywordflow">while</span> (x-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a> != 0) x = x-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>;
00065 }
00066 <span class="keywordflow">return</span> x;
00067 }
00068 };
00069
00070 <span class="keyword">template</span> &lt;<span class="keyword">class</span> Value&gt;
<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>
00072 {
<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>;
<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&lt;Value&gt;</a>* <a class="code" href="structOscl__Rb__Tree__Node.html">link_type</a>;
<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>;
00076 };
00077
00078
00079 <span class="keyword">template</span> &lt;<span class="keyword">class</span> Value&gt;
<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>
00081 {
<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>;
<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>&amp; <a class="code" href="structOscl__Rb__Tree__Iterator.html#s1">reference</a>;
<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>;
<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&lt;Value&gt;</a> <a class="code" href="structOscl__Rb__Tree__Iterator.html">iterator</a>;
<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&lt;Value&gt;</a> <a class="code" href="structOscl__Rb__Tree__Iterator.html">self</a>;
<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>;
<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&lt;Value&gt;</a>* <a class="code" href="structOscl__Rb__Tree__Node.html">link_type</a>;
00089
<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>;
00091
<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>() {}
<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)
00094 {
00095 node = x;
00096 }
<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&amp; it)
00098 {
00099 node = it.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>;
00100 }
00101
<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>
00103 <span class="keyword"> </span>{
00104 <span class="keywordflow">return</span> <a class="code" href="structOscl__Rb__Tree__Iterator.html#s6">link_type</a>(node)-&gt;value;
00105 }
<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-&gt;</a>()<span class="keyword"> const</span>
00107 <span class="keyword"> </span>{
00108 <span class="keywordflow">return</span> &amp;(<a class="code" href="structOscl__Rb__Tree__Iterator.html#a3">operator*</a>());
00109 }
00110
<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&amp; x)
00112 {
00113 <span class="keywordflow">return</span> node == x.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>;
00114 }
00115
<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&amp; x)
00117 {
00118 <span class="keywordflow">return</span> node != x.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>;
00119 }
00120
<a name="l00121"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a7">00121</a> self&amp; <a class="code" href="structOscl__Rb__Tree__Iterator.html#a7">operator++</a>()
00122 {
00123 <span class="keywordflow">if</span> (node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a> != 0)
00124 {
00125 node = node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>;
00126 <span class="keywordflow">while</span> (node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a> != 0)
00127 {
00128 node = node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>;
00129 }
00130 }
00131 <span class="keywordflow">else</span>
00132 {
00133 base_link_type y = node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>;
00134 <span class="keywordflow">while</span> (node == y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>)
00135 {
00136 node = y;
00137 y = y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>;
00138 }
00139 <span class="keywordflow">if</span> (node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a> != y) node = y;
00140 }
00141 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00142 }
00143
<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>)
00145 {
00146 self tmp = *<span class="keyword">this</span>;
00147 ++*<span class="keyword">this</span>;
00148 <span class="keywordflow">return</span> tmp;
00149 }
00150
<a name="l00151"></a><a class="code" href="structOscl__Rb__Tree__Iterator.html#a9">00151</a> self&amp; <a class="code" href="structOscl__Rb__Tree__Iterator.html#a9">operator--</a>()
00152 {
00153 <span class="keywordflow">if</span> (node-&gt;<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> &amp;&amp; (node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>)-&gt;parent == node)
00154 {
00155 node = node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>; <span class="comment">// return rightmost</span>
00156 }
00157 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a> != 0)
00158 {
00159 base_link_type y = node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>;
00160 <span class="keywordflow">while</span> (y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a> != 0)
00161 y = y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>;
00162 node = y;
00163 }
00164 <span class="keywordflow">else</span>
00165 {
00166 base_link_type y = node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>;
00167 <span class="keywordflow">while</span> (node == y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>)
00168 {
00169 node = y;
00170 y = y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>;
00171 }
00172 node = y;
00173 }
00174 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00175 }
00176
<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>)
00178 {
00179 self tmp = *<span class="keyword">this</span>;
00180 --*<span class="keyword">this</span>;
00181 <span class="keywordflow">return</span> tmp;
00182 }
00183 };
00184
00185
00186 <span class="keyword">template</span> &lt;<span class="keyword">class</span> Value&gt;
<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>
00188 {
<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>;
<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>&amp; <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#s1">reference</a>;
<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>;
<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&lt;Value&gt;</a> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">const_iterator</a>;
<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&lt;Value&gt;</a> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">self</a>;
<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>;
<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&lt;Value&gt;</a>* <a class="code" href="structOscl__Rb__Tree__Node.html">link_type</a>;
00196
<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>;
00198
<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>() {}
<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)
00201 {
00202 node = x;
00203 }
<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&amp; it)
00205 {
00206 node = it.<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#m0">node</a>;
00207 }
00208
<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>
00210 <span class="keyword"> </span>{
00211 <span class="keywordflow">return</span> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#s6">link_type</a>(node)-&gt;value;
00212 }
<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-&gt;</a>()<span class="keyword"> const</span>
00214 <span class="keyword"> </span>{
00215 <span class="keywordflow">return</span> &amp;(<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a3">operator*</a>());
00216 }
00217
<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&amp; x)
00219 {
00220 <span class="keywordflow">return</span> node == x.<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#m0">node</a>;
00221 }
00222
<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&amp; x)
00224 {
00225 <span class="keywordflow">return</span> node != x.<a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#m0">node</a>;
00226 }
00227
<a name="l00228"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a7">00228</a> self&amp; <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a7">operator++</a>()
00229 {
00230 <span class="keywordflow">if</span> (node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a> != 0)
00231 {
00232 node = node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>;
00233 <span class="keywordflow">while</span> (node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a> != 0)
00234 {
00235 node = node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>;
00236 }
00237 }
00238 <span class="keywordflow">else</span>
00239 {
00240 base_link_type y = node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>;
00241 <span class="keywordflow">while</span> (node == y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>)
00242 {
00243 node = y;
00244 y = y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>;
00245 }
00246 <span class="keywordflow">if</span> (node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a> != y) node = y;
00247 }
00248 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00249 }
00250
<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>)
00252 {
00253 self tmp = *<span class="keyword">this</span>;
00254 ++*<span class="keyword">this</span>;
00255 <span class="keywordflow">return</span> tmp;
00256 }
00257
<a name="l00258"></a><a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a9">00258</a> self&amp; <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html#a9">operator--</a>()
00259 {
00260 <span class="keywordflow">if</span> (node-&gt;<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> &amp;&amp; (node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>)-&gt;parent == node)
00261 {
00262 node = node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>; <span class="comment">// return rightmost</span>
00263 }
00264 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a> != 0)
00265 {
00266 base_link_type y = node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>;
00267 <span class="keywordflow">while</span> (y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a> != 0)
00268 y = y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>;
00269 node = y;
00270 }
00271 <span class="keywordflow">else</span>
00272 {
00273 base_link_type y = node-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>;
00274 <span class="keywordflow">while</span> (node == y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>)
00275 {
00276 node = y;
00277 y = y-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>;
00278 }
00279 node = y;
00280 }
00281 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00282 }
00283
<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>)
00285 {
00286 self tmp = *<span class="keyword">this</span>;
00287 --*<span class="keyword">this</span>;
00288 <span class="keywordflow">return</span> tmp;
00289 }
00290 };
00291
00292
<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>
00294 {
00295
00296 <span class="keyword">public</span>:
<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>;
00298
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&amp; root);
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&amp; root);
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&amp; root);
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,
00303 base_link_type&amp; root,
00304 base_link_type&amp; leftmost,
00305 base_link_type&amp; rightmost);
00306 };
00307
00308
00309 <span class="keyword">template</span> &lt;<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&gt;
<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>
00311 {
00312
00313 <span class="keyword">public</span>:
<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>;
<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>;
<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>;
<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>;
<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>&amp; <a class="code" href="classOscl__Rb__Tree.html#s4">reference</a>;
<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>&amp; <a class="code" href="classOscl__Rb__Tree.html#s5">const_reference</a>;
<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&lt;Value&gt;</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>;
<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&lt;value_type&gt;</a> <a class="code" href="structOscl__Rb__Tree__Iterator.html">iterator</a>;
<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&lt;value_type&gt;</a> <a class="code" href="structOscl__Rb__Tree__Const__Iterator.html">const_iterator</a>;
<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>;
<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>;
00325 <span class="keyword">private</span>:
00326 <span class="keyword">typedef</span> <span class="keyword">typename</span> <a class="code" href="structOscl__Rb__Tree__Node.html">Oscl_Rb_Tree_Node&lt;Value&gt;</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>;
00327 <span class="keyword">typedef</span> <a class="code" href="structOscl__Rb__Tree__Node.html">Oscl_Rb_Tree_Node&lt;Value&gt;</a> <a class="code" href="structOscl__Rb__Tree__Node.html">node_type</a>;
00328
00329 <span class="keyword">private</span>:
00330 link_type header;
00331 <a class="code" href="classOscl__Rb__Tree.html#s9">size_type</a> node_count;
00332 Compare key_compare;
00333 <a class="code" href="classOscl__TAlloc.html">Oscl_TAlloc&lt;node_type, Alloc&gt;</a> node_allocator;
00334
00335 <span class="keyword">public</span>:
<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&amp; comp = Compare())
00337 : node_count(0), key_compare(comp)
00338 {
00339 header = get_node();
00340 header-&gt;<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>;
00341 leftmost() = header;
00342 rightmost() = header;
00343 root() = 0;
00344 }
00345
<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&lt;Key, Value, KeyOfValue, Compare, Alloc&gt;</a>&amp; x)
00347 : node_count(0), key_compare(x.key_compare)
00348 {
00349 header = get_node();
00350 header-&gt;<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>;
00351 <span class="keywordflow">if</span> (x.root() == 0)
00352 {
00353 leftmost() = header;
00354 rightmost() = header;
00355 root() = 0;
00356 }
00357 <span class="keywordflow">else</span>
00358 {
00359 root() = copy(x.root(), header);
00360 leftmost() = minimum(root());
00361 rightmost() = maximum(root());
00362 }
00363 node_count = x.node_count;
00364 }
00365
<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>()
00367 {
00368 <a class="code" href="classOscl__Rb__Tree.html#a19">clear</a>();
00369 release_node(header);
00370 }
00371
00372 <a class="code" href="classOscl__Rb__Tree.html">Oscl_Rb_Tree&lt;Key, Value, KeyOfValue, Compare, Alloc&gt;</a>&amp;
<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&lt;Key, Value, KeyOfValue, Compare, Alloc&gt;</a>&amp; x)
00374 {
00375 <span class="keywordflow">if</span> (<span class="keyword">this</span> != &amp;x)
00376 {
00377 <a class="code" href="classOscl__Rb__Tree.html#a19">clear</a>();
00378 node_count = 0;
00379 key_compare = x.<a class="code" href="classOscl__Rb__Tree.html#o2">key_compare</a>;
00380
00381 <span class="keywordflow">if</span> (x.<a class="code" href="classOscl__Rb__Tree.html#c0">root</a>() == 0)
00382 {
00383 root() = 0;
00384 leftmost() = header;
00385 rightmost() = header;
00386 }
00387 <span class="keywordflow">else</span>
00388 {
00389 root() = copy(x.<a class="code" href="classOscl__Rb__Tree.html#c0">root</a>(), header);
00390 leftmost() = minimum(root());
00391 rightmost() = maximum(root());
00392 node_count = x.<a class="code" href="classOscl__Rb__Tree.html#o1">node_count</a>;
00393 }
00394 }
00395 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
00396 }
00397
00398 <span class="keyword">public</span>:
<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>()
00400 {
00401 <span class="keywordflow">return</span> leftmost();
00402 }
<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>
00404 <span class="keyword"> </span>{
00405 <span class="keywordflow">return</span> leftmost();
00406 }
<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>()
00408 {
00409 <span class="keywordflow">return</span> header;
00410 }
<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>
00412 <span class="keyword"> </span>{
00413 <span class="keywordflow">return</span> header;
00414 }
<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>
00416 <span class="keyword"> </span>{
00417 <span class="keywordflow">return</span> node_count == 0;
00418 }
<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>
00420 <span class="keyword"> </span>{
00421 <span class="keywordflow">return</span> node_count;
00422 }
<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>
00424 <span class="keyword"> </span>{
00425 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#s9">size_type</a>(-1);
00426 }
00427
<a name="l00428"></a><a class="code" href="classOscl__Rb__Tree.html#a11">00428</a> <a class="code" href="structOscl__Pair.html">Oscl_Pair&lt;iterator, bool&gt;</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>&amp; v)
00429 {
00430 link_type y = header;
00431 link_type x = root();
00432 <span class="keywordtype">bool</span> comp = <span class="keyword">true</span>;
00433 <span class="keywordflow">while</span> (x != 0)
00434 {
00435 y = x;
00436 comp = key_compare(KeyOfValue()(v), key(x));
00437 x = comp ? left(x) : right(x);
00438 }
00439 iterator j = <a class="code" href="classOscl__Rb__Tree.html#s7">iterator</a>(y);
00440 <span class="keywordflow">if</span> (comp)
00441 {
00442 <span class="keywordflow">if</span> (j == <a class="code" href="classOscl__Rb__Tree.html#a4">begin</a>())
00443 <span class="keywordflow">return</span> <a class="code" href="structOscl__Pair.html">Oscl_Pair&lt;iterator, bool&gt;</a>(insert(x, y, v), <span class="keyword">true</span>);
00444 <span class="keywordflow">else</span>
00445 --j;
00446 }
00447 <span class="keywordflow">if</span> (key_compare(key(j.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>), KeyOfValue()(v)))
00448 <span class="keywordflow">return</span> <a class="code" href="structOscl__Pair.html">Oscl_Pair&lt;iterator, bool&gt;</a>(insert(x, y, v), <span class="keyword">true</span>);
00449
00450 <span class="keywordflow">return</span> <a class="code" href="structOscl__Pair.html">Oscl_Pair&lt;iterator, bool&gt;</a>(j, <span class="keyword">false</span>);
00451 }
00452
<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>&amp; v)
00454 {
00455 <span class="keywordflow">if</span> (position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a> == header-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>) <span class="comment">// begin()</span>
00456 {
00457 <span class="keywordflow">if</span> (<a class="code" href="classOscl__Rb__Tree.html#a9">size</a>() &gt; 0 &amp;&amp; key_compare(KeyOfValue()(v), key(position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>)))
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);
00459 <span class="comment">// first argument just needs to be non-null</span>
00460 <span class="keywordflow">else</span>
00461 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#a11">insert_unique</a>(v).first;
00462 }
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>
00464 {
00465 <span class="keywordflow">if</span> (key_compare(key(rightmost()), KeyOfValue()(v)))
00466 <span class="keywordflow">return</span> insert(0, rightmost(), v);
00467 <span class="keywordflow">else</span>
00468 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#a11">insert_unique</a>(v).first;
00469 }
00470 <span class="keywordflow">else</span>
00471 {
00472 iterator before = position;
00473 --before;
00474 <span class="keywordflow">if</span> (key_compare(key(before.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>), KeyOfValue()(v))
00475 &amp;&amp; key_compare(KeyOfValue()(v), key(position.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>)))
00476 {
00477 <span class="keywordflow">if</span> (right(before.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>) == 0)
00478 <span class="keywordflow">return</span> insert(0, (link_type)before.<a class="code" href="structOscl__Rb__Tree__Iterator.html#m0">node</a>, v);
00479 <span class="keywordflow">else</span>
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);
00481 <span class="comment">// first argument just needs to be non-null</span>
00482 }
00483 <span class="keywordflow">else</span>
00484 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#a11">insert_unique</a>(v).first;
00485 }
00486 }
00487
<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)
00489 {
00490 <span class="keywordflow">for</span> (; first != last; ++first)
00491 <a class="code" href="classOscl__Rb__Tree.html#a11">insert_unique</a>(*first);
00492 }
00493
<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)
00495 {
00496 <span class="keywordflow">for</span> (; first != last; ++first)
00497 <a class="code" href="classOscl__Rb__Tree.html#a11">insert_unique</a>(*first);
00498 }
00499
<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)
00501 {
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>,
00503 header-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>,
00504 header-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>,
00505 header-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>);
00506
00507 destroy_node(y);
00508 --node_count;
00509 }
00510
<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>&amp; x)
00512 {
00513 <a class="code" href="structOscl__Pair.html">Oscl_Pair&lt;iterator, iterator&gt;</a> p = <a class="code" href="classOscl__Rb__Tree.html#a27">equal_range</a>(x);
00514 <a class="code" href="classOscl__Rb__Tree.html#s9">size_type</a> n = 0;
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);
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>);
00517 <span class="keywordflow">return</span> n;
00518 }
00519
<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)
00521 {
00522 <span class="keywordflow">if</span> (first == <a class="code" href="classOscl__Rb__Tree.html#a4">begin</a>() &amp;&amp; last == <a class="code" href="classOscl__Rb__Tree.html#a6">end</a>())
00523 <a class="code" href="classOscl__Rb__Tree.html#a19">clear</a>();
00524 <span class="keywordflow">else</span>
00525 <span class="keywordflow">while</span> (first != last) <a class="code" href="classOscl__Rb__Tree.html#a15">erase</a>(first++);
00526 }
00527
<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)
00529 {
00530 <span class="keywordflow">while</span> (first != last) <a class="code" href="classOscl__Rb__Tree.html#a15">erase</a>(*first++);
00531 }
00532
<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>()
00534 {
00535 <span class="keywordflow">if</span> (node_count != 0)
00536 {
00537 erase_without_rebalance(root());
00538 leftmost() = header;
00539 root() = 0;
00540 rightmost() = header;
00541 node_count = 0;
00542 }
00543 }
00544
<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&amp; k)
00546 {
00547 link_type y = header; <span class="comment">// Last node which is not less than k.</span>
00548 link_type x = root(); <span class="comment">// Current node.</span>
00549
00550 <span class="keywordflow">while</span> (x != 0)
00551 {
00552 <span class="keywordflow">if</span> (!key_compare(key(x), k))
00553 y = x, x = left(x);
00554 <span class="keywordflow">else</span>
00555 x = right(x);
00556 }
00557 iterator j = <a class="code" href="classOscl__Rb__Tree.html#s7">iterator</a>(y);
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;
00559 }
00560
<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&amp; k)<span class="keyword"> const</span>
00562 <span class="keyword"> </span>{
00563 link_type y = header; <span class="comment">/* Last node which is not less than k. */</span>
00564 link_type x = root(); <span class="comment">/* Current node. */</span>
00565
00566 <span class="keywordflow">while</span> (x != 0)
00567 {
00568 <span class="keywordflow">if</span> (!key_compare(key(x), k))
00569 y = x, x = left(x);
00570 <span class="keywordflow">else</span>
00571 x = right(x);
00572 }
00573 const_iterator j = <a class="code" href="classOscl__Rb__Tree.html#s8">const_iterator</a>(y);
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;
00575 }
00576
<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&amp; k)<span class="keyword"> const</span>
00578 <span class="keyword"> </span>{
00579 <a class="code" href="structOscl__Pair.html">Oscl_Pair&lt;const_iterator, const_iterator&gt;</a> p = <a class="code" href="classOscl__Rb__Tree.html#a27">equal_range</a>(k);
00580 <a class="code" href="classOscl__Rb__Tree.html#s9">size_type</a> n = 0;
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);
00582 <span class="keywordflow">return</span> n;
00583 }
00584
<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&amp; k)
00586 {
00587 link_type y = header; <span class="comment">/* Last node which is not less than k. */</span>
00588 link_type x = root(); <span class="comment">/* Current node. */</span>
00589
00590 <span class="keywordflow">while</span> (x != 0)
00591 {
00592 <span class="keywordflow">if</span> (!key_compare(key(x), k))
00593 {
00594 y = x;
00595 x = left(x);
00596 }
00597 <span class="keywordflow">else</span>
00598 x = right(x);
00599 }
00600 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#s7">iterator</a>(y);
00601 }
00602
<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&amp; k)<span class="keyword"> const</span>
00604 <span class="keyword"> </span>{
00605 link_type y = header; <span class="comment">/* Last node which is not less than k. */</span>
00606 link_type x = root(); <span class="comment">/* Current node. */</span>
00607
00608 <span class="keywordflow">while</span> (x != 0)
00609 {
00610 <span class="keywordflow">if</span> (!key_compare(key(x), k))
00611 {
00612 y = x;
00613 x = left(x);
00614 }
00615 <span class="keywordflow">else</span>
00616 x = right(x);
00617 }
00618 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#s8">const_iterator</a>(y);
00619 }
00620
<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&amp; k)
00622 {
00623 link_type y = header; <span class="comment">/* Last node which is greater than k. */</span>
00624 link_type x = root(); <span class="comment">/* Current node. */</span>
00625
00626 <span class="keywordflow">while</span> (x != 0)
00627 {
00628 <span class="keywordflow">if</span> (key_compare(k, key(x)))
00629 {
00630 y = x;
00631 x = left(x);
00632 }
00633 <span class="keywordflow">else</span>
00634 x = right(x);
00635 }
00636 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#s7">iterator</a>(y);
00637 }
00638
<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&amp; k)<span class="keyword"> const</span>
00640 <span class="keyword"> </span>{
00641 link_type y = header; <span class="comment">/* Last node which is greater than k. */</span>
00642 link_type x = root(); <span class="comment">/* Current node. */</span>
00643
00644 <span class="keywordflow">while</span> (x != 0)
00645 {
00646 <span class="keywordflow">if</span> (key_compare(k, key(x)))
00647 {
00648 y = x;
00649 x = left(x);
00650 }
00651 <span class="keywordflow">else</span>
00652 x = right(x);
00653 }
00654 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#s8">const_iterator</a>(y);
00655 }
00656
<a name="l00657"></a><a class="code" href="classOscl__Rb__Tree.html#a27">00657</a> <a class="code" href="structOscl__Pair.html">Oscl_Pair&lt;iterator, iterator&gt;</a> <a class="code" href="classOscl__Rb__Tree.html#a27">equal_range</a>(<span class="keyword">const</span> Key&amp; k)
00658 {
00659 <span class="keywordflow">return</span> <a class="code" href="structOscl__Pair.html">Oscl_Pair&lt;iterator, iterator&gt;</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));
00660 }
00661
<a name="l00662"></a><a class="code" href="classOscl__Rb__Tree.html#a28">00662</a> <a class="code" href="structOscl__Pair.html">Oscl_Pair&lt;const_iterator, const_iterator&gt;</a> <a class="code" href="classOscl__Rb__Tree.html#a27">equal_range</a>(<span class="keyword">const</span> Key&amp; k)<span class="keyword"> const</span>
00663 <span class="keyword"> </span>{
00664 <span class="keywordflow">return</span> <a class="code" href="structOscl__Pair.html">Oscl_Pair&lt;const_iterator, const_iterator&gt;</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));
00665 }
00666
00667 <span class="keyword">private</span>:
00668 <span class="comment">// this helper function performs a downcast from base_link_type&amp; to link_type&amp;</span>
00669 <span class="comment">// under C99 (gcc 3.x) this breaks aliasing rules so we have to go via a void** instead</span>
00670 <span class="keyword">inline</span> <span class="keyword">static</span> link_type&amp; cast_to_link_type(<a class="code" href="classOscl__Rb__Tree__Base.html#s0">base_link_type</a> &amp;node)
00671 {
00672 <span class="keywordtype">void</span>** ptr = (<span class="keywordtype">void</span>**) &amp; node;
00673 link_type* base = (link_type*) ptr;
00674 <span class="keywordflow">return</span> *base;
00675 }
00676
00677 link_type&amp; root()<span class="keyword"> const</span>
00678 <span class="keyword"> </span>{
00679 <span class="keywordflow">return</span> cast_to_link_type(header-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>);
00680 }
00681 link_type&amp; leftmost()<span class="keyword"> const</span>
00682 <span class="keyword"> </span>{
00683 <span class="keywordflow">return</span> cast_to_link_type(header-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>);
00684 }
00685 link_type&amp; rightmost()<span class="keyword"> const</span>
00686 <span class="keyword"> </span>{
00687 <span class="keywordflow">return</span> cast_to_link_type(header-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m3">right</a>);
00688 }
00689
00690 <span class="keyword">const</span> Key&amp; key(link_type x)<span class="keyword"> const</span>
00691 <span class="keyword"> </span>{
00692 <span class="keywordflow">return</span> KeyOfValue()(value(x));
00693 }
00694 <span class="keyword">static</span> <a class="code" href="classOscl__Rb__Tree.html#s4">reference</a> value(link_type x)
00695 {
00696 <span class="keywordflow">return</span> x-&gt;value;
00697 }
00698 <span class="keyword">static</span> link_type&amp; left(link_type x)
00699 {
00700 <span class="keywordflow">return</span> cast_to_link_type(x-&gt;left);
00701 }
00702 <span class="keyword">static</span> link_type&amp; right(link_type x)
00703 {
00704 <span class="keywordflow">return</span> cast_to_link_type(x-&gt;right);
00705 }
00706 <span class="keyword">static</span> link_type&amp; parent(link_type x)
00707 {
00708 <span class="keywordflow">return</span> cast_to_link_type(x-&gt;parent);
00709 }
00710
00711 <span class="keyword">const</span> Key&amp; key(<a class="code" href="classOscl__Rb__Tree__Base.html#s0">base_link_type</a> x)<span class="keyword"> const</span>
00712 <span class="keyword"> </span>{
00713 <span class="keywordflow">return</span> KeyOfValue()(value(x));
00714 }
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)
00716 {
00717 <span class="keywordflow">return</span> ((link_type)x)-&gt;value;
00718 }
00719 <span class="keyword">static</span> link_type&amp; left(<a class="code" href="classOscl__Rb__Tree__Base.html#s0">base_link_type</a> x)
00720 {
00721 <span class="keywordflow">return</span> cast_to_link_type(x-&gt;left);
00722 }
00723 <span class="keyword">static</span> link_type&amp; right(<a class="code" href="classOscl__Rb__Tree__Base.html#s0">base_link_type</a> x)
00724 {
00725 <span class="keywordflow">return</span> cast_to_link_type(x-&gt;right);
00726 }
00727 <span class="keyword">static</span> link_type&amp; parent(<a class="code" href="classOscl__Rb__Tree__Base.html#s0">base_link_type</a> x)
00728 {
00729 <span class="keywordflow">return</span> cast_to_link_type(x-&gt;parent);
00730 }
00731
00732 <span class="keyword">static</span> link_type minimum(link_type x)
00733 {
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);
00735 }
00736 <span class="keyword">static</span> link_type maximum(link_type x)
00737 {
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);
00739 }
00740
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>&amp; v)
00742 {
00743 link_type z;
00744
00745 <span class="keywordflow">if</span> (y == header || x != 0 || key_compare(KeyOfValue()(v), key(y)))
00746 {
00747 z = create_node(v);
00748 left(y) = z; <span class="comment">// also makes leftmost() = z when y == header</span>
00749 <span class="keywordflow">if</span> (y == header)
00750 {
00751 root() = z;
00752 rightmost() = z;
00753 }
00754 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (y == leftmost())
00755 leftmost() = z; <span class="comment">// maintain leftmost() pointing to min node</span>
00756 }
00757 <span class="keywordflow">else</span>
00758 {
00759 z = create_node(v);
00760 right(y) = z;
00761 <span class="keywordflow">if</span> (y == rightmost())
00762 rightmost() = z; <span class="comment">// maintain rightmost() pointing to max node</span>
00763 }
00764 parent(z) = y;
00765 left(z) = 0;
00766 right(z) = 0;
00767 <a class="code" href="classOscl__Rb__Tree__Base.html#a2">rebalance</a>(z, header-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m1">parent</a>);
00768 ++node_count;
00769 <span class="keywordflow">return</span> <a class="code" href="classOscl__Rb__Tree.html#s7">iterator</a>(z);
00770
00771 }
00772
00773 <span class="keywordtype">void</span> erase_without_rebalance(link_type x)
00774 {
00775 <span class="keywordflow">while</span> (x != 0)
00776 {
00777 erase_without_rebalance((link_type)x-&gt;right);
00778 link_type y = (link_type)x-&gt;<a class="code" href="structOscl__Rb__Tree__Node__Base.html#m2">left</a>;
00779 destroy_node(x);
00780 x = y;
00781 }
00782 }
00783
00784 link_type copy(link_type x, link_type p)
00785 {
00786 <span class="comment">// structural copy. x and p must be non-null.</span>
00787 link_type top = clone_node(x);
00788 top-&gt;parent = p;
00789
00790 <span class="keywordflow">if</span> (x-&gt;right)
00791 {
00792 top-&gt;right = copy(right(x), top);
00793 }
00794 p = top;
00795 x = left(x);
00796
00797 <span class="keywordflow">while</span> (x != 0)
00798 {
00799 link_type y = clone_node(x);
00800 p-&gt;left = y;
00801 y-&gt;parent = p;
00802 <span class="keywordflow">if</span> (x-&gt;right)
00803 {
00804 y-&gt;right = copy(right(x), y);
00805 }
00806 p = y;
00807 x = left(x);
00808 }
00809
00810 <span class="keywordflow">return</span> top;
00811 }
00812
00813 link_type get_node()
00814 {
00815 <span class="keywordflow">return</span> node_allocator.ALLOCATE(1);
00816 }
00817 <span class="keywordtype">void</span> release_node(link_type node)
00818 {
00819 node_allocator.<a class="code" href="classOscl__TAlloc.html#a5">deallocate</a>(node);
00820 }
00821
00822 link_type create_node(<span class="keyword">const</span> <a class="code" href="classOscl__Rb__Tree.html#s1">value_type</a>&amp; v)
00823 {
00824 link_type x = get_node();
00825 <span class="keyword">new</span>(&amp;x-&gt;value) <a class="code" href="classOscl__Rb__Tree.html#s1">value_type</a>(v);
00826 <span class="keywordflow">return</span> x;
00827 }
00828
00829 <span class="keywordtype">void</span> destroy_node(link_type x)
00830 {
00831 x-&gt;value.~Value();
00832 release_node(x);
00833 }
00834
00835 link_type clone_node(link_type x)
00836 {
00837 link_type tmp = create_node(x-&gt;value);
00838 tmp-&gt;color = x-&gt;color;
00839 tmp-&gt;left = 0;
00840 tmp-&gt;right = 0;
00841 <span class="keywordflow">return</span> tmp;
00842 }
00843
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>&amp; n)<span class="keyword"> const</span>
00845 <span class="keyword"> </span>{
00846 <span class="keywordflow">while</span> (first != last)
00847 {
00848 n++;
00849 first++;
00850 }
00851 }
00852
00853 <span class="keywordtype">void</span> distance(iterator first, iterator last, <a class="code" href="classOscl__Rb__Tree.html#s9">size_type</a>&amp; n)<span class="keyword"> const</span>
00854 <span class="keyword"> </span>{
00855 <span class="keywordflow">while</span> (first != last)
00856 {
00857 n++;
00858 first++;
00859 }
00860 }
00861 };
00862
00863
00867 <span class="preprocessor">#endif</span>
00868 <span class="preprocessor"></span>
</pre></div><hr size="1"><img src="pvlogo_small.jpg"><address style="align: right;"><small>OSCL API</small>
<address style="align: left;"><small>Posting Version: OPENCORE_20090310 </small>
</small></address>
</body>
</html>