1.1 --- a/epoc32/include/stdapis/stlport/stl/_heap.c Tue Nov 24 13:55:44 2009 +0000
1.2 +++ b/epoc32/include/stdapis/stlport/stl/_heap.c Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -1,1 +1,242 @@
1.4 -_heap.c
1.5 +/*
1.6 + *
1.7 + *
1.8 + * Copyright (c) 1994
1.9 + * Hewlett-Packard Company
1.10 + *
1.11 + * Copyright (c) 1996,1997
1.12 + * Silicon Graphics Computer Systems, Inc.
1.13 + *
1.14 + * Copyright (c) 1997
1.15 + * Moscow Center for SPARC Technology
1.16 + *
1.17 + * Copyright (c) 1999
1.18 + * Boris Fomitchev
1.19 + *
1.20 + * This material is provided "as is", with absolutely no warranty expressed
1.21 + * or implied. Any use is at your own risk.
1.22 + *
1.23 + * Permission to use or copy this software for any purpose is hereby granted
1.24 + * without fee, provided the above notices are retained on all copies.
1.25 + * Permission to modify the code and to distribute modified code is granted,
1.26 + * provided the above notices are retained, and a notice that the code was
1.27 + * modified is included with the above copyright notice.
1.28 + *
1.29 + */
1.30 +#ifndef _STLP_HEAP_C
1.31 +#define _STLP_HEAP_C
1.32 +
1.33 +#ifndef _STLP_INTERNAL_HEAP_H
1.34 +# include <stl/_heap.h>
1.35 +#endif
1.36 +
1.37 +#ifndef _STLP_INTERNAL_ITERATOR_BASE_H
1.38 +# include <stl/_iterator_base.h>
1.39 +#endif
1.40 +
1.41 +_STLP_BEGIN_NAMESPACE
1.42 +
1.43 +template <class _RandomAccessIterator, class _Distance, class _Tp>
1.44 +_STLP_INLINE_LOOP
1.45 +void
1.46 +__push_heap(_RandomAccessIterator __first,
1.47 + _Distance __holeIndex, _Distance __topIndex, _Tp __val)
1.48 +{
1.49 + _Distance __parent = (__holeIndex - 1) / 2;
1.50 + while (__holeIndex > __topIndex && *(__first + __parent) < __val) {
1.51 + *(__first + __holeIndex) = *(__first + __parent);
1.52 + __holeIndex = __parent;
1.53 + __parent = (__holeIndex - 1) / 2;
1.54 + }
1.55 + *(__first + __holeIndex) = __val;
1.56 +}
1.57 +
1.58 +template <class _RandomAccessIterator, class _Distance, class _Tp>
1.59 +inline void
1.60 +__push_heap_aux(_RandomAccessIterator __first,
1.61 + _RandomAccessIterator __last, _Distance*, _Tp*)
1.62 +{
1.63 + __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
1.64 + _Tp(*(__last - 1)));
1.65 +}
1.66 +
1.67 +template <class _RandomAccessIterator>
1.68 +void
1.69 +push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
1.70 +{
1.71 + __push_heap_aux(__first, __last,
1.72 + _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
1.73 +}
1.74 +
1.75 +
1.76 +template <class _RandomAccessIterator, class _Distance, class _Tp,
1.77 + class _Compare>
1.78 +_STLP_INLINE_LOOP
1.79 +void
1.80 +__push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
1.81 + _Distance __topIndex, _Tp __val, _Compare __comp)
1.82 +{
1.83 + _Distance __parent = (__holeIndex - 1) / 2;
1.84 + while (__holeIndex > __topIndex && __comp(*(__first + __parent), __val)) {
1.85 + *(__first + __holeIndex) = *(__first + __parent);
1.86 + __holeIndex = __parent;
1.87 + __parent = (__holeIndex - 1) / 2;
1.88 + }
1.89 + *(__first + __holeIndex) = __val;
1.90 +}
1.91 +
1.92 +template <class _RandomAccessIterator, class _Compare,
1.93 + class _Distance, class _Tp>
1.94 +inline void
1.95 +__push_heap_aux(_RandomAccessIterator __first,
1.96 + _RandomAccessIterator __last, _Compare __comp,
1.97 + _Distance*, _Tp*)
1.98 +{
1.99 + __push_heap(__first, _Distance((__last - __first) - 1), _Distance(0),
1.100 + _Tp(*(__last - 1)), __comp);
1.101 +}
1.102 +
1.103 +template <class _RandomAccessIterator, class _Compare>
1.104 +void
1.105 +push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
1.106 + _Compare __comp)
1.107 +{
1.108 + __push_heap_aux(__first, __last, __comp,
1.109 + _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator), _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
1.110 +}
1.111 +
1.112 +template <class _RandomAccessIterator, class _Distance, class _Tp>
1.113 +void
1.114 +__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
1.115 + _Distance __len, _Tp __val) {
1.116 + _Distance __topIndex = __holeIndex;
1.117 + _Distance __secondChild = 2 * __holeIndex + 2;
1.118 + while (__secondChild < __len) {
1.119 + if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
1.120 + __secondChild--;
1.121 + *(__first + __holeIndex) = *(__first + __secondChild);
1.122 + __holeIndex = __secondChild;
1.123 + __secondChild = 2 * (__secondChild + 1);
1.124 + }
1.125 + if (__secondChild == __len) {
1.126 + *(__first + __holeIndex) = *(__first + (__secondChild - 1));
1.127 + __holeIndex = __secondChild - 1;
1.128 + }
1.129 + __push_heap(__first, __holeIndex, __topIndex, __val);
1.130 +}
1.131 +
1.132 +
1.133 +template <class _RandomAccessIterator, class _Tp>
1.134 +inline void
1.135 +__pop_heap_aux(_RandomAccessIterator __first, _RandomAccessIterator __last, _Tp*) {
1.136 + __pop_heap(__first, __last - 1, __last - 1,
1.137 + _Tp(*(__last - 1)), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
1.138 +}
1.139 +
1.140 +template <class _RandomAccessIterator>
1.141 +void pop_heap(_RandomAccessIterator __first,
1.142 + _RandomAccessIterator __last) {
1.143 + __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator));
1.144 +}
1.145 +
1.146 +template <class _RandomAccessIterator, class _Distance,
1.147 + class _Tp, class _Compare>
1.148 +void
1.149 +__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
1.150 + _Distance __len, _Tp __val, _Compare __comp)
1.151 +{
1.152 + _Distance __topIndex = __holeIndex;
1.153 + _Distance __secondChild = 2 * __holeIndex + 2;
1.154 + while (__secondChild < __len) {
1.155 + if (__comp(*(__first + __secondChild), *(__first + (__secondChild - 1))))
1.156 + __secondChild--;
1.157 + *(__first + __holeIndex) = *(__first + __secondChild);
1.158 + __holeIndex = __secondChild;
1.159 + __secondChild = 2 * (__secondChild + 1);
1.160 + }
1.161 + if (__secondChild == __len) {
1.162 + *(__first + __holeIndex) = *(__first + (__secondChild - 1));
1.163 + __holeIndex = __secondChild - 1;
1.164 + }
1.165 + __push_heap(__first, __holeIndex, __topIndex, __val, __comp);
1.166 +}
1.167 +
1.168 +
1.169 +template <class _RandomAccessIterator, class _Tp, class _Compare>
1.170 +inline void
1.171 +__pop_heap_aux(_RandomAccessIterator __first,
1.172 + _RandomAccessIterator __last, _Tp*, _Compare __comp)
1.173 +{
1.174 + __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
1.175 + _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
1.176 +}
1.177 +
1.178 +
1.179 +template <class _RandomAccessIterator, class _Compare>
1.180 +void
1.181 +pop_heap(_RandomAccessIterator __first,
1.182 + _RandomAccessIterator __last, _Compare __comp)
1.183 +{
1.184 + __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator), __comp);
1.185 +}
1.186 +
1.187 +template <class _RandomAccessIterator, class _Tp, class _Distance>
1.188 +_STLP_INLINE_LOOP
1.189 +void
1.190 +__make_heap(_RandomAccessIterator __first,
1.191 + _RandomAccessIterator __last, _Tp*, _Distance*)
1.192 +{
1.193 + if (__last - __first < 2) return;
1.194 + _Distance __len = __last - __first;
1.195 + _Distance __parent = (__len - 2)/2;
1.196 +
1.197 + while (true) {
1.198 + __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
1.199 + if (__parent == 0) return;
1.200 + __parent--;
1.201 + }
1.202 +}
1.203 +
1.204 +template <class _RandomAccessIterator>
1.205 +void
1.206 +make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
1.207 +{
1.208 + __make_heap(__first, __last,
1.209 + _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
1.210 +}
1.211 +
1.212 +template <class _RandomAccessIterator, class _Compare,
1.213 + class _Tp, class _Distance>
1.214 +_STLP_INLINE_LOOP
1.215 +void
1.216 +__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
1.217 + _Compare __comp, _Tp*, _Distance*)
1.218 +{
1.219 + if (__last - __first < 2) return;
1.220 + _Distance __len = __last - __first;
1.221 + _Distance __parent = (__len - 2)/2;
1.222 +
1.223 + while (true) {
1.224 + __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
1.225 + __comp);
1.226 + if (__parent == 0) return;
1.227 + __parent--;
1.228 + }
1.229 +}
1.230 +
1.231 +template <class _RandomAccessIterator, class _Compare>
1.232 +void
1.233 +make_heap(_RandomAccessIterator __first,
1.234 + _RandomAccessIterator __last, _Compare __comp)
1.235 +{
1.236 + __make_heap(__first, __last, __comp,
1.237 + _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
1.238 +}
1.239 +
1.240 +_STLP_END_NAMESPACE
1.241 +
1.242 +#endif /* _STLP_HEAP_C */
1.243 +
1.244 +// Local Variables:
1.245 +// mode:C++
1.246 +// End: