_heap.c 7.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246
  1. /*
  2. *
  3. *
  4. * Copyright (c) 1994
  5. * Hewlett-Packard Company
  6. *
  7. * Copyright (c) 1996,1997
  8. * Silicon Graphics Computer Systems, Inc.
  9. *
  10. * Copyright (c) 1997
  11. * Moscow Center for SPARC Technology
  12. *
  13. * Copyright (c) 1999
  14. * Boris Fomitchev
  15. *
  16. * This material is provided "as is", with absolutely no warranty expressed
  17. * or implied. Any use is at your own risk.
  18. *
  19. * Permission to use or copy this software for any purpose is hereby granted
  20. * without fee, provided the above notices are retained on all copies.
  21. * Permission to modify the code and to distribute modified code is granted,
  22. * provided the above notices are retained, and a notice that the code was
  23. * modified is included with the above copyright notice.
  24. *
  25. */
  26. #ifndef _STLP_HEAP_C
  27. #define _STLP_HEAP_C
  28. #ifndef _STLP_INTERNAL_HEAP_H
  29. # include <stl/_heap.h>
  30. #endif
  31. #ifndef _STLP_INTERNAL_ITERATOR_BASE_H
  32. # include <stl/_iterator_base.h>
  33. #endif
  34. _STLP_BEGIN_NAMESPACE
  35. template <class _RandomAccessIterator, class _Distance, class _Tp>
  36. _STLP_INLINE_LOOP
  37. void
  38. __push_heap(_RandomAccessIterator __first,
  39. _Distance __holeIndex, _Distance __topIndex, _Tp __val)
  40. {
  41. _Distance __parent = (__holeIndex - 1) / 2;
  42. while (__holeIndex > __topIndex && *(__first + __parent) < __val) {
  43. *(__first + __holeIndex) = *(__first + __parent);
  44. __holeIndex = __parent;
  45. __parent = (__holeIndex - 1) / 2;
  46. }
  47. *(__first + __holeIndex) = __val;
  48. }
  49. template <class _RandomAccessIterator, class _Distance, class _Tp>
  50. inline void
  51. __push_heap_aux(_RandomAccessIterator __first,
  52. _RandomAccessIterator __last, _Distance*, _Tp*)
  53. {
  54. __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
  55. _Tp(*(__last - 1)));
  56. }
  57. template <class _RandomAccessIterator>
  58. void
  59. push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  60. {
  61. __push_heap_aux(__first, __last,
  62. _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
  63. }
  64. template <class _RandomAccessIterator, class _Distance, class _Tp,
  65. class _Compare>
  66. _STLP_INLINE_LOOP
  67. void
  68. __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  69. _Distance __topIndex, _Tp __val, _Compare __comp)
  70. {
  71. _Distance __parent = (__holeIndex - 1) / 2;
  72. while (__holeIndex > __topIndex && __comp(*(__first + __parent), __val)) {
  73. _STLP_VERBOSE_ASSERT(!__comp(__val, *(__first + __parent)), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  74. *(__first + __holeIndex) = *(__first + __parent);
  75. __holeIndex = __parent;
  76. __parent = (__holeIndex - 1) / 2;
  77. }
  78. *(__first + __holeIndex) = __val;
  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. void
  92. push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  93. _Compare __comp)
  94. {
  95. __push_heap_aux(__first, __last, __comp,
  96. _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
  97. }
  98. template <class _RandomAccessIterator, class _Distance, class _Tp>
  99. void
  100. __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  101. _Distance __len, _Tp __val) {
  102. _Distance __topIndex = __holeIndex;
  103. _Distance __secondChild = 2 * __holeIndex + 2;
  104. while (__secondChild < __len) {
  105. if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
  106. __secondChild--;
  107. *(__first + __holeIndex) = *(__first + __secondChild);
  108. __holeIndex = __secondChild;
  109. __secondChild = 2 * (__secondChild + 1);
  110. }
  111. if (__secondChild == __len) {
  112. *(__first + __holeIndex) = *(__first + (__secondChild - 1));
  113. __holeIndex = __secondChild - 1;
  114. }
  115. __push_heap(__first, __holeIndex, __topIndex, __val);
  116. }
  117. template <class _RandomAccessIterator, class _Tp>
  118. inline void
  119. __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*) {
  120. __pop_heap(__first, __last - 1, __last - 1,
  121. _Tp(*(__last - 1)), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
  122. }
  123. template <class _RandomAccessIterator>
  124. void pop_heap(_RandomAccessIterator __first,
  125. _RandomAccessIterator __last) {
  126. __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
  127. }
  128. template <class _RandomAccessIterator, class _Distance,
  129. class _Tp, class _Compare>
  130. void
  131. __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  132. _Distance __len, _Tp __val, _Compare __comp)
  133. {
  134. _Distance __topIndex = __holeIndex;
  135. _Distance __secondChild = 2 * __holeIndex + 2;
  136. while (__secondChild < __len) {
  137. if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1)))) {
  138. _STLP_VERBOSE_ASSERT(!__comp(*(__first + (__secondChild - 1)), *(__first + __secondChild)),
  139. _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  140. __secondChild--;
  141. }
  142. *(__first + __holeIndex) = *(__first + __secondChild);
  143. __holeIndex = __secondChild;
  144. __secondChild = 2 * (__secondChild + 1);
  145. }
  146. if (__secondChild == __len) {
  147. *(__first + __holeIndex) = *(__first + (__secondChild - 1));
  148. __holeIndex = __secondChild - 1;
  149. }
  150. __push_heap(__first, __holeIndex, __topIndex, __val, __comp);
  151. }
  152. template <class _RandomAccessIterator, class _Tp, class _Compare>
  153. inline void
  154. __pop_heap_aux(_RandomAccessIterator __first,
  155. _RandomAccessIterator __last, _Tp*, _Compare __comp)
  156. {
  157. __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
  158. _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
  159. }
  160. template <class _RandomAccessIterator, class _Compare>
  161. void
  162. pop_heap(_RandomAccessIterator __first,
  163. _RandomAccessIterator __last, _Compare __comp)
  164. {
  165. __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator), __comp);
  166. }
  167. template <class _RandomAccessIterator, class _Tp, class _Distance>
  168. _STLP_INLINE_LOOP
  169. void
  170. __make_heap(_RandomAccessIterator __first,
  171. _RandomAccessIterator __last, _Tp*, _Distance*)
  172. {
  173. if (__last - __first < 2) return;
  174. _Distance __len = __last - __first;
  175. _Distance __parent = (__len - 2)/2;
  176. for (;;) {
  177. __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
  178. if (__parent == 0) return;
  179. __parent--;
  180. }
  181. }
  182. template <class _RandomAccessIterator>
  183. void
  184. make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  185. {
  186. __make_heap(__first, __last,
  187. _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
  188. }
  189. template <class _RandomAccessIterator, class _Compare,
  190. class _Tp, class _Distance>
  191. _STLP_INLINE_LOOP
  192. void
  193. __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  194. _Compare __comp, _Tp*, _Distance*)
  195. {
  196. if (__last - __first < 2) return;
  197. _Distance __len = __last - __first;
  198. _Distance __parent = (__len - 2)/2;
  199. for (;;) {
  200. __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
  201. __comp);
  202. if (__parent == 0) return;
  203. __parent--;
  204. }
  205. }
  206. template <class _RandomAccessIterator, class _Compare>
  207. void
  208. make_heap(_RandomAccessIterator __first,
  209. _RandomAccessIterator __last, _Compare __comp)
  210. {
  211. __make_heap(__first, __last, __comp,
  212. _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
  213. }
  214. _STLP_END_NAMESPACE
  215. #endif /* _STLP_HEAP_C */
  216. // Local Variables:
  217. // mode:C++
  218. // End: