//==============================================================================
//
// fractions.h
//
// fraction arithmetics implementation
//
// developer: Henry Guennadi Levkin
//
// version 0.3
//
// for Windows use "__int64" instead of "long long"
//
//==============================================================================

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

//------------------------------------------------------------------------------
// 64-bit integer (long long) to string conversion
// version 0.2
void L64toStr(long long n, char* pStr)
{
  int i = 0;
  int m;
  int len;
  char c;
  char s = '+';

  if(n == LONG_LONG_MIN) // _I64_MIN  for Windows Microsoft compiler
  {
    strcpy(pStr,"-9223372036854775808");
    return;
  }

  if( n < 0 )
  {
    s = '-';
    n = - n;
    pStr[0]='-';
    i++;
  }

  do
  {
    m = n % (long long)10;
    pStr[i] = '0'+ m;
    n = n / (long long)10;
    i++;
  }
  while(n != 0);

  if(s == '+')
  {
    len = i;
  }
  else /* s=='-' */
  {
    len = i-1;
    pStr++;
  }

  for(i=0; i<len/2; i++)
  {
    c = pStr[i];
    pStr[i]       = pStr[len-1-i];
    pStr[len-1-i] = c;
  }
  pStr[len] = 0;

  if(s == '-')
  {
    pStr--;
  }
}

//------------------------------------------------------------------------------
// string to 64-bit integer conversion
// version 0.2
int StrtoL64(char* pStr, long long* pN)
{
  int i;
  int len = strlen(pStr);
  char s = pStr[0];

  *pN = 0;

  if(s == '-')
  {
    pStr++;
    len--;
  }

  for(i=0; i<len; i++)
  {
    if(pStr[i]>='0'  &&  pStr[i]<='9')
    {
      *pN = (*pN)*(long long)10 + (pStr[i]-'0');
    }
    else
    {
      return 1;
    }
  }

  if(s == '-')
  {
    pStr--;
    (*pN) = - (*pN);
  }

  return 0;
}

//------------------------------------------------------------------------------
typedef struct
{
  long long numerator;
  long long denominator;
  int sign;
}
SFraction;

//------------------------------------------------------------------------------
long long EuclidAlgorithm(long long n, long long m)
{
  long long p, q;

  if(n < m)
  {
    p=n;  n=m;  m=p;
  }

  while(1)
  {
    p = n/m; 
    q = n%m;
    if(q == 0) break;
    n = m;
    m = q;
  }

  return m;
}

//------------------------------------------------------------------------------
void FractionAssign(SFraction* pFrac, int  sign, long long numer, long long denom)
{
  pFrac->sign  = sign;
  pFrac->numerator   = (long long) numer;
  pFrac->denominator = (long long) denom;
}

//------------------------------------------------------------------------------
void FractionAssign32(SFraction* pFrac, int sign, int numer, int denom)
{
  pFrac->sign  = sign;
  pFrac->numerator   = (long long) numer;
  pFrac->denominator = (long long) denom;
}

//------------------------------------------------------------------------------
void FractionPrint(SFraction* pFrac)
{
  char numer[64], denom[64];
  if(pFrac->sign == -1)
  {
    printf("- ");
  }
  L64toStr(pFrac->numerator, numer);
  L64toStr(pFrac->denominator, denom);
  printf("%s / %s  ", numer, denom);
}

//------------------------------------------------------------------------------
// ?
void FractionCopy(SFraction* pFr, SFraction* pFrCopy)
{
  pFrCopy->sign  = pFr->sign;
  pFrCopy->numerator = pFr->numerator;
  pFrCopy->denominator = pFr->denominator;
}

//------------------------------------------------------------------------------
void FractionNegative(SFraction* pFr)
{
  if(pFr->sign >0) pFr->sign = -1;
  else pFr->sign = +1;
}

//------------------------------------------------------------------------------
int FractionAdd(SFraction* pFrac1, SFraction* pFrac2, SFraction* pResult)
{
  long long r;
  long long s;
  long long nod;
  long long ss;

  r = pFrac1->denominator * pFrac2->denominator;

  if(pFrac1->sign == pFrac2->sign)
  {
    s = pFrac1->numerator * pFrac2->denominator + pFrac2->numerator * pFrac1->denominator;
    pResult->sign = pFrac1->sign;
  }
  else
  {
    ss  = (pFrac1->sign)*pFrac1->numerator * pFrac2->denominator;
    ss += (pFrac2->sign)*pFrac2->numerator * pFrac1->denominator;
    if(ss >=0)
    {
      s = ss;
      pResult->sign = 1;
    }
    else
    {
      s = -ss;
      pResult->sign = -1;
    }
  }
  if(s==0)
  {
    pResult->numerator = 0;
    pResult->denominator = 1;
    return;
  }
  nod = EuclidAlgorithm(r, s);
  if(nod<0)  printf("EuclidAlgorithm error \n");

  pResult->numerator = (s/nod);
  pResult->denominator = (r/nod);
  
  return 0;
}

//------------------------------------------------------------------------------
int FractionSubtract(SFraction* pFrac1, SFraction* pFrac2, SFraction* pResult)
{
  SFraction frac2copy = *pFrac2;
  int res;
  
  FractionNegative(&frac2copy);
  
  res = FractionAdd(pFrac1, &frac2copy, pResult);

  return res;
}

//------------------------------------------------------------------------------
int FractionMultiply(SFraction* pFr1, SFraction* pFr2, SFraction* pFrRes)
{
  long long s = pFr1->numerator * pFr2->numerator;
  long long r = pFr1->denominator * pFr2->denominator;
  long long nod;

  if(s!=0)
  {
    nod = EuclidAlgorithm(r,s);
    pFrRes->numerator = (s/nod);
    pFrRes->denominator = (r/nod);
    pFrRes->sign = pFr1->sign * pFr2->sign;
  }
  else
  {
    pFrRes->numerator = 0;
    pFrRes->denominator = 1;
    pFrRes->sign  = 1;
  }

}

//------------------------------------------------------------------------------
int FractionDivide(SFraction* pFr1, SFraction* pFr2, SFraction* pFrRes)
{
  long long s = pFr1->numerator * pFr2->denominator;
  long long r = pFr1->denominator * pFr2->numerator ;
  long long nod;

  if(s!=0)
  {
    nod = EuclidAlgorithm(r,s);
    pFrRes->numerator = (s/nod);
    pFrRes->denominator = (r/nod);
    pFrRes->sign = pFr1->sign * pFr2->sign;
  }
  else
  {
    pFrRes->numerator = 0;
    pFrRes->denominator = 1;
    pFrRes->sign =  1;
  }
}