/******************************************************************************
			      class integer

Integers of arbitrary length and some of their logical and arithmetic 
operations.

Copyright: 
Jyrki Katajainen
Department of Computing
University of Copenhagen
DK-2100 Copenehagen East, Denmark
e-mail: jyrki@di.ku.dk

Version: 1.5
January - February 1999

The multiplication subroutines written by:
#####
e-mail: #####

Changes made to version 1.0:

9 February 1999

Christian Boesgaard <pink@diku.dk>
  friend integer<T> operator+(const integer<T>&, const integer<T>&);
  friend integer<T> operator*(const integer<T>&, const integer<T>&);
  friend ostream& operator<<(ostream&, const integer<T>&);
==>
  friend integer<T> operator+<>(const integer<T>&, const integer<T>&);
  friend integer<T> operator*<>(const integer<T>&, const integer<T>&);
  friend ostream& operator<< <>(ostream&, const integer<T>&);

Tommy <di981101@diku.dk>
New operations implemented
operator-: written by Tommy. Observe that this computes max(0, x - y).
operator==
operator!=
operator<
operator>
operator<=
operator<=

Jarl Friis <jarl@diku.dk>
  for (r = s_end - 1; (r != s_begin - 1) && *r == word<T>(T(0)); --r)
==>
  for (r = s_end - 1; (r != s_begin - 1) && *r == T(0); --r)

Changes made to version 1.1

9 February 1999

"S|ren Chr. Skov" <srenskov@diku.dk>
  for (r = s_end - 1; (r != s_begin - 1) && *r == T(0); --r)
==>
  for (r = s_end - 1; (r != s_begin - 1) && *r == word<T>(T(0)); --r)

Changes made to version 1.2

10 February 1999

Yesterday's first aid was a solution, but not the solution.
  for (r = s_end - 1; (r != s_begin - 1) && *r == word<T>(T(0)); --r)
==>
  for (r = s_end - 1; (r != s_begin - 1) && word<T>(*r) == word<T>(T(0)); --r)

Changes made to version 1.3

10 February 1999

Jarl Friis <jarl@diku.dk>
The main program is now in the form proposed by Jarl.

Changes made to version 1.4

14 February 1999

Christian Boesgaard <pink@diku.dk>
Christian corrected operator< and operator>. I have to admit that I had 
never time to test the logical operators. I thought they were trivial.
Phy, phy, Jyrki.

******************************************************************************/
	
#include <vector>    // defines vector
#include <algorithm> // defines min
#include <utility>   // defines pair
#include "word.cc"   // defines word

template <class T>
class integer {
public:
  integer();
  integer(T);
  integer(const integer<T>&);

  template <class In = T*>
  integer(In, In);

  integer<T>& operator=(const integer<T>&);
  
  friend bool operator==<>(const integer<T>&, const integer<T>&);
  friend bool operator!=<>(const integer<T>&, const integer<T>&);
  friend bool operator< <>(const integer<T>&, const integer<T>&);
  friend bool operator> <>(const integer<T>&, const integer<T>&);
  friend bool operator<=<>(const integer<T>&, const integer<T>&);
  friend bool operator>=<>(const integer<T>&, const integer<T>&);

  friend integer<T> operator+<>(const integer<T>&, const integer<T>&);
  friend integer<T> operator-<>(const integer<T>&, const integer<T>&); // max(0, x - y)
  friend pair<sign, integer<T> > operator-<>(const integer<T>&, const integer<T>&);
  friend integer<T> operator*<>(const integer<T>&, const integer<T>&);
  friend ostream& operator<< <>(ostream&, const integer<T>&);
private:
  vector<word<T> > vec;
  
  void init(const integer<T>&);
};

template <class T>
void integer<T>::init(const integer<T>& x) {
  typedef vector<word<T> >::size_type index;

  (*this).vec = vector<word<T> >();
  for (index i = 0; i < x.vec.size(); ++i)
    (*this).vec.push_back(x.vec[i]);
}

// constructors

template <class T>
integer<T>::integer() {
  (*this).vec = vector<word<T> >();
}

template <class T>
integer<T>::integer(T v) {
  if (v == T(0))
    (*this).vec = vector<word<T> >();
  else
    (*this).vec = vector<word<T> >(1, word<T>(v));
}

