/*******************************************************************************
+
+  LEDA 3.5
+
+  integer.h
+
+  This file is part of the LEDA research version (LEDA-R) that can be 
+  used free of charge in academic research and teaching. Any commercial
+  use of this software requires a license which is distributed by the
+  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
+  (fax +49 681 31104).
+
+  Copyright (c) 1991-1997  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/
#ifndef LEDA_INTEGER_H
#define LEDA_INTEGER_H

#if !defined(LEDA_ROOT_INCL_ID)
#define LEDA_ROOT_INCL_ID 350063
#include <LEDA/REDEFINE_NAMES.h>
#endif


//------------------------------------------------------------------------------
//
//  integer:  big integers
//
//  by Christian Uhrig and Stefan Naeher   (1994)
//
//  - 32 bit (unsigned long) vector representation
//  - use of a handle class concept (to avoid copy overhead)
//  - use of the LEDA memory management
//  - sparc assembler code for 32 bit multiplication
//
//------------------------------------------------------------------------------

/*{\Manpage {integer} {} {Integers of Arbitrary Length} }*/


#include <LEDA/basic.h>
#include <iostream.h>

#if _MIPS_SZLONG == 64
typedef unsigned int  int_word_type;
#else
typedef unsigned long int_word_type;
#endif

class integer_rep 
{
  friend class integer;
  friend class rational;

/*
  unsigned short  count;
  unsigned short  size;
  unsigned short  used;
           short  sign;
*/
  unsigned int  count;
  unsigned int  size;
  unsigned int  used;
           int  sign;
  int_word_type vec[1];


  friend integer_rep* copy_integer_rep(integer_rep*);

  friend integer operator + (const integer& a, const integer& b);
  friend integer operator - (const integer& a, const integer& b);
  friend integer operator * (const integer& a, const integer& b);
  friend integer operator / (const integer& a, const integer& b);
  friend integer operator % (const integer& a, const integer& b);

  friend integer operator & (const integer& a, const integer& b);
  friend integer operator | (const integer& a, const integer& b);
//friend integer operator ^ (const integer& a, const integer& b);

  friend bool operator == (const integer& a, const integer& b);
  friend bool operator < (const integer& a, const integer& b);
  friend bool operator > (const integer& a, const integer& b);

  friend inline bool operator != (const integer& a, const integer& b);
  friend inline bool operator >= (const integer& a, const integer& b);
  friend inline bool operator <= (const integer& a, const integer& b);

  friend ostream& operator << (ostream & out, const integer& a);
  friend istream& operator >> (istream & in, integer& a);
  friend random_source& operator >> (random_source&, integer& a);

  friend integer sqrt(const integer& a);
  friend integer abs(const integer& a);
  friend integer gcd(const integer&, const integer&);

  friend int log(const integer& a);

  friend inline int sign(const integer& a);

  friend integer_rep* new_integer_rep(unsigned int size);
  friend void delete_integer_rep(integer_rep *p);

};



class integer {

  friend class rational;

/*{\Mdefinition
An instance $a$ of the data type |\Mname| is an integer number of 
arbitrary length. 
}*/


private:

 integer_rep* PTR;

 integer(integer_rep* p) { PTR = p; }

 GenPtr copy() const { PTR->count++; return PTR; }
 void   clear()      { if (PTR && --(PTR->count)==0) delete_integer_rep(PTR); }
 int    refs() const { return PTR->count; }


public:

/*{\Mcreation a }*/
   
   integer();

/*{\Mcreate creates an instance |\Mvar| of type |\Mname| and initializes it
with zero.}*/

   integer(int n);

/*{\Mcreate creates an instance |\Mvar| of type |\Mname| and initializes it
with the value of $n$.}*/
  
   integer(unsigned int i);
   integer(long l);
   integer(unsigned long i);
   
   integer(double x); 
   
/*{\Mcreate creates an instance |\Mvar| of type |\Mname| and initializes it
with the integral part of $x$.}*/

