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

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Permission to use, copy, modify, distribute and sell this software
   7  * and its documentation for any purpose is hereby granted without fee,
   8  * provided that the above copyright notice appear in all copies and
   9  * that both that copyright notice and this permission notice appear
  10  * in supporting documentation.  Hewlett-Packard Company makes no
  11  * representations about the suitability of this software for any
  12  * purpose.  It is provided "as is" without express or implied warranty.
  13  *
  14  * Copyright (c) 1997
  15  * Silicon Graphics Computer Systems, Inc.
  16  *
  17  * Permission to use, copy, modify, distribute and sell this software
  18  * and its documentation for any purpose is hereby granted without fee,
  19  * provided that the above copyright notice appear in all copies and
  20  * that both that copyright notice and this permission notice appear
  21  * in supporting documentation.  Silicon Graphics makes no
  22  * representations about the suitability of this software for any
  23  * purpose.  It is provided "as is" without express or implied warranty.
  24  */
  25
  26 /* NOTE: This is an internal header file, included by other STL headers.
  27  *   You should not attempt to use it directly.
  28  */
  29
  30 #ifndef _CPP_BITS_STL_HEAP_H
  31 #define _CPP_BITS_STL_HEAP_H 1
  32
  33 namespace std
  34 {
  35
  36 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
  37
  38 template <class _RandomAccessIterator, class _Distance, class _Tp>
  39 void
  40 __push_heap(_RandomAccessIterator __first,
  41             _Distance __holeIndex, _Distance __topIndex, _Tp __value)
  42 {
  43   _Distance __parent = (__holeIndex - 1) / 2;
  44   while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
  45     *(__first + __holeIndex) = *(__first + __parent);
  46     __holeIndex = __parent;
  47     __parent = (__holeIndex - 1) / 2;
  48   }
  49   *(__first + __holeIndex) = __value;
  50 }
  51
  52 template <class _RandomAccessIterator, class _Distance, class _Tp>
  53 inline void
  54 __push_heap_aux(_RandomAccessIterator __first,
  55                 _RandomAccessIterator __last, _Distance*, _Tp*)
  56 {
  57   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
  58               _Tp(*(__last - 1)));
  59 }
  60
  61 template <class _RandomAccessIterator>
  62 inline void
  63 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  64 {
  65   // concept requirements
  66   glibcpp_function_requires(Mutable_RandomAccessIteratorConcept<
  67         _RandomAccessIterator>);
  68   glibcpp_function_requires(LessThanComparableConcept<
  69         typename iterator_traits<_RandomAccessIterator>::value_type>);
  70
  71   __push_heap_aux(__first, __last,
  72                   __distance_type(__first), __value_type(__first));
  73 }
  74
  75 template <class _RandomAccessIterator, class _Distance, class _Tp,
  76           class _Compare>
  77 void
  78 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  79             _Distance __topIndex, _Tp __value, _Compare __comp)
  80 {
  81   _Distance __parent = (__holeIndex - 1) / 2;
  82   while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
  83     *(__first + __holeIndex) = *(__first + __parent);
  84     __holeIndex = __parent;
  85     __parent = (__holeIndex - 1) / 2;
  86   }
  87   *(__first + __holeIndex) = __value;
  88 }
  89
  90 template <class _RandomAccessIterator, class _Compare,
  91           class _Distance, class _Tp>
  92 inline void
  93 __push_heap_aux(_RandomAccessIterator __first,
  94                 _RandomAccessIterator __last, _Compare __comp,
  95                 _Distance*, _Tp*)
  96 {
  97   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
  98               _Tp(*(__last - 1)), __comp);
  99 }
 100
 101 template <class _RandomAccessIterator, class _Compare>
 102 inline void
 103 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 104           _Compare __comp)
 105 {
 106   // concept requirements
 107   glibcpp_function_requires(Mutable_RandomAccessIteratorConcept<
 108         _RandomAccessIterator>);
 109
 110   __push_heap_aux(__first, __last, __comp,
 111                   __distance_type(__first), __value_type(__first));
 112 }
 113
 114 template <class _RandomAccessIterator, class _Distance, class _Tp>
 115 void
 116 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 117               _Distance __len, _Tp __value)
 118 {
 119   _Distance __topIndex = __holeIndex;
 120   _Distance __secondChild = 2 * __holeIndex + 2;
 121   while (__secondChild < __len) {
 122     if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
 123       __secondChild--;
 124     *(__first + __holeIndex) = *(__first + __secondChild);
 125     __holeIndex = __secondChild;
 126     __secondChild = 2 * (__secondChild + 1);
 127   }
 128   if (__secondChild == __len) {
 129     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
 130     __holeIndex = __secondChild - 1;
 131   }
 132   __push_heap(__first, __holeIndex, __topIndex, __value);
 133 }
 134
 135 template <class _RandomAccessIterator, class _Tp, class _Distance>
 136 inline void
 137 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 138            _RandomAccessIterator __result, _Tp __value, _Distance*)
 139 {
 140   *__result = *__first;
 141   __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
 142 }
 143
 144 template <class _RandomAccessIterator, class _Tp>
 145 inline void
 146 __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
 147                _Tp*)
 148 {
 149   __pop_heap(__first, __last - 1, __last - 1,
 150              _Tp(*(__last - 1)), __distance_type(__first));
 151 }
 152
 153 template <class _RandomAccessIterator>
 154 inline void pop_heap(_RandomAccessIterator __first,
 155                      _RandomAccessIterator __last)
 156 {
 157   // concept requirements
 158   glibcpp_function_requires(Mutable_RandomAccessIteratorConcept<
 159         _RandomAccessIterator>);
 160   glibcpp_function_requires(LessThanComparableConcept<
 161         typename iterator_traits<_RandomAccessIterator>::value_type>);
 162
 163   __pop_heap_aux(__first, __last, __value_type(__first));
 164 }
 165
 166 template <class _RandomAccessIterator, class _Distance,
 167           class _Tp, class _Compare>
 168 void
 169 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 170               _Distance __len, _Tp __value, _Compare __comp)
 171 {
 172   _Distance __topIndex = __holeIndex;
 173   _Distance __secondChild = 2 * __holeIndex + 2;
 174   while (__secondChild < __len) {
 175     if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
 176       __secondChild--;
 177     *(__first + __holeIndex) = *(__first + __secondChild);
 178     __holeIndex = __secondChild;
 179     __secondChild = 2 * (__secondChild + 1);
 180   }
 181   if (__secondChild == __len) {
 182     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
 183     __holeIndex = __secondChild - 1;
 184   }
 185   __push_heap(__first, __holeIndex, __topIndex, __value, __comp);
 186 }
 187
 188 template <class _RandomAccessIterator, class _Tp, class _Compare,
 189           class _Distance>
 190 inline void
 191 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 192            _RandomAccessIterator __result, _Tp __value, _Compare __comp,
 193            _Distance*)
 194 {
 195   *__result = *__first;
 196   __adjust_heap(__first, _Distance(0), _Distance(__last - __first),
 197                 __value, __comp);
 198 }
 199
 200 template <class _RandomAccessIterator, class _Tp, class _Compare>
 201 inline void
 202 __pop_heap_aux(_RandomAccessIterator __first,
 203                _RandomAccessIterator __last, _Tp*, _Compare __comp)
 204 {
 205   __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
 206              __distance_type(__first));
 207 }
 208
 209 template <class _RandomAccessIterator, class _Compare>
 210 inline void
 211 pop_heap(_RandomAccessIterator __first,
 212          _RandomAccessIterator __last, _Compare __comp)
 213 {
 214   // concept requirements
 215   glibcpp_function_requires(Mutable_RandomAccessIteratorConcept<
 216         _RandomAccessIterator>);
 217
 218   __pop_heap_aux(__first, __last, __value_type(__first), __comp);
 219 }
 220
 221 template <class _RandomAccessIterator, class _Tp, class _Distance>
 222 void
 223 __make_heap(_RandomAccessIterator __first,
 224             _RandomAccessIterator __last, _Tp*, _Distance*)
 225 {
 226   if (__last - __first < 2) return;
 227   _Distance __len = __last - __first;
 228   _Distance __parent = (__len - 2)/2;
 229
 230   while (true) {
 231     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
 232     if (__parent == 0) return;
 233     __parent--;
 234   }
 235 }
 236
 237 template <class _RandomAccessIterator>
 238 inline void
 239 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 240 {
 241   // concept requirements
 242   glibcpp_function_requires(Mutable_RandomAccessIteratorConcept<
 243         _RandomAccessIterator>);
 244   glibcpp_function_requires(LessThanComparableConcept<
 245         typename iterator_traits<_RandomAccessIterator>::value_type>);
 246
 247   __make_heap(__first, __last,
 248               __value_type(__first), __distance_type(__first));
 249 }
 250
 251 template <class _RandomAccessIterator, class _Compare,
 252           class _Tp, class _Distance>
 253 void
 254 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 255             _Compare __comp, _Tp*, _Distance*)
 256 {
 257   if (__last - __first < 2) return;
 258   _Distance __len = __last - __first;
 259   _Distance __parent = (__len - 2)/2;
 260
 261   while (true) {
 262     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
 263                   __comp);
 264     if (__parent == 0) return;
 265     __parent--;
 266   }
 267 }
 268
 269 template <class _RandomAccessIterator, class _Compare>
 270 inline void
 271 make_heap(_RandomAccessIterator __first,
 272           _RandomAccessIterator __last, _Compare __comp)
 273 {
 274   // concept requirements
 275   glibcpp_function_requires(Mutable_RandomAccessIteratorConcept<
 276         _RandomAccessIterator>);
 277
 278   __make_heap(__first, __last, __comp,
 279               __value_type(__first), __distance_type(__first));
 280 }
 281
 282 template <class _RandomAccessIterator>
 283 void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 284 {
 285   // concept requirements
 286   glibcpp_function_requires(Mutable_RandomAccessIteratorConcept<
 287         _RandomAccessIterator>);
 288   glibcpp_function_requires(LessThanComparableConcept<
 289         typename iterator_traits<_RandomAccessIterator>::value_type>);
 290
 291   while (__last - __first > 1)
 292     pop_heap(__first, __last--);
 293 }
 294
 295 template <class _RandomAccessIterator, class _Compare>
 296 void
 297 sort_heap(_RandomAccessIterator __first,
 298           _RandomAccessIterator __last, _Compare __comp)
 299 {
 300   // concept requirements
 301   glibcpp_function_requires(Mutable_RandomAccessIteratorConcept<
 302         _RandomAccessIterator>);
 303
 304   while (__last - __first > 1)
 305     pop_heap(__first, __last--, __comp);
 306 }
 307
 308 } // namespace std
 309
 310 #endif /* _CPP_BITS_STL_HEAP_H */
 311
 312 // Local Variables:
 313 // mode:C++
 314 // End: