home *** CD-ROM | disk | FTP | other *** search
/ PC World 2000 April / PCWorld_2000-04_cd.bin / Software / Servis / Devc / _SETUP.6 / Group15 / stl_heap.h < prev    next >
C/C++ Source or Header  |  1999-11-07  |  9KB  |  282 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. // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
  40.  
  41. template <class _RandomAccessIterator, class _Distance, class _Tp>
  42. void 
  43. __push_heap(_RandomAccessIterator __first,
  44.             _Distance __holeIndex, _Distance __topIndex, _Tp __value)
  45. {
  46.   _Distance __parent = (__holeIndex - 1) / 2;
  47.   while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
  48.     *(__first + __holeIndex) = *(__first + __parent);
  49.     __holeIndex = __parent;
  50.     __parent = (__holeIndex - 1) / 2;
  51.   }    
  52.   *(__first + __holeIndex) = __value;
  53. }
  54.  
  55. template <class _RandomAccessIterator, class _Distance, class _Tp>
  56. inline void 
  57. __push_heap_aux(_RandomAccessIterator __first,
  58.                 _RandomAccessIterator __last, _Distance*, _Tp*)
  59. {
  60.   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), 
  61.               _Tp(*(__last - 1)));
  62. }
  63.  
  64. template <class _RandomAccessIterator>
  65. inline void 
  66. push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  67. {
  68.   __push_heap_aux(__first, __last,
  69.                   __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
  70. }
  71.  
  72. template <class _RandomAccessIterator, class _Distance, class _Tp, 
  73.           class _Compare>
  74. void
  75. __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  76.             _Distance __topIndex, _Tp __value, _Compare __comp)
  77. {
  78.   _Distance __parent = (__holeIndex - 1) / 2;
  79.   while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
  80.     *(__first + __holeIndex) = *(__first + __parent);
  81.     __holeIndex = __parent;
  82.     __parent = (__holeIndex - 1) / 2;
  83.   }
  84.   *(__first + __holeIndex) = __value;
  85. }
  86.  
  87. template <class _RandomAccessIterator, class _Compare,
  88.           class _Distance, class _Tp>
  89. inline void 
  90. __push_heap_aux(_RandomAccessIterator __first,
  91.                 _RandomAccessIterator __last, _Compare __comp,
  92.                 _Distance*, _Tp*) 
  93. {
  94.   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), 
  95.               _Tp(*(__last - 1)), __comp);
  96. }
  97.  
  98. template <class _RandomAccessIterator, class _Compare>
  99. inline void 
  100. push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  101.           _Compare __comp)
  102. {
  103.   __push_heap_aux(__first, __last, __comp,
  104.                   __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
  105. }
  106.  
  107. template <class _RandomAccessIterator, class _Distance, class _Tp>
  108. void 
  109. __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  110.               _Distance __len, _Tp __value)
  111. {
  112.   _Distance __topIndex = __holeIndex;
  113.   _Distance __secondChild = 2 * __holeIndex + 2;
  114.   while (__secondChild < __len) {
  115.     if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
  116.       __secondChild--;
  117.     *(__first + __holeIndex) = *(__first + __secondChild);
  118.     __holeIndex = __secondChild;
  119.     __secondChild = 2 * (__secondChild + 1);
  120.   }
  121.   if (__secondChild == __len) {
  122.     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
  123.     __holeIndex = __secondChild - 1;
  124.   }
  125.   __push_heap(__first, __holeIndex, __topIndex, __value);
  126. }
  127.  
  128. template <class _RandomAccessIterator, class _Tp, class _Distance>
  129. inline void 
  130. __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  131.            _RandomAccessIterator __result, _Tp __value, _Distance*)
  132. {
  133.   *__result = *__first;
  134.   __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
  135. }
  136.  
  137. template <class _RandomAccessIterator, class _Tp>
  138. inline void 
  139. __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
  140.                _Tp*)
  141. {
  142.   __pop_heap(__first, __last - 1, __last - 1, 
  143.              _Tp(*(__last - 1)), __DISTANCE_TYPE(__first));
  144. }
  145.  
  146. template <class _RandomAccessIterator>
  147. inline void pop_heap(_RandomAccessIterator __first, 
  148.                      _RandomAccessIterator __last)
  149. {
  150.   __pop_heap_aux(__first, __last, __VALUE_TYPE(__first));
  151. }
  152.  
  153. template <class _RandomAccessIterator, class _Distance,
  154.           class _Tp, class _Compare>
  155. void
  156. __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  157.               _Distance __len, _Tp __value, _Compare __comp)
  158. {
  159.   _Distance __topIndex = __holeIndex;
  160.   _Distance __secondChild = 2 * __holeIndex + 2;
  161.   while (__secondChild < __len) {
  162.     if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
  163.       __secondChild--;
  164.     *(__first + __holeIndex) = *(__first + __secondChild);
  165.     __holeIndex = __secondChild;
  166.     __secondChild = 2 * (__secondChild + 1);
  167.   }
  168.   if (__secondChild == __len) {
  169.     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
  170.     __holeIndex = __secondChild - 1;
  171.   }
  172.   __push_heap(__first, __holeIndex, __topIndex, __value, __comp);
  173. }
  174.  
  175. template <class _RandomAccessIterator, class _Tp, class _Compare, 
  176.           class _Distance>
  177. inline void 
  178. __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  179.            _RandomAccessIterator __result, _Tp __value, _Compare __comp,
  180.            _Distance*)
  181. {
  182.   *__result = *__first;
  183.   __adjust_heap(__first, _Distance(0), _Distance(__last - __first), 
  184.                 __value, __comp);
  185. }
  186.  
  187. template <class _RandomAccessIterator, class _Tp, class _Compare>
  188. inline void 
  189. __pop_heap_aux(_RandomAccessIterator __first,
  190.                _RandomAccessIterator __last, _Tp*, _Compare __comp)
  191. {
  192.   __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
  193.              __DISTANCE_TYPE(__first));
  194. }
  195.  
  196. template <class _RandomAccessIterator, class _Compare>
  197. inline void 
  198. pop_heap(_RandomAccessIterator __first,
  199.          _RandomAccessIterator __last, _Compare __comp)
  200. {
  201.     __pop_heap_aux(__first, __last, __VALUE_TYPE(__first), __comp);
  202. }
  203.  
  204. template <class _RandomAccessIterator, class _Tp, class _Distance>
  205. void 
  206. __make_heap(_RandomAccessIterator __first,
  207.             _RandomAccessIterator __last, _Tp*, _Distance*)
  208. {
  209.   if (__last - __first < 2) return;
  210.   _Distance __len = __last - __first;
  211.   _Distance __parent = (__len - 2)/2;
  212.     
  213.   while (true) {
  214.     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
  215.     if (__parent == 0) return;
  216.     __parent--;
  217.   }
  218. }
  219.  
  220. template <class _RandomAccessIterator>
  221. inline void 
  222. make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  223. {
  224.   __make_heap(__first, __last,
  225.               __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
  226. }
  227.  
  228. template <class _RandomAccessIterator, class _Compare,
  229.           class _Tp, class _Distance>
  230. void
  231. __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  232.             _Compare __comp, _Tp*, _Distance*)
  233. {
  234.   if (__last - __first < 2) return;
  235.   _Distance __len = __last - __first;
  236.   _Distance __parent = (__len - 2)/2;
  237.     
  238.   while (true) {
  239.     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
  240.                   __comp);
  241.     if (__parent == 0) return;
  242.     __parent--;
  243.   }
  244. }
  245.  
  246. template <class _RandomAccessIterator, class _Compare>
  247. inline void 
  248. make_heap(_RandomAccessIterator __first, 
  249.           _RandomAccessIterator __last, _Compare __comp)
  250. {
  251.   __make_heap(__first, __last, __comp,
  252.               __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
  253. }
  254.  
  255. template <class _RandomAccessIterator>
  256. void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  257. {
  258.   while (__last - __first > 1)
  259.     pop_heap(__first, __last--);
  260. }
  261.  
  262. template <class _RandomAccessIterator, class _Compare>
  263. void 
  264. sort_heap(_RandomAccessIterator __first,
  265.           _RandomAccessIterator __last, _Compare __comp)
  266. {
  267.   while (__last - __first > 1)
  268.     pop_heap(__first, __last--, __comp);
  269. }
  270.  
  271. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  272. #pragma reset woff 1209
  273. #endif
  274.  
  275. __STL_END_NAMESPACE
  276.  
  277. #endif /* __SGI_STL_INTERNAL_HEAP_H */
  278.  
  279. // Local Variables:
  280. // mode:C++
  281. // End:
  282.