| <!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_priqueue.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> <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> |
| <hr><h1>oscl_priqueue.h</h1><a href="oscl__priqueue_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 _ P R I Q U E U E ( P R I O R I T Y Q U E U E )</span> |
| 00005 |
| 00006 <span class="comment">// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =</span> |
| 00007 |
| 00014 <span class="preprocessor">#ifndef OSCL_PRIQUEUE_H_INCLUDED</span> |
| 00015 <span class="preprocessor"></span><span class="preprocessor">#define OSCL_PRIQUEUE_H_INCLUDED</span> |
| 00016 <span class="preprocessor"></span> |
| 00017 |
| 00018 |
| 00030 <span class="preprocessor">#ifndef OSCL_BASE_H_INCLUDED</span> |
| 00031 <span class="preprocessor"></span><span class="preprocessor">#include "<a class="code" href="oscl__base_8h.html">oscl_base.h</a>"</span> |
| 00032 <span class="preprocessor">#endif</span> |
| 00033 <span class="preprocessor"></span> |
| 00034 |
| 00035 <span class="preprocessor">#ifndef OSCL_VECTOR_H_INCLUDED</span> |
| 00036 <span class="preprocessor"></span><span class="preprocessor">#include "<a class="code" href="oscl__vector_8h.html">oscl_vector.h</a>"</span> |
| 00037 <span class="preprocessor">#endif</span> |
| 00038 <span class="preprocessor"></span> |
| <a name="l00046"></a><a class="code" href="classOsclPriorityQueueBase.html">00046</a> <span class="keyword">class </span><a class="code" href="classOsclPriorityQueueBase.html">OsclPriorityQueueBase</a> |
| 00047 { |
| 00048 <span class="keyword">protected</span>: |
| <a name="l00049"></a><a class="code" href="classOsclPriorityQueueBase.html#b0">00049</a> <span class="keyword">virtual</span> <a class="code" href="classOsclPriorityQueueBase.html#b0">~OsclPriorityQueueBase</a>() |
| 00050 {} |
| 00051 |
| 00052 OSCL_IMPORT_REF <span class="keywordtype">void</span> <a class="code" href="classOsclPriorityQueueBase.html#b1">push_heap</a>(<a class="code" href="group__osclbase.html#a25">OsclAny</a>* first, <a class="code" href="group__osclbase.html#a25">OsclAny</a>* last) ; |
| 00053 |
| 00054 OSCL_IMPORT_REF <span class="keywordtype">void</span> <a class="code" href="classOsclPriorityQueueBase.html#b2">pop_heap</a>(<a class="code" href="group__osclbase.html#a25">OsclAny</a>* first, <a class="code" href="group__osclbase.html#a25">OsclAny</a>* last) ; |
| 00055 |
| 00056 OSCL_IMPORT_REF <a class="code" href="group__osclbase.html#a25">OsclAny</a>* <a class="code" href="classOsclPriorityQueueBase.html#b3">find_heap</a>(<span class="keyword">const</span> <a class="code" href="group__osclbase.html#a25">OsclAny</a>* input, <a class="code" href="group__osclbase.html#a25">OsclAny</a>* first, <a class="code" href="group__osclbase.html#a25">OsclAny</a>* last) ; |
| 00057 |
| 00058 OSCL_IMPORT_REF <span class="keywordtype">int</span> <a class="code" href="classOsclPriorityQueueBase.html#b4">remove</a>(<span class="keyword">const</span> <a class="code" href="group__osclbase.html#a25">OsclAny</a>* input) ; |
| 00059 |
| <a name="l00060"></a><a class="code" href="classOsclPriorityQueueBase.html#b5">00060</a> <span class="keywordtype">void</span> <a class="code" href="classOsclPriorityQueueBase.html#b5">construct</a>(<a class="code" href="classOscl__Opaque__Type__Compare.html">Oscl_Opaque_Type_Compare</a>* ot, <a class="code" href="classOscl__Vector__Base.html">Oscl_Vector_Base</a>* vec) |
| 00061 { |
| 00062 pOpaqueType = ot; |
| 00063 pVec = vec; |
| 00064 } |
| 00065 |
| 00066 <span class="keyword">private</span>: |
| 00067 |
| 00068 <span class="comment">//return delta from "first" to "last" expressed as a number of T elements.</span> |
| 00069 <span class="keywordtype">int</span> delta_T(<a class="code" href="group__osclbase.html#a25">OsclAny</a>*first, <a class="code" href="group__osclbase.html#a25">OsclAny</a>*last) |
| 00070 { |
| 00071 <span class="keywordflow">return</span> ((int)last -(int)first) / pVec-><a class="code" href="classOscl__Vector__Base.html#n3">sizeof_T</a>; |
| 00072 } |
| 00073 |
| 00074 <a class="code" href="classOscl__Opaque__Type__Compare.html">Oscl_Opaque_Type_Compare</a>* pOpaqueType; |
| 00075 <a class="code" href="classOscl__Vector__Base.html">Oscl_Vector_Base</a>* pVec; |
| 00076 }; |
| 00077 |
| <a name="l00078"></a><a class="code" href="classOsclCompareLess.html">00078</a> <span class="keyword">template</span> < <span class="keyword">class</span> T> <span class="keyword">class </span><a class="code" href="classOsclCompareLess.html">OsclCompareLess</a> |
| 00079 { |
| 00080 <span class="keyword">public</span>: |
| <a name="l00081"></a><a class="code" href="classOsclCompareLess.html#a0">00081</a> <span class="keywordtype">int</span> <a class="code" href="classOsclCompareLess.html#a0">compare</a>(T& a, T& b)<span class="keyword"> const</span> |
| 00082 <span class="keyword"> </span>{ |
| 00083 <span class="keywordflow">return</span> (a < b); |
| 00084 } |
| 00085 }; |
| 00086 |
| 00087 |
| 00088 |
| 00089 |
| 00090 |
| 00091 |
| 00092 |
| 00093 |
| 00094 <span class="keyword">template</span> < <span class="keyword">class </span>Qelem, <span class="keyword">class </span>Alloc, |
| 00095 <span class="keyword">class </span>Container = <a class="code" href="classOscl__Vector.html">Oscl_Vector<Qelem, Alloc></a>, |
| 00096 <span class="keyword">class </span>Compare = <a class="code" href="classOsclCompareLess.html">OsclCompareLess<Qelem></a> > |
| 00097 |
| <a name="l00098"></a><a class="code" href="classOsclPriorityQueue.html">00098</a> <span class="keyword">class </span><a class="code" href="classOsclPriorityQueue.html">OsclPriorityQueue</a> : <span class="keyword">public</span> <a class="code" href="classOsclPriorityQueueBase.html">OsclPriorityQueueBase</a> |
| 00099 , <span class="keyword">public</span> <a class="code" href="classOscl__Opaque__Type__Compare.html">Oscl_Opaque_Type_Compare</a> |
| 00100 { |
| 00101 |
| 00102 <span class="keyword">public</span>: |
| <a name="l00103"></a><a class="code" href="classOsclPriorityQueue.html#s0">00103</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> Container::value_type <a class="code" href="classOscl__Vector.html">value_type</a>; |
| <a name="l00104"></a><a class="code" href="classOsclPriorityQueue.html#s1">00104</a> <span class="keyword">typedef</span> Container <a class="code" href="classOscl__Vector.html">container_type</a>; |
| <a name="l00105"></a><a class="code" href="classOsclPriorityQueue.html#s2">00105</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> Container::iterator <a class="code" href="classOscl__Vector.html">iterator</a>; |
| <a name="l00106"></a><a class="code" href="classOsclPriorityQueue.html#s3">00106</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> Container::const_reference <a class="code" href="classOscl__Vector.html">const_reference</a>; |
| 00107 |
| <a name="l00108"></a><a class="code" href="classOsclPriorityQueue.html#a0">00108</a> <span class="keywordtype">bool</span> <a class="code" href="classOsclPriorityQueue.html#a0">empty</a>()<span class="keyword"> const</span> |
| 00109 <span class="keyword"> </span>{ |
| 00110 <span class="keywordflow">return</span> <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.empty(); |
| 00111 }; |
| <a name="l00112"></a><a class="code" href="classOsclPriorityQueue.html#a1">00112</a> uint32 <a class="code" href="classOsclPriorityQueue.html#a1">size</a>()<span class="keyword"> const</span> |
| 00113 <span class="keyword"> </span>{ |
| 00114 <span class="keywordflow">return</span> <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.size(); |
| 00115 }; |
| <a name="l00116"></a><a class="code" href="classOsclPriorityQueue.html#a2">00116</a> <span class="keywordtype">void</span> <a class="code" href="classOsclPriorityQueue.html#a2">reserve</a>(uint32 n) |
| 00117 { |
| 00118 <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.reserve(n); |
| 00119 }; |
| <a name="l00120"></a><a class="code" href="classOsclPriorityQueue.html#a3">00120</a> <a class="code" href="classOscl__Vector.html">const_reference</a> <a class="code" href="classOsclPriorityQueue.html#a3">top</a>()<span class="keyword"> const</span> |
| 00121 <span class="keyword"> </span>{ |
| 00122 <span class="keywordflow">return</span> <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.front(); |
| 00123 }; |
| <a name="l00124"></a><a class="code" href="classOsclPriorityQueue.html#a4">00124</a> <span class="keyword">const</span> Container & <a class="code" href="classOsclPriorityQueue.html#a4">vec</a>() |
| 00125 { |
| 00126 <span class="keywordflow">return</span> <a class="code" href="classOsclPriorityQueue.html#n0">c</a>; |
| 00127 } |
| 00128 |
| <a name="l00129"></a><a class="code" href="classOsclPriorityQueue.html#a5">00129</a> <span class="keywordtype">void</span> <a class="code" href="classOsclPriorityQueue.html#a5">push</a>(<span class="keyword">const</span> <a class="code" href="classOscl__Vector.html">value_type</a>& input) |
| 00130 { |
| 00131 <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.push_back(input); |
| 00132 <a class="code" href="classOsclPriorityQueue.html#b0">push_heap</a>(<a class="code" href="classOsclPriorityQueue.html#n0">c</a>.begin(), <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.end()); |
| 00133 } |
| 00134 |
| 00135 <span class="comment">//remove top element</span> |
| <a name="l00136"></a><a class="code" href="classOsclPriorityQueue.html#a6">00136</a> <span class="keywordtype">void</span> <a class="code" href="classOsclPriorityQueue.html#a6">pop</a>() |
| 00137 { |
| 00138 <a class="code" href="classOsclPriorityQueue.html#b1">pop_heap</a>(<a class="code" href="classOsclPriorityQueue.html#n0">c</a>.begin(), <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.end()); |
| 00139 <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.pop_back(); |
| 00140 } |
| 00141 |
| 00142 <span class="comment">//Remove an arbitrary element, by value.</span> |
| 00143 <span class="comment">//If there are multiple matches, this removes the first one it finds.</span> |
| 00144 <span class="comment">//Returns number of items removed(either 0 or 1).</span> |
| <a name="l00145"></a><a class="code" href="classOsclPriorityQueue.html#a7">00145</a> <span class="keywordtype">int</span> <a class="code" href="classOsclPriorityQueue.html#a7">remove</a>(<span class="keyword">const</span> <a class="code" href="classOscl__Vector.html">value_type</a>& input) |
| 00146 { |
| 00147 <span class="keywordflow">return</span> <a class="code" href="classOsclPriorityQueueBase.html#b4">OsclPriorityQueueBase::remove</a>(&input); |
| 00148 } |
| 00149 |
| 00150 <span class="comment">//Constructor</span> |
| <a name="l00151"></a><a class="code" href="classOsclPriorityQueue.html#a8">00151</a> <a class="code" href="classOsclPriorityQueue.html#a8">OsclPriorityQueue</a>(): <a class="code" href="classOsclPriorityQueueBase.html">OsclPriorityQueueBase</a>(), <a class="code" href="classOscl__Opaque__Type__Compare.html">Oscl_Opaque_Type_Compare</a>() |
| 00152 , <a class="code" href="classOsclPriorityQueue.html#n0">c</a>() |
| 00153 { |
| 00154 <a class="code" href="classOsclPriorityQueueBase.html#b5">OsclPriorityQueueBase::construct</a>(<span class="keyword">this</span>, &<a class="code" href="classOsclPriorityQueue.html#n0">c</a>); |
| 00155 } |
| 00156 |
| <a name="l00157"></a><a class="code" href="classOsclPriorityQueue.html#a9">00157</a> <span class="keyword">virtual</span> <a class="code" href="classOsclPriorityQueue.html#a9">~OsclPriorityQueue</a>() |
| 00158 {} |
| 00159 |
| 00160 <span class="keyword">protected</span>: |
| <a name="l00161"></a><a class="code" href="classOsclPriorityQueue.html#n0">00161</a> Container <a class="code" href="classOsclPriorityQueue.html#n0">c</a>; |
| <a name="l00162"></a><a class="code" href="classOsclPriorityQueue.html#n1">00162</a> Compare <a class="code" href="classOsclPriorityQueue.html#n1">comp</a>; |
| 00163 |
| 00164 |
| <a name="l00165"></a><a class="code" href="classOsclPriorityQueue.html#b0">00165</a> <span class="keywordtype">void</span> <a class="code" href="classOsclPriorityQueue.html#b0">push_heap</a>(<a class="code" href="classOscl__Vector.html">iterator</a> first, <a class="code" href="classOscl__Vector.html">iterator</a> last) |
| 00166 { |
| 00167 <a class="code" href="classOsclPriorityQueueBase.html#b1">OsclPriorityQueueBase::push_heap</a>(first, last); |
| 00168 } |
| 00169 |
| <a name="l00170"></a><a class="code" href="classOsclPriorityQueue.html#b1">00170</a> <span class="keywordtype">void</span> <a class="code" href="classOsclPriorityQueue.html#b1">pop_heap</a>(<a class="code" href="classOscl__Vector.html">iterator</a> first, <a class="code" href="classOscl__Vector.html">iterator</a> last) |
| 00171 { |
| 00172 <a class="code" href="classOsclPriorityQueueBase.html#b2">OsclPriorityQueueBase::pop_heap</a>(first, last); |
| 00173 } |
| 00174 |
| <a name="l00175"></a><a class="code" href="classOsclPriorityQueue.html#b2">00175</a> <a class="code" href="classOscl__Vector.html">iterator</a> <a class="code" href="classOsclPriorityQueue.html#b2">find_heap</a>(<span class="keyword">const</span> <a class="code" href="classOscl__Vector.html">value_type</a>& input, <a class="code" href="classOscl__Vector.html">iterator</a> first, <a class="code" href="classOscl__Vector.html">iterator</a> last) |
| 00176 { |
| 00177 <span class="keywordflow">return</span> <a class="code" href="classOsclPriorityQueueBase.html#b3">OsclPriorityQueueBase::find_heap</a>(&input, first, last); |
| 00178 } |
| 00179 |
| 00180 <span class="comment">//a debug routine for validating the current sort.</span> |
| <a name="l00181"></a><a class="code" href="classOsclPriorityQueue.html#b3">00181</a> <span class="keywordtype">int</span> <a class="code" href="classOsclPriorityQueue.html#b3">validate</a>() |
| 00182 { |
| 00183 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> ch; |
| 00184 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> par = 0;par < <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.size();par++) |
| 00185 { |
| 00186 ch = 2 * par + 1; |
| 00187 <span class="keywordflow">if</span> (ch < <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.size() && <a class="code" href="classOsclPriorityQueue.html#n1">comp</a>.compare(<a class="code" href="classOsclPriorityQueue.html#n0">c</a>[par], <a class="code" href="classOsclPriorityQueue.html#n0">c</a>[ch])) |
| 00188 <span class="keywordflow">return</span> par;<span class="comment">//error-- parent<child</span> |
| 00189 ch++; |
| 00190 <span class="keywordflow">if</span> (ch < <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.size() && <a class="code" href="classOsclPriorityQueue.html#n1">comp</a>.compare(<a class="code" href="classOsclPriorityQueue.html#n0">c</a>[par], <a class="code" href="classOsclPriorityQueue.html#n0">c</a>[ch])) |
| 00191 <span class="keywordflow">return</span> par;<span class="comment">//error-- parent<child</span> |
| 00192 } |
| 00193 <span class="keywordflow">return</span> -1;<span class="comment">//ok</span> |
| 00194 } |
| 00195 |
| <a name="l00196"></a><a class="code" href="classOsclPriorityQueue.html#l0">00196</a> <span class="keyword">friend</span> <span class="keyword">class </span><a class="code" href="classOsclPriorityQueue.html#l0">oscl_priqueue_test</a>; |
| 00197 |
| 00198 <span class="comment">//from Oscl_Opaque_Type_Compare</span> |
| <a name="l00199"></a><a class="code" href="classOsclPriorityQueue.html#b4">00199</a> <span class="keywordtype">void</span> <a class="code" href="classOsclPriorityQueue.html#b4">swap</a>(<a class="code" href="group__osclbase.html#a25">OsclAny</a>* dest, <span class="keyword">const</span> <a class="code" href="group__osclbase.html#a25">OsclAny</a>* src) |
| 00200 { |
| 00201 <a class="code" href="group__osclbase.html#a78">OSCL_ASSERT</a>(dest); |
| 00202 <a class="code" href="group__osclbase.html#a78">OSCL_ASSERT</a>(src); |
| 00203 <span class="keywordflow">if</span> (dest != src) |
| 00204 { |
| 00205 <a class="code" href="classOscl__Vector.html">value_type</a> temp(*((<a class="code" href="classOscl__Vector.html">value_type</a>*)dest)); |
| 00206 *((<a class="code" href="classOscl__Vector.html">value_type</a>*)dest) = *((<a class="code" href="classOscl__Vector.html">value_type</a>*)src); |
| 00207 *((<a class="code" href="classOscl__Vector.html">value_type</a>*)src) = temp; |
| 00208 } |
| 00209 } |
| 00210 |
| 00211 <span class="comment">//from Oscl_Opaque_Type_Compare</span> |
| <a name="l00212"></a><a class="code" href="classOsclPriorityQueue.html#b5">00212</a> <span class="keywordtype">int</span> <a class="code" href="classOsclPriorityQueue.html#b5">compare_LT</a>(<a class="code" href="group__osclbase.html#a25">OsclAny</a>* a, <a class="code" href="group__osclbase.html#a25">OsclAny</a>* b)<span class="keyword"> const</span> |
| 00213 <span class="keyword"> </span>{ |
| 00214 <a class="code" href="group__osclbase.html#a78">OSCL_ASSERT</a>(a); |
| 00215 <a class="code" href="group__osclbase.html#a78">OSCL_ASSERT</a>(b); |
| 00216 <span class="keywordflow">return</span> <a class="code" href="classOsclPriorityQueue.html#n1">comp</a>.compare(*((<a class="code" href="classOscl__Vector.html">value_type</a>*)a), *((<a class="code" href="classOscl__Vector.html">value_type</a>*)b)); |
| 00217 } |
| 00218 |
| 00219 <span class="comment">//from Oscl_Opaque_Type_Compare</span> |
| <a name="l00220"></a><a class="code" href="classOsclPriorityQueue.html#b6">00220</a> <span class="keywordtype">int</span> <a class="code" href="classOsclPriorityQueue.html#b6">compare_EQ</a>(<span class="keyword">const</span> <a class="code" href="group__osclbase.html#a25">OsclAny</a>* a, <span class="keyword">const</span> <a class="code" href="group__osclbase.html#a25">OsclAny</a>* b)<span class="keyword"> const</span> |
| 00221 <span class="keyword"> </span>{ |
| 00222 <a class="code" href="group__osclbase.html#a78">OSCL_ASSERT</a>(a); |
| 00223 <a class="code" href="group__osclbase.html#a78">OSCL_ASSERT</a>(b); |
| 00224 <span class="keywordflow">return</span> (*((<a class="code" href="classOscl__Vector.html">value_type</a>*)a)) == (*((<a class="code" href="classOscl__Vector.html">value_type</a>*)b)); |
| 00225 |
| 00226 } |
| 00227 |
| 00228 }; |
| 00229 |
| 00230 <span class="preprocessor">#endif</span> |
| 00231 <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> |
