/*******************************************************************************
        
        copyright:      Copyright (c) 2007  (yidabu  g m a i l at com) All rights reserved

        license:        BSD style: $(LICENSE)

        version:        Initial release: 2007

        author:         modified by yidabu ( D China : http://bbs.yidabu.com/forum-10-1.html )
        original post:  http://www.fenglin.info/gen_ex/53/Algorithm/323345.html

*******************************************************************************/

module dwin.lab.Bignumer;


import tango.text.convert.Integer;
debug( UnitTest ) import tango.util.log.Trace;  

class Bignumer 
{ 
public: 
    enum{BASELEN = 3,BASE = 1_000}; 
    enum{MAX = 100};      //i'm thinking change this to dynamic array if  possible.... 
    uint data[MAX];   //initialize as 0 
    uint len;         //initialize as 0  
    int  sign;        //initialize as 0   ; 0: positive; 1: negative 
	
    this (Bignumer b){ 
        Assign(b); 
    } 
    void Assign(Bignumer b) 
    { 
        len = b.len; 
        sign = b.sign; 
        data[]=b.data[]; 
    } 
    this(int num = 0){                 
        if(num == 0){len = 1;return;} 
        if(num < 0){ 
            sign = 1; 
            num = -num; 
        }        
        while(num > 0){            
            data[len++] = num % BASE; 
            num /= BASE; 
        } 
    } 
     
    this(char[] num){        
        if(num.length == 0) {len = 1;return;} 
        int beg = 0;       
        switch(num[0]){ 
			case '-': {sign = 1;}; 
			case '+': {++beg;} ;
			default : break; 
        } 
        int i = num.length - BASELEN; 
        for(; i >= beg; i -= BASELEN){     
            char[] tmp = num[i..i+BASELEN]; 
            data[len++] = atoi(tmp); 
            //data[len++] = std.conv.toUint(tmp); 
        } 
        i += BASELEN; 
        if(i>beg){ 
            char[] tmp = num[0..i]; 
            data[len++] = atoi(tmp); 
            //data[len++] = std.conv.toUint(tmp); 
        }        
    } 
     
    Bignumer opNeg() 
    { 
        Bignumer ret = new Bignumer(this); 
        ret.sign ^= 1; 
        return ret; 
    } 
         
    int opEquals(Bignumer b){ 
        if(sign != b.sign || len != b.len) return 0; 
        return data == b.data;         
    } 
     
    int absCmp(Bignumer b, Bignumer r){ 
        if(b.len>r.len) return 1; 
        else if(b.len<r.len) return 0;       
         
        for(int i = b.len-1;i >= 0; i--){ 
            if(b.data[i] > r.data[i]) 
                return 1; 
            else if(b.data[i] < r.data[i]) return 0; 
        } 
        return 0;        
    } 
     
    int opCmp(Bignumer b) 
    { 
        if(sign < b.sign) return 1; 
        else if(sign > b.sign) return 0;       
        if(sign == 0) return absCmp(this,b); 
        else return 1&absCmp(b,this);                
    } 
         
     // +
    Bignumer opAdd(Bignumer b) 
    {                                
        if(sign!=b.sign){ 
            b.sign ^= 1; 
            Bignumer ret = this-b; 
            b.sign ^= 1; 
            return ret; 
        }            
        Bignumer ret = new Bignumer(); 
        ret.sign = sign; 
        uint tmp = 0;      
        uint i; 
        for(i = 0; i<b.len && i<len; i++){ 
            ret.data[i]= (data[i] + b.data[i] + tmp) % BASE; 
            tmp = (data[i] + b.data[i] + tmp) / BASE;          
        }        
        void residual(uint len,uint data[]){ 
            for(;i < len; i++){ 
                ret.data[i] = (tmp + data[i]) % BASE; 
                tmp = (tmp + data[i]) / BASE;                       
     
            } 
        } 
        if(i < len) 
            residual(len, data);                              
        else if(i < b.len) 
            residual(b.len, b.data); 
        ret.len = i;       
        if(tmp) ret.data[ret.len++] = tmp;         
        return ret;      
    } 
         
	// -
    Bignumer opSub(Bignumer b) 
    {                                 
        if(sign != b.sign){ 
            b.sign ^= 1; 
            Bignumer ret = this + b;    
            b.sign ^= 1; 
            return ret; 
        } 
        Bignumer big,small; 
        Bignumer ret = new Bignumer(); 
        Bignumer absSub(Bignumer big,Bignumer small){  //assume big > small           
            int tmp = 0; 
            uint i;          
            ret.len = big.len; 
            for(i = 0;i<small.len&&i<big.len;i++){  
           
                uint t = small.data[i]+tmp; 
                tmp = (t>big.data[i]); 
                ret.data[i]=(BASE&(-tmp))+big.data[i]-t; 
            }                    
            for(;i<big.len;i++){ 
                uint t = tmp; 
                tmp = (t>big.data[i]); 
				ret.data[i]=(BASE&(-tmp))+big.data[i]-t;                    
     
            } 
            while(ret.data[ret.len-1] == 0&&ret.len>1) 
				ret.len--;      
            return ret; 
        }                    
        if(absCmp(this,b)){          
            big = this;small = b; 
            ret.sign = sign; 
        }else{           
            small = this;big = b; 
            ret.sign = sign^1; 
        }                                                
        return absSub(big,small); 
    } 
         
