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