<!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> &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_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-&gt;<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> &lt; <span class="keyword">class</span> T&gt; <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&amp; a, T&amp; b)<span class="keyword"> const</span>
00082 <span class="keyword">        </span>{
00083             <span class="keywordflow">return</span> (a &lt; b);
00084         }
00085 };
00086 
00087 
00088 
00089 
00090 
00091 
00092 
00093 
00094 <span class="keyword">template</span> &lt; <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&lt;Qelem, Alloc&gt;</a>,
00096 <span class="keyword">class </span>Compare = <a class="code" href="classOsclCompareLess.html">OsclCompareLess&lt;Qelem&gt;</a> &gt;
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 &amp; <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>&amp; 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>&amp; input)
00146         {
00147             <span class="keywordflow">return</span> <a class="code" href="classOsclPriorityQueueBase.html#b4">OsclPriorityQueueBase::remove</a>(&amp;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>, &amp;<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>&amp; 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>(&amp;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 &lt; <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.size();par++)
00185             {
00186                 ch = 2 * par + 1;
00187                 <span class="keywordflow">if</span> (ch &lt; <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.size() &amp;&amp; <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&lt;child</span>
00189                 ch++;
00190                 <span class="keywordflow">if</span> (ch &lt; <a class="code" href="classOsclPriorityQueue.html#n0">c</a>.size() &amp;&amp; <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&lt;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>