#include "stdafx.h"
#include "CIntegerZ.h"

// 0  <===> +0,     -0 不合法
int CIntegerZ::maxlen = MAX_CINTEGERZ_IP_LENGTH;   // 高精度數組長度
int CIntegerZ::nlen   = MAX_CINTEGERZ_IP_LENGTH-1; // 高精度數字最大長度
int CIntegerZ::rrrr   = 10000;   // 不可太大——乘法越界
int CIntegerZ::rlen   = 4;       // 10^n 進位制在此確定

CIntegerZ::CIntegerZ()
{
        memset( ip, 0, sizeof(int)*maxlen );
        ip[0] = bPositive = 1;
}

CIntegerZ::CIntegerZ( int n )
{
        *this = n;
}

CIntegerZ::CIntegerZ( string &s )
{
        *this = s;
}

CIntegerZ::CIntegerZ( char *pc )
{
        string s = pc;
        *this = s;
}

CIntegerZ::~CIntegerZ()
{
}

//  n == 0                                                ////////////////////////
CIntegerZ CIntegerZ::operator=( int n )
{
        memset( ip, 0, sizeof(int)*maxlen );
        if( n < 0 )
        {
                n = -n;
                bPositive = 0;
        }
        else
        {
                bPositive = 1;
        }
        if( n == 0 ) ip[0] = 1;
        while( n )
        {
                ip[++ip[0]]  = n % rrrr;
                n           /= rrrr;
        }
        return *this;
}

// s == "0",  "-0", "0000", "-0000", "0000123", "-00021", "f;aief"  ////////////////
// "++--", "+", "-", "+0", "+143"
CIntegerZ CIntegerZ::operator=( string &s )
{
        memset( ip, 0, maxlen*sizeof(int) );
        ip[0] = 1;
        bPositive = 1;

        int i, j, n=0, con;
        for( i=s.length()-1; i>=0; --i )
        {
                if( (s[i]<'0') || ('9'<s[i]) ) break;
                ++n;
        }
        if( (i>0) || (n==0) )
        {
                return *this;
        }
        
        if( s[0] == '+' )
        {
                s.erase( 0, 1 );
        }
        if( s[0] == '-' )
        {
                bPositive = 0;
                s.erase( 0, 1 );
        }
        if( (s[0]<'0') || ('9'<s[0]) )
        {
                return *this;
        }
        while( (s[0]=='0') && (s.length()>0) ) s.erase( 0, 1 );
        if( s.length() == 0 )
        {
                bPositive = 1;
                return *this;
        }

        con = 1;
        ip[0] = 0;
        for( i=s.length()-rlen; con; i=i-rlen )
        {
                for( con=((j=i)>0); j<0; ++j )
                        ;
                n = 0;
                for( ; j<i+rlen; ++j )
                {
                        n = n * 10 + s[j] - '0';
                }
                ip[++ip[0]] = n;
        }
        return *this;
}

CIntegerZ CIntegerZ::operator=( char *pc )
{
        string s = pc;
        return *this = s;
}

CIntegerZ CIntegerZ::Abs( void )
{
        CIntegerZ c(*this);
        c.bPositive = 1;
        return c;
}

CIntegerZ CIntegerZ::NegativeAbs( void )
{
        CIntegerZ c(*this);
        if( (c.ip[0]==1) && (c.ip[1]==0) )
        {
                c.bPositive = 1;
        }
        else
        {
                c.bPositive = 0;
        }
        return c;
}

string CIntegerZ::CIntZ2Str( void )
{
        string s;
        if( bPositive )
        {
                s = "+";
        }
        else
        {
                s = "-";
        }

        string ts = "";
        int i, k, n;

        n = ip[ip[0]];
        do
        {
                ts += char( n % 10 + '0' );
                n  /= 10;
        }while( n );
        for( i=ts.length()-1; i>=0; --i )
                s += ts[i];

        for( i=ip[0]-1; i>0; --i )
        {
                n = ip[i];
                ts = "0000000";
                k = rlen;
                while( n )
                {
                        ts[--k]  = char( n % 10 + '0' );
                        n       /= 10;
                }
                s += ts.substr( 0, rlen );
        }
        return s;
}

int operator>( CIntegerZ &a, CIntegerZ &b )
{
        return !( a <= b );
}

