home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / stlpt453.zip / STLport-4.5.3 / stlport / stl / _heap.c < prev    next >
C/C++ Source or Header  |  2002-02-02  |  8KB  |  243 lines
  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.  
  29. #ifndef _STLP_INTERNAL_HEAP_H
  30. # include <stl/_heap.h>
  31. #endif
  32.  
  33. #ifndef _STLP_INTERNAL_ITERATOR_BASE_H
  34. # include <stl/_iterator_base.h>
  35. #endif
  36.  
  37. _STLP_BEGIN_NAMESPACE
  38.  
  39. template <class _RandomAccessIterator, class _Distance, class _Tp>
  40. _STLP_INLINE_LOOP
  41. void 
  42. __push_heap(_RandomAccessIterator __first,
  43.             _Distance __holeIndex, _Distance __topIndex, _Tp __val)
  44. {
  45.   _Distance __parent = (__holeIndex - 1) / 2;
  46.   while (__holeIndex > __topIndex && *(__first + __parent) < __val) {
  47.     *(__first + __holeIndex) = *(__first + __parent);
  48.     __holeIndex = __parent;
  49.     __parent = (__holeIndex - 1) / 2;
  50.   }    
  51.   *(__first + __holeIndex) = __val;
  52. }
  53.  
  54. template <class _RandomAccessIterator, class _Distance, class _Tp>
  55. inline void 
  56. __push_heap_aux(_RandomAccessIterator __first,
  57.                 _RandomAccessIterator __last, _Distance*, _Tp*)
  58. {
  59.   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), 
  60.               _Tp(*(__last - 1)));
  61. }
  62.  
  63. template <class _RandomAccessIterator>
  64. void 
  65. push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  66. {
  67.   __push_heap_aux(__first, __last,
  68.                   _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
  69. }
  70.  
  71.  
  72. template <class _RandomAccessIterator, class _Distance, class _Tp, 
  73.           class _Compare>
  74. _STLP_INLINE_LOOP
  75. void
  76. __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  77.             _Distance __topIndex, _Tp __val, _Compare __comp)
  78. {
  79.   _Distance __parent = (__holeIndex - 1) / 2;
  80.   while (__holeIndex > __topIndex && __comp(*(__first + __parent), __val)) {
  81.     *(__first + __holeIndex) = *(__first + __parent);
  82.     __holeIndex = __parent;
  83.     __parent = (__holeIndex - 1) / 2;
  84.   }
  85.   *(__first + __holeIndex) = __val;
  86. }
  87.  
  88. template <class _RandomAccessIterator, class _Compare,
  89.           class _Distance, class _Tp>
  90. inline void 
  91. __push_heap_aux(_RandomAccessIterator __first,
  92.                 _RandomAccessIterator __last, _Compare __comp,
  93.                 _Distance*, _Tp*) 
  94. {
  95.   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), 
  96.               _Tp(*(__last - 1)), __comp);
  97. }
  98.  
  99. template <class _RandomAccessIterator, class _Compare>
  100. void 
  101. push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  102.           _Compare __comp) 
  103. {
  104.   __push_heap_aux(__first, __last, __comp,
  105.                   _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
  106. }
  107.  
  108. template <class _RandomAccessIterator, class _Distance, class _Tp>
  109. void 
  110. __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  111.               _Distance __len, _Tp __val) {
  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, __val);
  126. }
  127.  
  128.  
  129. template <class _RandomAccessIterator, class _Tp>
  130. inline void 
  131. __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*) {
  132.   __pop_heap(__first, __last - 1, __last - 1, 
  133.              _Tp(*(__last - 1)), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
  134. }
  135.  
  136. template <class _RandomAccessIterator>
  137. void pop_heap(_RandomAccessIterator __first, 
  138.           _RandomAccessIterator __last) {
  139.   __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
  140. }
  141.  
  142. template <class _RandomAccessIterator, class _Distance,
  143.           class _Tp, class _Compare>
  144. void
  145. __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  146.               _Distance __len, _Tp __val, _Compare __comp)
  147. {
  148.   _Distance __topIndex = __holeIndex;
  149.   _Distance __secondChild = 2 * __holeIndex + 2;
  150.   while (__secondChild < __len) {
  151.     if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
  152.       __secondChild--;
  153.     *(__first + __holeIndex) = *(__first + __secondChild);
  154.     __holeIndex = __secondChild;
  155.     __secondChild = 2 * (__secondChild + 1);
  156.   }
  157.   if (__secondChild == __len) {
  158.     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
  159.     __holeIndex = __secondChild - 1;
  160.   }
  161.   __push_heap(__first, __holeIndex, __topIndex, __val, __comp);
  162. }
  163.  
  164.  
  165. template <class _RandomAccessIterator, class _Tp, class _Compare>
  166. inline void 
  167. __pop_heap_aux(_RandomAccessIterator __first,
  168.                _RandomAccessIterator __last, _Tp*, _Compare __comp)
  169. {
  170.   __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
  171.              _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
  172. }
  173.  
  174.  
  175. template <class _RandomAccessIterator, class _Compare>
  176. void 
  177. pop_heap(_RandomAccessIterator __first,
  178.          _RandomAccessIterator __last, _Compare __comp)
  179. {
  180.     __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator), __comp);
  181. }
  182.  
  183. template <class _RandomAccessIterator, class _Tp, class _Distance>
  184. _STLP_INLINE_LOOP
  185. void 
  186. __make_heap(_RandomAccessIterator __first,
  187.             _RandomAccessIterator __last, _Tp*, _Distance*)
  188. {
  189.   if (__last - __first < 2) return;
  190.   _Distance __len = __last - __first;
  191.   _Distance __parent = (__len - 2)/2;
  192.     
  193.   while (true) {
  194.     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
  195.     if (__parent == 0) return;
  196.     __parent--;
  197.   }
  198. }
  199.  
  200. template <class _RandomAccessIterator>
  201. void 
  202. make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  203. {
  204.   __make_heap(__first, __last,
  205.               _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
  206. }
  207.  
  208. template <class _RandomAccessIterator, class _Compare,
  209.           class _Tp, class _Distance>
  210. _STLP_INLINE_LOOP
  211. void
  212. __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  213.             _Compare __comp, _Tp*, _Distance*)
  214. {
  215.   if (__last - __first < 2) return;
  216.   _Distance __len = __last - __first;
  217.   _Distance __parent = (__len - 2)/2;
  218.     
  219.   while (true) {
  220.     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
  221.                   __comp);
  222.     if (__parent == 0) return;
  223.     __parent--;
  224.   }
  225. }
  226.  
  227. template <class _RandomAccessIterator, class _Compare>
  228. void 
  229. make_heap(_RandomAccessIterator __first, 
  230.           _RandomAccessIterator __last, _Compare __comp)
  231. {
  232.   __make_heap(__first, __last, __comp,
  233.               _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
  234. }
  235.  
  236. _STLP_END_NAMESPACE
  237.  
  238. #endif /*  _STLP_HEAP_C */
  239.  
  240. // Local Variables:
  241. // mode:C++
  242. // End:
  243.