libstdc++/stl/stl_numeric.h

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Permission to use, copy, modify, distribute and sell this software
   7  * and its documentation for any purpose is hereby granted without fee,
   8  * provided that the above copyright notice appear in all copies and
   9  * that both that copyright notice and this permission notice appear
  10  * in supporting documentation.  Hewlett-Packard Company makes no
  11  * representations about the suitability of this software for any
  12  * purpose.  It is provided "as is" without express or implied warranty.
  13  *
  14  *
  15  * Copyright (c) 1996,1997
  16  * Silicon Graphics Computer Systems, Inc.
  17  *
  18  * Permission to use, copy, modify, distribute and sell this software
  19  * and its documentation for any purpose is hereby granted without fee,
  20  * provided that the above copyright notice appear in all copies and
  21  * that both that copyright notice and this permission notice appear
  22  * in supporting documentation.  Silicon Graphics makes no
  23  * representations about the suitability of this software for any
  24  * purpose.  It is provided "as is" without express or implied warranty.
  25  */
  26
  27 /* NOTE: This is an internal header file, included by other STL headers.
  28  *   You should not attempt to use it directly.
  29  */
  30
  31
  32 #ifndef __SGI_STL_INTERNAL_NUMERIC_H
  33 #define __SGI_STL_INTERNAL_NUMERIC_H
  34
  35 __STL_BEGIN_NAMESPACE
  36
  37 template <class _InputIterator, class _Tp>
  38 _Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
  39 {
  40   for ( ; __first != __last; ++__first)
  41     __init = __init + *__first;
  42   return __init;
  43 }
  44
  45 template <class _InputIterator, class _Tp, class _BinaryOperation>
  46 _Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
  47                _BinaryOperation __binary_op)
  48 {
  49   for ( ; __first != __last; ++__first)
  50     __init = __binary_op(__init, *__first);
  51   return __init;
  52 }
  53
  54 template <class _InputIterator1, class _InputIterator2, class _Tp>
  55 _Tp inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
  56                   _InputIterator2 __first2, _Tp __init)
  57 {
  58   for ( ; __first1 != __last1; ++__first1, ++__first2)
  59     __init = __init + (*__first1 * *__first2);
  60   return __init;
  61 }
  62
  63 template <class _InputIterator1, class _InputIterator2, class _Tp,
  64           class _BinaryOperation1, class _BinaryOperation2>
  65 _Tp inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
  66                   _InputIterator2 __first2, _Tp __init,
  67                   _BinaryOperation1 __binary_op1,
  68                   _BinaryOperation2 __binary_op2)
  69 {
  70   for ( ; __first1 != __last1; ++__first1, ++__first2)
  71     __init = __binary_op1(__init, __binary_op2(*__first1, *__first2));
  72   return __init;
  73 }
  74
  75 template <class _InputIterator, class _OutputIterator, class _Tp>
  76 _OutputIterator
  77 __partial_sum(_InputIterator __first, _InputIterator __last,
  78               _OutputIterator __result, _Tp*)
  79 {
  80   _Tp __value = *__first;
  81   while (++__first != __last) {
  82     __value = __value + *__first;
  83     *++__result = __value;
  84   }
  85   return ++__result;
  86 }
  87
  88 template <class _InputIterator, class _OutputIterator>
  89 _OutputIterator
  90 partial_sum(_InputIterator __first, _InputIterator __last,
  91             _OutputIterator __result)
  92 {
  93   if (__first == __last) return __result;
  94   *__result = *__first;
  95   return __partial_sum(__first, __last, __result, __VALUE_TYPE(__first));
  96 }
  97
  98 template <class _InputIterator, class _OutputIterator, class _Tp,
  99           class _BinaryOperation>
 100 _OutputIterator
 101 __partial_sum(_InputIterator __first, _InputIterator __last,
 102               _OutputIterator __result, _Tp*, _BinaryOperation __binary_op)
 103 {
 104   _Tp __value = *__first;
 105   while (++__first != __last) {
 106     __value = __binary_op(__value, *__first);
 107     *++__result = __value;
 108   }
 109   return ++__result;
 110 }
 111
 112 template <class _InputIterator, class _OutputIterator, class _BinaryOperation>
 113 _OutputIterator
 114 partial_sum(_InputIterator __first, _InputIterator __last,
 115             _OutputIterator __result, _BinaryOperation __binary_op)
 116 {
 117   if (__first == __last) return __result;
 118   *__result = *__first;
 119   return __partial_sum(__first, __last, __result, __VALUE_TYPE(__first),
 120                        __binary_op);
 121 }
 122
 123 template <class _InputIterator, class _OutputIterator, class _Tp>
 124 _OutputIterator
 125 __adjacent_difference(_InputIterator __first, _InputIterator __last,
 126                       _OutputIterator __result, _Tp*)
 127 {
 128   _Tp __value = *__first;
 129   while (++__first != __last) {
 130     _Tp __tmp = *__first;
 131     *++__result = __tmp - __value;
 132     __value = __tmp;
 133   }
 134   return ++__result;
 135 }
 136
 137 template <class _InputIterator, class _OutputIterator>
 138 _OutputIterator
 139 adjacent_difference(_InputIterator __first,
 140                     _InputIterator __last, _OutputIterator __result)
 141 {
 142   if (__first == __last) return __result;
 143   *__result = *__first;
 144   return __adjacent_difference(__first, __last, __result,
 145                                __VALUE_TYPE(__first));
 146 }
 147
 148 template <class _InputIterator, class _OutputIterator, class _Tp,
 149           class _BinaryOperation>
 150 _OutputIterator
 151 __adjacent_difference(_InputIterator __first, _InputIterator __last,
 152                       _OutputIterator __result, _Tp*,
 153                       _BinaryOperation __binary_op) {
 154   _Tp __value = *__first;
 155   while (++__first != __last) {
 156     _Tp __tmp = *__first;
 157     *++__result = __binary_op(__tmp, __value);
 158     __value = __tmp;
 159   }
 160   return ++__result;
 161 }
 162
 163 template <class _InputIterator, class _OutputIterator, class _BinaryOperation>
 164 _OutputIterator
 165 adjacent_difference(_InputIterator __first, _InputIterator __last,
 166                     _OutputIterator __result, _BinaryOperation __binary_op)
 167 {
 168   if (__first == __last) return __result;
 169   *__result = *__first;
 170   return __adjacent_difference(__first, __last, __result,
 171                                __VALUE_TYPE(__first),
 172                                __binary_op);
 173 }
 174
 175 // Returns __x ** __n, where __n >= 0.  _Note that "multiplication"
 176 // is required to be associative, but not necessarily commutative.
 177
 178
 179 template <class _Tp, class _Integer, class _MonoidOperation>
 180 _Tp __power(_Tp __x, _Integer __n, _MonoidOperation __opr)
 181 {
 182   if (__n == 0)
 183     return identity_element(__opr);
 184   else {
 185     while ((__n & 1) == 0) {
 186       __n >>= 1;
 187       __x = __opr(__x, __x);
 188     }
 189
 190     _Tp __result = __x;
 191     __n >>= 1;
 192     while (__n != 0) {
 193       __x = __opr(__x, __x);
 194       if ((__n & 1) != 0)
 195         __result = __opr(__result, __x);
 196       __n >>= 1;
 197     }
 198     return __result;
 199   }
 200 }
 201
 202 template <class _Tp, class _Integer>
 203 inline _Tp __power(_Tp __x, _Integer __n)
 204 {
 205   return __power(__x, __n, multiplies<_Tp>());
 206 }
 207
 208 // Alias for the internal name __power.  Note that power is an extension,
 209 // not part of the C++ standard.
 210
 211 template <class _Tp, class _Integer, class _MonoidOperation>
 212 inline _Tp power(_Tp __x, _Integer __n, _MonoidOperation __opr)
 213 {
 214   return __power(__x, __n, __opr);
 215 }
 216
 217 template <class _Tp, class _Integer>
 218 inline _Tp power(_Tp __x, _Integer __n)
 219 {
 220   return __power(__x, __n);
 221 }
 222
 223 // iota is not part of the C++ standard.  It is an extension.
 224
 225 template <class _ForwardIterator, class _Tp>
 226 void
 227 iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
 228 {
 229   while (__first != __last)
 230     *__first++ = __value++;
 231 }
 232
 233 __STL_END_NAMESPACE
 234
 235 #endif /* __SGI_STL_INTERNAL_NUMERIC_H */
 236
 237 // Local Variables:
 238 // mode:C++
 239 // End: