1// Heap implementation -*- C++ -*- 2 3// Copyright (C) 2001 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 2, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// You should have received a copy of the GNU General Public License along 17// with this library; see the file COPYING. If not, write to the Free 18// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 19// USA. 20 21// As a special exception, you may use this file as part of a free software 22// library without restriction. Specifically, if other files instantiate 23// templates or use macros or inline functions from this file, or you compile 24// this file and link it with other files to produce an executable, this 25// file does not by itself cause the resulting executable to be covered by 26// the GNU General Public License. This exception does not however 27// invalidate any other reasons why the executable file might be covered by 28// the GNU General Public License. 29 30/* 31 * 32 * Copyright (c) 1994 33 * Hewlett-Packard Company 34 * 35 * Permission to use, copy, modify, distribute and sell this software 36 * and its documentation for any purpose is hereby granted without fee, 37 * provided that the above copyright notice appear in all copies and 38 * that both that copyright notice and this permission notice appear 39 * in supporting documentation. Hewlett-Packard Company makes no 40 * representations about the suitability of this software for any 41 * purpose. It is provided "as is" without express or implied warranty. 42 * 43 * Copyright (c) 1997 44 * Silicon Graphics Computer Systems, Inc. 45 * 46 * Permission to use, copy, modify, distribute and sell this software 47 * and its documentation for any purpose is hereby granted without fee, 48 * provided that the above copyright notice appear in all copies and 49 * that both that copyright notice and this permission notice appear 50 * in supporting documentation. Silicon Graphics makes no 51 * representations about the suitability of this software for any 52 * purpose. It is provided "as is" without express or implied warranty. 53 */ 54 55/** @file stl_heap.h 56 * This is an internal header file, included by other library headers. 57 * You should not attempt to use it directly. 58 */ 59 60#ifndef _CPP_BITS_STL_HEAP_H 61#define _CPP_BITS_STL_HEAP_H 1 62 63namespace std 64{ 65 66 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap. 67 68 template<typename _RandomAccessIterator, typename _Distance, typename _Tp> 69 void 70 __push_heap(_RandomAccessIterator __first, 71 _Distance __holeIndex, _Distance __topIndex, _Tp __value) 72 { 73 _Distance __parent = (__holeIndex - 1) / 2; 74 while (__holeIndex > __topIndex && *(__first + __parent) < __value) { 75 *(__first + __holeIndex) = *(__first + __parent); 76 __holeIndex = __parent; 77 __parent = (__holeIndex - 1) / 2; 78 } 79 *(__first + __holeIndex) = __value; 80 } 81 82 template<typename _RandomAccessIterator> 83 inline void 84 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 85 { 86 typedef typename iterator_traits<_RandomAccessIterator>::value_type 87 _ValueType; 88 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 89 _DistanceType; 90 91 // concept requirements 92 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 93 _RandomAccessIterator>) 94 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 95 96 __push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), 97 _ValueType(*(__last - 1))); 98 } 99 100 template<typename _RandomAccessIterator, typename _Distance, typename _Tp, 101 typename _Compare> 102 void 103 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, 104 _Distance __topIndex, _Tp __value, _Compare __comp) 105 { 106 _Distance __parent = (__holeIndex - 1) / 2; 107 while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) { 108 *(__first + __holeIndex) = *(__first + __parent); 109 __holeIndex = __parent; 110 __parent = (__holeIndex - 1) / 2; 111 } 112 *(__first + __holeIndex) = __value; 113 } 114 115 template<typename _RandomAccessIterator, typename _Compare> 116 inline void 117 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 118 _Compare __comp) 119 { 120 typedef typename iterator_traits<_RandomAccessIterator>::value_type 121 _ValueType; 122 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 123 _DistanceType; 124 125 // concept requirements 126 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 127 _RandomAccessIterator>) 128 129 __push_heap(__first, _DistanceType((__last - __first) - 1), _DistanceType(0), 130 _ValueType(*(__last - 1)), __comp); 131 } 132 133 template<typename _RandomAccessIterator, typename _Distance, typename _Tp> 134 void 135 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 136 _Distance __len, _Tp __value) 137 { 138 _Distance __topIndex = __holeIndex; 139 _Distance __secondChild = 2 * __holeIndex + 2; 140 while (__secondChild < __len) { 141 if (*(__first + __secondChild) < *(__first + (__secondChild - 1))) 142 __secondChild--; 143 *(__first + __holeIndex) = *(__first + __secondChild); 144 __holeIndex = __secondChild; 145 __secondChild = 2 * (__secondChild + 1); 146 } 147 if (__secondChild == __len) { 148 *(__first + __holeIndex) = *(__first + (__secondChild - 1)); 149 __holeIndex = __secondChild - 1; 150 } 151 __push_heap(__first, __holeIndex, __topIndex, __value); 152 } 153 154 template<typename _RandomAccessIterator, typename _Tp> 155 inline void 156 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 157 _RandomAccessIterator __result, _Tp __value) 158 { 159 typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance; 160 *__result = *__first; 161 __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value); 162 } 163 164 template<typename _RandomAccessIterator> 165 inline void 166 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 167 { 168 typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; 169 170 // concept requirements 171 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 172 _RandomAccessIterator>) 173 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 174 175 __pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1))); 176 } 177 178 template<typename _RandomAccessIterator, typename _Distance, 179 typename _Tp, typename _Compare> 180 void 181 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 182 _Distance __len, _Tp __value, _Compare __comp) 183 { 184 _Distance __topIndex = __holeIndex; 185 _Distance __secondChild = 2 * __holeIndex + 2; 186 while (__secondChild < __len) { 187 if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1)))) 188 __secondChild--; 189 *(__first + __holeIndex) = *(__first + __secondChild); 190 __holeIndex = __secondChild; 191 __secondChild = 2 * (__secondChild + 1); 192 } 193 if (__secondChild == __len) { 194 *(__first + __holeIndex) = *(__first + (__secondChild - 1)); 195 __holeIndex = __secondChild - 1; 196 } 197 __push_heap(__first, __holeIndex, __topIndex, __value, __comp); 198 } 199 200 template<typename _RandomAccessIterator, typename _Tp, typename _Compare> 201 inline void 202 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 203 _RandomAccessIterator __result, _Tp __value, _Compare __comp) 204 { 205 typedef typename iterator_traits<_RandomAccessIterator>::difference_type _Distance; 206 *__result = *__first; 207 __adjust_heap(__first, _Distance(0), _Distance(__last - __first), 208 __value, __comp); 209 } 210 211 template<typename _RandomAccessIterator, typename _Compare> 212 inline void 213 pop_heap(_RandomAccessIterator __first, 214 _RandomAccessIterator __last, _Compare __comp) 215 { 216 // concept requirements 217 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 218 _RandomAccessIterator>) 219 220 typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType; 221 __pop_heap(__first, __last - 1, __last - 1, _ValueType(*(__last - 1)), __comp); 222 } 223 224 template<typename _RandomAccessIterator> 225 void 226 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 227 { 228 typedef typename iterator_traits<_RandomAccessIterator>::value_type 229 _ValueType; 230 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 231 _DistanceType; 232 233 // concept requirements 234 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 235 _RandomAccessIterator>) 236 __glibcpp_function_requires(_LessThanComparableConcept<_ValueType>) 237 238 if (__last - __first < 2) return; 239 _DistanceType __len = __last - __first; 240 _DistanceType __parent = (__len - 2)/2; 241 242 while (true) { 243 __adjust_heap(__first, __parent, __len, _ValueType(*(__first + __parent))); 244 if (__parent == 0) return; 245 __parent--; 246 } 247 } 248 249 template<typename _RandomAccessIterator, typename _Compare> 250 inline void 251 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 252 _Compare __comp) 253 { 254 typedef typename iterator_traits<_RandomAccessIterator>::value_type 255 _ValueType; 256 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 257 _DistanceType; 258 259 // concept requirements 260 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 261 _RandomAccessIterator>) 262 263 if (__last - __first < 2) return; 264 _DistanceType __len = __last - __first; 265 _DistanceType __parent = (__len - 2)/2; 266 267 while (true) { 268 __adjust_heap(__first, __parent, __len, 269 _ValueType(*(__first + __parent)), __comp); 270 if (__parent == 0) return; 271 __parent--; 272 } 273 } 274 275 template<typename _RandomAccessIterator> 276 void 277 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 278 { 279 // concept requirements 280 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 281 _RandomAccessIterator>) 282 __glibcpp_function_requires(_LessThanComparableConcept< 283 typename iterator_traits<_RandomAccessIterator>::value_type>) 284 285 while (__last - __first > 1) 286 pop_heap(__first, __last--); 287 } 288 289 template<typename _RandomAccessIterator, typename _Compare> 290 void 291 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 292 _Compare __comp) 293 { 294 // concept requirements 295 __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept< 296 _RandomAccessIterator>) 297 298 while (__last - __first > 1) 299 pop_heap(__first, __last--, __comp); 300 } 301 302} // namespace std 303 304#endif /* _CPP_BITS_STL_HEAP_H */ 305 306// Local Variables: 307// mode:C++ 308// End: 309