#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#define MAX_HOSTS_NUM 200

#define MAX_LINE_LENGTH 100000
#define MAX_HOSTNAME_LENGTH 200

int readHostNames( FILE *fpin, char *host_names[]);

void initStructures( int Oij[][MAX_HOSTS_NUM], int Oj[],
                     int Iij[][MAX_HOSTS_NUM+1], float PR[],
                     int hosts_num);

void readHostGraph_ComputeOij( FILE *fpin, int Oij[][MAX_HOSTS_NUM],
                               int hosts_num);

void computeOj( int Oj[], int Oij[][MAX_HOSTS_NUM], int hosts_num);

void computeIij( int Iij[][MAX_HOSTS_NUM+1], int Oij[][MAX_HOSTS_NUM],
                 int hosts_num);

void computePR( float PR[], int Oij[][MAX_HOSTS_NUM],
                int Oj[], int Iij[][MAX_HOSTS_NUM+1], int hosts_num);

void printOij( int Oij[][MAX_HOSTS_NUM], int hosts_num);
void printOj( int Oj[], int hosts_num);
void printIij( int Iij[][MAX_HOSTS_NUM+1], int hosts_num);
void printPR( float PR[], int hosts_num, char *host_names[]);

float euclideanDistance( float PR[], float next_PR[], int length);

void strRemoveNewLineChar( char str[]);
FILE *openFile( char *filename, char *mode);


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

   char *host_names[MAX_HOSTS_NUM];

   int Oij[MAX_HOSTS_NUM][MAX_HOSTS_NUM],
       Oj[MAX_HOSTS_NUM],
       Iij[MAX_HOSTS_NUM][MAX_HOSTS_NUM+1],
       hosts_num;

   float PR[MAX_HOSTS_NUM];

   if (argc != 3){
      printf("Wrong number of arguments.\n");
      printf("Usage: %s hostnames_file hostgraph_file\n", argv[0]);
      exit(1);
   }


   fpin= openFile(argv[1], "r");
   hosts_num= readHostNames(fpin, host_names);
   fclose(fpin);

   initStructures(Oij, Oj, Iij, PR, hosts_num);

   fpin= openFile(argv[2], "r");
   readHostGraph_ComputeOij(fpin, Oij, hosts_num);
   fclose(fpin);

   computeOj(Oj, Oij, hosts_num);
   computeIij(Iij, Oij, hosts_num);
   computePR(PR, Oij, Oj, Iij, hosts_num);

   printOij(Oij, hosts_num);
   printOj(Oj, hosts_num);
   printIij(Iij, hosts_num);
   printPR(PR, hosts_num, host_names);

   return 0;
}



int readHostNames( FILE *fpin, char *host_names[])
{
   /*   Reads host names and host ids from file fpin.
    *   Computes host_names[].
    *
    *   The structure of each line of fpin is:
    *   id name
    *
    *   Host with id=i and name=host_name is stored in
    *   host_names[i]==host_name.
    *
    *   It assumes hosts ids start from 0 and are incremented by 1
    *   (but they can be in any order in file fpin, e.g.
    *   host with id=2 first, host with id=0 second,
    *   host with id=1 third etc.
    *
    *   Returns the number of hosts read.
    */

   char line[MAX_LINE_LENGTH], line_copy[MAX_LINE_LENGTH],
        *delimeter=" ", *host_name, *token;

   int host_id, hosts_num, line_num;


   hosts_num= 0;
   line_num= 0;

   while (fgets(line, MAX_LINE_LENGTH, fpin) != NULL){
      line_num++;
      strcpy(line_copy, line);

      strRemoveNewLineChar(line);

      /* We tokenize each line of file fpin,
         based on the characters of delimeter string. */

      token= strtok(line, delimeter);

      if (token == NULL){
         printf("\n* Input file has bad structure \
                at the beggining of line: %d.\n",line_num);
         printf("* Line itself follows (without the ||):\n");
         printf("|%s|\n", line_copy);
         printf("* Exiting.\n");
         exit(3);
      }

         /* First token is the host id. */
      host_id= atoi(token);


      token= strtok(NULL, delimeter);

      if (token == NULL){
         printf("\n* Input file has bad structure \
                at line: %d.\n", line_num);
         printf("* Line itself follows (without the ||):\n");
         printf("|%s|\n", line_copy);
         printf("* Exiting.\n");
         exit(3);
      }

         /*   Second token is the host name.
          *   Note that we have to allocate memory. */
      host_name= (char *)malloc( strlen(token) * sizeof(char) );

      if (host_name == NULL){
         printf("\n* Error in allocating memory in readHostNames.\n");
         printf("Exiting.\n");
         exit(3);
      }

      strcpy(host_name, token);

         /* Note: strcpy(host_names[host_id], host_name)
          * would be wrong (why?). */

      host_names[host_id]= host_name;

      hosts_num++;
   } /* end while */

   return hosts_num;
}



