boost/algorithm/algorithm.hpp

0001 /*
0002    Copyright (c) Marshall Clow 2014.
0003
0004    Distributed under the Boost Software License, Version 1.0. (See accompanying
0005    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006
0007  Revision history:
0008     2 Dec 2014 mtc First version; power
0009
0010 */
0011
0012 /// \file algorithm.hpp
0013 /// \brief Misc Algorithms
0014 /// \author Marshall Clow
0015 ///
0016
0017 #ifndef BOOST_ALGORITHM_HPP
0018 #define BOOST_ALGORITHM_HPP
0019
0020 #include <functional> // for plus and multiplies
0021
0022 #include <boost/config.hpp>
0023 #include <boost/core/enable_if.hpp> // for boost::disable_if
0024 #include <boost/type_traits/is_integral.hpp>
0025
0026 namespace boost { namespace algorithm {
0027
0028 template <typename T>
0029 BOOST_CXX14_CONSTEXPR T identity_operation ( std::multiplies<T> ) { return T(1); }
0030
0031 template <typename T>
0032 BOOST_CXX14_CONSTEXPR T identity_operation ( std::plus<T> ) { return T(0); }
0033
0034
0035 /// \fn power ( T x, Integer n )
0036 /// \return the value "x" raised to the power "n"
0037 ///
0038 /// \param x     The value to be exponentiated
0039 /// \param n     The exponent (must be >= 0)
0040 ///
0041 //  \remark Taken from Knuth, The Art of Computer Programming, Volume 2:
0042 //  Seminumerical Algorithms, Section 4.6.3
0043 template <typename T, typename Integer>
0044 BOOST_CXX14_CONSTEXPR typename boost::enable_if<boost::is_integral<Integer>, T>::type
0045 power (T x, Integer n) {
0046     T y = 1; // Should be "T y{1};"
0047     if (n == 0) return y;
0048     while (true) {
0049         if (n % 2 == 1) {
0050             y = x * y;
0051             if (n == 1)
0052                 return y;
0053             }
0054         n = n / 2;
0055         x = x * x;
0056         }
0057     return y;
0058     }
0059
0060 /// \fn power ( T x, Integer n, Operation op )
0061 /// \return the value "x" raised to the power "n"
0062 /// using the operation "op".
0063 ///
0064 /// \param x     The value to be exponentiated
0065 /// \param n     The exponent (must be >= 0)
0066 /// \param op    The operation used
0067 ///
0068 //  \remark Taken from Knuth, The Art of Computer Programming, Volume 2:
0069 //  Seminumerical Algorithms, Section 4.6.3
0070 template <typename T, typename Integer, typename Operation>
0071 BOOST_CXX14_CONSTEXPR typename boost::enable_if<boost::is_integral<Integer>, T>::type
0072 power (T x, Integer n, Operation op) {
0073     T y = identity_operation(op);
0074     if (n == 0) return y;
0075     while (true) {
0076         if (n % 2 == 1) {
0077             y = op(x, y);
0078             if (n == 1)
0079                 return y;
0080             }
0081         n = n / 2;
0082         x = op(x, x);
0083         }
0084     return y;
0085     }
0086
0087 }}
0088
0089 #endif // BOOST_ALGORITHM_HPP