← Back to branch summary

~ubuntu-branches/ubuntu/hardy/libterralib/hardy

« back to all changes in this revision

Viewing changes to src/STLport/stl/_heap.c

  • Committer: Bazaar Package Importer
  • Author(s): Daniel T Chen
  • Date: 2005-11-25 22:32:59 UTC
  • Revision ID: james.westby@ubuntu.com-20051125223259-3zubal8ux4ki4fjg
Tags: upstream-3.0.3b2
Import upstream version 3.0.3b2

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/STLport/stl/_heap.c
 
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
    *(__first + __holeIndex) = *(__first + __parent);
 
82
    __holeIndex = __parent;
 
83
    __parent = (__holeIndex - 1) / 2;
 
84
  }
 
85
  *(__first + __holeIndex) = __val;
 
86
}
 
87
 
 
88
template <class _RandomAccessIterator, class _Compare,
 
89
          class _Distance, class _Tp>
 
90
inline void 
 
91
__push_heap_aux(_RandomAccessIterator __first,
 
92
                _RandomAccessIterator __last, _Compare __comp,
 
93
                _Distance*, _Tp*) 
 
94
{
 
95
  __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0), 
 
96
              _Tp(*(__last - 1)), __comp);
 
97
}
 
98
 
 
99
template <class _RandomAccessIterator, class _Compare>
 
100
void 
 
101
push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 
102
          _Compare __comp) 
 
103
{
 
104
  __push_heap_aux(__first, __last, __comp,
 
105
                  _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
 
106
}
 
107
 
 
108
template <class _RandomAccessIterator, class _Distance, class _Tp>
 
109
void 
 
110
__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 
111
              _Distance __len, _Tp __val) {
 
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, __val);
 
126
}
 
127
 
 
128
 
 
129
template <class _RandomAccessIterator, class _Tp>
 
130
inline void 
 
131
__pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*) {
 
132
  __pop_heap(__first, __last - 1, __last - 1, 
 
133
             _Tp(*(__last - 1)), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
 
134
}
 
135
 
 
136
template <class _RandomAccessIterator>
 
137
void pop_heap(_RandomAccessIterator __first, 
 
138
              _RandomAccessIterator __last) {
 
139
  __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
 
140
}
 
141
 
 
142
template <class _RandomAccessIterator, class _Distance,
 
143
          class _Tp, class _Compare>
 
144
void
 
145
__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
 
146
              _Distance __len, _Tp __val, _Compare __comp)
 
147
{
 
148
  _Distance __topIndex = __holeIndex;
 
149
  _Distance __secondChild = 2 * __holeIndex + 2;
 
150
  while (__secondChild < __len) {
 
151
    if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
 
152
      __secondChild--;
 
153
    *(__first + __holeIndex) = *(__first + __secondChild);
 
154
    __holeIndex = __secondChild;
 
155
    __secondChild = 2 * (__secondChild + 1);
 
156
  }
 
157
  if (__secondChild == __len) {
 
158
    *(__first + __holeIndex) = *(__first + (__secondChild - 1));
 
159
    __holeIndex = __secondChild - 1;
 
160
  }
 
161
  __push_heap(__first, __holeIndex, __topIndex, __val, __comp);
 
162
}
 
163
 
 
164
 
 
165
template <class _RandomAccessIterator, class _Tp, class _Compare>
 
166
inline void 
 
167
__pop_heap_aux(_RandomAccessIterator __first,
 
168
               _RandomAccessIterator __last, _Tp*, _Compare __comp)
 
169
{
 
170
  __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
 
171
             _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
 
172
}
 
173
 
 
174
 
 
175
template <class _RandomAccessIterator, class _Compare>
 
176
void 
 
177
pop_heap(_RandomAccessIterator __first,
 
178
         _RandomAccessIterator __last, _Compare __comp)
 
179
{
 
180
    __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator), __comp);
 
181
}
 
182
 
 
183
template <class _RandomAccessIterator, class _Tp, class _Distance>
 
184
_STLP_INLINE_LOOP
 
185
void 
 
186
__make_heap(_RandomAccessIterator __first,
 
187
            _RandomAccessIterator __last, _Tp*, _Distance*)
 
188
{
 
189
  if (__last - __first < 2) return;
 
190
  _Distance __len = __last - __first;
 
191
  _Distance __parent = (__len - 2)/2;
 
192
    
 
193
  while (true) {
 
194
    __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
 
195
    if (__parent == 0) return;
 
196
    __parent--;
 
197
  }
 
198
}
 
199
 
 
200
template <class _RandomAccessIterator>
 
201
void 
 
202
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 
203
{
 
204
  __make_heap(__first, __last,
 
205
              _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
 
206
}
 
207
 
 
208
template <class _RandomAccessIterator, class _Compare,
 
209
          class _Tp, class _Distance>
 
210
_STLP_INLINE_LOOP
 
211
void
 
212
__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
 
213
            _Compare __comp, _Tp*, _Distance*)
 
214
{
 
215
  if (__last - __first < 2) return;
 
216
  _Distance __len = __last - __first;
 
217
  _Distance __parent = (__len - 2)/2;
 
218
    
 
219
  while (true) {
 
220
    __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
 
221
                  __comp);
 
222
    if (__parent == 0) return;
 
223
    __parent--;
 
224
  }
 
225
}
 
226
 
 
227
template <class _RandomAccessIterator, class _Compare>
 
228
void 
 
229
make_heap(_RandomAccessIterator __first, 
 
230
          _RandomAccessIterator __last, _Compare __comp)
 
231
{
 
232
  __make_heap(__first, __last, __comp,
 
233
              _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
 
234
}
 
235
 
 
236
_STLP_END_NAMESPACE
 
237
 
 
238
#endif /*  _STLP_HEAP_C */
 
239
 
 
240
// Local Variables:
 
241
// mode:C++
 
242
// End: