ceph/src/boost/libs/algorithm/include/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/utility/enable_if.hpp> // for boost::disable_if
  23 #include <boost/type_traits/is_integral.hpp>
  24
  25 namespace boost { namespace algorithm {
  26
  27 template <typename T>
  28 T identity_operation ( std::multiplies<T> ) { return T(1); }
  29
  30 template <typename T>
  31 T identity_operation ( std::plus<T> ) { return T(0); }
  32
  33
  34 /// \fn power ( T x, Integer n )
  35 /// \return the value "x" raised to the power "n"
  36 ///
  37 /// \param x     The value to be exponentiated
  38 /// \param n     The exponent (must be >= 0)
  39 ///
  40 //  \remark Taken from Knuth, The Art of Computer Programming, Volume 2:
  41 //  Seminumerical Algorithms, Section 4.6.3
  42 template <typename T, typename Integer>
  43 typename boost::enable_if<boost::is_integral<Integer>, T>::type
  44 power (T x, Integer n) {
  45     T y = 1; // Should be "T y{1};"
  46     if (n == 0) return y;
  47     while (true) {
  48         if (n % 2 == 1) {
  49             y = x * y;
  50             if (n == 1)
  51                 return y;
  52             }
  53         n = n / 2;
  54         x = x * x;
  55         }
  56     return y;
  57     }
  58
  59 /// \fn power ( T x, Integer n, Operation op )
  60 /// \return the value "x" raised to the power "n"
  61 /// using the operation "op".
  62 ///
  63 /// \param x     The value to be exponentiated
  64 /// \param n     The exponent (must be >= 0)
  65 /// \param op    The operation used
  66 ///
  67 //  \remark Taken from Knuth, The Art of Computer Programming, Volume 2:
  68 //  Seminumerical Algorithms, Section 4.6.3
  69 template <typename T, typename Integer, typename Operation>
  70 typename boost::enable_if<boost::is_integral<Integer>, T>::type
  71 power (T x, Integer n, Operation op) {
  72     T y = identity_operation(op);
  73     if (n == 0) return y;
  74     while (true) {
  75         if (n % 2 == 1) {
  76             y = op(x, y);
  77             if (n == 1)
  78                 return y;
  79             }
  80         n = n / 2;
  81         x = op(x, x);
  82         }
  83     return y;
  84     }
  85
  86 }}
  87
  88 #endif // BOOST_ALGORITHM_HPP