headers/cpp/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 __SGI_STL_INTERNAL_HEAP_H
  31 #define __SGI_STL_INTERNAL_HEAP_H
  32
  33 __STL_BEGIN_NAMESPACE
  34
  35 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  36 #pragma set woff 1209
  37 #endif
  38
  39 // Heap-manipulation functions: push_heap, pop_heap, make_heap, sort_heap.
  40
  41 template <class _RandomAccessIterator, class _Distance, class _Tp>
  42 void
  43 __push_heap(_RandomAccessIterator __first,
  44             _Distance __holeIndex, _Distance __topIndex, _Tp __value)
  45 {
  46   _Distance __parent = (__holeIndex - 1) / 2;
  47   while (__holeIndex > __topIndex && *(__first + __parent) < __value) {
  48     *(__first + __holeIndex) = *(__first + __parent);
  49     __holeIndex = __parent;
  50     __parent = (__holeIndex - 1) / 2;
  51   }
  52   *(__first + __holeIndex) = __value;
  53 }
  54
  55 template <class _RandomAccessIterator, class _Distance, class _Tp>
  56 inline void
  57 __push_heap_aux(_RandomAccessIterator __first,
  58                 _RandomAccessIterator __last, _Distance*, _Tp*)
  59 {
  60   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
  61               _Tp(*(__last - 1)));
  62 }
  63
  64 template <class _RandomAccessIterator>
  65 inline void
  66 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  67 {
  68   __push_heap_aux(__first, __last,
  69                   __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
  70 }
  71
  72 template <class _RandomAccessIterator, class _Distance, class _Tp,
  73           class _Compare>
  74 void
  75 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  76             _Distance __topIndex, _Tp __value, _Compare __comp)
  77 {
  78   _Distance __parent = (__holeIndex - 1) / 2;
  79   while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
  80     *(__first + __holeIndex) = *(__first + __parent);
  81     __holeIndex = __parent;
  82     __parent = (__holeIndex - 1) / 2;
  83   }
  84   *(__first + __holeIndex) = __value;
  85 }
  86
  87 template <class _RandomAccessIterator, class _Compare,
  88           class _Distance, class _Tp>
  89 inline void
  90 __push_heap_aux(_RandomAccessIterator __first,
  91                 _RandomAccessIterator __last, _Compare __comp,
  92                 _Distance*, _Tp*)
  93 {
  94   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
  95               _Tp(*(__last - 1)), __comp);
  96 }
  97
  98 template <class _RandomAccessIterator, class _Compare>
  99 inline void
 100 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 101           _Compare __comp)
 102 {
 103   __push_heap_aux(__first, __last, __comp,
 104                   __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
 105 }
 106
 107 template <class _RandomAccessIterator, class _Distance, class _Tp>
 108 void
 109 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 110               _Distance __len, _Tp __value)
 111 {
 112   _Distance __topIndex = __holeIndex;
 113   _Distance __secondChild = 2 * __holeIndex + 2;
 114   while (__secondChild < __len) {
 115     if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
 116       __secondChild--;
 117     *(__first + __holeIndex) = *(__first + __secondChild);
 118     __holeIndex = __secondChild;
 119     __secondChild = 2 * (__secondChild + 1);
 120   }
 121   if (__secondChild == __len) {
 122     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
 123     __holeIndex = __secondChild - 1;
 124   }
 125   __push_heap(__first, __holeIndex, __topIndex, __value);
 126 }
 127
 128 template <class _RandomAccessIterator, class _Tp, class _Distance>
 129 inline void
 130 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 131            _RandomAccessIterator __result, _Tp __value, _Distance*)
 132 {
 133   *__result = *__first;
 134   __adjust_heap(__first, _Distance(0), _Distance(__last - __first), __value);
 135 }
 136
 137 template <class _RandomAccessIterator, class _Tp>
 138 inline void
 139 __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last,
 140                _Tp*)
 141 {
 142   __pop_heap(__first, __last - 1, __last - 1,
 143              _Tp(*(__last - 1)), __DISTANCE_TYPE(__first));
 144 }
 145
 146 template <class _RandomAccessIterator>
 147 inline void pop_heap(_RandomAccessIterator __first,
 148                      _RandomAccessIterator __last)
 149 {
 150   __pop_heap_aux(__first, __last, __VALUE_TYPE(__first));
 151 }
 152
 153 template <class _RandomAccessIterator, class _Distance,
 154           class _Tp, class _Compare>
 155 void
 156 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 157               _Distance __len, _Tp __value, _Compare __comp)
 158 {
 159   _Distance __topIndex = __holeIndex;
 160   _Distance __secondChild = 2 * __holeIndex + 2;
 161   while (__secondChild < __len) {
 162     if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
 163       __secondChild--;
 164     *(__first + __holeIndex) = *(__first + __secondChild);
 165     __holeIndex = __secondChild;
 166     __secondChild = 2 * (__secondChild + 1);
 167   }
 168   if (__secondChild == __len) {
 169     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
 170     __holeIndex = __secondChild - 1;
 171   }
 172   __push_heap(__first, __holeIndex, __topIndex, __value, __comp);
 173 }
 174
 175 template <class _RandomAccessIterator, class _Tp, class _Compare,
 176           class _Distance>
 177 inline void
 178 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 179            _RandomAccessIterator __result, _Tp __value, _Compare __comp,
 180            _Distance*)
 181 {
 182   *__result = *__first;
 183   __adjust_heap(__first, _Distance(0), _Distance(__last - __first),
 184                 __value, __comp);
 185 }
 186
 187 template <class _RandomAccessIterator, class _Tp, class _Compare>
 188 inline void
 189 __pop_heap_aux(_RandomAccessIterator __first,
 190                _RandomAccessIterator __last, _Tp*, _Compare __comp)
 191 {
 192   __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
 193              __DISTANCE_TYPE(__first));
 194 }
 195
 196 template <class _RandomAccessIterator, class _Compare>
 197 inline void
 198 pop_heap(_RandomAccessIterator __first,
 199          _RandomAccessIterator __last, _Compare __comp)
 200 {
 201     __pop_heap_aux(__first, __last, __VALUE_TYPE(__first), __comp);
 202 }
 203
 204 template <class _RandomAccessIterator, class _Tp, class _Distance>
 205 void
 206 __make_heap(_RandomAccessIterator __first,
 207             _RandomAccessIterator __last, _Tp*, _Distance*)
 208 {
 209   if (__last - __first < 2) return;
 210   _Distance __len = __last - __first;
 211   _Distance __parent = (__len - 2)/2;
 212
 213   while (true) {
 214     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
 215     if (__parent == 0) return;
 216     __parent--;
 217   }
 218 }
 219
 220 template <class _RandomAccessIterator>
 221 inline void
 222 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 223 {
 224   __make_heap(__first, __last,
 225               __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
 226 }
 227
 228 template <class _RandomAccessIterator, class _Compare,
 229           class _Tp, class _Distance>
 230 void
 231 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 232             _Compare __comp, _Tp*, _Distance*)
 233 {
 234   if (__last - __first < 2) return;
 235   _Distance __len = __last - __first;
 236   _Distance __parent = (__len - 2)/2;
 237
 238   while (true) {
 239     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
 240                   __comp);
 241     if (__parent == 0) return;
 242     __parent--;
 243   }
 244 }
 245
 246 template <class _RandomAccessIterator, class _Compare>
 247 inline void
 248 make_heap(_RandomAccessIterator __first,
 249           _RandomAccessIterator __last, _Compare __comp)
 250 {
 251   __make_heap(__first, __last, __comp,
 252               __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
 253 }
 254
 255 template <class _RandomAccessIterator>
 256 void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 257 {
 258   while (__last - __first > 1)
 259     pop_heap(__first, __last--);
 260 }
 261
 262 template <class _RandomAccessIterator, class _Compare>
 263 void
 264 sort_heap(_RandomAccessIterator __first,
 265           _RandomAccessIterator __last, _Compare __comp)
 266 {
 267   while (__last - __first > 1)
 268     pop_heap(__first, __last--, __comp);
 269 }
 270
 271 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
 272 #pragma reset woff 1209
 273 #endif
 274
 275 __STL_END_NAMESPACE
 276
 277 #endif /* __SGI_STL_INTERNAL_HEAP_H */
 278
 279 // Local Variables:
 280 // mode:C++
 281 // End: