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