	// *
    Bignumer opMul(Bignumer b){ 
        Bignumer ret = new Bignumer; 
        ret.sign = (b.sign^sign); 
        ret.len = (len+b.len-1); 
        uint tmp = 0; 
         
        for(uint i = 0;i<len;i++){ 
            for(int j = 0;j<b.len;j++){ 
                int c;               
                c = (ret.data[i+j]+data[i]*b.data[j]+tmp)/BASE; 
                //writefln(data[i],",",b.data[j],"; ",data[i]*b.data[j]); 
                 
				ret.data[i+j]=(ret.data[i+j]+data[i]*b.data[j]+tmp)%BASE;       
         
                tmp = c; 
            }            
        }                
        if(tmp) 
            ret.data[ret.len++]=tmp; 
        while(ret.data[ret.len-1] == 0&&ret.len>1) ret.
			len--;  
        return ret; 
    } 
         
	// /
    Bignumer opDiv(Bignumer b){ 
        Bignumer ret = new Bignumer; 
        if( len < b.len) return ret;        
        ret.sign = (b.sign ^ sign);        
        ret.len = len-b.len+1; 
        Bignumer tmp = new Bignumer(this);       
        tmp >>= (len-b.len+1);         
        int i = len-b.len; 
        for(; i >= 0; i--){ 
            tmp <<= 1;             
            tmp = tmp + new Bignumer(data[i]); 
            Bignumer c2 = new Bignumer(b); 
            int j = 1; 
            for(; c2 <= tmp && j < BASE; j++, c2 = c2+b){};
			//very low  efficiency,use binary search will be better 
			j--; 
            ret.data[i]=j;                       
            tmp = (tmp-c2+b);          
        } 
        while(ret.data[ret.len-1] ==0 && ret.len > 1) ret.len--;  
        return ret; 
    } 
     
     
    Bignumer opAddAssign(Bignumer b) 
    { 
        Bignumer tmp = this + b; 
        Assign(tmp); 
        return this; 
    } 
     
    Bignumer opSubAssign(Bignumer b) 
    { 
        Bignumer tmp = this - b; 
        Assign(tmp); 
        return this; 
    } 
     
    Bignumer opMulAssign(Bignumer b) 
    { 
        Bignumer tmp = this * b; 
        Assign(tmp); 
        return this; 
    } 
    Bignumer opDivAssign(Bignumer b) 
    { 
        Bignumer tmp = this / b; 
        Assign(tmp); 
        return this; 
    } 
    Bignumer opShr(uint s) 
    { 
        Bignumer ret = new Bignumer(this); 
        ret>>=s; 
        return ret; 
    } 
     
    Bignumer opShrAssign(uint s){ 
        uint i; 
        for(i = 0;i<(len-s);i++) 
            data[i]=data[i+s];       
        for(;i<len;i++)data[i]=0; 
        len-=s; 
        return this; 
    } 
         
    Bignumer opShlAssign(uint s){ 
        assert(len+s<MAX); 
        int i;                       
        for(i = len-1;i>=0;i--)        
            data[i+s]=data[i];       
        for(i = 0;i<s;i++) data[i]=0; 
        len+=s; 
        return this; 
    } 
     
    Bignumer opShl(uint s) 
    { 
        Bignumer ret = new Bignumer(this); 
        ret<<=s; 
        return ret; 
    } 
     
    //char[] toString(){ 
    char[] toUtf8(){ 
        char[64] tmp;
        char[] ret; 
        if(sign) ret~="-"; 
        else     ret~="+"; 
        for(int i = len-1; i >= 0; i--){ 
            //ret~= .toString(data[i]) ~ ","; 
            ret ~= itoa(tmp, data[i] ) ~ ","; 
        } 
        //ret ~= "BASE:"~ .toString(BASE); 
        //ret ~= "BASE:"~ itoa(tmp, BASE); 
        return ret;      
    } 
} 


debug( UnitTest ) unittest
{ 
    auto a = new Bignumer("12345678901234567890123456789012345678901234567890");
    auto b = new Bignumer("12345678901234567890123456789012345678901234567890");
    auto c = a - b;
    Trace("a - b = ")( c.toUtf8() ).newline;
    c = a + b -b;
    Trace("a + b - b = ")( c.toUtf8() ).newline;
    c = a * b / b;      //lost data here!
    Trace("a * b / b = ")( c.toUtf8() ).newline;
    c = a / b * b;
    Trace("a / b * b = ")( c.toUtf8() ).newline;
         
}