/*----------------------------------------------------------------------
//
//	compile with: mc -o allpairs -sync mpc allpairs.m
//	execute with: allpairs -input <in.file> -output <out.file>
//
//  parpath - parallel all-pairs shortest path algorithm
//            Written by Mike Patterson for CS133, Winter 96
//            Revised for consistency by Richard Meyer
//
// This parallel version performs row striping on the initial
// paths (A) matrix.
//
// For each iteration, k:
//
// the kth process passes its row values to all other
// processes, which use it to check each of their row values
// in the min() function listed above.
//
// Takes the following command line parameters:
//  -input  file, where file is the name of a file with the format:
//     N                                // size of graph 
//     blank line
//     NxN matrix, N elements per line  // -1 if no edge from i to j
//                                      //  0  if i == j
//                                      // >0 otherwise  
//  -output file, where file is the name of the output file.
//--------------------------------------------------------------------*/

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "maisie.h"

#define MAXSIZE 64

/*----------------------------------------------------------------------
// Min just returns the minimum of value1 and value2
//--------------------------------------------------------------------*/
int Min(value1, value2)
 int value1, value2;
{
  if (value1 < value2)
    return(value1);
  return(value2);
}

/*----------------------------------------------------------------------
// MaxIntSize
//
// Returns the number of characters val takes when printed.
//--------------------------------------------------------------------*/
int MaxIntSize(val)
 int val;
{
  int size = 1;     /* even '0' takes one space */

  if (val < 0) {
    val = abs(val);
    size++;         /* for the minus sign */
  }

  while (val > 9) {
    val = val / 10;
    size++;  
  }

  return(size);
}

/*----------------------------------------------------------------------
// PrintMatrix
//
// Prints the matrix to the output file.
//--------------------------------------------------------------------*/
int PrintMatrix(file, matrix, size)
 FILE* file;
 int   matrix[MAXSIZE][MAXSIZE];
 int   size;
{
  int  i, j;
  int  maxval;
  int  padding;
  char formatstring[10];

  maxval = 0;
  for (i = 0; i < size; i++)
    for (j = 0; j < size; j++)
      if (abs(maxval) < abs(matrix[i][j])) 
        maxval = matrix[i][j];
  
  padding = MaxIntSize(maxval) + 1;

  /* This next line creates something like "%4d" for the print
     stmt below, replacing the 4 with the padding value */

  sprintf(formatstring, " %%%dd", padding);

  for (i = 0; i < size; i++) {
    for (j = 0; j < size; j++)
      fprintf(file, formatstring, matrix[i][j]);
    fprintf(file, "\n");
  }
  fprintf(file, "\n");
  fclose(file);
}

/*----------------------------------------------------------------------
// ReadFile
//
// Reads in the digraph.
//--------------------------------------------------------------------*/
int ReadFile(file, size, graph)
 FILE* file;
 int*  size;
 int   graph[MAXSIZE][MAXSIZE];
{
  int i, j;

  assert(file != NULL);

  fscanf(file, "%d", size);

  for (i = 0; i < (*size); i++)
    for (j = 0; j < (*size); j++)
      fscanf(file, "%d", &graph[i][j]);

  fclose(file);
  return(1);
}

/*----------------------------------------------------------------------
// ParseArgs
//
// Parses the command line arguments.
//--------------------------------------------------------------------*/
int ParseArgs(argc, argv, inf, outf)
 int   argc; 
 char* argv[]; 
 FILE** inf;
 FILE** outf;
{
  int i;

  for (i = 0; i < argc; i++)
    if (strcasecmp(argv[i], "-input") == 0) {
      if (++i < argc) {
        if ((*inf = fopen(argv[i], "r")) == 0) {
          printf("Can't open input file.\n");
          return (0);
        }
      }
      else {
        printf("Not enough arguments.");
        printf("USAGE: %s -input infile -output outfile\n", argv[0]);
        return (0);
      }
    }
    else if (strcasecmp(argv[i], "-output") == 0) {
      if (++i < argc) {
        if ((*outf = fopen(argv[i], "w")) == 0) {
          printf("Can't open output file.\n");
          return (0);
        }
      }
      else {
        printf("Not enough arguments.");
        printf("USAGE: %s -input infile -output outfile\n", argv[0]);
        return (0);
      }
    }

  return(1);
}


