home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / libg++-2.7.1-bin.lha / lib / g++-include / heap.h < prev    next >
C/C++ Source or Header  |  1996-10-12  |  7KB  |  194 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  */
  15.  
  16. #ifndef HEAP_H
  17. #define HEAP_H
  18.  
  19. template <class RandomAccessIterator, class Distance, class T>
  20. void __push_heap(RandomAccessIterator first, Distance holeIndex,
  21.          Distance topIndex, T value) {
  22.     Distance parent = (holeIndex - 1) / 2;
  23.     while (holeIndex > topIndex && *(first + parent) < value) {
  24.     *(first + holeIndex) = *(first + parent);
  25.     holeIndex = parent;
  26.     parent = (holeIndex - 1) / 2;
  27.     }    
  28.     *(first + holeIndex) = value;
  29. }
  30.  
  31. template <class RandomAccessIterator, class T>
  32. inline void __push_heap_aux(RandomAccessIterator first,
  33.                 RandomAccessIterator last, T*) {
  34.     __push_heap(first, (last - first) - 1, 0, T(*(last - 1)));
  35. }
  36.  
  37. template <class RandomAccessIterator>
  38. inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) {
  39.     __push_heap_aux(first, last, value_type(first));
  40. }
  41.  
  42. template <class RandomAccessIterator, class Distance, class T, class Compare>
  43. void __push_heap(RandomAccessIterator first, Distance holeIndex,
  44.          Distance topIndex, T value, Compare comp) {
  45.     Distance parent = (holeIndex - 1) / 2;
  46.     while (holeIndex > topIndex && comp(*(first + parent), value)) {
  47.     *(first + holeIndex) = *(first + parent);
  48.     holeIndex = parent;
  49.     parent = (holeIndex - 1) / 2;
  50.     }
  51.     *(first + holeIndex) = value;
  52. }
  53.  
  54. template <class RandomAccessIterator, class Compare,  class T>
  55. inline void __push_heap_aux(RandomAccessIterator first,
  56.                 RandomAccessIterator last, Compare comp, T*) {
  57.     __push_heap(first, (last - first) - 1, 0, T(*(last - 1)), comp);
  58. }
  59.  
  60. template <class RandomAccessIterator, class Compare>
  61. inline void push_heap(RandomAccessIterator first, RandomAccessIterator last,
  62.               Compare comp) {
  63.     __push_heap_aux(first, last, comp, value_type(first));
  64. }
  65.  
  66. template <class RandomAccessIterator, class Distance, class T>
  67. void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
  68.            Distance len, T value) {
  69.     Distance topIndex = holeIndex;
  70.     Distance secondChild = 2 * holeIndex + 2;
  71.     while (secondChild < len) {
  72.     if (*(first + secondChild) < *(first + (secondChild - 1)))
  73.         secondChild--;
  74.     *(first + holeIndex) = *(first + secondChild);
  75.     holeIndex = secondChild;
  76.     secondChild = 2 * (secondChild + 1);
  77.     }
  78.     if (secondChild == len) {
  79.     *(first + holeIndex) = *(first + (secondChild - 1));
  80.     holeIndex = secondChild - 1;
  81.     }
  82.     __push_heap(first, holeIndex, topIndex, value);
  83. }
  84.  
  85. template <class RandomAccessIterator, class T, class Distance>
  86. inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
  87.                RandomAccessIterator result, T value, Distance*) {
  88.     *result = *first;
  89.     __adjust_heap(first, Distance(0), Distance(last - first), value);
  90. }
  91.  
  92. template <class RandomAccessIterator, class T>
  93. inline void __pop_heap_aux(RandomAccessIterator first,
  94.                RandomAccessIterator last, T*) {
  95.     __pop_heap(first, last - 1, last - 1, T(*(last - 1)), distance_type(first));
  96. }
  97.  
  98. template <class RandomAccessIterator>
  99. inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last) {
  100.     __pop_heap_aux(first, last, value_type(first));
  101. }
  102.  
  103. template <class RandomAccessIterator, class Distance, class T, class Compare>
  104. void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
  105.            Distance len, T value, Compare comp) {
  106.     Distance topIndex = holeIndex;
  107.     Distance secondChild = 2 * holeIndex + 2;
  108.     while (secondChild < len) {
  109.     if (comp(*(first + secondChild), *(first + (secondChild - 1))))
  110.         secondChild--;
  111.     *(first + holeIndex) = *(first + secondChild);
  112.     holeIndex = secondChild;
  113.     secondChild = 2 * (secondChild + 1);
  114.     }
  115.     if (secondChild == len) {
  116.     *(first + holeIndex) = *(first + (secondChild - 1));
  117.     holeIndex = secondChild - 1;
  118.     }
  119.     __push_heap(first, holeIndex, topIndex, value, comp);
  120. }
  121.  
  122. template <class RandomAccessIterator, class T, class Compare, class Distance>
  123. inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
  124.                RandomAccessIterator result, T value, Compare comp,
  125.                Distance*) {
  126.     *result = *first;
  127.     __adjust_heap(first, Distance(0), Distance(last - first), value, comp);
  128. }
  129.  
  130. template <class RandomAccessIterator, class T, class Compare>
  131. inline void __pop_heap_aux(RandomAccessIterator first,
  132.                RandomAccessIterator last, T*, Compare comp) {
  133.     __pop_heap(first, last - 1, last - 1, T(*(last - 1)), comp,
  134.            distance_type(first));
  135. }
  136.  
  137. template <class RandomAccessIterator, class Compare>
  138. inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
  139.              Compare comp) {
  140.     __pop_heap_aux(first, last, value_type(first), comp);
  141. }
  142.  
  143. template <class RandomAccessIterator, class T, class Distance>
  144. void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*,
  145.          Distance*) {
  146.     if (last - first < 2) return;
  147.     Distance len = last - first;
  148.     Distance parent = (len - 2)/2;
  149.     
  150.     while (true) {
  151.     __adjust_heap(first, parent, len, T(*(first + parent)));
  152.     if (parent == 0) return;
  153.     parent--;
  154.     }
  155. }
  156.  
  157. template <class RandomAccessIterator>
  158. inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
  159.     __make_heap(first, last, value_type(first), distance_type(first));
  160. }
  161.  
  162. template <class RandomAccessIterator, class Compare, class T, class Distance>
  163. void __make_heap(RandomAccessIterator first, RandomAccessIterator last,
  164.          Compare comp, T*, Distance*) {
  165.     if (last - first < 2) return;
  166.     Distance len = last - first;
  167.     Distance parent = (len - 2)/2;
  168.     
  169.     while (true) {
  170.     __adjust_heap(first, parent, len, T(*(first + parent)), comp);
  171.     if (parent == 0) return;
  172.     parent--;
  173.     }
  174. }
  175.  
  176. template <class RandomAccessIterator, class Compare>
  177. inline void make_heap(RandomAccessIterator first, RandomAccessIterator last,
  178.               Compare comp) {
  179.     __make_heap(first, last, comp, value_type(first), distance_type(first));
  180. }
  181.  
  182. template <class RandomAccessIterator>
  183. void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
  184.     while (last - first > 1) pop_heap(first, last--);
  185. }
  186.  
  187. template <class RandomAccessIterator, class Compare>
  188. void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
  189.            Compare comp) {
  190.     while (last - first > 1) pop_heap(first, last--, comp);
  191. }
  192.  
  193. #endif
  194.