/*
   In this project we created a class which represents a big integer
   value. "Big" means, it can hold arbitrary number of digits.
   We defined the basic operations on that class (operator= and
   operator+). The class seems to work correctly.

   However we have serious efficiency problems. It seems, that
   operations in main() are terrible slow, and even worse:
   execution time is non-linear with the number of digits.

   Try to detect the bottlenecks, and fix they (in iterative
   steps).

 */


#include <stdio.h>
#include <string.h>
#include <time.h>

class BigInt
{
    friend class DigitStream;
public:
        BigInt(const char*);
        BigInt(unsigned n = 0);
        BigInt(const BigInt&);
       ~BigInt()  { delete [] digits; }
    void    operator=(const BigInt&);
    BigInt  operator+(const BigInt&) const;
    void    print(FILE* f = stdout) const;
private:
    char*       digits;
    unsigned    ndigits;
        BigInt(char* d, unsigned n)  { digits = d; ndigits = n; }
};
class DigitStream
{
public:
    DigitStream(const BigInt& n)  { dp = n.digits; nd = n.ndigits; }
    unsigned operator++()  
    { 
        if ( nd == 0 ) 
            return 0;
        else           
        {
            nd--; 
            return *dp++; 
        } 
    }
private:
    char*       dp;
    unsigned    nd;
};
void BigInt::print(FILE* f) const
{
    for (int i = ndigits-1; i>=0; i--)   
        fprintf(f, "%c", digits[i]+'0');
}
void BigInt::operator=(const BigInt& n)
{
    if (this == &n)  return;
    delete [] digits;
    unsigned i = n.ndigits;
    digits = new char[ndigits = i];
    char* p = digits;
    char* q = n.digits;
    while(i--) 
        *p++ = *q++;
}
BigInt BigInt::operator+(const BigInt& n) const
{
    unsigned maxDigits = (ndigits>n.ndigits ? ndigits : n.ndigits)+1;
    char* sumPtr = new char[maxDigits];
    BigInt sum(sumPtr, maxDigits);
    DigitStream a(*this);
    DigitStream b(n);
    unsigned i = maxDigits;
    unsigned carry = 0;
    while (i--)
    {
        *sumPtr = (++a) + (++b) + carry;
        if ( *sumPtr >= 10 )
        {
            carry = 1;
            *sumPtr -= 10;
        }
        else carry = 0;
        sumPtr++;
    }
    return sum;
}
BigInt::BigInt(unsigned n)
{
    char d[3*sizeof(unsigned)+1];
    char* dp = d;
    ndigits = 0;
    do
    {
        *dp++ = n%10;
        n /= 10;
        ndigits++;
    } 
    while (n > 0);
    digits = new char[ndigits];
    for (register i = 0; i < ndigits; i++) 
        digits[i] = d[i];
}
BigInt::BigInt(const BigInt& n)
{
    unsigned i = n.ndigits;
    digits = new char[ndigits = i];
    char* p = digits;
    char* q = n.digits;
    while (i--)  
        *p++ = *q++;
}
BigInt::BigInt(const char* digitString)
{
    unsigned n = strlen(digitString);
    if (n != 0)
    {
        digits = new char[ndigits = n];
        char* p = digits;
        const char* q = &digitString[n];
        while (n--) 
            *p++ = *--q - '0';
    }
    else
    {
        digits = new char[ndigits = 1];
        digits[0] = 0;
    }
}

int main()
{
    BigInt b = 1;

    time_t t1 = time(NULL);
    for (int i = 1; i <= 50000; ++i)  
        b = b + 1;
    time_t t2 = time(NULL);

    printf("Elapsed time: %ld\n", t2 - t1);
    //  1000 rec =   1 sec
    //  2000 rec =   7 sec
    //  5000 rec =  38 sec
    //  10000 rec = 150 sec
    //   ... on my old machine :-)
}