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> 1000002 <span class="comment">// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =</span> 1100003 1200004 <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> 1300005 1400006 <span class="comment">// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =</span> 1500007 1600014 <span class="preprocessor">#ifndef OSCL_PRIQUEUE_H_INCLUDED</span> 1700015 <span class="preprocessor"></span><span class="preprocessor">#define OSCL_PRIQUEUE_H_INCLUDED</span> 1800016 <span class="preprocessor"></span> 1900017 2000018 2100030 <span class="preprocessor">#ifndef OSCL_BASE_H_INCLUDED</span> 2200031 <span class="preprocessor"></span><span class="preprocessor">#include "<a class="code" href="oscl__base_8h.html">oscl_base.h</a>"</span> 2300032 <span class="preprocessor">#endif</span> 2400033 <span class="preprocessor"></span> 2500034 2600035 <span class="preprocessor">#ifndef OSCL_VECTOR_H_INCLUDED</span> 2700036 <span class="preprocessor"></span><span class="preprocessor">#include "<a class="code" href="oscl__vector_8h.html">oscl_vector.h</a>"</span> 2800037 <span class="preprocessor">#endif</span> 2900038 <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> 3100047 { 3200048 <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>() 3400050 {} 3500051 3600052 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) ; 3700053 3800054 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) ; 3900055 4000056 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) ; 4100057 4200058 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) ; 4300059 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) 4500061 { 4600062 pOpaqueType = ot; 4700063 pVec = vec; 4800064 } 4900065 5000066 <span class="keyword">private</span>: 5100067 5200068 <span class="comment">//return delta from "first" to "last" expressed as a number of T elements.</span> 5300069 <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) 5400070 { 5500071 <span class="keywordflow">return</span> ((int)last -(int)first) / pVec-><a class="code" href="classOscl__Vector__Base.html#n3">sizeof_T</a>; 5600072 } 5700073 5800074 <a class="code" href="classOscl__Opaque__Type__Compare.html">Oscl_Opaque_Type_Compare</a>* pOpaqueType; 5900075 <a class="code" href="classOscl__Vector__Base.html">Oscl_Vector_Base</a>* pVec; 6000076 }; 6100077 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> 6300079 { 6400080 <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> 6600082 <span class="keyword"> </span>{ 6700083 <span class="keywordflow">return</span> (a < b); 6800084 } 6900085 }; 7000086 7100087 7200088 7300089 7400090 7500091 7600092 7700093 7800094 <span class="keyword">template</span> < <span class="keyword">class </span>Qelem, <span class="keyword">class </span>Alloc, 7900095 <span class="keyword">class </span>Container = <a class="code" href="classOscl__Vector.html">Oscl_Vector<Qelem, Alloc></a>, 8000096 <span class="keyword">class </span>Compare = <a class="code" href="classOsclCompareLess.html">OsclCompareLess<Qelem></a> > 8100097 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> 8300099 , <span class="keyword">public</span> <a class="code" href="classOscl__Opaque__Type__Compare.html">Oscl_Opaque_Type_Compare</a> 8400100 { 8500101 8600102 <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>; 9100107 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> 9300109 <span class="keyword"> </span>{ 9400110 <span class="keywordflow">return</span> <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.empty(); 9500111 }; 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> 9700113 <span class="keyword"> </span>{ 9800114 <span class="keywordflow">return</span> <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.size(); 9900115 }; 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) 10100117 { 10200118 <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.reserve(n); 10300119 }; 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> 10500121 <span class="keyword"> </span>{ 10600122 <span class="keywordflow">return</span> <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.front(); 10700123 }; 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>() 10900125 { 11000126 <span class="keywordflow">return</span> <a class="code" href="classOsclPriorityQueue.html#n0">c</a>; 11100127 } 11200128 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) 11400130 { 11500131 <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.push_back(input); 11600132 <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()); 11700133 } 11800134 11900135 <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>() 12100137 { 12200138 <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()); 12300139 <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.pop_back(); 12400140 } 12500141 12600142 <span class="comment">//Remove an arbitrary element, by value.</span> 12700143 <span class="comment">//If there are multiple matches, this removes the first one it finds.</span> 12800144 <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) 13000146 { 13100147 <span class="keywordflow">return</span> <a class="code" href="classOsclPriorityQueueBase.html#b4">OsclPriorityQueueBase::remove</a>(&input); 13200148 } 13300149 13400150 <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>() 13600152 , <a class="code" href="classOsclPriorityQueue.html#n0">c</a>() 13700153 { 13800154 <a class="code" href="classOsclPriorityQueueBase.html#b5">OsclPriorityQueueBase::construct</a>(<span class="keyword">this</span>, &<a class="code" href="classOsclPriorityQueue.html#n0">c</a>); 13900155 } 14000156 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>() 14200158 {} 14300159 14400160 <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>; 14700163 14800164 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) 15000166 { 15100167 <a class="code" href="classOsclPriorityQueueBase.html#b1">OsclPriorityQueueBase::push_heap</a>(first, last); 15200168 } 15300169 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) 15500171 { 15600172 <a class="code" href="classOsclPriorityQueueBase.html#b2">OsclPriorityQueueBase::pop_heap</a>(first, last); 15700173 } 15800174 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) 16000176 { 16100177 <span class="keywordflow">return</span> <a class="code" href="classOsclPriorityQueueBase.html#b3">OsclPriorityQueueBase::find_heap</a>(&input, first, last); 16200178 } 16300179 16400180 <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>() 16600182 { 16700183 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> ch; 16800184 <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++) 16900185 { 17000186 ch = 2 * par + 1; 17100187 <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])) 17200188 <span class="keywordflow">return</span> par;<span class="comment">//error-- parent<child</span> 17300189 ch++; 17400190 <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])) 17500191 <span class="keywordflow">return</span> par;<span class="comment">//error-- parent<child</span> 17600192 } 17700193 <span class="keywordflow">return</span> -1;<span class="comment">//ok</span> 17800194 } 17900195 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>; 18100197 18200198 <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) 18400200 { 18500201 <a class="code" href="group__osclbase.html#a78">OSCL_ASSERT</a>(dest); 18600202 <a class="code" href="group__osclbase.html#a78">OSCL_ASSERT</a>(src); 18700203 <span class="keywordflow">if</span> (dest != src) 18800204 { 18900205 <a class="code" href="classOscl__Vector.html">value_type</a> temp(*((<a class="code" href="classOscl__Vector.html">value_type</a>*)dest)); 19000206 *((<a class="code" href="classOscl__Vector.html">value_type</a>*)dest) = *((<a class="code" href="classOscl__Vector.html">value_type</a>*)src); 19100207 *((<a class="code" href="classOscl__Vector.html">value_type</a>*)src) = temp; 19200208 } 19300209 } 19400210 19500211 <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> 19700213 <span class="keyword"> </span>{ 19800214 <a class="code" href="group__osclbase.html#a78">OSCL_ASSERT</a>(a); 19900215 <a class="code" href="group__osclbase.html#a78">OSCL_ASSERT</a>(b); 20000216 <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)); 20100217 } 20200218 20300219 <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> 20500221 <span class="keyword"> </span>{ 20600222 <a class="code" href="group__osclbase.html#a78">OSCL_ASSERT</a>(a); 20700223 <a class="code" href="group__osclbase.html#a78">OSCL_ASSERT</a>(b); 20800224 <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)); 20900225 21000226 } 21100227 21200228 }; 21300229 21400230 <span class="preprocessor">#endif</span> 21500231 <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
