// Arbitrarily large numbers
//
// Author  Matthew Caryl
// Created 13.3.97

#include <iostream.h>
#include "LargeNumber.H"

int maximum(int a, int b);
int minimum(int a, int b);
long pow(long a, long b);

const unsigned int BIT_INCREMENT = 32;

int maximum(int a, int b)
{
    return a > b ? a : b;
}

int minimum(int a, int b)
{
    return a < b ? a : b;
}

long pow(long a, long b)
{
    long a1 = a;
    long b1 = b;
    long c = 1;
    
    while (b1 >= 1)
        {
        while (b & 1 == 0)
            {
            b1 = b1 / 2;
            a1 = a1 * a1;
            }
        b1 = b1 - 1;
        c = c * a1;
        }
    return c;
}

void LargeNumber::contract()
{
    while (number[sig] == 0 && sig > 0)
        sig--;
}

LargeNumber::LargeNumber(void)
{
    number = new char[BIT_INCREMENT];
    number[0] = 0;
    negative = false;
    max = BIT_INCREMENT - 1;
    sig = 0;
}

LargeNumber::LargeNumber(long n)
{
    negative = n < 0 ? true : false;
    n = n < 0 ? -n : n; // strip of sign
    number = new char[BIT_INCREMENT];
    for (int i = 0; i < BIT_INCREMENT; i++)
        {
        number[i] = n & 1;
        n >>= 1;
        }
    max = BIT_INCREMENT - 1;
    sig = BIT_INCREMENT - 1;
    contract(); // remove leading 0s
}

LargeNumber::LargeNumber(const LargeNumber& n)
{
    number = new char[n.max + 1];
    negative = n.negative;
    max = n.max;
    sig = n.sig;
    for (int i = sig; i >= 0; i--)
        number[i] = n.number[i];
}

LargeNumber::~LargeNumber(void)
{
    delete number;
}

char LargeNumber::to_char(void) const
{
    return to_long();
}

short LargeNumber::to_short(void) const
{
    return to_long();
}

int LargeNumber::to_int(void) const
{
    return to_long();
}

long LargeNumber::to_long(void) const
{
    long n = 0;

    for (int i = sig; i >= 0; i--)
        {
        n <<= 1;
        n |= number[i];
        }
    if (negative)
        return -n;
    else
        return n;
}

bool LargeNumber::even(void) const
{
    return number[0] == 0;
}

bool LargeNumber::odd(void) const
{
    return number[0] == 1;
}

int LargeNumber::length(void) const
{
    return sig + 1;
}

bool LargeNumber::bit(unsigned int p) const
{
    if (p <= sig) // check if within current size
        return number[p];
    else
        return false;
}

bool LargeNumber::zero(void) const
{
    return (sig == 0 && number[0] == 0);
}

bool LargeNumber::sign(void) const
{
    return negative;
}

void LargeNumber::truncate(int n)
{
    if (n < 1) // either set to zero
        {
        sig = 0;
        number[0] = 0;
        negative = false;
        }
    else if (sig > n - 1) // or chop down
        {
        sig = n - 1;
        contract(); // may have revealed leading zeros
        }
}

void LargeNumber::complement(void)
{
    if (!zero()) // can't have negative zeros
        negative = !negative;
}

bool LargeNumber::operator==(const LargeNumber& n) const
{
    if (sig != n.sig) // check size
        return false;
    if (negative != n.negative) // check sign
        return false;
    for (int i = sig; i >= 0; i--)
        if (number[i] != n.number[i]) // check bits
            return false;
    return true;
}

bool LargeNumber::operator!=(const LargeNumber& n) const
{
    return !(*this == n);
}

bool LargeNumber::smaller(const LargeNumber& n) const
{
    if (sig < n.sig) // check size
        return true;
    else if (sig > n.sig) // check sign
        return false;
    for (int i = sig; i >= 0; i--)
        if (number[i] < n.number[i]) // check bits
            return true;
        else if (number[i] > n.number[i])
            return false;
    return false;
}

bool LargeNumber::greater(const LargeNumber& n) const
{
    if (sig > n.sig) // check size
        return true;
    else if (sig < n.sig) // check sign
        return false;
    for (int i = sig; i >= 0; i--)
        if (number[i] > n.number[i]) // check bits
            return true;
        else if (number[i] < n.number[i])
            return false;
    return false;
}

bool LargeNumber::operator<(const LargeNumber& n) const
{
    if (negative & !n.negative) // try to make judgement using signs
        return true;
    else if (!negative & n.negative)
        return false;
    else if (negative)
        return !smaller(n);
    else
        return smaller(n);
}

bool LargeNumber::operator<=(const LargeNumber& n) const
{
    return *this < n || *this == n;
}

bool LargeNumber::operator>(const LargeNumber& n) const
{
    return !(*this <= n);
}

