/*  Rational - Rational number class with overflow detection
    Copyright (C) 2012-2017 Antonio Diaz Diaz.

    This program is free software. Redistribution and use in source and
    binary forms, with or without modification, are permitted provided
    that the following conditions are met:

    1. Redistributions of source code must retain the above copyright
    notice, this list of conditions and the following disclaimer.

    2. Redistributions in binary form must reproduce the above copyright
    notice, this list of conditions and the following disclaimer in the
    documentation and/or other materials provided with the distribution.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
*/
/*
    Exit status: 0 for a normal exit, 1 for environmental problems
    (file not found, invalid flags, I/O errors, etc), 2 to indicate a
    corrupt or invalid input file, 3 for an internal consistency error
    (eg, bug) which caused rational to panic.
*/

#include <cctype>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>

#include "arg_parser.h"
#include "rational.h"


namespace {

const char * const Program_name = "Rational";
const char * const program_name = "rational";
const char * const program_year = "2017";
const char * invocation_name = 0;


void show_help()
  {
  std::printf( "%s - Rational number class with overflow detection.\n", Program_name );
  std::printf( "See the source file 'main.cc' to learn how to use %s in\n", Program_name );
  std::printf( "your own programs.\n"
               "\nUsage: %s [options]\n", invocation_name );
  std::printf( "\nOptions:\n"
               "  -h, --help                   display this help and exit\n"
               "  -V, --version                output version information and exit\n"
               "  -p, --pi                     calculate approximations of pi\n"
               "  -q, --quiet                  quiet operation\n"
               "  -s, --sqrt=<n>               calculate approximations of sqrt(n)\n"
               "  -t, --test=<level>           run tests at given level (1-9)\n"
               "  -v, --verbose                verbose operation\n"
               "\nReport bugs to arg-parser-bug@nongnu.org\n"
               "Rational home page: http://www.nongnu.org/arg-parser/rational.html\n" );
  }


void show_version()
  {
  std::printf( "%s %s\n", program_name, PROGVERSION );
  std::printf( "Copyright (C) %s Antonio Diaz Diaz.\n", program_year );
  std::printf( "License 2-clause BSD.\n"
               "This is free software: you are free to change and redistribute it.\n"
               "There is NO WARRANTY, to the extent permitted by law.\n" );
  }


void show_error( const char * const msg, const int errcode = 0,
                 const bool help = false )
  {
  if( msg && msg[0] )
    {
    std::fprintf( stderr, "%s: %s", program_name, msg );
    if( errcode > 0 ) std::fprintf( stderr, ": %s", std::strerror( errcode ) );
    std::fputc( '\n', stderr );
    }
  if( help )
    std::fprintf( stderr, "Try '%s --help' for more information.\n",
                  invocation_name );
  }


void internal_error( const char * const msg )
  {
  std::fprintf( stderr, "%s: internal error: %s\n", program_name, msg );
  std::exit( 3 );
  }


void approximate_pi()
  {
  const std::string target( "3.141592653589793238462643383279502884197" );
  const int tlen = target.size();
  int max_len = 1;
  int n = 3, d = 1, dif = 0;

  std::printf( "target == %s\n", target.c_str() );
  std::fputs( "correct\ndecimals                  value\n", stdout );
  while( n <= INT_MAX - 3 )
    {
    const int q = n / d;
    if( q != 3 ) { if( q < 3 ) ++n; else { n += 3; ++d; } continue; }
    long long rest = n % d;
    int i = 2;
    for( ; i < tlen; ++i )
      {
      rest *= 10; dif = '0' + ( rest / d ) - target[i]; rest %= d;
      if( dif != 0 ) break;
      }
    if( i > max_len )
      {
      const Rational r( n, d );
      max_len = i;
      std::printf( "%2d      %s (%s)\n", i - 2,
                   r.to_decimal( 1, -(tlen - 2) ).c_str(),
                   r.to_fraction().c_str() );
      std::fflush( stdout );
      if( max_len >= tlen ) break;
      }
    if( dif < 0 ) ++n; else { n += 3; ++d; }
    }
  }


void approximate_sqrt( const int itarget )
  {
  const Rational target( itarget );
  Rational best_value( 1 ), best_error( itarget - 1 );
  const int prec = 10;
  int n = 1, d = 1;

  std::printf( "target == sqrt( %d )\n", itarget );
  std::fputs( "        error               value^2          value\n", stdout );
  while( n < INT_MAX )
    {
    const Rational value( n, d );
    Rational value2( value ); value2 *= value2;
    Rational error( value2 ); error -= target;
    if( value2.error() || error.error() ) break;
    if( error.abs() < best_error && error.abs() < 1 )
      {
      best_value = value; best_error = error.abs();
      std::printf( "%-21s    %-12s    %-12s (%s)\n",
                   error.to_decimal( 2, -( prec + 8 ) ).c_str(),
                   value2.to_decimal( 1, -prec ).c_str(),
                   value.to_decimal( 1, -prec ).c_str(),
                   value.to_fraction().c_str() );
      std::fflush( stdout );
      if( best_error == 0 ) break;
      }
    if( error < 0 ) ++n;
    else ++d;
    }
  }


int run_tests( const int level, const bool verbose )
  {
  int retval = 0;

  // relational on error test
  {
  const Rational r( 1, 0 );
  if( !r.error() )
    { std::fputs( "error: Rational( 1, 0 ) not rejected.\n", stderr );
      retval = 1; }
  if( r == 0 || r == 1 || r == INT_MAX || r == -INT_MAX ||
      !(r != 0) || !(r != 1) || !(r != INT_MAX) || !(r != -INT_MAX) ||
      r > -INT_MAX || r >= -INT_MAX || r < INT_MAX || r <= INT_MAX )
    { std::fputs( "error: bad relational result on error.\n", stderr );
      retval = 1; }
  }

  // ( num, 1 ) test
  {
  const Rational r0( INT_MAX, 1 );
  if( r0 != INT_MAX )
    { std::fputs( "error: Rational( INT_MAX, 1 ) not accepted.\n", stderr );
      retval = 1; }
  Rational r( INT_MIN, 1 );
  if( !r.error() )
    { std::fputs( "error: Rational( INT_MIN, 1 ) not rejected.\n", stderr );
      retval = 1; }
  r.assign( INT_MAX, 1 );
  if( r != INT_MAX || r != r0 )
    { std::fputs( "error: r.assign( INT_MAX, 1 ) not accepted.\n", stderr );
      retval = 1; }
  r.assign( INT_MIN, 1 );
  if( !r.error() )
    { std::fputs( "error: r.assign( INT_MIN, 1 ) not rejected.\n", stderr );
      retval = 1; }
  r.assign( -INT_MAX, 1 );
  if( r != -INT_MAX || r != -r0 || -r != r0 )
    { std::fputs( "error: r.assign( -INT_MAX, 1 ) not accepted.\n", stderr );
      retval = 1; }
  }

  // ( 1, num ) test
  {
  const Rational r0( 1, INT_MAX );
  if( r0.numerator() != 1 || r0.denominator() != INT_MAX )
    { std::fputs( "error: Rational( 1, INT_MAX ) not accepted.\n", stderr );
      retval = 1; }
  Rational r( 1, INT_MIN );
  if( !r.error() )
    { std::fputs( "error: Rational( 1, INT_MIN ) not rejected.\n", stderr );
      retval = 1; }
  r.assign( 1, INT_MAX );
  if( r.numerator() != 1 || r.denominator() != INT_MAX || r != r0 )
    { std::fputs( "error: r.assign( 1, INT_MAX ) not accepted.\n", stderr );
      retval = 1; }
  r.assign( 1, INT_MIN );
  if( !r.error() )
    { std::fputs( "error: r.assign( 1, INT_MIN ) not rejected.\n", stderr );
      retval = 1; }
  r.assign( 1, -INT_MAX );
  if( r.numerator() != -1 || r.denominator() != INT_MAX ||
      r != -r0 || -r != r0 )
    { std::fputs( "error: r.assign( 1, -INT_MAX ) not accepted.\n", stderr );
      retval = 1; }
  }

  // ( num, num ) test
  {
  const Rational r0( INT_MAX, INT_MAX );
  if( r0 != 1 )
    { std::fputs( "error: Rational( INT_MAX, INT_MAX ) not accepted.\n", stderr );
      retval = 1; }
  Rational r( INT_MIN, INT_MIN );
  if( r != 1 || r != r0 )
    { std::fputs( "error: Rational( INT_MIN, INT_MIN ) not accepted.\n", stderr );
      retval = 1; }
  r.assign( INT_MAX, INT_MAX );
  if( r != 1 || r != r0 )
    { std::fputs( "error: r.assign( INT_MAX, INT_MAX ) not accepted.\n", stderr );
      retval = 1; }
  r.assign( INT_MIN, INT_MIN );
  if( r != 1 || r != r0 )
    { std::fputs( "error: r.assign( INT_MIN, INT_MIN ) not accepted.\n", stderr );
      retval = 1; }
  r.assign( INT_MAX, -INT_MAX );
  if( r != -1 || r != -r0 || -r != r0 )
    { std::fputs( "error: r.assign( INT_MAX, -INT_MAX ) not accepted.\n", stderr );
      retval = 1; }
  }

  // ( num ) test
  {
  const Rational r0( INT_MAX );
  if( r0 != INT_MAX )
    { std::fputs( "error: Rational( INT_MAX ) not accepted.\n", stderr );
      retval = 1; }
  Rational r( INT_MIN );
  if( !r.error() )
    { std::fputs( "error: Rational( INT_MIN ) not rejected.\n", stderr );
      retval = 1; }
  r = INT_MAX;
  if( r != INT_MAX || r != r0 )
    { std::fputs( "error: ( r = INT_MAX ) not accepted.\n", stderr );
      retval = 1; }
  r = INT_MIN;
  if( !r.error() )
    { std::fputs( "error: ( r = INT_MIN ) not rejected.\n", stderr );
      retval = 1; }
  r = -INT_MAX;
  if( r != -INT_MAX || r != -r0 || -r != r0 )
    { std::fputs( "error: ( r = -INT_MAX ) not accepted.\n", stderr );
      retval = 1; }
  r = 0;
  if( r != 0 || r != r0 - r0 || r != -r )
    { std::fputs( "error: ( r = 0 ) not accepted.\n", stderr ); retval = 1; }
  r = r.inverse();
  if( !r.error() )
    { std::fputs( "error: inverse( 0 ) not rejected.\n", stderr );
      retval = 1; }
  }

  // zero test
  {
  const Rational r1( 0, 1 );
  const Rational r2( 0 );
  if( r1 != r2 || r1 != -r2 || r1 + r2 != 0 || r1 - r2 != 0 || r1 * r2 != 0 )
    { std::fputs( "error: ( 0, 1 ) != ( 0 )\n", stderr ); retval = 1; }
  const Rational r3( r2.inverse() );
  const Rational r4( 1, 0 );
  if( !r3.error() || !r4.error() || r3.numerator() != r4.numerator() ||
      r3.denominator() != r4.denominator() )
    { std::fprintf( stderr, "error: inverse( 0 ) [%d,%d] != Rational( 1, 0 ) [%d,%d]\n",
      r3.numerator(), r3.denominator(), r4.numerator(), r4.denominator() );
      retval = 1; }
  Rational r;
  if( r.numerator() != r2.numerator() || r.denominator() != r2.denominator() )
    { std::fprintf( stderr, "error: Rational() [%d,%d] != Rational( 0 ) [%d,%d]\n",
      r.numerator(), r2.denominator(), r.numerator(), r2.denominator() );
      retval = 1; }
  r.assign( 1, 0 );
  if( !r.error() || r.numerator() != r4.numerator() ||
      r.denominator() != r4.denominator() )
    { std::fprintf( stderr, "error: assign( 1, 0 ) [%d,%d] != Rational( 1, 0 ) [%d,%d]\n",
      r.numerator(), r.denominator(), r4.numerator(), r4.denominator() );
      retval = 1; }
  }

  // intermediate overflow test
  {
  const Rational r1( INT_MAX, 2 );
  const Rational r2( -INT_MAX, 2 );
  if( r1 != -r2 || -r1 != r2 || r1 + r2 != 0 ||
      r1 + r1 !=  INT_MAX || 2 * r1 !=  INT_MAX ||
      r2 + r2 != -INT_MAX || 2 * r2 != -INT_MAX )
    { std::fputs( "error: INT_MAX/2 + INT_MAX/2 != INT_MAX\n", stderr );
      retval = 1; }
  }


  const int sum_delta = 1000 * level * level * level;
  const int sum_limit = INT_MAX / 2;
  const int mul_limit = 46340;		// sqrt( 1 << 31 )

  // addition/comparison test
  for( int n = sum_limit - sum_delta; n <= sum_limit; ++n )
    {
    const int n2 = 2 * n;
    const Rational r1( n2, 2 );
    const Rational r2( n );
    const Rational r3( -n2, 2 );
    const Rational r4( -n );
    if( r1 != r2 || r2 != -r3 || r3 != r4 || r4 != -r1 ||
        -r1 + r2 != 0 || +r1 - r2 != 0 ||  n2 != r1 + r2 ||
        -r3 + r4 != 0 || +r3 - r4 != 0 || -n2 != r3 + r4 ||
        +r1 + r3 != 0 || -r1 - r3 != 0 ||  n2 != r1 - r3 ||
        +r2 + r4 != 0 || -r2 - r4 != 0 || -n2 != r4 - r2 )
      { std::fprintf( stderr, "error: ( 2 * %d, 2 ) != %d\n", n, n );
        retval = 1; break; }
    }

  // multiplication/division test
  for( int n = -mul_limit; n <= mul_limit; ++n )
    {
    if( n == 0 ) continue;
    const Rational r( n );
    if( r * n / r != n || r / n * r != n || r * r / r != n || r * n / r != r )
      { std::fprintf( stderr, "error: %d * %d / %d != %d\n", n, n, n, n );
        retval = 1; break; }
    }

  // multiplication by inverse test
  for( int n = -mul_limit; n <= mul_limit; ++n )
    {
    if( n == 0 ) continue;
    const Rational r1( n );
    const Rational r2( r1.inverse() );
    if( r1 * r2 != 1 )
      { std::fprintf( stderr, "error: %d * 1/%d != 1\n", n, n );
        retval = 1; break; }
    }

  // multiplication by INT_MAX inverse test
  {
  const Rational r1( INT_MAX );
  const Rational r2( 1, INT_MAX );
  const Rational r3( -INT_MAX );
  const Rational r4( 1, -INT_MAX );

  if( r1 * r2 !=  1 || r2 * r1 !=  1 || r3 * r4 !=  1 || r4 * r3 !=  1 ||
      r1 * r4 != -1 || r4 * r1 != -1 || r2 * r3 != -1 || r3 * r2 != -1 )
    { std::fprintf( stderr, "error: %d * 1/%d != 1\n", INT_MAX, INT_MAX );
      retval = 1; }

  if( r1 * r1.inverse() !=  1 || r2 * r2.inverse() !=  1 ||
      r3 * r3.inverse() !=  1 || r4 * r4.inverse() !=  1 ||
      r1 * r3.inverse() != -1 || r2 * r4.inverse() != -1 ||
      r3 * r1.inverse() != -1 || r4 * r2.inverse() != -1 )
    { std::fprintf( stderr, "error: %d * inverse( %d ) != 1\n", INT_MAX, INT_MAX );
      retval = 1; }

  if( r1 * r4.abs() !=  1 || r2 * r3.abs() !=  1 ||
      r4 * r1.abs() != -1 || r3 * r2.abs() != -1 ||
      r3 * r4.abs() != -1 || r4 * r3.abs() != -1 ||
      r3.abs() * r4.abs() != 1 || r4.abs() * r3.abs() != 1 )
    { std::fprintf( stderr, "error: %d * abs( 1/%d ) != 1\n", INT_MAX, INT_MAX );
      retval = 1; }
  }

  // operation chain test
  {
  const Rational r0( 1, 1000 );
  Rational r( r0 );
  const int n = 1000;
  const Rational rn( n );

  +r += n; r += rn; r *= n; ++r; r *= rn; r++;
  Rational ri( r );
  r--; r /= rn; --r; r /= n; r -= rn; +r -= n;
  if( r != r0 || ri != 2000002001 )
    { std::fprintf( stderr, "error: failed operation chain up ( ri == %s )\n",
                    ri.to_decimal( 1, -100 ).c_str() ); retval = 1; }

  r -= n; r -= rn; r *= n; --r; r *= rn; r--;
  ri = r;
  r++; r /= rn; ++r; r /= n; r += rn; r += n;
  if( r != r0 || ri != -2000000001 )
    { std::fprintf( stderr, "error: failed operation chain down ( ri == %s )\n",
                    ri.to_decimal( 1, -100 ).c_str() ); retval = 1; }
  }

  // round test
  {
  Rational rf( -1245, 10 );			// -124.5
  const Rational ra( 1, 4 );			//    0.25
  for( int i = -124; i <= 124; ++i )
    {
    if( (rf += ra).round() != i || (rf += ra).round() != i ||
        (rf += ra).round() != i || ( i != 0 && (rf += ra).round() != i ) )
      { std::fprintf( stderr, "error: (%s).round() == %d != %d )\n",
                      rf.to_decimal( 1, -100 ).c_str(), rf.round(), i );
        retval = 1; break; }
    }
  if( rf != Rational( 12425, 100 ) )
    { std::fprintf( stderr, "error: bad final value in round() test ( rf == %s )\n",
                    rf.to_decimal( 1, -100 ).c_str() ); retval = 1; }
  }

  // trunc test
  {
  Rational rf( -125 );
  const Rational ra( 1, 4 );			//    0.25
  for( int i = -124; i <= 124; ++i )
    {
    if( (rf += ra).trunc() != i || (rf += ra).trunc() != i ||
        (rf += ra).trunc() != i || (rf += ra).trunc() != i ||
        ( i == 0 && ( (rf += ra).trunc() != i ||
          (rf += ra).trunc() != i || (rf += ra).trunc() != i ) ) )
      { std::fprintf( stderr, "error: (%s).trunc() == %d != %d )\n",
                      rf.to_decimal( 1, -100 ).c_str(), rf.trunc(), i );
        retval = 1; break; }
    }
  if( rf != Rational( 12475, 100 ) )
    { std::fprintf( stderr, "error: bad final value in trunc() test ( rf == %s )\n",
                    rf.to_decimal( 1, -100 ).c_str() ); retval = 1; }
  }

  // addition loop and parse test
  {
  Rational sum( 0 );
  bool zero = false;
  for( Rational r( -123984, 1000 ), ra( 123, 1000 ); r < 124; )
    {
    const std::string s = r.to_decimal( 1, -10 );
    Rational r1;
    if( !r1.parse( s.c_str() ) || r1 != r )
      { std::fprintf( stderr, "error: parse error ( r == %s, r1 == %s )\n",
                      s.c_str(), r1.to_decimal( 1, -100 ).c_str() );
        retval = 1; }
    if( r == 0 ) zero = true;
    sum += r;
    r += ra;
    if( !( r1 < r ) )
      { std::fprintf( stderr, "error: comparison error ( %s < %s )\n",
                      s.c_str(), r.to_decimal( 1, -100 ).c_str() );
        retval = 1; }
    }
  if( sum != 0 )
    { std::fprintf( stderr, "error: sum is not zero ( sum == %s )\n",
                    sum.to_decimal( 1, -100 ).c_str() ); retval = 1; }
  if( !zero )
    { std::fputs( "error: zero not reached in sum loop.\n", stderr );
      retval = 1; }
  }

  // multiplication loop and parse test
  {
  bool one = false;
  for( Rational r( 8192, 1220703125 ), rm( 25, 10 ); !r.error(); )
    {
    const std::string s = r.to_decimal( 1, -100 );
    Rational r1;
    if( !r1.parse( s.c_str() ) || r1 != r )
      { std::fprintf( stderr, "error: parse error ( r == %s, r1 == %s )\n",
                      s.c_str(), r1.to_decimal( 1, -100 ).c_str() );
        retval = 1; }
    if( r == 1 ) one = true;
    r *= rm;
    if( r.error() && r1 < 149011 )
      { std::fprintf( stderr, "error: early overflow in mul loop ( r1 == %s )\n",
                      r1.to_decimal( 1, -100 ).c_str() ); retval = 1; }
    }
  if( !one )
    { std::fputs( "error: one not reached in mul loop.\n", stderr );
      retval = 1; }
  }

  // parse error test
  {
  Rational r( 123, 456 );		// 41/152
  if( r.parse( "789/0" ) || r.parse( "789." ) || r.parse( ".-789" ) ||
      r.parse( "789/%" ) || r.parse( "789.%" ) )
    { std::fprintf( stderr, "error: unexpected parse() success ( r == %s )\n",
                    r.to_fraction().c_str() ); retval = 1; }
  else if( r != Rational( 123, 456 ) )
    { std::fprintf( stderr, "error: parse() modified value on error ( r == %s )\n",
                    r.to_fraction().c_str() ); retval = 1; }
  }

  if( verbose && retval == 0 ) std::fputs( "Test passed.\n", stderr );
  return retval;
  }

} // end namespace