   integer(const integer& a)  { PTR = a.PTR;  PTR->count++; }
  ~integer() { clear(); }


/*{\Moperations 2 4.7 }*/

/*{\Mtext

The arithmetic operations $+,\ -,\ *,\ /,\ +=,\
-=,\ *=,\ /=,\ -$(unary), $++,\ --$,  the modulus operation ($\%$, $\% =$), bitwise
AND ($\&$, $\& =$), bitwise OR ($\Lvert \Lvert =$), the complement ($\ \tilde{}\ $),
the shift operations
($<<,\ >>$),
the comparison operations $<,\ <=,\ >,\ 
>=,\ ==,\ !=$ and the stream operations all are available.
}*/

   integer& operator=(const integer& x)
   { x.PTR->count++;
     clear();
     PTR = x.PTR;
     return *this;
    }

  // type conversion

/*
  operator GenPtr() { return (PTR->sign) ? PTR : 0; }
*/

  // member functions

  int    length()   const;
/*{\Mop returns the number of bits of the representation of |\Mvar|.}*/

  bool   islong()   const;
/*{\Mop returns whether |\Mvar| fits in the data type $long$.}*/

  bool   iszero()   const;
/*{\Mop returns whether |\Mvar| is equal to zero.}*/

  long to_long() const
  { if (PTR->sign == 0) return 0;
    else return  (PTR->sign > 0) ? ((long)PTR->vec[0]) : -((long)PTR->vec[0]);
   }
/*{\Mop returns a $long$ number which is initialized with the value of |\Mvar|.
        \precond $a$.islong() is $true$.}*/

  long   tolong()   const { return to_long(); }

  double to_double() const;
/*{\Mop returns a double floating point approximation of |\Mvar|. }*/

  double todouble() const { return to_double(); }
/*{\Xop returns a double floating point approximation of |\Mvar|. }*/


  string tostring() const; 
/*{\Mop returns the decimal representation of |\Mvar|. }*/

  int_word_type highword() const;

  void hex_print(ostream&) const;



  // friend functions & operators

  friend integer operator + (const integer& a, const integer& b);
  friend integer operator - (const integer& a, const integer& b);
  friend integer operator * (const integer& a, const integer& b);
  friend integer operator / (const integer& a, const integer& b);
  friend integer operator % (const integer& a, const integer& b);
  friend integer operator & (const integer& a, const integer& b);
  friend integer operator | (const integer& a, const integer& b);
//friend integer operator ^ (const integer& a, const integer& b);

  friend bool operator == (const integer& a, const integer& b);
  friend bool operator <  (const integer& a, const integer& b);
  friend bool operator >  (const integer& a, const integer& b);

  friend inline bool operator != (const integer& a, const integer& b);
  friend inline bool operator >= (const integer& a, const integer& b);
  friend inline bool operator <= (const integer& a, const integer& b);

/*{\Mtext
\smallskip
{\bf Non-member functions}
\smallskip }*/

  friend double Double(const integer& a) { return a.to_double(); }
/*{\Mfunc returns a double floating point approximation of $a$. }*/

  friend integer sqrt(const integer& a);
/*{\Mfunc returns the largest $integer$ which is not larger than the
          squareroot of $a$. }*/

  friend integer abs(const integer& a);
/*{\Mfunc returns the absolute value of $a$.}*/

  friend integer gcd(const integer& a, const integer& b);
/*{\Mfunc returns the greatest common divisor of $a$ and $b$.}*/

  friend int log(const integer& a);
/*{\Mfunc returns the logarithm of $a$ to the basis 2.}*/

  friend int  sign(const integer& a) { return a.PTR->sign; }
/*{\Mfunc returns the sign of $a$.}*/

  friend integer sqr(const integer& a) { return a*a; }
/*{\Mfunc returns  $a^2$. }*/




  // member functions and operators

  int  used_words() { return PTR->used; };
  int  zeros() const;
  void absolute();

