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
39template <class _RandomAccessIterator, class _Distance, class _Tp>
40_STLP_INLINE_LOOP
41void
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
54template <class _RandomAccessIterator, class _Distance, class _Tp>
55inline 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
63template <class _RandomAccessIterator>
64void
65push_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
72template <class _RandomAccessIterator, class _Distance, class _Tp,
73          class _Compare>
74_STLP_INLINE_LOOP
75void
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
89template <class _RandomAccessIterator, class _Compare,
90          class _Distance, class _Tp>
91inline 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
100template <class _RandomAccessIterator, class _Compare>
101void
102push_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
109template <class _RandomAccessIterator, class _Distance, class _Tp>
110void
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
130template <class _RandomAccessIterator, class _Tp>
131inline 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
137template <class _RandomAccessIterator>
138void pop_heap(_RandomAccessIterator __first,
139        _RandomAccessIterator __last) {
140  __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
141}
142
143template <class _RandomAccessIterator, class _Distance,
144          class _Tp, class _Compare>
145void
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
169template <class _RandomAccessIterator, class _Tp, class _Compare>
170inline 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
179template <class _RandomAccessIterator, class _Compare>
180void
181pop_heap(_RandomAccessIterator __first,
182         _RandomAccessIterator __last, _Compare __comp)
183{
184    __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator), __comp);
185}
186
187template <class _RandomAccessIterator, class _Tp, class _Distance>
188_STLP_INLINE_LOOP
189void
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
204template <class _RandomAccessIterator>
205void
206make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
207{
208  __make_heap(__first, __last,
209              _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
210}
211
212template <class _RandomAccessIterator, class _Compare,
213          class _Tp, class _Distance>
214_STLP_INLINE_LOOP
215void
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
231template <class _RandomAccessIterator, class _Compare>
232void
233make_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