#include "number.h"

#include <bu/sio.h>
#include <math.h>

#define RadixToBits( x ) ((int)(log((x))*0xb.8aa3b295c17fp-3+1.0))

Number::Number( int iRadix, int iScale ) :
    iRadix( iRadix ),
    iScale( iScale ),
    bPositive( true ),
    aInt( RadixToBits(iRadix) )
{
}

Number::Number( const Bu::String &sData, int iRadix, int iScale ) :
    iRadix( iRadix ),
    iScale( iScale ),
    bPositive( true ),
    aInt( RadixToBits( iRadix ) )
{
    set( sData );
}

Number::~Number()
{
}

Number &Number::operator=( const Bu::String &sNum )
{
    set( sNum );
    return *this;
}

Number &Number::operator=( const Number &rhs )
{
    set( rhs );
    return *this;
}

Number Number::operator+( const Number &rhs ) const
{
    return add( rhs, false );
}

Number Number::operator-( const Number &rhs ) const
{
    return add( rhs, true );
}

Number Number::operator*( const Number &rhs ) const
{
    Number ret( iRadix, iScale );

    int iCnt = aInt.getSize()+rhs.aInt.getSize();

    int iCarry = 0;
    int iZeros = 0;
    for( int j = 0; j < iCnt || iCarry > 0; j++ )
    {
//        Bu::println("Pos %1").arg(j);
        int iPos = iCarry;
        iCarry = 0;
        for( int k = 0; k < rhs.aInt.getSize(); k++ )
        {
            if( j-k < 0 )
                break;

            int iRes = digit(j-k)*rhs.digit(k);
            iPos += iRes;
            
//            Bu::println("  [%1] %2 * [%3] %4 = %5 -> %6").
//                arg( j-k ).arg( digit(j-k) ).arg( k ).arg( rhs.digit(k) ).
//                arg( iRes ).arg( iPos ).arg( iCarry );
        }
        if( (iPos%iRadix) == 0 )
            iZeros++;
        else
        {
            for(; iZeros > 0; iZeros-- )
                ret.aInt.append( 0 );
            ret.aInt.append( iPos%iRadix );
        }
        iCarry += iPos/iRadix;
    }

    if( bPositive == rhs.bPositive )
        ret.bPositive = true;
    else
        ret.bPositive = false;

    return ret;
}

Number Number::operator/( const Number &rhs ) const
{
    Number q( iRadix, iScale ), r( iRadix, iScale );
    divide( rhs, q, r );
    return q;
}

Number Number::operator%( const Number &rhs ) const
{
    Number q( iRadix, iScale ), r( iRadix, iScale );
    divide( rhs, q, r );
    return r;
}

Number Number::operator-() const
{
    Number neg( *this );
    neg.bPositive = !neg.bPositive;
    return neg;
}

bool Number::operator==( const Number &rhs ) const
{
    if( rhs.bPositive != bPositive ||
        rhs.iScale != iScale || 
        rhs.aInt.getSize() != aInt.getSize() )
        return false;

    for( int j = 0; j < aInt.getSize(); j++ )
    {
        if( aInt[j] != rhs.aInt[j] )
            return false;
    }

    return true;
}

bool Number::operator!=( const Number &rhs ) const
{
    return !(*this == rhs);
}

bool Number::operator>( const Number &rhs ) const
{
    if( bPositive && !rhs.bPositive )
        return true;
    if( !bPositive && rhs.bPositive )
        return false;

    if( aInt.getSize() > rhs.aInt.getSize() )
        return bPositive;
    if( aInt.getSize() < rhs.aInt.getSize() )
        return !bPositive;

    for( int j = aInt.getSize()-1; j >= 0; j-- )
    {
//        Bu::println("  --> %1 > %2 -> %3").arg( aInt[j] ).arg( rhs.aInt[j] ).
//            arg( aInt[j] > rhs.aInt[j] );
        int iDiff = aInt[j] - rhs.aInt[j];
        if( iDiff < 0 )
            return !bPositive;
        else if( iDiff > 0 )
            return bPositive;
    }
    return false;
}