bool LargeNumber::operator>=(const LargeNumber& n) const
{
    return !(*this < n);
}
    
void LargeNumber::expand(int n)
{
    if (n < sig) // don't need to expand
        return;
    if (max < n) // need to make a larger array
        {
        char* new_number = new char[n + 1];
        for (int i = sig; i >= 0; i--)
            new_number[i] = number[i];
        delete number;
        number = new_number;
        max = n;
        }
    for (int i = sig + 1; i <= max; i++) // zero top of array
        number[i] = 0;
    sig = n;
}

LargeNumber& LargeNumber::operator=(const LargeNumber& n)
{
    if (this == &n) // same object
        return *this;
    expand(n.sig); // make equal sizes
    sig = n.sig; // might have been larger
    for (int i = sig; i >= 0; i--)
        number[i] = n.number[i];
    negative = n.negative;
    return *this;
}

void LargeNumber::plus(const LargeNumber& n)
{
    int m = maximum(sig + 1, n.sig + 1);
    expand(m); // allow for overflow
    int i = 0;
    int carry = 0;
    for (; i <= n.sig; i++) // add overlap
        {
        carry += number[i] + n.number[i];
        number[i] = carry & 1;
        carry /= 2;
        }
    for (; carry != 0; i++) // continue with carry
        {
        carry += number[i];
        number[i] = carry & 1;
        carry /= 2;
        }
    contract();
}

void LargeNumber::minus(const LargeNumber& n)
{
    int m = maximum(sig, n.sig);
    expand(m);
    int i = 0;
    int carry = 0;
    for (; i <= n.sig; i++) // subtract overflow
        {
        carry += number[i] - n.number[i];
        number[i] = (carry + 2) & 1;
        carry = carry < 0 ? -1 : 0;
        }
    for (; carry != 0; i++) // continue with carry
        {
        carry += number[i];
        number[i] = (carry + 2) & 1;
        carry = carry < 0 ? -1 : 0;
        }
    contract();
}

LargeNumber& LargeNumber::operator+=(const LargeNumber& n)
{
    if ((negative ^ n.negative) == false) // cope with negatives
        this->plus(n);
    else
        {
        if (smaller(n))
            {
            LargeNumber m(*this);
            *this = n;
            minus(m);
            }
        else
            this->minus(n);
        if (zero())
            negative = false;
        }
    return *this;
}

LargeNumber& LargeNumber::operator-=(const LargeNumber& n)
{
    if ((negative ^ n.negative) == true) // cope with negatives
        this->plus(n);
    else
        {
        if (smaller(n))
            {
            LargeNumber m(*this);
            *this = n;
            minus(m);
            complement();
            }
        else
            this->minus(n);
        if (zero())
            negative = false;
        }
    return *this;
}

LargeNumber& LargeNumber::operator<<=(int n)
{
    if (n < 0) // avoid negatives
        {
        *this >>= -n;
        return *this;
        }
    expand(sig + n);
    for (int i = sig; i >= n; i--) // copy
        number[i] = number[i - n];
    for (int i = n - 1; i >= 0; i--) // then fill with 0s
        number[i] = 0;
    contract();
    return *this;
}

LargeNumber& LargeNumber::operator>>=(int n)
{
    if (n < 0) // avoid negatives
        {
        *this <<= -n;
        return *this;
        }
    // why can't I use - for (int i = 0; i <= sig - n; i++)
    for (int i = 0; i <= sig; i++) // copy
        number[i] = number[i + n];
    sig = sig - n; // shorten
    if (sig < 0)
        {
        sig = 0;
        number[0] = 0;
        }
    if (zero())
        negative = false;
    return *this;
}

LargeNumber& LargeNumber::operator++(void)
{
    return (*this += 1);
}

LargeNumber& LargeNumber::operator--(void)
{
    return (*this -= 1);
}

LargeNumber LargeNumber::operator++(int)
{
    LargeNumber c = *this;
    *this += 1;
    return c;
}

LargeNumber LargeNumber::operator--(int)
{
    LargeNumber c = *this;
    *this -= 1;
    return c;
}

LargeNumber& LargeNumber::operator*=(const LargeNumber& n)
{
    LargeNumber c;
    int m = sig + n.sig;
    expand(m);
    if (n.smaller(*this)) // loop through the smaller number
        {
        for (int i = 0; i <= n.sig; i++)
            {
            if (n.number[i] == 1)
                c.plus(*this); // add on multiples of two
            *this <<= 1;
            }
        }
    else
        {
        LargeNumber m = n;
        for (int i = 0; i <= sig; i++)
            {
            if (number[i] == 1)
                c.plus(m); // add on multiples of two
            m <<= 1;
            }
        }
    if (c.zero()) // check negatives
        c.negative = false;
    else
        c.negative = negative ^ n.negative;
    *this = c;
    contract();
    return *this;
}

