l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.8/include/bits/stl_heap.h

   1 // Heap implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001-2013 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
  61 namespace std _GLIBCXX_VISIBILITY(default)
  62 {
  63 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  64
  65   /**
  66    * @defgroup heap_algorithms Heap
  67    * @ingroup sorting_algorithms
  68    */
  69
  70   template<typename _RandomAccessIterator, typename _Distance>
  71     _Distance
  72     __is_heap_until(_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 __child;
  79           if ((__child & 1) == 0)
  80             ++__parent;
  81         }
  82       return __n;
  83     }
  84
  85   template<typename _RandomAccessIterator, typename _Distance,
  86            typename _Compare>
  87     _Distance
  88     __is_heap_until(_RandomAccessIterator __first, _Distance __n,
  89                     _Compare __comp)
  90     {
  91       _Distance __parent = 0;
  92       for (_Distance __child = 1; __child < __n; ++__child)
  93         {
  94           if (__comp(__first[__parent], __first[__child]))
  95             return __child;
  96           if ((__child & 1) == 0)
  97             ++__parent;
  98         }
  99       return __n;
 100     }
 101
 102   // __is_heap, a predicate testing whether or not a range is a heap.
 103   // This function is an extension, not part of the C++ standard.
 104   template<typename _RandomAccessIterator, typename _Distance>
 105     inline bool
 106     __is_heap(_RandomAccessIterator __first, _Distance __n)
 107     { return std::__is_heap_until(__first, __n) == __n; }
 108
 109   template<typename _RandomAccessIterator, typename _Compare,
 110            typename _Distance>
 111     inline bool
 112     __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
 113     { return std::__is_heap_until(__first, __n, __comp) == __n; }
 114
 115   template<typename _RandomAccessIterator>
 116     inline bool
 117     __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 118     { return std::__is_heap(__first, std::distance(__first, __last)); }
 119
 120   template<typename _RandomAccessIterator, typename _Compare>
 121     inline bool
 122     __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 123               _Compare __comp)
 124     { return std::__is_heap(__first, __comp, std::distance(__first, __last)); }
 125
 126   // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap,
 127   // + is_heap and is_heap_until in C++0x.
 128
 129   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
 130     void
 131     __push_heap(_RandomAccessIterator __first,
 132                 _Distance __holeIndex, _Distance __topIndex, _Tp __value)
 133     {
 134       _Distance __parent = (__holeIndex - 1) / 2;
 135       while (__holeIndex > __topIndex && *(__first + __parent) < __value)
 136         {
 137           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
 138           __holeIndex = __parent;
 139           __parent = (__holeIndex - 1) / 2;
 140         }
 141       *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
 142     }
 143
 144   /**
 145    *  @brief  Push an element onto a heap.
 146    *  @param  __first  Start of heap.
 147    *  @param  __last   End of heap + element.
 148    *  @ingroup heap_algorithms
 149    *
 150    *  This operation pushes the element at last-1 onto the valid heap
 151    *  over the range [__first,__last-1).  After completion,
 152    *  [__first,__last) is a valid heap.
 153   */
 154   template<typename _RandomAccessIterator>
 155     inline void
 156     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 157     {
 158       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 159           _ValueType;
 160       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 161           _DistanceType;
 162
 163       // concept requirements
 164       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 165             _RandomAccessIterator>)
 166       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
 167       __glibcxx_requires_valid_range(__first, __last);
 168       __glibcxx_requires_heap(__first, __last - 1);
 169
 170       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
 171       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
 172                        _DistanceType(0), _GLIBCXX_MOVE(__value));
 173     }
 174
 175   template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
 176            typename _Compare>
 177     void
 178     __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 179                 _Distance __topIndex, _Tp __value, _Compare __comp)
 180     {
 181       _Distance __parent = (__holeIndex - 1) / 2;
 182       while (__holeIndex > __topIndex
 183              && __comp(*(__first + __parent), __value))
 184         {
 185           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent));
 186           __holeIndex = __parent;
 187           __parent = (__holeIndex - 1) / 2;
 188         }
 189       *(__first + __holeIndex) = _GLIBCXX_MOVE(__value);
 190     }
 191
 192   /**
 193    *  @brief  Push an element onto a heap using comparison functor.
 194    *  @param  __first  Start of heap.
 195    *  @param  __last   End of heap + element.
 196    *  @param  __comp   Comparison functor.
 197    *  @ingroup heap_algorithms
 198    *
 199    *  This operation pushes the element at __last-1 onto the valid
 200    *  heap over the range [__first,__last-1).  After completion,
 201    *  [__first,__last) is a valid heap.  Compare operations are
 202    *  performed using comp.
 203   */
 204   template<typename _RandomAccessIterator, typename _Compare>
 205     inline void
 206     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 207               _Compare __comp)
 208     {
 209       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 210           _ValueType;
 211       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 212           _DistanceType;
 213
 214       // concept requirements
 215       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 216             _RandomAccessIterator>)
 217       __glibcxx_requires_valid_range(__first, __last);
 218       __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
 219
 220       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
 221       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
 222                        _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
 223     }
 224
 225   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
 226     void
 227     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 228                   _Distance __len, _Tp __value)
 229     {
 230       const _Distance __topIndex = __holeIndex;
 231       _Distance __secondChild = __holeIndex;
 232       while (__secondChild < (__len - 1) / 2)
 233         {
 234           __secondChild = 2 * (__secondChild + 1);
 235           if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
 236             __secondChild--;
 237           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
 238           __holeIndex = __secondChild;
 239         }
 240       if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
 241         {
 242           __secondChild = 2 * (__secondChild + 1);
 243           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
 244                                                      + (__secondChild - 1)));
 245           __holeIndex = __secondChild - 1;
 246         }
 247       std::__push_heap(__first, __holeIndex, __topIndex,
 248                        _GLIBCXX_MOVE(__value));
 249     }
 250
 251   template<typename _RandomAccessIterator>
 252     inline void
 253     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 254                _RandomAccessIterator __result)
 255     {
 256       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 257         _ValueType;
 258       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 259         _DistanceType;
 260
 261       _ValueType __value = _GLIBCXX_MOVE(*__result);
 262       *__result = _GLIBCXX_MOVE(*__first);
 263       std::__adjust_heap(__first, _DistanceType(0),
 264                          _DistanceType(__last - __first),
 265                          _GLIBCXX_MOVE(__value));
 266     }
 267
 268   /**
 269    *  @brief  Pop an element off a heap.
 270    *  @param  __first  Start of heap.
 271    *  @param  __last   End of heap.
 272    *  @pre    [__first, __last) is a valid, non-empty range.
 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_non_empty_range(__first, __last);
 291       __glibcxx_requires_valid_range(__first, __last);
 292       __glibcxx_requires_heap(__first, __last);
 293
 294       if (__last - __first > 1)
 295         {
 296           --__last;
 297           std::__pop_heap(__first, __last, __last);
 298         }
 299     }
 300
 301   template<typename _RandomAccessIterator, typename _Distance,
 302            typename _Tp, typename _Compare>
 303     void
 304     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 305                   _Distance __len, _Tp __value, _Compare __comp)
 306     {
 307       const _Distance __topIndex = __holeIndex;
 308       _Distance __secondChild = __holeIndex;
 309       while (__secondChild < (__len - 1) / 2)
 310         {
 311           __secondChild = 2 * (__secondChild + 1);
 312           if (__comp(*(__first + __secondChild),
 313                      *(__first + (__secondChild - 1))))
 314             __secondChild--;
 315           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
 316           __holeIndex = __secondChild;
 317         }
 318       if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
 319         {
 320           __secondChild = 2 * (__secondChild + 1);
 321           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
 322                                                      + (__secondChild - 1)));
 323           __holeIndex = __secondChild - 1;
 324         }
 325       std::__push_heap(__first, __holeIndex, __topIndex,
 326                        _GLIBCXX_MOVE(__value), __comp);
 327     }
 328
 329   template<typename _RandomAccessIterator, typename _Compare>
 330     inline void
 331     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 332                _RandomAccessIterator __result, _Compare __comp)
 333     {
 334       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 335         _ValueType;
 336       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 337         _DistanceType;
 338
 339       _ValueType __value = _GLIBCXX_MOVE(*__result);
 340       *__result = _GLIBCXX_MOVE(*__first);
 341       std::__adjust_heap(__first, _DistanceType(0),
 342                          _DistanceType(__last - __first),
 343                          _GLIBCXX_MOVE(__value), __comp);
 344     }
 345
 346   /**
 347    *  @brief  Pop an element off a heap using comparison functor.
 348    *  @param  __first  Start of heap.
 349    *  @param  __last   End of heap.
 350    *  @param  __comp   Comparison functor to use.
 351    *  @ingroup heap_algorithms
 352    *
 353    *  This operation pops the top of the heap.  The elements __first
 354    *  and __last-1 are swapped and [__first,__last-1) is made into a
 355    *  heap.  Comparisons are made using comp.
 356   */
 357   template<typename _RandomAccessIterator, typename _Compare>
 358     inline void
 359     pop_heap(_RandomAccessIterator __first,
 360              _RandomAccessIterator __last, _Compare __comp)
 361     {
 362       // concept requirements
 363       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 364             _RandomAccessIterator>)
 365       __glibcxx_requires_valid_range(__first, __last);
 366       __glibcxx_requires_non_empty_range(__first, __last);
 367       __glibcxx_requires_heap_pred(__first, __last, __comp);
 368
 369       if (__last - __first > 1)
 370         {
 371           --__last;
 372           std::__pop_heap(__first, __last, __last, __comp);
 373         }
 374     }
 375
 376   /**
 377    *  @brief  Construct a heap over a range.
 378    *  @param  __first  Start of heap.
 379    *  @param  __last   End of heap.
 380    *  @ingroup heap_algorithms
 381    *
 382    *  This operation makes the elements in [__first,__last) into a heap.
 383   */
 384   template<typename _RandomAccessIterator>
 385     void
 386     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 387     {
 388       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 389           _ValueType;
 390       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 391           _DistanceType;
 392
 393       // concept requirements
 394       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 395             _RandomAccessIterator>)
 396       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
 397       __glibcxx_requires_valid_range(__first, __last);
 398
 399       if (__last - __first < 2)
 400         return;
 401
 402       const _DistanceType __len = __last - __first;
 403       _DistanceType __parent = (__len - 2) / 2;
 404       while (true)
 405         {
 406           _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
 407           std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value));
 408           if (__parent == 0)
 409             return;
 410           __parent--;
 411         }
 412     }
 413
 414   /**
 415    *  @brief  Construct a heap over a range using comparison functor.
 416    *  @param  __first  Start of heap.
 417    *  @param  __last   End of heap.
 418    *  @param  __comp   Comparison functor to use.
 419    *  @ingroup heap_algorithms
 420    *
 421    *  This operation makes the elements in [__first,__last) into a heap.
 422    *  Comparisons are made using __comp.
 423   */
 424   template<typename _RandomAccessIterator, typename _Compare>
 425     void
 426     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 427               _Compare __comp)
 428     {
 429       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 430           _ValueType;
 431       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 432           _DistanceType;
 433
 434       // concept requirements
 435       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 436             _RandomAccessIterator>)
 437       __glibcxx_requires_valid_range(__first, __last);
 438
 439       if (__last - __first < 2)
 440         return;
 441
 442       const _DistanceType __len = __last - __first;
 443       _DistanceType __parent = (__len - 2) / 2;
 444       while (true)
 445         {
 446           _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
 447           std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
 448                              __comp);
 449           if (__parent == 0)
 450             return;
 451           __parent--;
 452         }
 453     }
 454
 455   /**
 456    *  @brief  Sort a heap.
 457    *  @param  __first  Start of heap.
 458    *  @param  __last   End of heap.
 459    *  @ingroup heap_algorithms
 460    *
 461    *  This operation sorts the valid heap in the range [__first,__last).
 462   */
 463   template<typename _RandomAccessIterator>
 464     void
 465     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 466     {
 467       // concept requirements
 468       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 469             _RandomAccessIterator>)
 470       __glibcxx_function_requires(_LessThanComparableConcept<
 471             typename iterator_traits<_RandomAccessIterator>::value_type>)
 472       __glibcxx_requires_valid_range(__first, __last);
 473       __glibcxx_requires_heap(__first, __last);
 474
 475       while (__last - __first > 1)
 476         {
 477           --__last;
 478           std::__pop_heap(__first, __last, __last);
 479         }
 480     }
 481
 482   /**
 483    *  @brief  Sort a heap using comparison functor.
 484    *  @param  __first  Start of heap.
 485    *  @param  __last   End of heap.
 486    *  @param  __comp   Comparison functor to use.
 487    *  @ingroup heap_algorithms
 488    *
 489    *  This operation sorts the valid heap in the range [__first,__last).
 490    *  Comparisons are made using __comp.
 491   */
 492   template<typename _RandomAccessIterator, typename _Compare>
 493     void
 494     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 495               _Compare __comp)
 496     {
 497       // concept requirements
 498       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 499             _RandomAccessIterator>)
 500       __glibcxx_requires_valid_range(__first, __last);
 501       __glibcxx_requires_heap_pred(__first, __last, __comp);
 502
 503       while (__last - __first > 1)
 504         {
 505           --__last;
 506           std::__pop_heap(__first, __last, __last, __comp);
 507         }
 508     }
 509
 510 #if __cplusplus >= 201103L
 511   /**
 512    *  @brief  Search the end of a heap.
 513    *  @param  __first  Start of range.
 514    *  @param  __last   End of range.
 515    *  @return  An iterator pointing to the first element not in the heap.
 516    *  @ingroup heap_algorithms
 517    *
 518    *  This operation returns the last iterator i in [__first, __last) for which
 519    *  the range [__first, i) is a heap.
 520   */
 521   template<typename _RandomAccessIterator>
 522     inline _RandomAccessIterator
 523     is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
 524     {
 525       // concept requirements
 526       __glibcxx_function_requires(_RandomAccessIteratorConcept<
 527             _RandomAccessIterator>)
 528       __glibcxx_function_requires(_LessThanComparableConcept<
 529             typename iterator_traits<_RandomAccessIterator>::value_type>)
 530       __glibcxx_requires_valid_range(__first, __last);
 531
 532       return __first + std::__is_heap_until(__first, std::distance(__first,
 533                                                                    __last));
 534     }
 535
 536   /**
 537    *  @brief  Search the end of a heap using comparison functor.
 538    *  @param  __first  Start of range.
 539    *  @param  __last   End of range.
 540    *  @param  __comp   Comparison functor to use.
 541    *  @return  An iterator pointing to the first element not in the heap.
 542    *  @ingroup heap_algorithms
 543    *
 544    *  This operation returns the last iterator i in [__first, __last) for which
 545    *  the range [__first, i) is a heap.  Comparisons are made using __comp.
 546   */
 547   template<typename _RandomAccessIterator, typename _Compare>
 548     inline _RandomAccessIterator
 549     is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
 550                   _Compare __comp)
 551     {
 552       // concept requirements
 553       __glibcxx_function_requires(_RandomAccessIteratorConcept<
 554             _RandomAccessIterator>)
 555       __glibcxx_requires_valid_range(__first, __last);
 556
 557       return __first + std::__is_heap_until(__first, std::distance(__first,
 558                                                                    __last),
 559                                             __comp);
 560     }
 561
 562   /**
 563    *  @brief  Determines whether a range is a heap.
 564    *  @param  __first  Start of range.
 565    *  @param  __last   End of range.
 566    *  @return  True if range is a heap, false otherwise.
 567    *  @ingroup heap_algorithms
 568   */
 569   template<typename _RandomAccessIterator>
 570     inline bool
 571     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 572     { return std::is_heap_until(__first, __last) == __last; }
 573
 574   /**
 575    *  @brief  Determines whether a range is a heap using comparison functor.
 576    *  @param  __first  Start of range.
 577    *  @param  __last   End of range.
 578    *  @param  __comp   Comparison functor to use.
 579    *  @return  True if range is a heap, false otherwise.
 580    *  @ingroup heap_algorithms
 581   */
 582   template<typename _RandomAccessIterator, typename _Compare>
 583     inline bool
 584     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 585             _Compare __comp)
 586     { return std::is_heap_until(__first, __last, __comp) == __last; }
 587 #endif
 588
 589 _GLIBCXX_END_NAMESPACE_VERSION
 590 } // namespace
 591
 592 #endif /* _STL_HEAP_H */