/********************************************************************
 ********************************************************************
 ** USAGE:  topcc [ --seq | --mpi | --pthread ] THIS_FILE
 ** ALGORITHM:  Euclidean sieve for factorization
 ** shared data:  num_to_factor (divided by each factor found)
 ** task input:   input (test factor for num_to_factor)
 ** task output:  1 or 0 (true or false)
 ** update:  Divide num_to_factor by num
 ********************************************************************
 ********************************************************************/

#include <stdlib.h> // for atol() [ Note long is only 32 bits on many mach's]
#include "topc.h"

#ifndef TASK_INTERVAL
#define TASK_INTERVAL 1000
#endif

// Used if TOPC_OPT_trace == 2, or: ./a.out --TOPC-trace=2
void trace_input( long *input ) { printf("%ld", *input); } 
void trace_result( long *input, long *output ) {
  if (*output == 1) printf("TRUE");
  if (*output == 0) printf("FALSE");
}

long factors[1000], max_factor=1, num_to_factor, next_num;
// TOP-C callback functions:
TOPC_BUF GenerateTaskInput(void);
TOPC_BUF DoTask( long *input );
TOPC_ACTION CheckTaskResult( long *input, long *output );
void UpdateSharedData( long *input, long *output );

int main(int argc, char *argv[])
{
  int i;

  // Set up defaults.  Can be overridden, e.g.:  ./a.out --TOPC-trace=0
  TOPC_OPT_trace_input = trace_input;
  TOPC_OPT_trace_result = trace_result;
  TOPC_OPT_trace = 2;
  TOPC_init(&argc, &argv);
  // Important:  Inspect command line only after TOPC_init()
  if (argc == 1 ) {
    if (TOPC_is_master()) {
      printf("WARNING: Missing number arg on command line. Using 123456789\n");
      num_to_factor = 123456789;
    } else
      num_to_factor = atol(argv[1]);
  }
  if (num_to_factor < 2) {
    fprintf(stderr, "Can't factor number less than 2\n"); exit(1);
  }

  factors[0]=0; // factors[0] is number of factors found so far
  next_num = 2 - TASK_INTERVAL; // last number factored
  TOPC_master_slave(GenerateTaskInput, DoTask, CheckTaskResult,
                    UpdateSharedData);

  if ( TOPC_is_master() ) {
    for (i = 1; i <= factors[ 0 ]; i++) printf("%ld ", factors[i]);
    printf("\n"); }
  TOPC_finalize();
  // printf("%d: Exiting\n", TOPC_rank()); fflush(stdout);
  exit(0);
}

TOPC_BUF GenerateTaskInput() {
  next_num = next_num + TASK_INTERVAL;
  if ( next_num > num_to_factor ) return NOTASK;
  else return TOPC_MSG(&next_num, sizeof(next_num));
}

TOPC_BUF DoTask( long *input )
{
  long limit;
  long num = *input;
  long task_out;

  limit = num + TASK_INTERVAL;
  for ( ; num < limit; num++ )
    if (num_to_factor % num == 0) {
      task_out = 1;
      return TOPC_MSG(&task_out, sizeof(long));
    }
  task_out = 0;
  return TOPC_MSG(&task_out, sizeof(long));
}

TOPC_ACTION CheckTaskResult( long *input, long *output )
{
  if ( *output == 0 ) return NO_ACTION;
  if ( TOPC_is_up_to_date() ) return UPDATE;
  if ( *input < max_factor ) return UPDATE;
  else return REDO;
}

void UpdateSharedData( long *input, long *output )
{
  long limit, num = *input;
  int i;
  limit = num + TASK_INTERVAL;
  // NOTE: Suppose we factor 12, 4 is reported as factor before 2 is reported
  for ( ; num < limit; num++ ) {
    if ( num_to_factor % num == 0 ) {
      if ( num < max_factor ) {
        max_factor = 1; // re-compute max_factor
        for( i = 1; i <= factors[0]; i++ ) {
          if (factors[i] > max_factor) max_factor = factors[i];
          while (factors[i] % num == 0) {
            factors[i] = factors[i] / num;
            num_to_factor = num_to_factor * num;
          }
        }
      }
      while (num_to_factor % num == 0) {
        factors[ ++factors[0] ] = num;
        num_to_factor = num_to_factor / num;
        if (num_to_factor == 1) return;
      }
    }
  }
}