#include "config.h"
#include "number.h"

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

// Enjoy the majisty of my magic floating point literal!
// This tells us how many bits we'll need per digit to represent a particular
// radix.  You can figure out how many digits any number will take up in any
// radix with the following:
//
// ceiling(ln( num ) / ln( radix ))
//
// As long as the base of the logs are the same it doesn't matter what the base
// is, it cancels out, so we don't have to be particular.  But we're always
// looking for the largest number in a radix to be stored in binary, so the
// denominator is always the same, so I precomputed it.
#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 )
{
    if( iRadix <= 1 )
        throw Bu::ExceptionBase("Invalid radix.  Radix must be > 1.");
}

Number::Number( const Bu::String &sData, int iScale, int iRadix ) :
    iRadix( iRadix ),
    iScale( iScale ),
    bPositive( true ),
    aInt( RadixToBits( iRadix ) ),
    aFrac( aInt.getBitWidth(), iScale )
{
    if( iRadix <= 1 )
        throw Bu::ExceptionBase("Invalid radix.  Radix must be > 1.");

    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 int32_t iNum )
{
    set( iNum );
    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 = -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;
    }

    ret.bPositive = !(!bPositive ^ !rhs.bPositive);

    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 Bu::String &rhs ) const
{
    Number nrhs( rhs, iScale, iRadix );
    return (*this) == nrhs;
}

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;
    }
    for( int j = 0; j < aFrac.getSize(); j++ )
    {
        if( aFrac[j] != rhs.aFrac[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;
    }
    int iMax = iScale;
    if( rhs.iScale > iMax )
        iMax = rhs.iScale;
//    Bu::println("Max scale = %1").arg( iMax );
    for( int j = 0; j < iMax; j++ )
    {
//        Bu::println(" > at %1 (%2 > %3)").arg( j )
//            .arg( digit(-1-j) ).arg( rhs.digit(-1-j) );
        int iDiff = digit(-1-j) - rhs.digit(-1-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;
    }
    int iMax = iScale;
    if( rhs.iScale > iMax )
        iMax = rhs.iScale;
    for( int j = 0; j < iMax; j++ )
    {
        int iDiff = digit(-1-j) - rhs.digit(-1-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-- )
    {
        int iDiff = aInt[j] - rhs.aInt[j];
        if( iDiff < 0 )
            return !bPositive;
        else if( iDiff > 0 )
            return bPositive;
    }
    int iMax = iScale;
    if( rhs.iScale > iMax )
        iMax = rhs.iScale;
    for( int j = 0; j < iMax; j++ )
    {
        int iDiff = digit(-1-j) - rhs.digit(-1-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;
    }
    int iMax = iScale;
    if( rhs.iScale > iMax )
        iMax = rhs.iScale;
    for( int j = 0; j < iMax; j++ )
    {
        int iDiff = digit(-1-j) - rhs.digit(-1-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++ ) { }

    int iDigit;
    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' )
            iDigit = sNum[j]-'0';
        else
            iDigit = sNum[j]-'a'+10;
        if( iDigit < 0 || iDigit >= iRadix )
            throw Bu::ExceptionBase(Bu::String(
                "Invalid character '%1' in Number::set").arg(sNum[j]).
                    end().getStr()
                );
        aInt.append( iDigit );
    }

    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' )
                iDigit = sNum[j]-'0';
            else
                iDigit = sNum[j]-'a'+10;
            
            if( iDigit < 0 || iDigit >= iRadix )
                throw Bu::ExceptionBase(Bu::String(
                    "Invalid character '%1' in Number::set").arg(sNum[j]).
                        end().getStr()
                    );
            aFrac.set( iFrac++, iDigit );
            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;
}

void Number::set( int32_t iNum )
{
    aFrac.zero();
    aInt.clear();
    while( iNum > 0 )
    {
        aInt.append( iNum%iRadix );
        iNum /= iRadix;
    }
}

void Number::divide( const Number &rhs, Number &q, Number &r ) const
{
    if( rhs.isZero() )
    {
        q = rhs;
        // This should be infinity (or negative infinity?)
        // but we don't support that yet.  Still have to figure that bit out.
        r.set( 0 );
        return;
    }
    if( isZero() )
    {
        q = *this;
        r.set( 0 );
        return;
    }

    DBS( DIVIDE, Bu::println("divide: %1 / %2").arg( *this ).arg( rhs ) );

    // iNumShift is how many digits we've shifted the entire equation,
    // effectively multiplying the numerator and divisor by iRadix*iNumShift
    int iNumShift = rhs.getEffectiveScale();
    DBS( DIVIDE, Bu::println("iNumShift = %1").arg( iNumShift ) );

    // Setup our divisor, this is important, it should be an integer to make
    // things easy, and it won't change once we create it.
    Number nDiv( 0, iRadix );
    for( int j = -iNumShift; j < rhs.aInt.getSize(); j++ )
    {
        DBS( DIVIDE, Bu::println("  -> '%1'").arg( rhs.digit( j ) ) );
        nDiv.aInt.append( rhs.digit( j ) );
    }
    nDiv.aInt.trim();
    DBS( DIVIDE, Bu::println("New divisor: %1").arg( nDiv ) );

    // Anchor is the position in the output the new digit will appear.
    // This also tells us where the ones place will be in our new numerator.
    int iAnchor = (aInt.getSize()+iNumShift)-nDiv.aInt.getSize();
    DBS( DIVIDE, Bu::println("Anchor: %1").arg( iAnchor ) );
    
    // Setup our output variables
    q.iRadix = r.iRadix = iRadix;
    q.iScale = r.iScale = iScale;
    q.bPositive = !(!bPositive ^ !rhs.bPositive);
    r.bPositive = true;
    q.aInt.clear();
    r.aInt.clear();
    if( q.aFrac.getSize() != iScale )
        q.aFrac = PackedIntArray( aFrac.getBitWidth(), iScale );
    if( r.aFrac.getSize() != iScale )
        r.aFrac = PackedIntArray( aFrac.getBitWidth(), iScale );

    // We seed the numerator with the bare minimum data that we potentially
    // need to actually divide. We need at least as many digits in the
    // numerator segment as we have in the denominator.
    Number nNum( iScale, iRadix );
    for( int j = iAnchor-iNumShift;
        nNum.aInt.getSize() < nDiv.aInt.getSize(); j++ )
    {
        DBS( DIVIDE, Bu::println("  ->[%1] '%2'").arg( j ).arg( digit(j) ) );
        nNum.aInt.append( digit( j ) );
    }
    nNum.aInt.trim();
    DBS( DIVIDE, Bu::println("New numerator: %1").arg( nNum ) );
    while( iAnchor >= -iScale && (!nNum.isZero() || iAnchor > 0)) // division loop
    {
        // As long as the numerator is smaller than the divisor we keep
        // including new digits.
        while( nNum.aInt.getSize() < nDiv.aInt.getSize() ||
               nNum < nDiv )
        {
            iAnchor--;
            int iDig = digit(iAnchor-iNumShift);
            if( nNum.aInt.getSize() == 0 && iDig == 0 )
            {
                if( iAnchor < -iScale )
                    break;
                continue;
            }
            nNum.aInt.insert( 0, iDig );
            DBS( DIVIDE, Bu::println("Numerator too small, new numerator: %1").arg( nNum ) );
        }

        DBS( DIVIDE, Bu::println("  New anchor: %1 vs iScale = %2").arg( iAnchor ).arg( iScale ) );
        if( iAnchor < 0 && -1-iAnchor >= iScale )
            break;
        
        // How many times does the divisor fit into the numerator
        int iCount = 0;
        for(;nNum >= nDiv; iCount++ )
        {
            DBS( DIVIDE, Bu::print(" ==> step %3: %1 - %2 = ").arg( nNum ).arg( nDiv ).arg( iCount ) );
            nNum = nNum - nDiv;
            DBS( DIVIDE, Bu::println("%1").arg( nNum ) );
        }
        DBS( DIVIDE, Bu::println("Total steps: %1").arg( iCount ) );

        if( iAnchor >= 0 )
        {
            while( q.aInt.getSize() <= iAnchor )
                q.aInt.append( 0 );
            q.aInt.set( iAnchor, iCount );
        }
        else
        {
            while( q.aFrac.getSize() <= -1-iAnchor )
                q.aFrac.append( 0 );
            q.aFrac.set( -1-iAnchor, iCount );
        }
    }
//    if( iAnchor <= 0 )
    {
        for( int j = -iAnchor; j < nNum.aInt.getSize(); j++ )
            r.aInt.append( nNum.aInt[j] );
        int jtop = 0;
        for(; nNum.aInt[jtop] == 0; jtop++ ) { }
        DBS( DIVIDE, Bu::println("Computing remainder fraction from %1 to %2")
            .arg( -iAnchor-1 ).arg( jtop ) );
        r.aFrac.clear();
        for( int j = -iAnchor-1, k = 0; j >= jtop && k < r.iScale; j--, k++ )
        {
            if( j < nNum.aInt.getSize() )
            {
                r.aFrac.set( k, nNum.aInt[j] );
                DBS( DIVIDE, Bu::println("setting %1 to %2").arg( k ).arg( nNum.aInt[j] ) );
            }
        }
    }
//    else
//    {
//        Bu::println("iAnchor: %1").arg( iAnchor );
//    }
    DBS( DIVIDE, Bu::println("Quotient: %1").arg( q ) );
    DBS( DIVIDE, Bu::println("Final numerator? %1").arg( nNum ) );
    DBS( DIVIDE, Bu::println("Remainder? %1").arg( r ) );
}

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::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];
}

void Number::setDigit( int iIdx, int iVal )
{
    if( iIdx < 0 )
    {
        if( iIdx >= -iScale )
            aFrac.set( -1-iIdx, iVal );
        return;
    }
    if( iIdx >= aInt.getSize() )
        return;
    aInt.set( iIdx, iVal );
}

void Number::setScale( int iNewScale )
{
    if( iNewScale == 0 )
        aFrac.clear();
    else if( iScale == iNewScale )
        return;
    else if( iScale < iNewScale )
    {
        while( aFrac.getSize() < iNewScale )
            aFrac.append(0);
    }
    else
    {
        while( aFrac.getSize() > iNewScale )
            aFrac.remove();
    }
    iScale = iNewScale;
}

int Number::getEffectiveScale() const
{
    if( iScale == 0 )
        return 0;
    int iSigDig = iScale-1;
    for( ; iSigDig >= 0 && aFrac.get( iSigDig ) == 0; iSigDig-- ) { }
    return iSigDig+1;
}

int32_t Number::toInt32() const
{
    int32_t ret = 0;
    int32_t ord = 1;
    for( int j = 0; j < aInt.getSize(); j++ )
    {
        ret += ord * aInt.get( j );
        ord *= iRadix;
    }
    return ret;
}

Number Number::toRadix( int iNewRadix, int iNewScale ) const
{
    if( iNewScale < 0 )
        iNewScale = iScale;
    Number ret( iNewScale, iNewRadix );

    Number me( 0, iRadix );
    me = *this;
    Number n( 0, iRadix );
    n.set( iNewRadix );
    while( !me.isZero() )
    {
//        Bu::println("%1 %% %2 = %3").arg( me ).arg( n ).arg( me%n );
        int dig = (me%n).toInt32();
        ret.aInt.append( dig );
        me = me / n;
//        Bu::println("New digit: %1 (%2)").arg( dig ).arg( me );
    }

    return ret;
}

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

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

    int iZeros = 0;
    int iCarry = 0;
    DBS( ADD, 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 );
            DBS( ADD,
            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;
        DBS( ADD, 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;
            if( iRes < iRadix )
            {
                iCarry = 0;
            }
            else
                iCarry = iRes/iRadix;

            DBS( ADD,
            Bu::println(" Place: %1 + %2 + (%3) = %4").
                arg( digit(j) ).arg( iComp-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( iCarry == 0 )
        {
            ret.bPositive = false;
            int iVal = iComp-ret.digit( -ret.iScale )+1;
            iCarry = (iVal >= iRadix) ? 1 : 0;
            ret.setDigit( -ret.iScale, iVal%iRadix );

            for( int j = -iScale+1; j < ret.aInt.getSize(); j++ )
            {
                iVal = iComp-ret.digit( j )+iCarry;
                iCarry = (iVal >= iRadix) ? 1 : 0;
                ret.setDigit( j, iVal%iRadix );
            }
        }
        ret.aInt.trim();
    }

    return ret;
}

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