Startsida Utforska Hjälp
Logga in
mooigraph
/
regraphlet
Bevaka 1
Stjärnmärk 0
Fork 0
Filer Ärenden 0 Pull-förfrågningar 0 Wiki
Gren: master
Grenar Taggar
regraphlet
/
orig
/
GTL-1.2.4
/
doc
/
manual
/
a00072.html

a00072.html 26 KB
Permalänk Historik Rå

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345 
  1. <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
    2. 

  2. <html>
    3. 

  3.   <head>
    4. 

  4.     <meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
    5. 

  5.       <title>GTL - Graph Template Library: bin_heap.h Source File</title>
    6. 

  6.       <link href="doxygen.css" rel="stylesheet" type="text/css">
    7. 

  7.   </head>
    8. 

  8.   <body>
    9. 

  9.     <p class="links">  
    10. 

  10.       <a href="../index.html">Home</a> |
    11. 

  11.       Documentation |
    12. 

  12.       <a href="../register.html">Download</a> |
    13. 

  13.       <a href="../platforms.html">Platforms</a> |
    14. 

  14.       <a href="../refer.html">Projects</a> |      
    15. 

  15.       <a href="../lists.html">Mailing Lists</a> |
    16. 

  16.       <a href="../history.html">Version History</a>
    17. 

  17.     </p>
    18. 

  18. 

  19. <!-- Generated by Doxygen 1.5.3 -->
    20. 

  20. <div class="tabs">
    21. 

  21.   <ul>
    22. 

  22.     <li><a href="index.html"><span>Main&nbsp;Page</span></a></li>
    23. 

  23.     <li><a href="classes.html"><span>Classes</span></a></li>
    24. 

  24.     <li class="current"><a href="files.html"><span>Files</span></a></li>
    25. 

  25.     <li><a href="pages.html"><span>Related&nbsp;Pages</span></a></li>
    26. 

  26.   </ul>
    27. 

  27. </div>
    28. 

  28. <h1>bin_heap.h</h1><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">//==========================================================================</span>
    29. 

  29. <a name="l00002"></a>00002 <span class="comment">//</span>
    30. 

  30. <a name="l00003"></a>00003 <span class="comment">//   bin_heap.h</span>
    31. 

  31. <a name="l00004"></a>00004 <span class="comment">//</span>
    32. 

  32. <a name="l00005"></a>00005 <span class="comment">//==========================================================================</span>
    33. 

  33. <a name="l00006"></a>00006 <span class="comment">// $Id: bin_heap.h,v 1.10 2003/01/07 07:01:05 chris Exp $</span>
    34. 

  34. <a name="l00007"></a>00007 
    35. 

  35. <a name="l00008"></a>00008 <span class="preprocessor">#ifndef GTL_BIN_HEAP_H</span>
    36. 

  36. <a name="l00009"></a>00009 <span class="preprocessor"></span><span class="preprocessor">#define GTL_BIN_HEAP_H</span>
    37. 

  37. <a name="l00010"></a>00010 <span class="preprocessor"></span>
    38. 

  38. <a name="l00011"></a>00011 <span class="preprocessor">#include &lt;GTL/GTL.h&gt;</span>
    39. 

  39. <a name="l00012"></a>00012 
    40. 

  40. <a name="l00013"></a>00013 <span class="preprocessor">#include &lt;cassert&gt;</span>
    41. 

  41. <a name="l00014"></a>00014 <span class="preprocessor">#include &lt;vector&gt;</span>
    42. 

  42. <a name="l00015"></a>00015 <span class="preprocessor">#include &lt;map&gt;</span>
    43. 

  43. <a name="l00016"></a>00016 
    44. 

  44. <a name="l00017"></a>00017 __GTL_BEGIN_NAMESPACE
    45. 

  45. <a name="l00018"></a>00018 
    46. 

  46. <a name="l00023"></a>00023 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T&gt;
    47. 

  47. <a name="l00024"></a>00024 <span class="keyword">class </span>heap_node
    48. 

  48. <a name="l00025"></a>00025 {
    49. 

  49. <a name="l00026"></a>00026 <span class="keyword">public</span>:
    50. 

  50. <a name="l00031"></a>00031     heap_node()
    51. 

  51. <a name="l00032"></a>00032     {
    52. 

  52. <a name="l00033"></a>00033     }
    53. 

  53. <a name="l00034"></a>00034 
    54. 

  54. <a name="l00038"></a>00038     heap_node(<span class="keyword">const</span> T&amp; n) : data(n)
    55. 

  55. <a name="l00039"></a>00039     {
    56. 

  56. <a name="l00040"></a>00040     }
    57. 

  57. <a name="l00041"></a>00041 
    58. 

  58. <a name="l00046"></a>00046     T data;
    59. 

  59. <a name="l00047"></a>00047 
    60. 

  60. <a name="l00052"></a>00052     <span class="keywordtype">int</span> pos;
    61. 

  61. <a name="l00053"></a>00053 };
    62. 

  62. <a name="l00054"></a>00054 
    63. 

  63. <a name="l00055"></a>00055     
    64. 

  64. <a name="l00061"></a>00061 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
    65. 

  65. <a name="l00062"></a><a class="code" href="a00006.html">00062</a> <span class="keyword">class </span><a class="code" href="a00006.html" title="Binary heap.">bin_heap</a>
    66. 

  66. <a name="l00063"></a>00063 {
    67. 

  67. <a name="l00064"></a>00064 <span class="keyword">public</span>:
    68. 

  68. <a name="l00070"></a>00070     <a class="code" href="a00006.html#9de42b60fac4b0d38aa738522eb7c4cd" title="Creates empty binary heap.">bin_heap</a>(<span class="keyword">const</span> Pred&amp; prd);
    69. 

  69. <a name="l00071"></a>00071 
    70. 

  70. <a name="l00078"></a>00078     <a class="code" href="a00006.html#9de42b60fac4b0d38aa738522eb7c4cd" title="Creates empty binary heap.">bin_heap</a>(<span class="keyword">const</span> Pred&amp; prd, <span class="keyword">const</span> <span class="keywordtype">int</span> est_size);
    71. 

  71. <a name="l00079"></a>00079 
    72. 

  72. <a name="l00085"></a>00085     <a class="code" href="a00006.html#9de42b60fac4b0d38aa738522eb7c4cd" title="Creates empty binary heap.">bin_heap</a>(<span class="keyword">const</span> <a class="code" href="a00006.html" title="Binary heap.">bin_heap&lt;T, Pred&gt;</a>&amp; bh);
    73. 

  73. <a name="l00086"></a>00086 
    74. 

  74. <a name="l00097"></a>00097     <a class="code" href="a00006.html" title="Binary heap.">bin_heap&lt;T, Pred&gt;</a>&amp; <a class="code" href="a00006.html#d31b6806316a272686015fcbf5f633cd" title="Assigns bh to this binary heap.">operator=</a>(<span class="keyword">const</span> <a class="code" href="a00006.html" title="Binary heap.">bin_heap&lt;T, Pred&gt;</a>&amp; bh);
    75. 

  75. <a name="l00098"></a>00098     
    76. 

  76. <a name="l00102"></a>00102     <a class="code" href="a00006.html#5283db56783a84ee28dea9d393acf905" title="Destructor.">~bin_heap</a>();
    77. 

  77. <a name="l00103"></a>00103 
    78. 

  78. <a name="l00109"></a>00109     <span class="keywordtype">void</span> <a class="code" href="a00006.html#6d658d61533e66cf83dce2f8e35bed17" title="Inserts ins in heap.">push</a>(<span class="keyword">const</span> T&amp; ins);
    79. 

  79. <a name="l00110"></a>00110 
    80. 

  80. <a name="l00114"></a>00114     <span class="keywordtype">void</span> <a class="code" href="a00006.html#b463bc655b2f46cd5ff021cab28b1210" title="Removes the element on top of the heap.">pop</a>();
    81. 

  81. <a name="l00115"></a>00115 
    82. 

  82. <a name="l00121"></a>00121     <span class="keyword">const</span> T&amp; <a class="code" href="a00006.html#09924a9669f054bc6fdcf2dc5637f7f3" title="Returns a reference to the element at the top of the heap.">top</a>() <span class="keyword">const</span>;
    83. 

  83. <a name="l00122"></a>00122     
    84. 

  84. <a name="l00135"></a>00135     <span class="keywordtype">void</span> <a class="code" href="a00006.html#b1353fe40c5cfc1205314a4db6334f1b" title="Reconstructs heap condition after changing key value of cha externally.">changeKey</a>(<span class="keyword">const</span> T&amp; cha);
    85. 

  85. <a name="l00136"></a>00136 
    86. 

  86. <a name="l00142"></a>00142     <span class="keywordtype">bool</span> <a class="code" href="a00006.html#6c6f5bf251a2a85ebdd1a1730eb7934d" title="Checks if heap is empty.">is_empty</a>() <span class="keyword">const</span>;
    87. 

  87. <a name="l00143"></a>00143 
    88. 

  88. <a name="l00148"></a>00148     <span class="keywordtype">void</span> clear();
    89. 

  89. <a name="l00149"></a>00149 <span class="keyword">private</span>:
    90. 

  90. <a name="l00154"></a>00154     <span class="keyword">const</span> Pred&amp; prd;
    91. 

  91. <a name="l00155"></a>00155 
    92. 

  92. <a name="l00160"></a>00160     <span class="keywordtype">int</span> size;
    93. 

  93. <a name="l00161"></a>00161 
    94. 

  94. <a name="l00167"></a>00167     <span class="keywordtype">int</span> capacity;
    95. 

  95. <a name="l00168"></a>00168 
    96. 

  96. <a name="l00173"></a>00173     vector&lt;heap_node&lt;T&gt;* &gt; container;
    97. 

  97. <a name="l00174"></a>00174 
    98. 

  98. <a name="l00179"></a>00179     map&lt;T, heap_node&lt;T&gt;* &gt; heap_node_map;
    99. 

  99. <a name="l00180"></a>00180 
    100. 

  100. <a name="l00185"></a>00185     <span class="keywordtype">void</span> bubble_up(heap_node&lt;T&gt;* <span class="keyword">const</span> n);
    101. 

  101. <a name="l00186"></a>00186 
    102. 

  102. <a name="l00191"></a>00191     <span class="keywordtype">void</span> bubble_down(heap_node&lt;T&gt;* <span class="keyword">const</span> n);
    103. 

  103. <a name="l00192"></a>00192 <span class="preprocessor">#ifdef _DEBUG</span>
    104. 

  104. <a name="l00193"></a>00193 <span class="preprocessor"></span><span class="keyword">public</span>:
    105. 

  105. <a name="l00198"></a>00198     <span class="keywordtype">void</span> print_data_container();
    106. 

  106. <a name="l00199"></a>00199 <span class="preprocessor">#endif  // _DEBUG</span>
    107. 

  107. <a name="l00200"></a>00200 <span class="preprocessor"></span>};
    108. 

  108. <a name="l00201"></a>00201 
    109. 

  109. <a name="l00202"></a>00202 <span class="comment">// Implementation Begin</span>
    110. 

  110. <a name="l00203"></a>00203 
    111. 

  111. <a name="l00204"></a>00204 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
    112. 

  112. <a name="l00205"></a><a class="code" href="a00006.html#9de42b60fac4b0d38aa738522eb7c4cd">00205</a> <a class="code" href="a00006.html#9de42b60fac4b0d38aa738522eb7c4cd" title="Creates empty binary heap.">bin_heap&lt;T, Pred&gt;::bin_heap</a>(<span class="keyword">const</span> Pred&amp; prd) :
    113. 

  113. <a name="l00206"></a>00206     prd(prd), size(0), capacity(50)
    114. 

  114. <a name="l00207"></a>00207 {
    115. 

  115. <a name="l00208"></a>00208     container.resize(capacity);
    116. 

  116. <a name="l00209"></a>00209 }
    117. 

  117. <a name="l00210"></a>00210 
    118. 

  118. <a name="l00211"></a>00211 
    119. 

  119. <a name="l00212"></a>00212 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
    120. 

  120. <a name="l00213"></a><a class="code" href="a00006.html#b911dd559d9d9fd665b9fdf2d8202bb8">00213</a> <a class="code" href="a00006.html#9de42b60fac4b0d38aa738522eb7c4cd" title="Creates empty binary heap.">bin_heap&lt;T, Pred&gt;::bin_heap</a>(<span class="keyword">const</span> Pred&amp; prd, <span class="keyword">const</span> <span class="keywordtype">int</span> est_size) :
    121. 

  121. <a name="l00214"></a>00214     prd(prd), size(0), capacity(50)
    122. 

  122. <a name="l00215"></a>00215 {
    123. 

  123. <a name="l00216"></a>00216     <span class="keywordflow">if</span> (est_size &gt; 50)
    124. 

  124. <a name="l00217"></a>00217     {
    125. 

  125. <a name="l00218"></a>00218         capacity = est_size;
    126. 

  126. <a name="l00219"></a>00219     }
    127. 

  127. <a name="l00220"></a>00220     container.resize(capacity);
    128. 

  128. <a name="l00221"></a>00221 }
    129. 

  129. <a name="l00222"></a>00222 
    130. 

  130. <a name="l00223"></a>00223 
    131. 

  131. <a name="l00224"></a>00224 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
    132. 

  132. <a name="l00225"></a><a class="code" href="a00006.html#19bd4241e097852ffda83b72557ffbdc">00225</a> <a class="code" href="a00006.html#9de42b60fac4b0d38aa738522eb7c4cd" title="Creates empty binary heap.">bin_heap&lt;T, Pred&gt;::bin_heap</a>(<span class="keyword">const</span> <a class="code" href="a00006.html" title="Binary heap.">bin_heap&lt;T, Pred&gt;</a>&amp; bh) :
    133. 

  133. <a name="l00226"></a>00226     prd(bh.prd), size(bh.size), capacity(bh.capacity)
    134. 

  134. <a name="l00227"></a>00227 {
    135. 

  135. <a name="l00228"></a>00228     container.resize(capacity);
    136. 

  136. <a name="l00229"></a>00229     <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i &lt; size; ++i)
    137. 

  137. <a name="l00230"></a>00230     {
    138. 

  138. <a name="l00231"></a>00231         container[i] = <span class="keyword">new</span> heap_node&lt;T&gt;(bh.<a class="code" href="a00006.html#674b15241cb407c08c53e0bd21fd1dc3">container</a>[i]-&gt;data);
    139. 

  139. <a name="l00232"></a>00232     }
    140. 

  140. <a name="l00233"></a>00233 }
    141. 

  141. <a name="l00234"></a>00234 
    142. 

  142. <a name="l00235"></a>00235 
    143. 

  143. <a name="l00236"></a>00236 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
    144. 

  144. <a name="l00237"></a><a class="code" href="a00006.html#d31b6806316a272686015fcbf5f633cd">00237</a> <a class="code" href="a00006.html" title="Binary heap.">bin_heap&lt;T, Pred&gt;</a>&amp; <a class="code" href="a00006.html#d31b6806316a272686015fcbf5f633cd" title="Assigns bh to this binary heap.">bin_heap&lt;T, Pred&gt;::operator=</a>(<span class="keyword">const</span> <a class="code" href="a00006.html" title="Binary heap.">bin_heap&lt;T, Pred&gt;</a>&amp; bh)
    145. 

  145. <a name="l00238"></a>00238 {
    146. 

  146. <a name="l00239"></a>00239     <span class="keywordflow">if</span> (<span class="keyword">this</span> != &amp;bh)    <span class="comment">// no self assignment</span>
    147. 

  147. <a name="l00240"></a>00240     {
    148. 

  148. <a name="l00241"></a>00241         assert(&amp;prd == &amp;(bh.<a class="code" href="a00006.html#5ecc420dfd03a6a0b4c9328cac1fae14">prd</a>));
    149. 

  149. <a name="l00242"></a>00242         clear();
    150. 

  150. <a name="l00243"></a>00243         size = bh.<a class="code" href="a00006.html#8dde1008dcc24d734dbdb2c7ca50435b">size</a>;
    151. 

  151. <a name="l00244"></a>00244         capacity = bh.<a class="code" href="a00006.html#c5aa6948898bfc047cae2fe99ba28f57">capacity</a>;
    152. 

  152. <a name="l00245"></a>00245         container.resize(capacity);
    153. 

  153. <a name="l00246"></a>00246         <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i &lt; size; ++i)
    154. 

  154. <a name="l00247"></a>00247         {
    155. 

  155. <a name="l00248"></a>00248             container[i] = <span class="keyword">new</span> heap_node&lt;T&gt;(bh.<a class="code" href="a00006.html#674b15241cb407c08c53e0bd21fd1dc3">container</a>[i]-&gt;data);
    156. 

  156. <a name="l00249"></a>00249         }
    157. 

  157. <a name="l00250"></a>00250     }
    158. 

  158. <a name="l00251"></a>00251     <span class="keywordflow">return</span> *<span class="keyword">this</span>;
    159. 

  159. <a name="l00252"></a>00252 }
    160. 

  160. <a name="l00253"></a>00253 
    161. 

  161. <a name="l00254"></a>00254 
    162. 

  162. <a name="l00255"></a>00255 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
    163. 

  163. <a name="l00256"></a><a class="code" href="a00006.html#5283db56783a84ee28dea9d393acf905">00256</a> <a class="code" href="a00006.html#5283db56783a84ee28dea9d393acf905" title="Destructor.">bin_heap&lt;T, Pred&gt;::~bin_heap</a>()
    164. 

  164. <a name="l00257"></a>00257 {
    165. 

  165. <a name="l00258"></a>00258     clear();
    166. 

  166. <a name="l00259"></a>00259 }
    167. 

  167. <a name="l00260"></a>00260 
    168. 

  168. <a name="l00261"></a>00261 
    169. 

  169. <a name="l00262"></a>00262 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
    170. 

  170. <a name="l00263"></a><a class="code" href="a00006.html#6d658d61533e66cf83dce2f8e35bed17">00263</a> <span class="keywordtype">void</span> <a class="code" href="a00006.html#6d658d61533e66cf83dce2f8e35bed17" title="Inserts ins in heap.">bin_heap&lt;T, Pred&gt;::push</a>(<span class="keyword">const</span> T&amp; ins)
    171. 

  171. <a name="l00264"></a>00264 {
    172. 

  172. <a name="l00265"></a>00265     <span class="keywordflow">if</span> (size == capacity)
    173. 

  173. <a name="l00266"></a>00266     {
    174. 

  174. <a name="l00267"></a>00267          <span class="comment">// dynamic memory allocation</span>
    175. 

  175. <a name="l00268"></a>00268         capacity *= 2;
    176. 

  176. <a name="l00269"></a>00269         container.resize(capacity);
    177. 

  177. <a name="l00270"></a>00270     }
    178. 

  178. <a name="l00271"></a>00271     heap_node&lt;T&gt;* n = <span class="keyword">new</span> heap_node&lt;T&gt;(ins);
    179. 

  179. <a name="l00272"></a>00272     n-&gt;pos = size;
    180. 

  180. <a name="l00273"></a>00273     container[size] = n;
    181. 

  181. <a name="l00274"></a>00274     heap_node_map[ins] = n;
    182. 

  182. <a name="l00275"></a>00275     ++size;
    183. 

  183. <a name="l00276"></a>00276     bubble_up(n);
    184. 

  184. <a name="l00277"></a>00277 }
    185. 

  185. <a name="l00278"></a>00278 
    186. 

  186. <a name="l00279"></a>00279 
    187. 

  187. <a name="l00280"></a>00280 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
    188. 

  188. <a name="l00281"></a><a class="code" href="a00006.html#b463bc655b2f46cd5ff021cab28b1210">00281</a> <span class="keywordtype">void</span> <a class="code" href="a00006.html#b463bc655b2f46cd5ff021cab28b1210" title="Removes the element on top of the heap.">bin_heap&lt;T, Pred&gt;::pop</a>() 
    189. 

  189. <a name="l00282"></a>00282 {
    190. 

  190. <a name="l00283"></a>00283     assert(size &gt; 0);
    191. 

  191. <a name="l00284"></a>00284     <span class="comment">// save smallest element for return (ensured by heap condition)</span>
    192. 

  192. <a name="l00285"></a>00285     heap_node_map.erase(container[0]-&gt;data);
    193. 

  193. <a name="l00286"></a>00286     <span class="keyword">delete</span> container[0];
    194. 

  194. <a name="l00287"></a>00287     <span class="comment">// replace by last element in array and decrease heap "size"</span>
    195. 

  195. <a name="l00288"></a>00288     <span class="keywordflow">if</span> (size &gt; 1)
    196. 

  196. <a name="l00289"></a>00289     {
    197. 

  197. <a name="l00290"></a>00290         container[0] = container[--size];
    198. 

  198. <a name="l00291"></a>00291         container[0]-&gt;pos = 0;
    199. 

  199. <a name="l00292"></a>00292         <span class="comment">// reorder heap to ensure heap conditions</span>
    200. 

  200. <a name="l00293"></a>00293         bubble_down(container[0]);
    201. 

  201. <a name="l00294"></a>00294     }
    202. 

  202. <a name="l00295"></a>00295     <span class="keywordflow">else</span>
    203. 

  203. <a name="l00296"></a>00296     {
    204. 

  204. <a name="l00297"></a>00297         size = 0;
    205. 

  205. <a name="l00298"></a>00298     }
    206. 

  206. <a name="l00299"></a>00299 }
    207. 

  207. <a name="l00300"></a>00300 
    208. 

  208. <a name="l00301"></a>00301 
    209. 

  209. <a name="l00302"></a>00302 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
    210. 

  210. <a name="l00303"></a><a class="code" href="a00006.html#09924a9669f054bc6fdcf2dc5637f7f3">00303</a> <span class="keyword">const</span> T&amp; <a class="code" href="a00006.html#09924a9669f054bc6fdcf2dc5637f7f3" title="Returns a reference to the element at the top of the heap.">bin_heap&lt;T, Pred&gt;::top</a>()<span class="keyword"> const</span>
    211. 

  211. <a name="l00304"></a>00304 <span class="keyword"></span>{
    212. 

  212. <a name="l00305"></a>00305     <span class="keywordflow">return</span> container[0]-&gt;data;
    213. 

  213. <a name="l00306"></a>00306 }
    214. 

  214. <a name="l00307"></a>00307 
    215. 

  215. <a name="l00308"></a>00308 
    216. 

  216. <a name="l00309"></a>00309 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
    217. 

  217. <a name="l00310"></a><a class="code" href="a00006.html#b1353fe40c5cfc1205314a4db6334f1b">00310</a> <span class="keywordtype">void</span> <a class="code" href="a00006.html#b1353fe40c5cfc1205314a4db6334f1b" title="Reconstructs heap condition after changing key value of cha externally.">bin_heap&lt;T, Pred&gt;::changeKey</a>(<span class="keyword">const</span> T&amp; cha)
    218. 

  218. <a name="l00311"></a>00311 {
    219. 

  219. <a name="l00312"></a>00312     <span class="keywordtype">int</span> pos = heap_node_map[cha]-&gt;pos;
    220. 

  220. <a name="l00313"></a>00313     heap_node&lt;T&gt;* n = container[pos];
    221. 

  221. <a name="l00314"></a>00314     <span class="keywordflow">if</span> (pos != 0)
    222. 

  222. <a name="l00315"></a>00315     {
    223. 

  223. <a name="l00316"></a>00316         heap_node&lt;T&gt;* father = container[(pos - 1) / 2];
    224. 

  224. <a name="l00317"></a>00317         <span class="keywordflow">if</span> (prd(n-&gt;data, father-&gt;data))
    225. 

  225. <a name="l00318"></a>00318         {
    226. 

  226. <a name="l00319"></a>00319             bubble_up(n);
    227. 

  227. <a name="l00320"></a>00320             <span class="keywordflow">return</span>;
    228. 

  228. <a name="l00321"></a>00321         }
    229. 

  229. <a name="l00322"></a>00322     }
    230. 

  230. <a name="l00323"></a>00323     bubble_down(n);
    231. 

  231. <a name="l00324"></a>00324 }
    232. 

  232. <a name="l00325"></a>00325 
    233. 

  233. <a name="l00326"></a>00326 
    234. 

  234. <a name="l00327"></a>00327 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
    235. 

  235. <a name="l00328"></a><a class="code" href="a00006.html#6c6f5bf251a2a85ebdd1a1730eb7934d">00328</a> <span class="keywordtype">bool</span> <a class="code" href="a00006.html#6c6f5bf251a2a85ebdd1a1730eb7934d" title="Checks if heap is empty.">bin_heap&lt;T, Pred&gt;::is_empty</a>()<span class="keyword"> const</span>
    236. 

  236. <a name="l00329"></a>00329 <span class="keyword"></span>{
    237. 

  237. <a name="l00330"></a>00330     <span class="comment">// empty if if first free index is 0</span>
    238. 

  238. <a name="l00331"></a>00331     <span class="keywordflow">return</span> size == 0;
    239. 

  239. <a name="l00332"></a>00332 }
    240. 

  240. <a name="l00333"></a>00333   
    241. 

  241. <a name="l00334"></a>00334 
    242. 

  242. <a name="l00335"></a>00335 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
    243. 

  243. <a name="l00336"></a>00336 <span class="keywordtype">void</span> <a class="code" href="a00006.html" title="Binary heap.">bin_heap&lt;T, Pred&gt;::clear</a>()
    244. 

  244. <a name="l00337"></a>00337 {
    245. 

  245. <a name="l00338"></a>00338     <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i &lt; size; ++i)
    246. 

  246. <a name="l00339"></a>00339     {
    247. 

  247. <a name="l00340"></a>00340         <span class="keyword">delete</span> container[i];
    248. 

  248. <a name="l00341"></a>00341     }
    249. 

  249. <a name="l00342"></a>00342     size = 0;
    250. 

  250. <a name="l00343"></a>00343     heap_node_map.clear();
    251. 

  251. <a name="l00344"></a>00344 }
    252. 

  252. <a name="l00345"></a>00345 
    253. 

  253. <a name="l00346"></a>00346   
    254. 

  254. <a name="l00347"></a>00347 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
    255. 

  255. <a name="l00348"></a>00348 <span class="keywordtype">void</span> <a class="code" href="a00006.html" title="Binary heap.">bin_heap&lt;T, Pred&gt;::bubble_up</a>(heap_node&lt;T&gt;* <span class="keyword">const</span> n)
    256. 

  256. <a name="l00349"></a>00349 {
    257. 

  257. <a name="l00350"></a>00350     <span class="keywordtype">int</span> pos = n-&gt;pos;
    258. 

  258. <a name="l00351"></a>00351     <span class="comment">// if we are not already at top AND the parent in heap is more</span>
    259. 

  259. <a name="l00352"></a>00352     <span class="keywordflow">while</span> ((pos != 0) &amp;&amp;
    260. 

  260. <a name="l00353"></a>00353            (prd(n-&gt;data, container[(pos - 1) / 2]-&gt;data)))
    261. 

  261. <a name="l00354"></a>00354     {
    262. 

  262. <a name="l00355"></a>00355         <span class="comment">// move father down</span>
    263. 

  263. <a name="l00356"></a>00356         container[pos] = container[(pos - 1) / 2];
    264. 

  264. <a name="l00357"></a>00357         container[pos]-&gt;pos = pos;
    265. 

  265. <a name="l00358"></a>00358         <span class="comment">// increment k to parent index</span>
    266. 

  266. <a name="l00359"></a>00359         pos = (pos - 1) / 2;
    267. 

  267. <a name="l00360"></a>00360     }
    268. 

  268. <a name="l00361"></a>00361     <span class="comment">// place value in its highest position in heap</span>
    269. 

  269. <a name="l00362"></a>00362     container[pos] = n;
    270. 

  270. <a name="l00363"></a>00363     container[pos]-&gt;pos = pos;
    271. 

  271. <a name="l00364"></a>00364 }
    272. 

  272. <a name="l00365"></a>00365 
    273. 

  273. <a name="l00366"></a>00366 
    274. 

  274. <a name="l00367"></a>00367 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
    275. 

  275. <a name="l00368"></a>00368 <span class="keywordtype">void</span> <a class="code" href="a00006.html" title="Binary heap.">bin_heap&lt;T, Pred&gt;::bubble_down</a>(heap_node&lt;T&gt;* <span class="keyword">const</span> n)
    276. 

  276. <a name="l00369"></a>00369 {
    277. 

  277. <a name="l00370"></a>00370     <span class="keywordtype">int</span> pos = n-&gt;pos;
    278. 

  278. <a name="l00371"></a>00371     <span class="keywordtype">int</span> j = 0;
    279. 

  279. <a name="l00372"></a>00372     <span class="keywordflow">while</span> (pos &lt; size / 2)
    280. 

  280. <a name="l00373"></a>00373     {
    281. 

  281. <a name="l00374"></a>00374         j = 2 * pos + 1;
    282. 

  282. <a name="l00375"></a>00375         <span class="comment">// if right child is smaller than left child get right child</span>
    283. 

  283. <a name="l00376"></a>00376         <span class="keywordflow">if</span> ((j &lt; size - 1) &amp;&amp;
    284. 

  284. <a name="l00377"></a>00377             (prd(container[j + 1]-&gt;data, container[j]-&gt;data)))
    285. 

  285. <a name="l00378"></a>00378         {
    286. 

  286. <a name="l00379"></a>00379             ++j;
    287. 

  287. <a name="l00380"></a>00380         }
    288. 

  288. <a name="l00381"></a>00381         <span class="comment">// if element is less or equal than its child leave it here</span>
    289. 

  289. <a name="l00382"></a>00382         <span class="keywordflow">if</span> (!prd(container[j]-&gt;data, n-&gt;data))
    290. 

  290. <a name="l00383"></a>00383         {
    291. 

  291. <a name="l00384"></a>00384             <span class="keywordflow">break</span>;
    292. 

  292. <a name="l00385"></a>00385         }
    293. 

  293. <a name="l00386"></a>00386         <span class="comment">// else move its child up</span>
    294. 

  294. <a name="l00387"></a>00387         container[pos] = container[j];
    295. 

  295. <a name="l00388"></a>00388         container[pos]-&gt;pos = pos;
    296. 

  296. <a name="l00389"></a>00389         <span class="comment">// repeat for new position</span>
    297. 

  297. <a name="l00390"></a>00390         pos = j;
    298. 

  298. <a name="l00391"></a>00391     }
    299. 

  299. <a name="l00392"></a>00392     <span class="comment">// place element into position, where heap condition is fulfilled</span>
    300. 

  300. <a name="l00393"></a>00393     container[pos] = n;
    301. 

  301. <a name="l00394"></a>00394     container[pos]-&gt;pos = pos;
    302. 

  302. <a name="l00395"></a>00395 }
    303. 

  303. <a name="l00396"></a>00396   
    304. 

  304. <a name="l00397"></a>00397 <span class="preprocessor">#ifdef _DEBUG</span>
    305. 

  305. <a name="l00398"></a>00398 <span class="preprocessor"></span><span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Pred&gt;
    306. 

  306. <a name="l00399"></a>00399 <span class="keywordtype">void</span> <a class="code" href="a00006.html" title="Binary heap.">bin_heap&lt;T, Pred&gt;::print_data_container</a>()
    307. 

  307. <a name="l00400"></a>00400 {
    308. 

  308. <a name="l00401"></a>00401     <span class="keywordflow">if</span> (size == 0)
    309. 

  309. <a name="l00402"></a>00402     {
    310. 

  310. <a name="l00403"></a>00403         cout &lt;&lt; <span class="stringliteral">"empty"</span>;
    311. 

  311. <a name="l00404"></a>00404     }
    312. 

  312. <a name="l00405"></a>00405     <span class="keywordflow">else</span>
    313. 

  313. <a name="l00406"></a>00406     {
    314. 

  314. <a name="l00407"></a>00407         <span class="keywordflow">for</span> (<span class="keywordtype">int</span> pos = 0; pos &lt; size; ++pos)
    315. 

  315. <a name="l00408"></a>00408         {
    316. 

  316. <a name="l00409"></a>00409             cout &lt;&lt; container[pos]-&gt;data &lt;&lt; <span class="stringliteral">" "</span>;
    317. 

  317. <a name="l00410"></a>00410         }
    318. 

  318. <a name="l00411"></a>00411     }
    319. 

  319. <a name="l00412"></a>00412     cout &lt;&lt; endl;
    320. 

  320. <a name="l00413"></a>00413 }
    321. 

  321. <a name="l00414"></a>00414 <span class="preprocessor">#endif  // _DEBUG</span>
    322. 

  322. <a name="l00415"></a>00415 <span class="preprocessor"></span>
    323. 

  323. <a name="l00416"></a>00416 <span class="comment">// Implementation End</span>
    324. 

  324. <a name="l00417"></a>00417 
    325. 

  325. <a name="l00418"></a>00418 __GTL_END_NAMESPACE
    326. 

  326. <a name="l00419"></a>00419 
    327. 

  327. <a name="l00420"></a>00420 <span class="preprocessor">#endif  // GTL_BIN_HEAP_H</span>
    328. 

  328. <a name="l00421"></a>00421 <span class="preprocessor"></span>
    329. 

  329. <a name="l00422"></a>00422 <span class="comment">//--------------------------------------------------------------------------</span>
    330. 

  330. <a name="l00423"></a>00423 <span class="comment">//   end of file</span>
    331. 

  331. <a name="l00424"></a>00424 <span class="comment">//--------------------------------------------------------------------------</span>
    332. 

  332. </pre></div>    <p class="links">
    333. 

  333.       <a href="http://www.uni-passau.de/">University of Passau</a>
    334. 

  334.       &nbsp;-&nbsp;
    335. 

  335.       <a href="http://www.fmi.uni-passau.de/">FMI</a>
    336. 

  336.       &nbsp;-&nbsp;
    337. 

  337.       <a href="http://www.fmi.uni-passau.de/fmi/lehrstuehle/brandenburg/">Theoretical
    338. 

  338. 	Computer Science</a>
    339. 

  339.     </p>
    340. 

  340.   <div class="copyright">
    341. 

  341.       Design &copy; 2002, 2003 <a href="mailto:raitner@fmi.uni-passau.de">Marcus Raitner</a>,  University of Passau 
    342. 

  342.   </div>
    343. 

  343. </body>
    344. 

  344. </html>
    345. 

  345.