//  Boost common_factor_rt.hpp header file  ----------------------------------//

//  (C) Copyright Daryle Walker and Paul Moore 2001-2002.  Permission to copy,

//  use, modify, sell and distribute this software is granted provided this

//  copyright notice appears in all copies.  This software is provided "as is"

//  without express or implied warranty, and with no claim as to its suitability

//  for any purpose. 

//  See http://www.boost.org for updates, documentation, and revision history. 

#ifndef BOOST_MATH_COMMON_FACTOR_RT_HPP

#define BOOST_MATH_COMMON_FACTOR_RT_HPP

#include <boost/math_fwd.hpp>  // self include

#include <boost/config.hpp>  // for BOOST_NESTED_TEMPLATE, etc.

#include <boost/limits.hpp>  // for std::numeric_limits

namespace boost

{

namespace math

{

//  Forward declarations for function templates  -----------------------------//

template < typename IntegerType >

    IntegerType  gcd( IntegerType const &a, IntegerType const &b );

template < typename IntegerType >

    IntegerType  lcm( IntegerType const &a, IntegerType const &b );

//  Greatest common divisor evaluator class declaration  ---------------------//

template < typename IntegerType >

class gcd_evaluator

{

public:

    // Types

    typedef IntegerType  result_type, first_argument_type, second_argument_type;

    // Function object interface

    result_type  operator ()( first_argument_type const &a,

     second_argument_type const &b ) const;

};  // boost::math::gcd_evaluator

//  Least common multiple evaluator class declaration  -----------------------//

template < typename IntegerType >

class lcm_evaluator

{

public:

    // Types

    typedef IntegerType  result_type, first_argument_type, second_argument_type;

    // Function object interface

    result_type  operator ()( first_argument_type const &a,

     second_argument_type const &b ) const;

};  // boost::math::lcm_evaluator

//  Implementation details  --------------------------------------------------//

namespace detail

{

    // Greatest common divisor for rings (including unsigned integers)

    template < typename RingType >

    RingType

    gcd_euclidean

    (

        RingType  a,

        RingType  b

    )

    {

        // Avoid repeated construction

        #ifndef __BORLANDC__

        RingType const  zero = static_cast<RingType>( 0 );

        #else

        RingType  zero = static_cast<RingType>( 0 );

        #endif

        // Reduce by GCD-remainder property [GCD(a,b) == GCD(b,a MOD b)]

        while ( true )

        {

            if ( a == zero )

                return b;

            b %= a;

            if ( b == zero )

                return a;

            a %= b;

        }

    }

    // Greatest common divisor for (signed) integers

    template < typename IntegerType >

    inline

    IntegerType

    gcd_integer

    (

        IntegerType const &  a,

        IntegerType const &  b

    )

    {

        // Avoid repeated construction

        IntegerType const  zero = static_cast<IntegerType>( 0 );

        IntegerType const  result = gcd_euclidean( a, b );

        return ( result < zero ) ? -result : result;

    }

    // Least common multiple for rings (including unsigned integers)

    template < typename RingType >

    inline

    RingType

    lcm_euclidean

    (

        RingType const &  a,

        RingType const &  b

    )

    {

        RingType const  zero = static_cast<RingType>( 0 );

        RingType const  temp = gcd_euclidean( a, b );

        return ( temp != zero ) ? ( a / temp * b ) : zero;

    }

    // Least common multiple for (signed) integers

    template < typename IntegerType >

    inline

    IntegerType

    lcm_integer

    (

        IntegerType const &  a,

        IntegerType const &  b

    )

    {

        // Avoid repeated construction

        IntegerType const  zero = static_cast<IntegerType>( 0 );

        IntegerType const  result = lcm_euclidean( a, b );

        return ( result < zero ) ? -result : result;

    }

    // Function objects to find the best way of computing GCD or LCM

#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS

#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

    template < typename T, bool IsSpecialized, bool IsSigned >

    struct gcd_optimal_evaluator_helper_t

    {

        T  operator ()( T const &a, T const &b )

        {

            return gcd_euclidean( a, b );

        }

    };

    template < typename T >

    struct gcd_optimal_evaluator_helper_t< T, true, true >

    {

        T  operator ()( T const &a, T const &b )

        {

            return gcd_integer( a, b );

        }

    };

#else

    template < bool IsSpecialized, bool IsSigned >

    struct gcd_optimal_evaluator_helper2_t

    {

        template < typename T >

        struct helper

        {

            T  operator ()( T const &a, T const &b )

            {

                return gcd_euclidean( a, b );

            }

        };

    };

    template < >

    struct gcd_optimal_evaluator_helper2_t< true, true >

    {

        template < typename T >