bool Number::operator<( const Number &rhs ) const
{
    if( bPositive && !rhs.bPositive )
        return false;
    if( !bPositive && rhs.bPositive )
        return true;

    if( aInt.getSize() < rhs.aInt.getSize() )
        return bPositive;
    if( aInt.getSize() > rhs.aInt.getSize() )
        return !bPositive;

    for( int j = aInt.getSize()-1; j >= 0; j-- )
    {
//        Bu::println("  --> %1 > %2 -> %3").arg( aInt[j] ).arg( rhs.aInt[j] ).
//            arg( aInt[j] < rhs.aInt[j] );
        int iDiff = aInt[j] - rhs.aInt[j];
        if( iDiff > 0 )
            return !bPositive;
        else if( iDiff < 0 )
            return bPositive;
    }
    return false;
}

bool Number::operator>=( const Number &rhs ) const
{
    if( bPositive && !rhs.bPositive )
        return true;
    if( !bPositive && rhs.bPositive )
        return false;

    if( aInt.getSize() > rhs.aInt.getSize() )
        return bPositive;
    if( aInt.getSize() < rhs.aInt.getSize() )
        return !bPositive;

    for( int j = aInt.getSize()-1; j >= 0; j-- )
    {
//        Bu::println("  --> %1 > %2 -> %3").arg( aInt[j] ).arg( rhs.aInt[j] ).
//            arg( aInt[j] > rhs.aInt[j] );
        int iDiff = aInt[j] - rhs.aInt[j];
        if( iDiff < 0 )
            return !bPositive;
        else if( iDiff > 0 )
            return bPositive;
    }
    return true;
}

bool Number::operator<=( const Number &rhs ) const
{
    if( bPositive && !rhs.bPositive )
        return false;
    if( !bPositive && rhs.bPositive )
        return true;

    if( aInt.getSize() < rhs.aInt.getSize() )
        return bPositive;
    if( aInt.getSize() > rhs.aInt.getSize() )
        return !bPositive;

    for( int j = aInt.getSize()-1; j >= 0; j-- )
    {
//        Bu::println("  --> %1 > %2 -> %3").arg( aInt[j] ).arg( rhs.aInt[j] ).
//            arg( aInt[j] < rhs.aInt[j] );
        int iDiff = aInt[j] - rhs.aInt[j];
        if( iDiff > 0 )
            return !bPositive;
        else if( iDiff < 0 )
            return bPositive;
    }
    return true;
}

void Number::set( const Bu::String &sNum )
{
    aInt.clear();
    bPositive = true;
    for( int j = sNum.getSize()-1; j >= 0; j-- )
    {
        if( sNum[j] == '+' )
            break;
        if( sNum[j] == '-' )
        {
            bPositive = false;
            break;
        }
        if( sNum[j] >= '0' && sNum[j] <= '9' )
            aInt.append( sNum[j]-'0' );
        else
            aInt.append( sNum[j]-'a'+10 );
    }
}

void Number::set( const Number &sNum )
{
    aInt.set( sNum.aInt );
    bPositive = sNum.bPositive;
    iScale = sNum.iScale;
}

Bu::String Number::toString() const
{
    if( aInt.getSize() == 0 )
        return "0";
    Bu::String sRet;
    if( !bPositive )
        sRet += '-';
    for( int j = aInt.getSize()-1; j >= 0; j-- )
    {
        int x = aInt.get( j );
        if( x >= 10 )
            sRet += x-10+'a';
        else
            sRet += x+'0';
    }
    
    return sRet;
}

int Number::digit( int iIdx ) const
{
    if( iIdx >= aInt.getSize() )
        return 0;
    return aInt[iIdx];
}

