unumeric.h

   1 // This file is part of the ustl library, an STL implementation.
   2 //
   3 // Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net>
   4 // This file is free software, distributed under the MIT License.
   5 //
   6 // unumeric.h
   7 //
   8 //      This file contains numeric algorithm templates.
   9 //
  10
  11 #ifndef UNUMERIC_H_6C99D6F6363832C644A6FFF336E84E18
  12 #define UNUMERIC_H_6C99D6F6363832C644A6FFF336E84E18
  13
  14 namespace ustl {
  15
  16 /// Returns the sum of all elements in [first, last) added to \p init.
  17 /// \ingroup NumericAlgorithms
  18 ///
  19 template <typename InputIterator, typename T>
  20 inline T accumulate (InputIterator first, InputIterator last, T init)
  21 {
  22     while (first < last)
  23         init += *first++;
  24     return (init);
  25 }
  26
  27 /// Returns the sum of all elements in [first, last) via \p op, added to \p init.
  28 /// \ingroup NumericAlgorithms
  29 ///
  30 template <typename InputIterator, typename T, typename BinaryFunction>
  31 inline T accumulate (InputIterator first, InputIterator last, T init, BinaryFunction binary_op)
  32 {
  33     while (first < last)
  34         init = binary_op (init, *first++);
  35     return (init);
  36 }
  37
  38 /// Assigns range [value, value + (last - first)) to [first, last)
  39 /// \ingroup NumericAlgorithms
  40 ///
  41 template <typename ForwardIterator, typename T>
  42 inline void iota (ForwardIterator first, ForwardIterator last, T value)
  43 {
  44     while (first < last)
  45         *first++ = value++;
  46 }
  47
  48 /// Returns the sum of products of respective elements in the given ranges.
  49 /// \ingroup NumericAlgorithms
  50 ///
  51 template <typename InputIterator1, typename InputIterator2, typename T>
  52 inline T inner_product (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init)
  53 {
  54     while (first1 < last1)
  55         init += *first1++ * *first2++;
  56     return (init);
  57 }
  58
  59 /// Returns the sum of products of respective elements in the given ranges.
  60 /// \ingroup NumericAlgorithms
  61 ///
  62 template <typename InputIterator1, typename InputIterator2, typename T,
  63           typename BinaryOperation1, typename BinaryOperation2>
  64 inline T inner_product
  65 (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init,
  66  BinaryOperation1 sumOp, BinaryOperation2 productOp)
  67 {
  68     while (first1 < last1)
  69         init = sumOp (init, productOp (*first1++, *first2++));
  70     return (init);
  71 }
  72
  73 /// Writes result such that result[i] = sum (first...first+i)
  74 /// \ingroup NumericAlgorithms
  75 ///
  76 template <typename InputIterator, typename OutputIterator>
  77 inline OutputIterator partial_sum (InputIterator first, InputIterator last, OutputIterator result)
  78 {
  79     if (first < last)
  80         *result = *first++;
  81     while (first < last)
  82         *++result = *first++ + *result;
  83     return (result);
  84 }
  85
  86 /// Writes result such that result[i] = sumOp (first...first+i)
  87 /// \ingroup NumericAlgorithms
  88 ///
  89 template <typename InputIterator, typename OutputIterator, typename BinaryOperation>
  90 inline OutputIterator partial_sum (InputIterator first, InputIterator last, OutputIterator result, BinaryOperation sumOp)
  91 {
  92     if (first < last)
  93         *result = *first++;
  94     while (first < last)
  95         *++result = sumOp (*first++, *result);
  96     return (result);
  97 }
  98
  99 /// Writes result such that result[i] = first[i] - first[i - 1]
 100 /// \ingroup NumericAlgorithms
 101 ///
 102 template <typename InputIterator, typename OutputIterator>
 103 inline OutputIterator adjacent_difference (InputIterator first, InputIterator last, OutputIterator result)
 104 {
 105     if (first < last)
 106         *result++ = *first++;
 107     while (first < last)
 108         *result++ = *first - *(first - 1);
 109     return (result);
 110 }
 111
 112 /// Writes result such that result[i] = differenceOp (first[i], first[i - 1])
 113 /// \ingroup NumericAlgorithms
 114 ///
 115 template <typename InputIterator, typename OutputIterator, typename BinaryOperation>
 116 inline OutputIterator adjacent_difference (InputIterator first, InputIterator last, OutputIterator result, BinaryOperation differenceOp)
 117 {
 118     if (first < last)
 119         *result++ = *first++;
 120     while (first < last)
 121         *result++ = differenceOp (*first, *(first - 1));
 122     return (result);
 123 }
 124
 125 /// \brief Returns x^n.
 126 /// Donald Knuth's Russian Peasant algorithm.
 127 /// \ingroup NumericAlgorithms
 128 ///
 129 template <typename T>
 130 inline T power (T x, unsigned n)
 131 {
 132     T result (n % 2 ? x : 1);
 133     while (n /= 2) {
 134         x *= x;
 135         if (n % 2)
 136             result *= x;
 137     }
 138     return (result);
 139 }
 140
 141 /// \brief Returns x^n, using \p op instead of multiplication.
 142 /// Donald Knuth's Russian Peasant algorithm.
 143 /// \ingroup NumericAlgorithms
 144 ///
 145 template <typename T, typename BinaryOperation>
 146 inline T power (T x, unsigned n, BinaryOperation op)
 147 {
 148     T result (n % 2 ? x : 1);
 149     while (n /= 2) {
 150         x = op (x, x);
 151         if (n % 2)
 152             result = op (result, x);
 153     }
 154     return (result);
 155 }
 156
 157 } // namespace ustl
 158
 159 #endif
 160