include/c++/stl/stl/_heap.c

   1 /*
   2  *
   3  *
   4  * Copyright (c) 1994
   5  * Hewlett-Packard Company
   6  *
   7  * Copyright (c) 1996,1997
   8  * Silicon Graphics Computer Systems, Inc.
   9  *
  10  * Copyright (c) 1997
  11  * Moscow Center for SPARC Technology
  12  *
  13  * Copyright (c) 1999
  14  * Boris Fomitchev
  15  *
  16  * This material is provided "as is", with absolutely no warranty expressed
  17  * or implied. Any use is at your own risk.
  18  *
  19  * Permission to use or copy this software for any purpose is hereby granted
  20  * without fee, provided the above notices are retained on all copies.
  21  * Permission to modify the code and to distribute modified code is granted,
  22  * provided the above notices are retained, and a notice that the code was
  23  * modified is included with the above copyright notice.
  24  *
  25  */
  26 #ifndef _STLP_HEAP_C
  27 #define _STLP_HEAP_C
  28
  29 #ifndef _STLP_INTERNAL_HEAP_H
  30 # include <stl/_heap.h>
  31 #endif
  32
  33 #ifndef _STLP_INTERNAL_ITERATOR_BASE_H
  34 # include <stl/_iterator_base.h>
  35 #endif
  36
  37 _STLP_BEGIN_NAMESPACE
  38
  39 template <class _RandomAccessIterator, class _Distance, class _Tp>
  40 _STLP_INLINE_LOOP
  41 void
  42 __push_heap(_RandomAccessIterator __first,
  43             _Distance __holeIndex, _Distance __topIndex, _Tp __val)
  44 {
  45   _Distance __parent = (__holeIndex - 1) / 2;
  46   while (__holeIndex > __topIndex && *(__first + __parent) < __val) {
  47     *(__first + __holeIndex) = *(__first + __parent);
  48     __holeIndex = __parent;
  49     __parent = (__holeIndex - 1) / 2;
  50   }
  51   *(__first + __holeIndex) = __val;
  52 }
  53
  54 template <class _RandomAccessIterator, class _Distance, class _Tp>
  55 inline void
  56 __push_heap_aux(_RandomAccessIterator __first,
  57                 _RandomAccessIterator __last, _Distance*, _Tp*)
  58 {
  59   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
  60               _Tp(*(__last - 1)));
  61 }
  62
  63 template <class _RandomAccessIterator>
  64 void
  65 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
  66 {
  67   __push_heap_aux(__first, __last,
  68                   _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
  69 }
  70
  71
  72 template <class _RandomAccessIterator, class _Distance, class _Tp,
  73           class _Compare>
  74 _STLP_INLINE_LOOP
  75 void
  76 __push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
  77             _Distance __topIndex, _Tp __val, _Compare __comp)
  78 {
  79   _Distance __parent = (__holeIndex - 1) / 2;
  80   while (__holeIndex > __topIndex && __comp(*(__first + __parent), __val)) {
  81     _STLP_VERBOSE_ASSERT(!__comp(__val, *(__first + __parent)), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
  82     *(__first + __holeIndex) = *(__first + __parent);
  83     __holeIndex = __parent;
  84     __parent = (__holeIndex - 1) / 2;
  85   }
  86   *(__first + __holeIndex) = __val;
  87 }
  88
  89 template <class _RandomAccessIterator, class _Compare,
  90           class _Distance, class _Tp>
  91 inline void
  92 __push_heap_aux(_RandomAccessIterator __first,
  93                 _RandomAccessIterator __last, _Compare __comp,
  94                 _Distance*, _Tp*)
  95 {
  96   __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
  97               _Tp(*(__last - 1)), __comp);
  98 }
  99
 100 template <class _RandomAccessIterator, class _Compare>
 101 void
 102 push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 103           _Compare __comp)
 104 {
 105   __push_heap_aux(__first, __last, __comp,
 106                   _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
 107 }
 108
 109 template <class _RandomAccessIterator, class _Distance, class _Tp>
 110 void
 111 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 112               _Distance __len, _Tp __val) {
 113   _Distance __topIndex = __holeIndex;
 114   _Distance __secondChild = 2 * __holeIndex + 2;
 115   while (__secondChild < __len) {
 116     if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
 117       __secondChild--;
 118     *(__first + __holeIndex) = *(__first + __secondChild);
 119     __holeIndex = __secondChild;
 120     __secondChild = 2 * (__secondChild + 1);
 121   }
 122   if (__secondChild == __len) {
 123     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
 124     __holeIndex = __secondChild - 1;
 125   }
 126   __push_heap(__first, __holeIndex, __topIndex, __val);
 127 }
 128
 129
 130 template <class _RandomAccessIterator, class _Tp>
 131 inline void
 132 __pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*) {
 133   __pop_heap(__first, __last - 1, __last - 1,
 134              _Tp(*(__last - 1)), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
 135 }
 136
 137 template <class _RandomAccessIterator>
 138 void pop_heap(_RandomAccessIterator __first,
 139         _RandomAccessIterator __last) {
 140   __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
 141 }
 142
 143 template <class _RandomAccessIterator, class _Distance,
 144           class _Tp, class _Compare>
 145 void
 146 __adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 147               _Distance __len, _Tp __val, _Compare __comp)
 148 {
 149   _Distance __topIndex = __holeIndex;
 150   _Distance __secondChild = 2 * __holeIndex + 2;
 151   while (__secondChild < __len) {
 152     if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1)))) {
 153       _STLP_VERBOSE_ASSERT(!__comp(*(__first + (__secondChild - 1)), *(__first + __secondChild)),
 154                            _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
 155       __secondChild--;
 156     }
 157     *(__first + __holeIndex) = *(__first + __secondChild);
 158     __holeIndex = __secondChild;
 159     __secondChild = 2 * (__secondChild + 1);
 160   }
 161   if (__secondChild == __len) {
 162     *(__first + __holeIndex) = *(__first + (__secondChild - 1));
 163     __holeIndex = __secondChild - 1;
 164   }
 165   __push_heap(__first, __holeIndex, __topIndex, __val, __comp);
 166 }
 167
 168
 169 template <class _RandomAccessIterator, class _Tp, class _Compare>
 170 inline void
 171 __pop_heap_aux(_RandomAccessIterator __first,
 172                _RandomAccessIterator __last, _Tp*, _Compare __comp)
 173 {
 174   __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
 175              _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
 176 }
 177
 178
 179 template <class _RandomAccessIterator, class _Compare>
 180 void
 181 pop_heap(_RandomAccessIterator __first,
 182          _RandomAccessIterator __last, _Compare __comp)
 183 {
 184     __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator), __comp);
 185 }
 186
 187 template <class _RandomAccessIterator, class _Tp, class _Distance>
 188 _STLP_INLINE_LOOP
 189 void
 190 __make_heap(_RandomAccessIterator __first,
 191             _RandomAccessIterator __last, _Tp*, _Distance*)
 192 {
 193   if (__last - __first < 2) return;
 194   _Distance __len = __last - __first;
 195   _Distance __parent = (__len - 2)/2;
 196
 197   for (;;) {
 198     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
 199     if (__parent == 0) return;
 200     __parent--;
 201   }
 202 }
 203
 204 template <class _RandomAccessIterator>
 205 void
 206 make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 207 {
 208   __make_heap(__first, __last,
 209               _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
 210 }
 211
 212 template <class _RandomAccessIterator, class _Compare,
 213           class _Tp, class _Distance>
 214 _STLP_INLINE_LOOP
 215 void
 216 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 217             _Compare __comp, _Tp*, _Distance*)
 218 {
 219   if (__last - __first < 2) return;
 220   _Distance __len = __last - __first;
 221   _Distance __parent = (__len - 2)/2;
 222
 223   for (;;) {
 224     __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
 225                   __comp);
 226     if (__parent == 0) return;
 227     __parent--;
 228   }
 229 }
 230
 231 template <class _RandomAccessIterator, class _Compare>
 232 void
 233 make_heap(_RandomAccessIterator __first,
 234           _RandomAccessIterator __last, _Compare __comp)
 235 {
 236   __make_heap(__first, __last, __comp,
 237               _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
 238 }
 239
 240 _STLP_END_NAMESPACE
 241
 242 #endif /*  _STLP_HEAP_C */
 243
 244 // Local Variables:
 245 // mode:C++
 246 // End: