Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  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 _CPP_BITS_STL_HEAP_H
  31. #define _CPP_BITS_STL_HEAP_H 1
  32.  
  33. namespace std
  34. {
  35.  
  36. // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
  37.  
  38. template <class _RandomAccessIterator, class _Distance, class _Tp>
  39. void
  40. __push_heap(_RandomAccessIterator __first,
  41.             _Distance __holeIndex, _Distance __topIndex, _Tp __value)
  42. {
  43.   _Distance __parent = (__holeIndex - 1) / 2;
  44.   while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
  45.     *(__first + __holeIndex) = *(__first + __parent);
  46.     __holeIndex = __parent;
  47.     __parent = (__holeIndex - 1) / 2;
  48.   }    
  49.   *(__first + __holeIndex) = __value;
  50. }
  51.  
  52. template <class _RandomAccessIterator, class _Distance, class _Tp>
  53. inline void
  54. __push_heap_aux(_RandomAccessIterator __first,
  55.                 _RandomAccessIterator __last, _Distance*, _Tp*)
  56. {
  57.   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
  58.               _Tp(*(__last - 1)));
  59. }
  60.  
  61. template <class _RandomAccessIterator>
  62. inline void
  63. push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  64. {
  65.   // concept requirements
  66.   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  67.         _RandomAccessIterator>);
  68.   __glibcpp_function_requires(_LessThanComparableConcept<
  69.         typename iterator_traits<_RandomAccessIterator>::value_type>);
  70.  
  71.   __push_heap_aux(__first, __last,
  72.                   __distance_type(__first), __value_type(__first));
  73. }
  74.  
  75. template <class _RandomAccessIterator, class _Distance, class _Tp,
  76.           class _Compare>
  77. void
  78. __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  79.             _Distance __topIndex, _Tp __value, _Compare __comp)
  80. {
  81.   _Distance __parent = (__holeIndex - 1) / 2;
  82.   while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
  83.     *(__first + __holeIndex) = *(__first + __parent);
  84.     __holeIndex = __parent;
  85.     __parent = (__holeIndex - 1) / 2;
  86.   }
  87.   *(__first + __holeIndex) = __value;
  88. }
  89.  
  90. template <class _RandomAccessIterator, class _Compare,
  91.           class _Distance, class _Tp>
  92. inline void
  93. __push_heap_aux(_RandomAccessIterator __first,
  94.                 _RandomAccessIterator __last, _Compare __comp,
  95.                 _Distance*, _Tp*)
  96. {
  97.   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
  98.               _Tp(*(__last - 1)), __comp);
  99. }
  100.  
  101. template <class _RandomAccessIterator, class _Compare>
  102. inline void
  103. push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  104.           _Compare __comp)
  105. {
  106.   // concept requirements
  107.   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  108.         _RandomAccessIterator>);
  109.  
  110.   __push_heap_aux(__first, __last, __comp,
  111.                   __distance_type(__first), __value_type(__first));
  112. }
  113.  
  114. template <class _RandomAccessIterator, class _Distance, class _Tp>
  115. void
  116. __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  117.               _Distance __len, _Tp __value)
  118. {
  119.   _Distance __topIndex = __holeIndex;
  120.   _Distance __secondChild = 2 * __holeIndex + 2;
  121.   while (__secondChild < __len) {
  122.     if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
  123.       __secondChild--;
  124.     *(__first + __holeIndex) = *(__first + __secondChild);
  125.     __holeIndex = __secondChild;
  126.     __secondChild = 2 * (__secondChild + 1);
  127.   }
  128.   if (__secondChild == __len) {
  129.     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
  130.     __holeIndex = __secondChild - 1;
  131.   }
  132.   __push_heap(__first, __holeIndex, __topIndex, __value);
  133. }
  134.  
  135. template <class _RandomAccessIterator, class _Tp, class _Distance>
  136. inline void
  137. __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  138.            _RandomAccessIterator __result, _Tp __value, _Distance*)
  139. {
  140.   *__result = *__first;
  141.   __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
  142. }
  143.  
  144. template <class _RandomAccessIterator, class _Tp>
  145. inline void
  146. __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
  147.                _Tp*)
  148. {
  149.   __pop_heap(__first, __last - 1, __last - 1,
  150.              _Tp(*(__last - 1)), __distance_type(__first));
  151. }
  152.  
  153. template <class _RandomAccessIterator>
  154. inline void pop_heap(_RandomAccessIterator __first,
  155.                      _RandomAccessIterator __last)
  156. {
  157.   // concept requirements
  158.   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  159.         _RandomAccessIterator>);
  160.   __glibcpp_function_requires(_LessThanComparableConcept<
  161.         typename iterator_traits<_RandomAccessIterator>::value_type>);
  162.  
  163.   __pop_heap_aux(__first, __last, __value_type(__first));
  164. }
  165.  
  166. template <class _RandomAccessIterator, class _Distance,
  167.           class _Tp, class _Compare>
  168. void
  169. __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  170.               _Distance __len, _Tp __value, _Compare __comp)
  171. {
  172.   _Distance __topIndex = __holeIndex;
  173.   _Distance __secondChild = 2 * __holeIndex + 2;
  174.   while (__secondChild < __len) {
  175.     if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
  176.       __secondChild--;
  177.     *(__first + __holeIndex) = *(__first + __secondChild);
  178.     __holeIndex = __secondChild;
  179.     __secondChild = 2 * (__secondChild + 1);
  180.   }
  181.   if (__secondChild == __len) {
  182.     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
  183.     __holeIndex = __secondChild - 1;
  184.   }
  185.   __push_heap(__first, __holeIndex, __topIndex, __value, __comp);
  186. }
  187.  
  188. template <class _RandomAccessIterator, class _Tp, class _Compare,
  189.           class _Distance>
  190. inline void
  191. __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  192.            _RandomAccessIterator __result, _Tp __value, _Compare __comp,
  193.            _Distance*)
  194. {
  195.   *__result = *__first;
  196.   __adjust_heap(__first, _Distance(0), _Distance(__last - __first),
  197.                 __value, __comp);
  198. }
  199.  
  200. template <class _RandomAccessIterator, class _Tp, class _Compare>
  201. inline void
  202. __pop_heap_aux(_RandomAccessIterator __first,
  203.                _RandomAccessIterator __last, _Tp*, _Compare __comp)
  204. {
  205.   __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
  206.              __distance_type(__first));
  207. }
  208.  
  209. template <class _RandomAccessIterator, class _Compare>
  210. inline void
  211. pop_heap(_RandomAccessIterator __first,
  212.          _RandomAccessIterator __last, _Compare __comp)
  213. {
  214.   // concept requirements
  215.   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  216.         _RandomAccessIterator>);
  217.  
  218.   __pop_heap_aux(__first, __last, __value_type(__first), __comp);
  219. }
  220.  
  221. template <class _RandomAccessIterator, class _Tp, class _Distance>
  222. void
  223. __make_heap(_RandomAccessIterator __first,
  224.             _RandomAccessIterator __last, _Tp*, _Distance*)
  225. {
  226.   if (__last - __first < 2) return;
  227.   _Distance __len = __last - __first;
  228.   _Distance __parent = (__len - 2)/2;
  229.    
  230.   while (true) {
  231.     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
  232.     if (__parent == 0) return;
  233.     __parent--;
  234.   }
  235. }
  236.  
  237. template <class _RandomAccessIterator>
  238. inline void
  239. make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  240. {
  241.   // concept requirements
  242.   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  243.         _RandomAccessIterator>);
  244.   __glibcpp_function_requires(_LessThanComparableConcept<
  245.         typename iterator_traits<_RandomAccessIterator>::value_type>);
  246.  
  247.   __make_heap(__first, __last,
  248.               __value_type(__first), __distance_type(__first));
  249. }
  250.  
  251. template <class _RandomAccessIterator, class _Compare,
  252.           class _Tp, class _Distance>
  253. void
  254. __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
  255.             _Compare __comp, _Tp*, _Distance*)
  256. {
  257.   if (__last - __first < 2) return;
  258.   _Distance __len = __last - __first;
  259.   _Distance __parent = (__len - 2)/2;
  260.    
  261.   while (true) {
  262.     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
  263.                   __comp);
  264.     if (__parent == 0) return;
  265.     __parent--;
  266.   }
  267. }
  268.  
  269. template <class _RandomAccessIterator, class _Compare>
  270. inline void
  271. make_heap(_RandomAccessIterator __first,
  272.           _RandomAccessIterator __last, _Compare __comp)
  273. {
  274.   // concept requirements
  275.   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  276.         _RandomAccessIterator>);
  277.  
  278.   __make_heap(__first, __last, __comp,
  279.               __value_type(__first), __distance_type(__first));
  280. }
  281.  
  282. template <class _RandomAccessIterator>
  283. void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  284. {
  285.   // concept requirements
  286.   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  287.         _RandomAccessIterator>);
  288.   __glibcpp_function_requires(_LessThanComparableConcept<
  289.         typename iterator_traits<_RandomAccessIterator>::value_type>);
  290.  
  291.   while (__last - __first > 1)
  292.     pop_heap(__first, __last--);
  293. }
  294.  
  295. template <class _RandomAccessIterator, class _Compare>
  296. void
  297. sort_heap(_RandomAccessIterator __first,
  298.           _RandomAccessIterator __last, _Compare __comp)
  299. {
  300.   // concept requirements
  301.   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  302.         _RandomAccessIterator>);
  303.  
  304.   while (__last - __first > 1)
  305.     pop_heap(__first, __last--, __comp);
  306. }
  307.  
  308. } // namespace std
  309.  
  310. #endif /* _CPP_BITS_STL_HEAP_H */
  311.  
  312. // Local Variables:
  313. // mode:C++
  314. // End:
  315.