1.1 --- a/epoc32/include/stdapis/stlport/stl/_heap.c Tue Mar 16 16:12:26 2010 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,242 +0,0 @@
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: