libstdc++-v3/include/bits/stl_heap.h

   1 // Heap implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 3, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 /*
  27  *
  28  * Copyright (c) 1994
  29  * Hewlett-Packard Company
  30  *
  31  * Permission to use, copy, modify, distribute and sell this software
  32  * and its documentation for any purpose is hereby granted without fee,
  33  * provided that the above copyright notice appear in all copies and
  34  * that both that copyright notice and this permission notice appear
  35  * in supporting documentation.  Hewlett-Packard Company makes no
  36  * representations about the suitability of this software for any
  37  * purpose.  It is provided "as is" without express or implied warranty.
  38  *
  39  * Copyright (c) 1997
  40  * Silicon Graphics Computer Systems, Inc.
  41  *
  42  * Permission to use, copy, modify, distribute and sell this software
  43  * and its documentation for any purpose is hereby granted without fee,
  44  * provided that the above copyright notice appear in all copies and
  45  * that both that copyright notice and this permission notice appear
  46  * in supporting documentation.  Silicon Graphics makes no
  47  * representations about the suitability of this software for any
  48  * purpose.  It is provided "as is" without express or implied warranty.
  49  */
  50
  51 /** @file bits/stl_heap.h
  52  *  This is an internal header file, included by other library headers.
  53  *  Do not attempt to use it directly. @headername{queue}
  54  */
  55
  56 #ifndef _STL_HEAP_H
  57 #define _STL_HEAP_H 1
  58
  59 #include <debug/debug.h>
  60 #include <bits/move.h>
  61
  62 namespace std _GLIBCXX_VISIBILITY(default)
  63 {
  64 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  65
  66   /**
  67    * @defgroup heap_algorithms Heap
  68    * @ingroup sorting_algorithms
  69    */
  70
  71   template<typename _RandomAccessIterator, typename _Distance>
  72     _Distance
  73     __is_heap_until(_RandomAccessIterator __first, _Distance __n)
  74     {
  75       _Distance __parent = 0;
  76       for (_Distance __child = 1; __child < __n; ++__child)
  77         {
  78           if (__first[__parent] < __first[__child])
  79             return __child;
  80           if ((__child & 1) == 0)
  81             ++__parent;
  82         }
  83       return __n;
  84     }
  85
  86   template<typename _RandomAccessIterator, typename _Distance,
  87            typename _Compare>
  88     _Distance
  89     __is_heap_until(_RandomAccessIterator __first, _Distance __n,
  90                     _Compare __comp)
  91     {
  92       _Distance __parent = 0;
  93       for (_Distance __child = 1; __child < __n; ++__child)
  94         {
  95           if (__comp(__first[__parent], __first[__child]))
  96             return __child;
  97           if ((__child & 1) == 0)
  98             ++__parent;
  99         }
 100       return __n;
 101     }
 102
 103   // __is_heap, a predicate testing whether or not a range is a heap.
 104   // This function is an extension, not part of the C++ standard.
 105   template<typename _RandomAccessIterator, typename _Distance>
 106     inline bool
 107     __is_heap(_RandomAccessIterator __first, _Distance __n)
 108     { return std::__is_heap_until(__first, __n) == __n; }
 109
 110   template<typename _RandomAccessIterator, typename _Compare,
 111            typename _Distance>
 112     inline bool
 113     __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
 114     { return std::__is_heap_until(__first, __n, __comp) == __n; }
 115
 116   template<typename _RandomAccessIterator>
 117     inline bool
 118     __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 119     { return std::__is_heap(__first, std::distance(__first, __last)); }
 120
 121   template<typename _RandomAccessIterator, typename _Compare>
 122     inline bool
 123     __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 124               _Compare __comp)
 125     { return std::__is_heap(__first, __comp, std::distance(__first, __last)); }
 126
 127   // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
 128   // + is_heap and is_heap_until in C++0x.
 129
 130   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
 131     void
 132     __push_heap(_RandomAccessIterator __first,
 133                 _Distance __holeIndex, _Distance __topIndex, _Tp __value)
 134     {
 135       _Distance __parent = (__holeIndex - 1) / 2;
 136       while (__holeIndex > __topIndex && *(__first + __parent) < __value)
 137         {
 138           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
 139           __holeIndex = __parent;
 140           __parent = (__holeIndex - 1) / 2;
 141         }
 142       *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
 143     }
 144
 145   /**
 146    *  @brief  Push an element onto a heap.
 147    *  @param  __first  Start of heap.
 148    *  @param  __last   End of heap + element.
 149    *  @ingroup heap_algorithms
 150    *
 151    *  This operation pushes the element at last-1 onto the valid heap
 152    *  over the range [__first,__last-1).  After completion,
 153    *  [__first,__last) is a valid heap.
 154   */
 155   template<typename _RandomAccessIterator>
 156     inline void
 157     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 158     {
 159       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 160           _ValueType;
 161       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 162           _DistanceType;
 163
 164       // concept requirements
 165       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 166             _RandomAccessIterator>)
 167       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
 168       __glibcxx_requires_valid_range(__first, __last);
 169       __glibcxx_requires_heap(__first, __last - 1);
 170
 171       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
 172       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
 173                        _DistanceType(0), _GLIBCXX_MOVE(__value));
 174     }
 175
 176   template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
 177            typename _Compare>
 178     void
 179     __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 180                 _Distance __topIndex, _Tp __value, _Compare __comp)
 181     {
 182       _Distance __parent = (__holeIndex - 1) / 2;
 183       while (__holeIndex > __topIndex
 184              && __comp(*(__first + __parent), __value))
 185         {
 186           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
 187           __holeIndex = __parent;
 188           __parent = (__holeIndex - 1) / 2;
 189         }
 190       *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
 191     }
 192
 193   /**
 194    *  @brief  Push an element onto a heap using comparison functor.
 195    *  @param  __first  Start of heap.
 196    *  @param  __last   End of heap + element.
 197    *  @param  __comp   Comparison functor.
 198    *  @ingroup heap_algorithms
 199    *
 200    *  This operation pushes the element at __last-1 onto the valid
 201    *  heap over the range [__first,__last-1).  After completion,
 202    *  [__first,__last) is a valid heap.  Compare operations are
 203    *  performed using comp.
 204   */
 205   template<typename _RandomAccessIterator, typename _Compare>
 206     inline void
 207     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 208               _Compare __comp)
 209     {
 210       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 211           _ValueType;
 212       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 213           _DistanceType;
 214
 215       // concept requirements
 216       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 217             _RandomAccessIterator>)
 218       __glibcxx_requires_valid_range(__first, __last);
 219       __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
 220
 221       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
 222       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
 223                        _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
 224     }
 225
 226   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
 227     void
 228     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 229                   _Distance __len, _Tp __value)
 230     {
 231       const _Distance __topIndex = __holeIndex;
 232       _Distance __secondChild = __holeIndex;
 233       while (__secondChild < (__len - 1) / 2)
 234         {
 235           __secondChild = 2 * (__secondChild + 1);
 236           if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
 237             __secondChild--;
 238           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
 239           __holeIndex = __secondChild;
 240         }
 241       if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
 242         {
 243           __secondChild = 2 * (__secondChild + 1);
 244           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
 245                                                      + (__secondChild - 1)));
 246           __holeIndex = __secondChild - 1;
 247         }
 248       std::__push_heap(__first, __holeIndex, __topIndex,
 249                        _GLIBCXX_MOVE(__value));
 250     }
 251
 252   template<typename _RandomAccessIterator>
 253     inline void
 254     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 255                _RandomAccessIterator __result)
 256     {
 257       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 258         _ValueType;
 259       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 260         _DistanceType;
 261
 262       _ValueType __value = _GLIBCXX_MOVE(*__result);
 263       *__result = _GLIBCXX_MOVE(*__first);
 264       std::__adjust_heap(__first, _DistanceType(0),
 265                          _DistanceType(__last - __first),
 266                          _GLIBCXX_MOVE(__value));
 267     }
 268
 269   /**
 270    *  @brief  Pop an element off a heap.
 271    *  @param  __first  Start of heap.
 272    *  @param  __last   End of heap.
 273    *  @ingroup heap_algorithms
 274    *
 275    *  This operation pops the top of the heap.  The elements __first
 276    *  and __last-1 are swapped and [__first,__last-1) is made into a
 277    *  heap.
 278   */
 279   template<typename _RandomAccessIterator>
 280     inline void
 281     pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 282     {
 283       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 284         _ValueType;
 285
 286       // concept requirements
 287       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 288             _RandomAccessIterator>)
 289       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
 290       __glibcxx_requires_valid_range(__first, __last);
 291       __glibcxx_requires_heap(__first, __last);
 292
 293       --__last;
 294       std::__pop_heap(__first, __last, __last);
 295     }
 296
 297   template<typename _RandomAccessIterator, typename _Distance,
 298            typename _Tp, typename _Compare>
 299     void
 300     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 301                   _Distance __len, _Tp __value, _Compare __comp)
 302     {
 303       const _Distance __topIndex = __holeIndex;
 304       _Distance __secondChild = __holeIndex;
 305       while (__secondChild < (__len - 1) / 2)
 306         {
 307           __secondChild = 2 * (__secondChild + 1);
 308           if (__comp(*(__first + __secondChild),
 309                      *(__first + (__secondChild - 1))))
 310             __secondChild--;
 311           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
 312           __holeIndex = __secondChild;
 313         }
 314       if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
 315         {
 316           __secondChild = 2 * (__secondChild + 1);
 317           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
 318                                                      + (__secondChild - 1)));
 319           __holeIndex = __secondChild - 1;
 320         }
 321       std::__push_heap(__first, __holeIndex, __topIndex,
 322                        _GLIBCXX_MOVE(__value), __comp);
 323     }
 324
 325   template<typename _RandomAccessIterator, typename _Compare>
 326     inline void
 327     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 328                _RandomAccessIterator __result, _Compare __comp)
 329     {
 330       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 331         _ValueType;
 332       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 333         _DistanceType;
 334
 335       _ValueType __value = _GLIBCXX_MOVE(*__result);
 336       *__result = _GLIBCXX_MOVE(*__first);
 337       std::__adjust_heap(__first, _DistanceType(0),
 338                          _DistanceType(__last - __first),
 339                          _GLIBCXX_MOVE(__value), __comp);
 340     }
 341
 342   /**
 343    *  @brief  Pop an element off a heap using comparison functor.
 344    *  @param  __first  Start of heap.
 345    *  @param  __last   End of heap.
 346    *  @param  __comp   Comparison functor to use.
 347    *  @ingroup heap_algorithms
 348    *
 349    *  This operation pops the top of the heap.  The elements __first
 350    *  and __last-1 are swapped and [__first,__last-1) is made into a
 351    *  heap.  Comparisons are made using comp.
 352   */
 353   template<typename _RandomAccessIterator, typename _Compare>
 354     inline void
 355     pop_heap(_RandomAccessIterator __first,
 356              _RandomAccessIterator __last, _Compare __comp)
 357     {
 358       // concept requirements
 359       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 360             _RandomAccessIterator>)
 361       __glibcxx_requires_valid_range(__first, __last);
 362       __glibcxx_requires_heap_pred(__first, __last, __comp);
 363
 364       --__last;
 365       std::__pop_heap(__first, __last, __last, __comp);
 366     }
 367
 368   /**
 369    *  @brief  Construct a heap over a range.
 370    *  @param  __first  Start of heap.
 371    *  @param  __last   End of heap.
 372    *  @ingroup heap_algorithms
 373    *
 374    *  This operation makes the elements in [__first,__last) into a heap.
 375   */
 376   template<typename _RandomAccessIterator>
 377     void
 378     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 379     {
 380       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 381           _ValueType;
 382       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 383           _DistanceType;
 384
 385       // concept requirements
 386       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 387             _RandomAccessIterator>)
 388       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
 389       __glibcxx_requires_valid_range(__first, __last);
 390
 391       if (__last - __first < 2)
 392         return;
 393
 394       const _DistanceType __len = __last - __first;
 395       _DistanceType __parent = (__len - 2) / 2;
 396       while (true)
 397         {
 398           _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
 399           std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value));
 400           if (__parent == 0)
 401             return;
 402           __parent--;
 403         }
 404     }
 405
 406   /**
 407    *  @brief  Construct a heap over a range using comparison functor.
 408    *  @param  __first  Start of heap.
 409    *  @param  __last   End of heap.
 410    *  @param  __comp   Comparison functor to use.
 411    *  @ingroup heap_algorithms
 412    *
 413    *  This operation makes the elements in [__first,__last) into a heap.
 414    *  Comparisons are made using __comp.
 415   */
 416   template<typename _RandomAccessIterator, typename _Compare>
 417     void
 418     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 419               _Compare __comp)
 420     {
 421       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 422           _ValueType;
 423       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 424           _DistanceType;
 425
 426       // concept requirements
 427       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 428             _RandomAccessIterator>)
 429       __glibcxx_requires_valid_range(__first, __last);
 430
 431       if (__last - __first < 2)
 432         return;
 433
 434       const _DistanceType __len = __last - __first;
 435       _DistanceType __parent = (__len - 2) / 2;
 436       while (true)
 437         {
 438           _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
 439           std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
 440                              __comp);
 441           if (__parent == 0)
 442             return;
 443           __parent--;
 444         }
 445     }
 446
 447   /**
 448    *  @brief  Sort a heap.
 449    *  @param  __first  Start of heap.
 450    *  @param  __last   End of heap.
 451    *  @ingroup heap_algorithms
 452    *
 453    *  This operation sorts the valid heap in the range [__first,__last).
 454   */
 455   template<typename _RandomAccessIterator>
 456     void
 457     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 458     {
 459       // concept requirements
 460       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 461             _RandomAccessIterator>)
 462       __glibcxx_function_requires(_LessThanComparableConcept<
 463             typename iterator_traits<_RandomAccessIterator>::value_type>)
 464       __glibcxx_requires_valid_range(__first, __last);
 465       __glibcxx_requires_heap(__first, __last);
 466
 467       while (__last - __first > 1)
 468         {
 469           --__last;
 470           std::__pop_heap(__first, __last, __last);
 471         }
 472     }
 473
 474   /**
 475    *  @brief  Sort a heap using comparison functor.
 476    *  @param  __first  Start of heap.
 477    *  @param  __last   End of heap.
 478    *  @param  __comp   Comparison functor to use.
 479    *  @ingroup heap_algorithms
 480    *
 481    *  This operation sorts the valid heap in the range [__first,__last).
 482    *  Comparisons are made using __comp.
 483   */
 484   template<typename _RandomAccessIterator, typename _Compare>
 485     void
 486     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 487               _Compare __comp)
 488     {
 489       // concept requirements
 490       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 491             _RandomAccessIterator>)
 492       __glibcxx_requires_valid_range(__first, __last);
 493       __glibcxx_requires_heap_pred(__first, __last, __comp);
 494
 495       while (__last - __first > 1)
 496         {
 497           --__last;
 498           std::__pop_heap(__first, __last, __last, __comp);
 499         }
 500     }
 501
 502 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 503   /**
 504    *  @brief  Search the end of a heap.
 505    *  @param  __first  Start of range.
 506    *  @param  __last   End of range.
 507    *  @return  An iterator pointing to the first element not in the heap.
 508    *  @ingroup heap_algorithms
 509    *
 510    *  This operation returns the last iterator i in [__first, __last) for which
 511    *  the range [__first, i) is a heap.
 512   */
 513   template<typename _RandomAccessIterator>
 514     inline _RandomAccessIterator
 515     is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
 516     {
 517       // concept requirements
 518       __glibcxx_function_requires(_RandomAccessIteratorConcept<
 519             _RandomAccessIterator>)
 520       __glibcxx_function_requires(_LessThanComparableConcept<
 521             typename iterator_traits<_RandomAccessIterator>::value_type>)
 522       __glibcxx_requires_valid_range(__first, __last);
 523
 524       return __first + std::__is_heap_until(__first, std::distance(__first,
 525                                                                    __last));
 526     }
 527
 528   /**
 529    *  @brief  Search the end of a heap using comparison functor.
 530    *  @param  __first  Start of range.
 531    *  @param  __last   End of range.
 532    *  @param  __comp   Comparison functor to use.
 533    *  @return  An iterator pointing to the first element not in the heap.
 534    *  @ingroup heap_algorithms
 535    *
 536    *  This operation returns the last iterator i in [__first, __last) for which
 537    *  the range [__first, i) is a heap.  Comparisons are made using __comp.
 538   */
 539   template<typename _RandomAccessIterator, typename _Compare>
 540     inline _RandomAccessIterator
 541     is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
 542                   _Compare __comp)
 543     {
 544       // concept requirements
 545       __glibcxx_function_requires(_RandomAccessIteratorConcept<
 546             _RandomAccessIterator>)
 547       __glibcxx_requires_valid_range(__first, __last);
 548
 549       return __first + std::__is_heap_until(__first, std::distance(__first,
 550                                                                    __last),
 551                                             __comp);
 552     }
 553
 554   /**
 555    *  @brief  Determines whether a range is a heap.
 556    *  @param  __first  Start of range.
 557    *  @param  __last   End of range.
 558    *  @return  True if range is a heap, false otherwise.
 559    *  @ingroup heap_algorithms
 560   */
 561   template<typename _RandomAccessIterator>
 562     inline bool
 563     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 564     { return std::is_heap_until(__first, __last) == __last; }
 565
 566   /**
 567    *  @brief  Determines whether a range is a heap using comparison functor.
 568    *  @param  __first  Start of range.
 569    *  @param  __last   End of range.
 570    *  @param  __comp   Comparison functor to use.
 571    *  @return  True if range is a heap, false otherwise.
 572    *  @ingroup heap_algorithms
 573   */
 574   template<typename _RandomAccessIterator, typename _Compare>
 575     inline bool
 576     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 577             _Compare __comp)
 578     { return std::is_heap_until(__first, __last, __comp) == __last; }
 579 #endif
 580
 581 _GLIBCXX_END_NAMESPACE_VERSION
 582 } // namespace
 583
 584 #endif /* _STL_HEAP_H */