template <class T>
integer<T>::integer(const integer<T>& x) {
  (*this).init(x);
}

template <class T>
template <class In = T*>
integer<T>::integer(In s_begin, In s_end) {
  typedef vector<word<T> >::size_type index;

  (*this).vec = vector<word<T> >();
  In r;
  for (r = s_end - 1; (r != s_begin - 1) && word<T>(*r) == word<T>(T(0)); --r)
    ;
  r++;
  In p = s_begin;
  for (index i = 0; p != r; ++p, ++i) {
    (*this).vec.push_back(word<T>(*p));
  }
}
 
// assignment

template <class T>
integer<T>& integer<T>::operator=(const integer<T>& rhs) {
  if (this == &rhs) 
    return *this;
  init(rhs);
  return *this;
}

// logical operations

template <class T>
bool operator==(const integer<T>& x, const integer<T>& y) {
  typedef vector<word<T> >::size_type index;
  
  index m = x.vec.size();
  index n = y.vec.size();
  if (m != n) 
    return false;
  else {
    for (index i = 0; i < n; ++i) {
      if (x.vec[i] != y.vec[i]) 
	return false;
    }
    return true;
  }
}

template <class T>
bool operator!=(const integer<T>& x, const integer<T>& y) {
  return !(x == y);
}

template <class T>
bool operator<(const integer<T>& x, const integer<T>& y) {
  typedef vector<word<T> >::size_type index;
  
  index m = x.vec.size();
  index n = y.vec.size();
  if (m < n) 
    return true;
  else if (m > n)
    return false;
  else {
    for (index i = n; i > 0; i--){ 
      if (x.vec[i - 1] != y.vec[i - 1]) {
	return (x.vec[i - 1] < y.vec[i - 1]);
      };
    };
    return false;
  };
}

template <class T>
bool operator>(const integer<T>& x, const integer<T>& y) {
  typedef vector<word<T> >::size_type index;
  
  index m = x.vec.size();
  index n = y.vec.size();
  if (m > n) 
    return true;
  else if (m < n)
    return false;
  else {
    for (index i = n; i > 0; i--){ 
      if (x.vec[i - 1] != y.vec[i - 1]) {
	return (x.vec[i - 1] > y.vec[i - 1]);
      };
    };
    return false;
  };
}
  
template <class T>
bool operator<=(const integer<T>& x, const integer<T>& y) {
  return !(x > y);
}

template <class T>
bool operator>=(const integer<T>& x, const integer<T>& y) {
  return !(x < y);
}

// addition

template <class T>
integer<T> operator+(const integer<T>& x, const integer<T>& y) {
  typedef vector<word<T> >::size_type index;
  typedef pair<word<T>, word<T> > word_pair;

  index m = min(x.vec.size(), y.vec.size());
  index n = max(x.vec.size(), y.vec.size());
  vector<word<T> > v(n + 1, word<T>(T(0)));
  word<T> carry = word<T>(T(0));
  for (index i = 0; i < m; ++i) {
    word_pair p = x.vec[i] + y.vec[i];
    word_pair q = p.second + carry;
    word_pair r = p.first + q.first;
    carry = r.second;
    v[i] = q.second;
  }
  if (x.vec.size() > m) {
    for (index i = m; i < n; ++i) {
      word_pair p = x.vec[i] + carry;
      carry = p.first;
      v[i] = p.second;
    }
  }
  else {
    for (index i = m; i < n; ++i) {
      word_pair p = y.vec[i] + carry;
      carry = p.first;
      v[i] = p.second;
    }
  }
  v[n] = carry;
  return integer<T>(v.begin(), v.end());
}

// subtraction; computes max(0, x - y)

