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
__push_heap(_RandomAccessIterator __first,_Distance __holeIndex,_Distance __topIndex,_Tp __val)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
__push_heap_aux(_RandomAccessIterator __first,_RandomAccessIterator __last,_Distance *,_Tp *)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
push_heap(_RandomAccessIterator __first,_RandomAccessIterator __last)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
__push_heap(_RandomAccessIterator __first,_Distance __holeIndex,_Distance __topIndex,_Tp __val,_Compare __comp)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
__push_heap_aux(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp,_Distance *,_Tp *)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
push_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)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
__adjust_heap(_RandomAccessIterator __first,_Distance __holeIndex,_Distance __len,_Tp __val)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
__pop_heap_aux(_RandomAccessIterator __first,_RandomAccessIterator __last,_Tp *)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>
pop_heap(_RandomAccessIterator __first,_RandomAccessIterator __last)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
__adjust_heap(_RandomAccessIterator __first,_Distance __holeIndex,_Distance __len,_Tp __val,_Compare __comp)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
__pop_heap_aux(_RandomAccessIterator __first,_RandomAccessIterator __last,_Tp *,_Compare __comp)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
pop_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)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
__make_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_Tp *,_Distance *)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
make_heap(_RandomAccessIterator __first,_RandomAccessIterator __last)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
__make_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp,_Tp *,_Distance *)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
make_heap(_RandomAccessIterator __first,_RandomAccessIterator __last,_Compare __comp)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