1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/tools/stlport/stl/_heap.c Wed Mar 31 12:33:34 2010 +0100
1.3 @@ -0,0 +1,246 @@
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 + _STLP_VERBOSE_ASSERT(!__comp(__val, *(__first + __parent)), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
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 + _STLP_VERBOSE_ASSERT(!__comp(*(__first + (__secondChild - 1)), *(__first + __secondChild)),
1.157 + _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.158 + __secondChild--;
1.159 + }
1.160 + *(__first + __holeIndex) = *(__first + __secondChild);
1.161 + __holeIndex = __secondChild;
1.162 + __secondChild = 2 * (__secondChild + 1);
1.163 + }
1.164 + if (__secondChild == __len) {
1.165 + *(__first + __holeIndex) = *(__first + (__secondChild - 1));
1.166 + __holeIndex = __secondChild - 1;
1.167 + }
1.168 + __push_heap(__first, __holeIndex, __topIndex, __val, __comp);
1.169 +}
1.170 +
1.171 +
1.172 +template <class _RandomAccessIterator, class _Tp, class _Compare>
1.173 +inline void
1.174 +__pop_heap_aux(_RandomAccessIterator __first,
1.175 + _RandomAccessIterator __last, _Tp*, _Compare __comp)
1.176 +{
1.177 + __pop_heap(__first, __last - 1, __last - 1, _Tp(*(__last - 1)), __comp,
1.178 + _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
1.179 +}
1.180 +
1.181 +
1.182 +template <class _RandomAccessIterator, class _Compare>
1.183 +void
1.184 +pop_heap(_RandomAccessIterator __first,
1.185 + _RandomAccessIterator __last, _Compare __comp)
1.186 +{
1.187 + __pop_heap_aux(__first, __last, _STLP_VALUE_TYPE(__first, _RandomAccessIterator), __comp);
1.188 +}
1.189 +
1.190 +template <class _RandomAccessIterator, class _Tp, class _Distance>
1.191 +_STLP_INLINE_LOOP
1.192 +void
1.193 +__make_heap(_RandomAccessIterator __first,
1.194 + _RandomAccessIterator __last, _Tp*, _Distance*)
1.195 +{
1.196 + if (__last - __first < 2) return;
1.197 + _Distance __len = __last - __first;
1.198 + _Distance __parent = (__len - 2)/2;
1.199 +
1.200 + for (;;) {
1.201 + __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)));
1.202 + if (__parent == 0) return;
1.203 + __parent--;
1.204 + }
1.205 +}
1.206 +
1.207 +template <class _RandomAccessIterator>
1.208 +void
1.209 +make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
1.210 +{
1.211 + __make_heap(__first, __last,
1.212 + _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
1.213 +}
1.214 +
1.215 +template <class _RandomAccessIterator, class _Compare,
1.216 + class _Tp, class _Distance>
1.217 +_STLP_INLINE_LOOP
1.218 +void
1.219 +__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
1.220 + _Compare __comp, _Tp*, _Distance*)
1.221 +{
1.222 + if (__last - __first < 2) return;
1.223 + _Distance __len = __last - __first;
1.224 + _Distance __parent = (__len - 2)/2;
1.225 +
1.226 + for (;;) {
1.227 + __adjust_heap(__first, __parent, __len, _Tp(*(__first + __parent)),
1.228 + __comp);
1.229 + if (__parent == 0) return;
1.230 + __parent--;
1.231 + }
1.232 +}
1.233 +
1.234 +template <class _RandomAccessIterator, class _Compare>
1.235 +void
1.236 +make_heap(_RandomAccessIterator __first,
1.237 + _RandomAccessIterator __last, _Compare __comp)
1.238 +{
1.239 + __make_heap(__first, __last, __comp,
1.240 + _STLP_VALUE_TYPE(__first, _RandomAccessIterator), _STLP_DISTANCE_TYPE(__first, _RandomAccessIterator));
1.241 +}
1.242 +
1.243 +_STLP_END_NAMESPACE
1.244 +
1.245 +#endif /* _STLP_HEAP_C */
1.246 +
1.247 +// Local Variables:
1.248 +// mode:C++
1.249 +// End: