//alias size_t BigDigit;
alias ulong BigDigit;

// appends digit onto the current digits, which may allocate
// this frees up old memory in the case of an allocation
private void append( inout BigDigit[] digits, BigDigit digit )
{
    BigDigit* oldPtr = digits.ptr;
    digits ~= digit;
    if ( oldPtr !is digits.ptr )
        delete oldPtr[0..(digits.length - 1)];
}

public class BigNum
{
    // The least significant digit is the zeroth digit.  
    private BigDigit[] digits;
    private bool m_negative = false;
    
    public bool negative() { return m_negative; }
    public bool positive() { return !m_negative; }
    
    this()
    {
        digits = new BigDigit[1];
    }
    
    this( int input )
    {
        digits = new BigDigit[1];
        // TODO: what if size_t is less than 32 bits long?
        digits[0] = input & 0x7FFFFFFF;
        m_negative = cast(bool)((input & 0x80000000) >> 31);
    }
    
    this( uint input )
    {
        digits = new BigDigit[1];
        // TODO: what if size_t is less than 32 bits long?
        digits[0] = input;
    }
    
    this( BigDigit[] numberToUse, bool Negative )
    {
        digits = numberToUse;
        m_negative = Negative;
        
        // if the most significant digit is 0, we need to lose it
        uint shrink = 0;
        for ( int i = digits.length - 1; i >= 0; i-- )
        {
            if ( digits[i] == 0 )
                shrink++;
            else
                break;
        }
        digits.length = digits.length - shrink;
    }
    
    ~this()
    {
        delete digits;
    }
    
    BigNum opNeg()
    {
        m_negative = !m_negative;
        return this;
    }
    
    private int unsignedOpCmp( BigNum that )
    {
        if ( this.digits.length > that.digits.length )
            return 1;
        else if ( this.digits.length < that.digits.length )
            return -1;
        else // ( this.digits.length == that.digits.length )
        {
            BigDigit[] digits1 = this.digits;
            BigDigit[] digits2 = that.digits;
            for( uint i = digits1.length - 1;
                 i >= 0; i-- )
            {
                if ( digits1[i] > digits2[i] )
                    return 1;
                else if ( digits1[i] < digits2[i] )
                    return -1;
            }
            
            return 0;
        }
    }
    
    int opCmp( BigNum that )
    {
        if ( this.negative )
        {
            if ( that.negative )
                // both negative, unsignedOpCmp treats them as positive, so reverse the result
                return -unsignedOpCmp( that );
            else
                // this is negative and that is positive, so this is less than that.
                return -1;
        }
        else
        {
            if ( that.negative )
                // this is positive and that is negative, so this is greater than that.
                return 1; 
            else
                // both positive
                return unsignedOpCmp( that );
        }
    }
    
    bool unsignedEquals( BigNum that )
    {
        if ( this.digits.length != that.digits.length )
            return false;
        else
        {
            BigDigit[] digits1 = this.digits;
            BigDigit[] digits2 = that.digits;
            uint len = digits1.length;
            for( uint i = 0; i < len; i++ )
            {
                if ( digits1[i] != digits2[i] )
                    return false;
            }
            
            return true;
        }
    }
    
    int opEquals( BigNum that )
    {
        if ( this.negative )
        {
            if ( that.negative )
                return unsignedEquals( that );
            else
                return false;
        }
        else
        {
            if ( that.negative )
                return false;
            else
                // both positive
                return unsignedEquals( that );
        }
    }
    
    // used by opAdd (or opSub if you subtract a negative)
    private BigNum add( BigNum number1, BigNum number2 )
    {
        BigDigit[] shorter;
        BigDigit[] longer;
        
        if ( number1.digits.length < number2.digits.length )
        {
            shorter = number1.digits;
            longer = number2.digits;
        }
        else
        {
            shorter = number2.digits;
            longer = number1.digits;
        }
        
        BigDigit[] result = new BigDigit[longer.length];
        
        // msd is the Most Significant Digit
        uint msd = shorter.length - 1;
        for ( uint i = 0; i < msd; i++ )
        {
            result[i] = shorter[i] + longer[i];
            
            // check for non-overflow
            
            if ( result[i] >= longer[i] )
                continue;
            
            if ( result[i] >= shorter[i] )
                continue;
            
            // it overflowed, carry the one.
            result[i+1] = 1;
        }
        
        // handle possible overflow at the end
        result[msd] = shorter[msd] + longer[msd];
        if ( shorter.length == result.length )
        {
            // handle overflow at the end
            if ( result[msd] < longer[msd] || result[msd] < shorter[msd] )
                append( result, 1 );
            
            goto the_end;
        }
        else
        {
            if ( result[msd] < longer[msd] || result[msd] < shorter[msd] )
                result[msd+1] = 1;
        }
        
        msd = result.length - 1;
        for ( uint i = shorter.length; i < msd; i++ )
        {
            result[i] += longer[i];
            
            // check for overflow
            if ( result[i] < longer[i] )
                result[i+1] = 1;
        }
        
        // handle possible overflow at the end
        result[msd] += longer[msd];
        if ( result[msd] < longer[msd] )
            append( result, 1 );
        
      the_end:
        
        if ( number1.negative )
            return new BigNum( result, true );
        else
            return new BigNum( result, false );
    }
    
