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

   1 // Heap implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
   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 2, 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 // You should have received a copy of the GNU General Public License along
  18 // with this library; see the file COPYING.  If not, write to the Free
  19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  20 // USA.
  21
  22 // As a special exception, you may use this file as part of a free software
  23 // library without restriction.  Specifically, if other files instantiate
  24 // templates or use macros or inline functions from this file, or you compile
  25 // this file and link it with other files to produce an executable, this
  26 // file does not by itself cause the resulting executable to be covered by
  27 // the GNU General Public License.  This exception does not however
  28 // invalidate any other reasons why the executable file might be covered by
  29 // the GNU General Public License.
  30
  31 /*
  32  *
  33  * Copyright (c) 1994
  34  * Hewlett-Packard Company
  35  *
  36  * Permission to use, copy, modify, distribute and sell this software
  37  * and its documentation for any purpose is hereby granted without fee,
  38  * provided that the above copyright notice appear in all copies and
  39  * that both that copyright notice and this permission notice appear
  40  * in supporting documentation.  Hewlett-Packard Company makes no
  41  * representations about the suitability of this software for any
  42  * purpose.  It is provided "as is" without express or implied warranty.
  43  *
  44  * Copyright (c) 1997
  45  * Silicon Graphics Computer Systems, Inc.
  46  *
  47  * Permission to use, copy, modify, distribute and sell this software
  48  * and its documentation for any purpose is hereby granted without fee,
  49  * provided that the above copyright notice appear in all copies and
  50  * that both that copyright notice and this permission notice appear
  51  * in supporting documentation.  Silicon Graphics makes no
  52  * representations about the suitability of this software for any
  53  * purpose.  It is provided "as is" without express or implied warranty.
  54  */
  55
  56 /** @file stl_heap.h
  57  *  This is an internal header file, included by other library headers.
  58  *  You should not attempt to use it directly.
  59  */
  60
  61 #ifndef _STL_HEAP_H
  62 #define _STL_HEAP_H 1
  63
  64 #include <debug/debug.h>
  65 #include <bits/move.h>
  66
  67 _GLIBCXX_BEGIN_NAMESPACE(std)
  68
  69   /**
  70    * @defgroup heap_algorithms Heap Algorithms
  71    * @ingroup sorting_algorithms
  72    */
  73
  74   template<typename _RandomAccessIterator, typename _Distance>
  75     _Distance
  76     __is_heap_until(_RandomAccessIterator __first, _Distance __n)
  77     {
  78       _Distance __parent = 0;
  79       for (_Distance __child = 1; __child < __n; ++__child)
  80         {
  81           if (__first[__parent] < __first[__child])
  82             return __child;
  83           if ((__child & 1) == 0)
  84             ++__parent;
  85         }
  86       return __n;
  87     }
  88
  89   template<typename _RandomAccessIterator, typename _Distance,
  90            typename _Compare>
  91     _Distance
  92     __is_heap_until(_RandomAccessIterator __first, _Distance __n,
  93                     _Compare __comp)
  94     {
  95       _Distance __parent = 0;
  96       for (_Distance __child = 1; __child < __n; ++__child)
  97         {
  98           if (__comp(__first[__parent], __first[__child]))
  99             return __child;
 100           if ((__child & 1) == 0)
 101             ++__parent;
 102         }
 103       return __n;
 104     }
 105
 106   // __is_heap, a predicate testing whether or not a range is a heap.
 107   // This function is an extension, not part of the C++ standard.
 108   template<typename _RandomAccessIterator, typename _Distance>
 109     inline bool
 110     __is_heap(_RandomAccessIterator __first, _Distance __n)
 111     { return std::__is_heap_until(__first, __n) == __n; }
 112
 113   template<typename _RandomAccessIterator, typename _Compare,
 114            typename _Distance>
 115     inline bool
 116     __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
 117     { return std::__is_heap_until(__first, __n, __comp) == __n; }
 118
 119   template<typename _RandomAccessIterator>
 120     inline bool
 121     __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 122     { return std::__is_heap(__first, std::distance(__first, __last)); }
 123
 124   template<typename _RandomAccessIterator, typename _Compare>
 125     inline bool
 126     __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 127               _Compare __comp)
 128     { return std::__is_heap(__first, __comp, std::distance(__first, __last)); }
 129
 130   // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
 131   // + is_heap and is_heap_until in C++0x.
 132
 133   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
 134     void
 135     __push_heap(_RandomAccessIterator __first,
 136                 _Distance __holeIndex, _Distance __topIndex, _Tp __value)
 137     {
 138       _Distance __parent = (__holeIndex - 1) / 2;
 139       while (__holeIndex > __topIndex && *(__first + __parent) < __value)
 140         {
 141           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
 142           __holeIndex = __parent;
 143           __parent = (__holeIndex - 1) / 2;
 144         }
 145       *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
 146     }
 147
 148   /**
 149    *  @brief  Push an element onto a heap.
 150    *  @param  first  Start of heap.
 151    *  @param  last   End of heap + element.
 152    *  @ingroup heap_algorithms
 153    *
 154    *  This operation pushes the element at last-1 onto the valid heap over the
 155    *  range [first,last-1).  After completion, [first,last) is a valid heap.
 156   */
 157   template<typename _RandomAccessIterator>
 158     inline void
 159     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 160     {
 161       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 162           _ValueType;
 163       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 164           _DistanceType;
 165
 166       // concept requirements
 167       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 168             _RandomAccessIterator>)
 169       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
 170       __glibcxx_requires_valid_range(__first, __last);
 171       __glibcxx_requires_heap(__first, __last - 1);
 172
 173       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
 174       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
 175                        _DistanceType(0), _GLIBCXX_MOVE(__value));
 176     }
 177
 178   template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
 179            typename _Compare>
 180     void
 181     __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 182                 _Distance __topIndex, _Tp __value, _Compare __comp)
 183     {
 184       _Distance __parent = (__holeIndex - 1) / 2;
 185       while (__holeIndex > __topIndex
 186              && __comp(*(__first + __parent), __value))
 187         {
 188           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
 189           __holeIndex = __parent;
 190           __parent = (__holeIndex - 1) / 2;
 191         }
 192       *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
 193     }
 194
 195   /**
 196    *  @brief  Push an element onto a heap using comparison functor.
 197    *  @param  first  Start of heap.
 198    *  @param  last   End of heap + element.
 199    *  @param  comp   Comparison functor.
 200    *  @ingroup heap_algorithms
 201    *
 202    *  This operation pushes the element at last-1 onto the valid heap over the
 203    *  range [first,last-1).  After completion, [first,last) is a valid heap.
 204    *  Compare operations are performed using comp.
 205   */
 206   template<typename _RandomAccessIterator, typename _Compare>
 207     inline void
 208     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 209               _Compare __comp)
 210     {
 211       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 212           _ValueType;
 213       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 214           _DistanceType;
 215
 216       // concept requirements
 217       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 218             _RandomAccessIterator>)
 219       __glibcxx_requires_valid_range(__first, __last);
 220       __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
 221
 222       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
 223       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
 224                        _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
 225     }
 226
 227   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
 228     void
 229     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 230                   _Distance __len, _Tp __value)
 231     {
 232       const _Distance __topIndex = __holeIndex;
 233       _Distance __secondChild = __holeIndex;
 234       while (__secondChild < (__len - 1) / 2)
 235         {
 236           __secondChild = 2 * (__secondChild + 1);
 237           if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
 238             __secondChild--;
 239           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
 240           __holeIndex = __secondChild;
 241         }
 242       if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
 243         {
 244           __secondChild = 2 * (__secondChild + 1);
 245           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
 246                                                      + (__secondChild - 1)));
 247           __holeIndex = __secondChild - 1;
 248         }
 249       std::__push_heap(__first, __holeIndex, __topIndex,
 250                        _GLIBCXX_MOVE(__value));
 251     }
 252
 253   template<typename _RandomAccessIterator>
 254     inline void
 255     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 256                _RandomAccessIterator __result)
 257     {
 258       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 259         _ValueType;
 260       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 261         _DistanceType;
 262
 263       _ValueType __value = _GLIBCXX_MOVE(*__result);
 264       *__result = _GLIBCXX_MOVE(*__first);
 265       std::__adjust_heap(__first, _DistanceType(0),
 266                          _DistanceType(__last - __first),
 267                          _GLIBCXX_MOVE(__value));
 268     }
 269
 270   /**
 271    *  @brief  Pop an element off a heap.
 272    *  @param  first  Start of heap.
 273    *  @param  last   End of heap.
 274    *  @ingroup heap_algorithms
 275    *
 276    *  This operation pops the top of the heap.  The elements first and last-1
 277    *  are swapped and [first,last-1) is made into a 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 and last-1
 350    *  are swapped and [first,last-1) is made into a heap.  Comparisons are
 351    *  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
 582
 583 #endif /* _STL_HEAP_H */