epoc32/include/stdapis/stlport/stl/_heap.c
branchSymbian2
changeset 2 2fe1408b6811
parent 0 061f57f2323e
     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: