// $Id: bignum.cc,v 1.3 2006-10-11 11:12:38 cactus Exp $ -*- c++ -*-

#include "bignum.h"

Bignum::Bignum ():
    n (0),
    d (0)
{
}

Bignum::Bignum (size_t n_):
    n (0),
    d (new digit_t[n_])
{
}

Bignum::~Bignum()
{
    delete[] d;
}

Bignum::Bignum (const Bignum &that):
    n (that.n),
    d (new digit_t[n])
{
    for (size_t i = 0; i != n; ++i)
        d[i] = that.d[n];
}

Bignum& Bignum::operator= (const Bignum &that)
{
    if (this == &that) return *this;

    delete[] d;

    n = that.n;
    d = new digit_t[n];
    for (size_t i = 0; i != n; ++i)
        d[i] = that.d[i];

    return *this;
}

bool operator== (const Bignum &x, const Bignum &y)
{
    if (&x == &y) return true;

    if (x.n != y.n) return false;    
    for (size_t i = 0; i != x.n; ++i)
        if (x.d[i] != y.d[i]) return false;

    return true;
}

bool operator< (const Bignum &x, const Bignum &y)
{
    if (&x == &y) return false;
    
    if (x.n != y.n) return x.n < y.n;

    for (size_t i = x.n; i != 0; --i)
        if (x.d[i - 1] != y.d[i - 1]) return x.d[i - 1] < y.d[i - 1];

    return false;
}

Bignum::Bignum (const std::string &s):
    n(0),
    d(new digit_t[s.size()])
{
    int k;
    for (k = 0; k != s.size () && s[k] == '0'; ++k);   
    
    n = s.size () - k;
    for (unsigned int i = 0; i != s.size () - k; ++i)
        d[n - (i + 1)] = digit_from_char (s[k + i]);
}

Bignum::digit_t Bignum::digit_from_char (char c)
{
    if (!('0' <= c && c <= '9')) throw std::bad_cast();
    return c - '0';
}

Bignum::digit_t Bignum::truncate_digit (digit_t a_plus_b, digit_t &overflow)
{    
    overflow = a_plus_b / 10;
    return a_plus_b % 10;
}

Bignum operator+ (const Bignum &x, const Bignum &y)
{
    Bignum z (std::max(x.n, y.n) + 1);

    Bignum::digit_t overflow = 0;
    
    size_t i = 0;
    for (; i < x.n || i < y.n; ++i)
    {
        if (i < x.n && i < y.n)
            z.d[i] = Bignum::truncate_digit (x.d[i] + y.d[i] + overflow, overflow);
        else if (i < x.n)
            z.d[i] = Bignum::truncate_digit (x.d[i] + overflow, overflow);
        else if (i < y.n)
            z.d[i] = Bignum::truncate_digit (y.d[i] + overflow, overflow);   
    }

    if (overflow)
        z.d[i++] = overflow;

    z.n = i;
    
    return z;
}

Bignum operator* (const Bignum &x, const Bignum &y)
{
    Bignum z;

    for (size_t i = 0; i != x.n; ++i)
    {
        Bignum tmp (y.n + i + 1);
        tmp.n = y.n + i;        
        
        Bignum::digit_t overflow = 0;
        
        for (size_t j = 0; j != y.n; ++j)
            tmp.d[j + i] = Bignum::truncate_digit (x.d[i] * y.d[j] + overflow, overflow);

        if (overflow)
            tmp.d[tmp.n++] = overflow;

        z += tmp;
    }
    
    return z;
}

Bignum Bignum::operator+= (const Bignum &y)
{
    *this = *this + y;
    return *this;
}

Bignum Bignum::operator*= (const Bignum &y)
{
    *this = *this * y;
    return *this;
}

std::string Bignum::str () const
{
    if (n == 0)
        return "0";
    
    std::string s = "";
    s.reserve (n);

    for (unsigned int i = n; i; --i)
    {
        s += '0' + d[i - 1];
    }

    return s;
}

#include <iostream>

std::ostream& operator<< (std::ostream &ostr, const Bignum &bignum)
{
    ostr << bignum.str ();
    return ostr;
}

std::istream& operator>> (std::istream &istr, Bignum &bignum)
{
    std::string str;
    istr >> str;
    if (istr)
        try
        {
            bignum = Bignum (str);
        }
        catch (std::bad_cast &e)
        {
            istr.setstate (std::istream::failbit);
        }    
    return istr;
}