Number Number::add( const Number &rhs, bool bSub ) const
{
    Number ret( iRadix, iScale );

    int iPlaces = Bu::buMax(rhs.aInt.getSize(), aInt.getSize() );

    int iZeros = 0;
    int iCarry = 0;
//    Bu::println("::: %1 + %2:").arg( toString() ).arg( rhs.toString() );

    if( bPositive == (bSub?!rhs.bPositive:rhs.bPositive))
    {
        ret.bPositive = bPositive;
        for( int j = 0; j < iPlaces || iCarry > 0; j++ )
        {
            int iRes = iCarry + digit( j ) + rhs.digit( j );
//            Bu::println(" Place: %1 + %2 + (%3) = %4").
//                arg( digit(j) ).arg( rhs.digit( j ) ).arg( iCarry )
//                .arg( iRes );
            if( iRes == 0 )
            {
                iZeros++;
                continue;
            }
            for(; iZeros > 0; iZeros-- )
                ret.aInt.append( 0 );
            
            ret.aInt.append( (iRes%iRadix) );
            if( iRes < iRadix )
                iCarry = 0;
            else
                iCarry = iRes/iRadix;
        }
    }
    else
    {
        iCarry = 1;
//        Bu::println("--method b--");
        ret.bPositive = bPositive;
        int iRes;
        int iComp = (iRadix-1);
        for( int j = 0; j < iPlaces; j++ )
        {
            iRes = digit( j ) + (iComp-rhs.digit( j )) + iCarry;
//            Bu::println(" Place: %1 + %2 + (%3) = %4").
//                arg( digit(j) ).arg( 9-rhs.digit( j ) ).arg( iCarry )
//                .arg( iRes );
            if( iRes == 0 )
            {
                iZeros++;
                continue;
            }
            for(; iZeros > 0; iZeros-- )
                ret.aInt.append( 0 );

            ret.aInt.append( (iRes%iRadix) );
            if( iRes < iRadix )
                iCarry = 0;
            else
                iCarry = iRes/iRadix;
        }
        if( iCarry == 0 )
        {
            ret.bPositive = false;
            ret.aInt.set( 0, iComp-ret.aInt.get( 0 )+1);
            for( int j = 1; j < ret.aInt.getSize(); j++ )
            {
                ret.aInt.set( j, iComp-ret.aInt.get( j ));
            }
        }
        else
        {
            ret.aInt.trim();
        }
    }

    return ret;
}

void Number::divide( const Number &rhs, Number &q, Number &r ) const
{
    q.aInt.clear();
    r = *this;
    
    if( rhs.aInt.getSize() > aInt.getSize() )
        return;

    if( bPositive == rhs.bPositive )
        q.bPositive = true;
    else
        q.bPositive = false;

    int iMinWidth = rhs.aInt.getSize();

    int iAnchor = r.aInt.getSize()-iMinWidth;
    int iSample = iMinWidth;
    do
    {
//        Bu::println("%1\n-----").arg( r.aInt.toString() );
        Number sub( iRadix, iScale );
        for(;;)
        {
//            Bu::println("  -> Anchor: %1, Sample: %2").arg( iAnchor ).arg( iSample );
            sub.aInt.set( r.aInt, iAnchor, iSample );
//            Bu::println("%1\n%2\n----").arg( sub.toString() ).arg( rhs.toString() );
            if( sub < rhs )
            {
                iSample++;
                iAnchor--;
                if( iAnchor < 0 )
                {
//                    Bu::println("[Inner exit] Complete: q = %1, r = %2").arg( q.toString() ).arg( r.toString() );
                    return;
                }
            }
            else
                break;
        }

        Number x( iRadix, iScale );
        int iRes = 0;
        for( ; x <= sub; iRes++, x = x + rhs ) { }
        x = sub - (x - rhs);
        for( int j = 0; iAnchor+j >= 0 && j < x.aInt.getSize(); j++ )
            r.aInt.set( iAnchor+j, x.aInt.get( j ) );
        while( r.aInt.getSize() > iAnchor+x.aInt.getSize() )
            r.aInt.remove();
//        Bu::println(" -> Post remainder patch: %1 -> %2").
//            arg( x.toString() ).arg( r.toString() );

//        Bu::println("%1 (%2)").arg( iRes-1 ).arg( x.toString() );
        while( q.aInt.getSize() <= iAnchor )
            q.aInt.append(0);
        q.aInt.set( iAnchor, iRes-1 );

        iSample = iMinWidth;
        iAnchor = r.aInt.getSize()-iMinWidth;
//        Bu::println("  -> new Anchor: %1, Sample: %2").arg( iAnchor ).
//            arg( iSample );
    } while( iAnchor >= 0 );

//    Bu::println("Complete: q = %1, r = %2").arg( q.toString() ).arg( r.toString() );
}

Bu::Formatter &operator<<( Bu::Formatter &f, const Number &n )
{
    return f << n.toString();
}