void initStructures( int Oij[][MAX_HOSTS_NUM], int Oj[],
                     int Iij[][MAX_HOSTS_NUM+1],
                     float PR[], int hosts_num)
{
      /*   Initialises our array structures. */

   int i, j;


   for (i= 0; i<= hosts_num-1; i++){
      Oj[i]= 0;
      PR[i]= 1.0;

      for (j=0; j<= hosts_num-1; j++){
         Oij[i][j]= 0;
         Iij[i][j]= 0;
      }
   }

   return;
}



void readHostGraph_ComputeOij( FILE *fpin, int Oij[][MAX_HOSTS_NUM],
                               int hosts_num){

      /*   Reads Oij information from fpin, and computes Oij[]][].
       *
       *   The structure of each line of fpin is:
       *   src -> dest1:nlinks1 dest2:nlinks2 ... destk:nlinksk
       *
       *   Oij[i][j] is the number of links from
       *   host with id=j towards host with id=i,
       *   and is already initialised to 0.
       */

   char line[MAX_LINE_LENGTH], line_copy[MAX_LINE_LENGTH],
        *delimeter_start=" ->", delimeter_following= ':',
        *token, *char_ptr;

   int host_i, host_j, links_num, line_num;

   line_num= 0;

   while (fgets(line, MAX_LINE_LENGTH, fpin) != NULL){

      line_num++;
      strcpy(line_copy, line);

      strRemoveNewLineChar(line);

         /*   We tokenize each line of file fpin,
          *   based on the characters of delimeter_start string. */

      token= strtok(line, delimeter_start);

      if (token == NULL){
         printf("\n* Input file has bad structure \
                at the beggining of line: %d.\n", line_num);
         printf("* Line itself follows (without the ||):\n");
         printf("|%s|\n", line_copy);
         printf("* Exiting.\n");
         exit(3);
      }

         /* First token is host_j id. */
      host_j= atoi(token);


         /*   We tokenize the rest of each line of file fpin,
          *   based on the characters of delimeter_start string.
          *   Space character of delimeter_start will now be used.*/

      while ( (token= strtok(NULL, delimeter_start)) != NULL){
         /*   Each next token has the form host_i_id:nlinksi, where
          *   nlinksi is the number of links from host_j to host_i. */

             /* delimeter_following is char ':'. */
         char_ptr= strchr(token, delimeter_following);

         if (char_ptr == NULL){
            printf("\n* Input file has bad structure at some part \
                   of line: %d.\n", line_num);
            printf("* Line itself follows (without the ||):\n");
            printf("|%s|\n", line_copy);
            printf("* Exiting.\n");

            exit(3);
         }

            /*   Now char_ptr points to ':' of the token
             *   of the form host_i_id:nlinksi, so,
             *   to retrieve the nlinksi part, we use char_ptr+1. */

         links_num= atoi(char_ptr + 1);

            /*   We don't need the nlinksi part of token any more,
             *   so we discard it in order to retrieve
             *   the first host_i_id part of the token. */

         *char_ptr='\0';
         host_i= atoi(token);
         Oij[host_i][host_j]+= links_num;

      } /* end while */
   } /* end while */

   return;
}



