l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.6/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 over the
 152    *  range [first,last-1).  After completion, [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 heap over the
 200    *  range [first,last-1).  After completion, [first,last) is a valid heap.
 201    *  Compare operations are performed using comp.
 202   */
 203   template<typename _RandomAccessIterator, typename _Compare>
 204     inline void
 205     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 206               _Compare __comp)
 207     {
 208       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 209           _ValueType;
 210       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 211           _DistanceType;
 212
 213       // concept requirements
 214       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 215             _RandomAccessIterator>)
 216       __glibcxx_requires_valid_range(__first, __last);
 217       __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
 218
 219       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
 220       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
 221                        _DistanceType(0), _GLIBCXX_MOVE(__value), __comp);
 222     }
 223
 224   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
 225     void
 226     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 227                   _Distance __len, _Tp __value)
 228     {
 229       const _Distance __topIndex = __holeIndex;
 230       _Distance __secondChild = __holeIndex;
 231       while (__secondChild < (__len - 1) / 2)
 232         {
 233           __secondChild = 2 * (__secondChild + 1);
 234           if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
 235             __secondChild--;
 236           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
 237           __holeIndex = __secondChild;
 238         }
 239       if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
 240         {
 241           __secondChild = 2 * (__secondChild + 1);
 242           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
 243                                                      + (__secondChild - 1)));
 244           __holeIndex = __secondChild - 1;
 245         }
 246       std::__push_heap(__first, __holeIndex, __topIndex,
 247                        _GLIBCXX_MOVE(__value));
 248     }
 249
 250   template<typename _RandomAccessIterator>
 251     inline void
 252     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 253                _RandomAccessIterator __result)
 254     {
 255       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 256         _ValueType;
 257       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 258         _DistanceType;
 259
 260       _ValueType __value = _GLIBCXX_MOVE(*__result);
 261       *__result = _GLIBCXX_MOVE(*__first);
 262       std::__adjust_heap(__first, _DistanceType(0),
 263                          _DistanceType(__last - __first),
 264                          _GLIBCXX_MOVE(__value));
 265     }
 266
 267   /**
 268    *  @brief  Pop an element off a heap.
 269    *  @param  first  Start of heap.
 270    *  @param  last   End of heap.
 271    *  @ingroup heap_algorithms
 272    *
 273    *  This operation pops the top of the heap.  The elements first and last-1
 274    *  are swapped and [first,last-1) is made into a heap.
 275   */
 276   template<typename _RandomAccessIterator>
 277     inline void
 278     pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 279     {
 280       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 281         _ValueType;
 282
 283       // concept requirements
 284       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 285             _RandomAccessIterator>)
 286       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
 287       __glibcxx_requires_valid_range(__first, __last);
 288       __glibcxx_requires_heap(__first, __last);
 289
 290       --__last;
 291       std::__pop_heap(__first, __last, __last);
 292     }
 293
 294   template<typename _RandomAccessIterator, typename _Distance,
 295            typename _Tp, typename _Compare>
 296     void
 297     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 298                   _Distance __len, _Tp __value, _Compare __comp)
 299     {
 300       const _Distance __topIndex = __holeIndex;
 301       _Distance __secondChild = __holeIndex;
 302       while (__secondChild < (__len - 1) / 2)
 303         {
 304           __secondChild = 2 * (__secondChild + 1);
 305           if (__comp(*(__first + __secondChild),
 306                      *(__first + (__secondChild - 1))))
 307             __secondChild--;
 308           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
 309           __holeIndex = __secondChild;
 310         }
 311       if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
 312         {
 313           __secondChild = 2 * (__secondChild + 1);
 314           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
 315                                                      + (__secondChild - 1)));
 316           __holeIndex = __secondChild - 1;
 317         }
 318       std::__push_heap(__first, __holeIndex, __topIndex,
 319                        _GLIBCXX_MOVE(__value), __comp);
 320     }
 321
 322   template<typename _RandomAccessIterator, typename _Compare>
 323     inline void
 324     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 325                _RandomAccessIterator __result, _Compare __comp)
 326     {
 327       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 328         _ValueType;
 329       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 330         _DistanceType;
 331
 332       _ValueType __value = _GLIBCXX_MOVE(*__result);
 333       *__result = _GLIBCXX_MOVE(*__first);
 334       std::__adjust_heap(__first, _DistanceType(0),
 335                          _DistanceType(__last - __first),
 336                          _GLIBCXX_MOVE(__value), __comp);
 337     }
 338
 339   /**
 340    *  @brief  Pop an element off a heap using comparison functor.
 341    *  @param  first  Start of heap.
 342    *  @param  last   End of heap.
 343    *  @param  comp   Comparison functor to use.
 344    *  @ingroup heap_algorithms
 345    *
 346    *  This operation pops the top of the heap.  The elements first and last-1
 347    *  are swapped and [first,last-1) is made into a heap.  Comparisons are
 348    *  made using comp.
 349   */
 350   template<typename _RandomAccessIterator, typename _Compare>
 351     inline void
 352     pop_heap(_RandomAccessIterator __first,
 353              _RandomAccessIterator __last, _Compare __comp)
 354     {
 355       // concept requirements
 356       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 357             _RandomAccessIterator>)
 358       __glibcxx_requires_valid_range(__first, __last);
 359       __glibcxx_requires_heap_pred(__first, __last, __comp);
 360
 361       --__last;
 362       std::__pop_heap(__first, __last, __last, __comp);
 363     }
 364
 365   /**
 366    *  @brief  Construct a heap over a range.
 367    *  @param  first  Start of heap.
 368    *  @param  last   End of heap.
 369    *  @ingroup heap_algorithms
 370    *
 371    *  This operation makes the elements in [first,last) into a heap.
 372   */
 373   template<typename _RandomAccessIterator>
 374     void
 375     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 376     {
 377       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 378           _ValueType;
 379       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 380           _DistanceType;
 381
 382       // concept requirements
 383       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 384             _RandomAccessIterator>)
 385       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
 386       __glibcxx_requires_valid_range(__first, __last);
 387
 388       if (__last - __first < 2)
 389         return;
 390
 391       const _DistanceType __len = __last - __first;
 392       _DistanceType __parent = (__len - 2) / 2;
 393       while (true)
 394         {
 395           _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
 396           std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value));
 397           if (__parent == 0)
 398             return;
 399           __parent--;
 400         }
 401     }
 402
 403   /**
 404    *  @brief  Construct a heap over a range using comparison functor.
 405    *  @param  first  Start of heap.
 406    *  @param  last   End of heap.
 407    *  @param  comp   Comparison functor to use.
 408    *  @ingroup heap_algorithms
 409    *
 410    *  This operation makes the elements in [first,last) into a heap.
 411    *  Comparisons are made using comp.
 412   */
 413   template<typename _RandomAccessIterator, typename _Compare>
 414     void
 415     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 416               _Compare __comp)
 417     {
 418       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 419           _ValueType;
 420       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 421           _DistanceType;
 422
 423       // concept requirements
 424       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 425             _RandomAccessIterator>)
 426       __glibcxx_requires_valid_range(__first, __last);
 427
 428       if (__last - __first < 2)
 429         return;
 430
 431       const _DistanceType __len = __last - __first;
 432       _DistanceType __parent = (__len - 2) / 2;
 433       while (true)
 434         {
 435           _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
 436           std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
 437                              __comp);
 438           if (__parent == 0)
 439             return;
 440           __parent--;
 441         }
 442     }
 443
 444   /**
 445    *  @brief  Sort a heap.
 446    *  @param  first  Start of heap.
 447    *  @param  last   End of heap.
 448    *  @ingroup heap_algorithms
 449    *
 450    *  This operation sorts the valid heap in the range [first,last).
 451   */
 452   template<typename _RandomAccessIterator>
 453     void
 454     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 455     {
 456       // concept requirements
 457       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 458             _RandomAccessIterator>)
 459       __glibcxx_function_requires(_LessThanComparableConcept<
 460             typename iterator_traits<_RandomAccessIterator>::value_type>)
 461       __glibcxx_requires_valid_range(__first, __last);
 462       __glibcxx_requires_heap(__first, __last);
 463
 464       while (__last - __first > 1)
 465         {
 466           --__last;
 467           std::__pop_heap(__first, __last, __last);
 468         }
 469     }
 470
 471   /**
 472    *  @brief  Sort a heap using comparison functor.
 473    *  @param  first  Start of heap.
 474    *  @param  last   End of heap.
 475    *  @param  comp   Comparison functor to use.
 476    *  @ingroup heap_algorithms
 477    *
 478    *  This operation sorts the valid heap in the range [first,last).
 479    *  Comparisons are made using comp.
 480   */
 481   template<typename _RandomAccessIterator, typename _Compare>
 482     void
 483     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 484               _Compare __comp)
 485     {
 486       // concept requirements
 487       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 488             _RandomAccessIterator>)
 489       __glibcxx_requires_valid_range(__first, __last);
 490       __glibcxx_requires_heap_pred(__first, __last, __comp);
 491
 492       while (__last - __first > 1)
 493         {
 494           --__last;
 495           std::__pop_heap(__first, __last, __last, __comp);
 496         }
 497     }
 498
 499 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 500   /**
 501    *  @brief  Search the end of a heap.
 502    *  @param  first  Start of range.
 503    *  @param  last   End of range.
 504    *  @return  An iterator pointing to the first element not in the heap.
 505    *  @ingroup heap_algorithms
 506    *
 507    *  This operation returns the last iterator i in [first, last) for which
 508    *  the range [first, i) is a heap.
 509   */
 510   template<typename _RandomAccessIterator>
 511     inline _RandomAccessIterator
 512     is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
 513     {
 514       // concept requirements
 515       __glibcxx_function_requires(_RandomAccessIteratorConcept<
 516             _RandomAccessIterator>)
 517       __glibcxx_function_requires(_LessThanComparableConcept<
 518             typename iterator_traits<_RandomAccessIterator>::value_type>)
 519       __glibcxx_requires_valid_range(__first, __last);
 520
 521       return __first + std::__is_heap_until(__first, std::distance(__first,
 522                                                                    __last));
 523     }
 524
 525   /**
 526    *  @brief  Search the end of a heap using comparison functor.
 527    *  @param  first  Start of range.
 528    *  @param  last   End of range.
 529    *  @param  comp   Comparison functor to use.
 530    *  @return  An iterator pointing to the first element not in the heap.
 531    *  @ingroup heap_algorithms
 532    *
 533    *  This operation returns the last iterator i in [first, last) for which
 534    *  the range [first, i) is a heap.  Comparisons are made using comp.
 535   */
 536   template<typename _RandomAccessIterator, typename _Compare>
 537     inline _RandomAccessIterator
 538     is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
 539                   _Compare __comp)
 540     {
 541       // concept requirements
 542       __glibcxx_function_requires(_RandomAccessIteratorConcept<
 543             _RandomAccessIterator>)
 544       __glibcxx_requires_valid_range(__first, __last);
 545
 546       return __first + std::__is_heap_until(__first, std::distance(__first,
 547                                                                    __last),
 548                                             __comp);
 549     }
 550
 551   /**
 552    *  @brief  Determines whether a range is a heap.
 553    *  @param  first  Start of range.
 554    *  @param  last   End of range.
 555    *  @return  True if range is a heap, false otherwise.
 556    *  @ingroup heap_algorithms
 557   */
 558   template<typename _RandomAccessIterator>
 559     inline bool
 560     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 561     { return std::is_heap_until(__first, __last) == __last; }
 562
 563   /**
 564    *  @brief  Determines whether a range is a heap using comparison functor.
 565    *  @param  first  Start of range.
 566    *  @param  last   End of range.
 567    *  @param  comp   Comparison functor to use.
 568    *  @return  True if range is a heap, false otherwise.
 569    *  @ingroup heap_algorithms
 570   */
 571   template<typename _RandomAccessIterator, typename _Compare>
 572     inline bool
 573     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 574             _Compare __comp)
 575     { return std::is_heap_until(__first, __last, __comp) == __last; }
 576 #endif
 577
 578 _GLIBCXX_END_NAMESPACE_VERSION
 579 } // namespace
 580
 581 #endif /* _STL_HEAP_H */