/* greatest_common_divisor.hpp header file
 *
 * Copyright Cromwell D. Enage 2004.  Use, modification, and distribution are
 * subject to the Boost Software License, Version 1.0.  (See accompanying file
 * LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 */

#ifndef GREATEST_COMMON_DIVISOR_HPP
#define GREATEST_COMMON_DIVISOR_HPP

/*
 * Defines the workaround macros for ill-conforming compilers.
 */
#include <boost/config.hpp>

/*
 * Defines the boost::mpl::and_ class template.
 */
#include <boost/mpl/and.hpp>

/*
 * Defines the boost::mpl::equal_to class template.
 */
#include <boost/mpl/equal_to.hpp>

/*
 * Defines the boost::mpl::if_c class template.
 */
#include <boost/mpl/if.hpp>

/*
 * Defines the boost::mpl::integral_c class template.
 */
#include <boost/mpl/integral_c.hpp>

/*
 * Defines the boost::mpl::less struct template.
 */
#include <boost/mpl/less.hpp>

/*
 * Defines the boost::mpl::modulus_c struct template.
 */
#include <boost/mpl/modulus.hpp>

/*
 * Defines the boost::mpl::negate struct template.
 */
#include <boost/mpl/negate.hpp>

/*
 * Defines the boost::mpl::not_equal_to struct template.
 */
#include <boost/mpl/not_equal_to.hpp>

namespace boost {
  namespace mpl {

    /*
     * Workaround for compilers that don't support partial specialization.
     */
    namespace aux {

        template <bool C>
        struct gcd_impl
        {
            template <typename IntegralType>
            struct result_type
            {
                template <IntegralType N>
                struct abs_cond
                {
                    typedef typename less<integral_c<IntegralType,N>,
                                          integral_c<IntegralType,0> >::type
                            type;
                    BOOST_STATIC_CONSTANT(bool, value = type::value);
                };

                template <IntegralType N>
                struct abs_N
                {
                    typedef typename if_c<abs_cond<N>::value,
                                          negate<integral_c<IntegralType,N> >,
                                          integral_c<IntegralType,N> >::type
                            type;
                    BOOST_STATIC_CONSTANT(bool, value = type::value);
                };

                template <IntegralType A, IntegralType B>
                struct less_A_B
                {
                    typedef typename less<integral_c<IntegralType,A>,
                                          integral_c<IntegralType,B> >::type
                            type;
                    BOOST_STATIC_CONSTANT(bool, value = type::value);
                };

                template <IntegralType A, IntegralType B>
                struct next_A
                {
                    typedef typename if_c<less_A_B<A,B>::value,
                                          integral_c<IntegralType,A>,
                                          integral_c<IntegralType,B> >::type
                            type;
                    BOOST_STATIC_CONSTANT(IntegralType, value = type::value);
                };

                template <IntegralType A, IntegralType B>
                struct next_B
                {
                    typedef typename if_c<less_A_B<A,B>::value,
                                          modulus_c<IntegralType,B,A>,
                                          modulus_c<IntegralType,A,B>
                                         >::type
                            modulus_type;
                    typedef typename modulus_type::type
                            type;
                    BOOST_STATIC_CONSTANT(IntegralType, value = type::value);
                };

                template <IntegralType A, IntegralType B>
                struct next_bool
                {
                    typedef typename not_equal_to<
                                       integral_c<IntegralType,
                                                  next_B<A,B>::value>,
                                       integral_c<IntegralType,0> >::type
                            type;
                    BOOST_STATIC_CONSTANT(bool, value = type::value);
                };

                template <IntegralType A, IntegralType B>
                class result_
                {
                 private:
                    typedef typename gcd_impl<next_bool<A,B>::value>
                              ::template result_type<IntegralType>
                            result_type;

                 public:
                    typedef typename result_type
                              ::template result_<next_A<A,B>::value,
                                                 next_B<A,B>::value>::type
                            type;
                };
            };
        };

        template <>
        struct gcd_impl<false>
        {
            template <typename IntegralType>
            struct result_type
            {
                template <IntegralType N>
                struct zero_cond
                {
                    typedef typename equal_to<integral_c<IntegralType,N>,
                                              integral_c<IntegralType,0> >::type
                            type;
                    BOOST_STATIC_CONSTANT(bool, value = type::value);
                };

                template <IntegralType N>
                struct abs_cond
                {
                    typedef typename less<integral_c<IntegralType,N>,
                                          integral_c<IntegralType,0> >::type
                            type;
                    BOOST_STATIC_CONSTANT(bool, value = type::value);
                };

                template <IntegralType N>
                struct abs_N
                {
                    typedef typename if_c<abs_cond<N>::value,
                                          negate<integral_c<IntegralType,N> >,
                                          integral_c<IntegralType,N> >::type
                            type;
                };

                template <IntegralType A, IntegralType B>
                class result_
                {
                 private:
                    typedef typename if_c<zero_cond<A>::value,
                                          abs_N<B>,abs_N<A> >::type
                            abs_type;

                 public:
                    typedef typename abs_type::type
                            type;
                };
            };
        };

        template <typename IntegralType, IntegralType A, IntegralType B>
        struct gcd_cond
        {
            typedef typename and_<not_equal_to<integral_c<IntegralType,A>,
                                               integral_c<IntegralType,0> >,
                                  not_equal_to<integral_c<IntegralType,B>,
                                               integral_c<IntegralType,0> >
                                 >::type
                    type;
            BOOST_STATIC_CONSTANT(bool, value = type::value);
        };
    } // namespace aux

    template <typename IntegralType, IntegralType A, IntegralType B>
    class greatest_common_divisor_c
    {
     private:
        typedef typename aux::gcd_impl<aux::gcd_cond<IntegralType,A,B>::value>
                  ::template result_type<IntegralType>
                result_type;

     public:
        /*
         * Metafunction return type.
         */
        typedef typename result_type::template result_<A,B>::type type;
    };
  }  // namespace mpl
}  // namespace boost

#endif /* GREATEST_COMMON_DIVISOR_HPP */