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: 247