void computeOj( int Oj[], int Oij[][MAX_HOSTS_NUM], int hosts_num)
{
      /*   Computes Oj[], using Oij[][].
       *
       *   Oj[j] is the total number of links starting from
       *   host with id=j, and is already initialised to 0.
       */

   int i, j;


      /* We just have to run through Oij[][] by columns. */
   for (j= 0; j<= hosts_num-1; j++)
   for (i= 0; i<= hosts_num-1; i++)
      Oj[j]+= Oij[i][j];

   return;
}



void computeIij( int Iij[][MAX_HOSTS_NUM+1], int Oij[][MAX_HOSTS_NUM],
                 int hosts_num)
{
      /*   Computes Iij[][], using Oij[][].
       *
       *   The structure of each line i of Iij[i][], for host i, is:
       *   Iij[i][0] contains the total number of hosts pointing
       *   to host i (hosts_pointingto_i). Each of the
       *   following cells Iij[i][j], 1<= j <=hosts_pointingto_i,
       *   contains the host_id hj of host hj pointing to host i.
       *
       *   Iij[][] is already initialised to 0.
       */

   int i, j, hosts_pointingto_i;


   hosts_pointingto_i= 0;

     /* We run through Oij[][] by rows. */

   for (i= 0; i<= hosts_num-1; i++){

      for (j= 0; j<= hosts_num-1; j++){
         if (Oij[i][j] != 0){
            hosts_pointingto_i++;
            Iij[i][hosts_pointingto_i]= j;
         }
      }
      Iij[i][0]= hosts_pointingto_i;
      hosts_pointingto_i= 0;
   }
   return;
}


void computePR( float PR[], int Oij[][MAX_HOSTS_NUM],
                int Oj[], int Iij[][MAX_HOSTS_NUM+1], int hosts_num){

      /*   Computes array PR[], using arrays Oij[][], Oj[] and Iij[][].
       *
       *   PR[i] is the rank of host with id=i,
       *   and is already initialised.
       */

   const float d= 0.85;
   const float limit= 0.01;

   float *next_PR, first_factor, second_factor, sum_factor,
         euclidean_distance;

   int i, j, hj, hosts_pointingto_i;

   /*   Allocate memory for next_PR[hosts_num]. */

   next_PR= (float *)calloc(hosts_num, sizeof(float));

   if (next_PR == NULL){
      printf("*Out of memory, trying to allocate next_PR.\nExiting.\n");
      exit(2);
   }

      /* Initial values. */
   first_factor= (1-d)/hosts_num;
   sum_factor= 0.0;

   int loop= 1;

   while (1){
      /* We calculate the next_PR[] vector. */
      for (i= 0; i<= hosts_num-1; i++){

         hosts_pointingto_i= Iij[i][0];

         for (j= 1; j<= hosts_pointingto_i; j++){

            hj= Iij[i][j];
            if (Oj[hj] != 0){
			sum_factor+= (PR[hj] * Oij[i][hj]) / Oj[hj];
            }
            else{
               printf("\n*!* This cannot happen in function computePR");
               printf("\nExiting.\n");
               exit(4);
            }
         }
         second_factor= d * sum_factor;
         next_PR[i]= first_factor + second_factor;

         sum_factor= 0.0;
      }

      euclidean_distance= euclideanDistance(PR, next_PR, hosts_num);

      loop++;


      if (euclidean_distance < limit){
         free(next_PR);
         break;
      }
      else{
         for (i= 0; i<= hosts_num-1; i++){
            PR[i]= next_PR[i];
         }
      }
   }
   return;
}



float euclideanDistance( float PR[], float next_PR[], int length)
{
      /*   Calculates the Euclidean distance of two vectors PR[]
       *   and next_PR of length length.
       *
       *   The Euclidean distance of two vectors X, Y, where
       *   X=(x1, x2, ..., xn) and Y=(y1, y2, ..., yn), is given by
       *   the square root of the sum of the squares of the differences
       *   of their elements, i.e. sqrt(sum((xi - yi)^2)) */

   float eucl_dist, diff, sum;
   int i;

   sum= 0.0;

   for (i= 0; i<= length-1; i++){
      diff= PR[i] - next_PR[i];
      sum+= diff * diff;
   }

   eucl_dist= sqrt(sum);

   return eucl_dist;
}