int main( const int argc, const char * const argv[] )
  {
  int level = 0;
  int sqrt_target = 0;
  bool pi_flag = false;
  bool verbose = false;
  invocation_name = argv[0];

  const Arg_parser::Option options[] =
    {
    { 'h', "help",    Arg_parser::no  },
    { 'p', "pi",      Arg_parser::no  },
    { 'q', "quiet",   Arg_parser::no  },
    { 's', "sqrt",    Arg_parser::yes },
    { 't', "test",    Arg_parser::yes },
    { 'v', "verbose", Arg_parser::no  },
    { 'V', "version", Arg_parser::no  },
    {  0 , 0,         Arg_parser::no  } };

  const Arg_parser parser( argc, argv, options );
  if( parser.error().size() )				// bad option
    { show_error( parser.error().c_str(), 0, true ); return 1; }

  int argind = 0;
  for( ; argind < parser.arguments(); ++argind )
    {
    const int code = parser.code( argind );
    if( !code ) break;					// no more options
    const char * const arg = parser.argument( argind ).c_str();
    switch( code )
      {
      case 'h': show_help(); return 0;
      case 'p': pi_flag = true; break;
      case 'q': verbose = false; break;
      case 's': sqrt_target = strtoul( arg, 0, 0 );
                if( sqrt_target < 2 )
                  { show_error( "Bad sqrt target", 0, true ); return 1; }
                break;
      case 't': if( std::isdigit( *arg ) && *arg != '0' && !arg[1] )
                  level = *arg - '0';
                else { show_error( "Bad test level", 0, true ); return 1; }
                break;
      case 'v': verbose = true; break;
      case 'V': show_version(); return 0;
      default : internal_error( "uncaught option." );
      }
    } // end process options

  int retval = 0;
  if( level > 0 ) retval = run_tests( level, verbose );

  for( int i = 0; argind + i < parser.arguments(); ++i )
    {
    const char * const arg = parser.argument( argind + i ).c_str();
    Rational r;
    if( r.parse( arg ) )
      std::printf( "argument %d == %s (%s)\n", i + 1,
                    r.to_decimal( 1, -40 ).c_str(), r.to_fraction().c_str() );
    else
      { std::printf( "error parsing argument %d (%s)\n", i + 1, arg );
        retval = 1; }
    }

  if( pi_flag ) approximate_pi();
  if( sqrt_target > 0 ) approximate_sqrt( sqrt_target );
  return retval;
  }
