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_priqueue.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_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> 10 00002 <span class="comment">// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =</span> 11 00003 12 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> 13 00005 14 00006 <span class="comment">// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =</span> 15 00007 16 00014 <span class="preprocessor">#ifndef OSCL_PRIQUEUE_H_INCLUDED</span> 17 00015 <span class="preprocessor"></span><span class="preprocessor">#define OSCL_PRIQUEUE_H_INCLUDED</span> 18 00016 <span class="preprocessor"></span> 19 00017 20 00018 21 00030 <span class="preprocessor">#ifndef OSCL_BASE_H_INCLUDED</span> 22 00031 <span class="preprocessor"></span><span class="preprocessor">#include "<a class="code" href="oscl__base_8h.html">oscl_base.h</a>"</span> 23 00032 <span class="preprocessor">#endif</span> 24 00033 <span class="preprocessor"></span> 25 00034 26 00035 <span class="preprocessor">#ifndef OSCL_VECTOR_H_INCLUDED</span> 27 00036 <span class="preprocessor"></span><span class="preprocessor">#include "<a class="code" href="oscl__vector_8h.html">oscl_vector.h</a>"</span> 28 00037 <span class="preprocessor">#endif</span> 29 00038 <span class="preprocessor"></span> 30 <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> 31 00047 { 32 00048 <span class="keyword">protected</span>: 33 <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>() 34 00050 {} 35 00051 36 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) ; 37 00053 38 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) ; 39 00055 40 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) ; 41 00057 42 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) ; 43 00059 44 <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) 45 00061 { 46 00062 pOpaqueType = ot; 47 00063 pVec = vec; 48 00064 } 49 00065 50 00066 <span class="keyword">private</span>: 51 00067 52 00068 <span class="comment">//return delta from "first" to "last" expressed as a number of T elements.</span> 53 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) 54 00070 { 55 00071 <span class="keywordflow">return</span> ((int)last -(int)first) / pVec-><a class="code" href="classOscl__Vector__Base.html#n3">sizeof_T</a>; 56 00072 } 57 00073 58 00074 <a class="code" href="classOscl__Opaque__Type__Compare.html">Oscl_Opaque_Type_Compare</a>* pOpaqueType; 59 00075 <a class="code" href="classOscl__Vector__Base.html">Oscl_Vector_Base</a>* pVec; 60 00076 }; 61 00077 62 <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> 63 00079 { 64 00080 <span class="keyword">public</span>: 65 <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> 66 00082 <span class="keyword"> </span>{ 67 00083 <span class="keywordflow">return</span> (a < b); 68 00084 } 69 00085 }; 70 00086 71 00087 72 00088 73 00089 74 00090 75 00091 76 00092 77 00093 78 00094 <span class="keyword">template</span> < <span class="keyword">class </span>Qelem, <span class="keyword">class </span>Alloc, 79 00095 <span class="keyword">class </span>Container = <a class="code" href="classOscl__Vector.html">Oscl_Vector<Qelem, Alloc></a>, 80 00096 <span class="keyword">class </span>Compare = <a class="code" href="classOsclCompareLess.html">OsclCompareLess<Qelem></a> > 81 00097 82 <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> 83 00099 , <span class="keyword">public</span> <a class="code" href="classOscl__Opaque__Type__Compare.html">Oscl_Opaque_Type_Compare</a> 84 00100 { 85 00101 86 00102 <span class="keyword">public</span>: 87 <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>; 88 <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>; 89 <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>; 90 <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>; 91 00107 92 <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> 93 00109 <span class="keyword"> </span>{ 94 00110 <span class="keywordflow">return</span> <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.empty(); 95 00111 }; 96 <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> 97 00113 <span class="keyword"> </span>{ 98 00114 <span class="keywordflow">return</span> <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.size(); 99 00115 }; 100 <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) 101 00117 { 102 00118 <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.reserve(n); 103 00119 }; 104 <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> 105 00121 <span class="keyword"> </span>{ 106 00122 <span class="keywordflow">return</span> <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.front(); 107 00123 }; 108 <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>() 109 00125 { 110 00126 <span class="keywordflow">return</span> <a class="code" href="classOsclPriorityQueue.html#n0">c</a>; 111 00127 } 112 00128 113 <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) 114 00130 { 115 00131 <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.push_back(input); 116 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()); 117 00133 } 118 00134 119 00135 <span class="comment">//remove top element</span> 120 <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>() 121 00137 { 122 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()); 123 00139 <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.pop_back(); 124 00140 } 125 00141 126 00142 <span class="comment">//Remove an arbitrary element, by value.</span> 127 00143 <span class="comment">//If there are multiple matches, this removes the first one it finds.</span> 128 00144 <span class="comment">//Returns number of items removed(either 0 or 1).</span> 129 <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) 130 00146 { 131 00147 <span class="keywordflow">return</span> <a class="code" href="classOsclPriorityQueueBase.html#b4">OsclPriorityQueueBase::remove</a>(&input); 132 00148 } 133 00149 134 00150 <span class="comment">//Constructor</span> 135 <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>() 136 00152 , <a class="code" href="classOsclPriorityQueue.html#n0">c</a>() 137 00153 { 138 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>); 139 00155 } 140 00156 141 <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>() 142 00158 {} 143 00159 144 00160 <span class="keyword">protected</span>: 145 <a name="l00161"></a><a class="code" href="classOsclPriorityQueue.html#n0">00161</a> Container <a class="code" href="classOsclPriorityQueue.html#n0">c</a>; 146 <a name="l00162"></a><a class="code" href="classOsclPriorityQueue.html#n1">00162</a> Compare <a class="code" href="classOsclPriorityQueue.html#n1">comp</a>; 147 00163 148 00164 149 <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) 150 00166 { 151 00167 <a class="code" href="classOsclPriorityQueueBase.html#b1">OsclPriorityQueueBase::push_heap</a>(first, last); 152 00168 } 153 00169 154 <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) 155 00171 { 156 00172 <a class="code" href="classOsclPriorityQueueBase.html#b2">OsclPriorityQueueBase::pop_heap</a>(first, last); 157 00173 } 158 00174 159 <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) 160 00176 { 161 00177 <span class="keywordflow">return</span> <a class="code" href="classOsclPriorityQueueBase.html#b3">OsclPriorityQueueBase::find_heap</a>(&input, first, last); 162 00178 } 163 00179 164 00180 <span class="comment">//a debug routine for validating the current sort.</span> 165 <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>() 166 00182 { 167 00183 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> ch; 168 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++) 169 00185 { 170 00186 ch = 2 * par + 1; 171 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])) 172 00188 <span class="keywordflow">return</span> par;<span class="comment">//error-- parent<child</span> 173 00189 ch++; 174 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])) 175 00191 <span class="keywordflow">return</span> par;<span class="comment">//error-- parent<child</span> 176 00192 } 177 00193 <span class="keywordflow">return</span> -1;<span class="comment">//ok</span> 178 00194 } 179 00195 180 <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>; 181 00197 182 00198 <span class="comment">//from Oscl_Opaque_Type_Compare</span> 183 <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) 184 00200 { 185 00201 <a class="code" href="group__osclbase.html#a78">OSCL_ASSERT</a>(dest); 186 00202 <a class="code" href="group__osclbase.html#a78">OSCL_ASSERT</a>(src); 187 00203 <span class="keywordflow">if</span> (dest != src) 188 00204 { 189 00205 <a class="code" href="classOscl__Vector.html">value_type</a> temp(*((<a class="code" href="classOscl__Vector.html">value_type</a>*)dest)); 190 00206 *((<a class="code" href="classOscl__Vector.html">value_type</a>*)dest) = *((<a class="code" href="classOscl__Vector.html">value_type</a>*)src); 191 00207 *((<a class="code" href="classOscl__Vector.html">value_type</a>*)src) = temp; 192 00208 } 193 00209 } 194 00210 195 00211 <span class="comment">//from Oscl_Opaque_Type_Compare</span> 196 <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> 197 00213 <span class="keyword"> </span>{ 198 00214 <a class="code" href="group__osclbase.html#a78">OSCL_ASSERT</a>(a); 199 00215 <a class="code" href="group__osclbase.html#a78">OSCL_ASSERT</a>(b); 200 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)); 201 00217 } 202 00218 203 00219 <span class="comment">//from Oscl_Opaque_Type_Compare</span> 204 <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> 205 00221 <span class="keyword"> </span>{ 206 00222 <a class="code" href="group__osclbase.html#a78">OSCL_ASSERT</a>(a); 207 00223 <a class="code" href="group__osclbase.html#a78">OSCL_ASSERT</a>(b); 208 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)); 209 00225 210 00226 } 211 00227 212 00228 }; 213 00229 214 00230 <span class="preprocessor">#endif</span> 215 00231 <span class="preprocessor"></span> 216 </pre></div><hr size="1"><img src="pvlogo_small.jpg"><address style="align: right;"><small>OSCL API</small> 217 <address style="align: left;"><small>Posting Version: OPENCORE_20090310 </small> 218 </small></address> 219 </body> 220 </html> 221
