libstdc++-v3/include/bits/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 _CPP_BITS_STL_NUMERIC_H
  33 #define _CPP_BITS_STL_NUMERIC_H 1
  34
  35 namespace std
  36 {
  37
  38 template <class _InputIterator, class _Tp>
  39 _Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
  40 {
  41   // concept requirements
  42   glibcpp_function_requires(InputIteratorConcept<_InputIterator>);
  43
  44   for ( ; __first != __last; ++__first)
  45     __init = __init + *__first;
  46   return __init;
  47 }
  48
  49 template <class _InputIterator, class _Tp, class _BinaryOperation>
  50 _Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
  51               _BinaryOperation __binary_op)
  52 {
  53   // concept requirements
  54   glibcpp_function_requires(InputIteratorConcept<_InputIterator>);
  55
  56   for ( ; __first != __last; ++__first)
  57     __init = __binary_op(__init, *__first);
  58   return __init;
  59 }
  60
  61 template <class _InputIterator1, class _InputIterator2, class _Tp>
  62 _Tp inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
  63                  _InputIterator2 __first2, _Tp __init)
  64 {
  65   // concept requirements
  66   glibcpp_function_requires(InputIteratorConcept<_InputIterator1>);
  67   glibcpp_function_requires(InputIteratorConcept<_InputIterator2>);
  68
  69   for ( ; __first1 != __last1; ++__first1, ++__first2)
  70     __init = __init + (*__first1 * *__first2);
  71   return __init;
  72 }
  73
  74 template <class _InputIterator1, class _InputIterator2, class _Tp,
  75           class _BinaryOperation1, class _BinaryOperation2>
  76 _Tp inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
  77                  _InputIterator2 __first2, _Tp __init,
  78                  _BinaryOperation1 __binary_op1,
  79                  _BinaryOperation2 __binary_op2)
  80 {
  81   // concept requirements
  82   glibcpp_function_requires(InputIteratorConcept<_InputIterator1>);
  83   glibcpp_function_requires(InputIteratorConcept<_InputIterator2>);
  84
  85   for ( ; __first1 != __last1; ++__first1, ++__first2)
  86     __init = __binary_op1(__init, __binary_op2(*__first1, *__first2));
  87   return __init;
  88 }
  89
  90 template <class _InputIterator, class _OutputIterator, class _Tp>
  91 _OutputIterator
  92 __partial_sum(_InputIterator __first, _InputIterator __last,
  93               _OutputIterator __result, _Tp*)
  94 {
  95   _Tp __value = *__first;
  96   while (++__first != __last) {
  97     __value = __value + *__first;
  98     *++__result = __value;
  99   }
 100   return ++__result;
 101 }
 102
 103 template <class _InputIterator, class _OutputIterator>
 104 _OutputIterator
 105 partial_sum(_InputIterator __first, _InputIterator __last,
 106             _OutputIterator __result)
 107 {
 108   // concept requirements
 109   glibcpp_function_requires(InputIteratorConcept<_InputIterator>);
 110   glibcpp_function_requires(OutputIteratorConcept<_OutputIterator,
 111         typename iterator_traits<_InputIterator>::value_type>);
 112
 113   if (__first == __last) return __result;
 114   *__result = *__first;
 115   return __partial_sum(__first, __last, __result, __value_type(__first));
 116 }
 117
 118 template <class _InputIterator, class _OutputIterator, class _Tp,
 119           class _BinaryOperation>
 120 _OutputIterator
 121 __partial_sum(_InputIterator __first, _InputIterator __last,
 122               _OutputIterator __result, _Tp*, _BinaryOperation __binary_op)
 123 {
 124   _Tp __value = *__first;
 125   while (++__first != __last) {
 126     __value = __binary_op(__value, *__first);
 127     *++__result = __value;
 128   }
 129   return ++__result;
 130 }
 131
 132 template <class _InputIterator, class _OutputIterator, class _BinaryOperation>
 133 _OutputIterator
 134 partial_sum(_InputIterator __first, _InputIterator __last,
 135             _OutputIterator __result, _BinaryOperation __binary_op)
 136 {
 137   // concept requirements
 138   glibcpp_function_requires(InputIteratorConcept<_InputIterator>);
 139   glibcpp_function_requires(OutputIteratorConcept<_OutputIterator,
 140         typename iterator_traits<_InputIterator>::value_type>);
 141
 142   if (__first == __last) return __result;
 143   *__result = *__first;
 144   return __partial_sum(__first, __last, __result, __value_type(__first),
 145                        __binary_op);
 146 }
 147
 148 template <class _InputIterator, class _OutputIterator, class _Tp>
 149 _OutputIterator
 150 __adjacent_difference(_InputIterator __first, _InputIterator __last,
 151                       _OutputIterator __result, _Tp*)
 152 {
 153   _Tp __value = *__first;
 154   while (++__first != __last) {
 155     _Tp __tmp = *__first;
 156     *++__result = __tmp - __value;
 157     __value = __tmp;
 158   }
 159   return ++__result;
 160 }
 161
 162 template <class _InputIterator, class _OutputIterator>
 163 _OutputIterator
 164 adjacent_difference(_InputIterator __first,
 165                     _InputIterator __last, _OutputIterator __result)
 166 {
 167   // concept requirements
 168   glibcpp_function_requires(InputIteratorConcept<_InputIterator>);
 169   glibcpp_function_requires(OutputIteratorConcept<_OutputIterator,
 170         typename iterator_traits<_InputIterator>::value_type>);
 171
 172   if (__first == __last) return __result;
 173   *__result = *__first;
 174   return __adjacent_difference(__first, __last, __result,
 175                                __value_type(__first));
 176 }
 177
 178 template <class _InputIterator, class _OutputIterator, class _Tp,
 179           class _BinaryOperation>
 180 _OutputIterator
 181 __adjacent_difference(_InputIterator __first, _InputIterator __last,
 182                       _OutputIterator __result, _Tp*,
 183                       _BinaryOperation __binary_op) {
 184   _Tp __value = *__first;
 185   while (++__first != __last) {
 186     _Tp __tmp = *__first;
 187     *++__result = __binary_op(__tmp, __value);
 188     __value = __tmp;
 189   }
 190   return ++__result;
 191 }
 192
 193 template <class _InputIterator, class _OutputIterator, class _BinaryOperation>
 194 _OutputIterator
 195 adjacent_difference(_InputIterator __first, _InputIterator __last,
 196                     _OutputIterator __result, _BinaryOperation __binary_op)
 197 {
 198   // concept requirements
 199   glibcpp_function_requires(InputIteratorConcept<_InputIterator>);
 200   glibcpp_function_requires(OutputIteratorConcept<_OutputIterator,
 201         typename iterator_traits<_InputIterator>::value_type>);
 202
 203   if (__first == __last) return __result;
 204   *__result = *__first;
 205   return __adjacent_difference(__first, __last, __result,
 206                                __value_type(__first),
 207                                __binary_op);
 208 }
 209
 210 // Returns __x ** __n, where __n >= 0.  _Note that "multiplication"
 211 // is required to be associative, but not necessarily commutative.
 212
 213
 214 template <class _Tp, class _Integer, class _MonoidOperation>
 215 _Tp __power(_Tp __x, _Integer __n, _MonoidOperation __monoid_op)
 216 {
 217   if (__n == 0)
 218     return identity_element(__monoid_op);
 219   else {
 220     while ((__n & 1) == 0) {
 221       __n >>= 1;
 222       __x = __monoid_op(__x, __x);
 223     }
 224
 225     _Tp __result = __x;
 226     __n >>= 1;
 227     while (__n != 0) {
 228       __x = __monoid_op(__x, __x);
 229       if ((__n & 1) != 0)
 230         __result = __monoid_op(__result, __x);
 231       __n >>= 1;
 232     }
 233     return __result;
 234   }
 235 }
 236
 237 template <class _Tp, class _Integer>
 238 inline _Tp __power(_Tp __x, _Integer __n)
 239 {
 240   return __power(__x, __n, multiplies<_Tp>());
 241 }
 242
 243 // Alias for the internal name __power.  Note that power is an extension,
 244 // not part of the C++ standard.
 245
 246 template <class _Tp, class _Integer, class _MonoidOperation>
 247 inline _Tp power(_Tp __x, _Integer __n, _MonoidOperation __monoid_op)
 248 {
 249   return __power(__x, __n, __monoid_op);
 250 }
 251
 252 template <class _Tp, class _Integer>
 253 inline _Tp power(_Tp __x, _Integer __n)
 254 {
 255   return __power(__x, __n);
 256 }
 257
 258 // iota is not part of the C++ standard.  It is an extension.
 259
 260 template <class _ForwardIter, class _Tp>
 261 void
 262 iota(_ForwardIter __first, _ForwardIter __last, _Tp __value)
 263 {
 264   // concept requirements
 265   glibcpp_function_requires(Mutable_ForwardIteratorConcept<_ForwardIter>);
 266   glibcpp_function_requires(ConvertibleConcept<_Tp,
 267         typename iterator_traits<_ForwardIter>::value_type>);
 268
 269   while (__first != __last)
 270     *__first++ = __value++;
 271 }
 272
 273 } // namespace std
 274
 275 #endif /* _CPP_BITS_STL_NUMERIC_H */
 276
 277 // Local Variables:
 278 // mode:C++
 279 // End: