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

   1 // Heap implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 2, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // You should have received a copy of the GNU General Public License along
  18 // with this library; see the file COPYING.  If not, write to the Free
  19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  20 // USA.
  21
  22 // As a special exception, you may use this file as part of a free software
  23 // library without restriction.  Specifically, if other files instantiate
  24 // templates or use macros or inline functions from this file, or you compile
  25 // this file and link it with other files to produce an executable, this
  26 // file does not by itself cause the resulting executable to be covered by
  27 // the GNU General Public License.  This exception does not however
  28 // invalidate any other reasons why the executable file might be covered by
  29 // the GNU General Public License.
  30
  31 /*
  32  *
  33  * Copyright (c) 1994
  34  * Hewlett-Packard Company
  35  *
  36  * Permission to use, copy, modify, distribute and sell this software
  37  * and its documentation for any purpose is hereby granted without fee,
  38  * provided that the above copyright notice appear in all copies and
  39  * that both that copyright notice and this permission notice appear
  40  * in supporting documentation.  Hewlett-Packard Company makes no
  41  * representations about the suitability of this software for any
  42  * purpose.  It is provided "as is" without express or implied warranty.
  43  *
  44  * Copyright (c) 1997
  45  * Silicon Graphics Computer Systems, Inc.
  46  *
  47  * Permission to use, copy, modify, distribute and sell this software
  48  * and its documentation for any purpose is hereby granted without fee,
  49  * provided that the above copyright notice appear in all copies and
  50  * that both that copyright notice and this permission notice appear
  51  * in supporting documentation.  Silicon Graphics makes no
  52  * representations about the suitability of this software for any
  53  * purpose.  It is provided "as is" without express or implied warranty.
  54  */
  55
  56 /** @file stl_heap.h
  57  *  This is an internal header file, included by other library headers.
  58  *  You should not attempt to use it directly.
  59  */
  60
  61 #ifndef _STL_HEAP_H
  62 #define _STL_HEAP_H 1
  63
  64 #include <debug/debug.h>
  65 #include <bits/stl_move.h>
  66
  67 _GLIBCXX_BEGIN_NAMESPACE(std)
  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
 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
 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
 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       std::__pop_heap(__first, __last - 1, __last - 1);
 289     }
 290
 291   template<typename _RandomAccessIterator, typename _Distance,
 292            typename _Tp, typename _Compare>
 293     void
 294     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 295                   _Distance __len, _Tp __value, _Compare __comp)
 296     {
 297       const _Distance __topIndex = __holeIndex;
 298       _Distance __secondChild = __holeIndex;
 299       while (__secondChild < (__len - 1) / 2)
 300         {
 301           __secondChild = 2 * (__secondChild + 1);
 302           if (__comp(*(__first + __secondChild),
 303                      *(__first + (__secondChild - 1))))
 304             __secondChild--;
 305           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild));
 306           __holeIndex = __secondChild;
 307         }
 308       if ((__len & 1) == 0 && __secondChild == (__len - 2) / 2)
 309         {
 310           __secondChild = 2 * (__secondChild + 1);
 311           *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first
 312                                                      + (__secondChild - 1)));
 313           __holeIndex = __secondChild - 1;
 314         }
 315       std::__push_heap(__first, __holeIndex, __topIndex,
 316                        _GLIBCXX_MOVE(__value), __comp);
 317     }
 318
 319   template<typename _RandomAccessIterator, typename _Compare>
 320     inline void
 321     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 322                _RandomAccessIterator __result, _Compare __comp)
 323     {
 324       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 325         _ValueType;
 326       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 327         _DistanceType;
 328
 329       _ValueType __value = _GLIBCXX_MOVE(*__result);
 330       *__result = _GLIBCXX_MOVE(*__first);
 331       std::__adjust_heap(__first, _DistanceType(0),
 332                          _DistanceType(__last - __first),
 333                          _GLIBCXX_MOVE(__value), __comp);
 334     }
 335
 336   /**
 337    *  @brief  Pop an element off a heap using comparison functor.
 338    *  @param  first  Start of heap.
 339    *  @param  last   End of heap.
 340    *  @param  comp   Comparison functor to use.
 341    *  @ingroup heap
 342    *
 343    *  This operation pops the top of the heap.  The elements first and last-1
 344    *  are swapped and [first,last-1) is made into a heap.  Comparisons are
 345    *  made using comp.
 346   */
 347   template<typename _RandomAccessIterator, typename _Compare>
 348     inline void
 349     pop_heap(_RandomAccessIterator __first,
 350              _RandomAccessIterator __last, _Compare __comp)
 351     {
 352       // concept requirements
 353       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 354             _RandomAccessIterator>)
 355       __glibcxx_requires_valid_range(__first, __last);
 356       __glibcxx_requires_heap_pred(__first, __last, __comp);
 357
 358       std::__pop_heap(__first, __last - 1, __last - 1, __comp);
 359     }
 360
 361   /**
 362    *  @brief  Construct a heap over a range.
 363    *  @param  first  Start of heap.
 364    *  @param  last   End of heap.
 365    *  @ingroup heap
 366    *
 367    *  This operation makes the elements in [first,last) into a heap.
 368   */
 369   template<typename _RandomAccessIterator>
 370     void
 371     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 372     {
 373       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 374           _ValueType;
 375       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 376           _DistanceType;
 377
 378       // concept requirements
 379       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 380             _RandomAccessIterator>)
 381       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
 382       __glibcxx_requires_valid_range(__first, __last);
 383
 384       if (__last - __first < 2)
 385         return;
 386
 387       const _DistanceType __len = __last - __first;
 388       _DistanceType __parent = (__len - 2) / 2;
 389       while (true)
 390         {
 391           _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
 392           std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value));
 393           if (__parent == 0)
 394             return;
 395           __parent--;
 396         }
 397     }
 398
 399   /**
 400    *  @brief  Construct a heap over a range using comparison functor.
 401    *  @param  first  Start of heap.
 402    *  @param  last   End of heap.
 403    *  @param  comp   Comparison functor to use.
 404    *  @ingroup heap
 405    *
 406    *  This operation makes the elements in [first,last) into a heap.
 407    *  Comparisons are made using comp.
 408   */
 409   template<typename _RandomAccessIterator, typename _Compare>
 410     void
 411     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 412               _Compare __comp)
 413     {
 414       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 415           _ValueType;
 416       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 417           _DistanceType;
 418
 419       // concept requirements
 420       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 421             _RandomAccessIterator>)
 422       __glibcxx_requires_valid_range(__first, __last);
 423
 424       if (__last - __first < 2)
 425         return;
 426
 427       const _DistanceType __len = __last - __first;
 428       _DistanceType __parent = (__len - 2) / 2;
 429       while (true)
 430         {
 431           _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
 432           std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
 433                              __comp);
 434           if (__parent == 0)
 435             return;
 436           __parent--;
 437         }
 438     }
 439
 440   /**
 441    *  @brief  Sort a heap.
 442    *  @param  first  Start of heap.
 443    *  @param  last   End of heap.
 444    *  @ingroup heap
 445    *
 446    *  This operation sorts the valid heap in the range [first,last).
 447   */
 448   template<typename _RandomAccessIterator>
 449     void
 450     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 451     {
 452       // concept requirements
 453       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 454             _RandomAccessIterator>)
 455       __glibcxx_function_requires(_LessThanComparableConcept<
 456             typename iterator_traits<_RandomAccessIterator>::value_type>)
 457       __glibcxx_requires_valid_range(__first, __last);
 458       __glibcxx_requires_heap(__first, __last);
 459
 460       while (__last - __first > 1)
 461         std::pop_heap(__first, _RandomAccessIterator(__last--));
 462     }
 463
 464   /**
 465    *  @brief  Sort a heap using comparison functor.
 466    *  @param  first  Start of heap.
 467    *  @param  last   End of heap.
 468    *  @param  comp   Comparison functor to use.
 469    *  @ingroup heap
 470    *
 471    *  This operation sorts the valid heap in the range [first,last).
 472    *  Comparisons are made using comp.
 473   */
 474   template<typename _RandomAccessIterator, typename _Compare>
 475     void
 476     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 477               _Compare __comp)
 478     {
 479       // concept requirements
 480       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 481             _RandomAccessIterator>)
 482       __glibcxx_requires_valid_range(__first, __last);
 483       __glibcxx_requires_heap_pred(__first, __last, __comp);
 484
 485       while (__last - __first > 1)
 486         std::pop_heap(__first, _RandomAccessIterator(__last--), __comp);
 487     }
 488
 489 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 490   /**
 491    *  @brief  Search the end of a heap.
 492    *  @param  first  Start of range.
 493    *  @param  last   End of range.
 494    *  @return  An iterator pointing to the first element not in the heap.
 495    *  @ingroup heap
 496    *
 497    *  This operation returns the last iterator i in [first, last) for which
 498    *  the range [first, i) is a heap.
 499   */
 500   template<typename _RandomAccessIterator>
 501     inline _RandomAccessIterator
 502     is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last)
 503     {
 504       // concept requirements
 505       __glibcxx_function_requires(_RandomAccessIteratorConcept<
 506             _RandomAccessIterator>)
 507       __glibcxx_function_requires(_LessThanComparableConcept<
 508             typename iterator_traits<_RandomAccessIterator>::value_type>)
 509       __glibcxx_requires_valid_range(__first, __last);
 510
 511       return __first + std::__is_heap_until(__first, std::distance(__first,
 512                                                                    __last));
 513     }
 514
 515   /**
 516    *  @brief  Search the end of a heap using comparison functor.
 517    *  @param  first  Start of range.
 518    *  @param  last   End of range.
 519    *  @param  comp   Comparison functor to use.
 520    *  @return  An iterator pointing to the first element not in the heap.
 521    *  @ingroup heap
 522    *
 523    *  This operation returns the last iterator i in [first, last) for which
 524    *  the range [first, i) is a heap.  Comparisons are made using comp.
 525   */
 526   template<typename _RandomAccessIterator, typename _Compare>
 527     inline _RandomAccessIterator
 528     is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last,
 529                   _Compare __comp)
 530     {
 531       // concept requirements
 532       __glibcxx_function_requires(_RandomAccessIteratorConcept<
 533             _RandomAccessIterator>)
 534       __glibcxx_requires_valid_range(__first, __last);
 535
 536       return __first + std::__is_heap_until(__first, std::distance(__first,
 537                                                                    __last),
 538                                             __comp);
 539     }
 540
 541   /**
 542    *  @brief  Determines whether a range is a heap.
 543    *  @param  first  Start of range.
 544    *  @param  last   End of range.
 545    *  @return  True if range is a heap, false otherwise.
 546    *  @ingroup heap
 547   */
 548   template<typename _RandomAccessIterator>
 549     inline bool
 550     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 551     { return std::is_heap_until(__first, __last) == __last; }
 552
 553   /**
 554    *  @brief  Determines whether a range is a heap using comparison functor.
 555    *  @param  first  Start of range.
 556    *  @param  last   End of range.
 557    *  @param  comp   Comparison functor to use.
 558    *  @return  True if range is a heap, false otherwise.
 559    *  @ingroup heap
 560   */
 561   template<typename _RandomAccessIterator, typename _Compare>
 562     inline bool
 563     is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 564             _Compare __comp)
 565     { return std::is_heap_until(__first, __last, __comp) == __last; }
 566 #endif
 567
 568 _GLIBCXX_END_NAMESPACE
 569
 570 #endif /* _STL_HEAP_H */