int operator>( int n,        CIntegerZ &b )
{
        return !( CIntegerZ(n) <= b );
}

int operator>( CIntegerZ &a, int n        )
{
        return !( a <= CIntegerZ(n) );
}

int operator<( CIntegerZ &a, CIntegerZ &b )
{
        return !( a >= b );
}

int operator<( int n,         CIntegerZ &b )
{
        return !( CIntegerZ(n) >= b );
}

int operator<( CIntegerZ &a, int n        )
{
        return !( a >= CIntegerZ(n) );
}

int operator==( CIntegerZ &a, CIntegerZ &b )
{
        if( a.ip[0] != b.ip[0] ) return 0;
        if( a.bPositive != b.bPositive ) return 0;
        
        for( int i=a.ip[0]; i>0; --i )
        {
                if( a.ip[i] != b.ip[i] ) return 0;
        }

        return 1;
}

int operator==( int n,         CIntegerZ &b )
{
        return CIntegerZ(n) == b;
}

int operator==( CIntegerZ &a, int n        )
{
        return a == CIntegerZ(n);
}

int operator>=( CIntegerZ &a, CIntegerZ &b )
{
        if( a.bPositive )
        {
                if( !b.bPositive )      return 1;
                if( a.ip[0] > b.ip[0] ) return 1;
                if( a.ip[0] < b.ip[0] ) return 0;
        }
        else
        {
                if( b.bPositive )       return 0;
                if( a.ip[0] > b.ip[0] ) return 0;
                if( a.ip[0] < b.ip[0] ) return 1;
        }
        
        for( int i=a.ip[0]; i>0; --i )
        {
                if( a.ip[i] > b.ip[i] ) return a.bPositive;
                if( a.ip[i] < b.ip[i] ) return !a.bPositive;
        }

        return 1;
}

int operator>=( int n,         CIntegerZ &b )
{
        return CIntegerZ(n) >= b;
}

int operator>=( CIntegerZ &a, int n        )
{
        return a >= CIntegerZ(n);
}

int operator<=( CIntegerZ &a, CIntegerZ &b )
{
        if( a.bPositive )
        {
                if( !b.bPositive )      return 0;
                if( a.ip[0] > b.ip[0] ) return 0;
                if( a.ip[0] < b.ip[0] ) return 1;
        }
        else
        {
                if( b.bPositive )       return 1;
                if( a.ip[0] > b.ip[0] ) return 1;
                if( a.ip[0] < b.ip[0] ) return 0;
        }
        
        for( int i=a.ip[0]; i>0; --i )
        {
                if( a.ip[i] > b.ip[i] ) return !a.bPositive;
                if( a.ip[i] < b.ip[i] ) return a.bPositive;
        }

        return 1;

}

int operator<=( int n,         CIntegerZ &b )
{
        return CIntegerZ(n) <= b;
}

int operator<=( CIntegerZ &a, int n        )
{
        return a <= CIntegerZ(n);
}

CIntegerZ operator+( CIntegerZ &a, CIntegerZ &b )
{
        CIntegerZ c;
        if( a.bPositive == b.bPositive )
        {
                int i, l=a.ip[0], g=0;
                if( l < b.ip[0] ) l = b.ip[0];
                for( i=1; i<=l; ++i )
                {
                        g       += a.ip[i] + b.ip[i];
                        c.ip[i]  = g % CIntegerZ.rrrr;
                        g       /= CIntegerZ.rrrr;
                }
                while( g )
                {
                        c.ip[++l]  = g % CIntegerZ.rrrr;
                        g         /= CIntegerZ.rrrr;
                }
                c.ip[0] = l;
                c.bPositive = a.bPositive;
                return c;
        }

        if( a.bPositive )
        {
                c = b;
                c.bPositive = 1;
                return a - c;
        }

        c = a;
        c.bPositive = 1;
        return b - c;
}

CIntegerZ operator+( int n,         CIntegerZ &b )
{
        return CIntegerZ(n) + b;
}

CIntegerZ operator+( CIntegerZ &a, int n        )
{
        return a + CIntegerZ(n);
}

