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
41template <class _RandomAccessIterator, class _Distance, class _Tp>
42void
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
55template <class _RandomAccessIterator, class _Distance, class _Tp>
56inline 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
64template <class _RandomAccessIterator>
65inline void
66push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
67{
68  __push_heap_aux(__first, __last,
69                  __DISTANCE_TYPE(__first), __VALUE_TYPE(__first));
70}
71
72template <class _RandomAccessIterator, class _Distance, class _Tp,
73          class _Compare>
74void
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
87template <class _RandomAccessIterator, class _Compare,
88          class _Distance, class _Tp>
89inline 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
98template <class _RandomAccessIterator, class _Compare>
99inline void
100push_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
107template <class _RandomAccessIterator, class _Distance, class _Tp>
108void
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
128template <class _RandomAccessIterator, class _Tp, class _Distance>
129inline 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
137template <class _RandomAccessIterator, class _Tp>
138inline 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
146template <class _RandomAccessIterator>
147inline void pop_heap(_RandomAccessIterator __first,
148                     _RandomAccessIterator __last)
149{
150  __pop_heap_aux(__first, __last, __VALUE_TYPE(__first));
151}
152
153template <class _RandomAccessIterator, class _Distance,
154          class _Tp, class _Compare>
155void
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
175template <class _RandomAccessIterator, class _Tp, class _Compare,
176          class _Distance>
177inline 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
187template <class _RandomAccessIterator, class _Tp, class _Compare>
188inline 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
196template <class _RandomAccessIterator, class _Compare>
197inline void
198pop_heap(_RandomAccessIterator __first,
199         _RandomAccessIterator __last, _Compare __comp)
200{
201    __pop_heap_aux(__first, __last, __VALUE_TYPE(__first), __comp);
202}
203
204template <class _RandomAccessIterator, class _Tp, class _Distance>
205void
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
220template <class _RandomAccessIterator>
221inline void
222make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
223{
224  __make_heap(__first, __last,
225              __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
226}
227
228template <class _RandomAccessIterator, class _Compare,
229          class _Tp, class _Distance>
230void
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
246template <class _RandomAccessIterator, class _Compare>
247inline void
248make_heap(_RandomAccessIterator __first,
249          _RandomAccessIterator __last, _Compare __comp)
250{
251  __make_heap(__first, __last, __comp,
252              __VALUE_TYPE(__first), __DISTANCE_TYPE(__first));
253}
254
255template <class _RandomAccessIterator>
256void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
257{
258  while (__last - __first > 1)
259    pop_heap(__first, __last--);
260}
261
262template <class _RandomAccessIterator, class _Compare>
263void
264sort_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:
282