stl_heap.h
上传用户:nizebo
上传日期:2022-05-14
资源大小:882k
文件大小:10k
源码类别:

STL

开发平台:

Visual C++

  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. /* NOTE: This is an internal header file, included by other STL headers.
  26.  *   You should not attempt to use it directly.
  27.  */
  28. #ifndef __SGI_STL_INTERNAL_HEAP_H
  29. #define __SGI_STL_INTERNAL_HEAP_H
  30. __STL_BEGIN_NAMESPACE
  31. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  32. #pragma set woff 1209
  33. #endif
  34. // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
  35. template <class _RandomAccessIterator, class _Distance, class _Tp>
  36. void 
  37. __push_heap(_RandomAccessIterator __first,
  38.             _Distance __holeIndex, _Distance __topIndex, _Tp __value)
  39. {
  40.   _Distance __parent = (__holeIndex - 1) / 2;
  41.   while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
  42.     *(__first + __holeIndex) = *(__first + __parent);
  43.     __holeIndex = __parent;
  44.     __parent = (__holeIndex - 1) / 2;
  45.   }    
  46.   *(__first + __holeIndex) = __value;
  47. }
  48. template <class _RandomAccessIterator, class _Distance, class _Tp>
  49. inline void 
  50. __push_heap_aux(_RandomAccessIterator __first,
  51.                 _RandomAccessIterator __last, _Distance*, _Tp*)
  52. {
  53.   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), 
  54.               _Tp(*(__last - 1)));
  55. }
  56. template <class _RandomAccessIterator>
  57. inline void 
  58. push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  59. {
  60.   __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  61.   __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
  62.                  _LessThanComparable);
  63.   __push_heap_aux(__first, __last,
  64.                   __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
  65. }
  66. template <class _RandomAccessIterator, class _Distance, class _Tp, 
  67.           class _Compare>
  68. void
  69. __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  70.             _Distance __topIndex, _Tp __value, _Compare __comp)
  71. {
  72.   _Distance __parent = (__holeIndex - 1) / 2;
  73.   while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
  74.     *(__first + __holeIndex) = *(__first + __parent);
  75.     __holeIndex = __parent;
  76.     __parent = (__holeIndex - 1) / 2;
  77.   }
  78.   *(__first + __holeIndex) = __value;
  79. }
  80. template <class _RandomAccessIterator, class _Compare,
  81.           class _Distance, class _Tp>
  82. inline void 
  83. __push_heap_aux(_RandomAccessIterator __first,
  84.                 _RandomAccessIterator __last, _Compare __comp,
  85.                 _Distance*, _Tp*) 
  86. {
  87.   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), 
  88.               _Tp(*(__last - 1)), __comp);
  89. }
  90. template <class _RandomAccessIterator, class _Compare>
  91. inline void 
  92. push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  93.           _Compare __comp)
  94. {
  95.   __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  96.   __push_heap_aux(__first, __last, __comp,
  97.                   __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
  98. }
  99. template <class _RandomAccessIterator, class _Distance, class _Tp>
  100. void 
  101. __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  102.               _Distance __len, _Tp __value)
  103. {
  104.   _Distance __topIndex = __holeIndex;
  105.   _Distance __secondChild = 2 * __holeIndex + 2;
  106.   while (__secondChild < __len) {
  107.     if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
  108.       __secondChild--;
  109.     *(__first + __holeIndex) = *(__first + __secondChild);
  110.     __holeIndex = __secondChild;
  111.     __secondChild = 2 * (__secondChild + 1);
  112.   }
  113.   if (__secondChild == __len) {
  114.     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
  115.     __holeIndex = __secondChild - 1;
  116.   }
  117.   __push_heap(__first, __holeIndex, __topIndex, __value);
  118. }
  119. template <class _RandomAccessIterator, class _Tp, class _Distance>
  120. inline void 
  121. __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  122.            _RandomAccessIterator __result, _Tp __value, _Distance*)
  123. {
  124.   *__result = *__first;
  125.   __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
  126. }
  127. template <class _RandomAccessIterator, class _Tp>
  128. inline void 
  129. __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
  130.                _Tp*)
  131. {
  132.   __pop_heap(__first, __last - 1, __last - 1, 
  133.              _Tp(*(__last - 1)), __DISTANCE_TYPE(__first));
  134. }
  135. template <class _RandomAccessIterator>
  136. inline void pop_heap(_RandomAccessIterator __first, 
  137.                      _RandomAccessIterator __last)
  138. {
  139.   __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  140.   __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
  141.                  _LessThanComparable);
  142.   __pop_heap_aux(__first, __last, __VALUE_TYPE(__first));
  143. }
  144. template <class _RandomAccessIterator, class _Distance,
  145.           class _Tp, class _Compare>
  146. void
  147. __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  148.               _Distance __len, _Tp __value, _Compare __comp)
  149. {
  150.   _Distance __topIndex = __holeIndex;
  151.   _Distance __secondChild = 2 * __holeIndex + 2;
  152.   while (__secondChild < __len) {
  153.     if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
  154.       __secondChild--;
  155.     *(__first + __holeIndex) = *(__first + __secondChild);
  156.     __holeIndex = __secondChild;
  157.     __secondChild = 2 * (__secondChild + 1);
  158.   }
  159.   if (__secondChild == __len) {
  160.     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
  161.     __holeIndex = __secondChild - 1;
  162.   }
  163.   __push_heap(__first, __holeIndex, __topIndex, __value, __comp);
  164. }
  165. template <class _RandomAccessIterator, class _Tp, class _Compare, 
  166.           class _Distance>
  167. inline void 
  168. __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  169.            _RandomAccessIterator __result, _Tp __value, _Compare __comp,
  170.            _Distance*)
  171. {
  172.   *__result = *__first;
  173.   __adjust_heap(__first, _Distance(0), _Distance(__last - __first), 
  174.                 __value, __comp);
  175. }
  176. template <class _RandomAccessIterator, class _Tp, class _Compare>
  177. inline void 
  178. __pop_heap_aux(_RandomAccessIterator __first,
  179.                _RandomAccessIterator __last, _Tp*, _Compare __comp)
  180. {
  181.   __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
  182.              __DISTANCE_TYPE(__first));
  183. }
  184. template <class _RandomAccessIterator, class _Compare>
  185. inline void 
  186. pop_heap(_RandomAccessIterator __first,
  187.          _RandomAccessIterator __last, _Compare __comp)
  188. {
  189.   __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  190.   __pop_heap_aux(__first, __last, __VALUE_TYPE(__first), __comp);
  191. }
  192. template <class _RandomAccessIterator, class _Tp, class _Distance>
  193. void 
  194. __make_heap(_RandomAccessIterator __first,
  195.             _RandomAccessIterator __last, _Tp*, _Distance*)
  196. {
  197.   if (__last - __first < 2) return;
  198.   _Distance __len = __last - __first;
  199.   _Distance __parent = (__len - 2)/2;
  200.     
  201.   while (true) {
  202.     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
  203.     if (__parent == 0) return;
  204.     __parent--;
  205.   }
  206. }
  207. template <class _RandomAccessIterator>
  208. inline void 
  209. make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  210. {
  211.   __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  212.   __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
  213.                  _LessThanComparable);
  214.   __make_heap(__first, __last,
  215.               __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
  216. }
  217. template <class _RandomAccessIterator, class _Compare,
  218.           class _Tp, class _Distance>
  219. void
  220. __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  221.             _Compare __comp, _Tp*, _Distance*)
  222. {
  223.   if (__last - __first < 2) return;
  224.   _Distance __len = __last - __first;
  225.   _Distance __parent = (__len - 2)/2;
  226.     
  227.   while (true) {
  228.     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
  229.                   __comp);
  230.     if (__parent == 0) return;
  231.     __parent--;
  232.   }
  233. }
  234. template <class _RandomAccessIterator, class _Compare>
  235. inline void 
  236. make_heap(_RandomAccessIterator __first, 
  237.           _RandomAccessIterator __last, _Compare __comp)
  238. {
  239.   __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  240.   __make_heap(__first, __last, __comp,
  241.               __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
  242. }
  243. template <class _RandomAccessIterator>
  244. void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  245. {
  246.   __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  247.   __STL_REQUIRES(typename iterator_traits<_RandomAccessIterator>::value_type,
  248.                  _LessThanComparable);
  249.   while (__last - __first > 1)
  250.     pop_heap(__first, __last--);
  251. }
  252. template <class _RandomAccessIterator, class _Compare>
  253. void 
  254. sort_heap(_RandomAccessIterator __first,
  255.           _RandomAccessIterator __last, _Compare __comp)
  256. {
  257.   __STL_REQUIRES(_RandomAccessIterator, _Mutable_RandomAccessIterator);
  258.   while (__last - __first > 1)
  259.     pop_heap(__first, __last--, __comp);
  260. }
  261. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  262. #pragma reset woff 1209
  263. #endif
  264. __STL_END_NAMESPACE
  265. #endif /* __SGI_STL_INTERNAL_HEAP_H */
  266. // Local Variables:
  267. // mode:C++
  268. // End: