libstdc++-v3/include/bits/stl_heap.h

   1 // Heap implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  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 /* NOTE: This is an internal header file, included by other STL headers.
  56  *   You should not attempt to use it directly.
  57  */
  58
  59 #ifndef _CPP_BITS_STL_HEAP_H
  60 #define _CPP_BITS_STL_HEAP_H 1
  61
  62 namespace std
  63 {
  64
  65 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
  66
  67 template <class _RandomAccessIterator, class _Distance, class _Tp>
  68 void
  69 __push_heap(_RandomAccessIterator __first,
  70             _Distance __holeIndex, _Distance __topIndex, _Tp __value)
  71 {
  72   _Distance __parent = (__holeIndex - 1) / 2;
  73   while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
  74     *(__first + __holeIndex) = *(__first + __parent);
  75     __holeIndex = __parent;
  76     __parent = (__holeIndex - 1) / 2;
  77   }
  78   *(__first + __holeIndex) = __value;
  79 }
  80
  81 template <class _RandomAccessIterator, class _Distance, class _Tp>
  82 inline void
  83 __push_heap_aux(_RandomAccessIterator __first,
  84                 _RandomAccessIterator __last, _Distance*, _Tp*)
  85 {
  86   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
  87               _Tp(*(__last - 1)));
  88 }
  89
  90 template <class _RandomAccessIterator>
  91 inline void
  92 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  93 {
  94   // concept requirements
  95   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
  96         _RandomAccessIterator>);
  97   __glibcpp_function_requires(_LessThanComparableConcept<
  98         typename iterator_traits<_RandomAccessIterator>::value_type>);
  99
 100   __push_heap_aux(__first, __last,
 101                   __distance_type(__first), __value_type(__first));
 102 }
 103
 104 template <class _RandomAccessIterator, class _Distance, class _Tp,
 105           class _Compare>
 106 void
 107 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 108             _Distance __topIndex, _Tp __value, _Compare __comp)
 109 {
 110   _Distance __parent = (__holeIndex - 1) / 2;
 111   while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
 112     *(__first + __holeIndex) = *(__first + __parent);
 113     __holeIndex = __parent;
 114     __parent = (__holeIndex - 1) / 2;
 115   }
 116   *(__first + __holeIndex) = __value;
 117 }
 118
 119 template <class _RandomAccessIterator, class _Compare,
 120           class _Distance, class _Tp>
 121 inline void
 122 __push_heap_aux(_RandomAccessIterator __first,
 123                 _RandomAccessIterator __last, _Compare __comp,
 124                 _Distance*, _Tp*)
 125 {
 126   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
 127               _Tp(*(__last - 1)), __comp);
 128 }
 129
 130 template <class _RandomAccessIterator, class _Compare>
 131 inline void
 132 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 133           _Compare __comp)
 134 {
 135   // concept requirements
 136   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 137         _RandomAccessIterator>);
 138
 139   __push_heap_aux(__first, __last, __comp,
 140                   __distance_type(__first), __value_type(__first));
 141 }
 142
 143 template <class _RandomAccessIterator, class _Distance, class _Tp>
 144 void
 145 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 146               _Distance __len, _Tp __value)
 147 {
 148   _Distance __topIndex = __holeIndex;
 149   _Distance __secondChild = 2 * __holeIndex + 2;
 150   while (__secondChild < __len) {
 151     if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
 152       __secondChild--;
 153     *(__first + __holeIndex) = *(__first + __secondChild);
 154     __holeIndex = __secondChild;
 155     __secondChild = 2 * (__secondChild + 1);
 156   }
 157   if (__secondChild == __len) {
 158     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
 159     __holeIndex = __secondChild - 1;
 160   }
 161   __push_heap(__first, __holeIndex, __topIndex, __value);
 162 }
 163
 164 template <class _RandomAccessIterator, class _Tp, class _Distance>
 165 inline void
 166 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 167            _RandomAccessIterator __result, _Tp __value, _Distance*)
 168 {
 169   *__result = *__first;
 170   __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
 171 }
 172
 173 template <class _RandomAccessIterator, class _Tp>
 174 inline void
 175 __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
 176                _Tp*)
 177 {
 178   __pop_heap(__first, __last - 1, __last - 1,
 179              _Tp(*(__last - 1)), __distance_type(__first));
 180 }
 181
 182 template <class _RandomAccessIterator>
 183 inline void pop_heap(_RandomAccessIterator __first,
 184                      _RandomAccessIterator __last)
 185 {
 186   // concept requirements
 187   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 188         _RandomAccessIterator>);
 189   __glibcpp_function_requires(_LessThanComparableConcept<
 190         typename iterator_traits<_RandomAccessIterator>::value_type>);
 191
 192   __pop_heap_aux(__first, __last, __value_type(__first));
 193 }
 194
 195 template <class _RandomAccessIterator, class _Distance,
 196           class _Tp, class _Compare>
 197 void
 198 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 199               _Distance __len, _Tp __value, _Compare __comp)
 200 {
 201   _Distance __topIndex = __holeIndex;
 202   _Distance __secondChild = 2 * __holeIndex + 2;
 203   while (__secondChild < __len) {
 204     if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
 205       __secondChild--;
 206     *(__first + __holeIndex) = *(__first + __secondChild);
 207     __holeIndex = __secondChild;
 208     __secondChild = 2 * (__secondChild + 1);
 209   }
 210   if (__secondChild == __len) {
 211     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
 212     __holeIndex = __secondChild - 1;
 213   }
 214   __push_heap(__first, __holeIndex, __topIndex, __value, __comp);
 215 }
 216
 217 template <class _RandomAccessIterator, class _Tp, class _Compare,
 218           class _Distance>
 219 inline void
 220 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 221            _RandomAccessIterator __result, _Tp __value, _Compare __comp,
 222            _Distance*)
 223 {
 224   *__result = *__first;
 225   __adjust_heap(__first, _Distance(0), _Distance(__last - __first),
 226                 __value, __comp);
 227 }
 228
 229 template <class _RandomAccessIterator, class _Tp, class _Compare>
 230 inline void
 231 __pop_heap_aux(_RandomAccessIterator __first,
 232                _RandomAccessIterator __last, _Tp*, _Compare __comp)
 233 {
 234   __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
 235              __distance_type(__first));
 236 }
 237
 238 template <class _RandomAccessIterator, class _Compare>
 239 inline void
 240 pop_heap(_RandomAccessIterator __first,
 241          _RandomAccessIterator __last, _Compare __comp)
 242 {
 243   // concept requirements
 244   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 245         _RandomAccessIterator>);
 246
 247   __pop_heap_aux(__first, __last, __value_type(__first), __comp);
 248 }
 249
 250 template <class _RandomAccessIterator, class _Tp, class _Distance>
 251 void
 252 __make_heap(_RandomAccessIterator __first,
 253             _RandomAccessIterator __last, _Tp*, _Distance*)
 254 {
 255   if (__last - __first < 2) return;
 256   _Distance __len = __last - __first;
 257   _Distance __parent = (__len - 2)/2;
 258
 259   while (true) {
 260     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
 261     if (__parent == 0) return;
 262     __parent--;
 263   }
 264 }
 265
 266 template <class _RandomAccessIterator>
 267 inline void
 268 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 269 {
 270   // concept requirements
 271   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 272         _RandomAccessIterator>);
 273   __glibcpp_function_requires(_LessThanComparableConcept<
 274         typename iterator_traits<_RandomAccessIterator>::value_type>);
 275
 276   __make_heap(__first, __last,
 277               __value_type(__first), __distance_type(__first));
 278 }
 279
 280 template <class _RandomAccessIterator, class _Compare,
 281           class _Tp, class _Distance>
 282 void
 283 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 284             _Compare __comp, _Tp*, _Distance*)
 285 {
 286   if (__last - __first < 2) return;
 287   _Distance __len = __last - __first;
 288   _Distance __parent = (__len - 2)/2;
 289
 290   while (true) {
 291     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
 292                   __comp);
 293     if (__parent == 0) return;
 294     __parent--;
 295   }
 296 }
 297
 298 template <class _RandomAccessIterator, class _Compare>
 299 inline void
 300 make_heap(_RandomAccessIterator __first,
 301           _RandomAccessIterator __last, _Compare __comp)
 302 {
 303   // concept requirements
 304   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 305         _RandomAccessIterator>);
 306
 307   __make_heap(__first, __last, __comp,
 308               __value_type(__first), __distance_type(__first));
 309 }
 310
 311 template <class _RandomAccessIterator>
 312 void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 313 {
 314   // concept requirements
 315   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 316         _RandomAccessIterator>);
 317   __glibcpp_function_requires(_LessThanComparableConcept<
 318         typename iterator_traits<_RandomAccessIterator>::value_type>);
 319
 320   while (__last - __first > 1)
 321     pop_heap(__first, __last--);
 322 }
 323
 324 template <class _RandomAccessIterator, class _Compare>
 325 void
 326 sort_heap(_RandomAccessIterator __first,
 327           _RandomAccessIterator __last, _Compare __comp)
 328 {
 329   // concept requirements
 330   __glibcpp_function_requires(_Mutable_RandomAccessIteratorConcept<
 331         _RandomAccessIterator>);
 332
 333   while (__last - __first > 1)
 334     pop_heap(__first, __last--, __comp);
 335 }
 336
 337 } // namespace std
 338
 339 #endif /* _CPP_BITS_STL_HEAP_H */
 340
 341 // Local Variables:
 342 // mode:C++
 343 // End: