/* mmahoney.cpp -- Matt Mahoney, mmahoney@cs.fit.edu

This file contains function definitions for types Integer and Real,
infinite range/precision numbers.  See mmahoney.h for documentation.
*/

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cctype>
#include <string>
#include <vector>
#include <algorithm>
#include "mmahoney.h"
using namespace std;

// Construct Real from d with p decimal places of precision
Real::Real(double d, int p): v(0), pr10(0), prb(0) {
  prec10(p);

  // Scale d to find the leading digit
  int digits=prec()+1;
  while (digits>0 && d>-1 && d<1) {
    --digits;
    d*=base();
  }
  while (d>=base() || d<=-base()) {
    ++digits;
     d/=base();
  }

  // Chop d into digits
  for (int i=digits-1; i>=0; --i) {
    add(i, BT(floor(d)));
    d=(d-digit(i))*base();
  }
}

// Set precision to n decimal digits
void Real::prec10(int n) {
  int oldp=prec();
  int newp = n>0 ? int(ceil(n*log(10)/log(base()))) : 0;
  if (int(v.size())>0 && newp>oldp) {  // Grow?  append zeros
    vector<BT> newv(v.size()+newp-oldp);
    copy(v.begin(), v.end(), newv.begin()+newp-oldp);
    v=newv;
  }
  else if (v.begin()+oldp-newp>=v.end())  // Negative size?
    v.resize(0);
  else if (newp<oldp)  // Chop digits
    v=vector<BT>(v.begin()+oldp-newp, v.end());
  pr10=n;
  prb=newp;
}

// Add x to v[i] and carry, changing size as needed
void Real::add(int i, Digit_t x) {
  if (i<0)
    return;
  while (x) {

    // Extend the leading digit until i is in bounds
    while (i>=size()) {
      if (digit(size()-1)<0) {
        v.back()+=base();
        v.push_back(-1);
      }
      else
        v.push_back(0);
    }

    // Add x to v[i]
    Digit_t sum=digit(i)+x;
    if (sum<base() && (sum>=0 || (i==size()-1 && sum>-base()))) {
      v[i]=sum;  // no carry
      break;
    }

    // Put the carry in x and add to the next digit
    x=sum/base();
    Digit_t rem=sum-x*base();
    if (rem<0) {
      rem+=base();
      --x;
    }
    v[i]=rem;
    ++i;
  }

  // Trim unneeded leading digits
  while (!v.empty() && v.back()==0)
    v.pop_back();
  while (int(v.size())>=2 && v.back()==-1 && v[v.size()-2]>0) {
    v.pop_back();
    v.back()-=base();
  }
}

// Subtraction
Real operator - (Real a, const Real& b) {
  a.prec10(max(a.prec10(), b.prec10()));
  const int pr=a.prec()-b.prec();
  for (int i=0; i<b.size(); ++i)
    a.add(i+pr, -b.digit(i));
  return a;
}

// Multiplication
Real& operator *= (Real& a, const Real& b) {
  Real r(0, max(a.prec10(), b.prec10()));  // Result
  const int pr=r.prec()-a.prec()-b.prec();
  for (int i=0; i<a.size(); ++i)
    for (int j=max(0, -i-pr); j<b.size(); ++j)
      r.add(i+j+pr, a.digit(i)*b.digit(j));
  return a=r;
}

// Comparison
bool operator < (const Real& a, const Real& b) {
  for (int i=max(a.size()-a.prec(), b.size()-b.prec());
      i >= -a.prec() || i >= -b.prec(); --i) {
    if (a.digit(i+a.prec())!=b.digit(i+b.prec()))
      return a.digit(i+a.prec()) < b.digit(i+b.prec());
  }
  return false;
}

// Division
Real operator / (Real a, Real b) {
  int pr=max(a.prec10(), b.prec10());
  a.prec10(pr);
  b.prec10(pr);
  if (b.size()==0)
    return Real(0, pr);
  else if (a<0)
    return -(-a/b);
  else if (b<0)
    return -(a/-b);
  Real m(1, pr);
  Real q(0, pr);
  const Integer mul=1<<30;
  while (b<a) {
    b*=mul;
    m*=mul;
  }
  const Real half(0.5, 1);
  while (m>0) {
    if (b<=a) {
      q+=m;
      a-=b;
    }
    m*=half;
    m.prec10(pr);
    b*=half;
    b.prec10(pr);
  }
  return q;
}

// Input: accept digits and at most one decimal point and a leading minus
istream& operator >> (istream& in, Real& a) {
  a=Real(0, a.prec10()); 
  Integer wt=0;  // pow(10, decimal places) in input
  int sign=1;    // -1 if leading -
  string s;      // Input
  in >> s;
  for (int i=0; i<int(s.size()); ++i) {
    if (i==0 && s[0]=='-')
      sign=-1;
    else if (isdigit(s[i])) {
      a=a*Integer(10)+Integer((s[i]-'0')*sign);
      wt*=Integer(10);
    }
    else if (s[i]=='.' && wt==0 && a.prec10()>0)
      wt=1;
    else
      break;
  }
  if (wt>1)
    a=a/wt;
  return in;
}

// Output a Real
ostream& operator << (ostream& out, const Real& a) {
  if (a<Integer(0))
    return out << "-" << -a;
  else if (a==0)
    return out << "0";

  // Now a > 0.  If the base is a power of 10, print the digits
  if (a.base10()) {
    out << setfill('0');
    for (int i=max(a.size()-1, a.prec()); i>=0; --i) {
      out << a.digit(i);
      if (i>0 && i==a.prec())
        out << '.';
      out << setw(a.base10());
    }
    return out << setw(0) << setfill(' ');
  }

  // Otherwise convert to base 10
  Integer tens=1;
  for (int i=a.prec10(); i>0; --i)
    tens*=10;
  Integer b=Integer(a*tens);  // Remove the decimal point
  string s;  // Stack of digits in reverse order
  int pr=a.prec10();
  while (pr-->=0 || b>0) {
    s+=char((b%10).digit(0)+'0');
    b/=10;
  }
  for (int i=int(s.size())-1; i>=0; --i) {  // Print the digits
    out << s[i];
    if (i>0 && i==a.prec10())
      out << '.';
  }
  return out;
}