epoc32/include/stdapis/stlport/stl/_heap.c
branchSymbian3
changeset 4 837f303aceeb
     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: