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 41 template <class _RandomAccessIterator, class _Distance, class _Tp> 42 void 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 55 template <class _RandomAccessIterator, class _Distance, class _Tp> 56 inline 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 64 template <class _RandomAccessIterator> 65 inline void 66 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 67 { 68 __push_heap_aux(__first, __last, 69 __DISTANCE_TYPE(__first), __VALUE_TYPE(__first)); 70 } 71 72 template <class _RandomAccessIterator, class _Distance, class _Tp, 73 class _Compare> 74 void 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 87 template <class _RandomAccessIterator, class _Compare, 88 class _Distance, class _Tp> 89 inline 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 98 template <class _RandomAccessIterator, class _Compare> 99 inline void 100 push_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 107 template <class _RandomAccessIterator, class _Distance, class _Tp> 108 void 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 128 template <class _RandomAccessIterator, class _Tp, class _Distance> 129 inline 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 137 template <class _RandomAccessIterator, class _Tp> 138 inline 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 146 template <class _RandomAccessIterator> 147 inline void pop_heap(_RandomAccessIterator __first, 148 _RandomAccessIterator __last) 149 { 150 __pop_heap_aux(__first, __last, __VALUE_TYPE(__first)); 151 } 152 153 template <class _RandomAccessIterator, class _Distance, 154 class _Tp, class _Compare> 155 void 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 175 template <class _RandomAccessIterator, class _Tp, class _Compare, 176 class _Distance> 177 inline 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 187 template <class _RandomAccessIterator, class _Tp, class _Compare> 188 inline 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 196 template <class _RandomAccessIterator, class _Compare> 197 inline void 198 pop_heap(_RandomAccessIterator __first, 199 _RandomAccessIterator __last, _Compare __comp) 200 { 201 __pop_heap_aux(__first, __last, __VALUE_TYPE(__first), __comp); 202 } 203 204 template <class _RandomAccessIterator, class _Tp, class _Distance> 205 void 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 220 template <class _RandomAccessIterator> 221 inline void 222 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 223 { 224 __make_heap(__first, __last, 225 __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); 226 } 227 228 template <class _RandomAccessIterator, class _Compare, 229 class _Tp, class _Distance> 230 void 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 246 template <class _RandomAccessIterator, class _Compare> 247 inline void 248 make_heap(_RandomAccessIterator __first, 249 _RandomAccessIterator __last, _Compare __comp) 250 { 251 __make_heap(__first, __last, __comp, 252 __VALUE_TYPE(__first), __DISTANCE_TYPE(__first)); 253 } 254 255 template <class _RandomAccessIterator> 256 void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 257 { 258 while (__last - __first > 1) 259 pop_heap(__first, __last--); 260 } 261 262 template <class _RandomAccessIterator, class _Compare> 263 void 264 sort_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