  int_word_type contents(int k) const { return PTR->vec[k]; };

  integer div(const integer&, integer&) const;

  integer operator-() const;
  integer operator~() const;

  integer operator<<(long n) const;
  integer operator>>(long n) const;
  integer operator+= (const integer& b) { return *this = *this + b; }
  integer operator-= (const integer& b) { return *this = *this - b; }
  integer operator*= (const integer& b) { return *this = *this * b; }
  integer operator/= (const integer& b) { return *this = *this / b; }
  integer operator%= (const integer& b) { return *this = *this % b; }
  integer operator&= (const integer& b) { return *this = *this & b; }
  integer operator|= (const integer& b) { return *this = *this | b; }
  integer operator<<=(int n) { return *this = *this << n; }
  integer operator>>=(int n) { return *this = *this >> n; }
  integer operator++ ();
  integer operator++ (int);
  integer operator-- ();
  integer operator-- (int);

  friend integer operator+(const integer& x, int i) { return x + integer(i); }
  friend integer operator+(int i, const integer& x) { return integer(i) + x; }
  friend integer operator-(const integer& x, int i) { return x - integer(i); }
  friend integer operator-(int i, const integer& x) { return integer(i) - x; }
  friend integer operator*(const integer& x, int i) { return x * integer(i); }
  friend integer operator*(int i, const integer& x) { return integer(i) * x; }
  friend integer operator/(const integer& x, int i) { return x / integer(i); }
  friend integer operator/(int i, const integer& x) { return integer(i) / x; }


  bool operator==(int n) const;
  bool operator< (int n) const;
  bool operator> (int n) const;
  bool operator!=(int n) const;
  bool operator>=(int n) const;
  bool operator<=(int n) const;

  // static members

  static integer random(int n);


  // more friends

  friend ostream& operator << (ostream& O, const integer& a);
  friend istream& operator >> (istream& I, integer& a);

  friend random_source& operator>> (random_source& ran, integer& x);
/*{\Xbinopfunc extracts an integer of default precision from random source 
               $ran$ (cf. /ref{Radom Sources}) and assings it to $x$. }*/


  static int cmp(const integer& a, const integer& b);

  LEDA_MEMORY(integer)

};

inline char* leda_tname(const integer*) { return "integer"; }



inline int compare(const integer& a, const integer& b)
{ return integer::cmp(a,b); }


inline bool operator != (const integer& a, const integer& b) { return !(a==b); }
inline bool operator <= (const integer& a, const integer& b) { return !(a>b);  }
inline bool operator >= (const integer& a, const integer& b) { return !(a<b);  }




inline bool integer::iszero() const { return (PTR->sign == 0); }

inline bool integer::islong() const
{ if (PTR->sign == 0) return true;
  else return (PTR->used == 1 && PTR->vec[0] <= 0x8FFFFFFF);
 }


inline int_word_type integer::highword() const
{ if (PTR->sign == 0) return 0;
  else return PTR->vec[PTR->used-1];
 }


inline bool integer::operator!=(int a) const { return !operator==(a); }
inline bool integer::operator<=(int a) const { return !operator>(a);  }
inline bool integer::operator>=(int a) const { return !operator<(a);  }


inline integer integer::operator++ () { return *this = *this + 1; }
inline integer integer::operator-- () { return *this = *this - 1; }

inline integer integer::operator++ (int) 
{ integer i = *this;
  *this = *this + 1;
  return i;
 }

inline integer integer::operator-- (int) 
{ integer i = *this;
  *this = *this - 1;
  return i;
 }


/*{\Mimplementation 
An $integer$ is essentially implemented by a 
vector $vec$ of $unsigned\ long$ numbers. 
The sign and the size are stored in extra variables.
Some time critical functions are also implemented in sparc assembler code.}*/



#if LEDA_ROOT_INCL_ID == 350063
#undef LEDA_ROOT_INCL_ID
#include <LEDA/UNDEFINE_NAMES.h>
#endif


#endif
