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

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