template <class T>
integer<T> operator-(const integer<T>& x, const integer<T>& y) {
  typedef vector<word<T> >::size_type index;
  typedef pair<word<T>, word<T> > word_pair;
  typedef pair<sign, word<T> > signed_word;

  index m = y.vec.size();
  index n = x.vec.size();
  if (m > n)
    return integer<T>();
  vector<word<T> > v(n, word<T>(T(0)));
  word<T> borrow = word<T>(T(0));
  word<T> maxword = word<T>(T(~0));

  for (index i = 0; i < m; ++i) {
    word_pair q = y.vec[i] + borrow;
    if (q.first == word<T>(T(1))) {
      // q.second == 0
      borrow = word<T>(T(1));
      v[i] = x.vec[i];
    }
    else {
      signed_word sw = x.vec[i] - q.second;
      if (sw.first == minus) {
	borrow = word<T>(T(1));
	signed_word pp = maxword - q.second;
	word_pair t = pp.second + x.vec[i];
	word_pair u = t.second + word<T>(T(1));
	v[i] = u.second;
      }
      else {
	borrow = word<T>(T(0));
	v[i] = sw.second;
      }
    }
  }
  for (index i=m; i<n; i++){
    signed_word sw = x.vec[i] - borrow;
    if (sw.first == minus) {
      borrow = word<T>(T(1));
      v[i] = maxword;
    }
    else {
      borrow = word<T>(T(0));
      v[i] = sw.second;
    }
  }
  if (borrow == word<T>(T(0)))
    return integer<T>(v.begin(), v.end());
  else
    return integer<T>();
}

// multiplication

#if SCHOOL

template <class T>
integer<T> operator*(const integer<T>& x, const integer<T>& y) {
  cerr << "Not yet implemented!" << endl;
  exit(7);
}

#else

template <class T>
integer<T> operator*(const integer<T>& x, const integer<T>& y) {
  cerr << "Not yet implemented!" << endl;
  exit(7);
}

#endif

// outputting

template <class T>
ostream& operator<<(ostream& out, const integer<T>& x) {
  typedef vector<word<T> >::size_type index;

  if (x.vec.size() == 0) 
    out << word<T>(T(0));
  else
    for (index i = x.vec.size(); i > 0; --i) {
      out << x.vec[i - 1];
      if (i != 0)
	out << '\t';
    }
  return out;
}

#if defined(UNIT_TEST_INTEGER)

int main() {
  integer<unsigned char> x = integer<unsigned char>((unsigned char)(189));
  integer<unsigned char> x2 = x + x;
  integer<unsigned char> x4 = x2 + x2;
  integer<unsigned char> x3 = x4 - x;
  integer<unsigned char> y = x - x2;

  integer<unsigned char> p1 = x * x;
  integer<unsigned char> p2 = x * p1;
  integer<unsigned char> p3 = p1 * x;
  integer<unsigned char> p4 = p1 * p1;
  integer<unsigned char> p5 = p3 * p1;
  integer<unsigned char> p6 = p1 * p3;

  cout << "x = " << x << endl;
  cout << "x + x = " << x2 << endl;
  cout << "2x + 2x = " << x4 << endl;
  cout << "4x - x = " << x3 << endl;
  cout << "max(0, x - 2x) = " << y << endl;
  cout << "x * x = " << p1 << endl;
  cout << "x * (x * x) = " << p2 << endl;
  cout << "(x * x) * x = " << p3 << endl;
  cout << "(x * x) * (x * x) = " << p4 << endl;
  cout << "((x * x) * x) * (x * x)= " << p5 << endl;
  cout << "(x * x) * ((x * x) * x) = " << p6 << endl;

  return(0);
}

/*

freja> g++ -Wall -DUNIT_TEST_INTEGER -DSCHOOL=1 integer.cc
freja> a.out
x = 189
x + x = 1       122
2x + 2x = 2     244
4x - x = 2      55
max(0, x - 2x) = 0
x * x = 139     137
x * (x * x) = 103       4       37
(x * x) * x = 103       4       37
(x * x) * (x * x) = 76  14      15      81
((x * x) * x) * (x * x)= 56     38      97      78      205
(x * x) * ((x * x) * x) = 56    38      97      78      205

freja> g++ -Wall -DUNIT_TEST_INTEGER -DSCHOOL=0 integer.cc
freja> a.out
x = 189
x + x = 1       122
2x + 2x = 2     244
4x - x = 2      55
max(0, x - 2x) = 0
x * x = 139     137
x * (x * x) = 103       4       37
(x * x) * x = 103       4       37
(x * x) * (x * x) = 76  14      15      81
((x * x) * x) * (x * x)= 56     38      97      78      205
(x * x) * ((x * x) * x) = 56    38      97      78      205

*/

#endif