        struct helper

        {

            T  operator ()( T const &a, T const &b )

            {

                return gcd_integer( a, b );

            }

        };

    };

    template < typename T, bool IsSpecialized, bool IsSigned >

    struct gcd_optimal_evaluator_helper_t

        : gcd_optimal_evaluator_helper2_t<IsSpecialized, IsSigned>

           ::BOOST_NESTED_TEMPLATE helper<T>

    {

    };

#endif

    template < typename T >

    struct gcd_optimal_evaluator

    {

        T  operator ()( T const &a, T const &b )

        {

            typedef ::std::numeric_limits<T>  limits_type;

            typedef gcd_optimal_evaluator_helper_t<T,

             limits_type::is_specialized, limits_type::is_signed>  helper_type;

            helper_type  solver;

            return solver( a, b );

        }

    };

#else // BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS

    template < typename T >

    struct gcd_optimal_evaluator

    {

        T  operator ()( T const &a, T const &b )

        {

            return gcd_integer( a, b );

        }

    };

#endif

#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS

#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION

    template < typename T, bool IsSpecialized, bool IsSigned >

    struct lcm_optimal_evaluator_helper_t

    {

        T  operator ()( T const &a, T const &b )

        {

            return lcm_euclidean( a, b );

        }

    };

    template < typename T >

    struct lcm_optimal_evaluator_helper_t< T, true, true >

    {

        T  operator ()( T const &a, T const &b )

        {

            return lcm_integer( a, b );

        }

    };

#else

    template < bool IsSpecialized, bool IsSigned >

    struct lcm_optimal_evaluator_helper2_t

    {

        template < typename T >

        struct helper

        {

            T  operator ()( T const &a, T const &b )

            {

                return lcm_euclidean( a, b );

            }

        };

    };

    template < >

    struct lcm_optimal_evaluator_helper2_t< true, true >

    {

        template < typename T >

        struct helper

        {

            T  operator ()( T const &a, T const &b )

            {

                return lcm_integer( a, b );

            }

        };

    };

    template < typename T, bool IsSpecialized, bool IsSigned >

    struct lcm_optimal_evaluator_helper_t

        : lcm_optimal_evaluator_helper2_t<IsSpecialized, IsSigned>

           ::BOOST_NESTED_TEMPLATE helper<T>

    {

    };

#endif

    template < typename T >

    struct lcm_optimal_evaluator

    {

        T  operator ()( T const &a, T const &b )

        {

            typedef ::std::numeric_limits<T>  limits_type;

            typedef lcm_optimal_evaluator_helper_t<T,

             limits_type::is_specialized, limits_type::is_signed>  helper_type;

            helper_type  solver;

            return solver( a, b );

        }

    };

#else // BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS

    template < typename T >

    struct lcm_optimal_evaluator

    {

        T  operator ()( T const &a, T const &b )

        {

            return lcm_integer( a, b );

        }

    };

#endif

    // Functions to find the GCD or LCM in the best way

    template < typename T >

    inline

    T

    gcd_optimal

    (

        T const &  a,

        T const &  b

    )

    {

        gcd_optimal_evaluator<T>  solver;

        return solver( a, b );

    }

    template < typename T >

    inline

    T

    lcm_optimal

    (

        T const &  a,

        T const &  b

    )

    {

        lcm_optimal_evaluator<T>  solver;

        return solver( a, b );

    }

}  // namespace detail

//  Greatest common divisor evaluator member function definition  ------------//

template < typename IntegerType >

inline

typename gcd_evaluator<IntegerType>::result_type

gcd_evaluator<IntegerType>::operator ()

(

    first_argument_type const &   a,

    second_argument_type const &  b

) const

{

    return detail::gcd_optimal( a, b );

}

//  Least common multiple evaluator member function definition  --------------//

template < typename IntegerType >

inline

typename lcm_evaluator<IntegerType>::result_type

lcm_evaluator<IntegerType>::operator ()

(

    first_argument_type const &   a,

    second_argument_type const &  b

) const

{

    return detail::lcm_optimal( a, b );

}

//  Greatest common divisor and least common multiple function definitions  --//

template < typename IntegerType >

inline

IntegerType

gcd

(

    IntegerType const &  a,

    IntegerType const &  b

)

{

    gcd_evaluator<IntegerType>  solver;

    return solver( a, b );

}

template < typename IntegerType >

inline

IntegerType

lcm

(

    IntegerType const &  a,

    IntegerType const &  b

)

{

    lcm_evaluator<IntegerType>  solver;

    return solver( a, b );

}

}  // namespace math

}  // namespace boost

#endif  // BOOST_MATH_COMMON_FACTOR_RT_HPP