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