contrib/libstdc++/include/bits/stl_heap.h

   1 // Heap implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2004, 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /*
  31  *
  32  * Copyright (c) 1994
  33  * Hewlett-Packard Company
  34  *
  35  * Permission to use, copy, modify, distribute and sell this software
  36  * and its documentation for any purpose is hereby granted without fee,
  37  * provided that the above copyright notice appear in all copies and
  38  * that both that copyright notice and this permission notice appear
  39  * in supporting documentation.  Hewlett-Packard Company makes no
  40  * representations about the suitability of this software for any
  41  * purpose.  It is provided "as is" without express or implied warranty.
  42  *
  43  * Copyright (c) 1997
  44  * Silicon Graphics Computer Systems, Inc.
  45  *
  46  * Permission to use, copy, modify, distribute and sell this software
  47  * and its documentation for any purpose is hereby granted without fee,
  48  * provided that the above copyright notice appear in all copies and
  49  * that both that copyright notice and this permission notice appear
  50  * in supporting documentation.  Silicon Graphics makes no
  51  * representations about the suitability of this software for any
  52  * purpose.  It is provided "as is" without express or implied warranty.
  53  */
  54
  55 /** @file stl_heap.h
  56  *  This is an internal header file, included by other library headers.
  57  *  You should not attempt to use it directly.
  58  */
  59
  60 #ifndef _STL_HEAP_H
  61 #define _STL_HEAP_H 1
  62
  63 #include <debug/debug.h>
  64
  65 _GLIBCXX_BEGIN_NAMESPACE(std)
  66
  67   // is_heap, a predicate testing whether or not a range is
  68   // a heap.  This function is an extension, not part of the C++
  69   // standard.
  70   template<typename _RandomAccessIterator, typename _Distance>
  71     bool
  72     __is_heap(_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 false;
  79           if ((__child & 1) == 0)
  80             ++__parent;
  81         }
  82       return true;
  83     }
  84
  85   template<typename _RandomAccessIterator, typename _Distance,
  86            typename _StrictWeakOrdering>
  87     bool
  88     __is_heap(_RandomAccessIterator __first, _StrictWeakOrdering __comp,
  89               _Distance __n)
  90     {
  91       _Distance __parent = 0;
  92       for (_Distance __child = 1; __child < __n; ++__child)
  93         {
  94           if (__comp(__first[__parent], __first[__child]))
  95             return false;
  96           if ((__child & 1) == 0)
  97             ++__parent;
  98         }
  99       return true;
 100     }
 101
 102   template<typename _RandomAccessIterator>
 103     bool
 104     __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 105     { return std::__is_heap(__first, std::distance(__first, __last)); }
 106
 107   template<typename _RandomAccessIterator, typename _StrictWeakOrdering>
 108     bool
 109     __is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 110             _StrictWeakOrdering __comp)
 111     { return std::__is_heap(__first, __comp, std::distance(__first, __last)); }
 112
 113   // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
 114
 115   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
 116     void
 117     __push_heap(_RandomAccessIterator __first,
 118                 _Distance __holeIndex, _Distance __topIndex, _Tp __value)
 119     {
 120       _Distance __parent = (__holeIndex - 1) / 2;
 121       while (__holeIndex > __topIndex && *(__first + __parent) < __value)
 122         {
 123           *(__first + __holeIndex) = *(__first + __parent);
 124           __holeIndex = __parent;
 125           __parent = (__holeIndex - 1) / 2;
 126         }
 127       *(__first + __holeIndex) = __value;
 128     }
 129
 130   /**
 131    *  @brief  Push an element onto a heap.
 132    *  @param  first  Start of heap.
 133    *  @param  last   End of heap + element.
 134    *  @ingroup heap
 135    *
 136    *  This operation pushes the element at last-1 onto the valid heap over the
 137    *  range [first,last-1).  After completion, [first,last) is a valid heap.
 138   */
 139   template<typename _RandomAccessIterator>
 140     inline void
 141     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 142     {
 143       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 144           _ValueType;
 145       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 146           _DistanceType;
 147
 148       // concept requirements
 149       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 150             _RandomAccessIterator>)
 151       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
 152       __glibcxx_requires_valid_range(__first, __last);
 153       //      __glibcxx_requires_heap(__first, __last - 1);
 154
 155       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
 156                        _DistanceType(0), _ValueType(*(__last - 1)));
 157     }
 158
 159   template<typename _RandomAccessIterator, typename _Distance, typename _Tp,
 160             typename _Compare>
 161     void
 162     __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 163                 _Distance __topIndex, _Tp __value, _Compare __comp)
 164     {
 165       _Distance __parent = (__holeIndex - 1) / 2;
 166       while (__holeIndex > __topIndex
 167              && __comp(*(__first + __parent), __value))
 168         {
 169           *(__first + __holeIndex) = *(__first + __parent);
 170           __holeIndex = __parent;
 171           __parent = (__holeIndex - 1) / 2;
 172         }
 173       *(__first + __holeIndex) = __value;
 174     }
 175
 176   /**
 177    *  @brief  Push an element onto a heap using comparison functor.
 178    *  @param  first  Start of heap.
 179    *  @param  last   End of heap + element.
 180    *  @param  comp   Comparison functor.
 181    *  @ingroup heap
 182    *
 183    *  This operation pushes the element at last-1 onto the valid heap over the
 184    *  range [first,last-1).  After completion, [first,last) is a valid heap.
 185    *  Compare operations are performed using comp.
 186   */
 187   template<typename _RandomAccessIterator, typename _Compare>
 188     inline void
 189     push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 190               _Compare __comp)
 191     {
 192       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 193           _ValueType;
 194       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 195           _DistanceType;
 196
 197       // concept requirements
 198       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 199             _RandomAccessIterator>)
 200       __glibcxx_requires_valid_range(__first, __last);
 201       __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
 202
 203       std::__push_heap(__first, _DistanceType((__last - __first) - 1),
 204                        _DistanceType(0), _ValueType(*(__last - 1)), __comp);
 205     }
 206
 207   template<typename _RandomAccessIterator, typename _Distance, typename _Tp>
 208     void
 209     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 210                   _Distance __len, _Tp __value)
 211     {
 212       const _Distance __topIndex = __holeIndex;
 213       _Distance __secondChild = 2 * __holeIndex + 2;
 214       while (__secondChild < __len)
 215         {
 216           if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
 217             __secondChild--;
 218           *(__first + __holeIndex) = *(__first + __secondChild);
 219           __holeIndex = __secondChild;
 220           __secondChild = 2 * (__secondChild + 1);
 221         }
 222       if (__secondChild == __len)
 223         {
 224           *(__first + __holeIndex) = *(__first + (__secondChild - 1));
 225           __holeIndex = __secondChild - 1;
 226         }
 227       std::__push_heap(__first, __holeIndex, __topIndex, __value);
 228     }
 229
 230   template<typename _RandomAccessIterator, typename _Tp>
 231     inline void
 232     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 233                _RandomAccessIterator __result, _Tp __value)
 234     {
 235       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 236         _Distance;
 237       *__result = *__first;
 238       std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
 239                          __value);
 240     }
 241
 242   /**
 243    *  @brief  Pop an element off a heap.
 244    *  @param  first  Start of heap.
 245    *  @param  last   End of heap.
 246    *  @ingroup heap
 247    *
 248    *  This operation pops the top of the heap.  The elements first and last-1
 249    *  are swapped and [first,last-1) is made into a heap.
 250   */
 251   template<typename _RandomAccessIterator>
 252     inline void
 253     pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 254     {
 255       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 256         _ValueType;
 257
 258       // concept requirements
 259       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 260             _RandomAccessIterator>)
 261       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
 262       __glibcxx_requires_valid_range(__first, __last);
 263       __glibcxx_requires_heap(__first, __last);
 264
 265       std::__pop_heap(__first, __last - 1, __last - 1,
 266                       _ValueType(*(__last - 1)));
 267     }
 268
 269   template<typename _RandomAccessIterator, typename _Distance,
 270            typename _Tp, typename _Compare>
 271     void
 272     __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 273                   _Distance __len, _Tp __value, _Compare __comp)
 274     {
 275       const _Distance __topIndex = __holeIndex;
 276       _Distance __secondChild = 2 * __holeIndex + 2;
 277       while (__secondChild < __len)
 278         {
 279           if (__comp(*(__first + __secondChild),
 280                      *(__first + (__secondChild - 1))))
 281             __secondChild--;
 282           *(__first + __holeIndex) = *(__first + __secondChild);
 283           __holeIndex = __secondChild;
 284           __secondChild = 2 * (__secondChild + 1);
 285         }
 286       if (__secondChild == __len)
 287         {
 288           *(__first + __holeIndex) = *(__first + (__secondChild - 1));
 289           __holeIndex = __secondChild - 1;
 290         }
 291       std::__push_heap(__first, __holeIndex, __topIndex, __value, __comp);
 292     }
 293
 294   template<typename _RandomAccessIterator, typename _Tp, typename _Compare>
 295     inline void
 296     __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 297                _RandomAccessIterator __result, _Tp __value, _Compare __comp)
 298     {
 299       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 300         _Distance;
 301       *__result = *__first;
 302       std::__adjust_heap(__first, _Distance(0), _Distance(__last - __first),
 303                          __value, __comp);
 304     }
 305
 306   /**
 307    *  @brief  Pop an element off a heap using comparison functor.
 308    *  @param  first  Start of heap.
 309    *  @param  last   End of heap.
 310    *  @param  comp   Comparison functor to use.
 311    *  @ingroup heap
 312    *
 313    *  This operation pops the top of the heap.  The elements first and last-1
 314    *  are swapped and [first,last-1) is made into a heap.  Comparisons are
 315    *  made using comp.
 316   */
 317   template<typename _RandomAccessIterator, typename _Compare>
 318     inline void
 319     pop_heap(_RandomAccessIterator __first,
 320              _RandomAccessIterator __last, _Compare __comp)
 321     {
 322       // concept requirements
 323       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 324             _RandomAccessIterator>)
 325       __glibcxx_requires_valid_range(__first, __last);
 326       __glibcxx_requires_heap_pred(__first, __last, __comp);
 327
 328       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 329         _ValueType;
 330       std::__pop_heap(__first, __last - 1, __last - 1,
 331                       _ValueType(*(__last - 1)), __comp);
 332     }
 333
 334   /**
 335    *  @brief  Construct a heap over a range.
 336    *  @param  first  Start of heap.
 337    *  @param  last   End of heap.
 338    *  @ingroup heap
 339    *
 340    *  This operation makes the elements in [first,last) into a heap.
 341   */
 342   template<typename _RandomAccessIterator>
 343     void
 344     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 345     {
 346       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 347           _ValueType;
 348       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 349           _DistanceType;
 350
 351       // concept requirements
 352       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 353             _RandomAccessIterator>)
 354       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
 355       __glibcxx_requires_valid_range(__first, __last);
 356
 357       if (__last - __first < 2)
 358         return;
 359
 360       const _DistanceType __len = __last - __first;
 361       _DistanceType __parent = (__len - 2) / 2;
 362       while (true)
 363         {
 364           std::__adjust_heap(__first, __parent, __len,
 365                              _ValueType(*(__first + __parent)));
 366           if (__parent == 0)
 367             return;
 368           __parent--;
 369         }
 370     }
 371
 372   /**
 373    *  @brief  Construct a heap over a range using comparison functor.
 374    *  @param  first  Start of heap.
 375    *  @param  last   End of heap.
 376    *  @param  comp   Comparison functor to use.
 377    *  @ingroup heap
 378    *
 379    *  This operation makes the elements in [first,last) into a heap.
 380    *  Comparisons are made using comp.
 381   */
 382   template<typename _RandomAccessIterator, typename _Compare>
 383     inline void
 384     make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 385               _Compare __comp)
 386     {
 387       typedef typename iterator_traits<_RandomAccessIterator>::value_type
 388           _ValueType;
 389       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
 390           _DistanceType;
 391
 392       // concept requirements
 393       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 394             _RandomAccessIterator>)
 395       __glibcxx_requires_valid_range(__first, __last);
 396
 397       if (__last - __first < 2)
 398         return;
 399
 400       const _DistanceType __len = __last - __first;
 401       _DistanceType __parent = (__len - 2) / 2;
 402       while (true)
 403         {
 404           std::__adjust_heap(__first, __parent, __len,
 405                              _ValueType(*(__first + __parent)), __comp);
 406           if (__parent == 0)
 407             return;
 408           __parent--;
 409         }
 410     }
 411
 412   /**
 413    *  @brief  Sort a heap.
 414    *  @param  first  Start of heap.
 415    *  @param  last   End of heap.
 416    *  @ingroup heap
 417    *
 418    *  This operation sorts the valid heap in the range [first,last).
 419   */
 420   template<typename _RandomAccessIterator>
 421     void
 422     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 423     {
 424       // concept requirements
 425       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 426             _RandomAccessIterator>)
 427       __glibcxx_function_requires(_LessThanComparableConcept<
 428             typename iterator_traits<_RandomAccessIterator>::value_type>)
 429       __glibcxx_requires_valid_range(__first, __last);
 430       //      __glibcxx_requires_heap(__first, __last);
 431
 432       while (__last - __first > 1)
 433         std::pop_heap(__first, _RandomAccessIterator(__last--));
 434     }
 435
 436   /**
 437    *  @brief  Sort a heap using comparison functor.
 438    *  @param  first  Start of heap.
 439    *  @param  last   End of heap.
 440    *  @param  comp   Comparison functor to use.
 441    *  @ingroup heap
 442    *
 443    *  This operation sorts the valid heap in the range [first,last).
 444    *  Comparisons are made using comp.
 445   */
 446   template<typename _RandomAccessIterator, typename _Compare>
 447     void
 448     sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 449               _Compare __comp)
 450     {
 451       // concept requirements
 452       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 453             _RandomAccessIterator>)
 454       __glibcxx_requires_valid_range(__first, __last);
 455       __glibcxx_requires_heap_pred(__first, __last, __comp);
 456
 457       while (__last - __first > 1)
 458         std::pop_heap(__first, _RandomAccessIterator(__last--), __comp);
 459     }
 460
 461 _GLIBCXX_END_NAMESPACE
 462
 463 #endif /* _STL_HEAP_H */