#ifndef BOOST_MPL_GCD_HPP_INCLUDED
#define BOOST_MPL_GCD_HPP_INCLUDED

#include "boost/mpl/minus.hpp"
#include "boost/mpl/modulus.hpp"
#include "boost/mpl/equal_to.hpp"

/*
   mpl 'types' implementation of greatest common denominator
 */
//  after  "boost/math/common_factor_ct.hpp" which is...
//  (C) Copyright Daryle Walker and Stephen Cleary 2001-2002.

//  (C) Copyright Andy Little 2005
//  Distributed under 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)


namespace boost{namespace mpl{

    template <typename A, typename B>
    struct gcd;

    namespace detail{  

        template< typename T> 
        struct zero_type : minus<T,T> {};

        template <typename T>
        struct is_zero : equal_to<
            T,
            zero_type<T> 
        >{};

        template < 
            typename Lhs, 
            typename Rhs,
            bool Tail = is_zero<Rhs>::value 
        >
        struct gcd_impl;

        template < 
            typename Lhs, 
            typename Rhs
        >
        struct gcd_impl <Lhs,Rhs,false> : gcd_impl<
                Rhs,
                typename mpl::modulus<Lhs,Rhs>::type
        >{ };

        template < 
            typename Lhs, 
            typename Rhs  
        >
        struct gcd_impl<Lhs, Rhs,true> : Lhs {};

    }//detail

    template <typename Lhs, typename Rhs>
    struct gcd : detail::gcd_impl<
        typename Lhs::type, 
        typename Rhs::type 
    >{};

}}// boost::mpl


#endif