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 _STLP_INTERNAL_HEAP_H 31#define _STLP_INTERNAL_HEAP_H 32 33_STLP_BEGIN_NAMESPACE 34 35// Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap. 36 37template <class _RandomAccessIterator> 38void 39push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last); 40 41 42template <class _RandomAccessIterator, class _Compare> 43void 44push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 45 _Compare __comp); 46 47template <class _RandomAccessIterator, class _Distance, class _Tp> 48void 49__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 50 _Distance __len, _Tp __val); 51 52template <class _RandomAccessIterator, class _Tp, class _Distance> 53inline void 54__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 55 _RandomAccessIterator __result, _Tp __val, _Distance*) 56{ 57 *__result = *__first; 58 __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __val); 59} 60 61template <class _RandomAccessIterator> 62void pop_heap(_RandomAccessIterator __first, 63 _RandomAccessIterator __last); 64 65template <class _RandomAccessIterator, class _Distance, 66 class _Tp, class _Compare> 67void 68__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 69 _Distance __len, _Tp __val, _Compare __comp); 70 71template <class _RandomAccessIterator, class _Tp, class _Compare, 72 class _Distance> 73inline void 74__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 75 _RandomAccessIterator __result, _Tp __val, _Compare __comp, 76 _Distance*) 77{ 78 *__result = *__first; 79 __adjust_heap(__first, _Distance(0), _Distance(__last - __first), 80 __val, __comp); 81} 82 83template <class _RandomAccessIterator, class _Compare> 84void 85pop_heap(_RandomAccessIterator __first, 86 _RandomAccessIterator __last, _Compare __comp); 87 88template <class _RandomAccessIterator> 89void 90make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last); 91 92template <class _RandomAccessIterator, class _Compare> 93void 94make_heap(_RandomAccessIterator __first, 95 _RandomAccessIterator __last, _Compare __comp); 96 97template <class _RandomAccessIterator> 98_STLP_INLINE_LOOP 99void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 100{ 101 while (__last - __first > 1) 102 pop_heap(__first, __last--); 103} 104 105template <class _RandomAccessIterator, class _Compare> 106_STLP_INLINE_LOOP 107void 108sort_heap(_RandomAccessIterator __first, 109 _RandomAccessIterator __last, _Compare __comp) 110{ 111 while (__last - __first > 1) 112 pop_heap(__first, __last--, __comp); 113} 114 115_STLP_END_NAMESPACE 116 117# if !defined (_STLP_LINK_TIME_INSTANTIATION) 118# include <stl/_heap.c> 119# endif 120 121#endif /* _STLP_INTERNAL_HEAP_H */ 122 123// Local Variables: 124// mode:C++ 125// End: 126