home *** CD-ROM | disk | FTP | other *** search
/ PC World 2000 January / PCWorld_2000-01_cd.bin / Software / Servis / Devc / _SETUP.4 / Group3 / stl_heap.h < prev    next >
C/C++ Source or Header  |  1998-03-08  |  8KB  |  227 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.  * Copyright (c) 1997
  15.  * Silicon Graphics Computer Systems, Inc.
  16.  *
  17.  * Permission to use, copy, modify, distribute and sell this software
  18.  * and its documentation for any purpose is hereby granted without fee,
  19.  * provided that the above copyright notice appear in all copies and
  20.  * that both that copyright notice and this permission notice appear
  21.  * in supporting documentation.  Silicon Graphics makes no
  22.  * representations about the suitability of this software for any
  23.  * purpose.  It is provided "as is" without express or implied warranty.
  24.  */
  25.  
  26. /* NOTE: This is an internal header file, included by other STL headers.
  27.  *   You should not attempt to use it directly.
  28.  */
  29.  
  30. #ifndef __SGI_STL_INTERNAL_HEAP_H
  31. #define __SGI_STL_INTERNAL_HEAP_H
  32.  
  33. __STL_BEGIN_NAMESPACE
  34.  
  35. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  36. #pragma set woff 1209
  37. #endif
  38.  
  39. template <class RandomAccessIterator, class Distance, class T>
  40. void __push_heap(RandomAccessIterator first, Distance holeIndex,
  41.                  Distance topIndex, T value) {
  42.   Distance parent = (holeIndex - 1) / 2;
  43.   while (holeIndex > topIndex && *(first + parent) < value) {
  44.     *(first + holeIndex) = *(first + parent);
  45.     holeIndex = parent;
  46.     parent = (holeIndex - 1) / 2;
  47.   }    
  48.   *(first + holeIndex) = value;
  49. }
  50.  
  51. template <class RandomAccessIterator, class Distance, class T>
  52. inline void __push_heap_aux(RandomAccessIterator first,
  53.                             RandomAccessIterator last, Distance*, T*) {
  54.   __push_heap(first, Distance((last - first) - 1), Distance(0), 
  55.               T(*(last - 1)));
  56. }
  57.  
  58. template <class RandomAccessIterator>
  59. inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) {
  60.   __push_heap_aux(first, last, distance_type(first), value_type(first));
  61. }
  62.  
  63. template <class RandomAccessIterator, class Distance, class T, class Compare>
  64. void __push_heap(RandomAccessIterator first, Distance holeIndex,
  65.                  Distance topIndex, T value, Compare comp) {
  66.   Distance parent = (holeIndex - 1) / 2;
  67.   while (holeIndex > topIndex && comp(*(first + parent), value)) {
  68.     *(first + holeIndex) = *(first + parent);
  69.     holeIndex = parent;
  70.     parent = (holeIndex - 1) / 2;
  71.   }
  72.   *(first + holeIndex) = value;
  73. }
  74.  
  75. template <class RandomAccessIterator, class Compare, class Distance, class T>
  76. inline void __push_heap_aux(RandomAccessIterator first,
  77.                             RandomAccessIterator last, Compare comp,
  78.                             Distance*, T*) {
  79.   __push_heap(first, Distance((last - first) - 1), Distance(0), 
  80.               T(*(last - 1)), comp);
  81. }
  82.  
  83. template <class RandomAccessIterator, class Compare>
  84. inline void push_heap(RandomAccessIterator first, RandomAccessIterator last,
  85.                       Compare comp) {
  86.   __push_heap_aux(first, last, comp, distance_type(first), value_type(first));
  87. }
  88.  
  89. template <class RandomAccessIterator, class Distance, class T>
  90. void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
  91.                    Distance len, T value) {
  92.   Distance topIndex = holeIndex;
  93.   Distance secondChild = 2 * holeIndex + 2;
  94.   while (secondChild < len) {
  95.     if (*(first + secondChild) < *(first + (secondChild - 1)))
  96.       secondChild--;
  97.     *(first + holeIndex) = *(first + secondChild);
  98.     holeIndex = secondChild;
  99.     secondChild = 2 * (secondChild + 1);
  100.   }
  101.   if (secondChild == len) {
  102.     *(first + holeIndex) = *(first + (secondChild - 1));
  103.     holeIndex = secondChild - 1;
  104.   }
  105.   __push_heap(first, holeIndex, topIndex, value);
  106. }
  107.  
  108. template <class RandomAccessIterator, class T, class Distance>
  109. inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
  110.                        RandomAccessIterator result, T value, Distance*) {
  111.   *result = *first;
  112.   __adjust_heap(first, Distance(0), Distance(last - first), value);
  113. }
  114.  
  115. template <class RandomAccessIterator, class T>
  116. inline void __pop_heap_aux(RandomAccessIterator first,
  117.                            RandomAccessIterator last, T*) {
  118.   __pop_heap(first, last - 1, last - 1, T(*(last - 1)), distance_type(first));
  119. }
  120.  
  121. template <class RandomAccessIterator>
  122. inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last) {
  123.   __pop_heap_aux(first, last, value_type(first));
  124. }
  125.  
  126. template <class RandomAccessIterator, class Distance, class T, class Compare>
  127. void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
  128.                    Distance len, T value, Compare comp) {
  129.   Distance topIndex = holeIndex;
  130.   Distance secondChild = 2 * holeIndex + 2;
  131.   while (secondChild < len) {
  132.     if (comp(*(first + secondChild), *(first + (secondChild - 1))))
  133.       secondChild--;
  134.     *(first + holeIndex) = *(first + secondChild);
  135.     holeIndex = secondChild;
  136.     secondChild = 2 * (secondChild + 1);
  137.   }
  138.   if (secondChild == len) {
  139.     *(first + holeIndex) = *(first + (secondChild - 1));
  140.     holeIndex = secondChild - 1;
  141.   }
  142.   __push_heap(first, holeIndex, topIndex, value, comp);
  143. }
  144.  
  145. template <class RandomAccessIterator, class T, class Compare, class Distance>
  146. inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
  147.                        RandomAccessIterator result, T value, Compare comp,
  148.                        Distance*) {
  149.   *result = *first;
  150.   __adjust_heap(first, Distance(0), Distance(last - first), value, comp);
  151. }
  152.  
  153. template <class RandomAccessIterator, class T, class Compare>
  154. inline void __pop_heap_aux(RandomAccessIterator first,
  155.                            RandomAccessIterator last, T*, Compare comp) {
  156.   __pop_heap(first, last - 1, last - 1, T(*(last - 1)), comp,
  157.              distance_type(first));
  158. }
  159.  
  160. template <class RandomAccessIterator, class Compare>
  161. inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
  162.                      Compare comp) {
  163.     __pop_heap_aux(first, last, value_type(first), comp);
  164. }
  165.  
  166. template <class RandomAccessIterator, class T, class Distance>
  167. void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*,
  168.                  Distance*) {
  169.   if (last - first < 2) return;
  170.   Distance len = last - first;
  171.   Distance parent = (len - 2)/2;
  172.     
  173.   while (true) {
  174.     __adjust_heap(first, parent, len, T(*(first + parent)));
  175.     if (parent == 0) return;
  176.     parent--;
  177.   }
  178. }
  179.  
  180. template <class RandomAccessIterator>
  181. inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
  182.   __make_heap(first, last, value_type(first), distance_type(first));
  183. }
  184.  
  185. template <class RandomAccessIterator, class Compare, class T, class Distance>
  186. void __make_heap(RandomAccessIterator first, RandomAccessIterator last,
  187.                  Compare comp, T*, Distance*) {
  188.   if (last - first < 2) return;
  189.   Distance len = last - first;
  190.   Distance parent = (len - 2)/2;
  191.     
  192.   while (true) {
  193.     __adjust_heap(first, parent, len, T(*(first + parent)), comp);
  194.     if (parent == 0) return;
  195.     parent--;
  196.   }
  197. }
  198.  
  199. template <class RandomAccessIterator, class Compare>
  200. inline void make_heap(RandomAccessIterator first, RandomAccessIterator last,
  201.                       Compare comp) {
  202.   __make_heap(first, last, comp, value_type(first), distance_type(first));
  203. }
  204.  
  205. template <class RandomAccessIterator>
  206. void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
  207.   while (last - first > 1) pop_heap(first, last--);
  208. }
  209.  
  210. template <class RandomAccessIterator, class Compare>
  211. void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
  212.                Compare comp) {
  213.   while (last - first > 1) pop_heap(first, last--, comp);
  214. }
  215.  
  216. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  217. #pragma reset woff 1209
  218. #endif
  219.  
  220. __STL_END_NAMESPACE
  221.  
  222. #endif /* __SGI_STL_INTERNAL_HEAP_H */
  223.  
  224. // Local Variables:
  225. // mode:C++
  226. // End:
  227.