5 * Hewlett-Packard Company
7 * Copyright (c) 1996,1997
8 * Silicon Graphics Computer Systems, Inc.
11 * Moscow Center for SPARC Technology
16 * This material is provided "as is", with absolutely no warranty expressed
17 * or implied. Any use is at your own risk.
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.
29 #ifndef _STLP_INTERNAL_HEAP_H
30 # include <stl/_heap.h>
33 #ifndef _STLP_INTERNAL_ITERATOR_BASE_H
34 # include <stl/_iterator_base.h>
39 template <class _RandomAccessIterator
, class _Distance
, class _Tp
>
42 __push_heap(_RandomAccessIterator __first
,
43 _Distance __holeIndex
, _Distance __topIndex
, _Tp __val
)
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;
51 *(__first
+ __holeIndex
) = __val
;
54 template <class _RandomAccessIterator
, class _Distance
, class _Tp
>
56 __push_heap_aux(_RandomAccessIterator __first
,
57 _RandomAccessIterator __last
, _Distance
*, _Tp
*)
59 __push_heap(__first
, _Distance((__last
- __first
) - 1), _Distance(0),
63 template <class _RandomAccessIterator
>
65 push_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
67 __push_heap_aux(__first
, __last
,
68 _STLP_DISTANCE_TYPE(__first
, _RandomAccessIterator
), _STLP_VALUE_TYPE(__first
, _RandomAccessIterator
));
72 template <class _RandomAccessIterator
, class _Distance
, class _Tp
,
76 __push_heap(_RandomAccessIterator __first
, _Distance __holeIndex
,
77 _Distance __topIndex
, _Tp __val
, _Compare __comp
)
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;
86 *(__first
+ __holeIndex
) = __val
;
89 template <class _RandomAccessIterator
, class _Compare
,
90 class _Distance
, class _Tp
>
92 __push_heap_aux(_RandomAccessIterator __first
,
93 _RandomAccessIterator __last
, _Compare __comp
,
96 __push_heap(__first
, _Distance((__last
- __first
) - 1), _Distance(0),
97 _Tp(*(__last
- 1)), __comp
);
100 template <class _RandomAccessIterator
, class _Compare
>
102 push_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
105 __push_heap_aux(__first
, __last
, __comp
,
106 _STLP_DISTANCE_TYPE(__first
, _RandomAccessIterator
), _STLP_VALUE_TYPE(__first
, _RandomAccessIterator
));
109 template <class _RandomAccessIterator
, class _Distance
, class _Tp
>
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)))
118 *(__first
+ __holeIndex
) = *(__first
+ __secondChild
);
119 __holeIndex
= __secondChild
;
120 __secondChild
= 2 * (__secondChild
+ 1);
122 if (__secondChild
== __len
) {
123 *(__first
+ __holeIndex
) = *(__first
+ (__secondChild
- 1));
124 __holeIndex
= __secondChild
- 1;
126 __push_heap(__first
, __holeIndex
, __topIndex
, __val
);
130 template <class _RandomAccessIterator
, class _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
));
137 template <class _RandomAccessIterator
>
138 void pop_heap(_RandomAccessIterator __first
,
139 _RandomAccessIterator __last
) {
140 __pop_heap_aux(__first
, __last
, _STLP_VALUE_TYPE(__first
, _RandomAccessIterator
));
143 template <class _RandomAccessIterator
, class _Distance
,
144 class _Tp
, class _Compare
>
146 __adjust_heap(_RandomAccessIterator __first
, _Distance __holeIndex
,
147 _Distance __len
, _Tp __val
, _Compare __comp
)
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
)
157 *(__first
+ __holeIndex
) = *(__first
+ __secondChild
);
158 __holeIndex
= __secondChild
;
159 __secondChild
= 2 * (__secondChild
+ 1);
161 if (__secondChild
== __len
) {
162 *(__first
+ __holeIndex
) = *(__first
+ (__secondChild
- 1));
163 __holeIndex
= __secondChild
- 1;
165 __push_heap(__first
, __holeIndex
, __topIndex
, __val
, __comp
);
169 template <class _RandomAccessIterator
, class _Tp
, class _Compare
>
171 __pop_heap_aux(_RandomAccessIterator __first
,
172 _RandomAccessIterator __last
, _Tp
*, _Compare __comp
)
174 __pop_heap(__first
, __last
- 1, __last
- 1, _Tp(*(__last
- 1)), __comp
,
175 _STLP_DISTANCE_TYPE(__first
, _RandomAccessIterator
));
179 template <class _RandomAccessIterator
, class _Compare
>
181 pop_heap(_RandomAccessIterator __first
,
182 _RandomAccessIterator __last
, _Compare __comp
)
184 __pop_heap_aux(__first
, __last
, _STLP_VALUE_TYPE(__first
, _RandomAccessIterator
), __comp
);
187 template <class _RandomAccessIterator
, class _Tp
, class _Distance
>
190 __make_heap(_RandomAccessIterator __first
,
191 _RandomAccessIterator __last
, _Tp
*, _Distance
*)
193 if (__last
- __first
< 2) return;
194 _Distance __len
= __last
- __first
;
195 _Distance __parent
= (__len
- 2)/2;
198 __adjust_heap(__first
, __parent
, __len
, _Tp(*(__first
+ __parent
)));
199 if (__parent
== 0) return;
204 template <class _RandomAccessIterator
>
206 make_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
)
208 __make_heap(__first
, __last
,
209 _STLP_VALUE_TYPE(__first
, _RandomAccessIterator
), _STLP_DISTANCE_TYPE(__first
, _RandomAccessIterator
));
212 template <class _RandomAccessIterator
, class _Compare
,
213 class _Tp
, class _Distance
>
216 __make_heap(_RandomAccessIterator __first
, _RandomAccessIterator __last
,
217 _Compare __comp
, _Tp
*, _Distance
*)
219 if (__last
- __first
< 2) return;
220 _Distance __len
= __last
- __first
;
221 _Distance __parent
= (__len
- 2)/2;
224 __adjust_heap(__first
, __parent
, __len
, _Tp(*(__first
+ __parent
)),
226 if (__parent
== 0) return;
231 template <class _RandomAccessIterator
, class _Compare
>
233 make_heap(_RandomAccessIterator __first
,
234 _RandomAccessIterator __last
, _Compare __comp
)
236 __make_heap(__first
, __last
, __comp
,
237 _STLP_VALUE_TYPE(__first
, _RandomAccessIterator
), _STLP_DISTANCE_TYPE(__first
, _RandomAccessIterator
));
242 #endif /* _STLP_HEAP_C */