CIntegerZ operator-( CIntegerZ &a, CIntegerZ &b )
{
        CIntegerZ c;
        if( a.bPositive == b.bPositive )
        {
                int i, l, bPos=a.bPositive;
                a.bPositive = b.bPositive = 1;
                if( a >= b )
                {
                        c.bPositive = bPos;
                        l = a.ip[0];
                        for( i=1; i<=l; ++i )
                                c.ip[i] = a.ip[i] - b.ip[i];
                }
                else
                {
                        c.bPositive = !bPos;
                        l = b.ip[0];
                        for( i=1; i<=l; ++i )
                                c.ip[i] = b.ip[i] - a.ip[i];
                }
                for( i=1; i<l; ++i )
                {
                        if( c.ip[i] < 0 )
                        {
                                c.ip[i]   += CIntegerZ.rrrr;
                                c.ip[i+1] -= 1;
                        }
                }
                a.bPositive = b.bPositive = bPos;
                while( (c.ip[l]==0) && (l>1) ) --l;
                c.ip[0] = l;
                if( (c.ip[0]==1) && (c.ip[1]==0) ) c.bPositive = 1;
                return c;
        }

        if( a.bPositive )
        {
                c = b;
                c.bPositive = 1;
                return a + c;
        }

        c = b;
        c.bPositive = 0;
        return a + c;
}

CIntegerZ operator-( int n,         CIntegerZ &b )
{
        return CIntegerZ(n) - b;
}

CIntegerZ operator-( CIntegerZ &a, int n       )
{
        return a - CIntegerZ(n);
}

CIntegerZ operator*( CIntegerZ &a, CIntegerZ &b )
{
        CIntegerZ c;
        if( (a==0) || (b==0) ) return c;

        int la=a.ip[0], lb=b.ip[0], i, j;
        for( i=1; i<=la; ++i )
        for( j=1; j<=lb; ++j )
        {
                c.ip[i+j-1] += a.ip[i] * b.ip[j];
                c.ip[i+j]   += c.ip[i+j-1] / CIntegerZ.rrrr;
                c.ip[i+j-1] %= CIntegerZ.rrrr;
        }
        c.ip[0] = i + j;
        while( (c.ip[c.ip[0]]==0) && (c.ip[0]>1) ) c.ip[0] -= 1;
        c.bPositive = ( a.bPositive == b.bPositive );
        return c;
}

CIntegerZ operator*( int n,         CIntegerZ &b )
{
        return CIntegerZ(n) * b;
}

CIntegerZ operator*( CIntegerZ &a, int n        )
{
        return a * CIntegerZ(n);
}

CIntegerZ operator/( CIntegerZ &a, CIntegerZ &b )
{
        CIntegerZ c;
        if( a == 0 ) return c;

        int bPos_a = a.bPositive, bPos_b = b.bPositive;
        a.bPositive = b.bPositive = 1;

        if( a < b )
        {
                a.bPositive = bPos_a;
                b.bPositive = bPos_b;
                return c;
        }

        int i, j, k, n;
        c.ip[0] = a.ip[0] - b.ip[0] + 1;
        for( i=c.ip[0]; i>0; --i )
        {
                n = 0;
                for( k=CIntegerZ.rrrr/10; k>0; k/=10 )
                {
                        for( j=9*k; j>=0; j-=k )
                        {
                                c.ip[i] = n + j;
                                if( c * b <= a )
                                {
                                        n += j;
                                        break;
                                }
                        }
                }
                c.ip[i] = n;
        }

        while( (c.ip[c.ip[0]]==0) && (c.ip[0]>1) ) c.ip[0] -= 1;
        a.bPositive = bPos_a;
        b.bPositive = bPos_b;
        c.bPositive = ( bPos_a == bPos_b );
        return c;
}

CIntegerZ operator/( int n,         CIntegerZ &b )
{
        return CIntegerZ(n) / b;
}

CIntegerZ operator/( CIntegerZ &a, int n        )
{
        return a / CIntegerZ(n);
}

CIntegerZ operator%( CIntegerZ &a, CIntegerZ &b )
{
        return  a - ( ( a / b ) * b );
}

CIntegerZ operator%( int n,         CIntegerZ &b )
{
        return CIntegerZ(n) % b;
}

CIntegerZ operator%( CIntegerZ &a, int n        )
{
        return a % CIntegerZ(n);
}