1// Heap implementation -*- C++ -*- 2 3// Copyright (C) 2001, 2004, 2005, 2006 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 _STL_HEAP_H 61#define _STL_HEAP_H 1 62 63#include <debug/debug.h> 64 65_GLIBCXX_BEGIN_NAMESPACE(std) 66 67 // is_heap, a predicate testing whether or not a range is 68 // a heap. This function is an extension, not part of the C++ 69 // standard. 70 template<typename _RandomAccessIterator, typename _Distance> 71 bool 72 __is_heap(_RandomAccessIterator __first, _Distance __n) 73 { 74 _Distance __parent = 0; 75 for (_Distance __child = 1; __child < __n; ++__child) 76 { 77 if (__first[__parent] < __first[__child]) 78 return false; 79 if ((__child & 1) == 0) 80 ++__parent; 81 } 82 return true; 83 } 84 85 template<typename _RandomAccessIterator, typename _Distance, 86 typename _StrictWeakOrdering> 87 bool 88 __is_heap(_RandomAccessIterator __first, _StrictWeakOrdering __comp, 89 _Distance __n) 90 { 91 _Distance __parent = 0; 92 for (_Distance __child = 1; __child < __n; ++__child) 93 { 94 if (__comp(__first[__parent], __first[__child])) 95 return false; 96 if ((__child & 1) == 0) 97 ++__parent; 98 } 99 return true; 100 } 101 102 template<typename _RandomAccessIterator> 103 bool 104 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 105 { return std::__is_heap(__first, std::distance(__first, __last)); } 106 107 template<typename _RandomAccessIterator, typename _StrictWeakOrdering> 108 bool 109 __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 110 _StrictWeakOrdering __comp) 111 { return std::__is_heap(__first, __comp, std::distance(__first, __last)); } 112 113 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap. 114 115 template<typename _RandomAccessIterator, typename _Distance, typename _Tp> 116 void 117 __push_heap(_RandomAccessIterator __first, 118 _Distance __holeIndex, _Distance __topIndex, _Tp __value) 119 { 120 _Distance __parent = (__holeIndex - 1) / 2; 121 while (__holeIndex > __topIndex && *(__first + __parent) < __value) 122 { 123 *(__first + __holeIndex) = *(__first + __parent); 124 __holeIndex = __parent; 125 __parent = (__holeIndex - 1) / 2; 126 } 127 *(__first + __holeIndex) = __value; 128 } 129 130 /** 131 * @brief Push an element onto a heap. 132 * @param first Start of heap. 133 * @param last End of heap + element. 134 * @ingroup heap 135 * 136 * This operation pushes the element at last-1 onto the valid heap over the 137 * range [first,last-1). After completion, [first,last) is a valid heap. 138 */ 139 template<typename _RandomAccessIterator> 140 inline void 141 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 142 { 143 typedef typename iterator_traits<_RandomAccessIterator>::value_type 144 _ValueType; 145 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 146 _DistanceType; 147 148 // concept requirements 149 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 150 _RandomAccessIterator>) 151 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 152 __glibcxx_requires_valid_range(__first, __last); 153 // __glibcxx_requires_heap(__first, __last - 1); 154 155 std::__push_heap(__first, _DistanceType((__last - __first) - 1), 156 _DistanceType(0), _ValueType(*(__last - 1))); 157 } 158 159 template<typename _RandomAccessIterator, typename _Distance, typename _Tp, 160 typename _Compare> 161 void 162 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex, 163 _Distance __topIndex, _Tp __value, _Compare __comp) 164 { 165 _Distance __parent = (__holeIndex - 1) / 2; 166 while (__holeIndex > __topIndex 167 && __comp(*(__first + __parent), __value)) 168 { 169 *(__first + __holeIndex) = *(__first + __parent); 170 __holeIndex = __parent; 171 __parent = (__holeIndex - 1) / 2; 172 } 173 *(__first + __holeIndex) = __value; 174 } 175 176 /** 177 * @brief Push an element onto a heap using comparison functor. 178 * @param first Start of heap. 179 * @param last End of heap + element. 180 * @param comp Comparison functor. 181 * @ingroup heap 182 * 183 * This operation pushes the element at last-1 onto the valid heap over the 184 * range [first,last-1). After completion, [first,last) is a valid heap. 185 * Compare operations are performed using comp. 186 */ 187 template<typename _RandomAccessIterator, typename _Compare> 188 inline void 189 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 190 _Compare __comp) 191 { 192 typedef typename iterator_traits<_RandomAccessIterator>::value_type 193 _ValueType; 194 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 195 _DistanceType; 196 197 // concept requirements 198 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 199 _RandomAccessIterator>) 200 __glibcxx_requires_valid_range(__first, __last); 201 __glibcxx_requires_heap_pred(__first, __last - 1, __comp); 202 203 std::__push_heap(__first, _DistanceType((__last - __first) - 1), 204 _DistanceType(0), _ValueType(*(__last - 1)), __comp); 205 } 206 207 template<typename _RandomAccessIterator, typename _Distance, typename _Tp> 208 void 209 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 210 _Distance __len, _Tp __value) 211 { 212 const _Distance __topIndex = __holeIndex; 213 _Distance __secondChild = 2 * __holeIndex + 2; 214 while (__secondChild < __len) 215 { 216 if (*(__first + __secondChild) < *(__first + (__secondChild - 1))) 217 __secondChild--; 218 *(__first + __holeIndex) = *(__first + __secondChild); 219 __holeIndex = __secondChild; 220 __secondChild = 2 * (__secondChild + 1); 221 } 222 if (__secondChild == __len) 223 { 224 *(__first + __holeIndex) = *(__first + (__secondChild - 1)); 225 __holeIndex = __secondChild - 1; 226 } 227 std::__push_heap(__first, __holeIndex, __topIndex, __value); 228 } 229 230 template<typename _RandomAccessIterator, typename _Tp> 231 inline void 232 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 233 _RandomAccessIterator __result, _Tp __value) 234 { 235 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 236 _Distance; 237 *__result = *__first; 238 std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first), 239 __value); 240 } 241 242 /** 243 * @brief Pop an element off a heap. 244 * @param first Start of heap. 245 * @param last End of heap. 246 * @ingroup heap 247 * 248 * This operation pops the top of the heap. The elements first and last-1 249 * are swapped and [first,last-1) is made into a heap. 250 */ 251 template<typename _RandomAccessIterator> 252 inline void 253 pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 254 { 255 typedef typename iterator_traits<_RandomAccessIterator>::value_type 256 _ValueType; 257 258 // concept requirements 259 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 260 _RandomAccessIterator>) 261 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 262 __glibcxx_requires_valid_range(__first, __last); 263 __glibcxx_requires_heap(__first, __last); 264 265 std::__pop_heap(__first, __last - 1, __last - 1, 266 _ValueType(*(__last - 1))); 267 } 268 269 template<typename _RandomAccessIterator, typename _Distance, 270 typename _Tp, typename _Compare> 271 void 272 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex, 273 _Distance __len, _Tp __value, _Compare __comp) 274 { 275 const _Distance __topIndex = __holeIndex; 276 _Distance __secondChild = 2 * __holeIndex + 2; 277 while (__secondChild < __len) 278 { 279 if (__comp(*(__first + __secondChild), 280 *(__first + (__secondChild - 1)))) 281 __secondChild--; 282 *(__first + __holeIndex) = *(__first + __secondChild); 283 __holeIndex = __secondChild; 284 __secondChild = 2 * (__secondChild + 1); 285 } 286 if (__secondChild == __len) 287 { 288 *(__first + __holeIndex) = *(__first + (__secondChild - 1)); 289 __holeIndex = __secondChild - 1; 290 } 291 std::__push_heap(__first, __holeIndex, __topIndex, __value, __comp); 292 } 293 294 template<typename _RandomAccessIterator, typename _Tp, typename _Compare> 295 inline void 296 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 297 _RandomAccessIterator __result, _Tp __value, _Compare __comp) 298 { 299 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 300 _Distance; 301 *__result = *__first; 302 std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first), 303 __value, __comp); 304 } 305 306 /** 307 * @brief Pop an element off a heap using comparison functor. 308 * @param first Start of heap. 309 * @param last End of heap. 310 * @param comp Comparison functor to use. 311 * @ingroup heap 312 * 313 * This operation pops the top of the heap. The elements first and last-1 314 * are swapped and [first,last-1) is made into a heap. Comparisons are 315 * made using comp. 316 */ 317 template<typename _RandomAccessIterator, typename _Compare> 318 inline void 319 pop_heap(_RandomAccessIterator __first, 320 _RandomAccessIterator __last, _Compare __comp) 321 { 322 // concept requirements 323 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 324 _RandomAccessIterator>) 325 __glibcxx_requires_valid_range(__first, __last); 326 __glibcxx_requires_heap_pred(__first, __last, __comp); 327 328 typedef typename iterator_traits<_RandomAccessIterator>::value_type 329 _ValueType; 330 std::__pop_heap(__first, __last - 1, __last - 1, 331 _ValueType(*(__last - 1)), __comp); 332 } 333 334 /** 335 * @brief Construct a heap over a range. 336 * @param first Start of heap. 337 * @param last End of heap. 338 * @ingroup heap 339 * 340 * This operation makes the elements in [first,last) into a heap. 341 */ 342 template<typename _RandomAccessIterator> 343 void 344 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 345 { 346 typedef typename iterator_traits<_RandomAccessIterator>::value_type 347 _ValueType; 348 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 349 _DistanceType; 350 351 // concept requirements 352 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 353 _RandomAccessIterator>) 354 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) 355 __glibcxx_requires_valid_range(__first, __last); 356 357 if (__last - __first < 2) 358 return; 359 360 const _DistanceType __len = __last - __first; 361 _DistanceType __parent = (__len - 2) / 2; 362 while (true) 363 { 364 std::__adjust_heap(__first, __parent, __len, 365 _ValueType(*(__first + __parent))); 366 if (__parent == 0) 367 return; 368 __parent--; 369 } 370 } 371 372 /** 373 * @brief Construct a heap over a range using comparison functor. 374 * @param first Start of heap. 375 * @param last End of heap. 376 * @param comp Comparison functor to use. 377 * @ingroup heap 378 * 379 * This operation makes the elements in [first,last) into a heap. 380 * Comparisons are made using comp. 381 */ 382 template<typename _RandomAccessIterator, typename _Compare> 383 inline void 384 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 385 _Compare __comp) 386 { 387 typedef typename iterator_traits<_RandomAccessIterator>::value_type 388 _ValueType; 389 typedef typename iterator_traits<_RandomAccessIterator>::difference_type 390 _DistanceType; 391 392 // concept requirements 393 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 394 _RandomAccessIterator>) 395 __glibcxx_requires_valid_range(__first, __last); 396 397 if (__last - __first < 2) 398 return; 399 400 const _DistanceType __len = __last - __first; 401 _DistanceType __parent = (__len - 2) / 2; 402 while (true) 403 { 404 std::__adjust_heap(__first, __parent, __len, 405 _ValueType(*(__first + __parent)), __comp); 406 if (__parent == 0) 407 return; 408 __parent--; 409 } 410 } 411 412 /** 413 * @brief Sort a heap. 414 * @param first Start of heap. 415 * @param last End of heap. 416 * @ingroup heap 417 * 418 * This operation sorts the valid heap in the range [first,last). 419 */ 420 template<typename _RandomAccessIterator> 421 void 422 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) 423 { 424 // concept requirements 425 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 426 _RandomAccessIterator>) 427 __glibcxx_function_requires(_LessThanComparableConcept< 428 typename iterator_traits<_RandomAccessIterator>::value_type>) 429 __glibcxx_requires_valid_range(__first, __last); 430 // __glibcxx_requires_heap(__first, __last); 431 432 while (__last - __first > 1) 433 std::pop_heap(__first, _RandomAccessIterator(__last--)); 434 } 435 436 /** 437 * @brief Sort a heap using comparison functor. 438 * @param first Start of heap. 439 * @param last End of heap. 440 * @param comp Comparison functor to use. 441 * @ingroup heap 442 * 443 * This operation sorts the valid heap in the range [first,last). 444 * Comparisons are made using comp. 445 */ 446 template<typename _RandomAccessIterator, typename _Compare> 447 void 448 sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, 449 _Compare __comp) 450 { 451 // concept requirements 452 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< 453 _RandomAccessIterator>) 454 __glibcxx_requires_valid_range(__first, __last); 455 __glibcxx_requires_heap_pred(__first, __last, __comp); 456 457 while (__last - __first > 1) 458 std::pop_heap(__first, _RandomAccessIterator(__last--), __comp); 459 } 460 461_GLIBCXX_END_NAMESPACE 462 463#endif /* _STL_HEAP_H */ 464