void printOij( int Oij[][MAX_HOSTS_NUM], int hosts_num)
{
   int i, j, links_num;


   printf("\n+++ Start of printing structure Oij +++\n");
   printf("The structure of each line is:\n");
   printf("src -> dest1:nlinks1 dest2:nlinks2 ... destk:nlinksk\n\n");

   for (j= 0; j<= hosts_num-1; j++){

      printf("%d ->", j);

      for (i= 0; i<= hosts_num-1; i++){
         links_num= Oij[i][j];
         if (links_num > 0){
            printf(" %d:%d", i, links_num);
          }
      }

      printf("\n");

   }

   printf("\n--- End of printing structure Oij ---\n");
   return;
}



void printOj( int Oj[], int hosts_num)
{
   int j;

   printf("\n\n+++ Start of printing structure Oj +++\n");
   printf("The structure of each line is:\n");
   printf("src -=> links_total\n\n");

   for (j= 0; j<= hosts_num-1; j++){
      printf("%d -=> %d\n", j, Oj[j]);
   }

   printf("\n--- End of printing structure Oj ---\n");

   return;
}



void printIij( int Iij[][MAX_HOSTS_NUM+1], int hosts_num)
{
   int i, j, hosts_pointingto_i;


   printf("\n\n+++ Start of printing structure Iij +++\n");
   printf("The structure of each line is:\n");
   printf("dest <== hosts_total hostid1 hostid2 ... hostidk\n\n");

   for (i= 0; i<= hosts_num-1; i++){

      hosts_pointingto_i= Iij[i][0];

      printf("%d <== %d", i, hosts_pointingto_i);
      for (j= 1; j<= hosts_pointingto_i; j++){
         printf(" %d", Iij[i][j]);
      }
      printf("\n");
   }

   printf("\n--- End of printing structure Iij ---\n");
   return;
}


void printPR( float PR[], int hosts_num, char *host_names[])
{
   const float UNDEF= -1;
   float *norm_PR, sum_PR;
   int i;


      /*   Allocate memory for norm_PR[hosts_num]. */

   norm_PR= (float *)calloc(hosts_num, sizeof(float));

   if (norm_PR == NULL){
      printf("*Out of memory, trying to allocate next_PR.\nExiting.\n");
      exit(2);
   }

   /* Compute normalised PR, norm_PR[]= PR[i] / sum(PR[i]). */

   sum_PR= 0.0;

   for (i= 0; i<= hosts_num-1; i++){
      sum_PR+= PR[i];
   }

   for (i= 0; i<= hosts_num-1; i++){

      if (sum_PR != 0){
         norm_PR[i]= PR[i] / sum_PR;
      }
      else{
         norm_PR[i]= UNDEF;
      }
   }


   printf("\n\n+++ Start of printing PR +++\n");
   printf("\nhost_id\thost_name\thost_rank\tnorm_host_rank\n");

   for (i= 0; i<= hosts_num-1; i++){
      printf("%d\t%s\t%.3f\t%.2f\n", i, host_names[i],
                                     PR[i], norm_PR[i]);
   }

   printf("\n--- End of printing PR ---\n");

   free(norm_PR);
   return;
}



void strRemoveNewLineChar( char str[])
{
   char new_line_char= '\n', carriage_return_char='\r', *position;

   /* There is the DOS/Unix CR-LF matter
    * (CarriageReturn - LineFeed, LF is the new line character. */

      /* Set position to point to carriage_return_char of str. */
   position= strchr(str, carriage_return_char);

      /* If there is no carriage_return_char in str. */
   if (position == NULL){
      /* Set position to point to new_line_char of str. */
      position= strchr(str, new_line_char);
   }

     /* If there is carriage_return_char or new_line_char in str. */
   if (position != NULL){
      *position= '\0';
   }

   return;
}




FILE *openFile( char *filename, char *mode)
{
   FILE *fp;


   fp= fopen(filename, mode);

   if (fp==NULL){
      printf("Cannot open file: %s.\nExiting.\n", filename);
      exit(1);
      return NULL;
   }
   else{
      return fp;
   }
}