#include "number.h"

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

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

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

Number::Number( const Bu::String &sData, int iScale, int iRadix ) :
    iRadix( iRadix ),
    iScale( iScale ),
    bPositive( true ),
    aInt( RadixToBits( iRadix ) ),
    aFrac( aInt.getBitWidth(), iScale )
{
    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( iScale+rhs.iScale,iRadix );

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

    int iCarry = 0;
    int iZeros = 0;
    for( int j = -iScale-rhs.iScale; j < iCnt || iCarry > 0; j++ )
    {
//        Bu::println("Pos %1").arg(j);
        int iPos = iCarry;
        iCarry = 0;
        for( int k = 1-rhs.iScale; 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 );
        }
//        Bu::println("=> %1 = %2 (%3 / %4)").arg( j ).arg( iPos ).arg( iPos%iRadix ).arg( iPos/iRadix );
        if( j < 0 )
            ret.aFrac.set( -1-j, (iPos%iRadix) );
        else
        {
            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( iScale, iRadix ), r( iScale, iRadix );
    divide( rhs, q, r );
    return q;
}

Number Number::operator%( const Number &rhs ) const
{
    Number q( iScale, iRadix ), r( iScale, iRadix );
    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 )
{
//    Bu::println("Parsing: '%1'").arg( sNum );
    aInt.clear();
    aFrac.zero();
    bPositive = true;
    if( sNum.isEmpty() )
        return;
    int iPt;
    for( iPt = 0; iPt < sNum.getSize() && sNum[iPt] != '.'; iPt++ ) { }

    int iEnd = 0;
    if( sNum[iEnd] == '+' )
        iEnd++;
    else if( sNum[iEnd] == '-' )
    {
        bPositive = false;
        iEnd++;
    }
    for( ; iEnd < sNum.getSize() && sNum[iEnd] == '0'; iEnd++ ) { }

    for( int j = iPt-1; j >= iEnd; j-- )
    {
//        Bu::println(" -> '%1'").arg( sNum[j] );
        if( sNum[j] == '.' )
            break;
        if( sNum[j] >= '0' && sNum[j] <= '9' )
            aInt.append( sNum[j]-'0' );
        else
            aInt.append( sNum[j]-'a'+10 );
    }

    if( iScale > 0 )
    {
        int iFrac = 0;
        for( int j = iPt+1; j < sNum.getSize(); j++ )
        {
//            Bu::println(" => '%1'").arg( sNum[j] );
            if( sNum[j] >= '0' && sNum[j] <= '9' )
                aFrac.set( iFrac++, sNum[j]-'0' );
            else
                aFrac.set( iFrac++, sNum[j]-'a'+10 );
            if( iFrac >= iScale )
                break;
        }
    }

//    Bu::println("done.");
}

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

Bu::String Number::toString() const
{
    int iSigDig = iScale-1;
    for( ; iSigDig >= 0 && aFrac.get( iSigDig ) == 0; iSigDig-- ) { }
    if( aInt.getSize() == 0 && iSigDig <= 0 )
        return "0";
    Bu::String sRet;
    if( !bPositive )
        sRet += '-';
    if( aInt.getSize() > 0 )
    {
        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';
        }
    }
    else
        sRet += "0";
    if( iSigDig >= 0 )
    {
        sRet += '.';
        for( int j = 0; j <= iSigDig; j++ )
        {
            int x = aFrac.get( j );
            if( x >= 10 )
                sRet += x-10+'a';
            else
                sRet += x+'0';
        }
    }
    
    return sRet;
}

int Number::digit( int iIdx ) const
{
    if( iIdx < 0 )
    {
        if( iIdx <= -iScale )
            return 0;
        else
            return aFrac[-1-iIdx];
    }
    if( iIdx >= aInt.getSize() )
        return 0;
    return aInt[iIdx];
}

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

    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 = -iScale; j < iPlaces || iCarry > 0; j++ )
        {
            int iRes = iCarry + digit( j ) + rhs.digit( j );
//            Bu::println(" [%5] Place: %1 + %2 + (%3) = %4").
//                arg( digit(j) ).arg( rhs.digit( j ) ).arg( iCarry )
//                .arg( iRes ).arg( j );
            if( j < 0 )
                ret.aFrac.set( -1-j, (iRes%iRadix) );
            else
            {
                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 = -iScale; 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( j < 0 )
                ret.aFrac.set( -1-j, (iRes%iRadix) );
            else
            {
                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
{
    if( rhs.iScale > 0 )
    {
        Number newrhs = Number( 0, iRadix );
        Number newbase = Number( iScale, iRadix );
        int iOff;
        for( iOff = -iScale; iOff < 0 && rhs.digit( iOff ) == 0; iOff++ ) { }
        if( iOff < 0 )
        {
            for( int j = iOff; j < rhs.aInt.getSize(); j++ )
            {
                newrhs.aInt.append( rhs.digit( j ) );
                newbase.aInt.append( digit( j ) );
            }
            for( int j = rhs.aInt.getSize(); j < aInt.getSize(); j++ )
            {
                newbase.aInt.append( aInt.get( j ) );
            }
            for( int j = iScale+iOff; j >= -iOff; j-- )
            {
                newbase.aFrac.set( j+iOff, aFrac.get( j ) );
            }

//            Bu::println("Conv %1 => %2 (iOff = %3)").arg( rhs ).arg( newrhs ).arg( iOff );
//            Bu::println("Conv %1 => %2 (iOff = %3)").arg( *this ).arg( newbase ).arg( iOff );

            newbase.divide( newrhs, q, r );
            return;
        }
    }
    
    q = Number( iScale, iRadix );
    r = *this;

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

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

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

        Number x( 0, iRadix );
        int iRes = -1;
//        Bu::println("{x = %1, sub=%2, rhs=%4, iRes=%3}").arg( x ).arg(sub).arg(iRes).arg(rhs);
        for( ; x <= sub; iRes++, x = x + rhs ) { 
//        Bu::println("{x = %1, sub=%2, rhs=%4, iRes=%3, x+rhs=%5}").arg( x ).arg(sub).arg(iRes).arg(rhs).arg(x+rhs);
        }
        x = sub - (x - rhs);
        if( !x.bPositive )
        {
            iSample++;
            iAnchor--;
//            Bu::println("What?  it's negative? %1").arg( x );
            continue;
        }
        if( iAnchor < 0 )
        {
            r = x;
        }
        else
        {
            for( int j = 0; j < x.aInt.getSize(); j++ )
                r.aInt.set( iAnchor+j, x.aInt.get( j ) );
        }

        while( r.aInt.getSize() > Bu::buMax(0,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 ).arg( x.toString() );
        while( q.aInt.getSize() <= iAnchor )
            q.aInt.append(0);
        if( iAnchor >= 0 )
            q.aInt.set( iAnchor, iRes );
        else
            q.aFrac.set( -1-iAnchor, iRes );
        
        iSample = iMinWidth;
        if( iAnchor > 0 )
            iAnchor -= rhs.aInt.getSize()-x.aInt.getSize();
        else
            iAnchor--;
//        iAnchor = r.aInt.getSize()-iMinWidth;
//        Bu::println("  -> new Anchor: %1, Sample: %2").arg( iAnchor ).
//            arg( iSample );
    } while( iAnchor >= -iScale );

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

bool Number::isZero() const
{
    if( aInt.getSize() == 0 && iScale == 0 )
        return true;

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

    return true;
}

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