    private void addAssign( BigNum that )
    {
    
    }
    
    // used by opSub (or opAdd if you add a negative)
    // subtracts number2 from number1
    private BigNum subtract( BigNum number1, BigNum number2 )
    {
        BigDigit[] smaller;
        BigDigit[] bigger;
        bool neg;
        
        switch( number1.unsignedOpCmp( number2 ) )
        {
            case -1:
                smaller = number1.digits;
                bigger = number2.digits;
                neg = true;
                break;
            case 0:
                
                return new BigNum();
            case 1:
                smaller = number2.digits;
                bigger = number1.digits;
                neg = false;
                break;
            default:
                assert(0);
        }
        
        BigDigit[] result = new BigDigit[bigger.length];
        
        uint length = bigger.length;
        for ( uint i = 0; i < length; i++ )
        {
            result[i] = bigger[i] - smaller[i];
            
            if ( result[i] > bigger[i] ) // oh crap, an underflow!
                result[i+1]--; // borrow a one
        }
        
        return new BigNum( result, neg );
    }
    
    BigNum opAdd( BigNum that )
    {
        BigNum result;
        bool neg; //negative
        if ( this.positive && that.negative ) // this + -that = this - that
            result = subtract( this, that );
        else if ( that.positive && this.negative ) // that + -this = that - this
            result = subtract( that, this );
        else
            result = add( this, that );
        
        return result;
    }
    
    BigNum opSub( BigNum that )
    {
        BigNum result;
        if ( this.positive && that.positive )
            result = subtract( this, that );
        else if ( this.negative && that.negative ) // -a - -b = -a + b = b - a
            result = subtract( that, this );
        else
            result = add( this, that );
        
        return result;
    }
    
    void opAddAssign( BigNum that )
    {
        
    }
    
    // for some reason 'static if else' gave compiler...
    static if ( BigDigit.sizeof != 4 && BigDigit.sizeof != 8 )
        static assert(0);
    
    static if ( BigDigit.sizeof == 4  )
        const shift = 3;
    static if ( BigDigit.sizeof == 8 )
        const shift = 4;
    
    // radix currently ignored
    char[] toString( uint radix = 16 )
    {
        static char[16] charmap = "0123456789ABCDEF";
        
        size_t allocSize = (digits.length << shift) + m_negative;
        
        char[] result = new char[allocSize];
        size_t index = 0;
        
        if ( m_negative )
        {
            result[index] = '-';
            index++;
        }
        
        for ( int i = digits.length - 1; i >= 0; i-- )
        {
            BigDigit digit = digits[i];
            ubyte remainder;
            const start = (BigDigit.sizeof << 1) - 1;
            
            for ( int j = start; j >= 0; j-- )
            {
                remainder = digit & 0x0f;
                
                result[index + j] = charmap[remainder];
                
                digit >>= 4;
            }
            index += BigDigit.sizeof << 1; // number of hex digits in a big digit
        }
        
        return result;
    }
}

import std.stdio;

unittest
{
    static ulong[2] one   = [0xffffffffffffffff,0xffffffffffffffff];
    static ulong[1] two   = [0x00000000ffffffff];
    static ulong[3] three = [0x00000000fffffffe,0x0000000000000000,0x0000000000000001];
    
    BigNum n = new BigNum( cast(BigDigit[])one, false );
    BigNum m = new BigNum( cast(BigDigit[])two, false );
    BigNum o = new BigNum( cast(BigDigit[])three, false );
    
    assert ( o == n + m );
}