boost/algorithm/algorithm.hpp

   1 /*
   2    Copyright (c) Marshall Clow 2014.
   3
   4    Distributed under the Boost Software License, Version 1.0. (See accompanying
   5    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6
   7  Revision history:
   8     2 Dec 2014 mtc First version; power
   9
  10 */
  11
  12 /// \file algorithm.hpp
  13 /// \brief Misc Algorithms
  14 /// \author Marshall Clow
  15 ///
  16
  17 #ifndef BOOST_ALGORITHM_HPP
  18 #define BOOST_ALGORITHM_HPP
  19
  20 #include <functional> // for plus and multiplies
  21
  22 #include <boost/config.hpp>
  23 #include <boost/utility/enable_if.hpp> // for boost::disable_if
  24 #include <boost/type_traits/is_integral.hpp>
  25
  26 namespace boost { namespace algorithm {
  27
  28 template <typename T>
  29 BOOST_CXX14_CONSTEXPR T identity_operation ( std::multiplies<T> ) { return T(1); }
  30
  31 template <typename T>
  32 BOOST_CXX14_CONSTEXPR T identity_operation ( std::plus<T> ) { return T(0); }
  33
  34
  35 /// \fn power ( T x, Integer n )
  36 /// \return the value "x" raised to the power "n"
  37 ///
  38 /// \param x     The value to be exponentiated
  39 /// \param n     The exponent (must be >= 0)
  40 ///
  41 //  \remark Taken from Knuth, The Art of Computer Programming, Volume 2:
  42 //  Seminumerical Algorithms, Section 4.6.3
  43 template <typename T, typename Integer>
  44 BOOST_CXX14_CONSTEXPR typename boost::enable_if<boost::is_integral<Integer>, T>::type
  45 power (T x, Integer n) {
  46     T y = 1; // Should be "T y{1};"
  47     if (n == 0) return y;
  48     while (true) {
  49         if (n % 2 == 1) {
  50             y = x * y;
  51             if (n == 1)
  52                 return y;
  53             }
  54         n = n / 2;
  55         x = x * x;
  56         }
  57     return y;
  58     }
  59
  60 /// \fn power ( T x, Integer n, Operation op )
  61 /// \return the value "x" raised to the power "n"
  62 /// using the operation "op".
  63 ///
  64 /// \param x     The value to be exponentiated
  65 /// \param n     The exponent (must be >= 0)
  66 /// \param op    The operation used
  67 ///
  68 //  \remark Taken from Knuth, The Art of Computer Programming, Volume 2:
  69 //  Seminumerical Algorithms, Section 4.6.3
  70 template <typename T, typename Integer, typename Operation>
  71 BOOST_CXX14_CONSTEXPR typename boost::enable_if<boost::is_integral<Integer>, T>::type
  72 power (T x, Integer n, Operation op) {
  73     T y = identity_operation(op);
  74     if (n == 0) return y;
  75     while (true) {
  76         if (n % 2 == 1) {
  77             y = op(x, y);
  78             if (n == 1)
  79                 return y;
  80             }
  81         n = n / 2;
  82         x = op(x, x);
  83         }
  84     return y;
  85     }
  86
  87 }}
  88
  89 #endif // BOOST_ALGORITHM_HPP