LargeNumber& LargeNumber::operator/=(const LargeNumber& n)
{
    if (n.zero()) // no divide by zero
        throw;
    LargeNumber c;
    LargeNumber m = n;
    m <<= maximum(sig - n.sig, 0); // power of two multiple of n
    for (int i = pow(2, sig - n.sig); i > 0; i /= 2)
        {
        if (!m.greater(*this))
            {
            minus(m); // subtract of large chunk at time
            c += i;
            }
        m >>= 1; // shrink chunk down
        }
    if (c.zero()) // check negatives
        c.negative = false;
    else
        c.negative = negative ^ n.negative;
    *this = c;
    return *this;
}

LargeNumber& LargeNumber::operator%=(const LargeNumber& n)
{
    if (n.zero()) // no divide by zero
        throw;
    LargeNumber m = n;
    m <<= maximum(sig - n.sig, 0); // power of two multiple of n
    for (int i = sig - n.sig; i >= 0; i--)
        {
        if (!m.greater(*this))
            minus(m); // subtract of large chunk at time
        m >>= 1; // shrink chunk down
        }
    if (zero())
        negative = false;
    return *this;
}

LargeNumber& LargeNumber::operator&=(const LargeNumber& n)
{
    int m = maximum(sig, n.sig);
    expand(m); // match sizes
    for (int i = minimum(sig, n.sig); i >= 0; i--)
        number[i] &= n.number[i];
    contract();
    return *this;
}

LargeNumber& LargeNumber::operator|=(const LargeNumber& n)
{
    int m = maximum(sig, n.sig);
    expand(m); // match sizes
    for (int i = minimum(sig, n.sig); i >= 0; i--)
        number[i] |= n.number[i];
    contract();
    return *this;
}

LargeNumber& LargeNumber::operator^=(const LargeNumber& n)
{
    int m = maximum(sig, n.sig);
    expand(m); // match sizes
    for (int i = minimum(sig, n.sig); i >= 0; i--)
        number[i] ^= n.number[i];
    contract();
    return *this;
}

LargeNumber LargeNumber::operator+(const LargeNumber& n) const
{
    LargeNumber c = *this;
    c += n;
    return c;
}

LargeNumber LargeNumber::operator-(const LargeNumber& n) const
{
    LargeNumber c = *this;
    c -= n;
    return c;
}

LargeNumber LargeNumber::operator*(const LargeNumber& n) const
{
    LargeNumber c = *this;
    c *= n;
    return c;
}

LargeNumber LargeNumber::operator/(const LargeNumber& n) const
{
    LargeNumber c = *this;
    c /= n;
    return c;
}

LargeNumber LargeNumber::operator%(const LargeNumber& n) const
{
    LargeNumber c = *this;
    c %= n;
    return c;
}

LargeNumber LargeNumber::operator&(const LargeNumber& n) const
{
    LargeNumber c = *this;
    c &= n;
    return c;
}

LargeNumber LargeNumber::operator|(const LargeNumber& n) const
{
    LargeNumber c = *this;
    c |= n;
    return c;
}

LargeNumber LargeNumber::operator^(const LargeNumber& n) const
{
    LargeNumber c = *this;
    c ^= n;
    return c;
}

LargeNumber LargeNumber::operator<<(int n) const
{
    LargeNumber c = *this;
    c <<= n;
    return c;
}

LargeNumber LargeNumber::operator>>(int n) const
{
    LargeNumber c = *this;
    c >>= n;
    return c;
}

ostream& operator<<(ostream& s, const LargeNumber& n)
{
    if (n.negative)
        s << '-';
    for (int i = n.sig; i >= 0; i--)
        s << char(n.number[i] + '0');
    return s;
}

istream& operator>>(istream& s, LargeNumber& n)
{
    char c;
    while (s.get(c)) // strip any leading spaces
        if (c != ' ' && c != '\n' && c != '\r')
            {
            s.putback(c);
            break;
            }
    n = 0;
    while (s.get(c)) // check for negative
        {
        if (c != '-' & c != '+')
            {
            s.putback(c);
            break;
            }
        if (c == '-')
            n.negative = !n.negative;
        }
    while (s.get(c)) // build digits in reverse
        {
        if (c != '0' & c != '1')
            {
            s.putback(c);
            break;
            }
        if (n.sig > n.max) {
            n.expand(n.sig + BIT_INCREMENT);
            n.sig -= BIT_INCREMENT;
            }
        n.number[n.sig++] = c - '0';
        }
    if (n.sig > 0) // put digits right way round
        {
        n.sig--;
        for (int j = n.sig; j > n.sig / 2; j--)
            {
            c = n.number[j];
            n.number[j] = n.number[n.sig - j];
            n.number[n.sig - j] = c;
            }
        n.contract();
        }
    return s;
}