/*----------------------------------------------------------------------
// FillInMatrix
//
// Used to place a row vector into the matrix.
//--------------------------------------------------------------------*/
int FillInMatrix(matrix, size, row, vector)
 int matrix[MAXSIZE][MAXSIZE];
 int size;
 int row;
 int vector[MAXSIZE];
{
  int j;

  for (j = 0; j < size; j++)
    matrix[row][j] = vector[j];
}


/*----------------------------------------------------------------------
// Driver entity
//
// Reads the input, creates the node entities, collects and prints
// the results.
//--------------------------------------------------------------------*/
entity driver{argc, argv}
 int argc;
 char **argv;
{
  int   size;                        /* size of digraph                */
  int   i;                           /* generic counters and indices   */
  int   processors;
  int   block_size;
  int   graph[MAXSIZE][MAXSIZE]; 
  FILE* in_file;
  FILE* out_file;

  ename nodes[MAXSIZE];

  message Init {ename nodes[MAXSIZE];} init;
  message Row  {int row[MAXSIZE]; int node;} row;

  if (!ParseArgs(argc, argv, &in_file, &out_file))
    terminate();

  if (!ReadFile(in_file, &size, graph)) {
    printf("program terminating\n");
    terminate();
  }

  processors = nnodes();
  block_size = size / processors;
  if (size % processors)
    block_size++;

  for (i = 0; i < processors; i++) {
    nodes[i] = new Node{i, size, block_size, processors, self} at i;
  }

  for (i = 0; i < processors; i++)
    invoke nodes[i] with Init{nodes};

  for (i = 0; i < size; i++)
    invoke nodes[i/block_size] with Row{graph[i], i};

  for (i = 0; i < size; i++)
    wait until row = mtype (Row)
      FillInMatrix(graph, size, row.node, row.row);

  PrintMatrix(out_file, graph, size);

  terminate();
}

/*----------------------------------------------------------------------
// entity Node
//
// Calculates the shortest path for a row.
//--------------------------------------------------------------------*/
entity Node {mynode, size, block_size, processors, spokesperson}
 int   mynode;
 int   size;
 int   block_size;
 int   processors;
 ename spokesperson;
{
  int i, j, k;
  int my_block_size, my_base;
  ename nodes[MAXSIZE];
  ename myid;
  int   graph[MAXSIZE][MAXSIZE];

  message Init {ename nodes[MAXSIZE];} init;
  message Row {int row[MAXSIZE]; int node;} row;

  my_block_size = Min(block_size, (size - (mynode * block_size)));
  my_base = block_size * mynode;

  wait until
    mtype (Init)
      for (i = 0; i < size; i++)
        nodes[i] = msg.Init.nodes[i];

  for (i = 0; i < my_block_size; i++)
    wait until row = mtype (Row) {
      FillInMatrix(graph, size, row.node, row.row);
    }

  for (k = 0; k < size; k++) {
    if (mynode == (k/block_size)) {
      for (i = 0; i < processors; i++)
        invoke nodes[i] with Row{graph[k], k};
    }

    wait until
      row = mtype (Row) st (msg.Row.node == k)
        ; /* do nothing */

    for (i = my_base; i < (my_base + my_block_size); i++) {
      if (graph[i][k] < 1) continue;
      for (j = 0; j < size; j++) {
        if (row.row[j] < 1)
          continue;
        if (graph[i][j] < 0)
          graph[i][j] = graph[i][k] + row.row[j];
        else
          graph[i][j] = Min(graph[i][j], (graph[i][k] + row.row[j]));
      }
    }
  }

  for (i = my_base; i < (my_base + my_block_size); i++)
    invoke spokesperson with Row{graph[i], i};
}