#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/stat.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
#include <errno.h>
#include <math.h>
#include <sys/wait.h>
#include <unistd.h>

void errormsg( char *msg ) {
   perror( msg );
   exit( 1 );
}

int sum(int arr[], int m) {
    int sum = 0; // initialize sum

    // Iterate through all elements
    // and add them to sum
    for (int i = 0; i < m; i++)
		sum += arr[i];

    return sum;
}

int main(int argc, char* argv[]) {
	int n;                 		// size of input array
	int m;                 		// number of processes that will perform the work
	char * input_file;			// input file name
	char * output_file;			// output file name

	int numIter;				// Total number of iterations to find the prefix sum output array
	int id;						// Tracks the id/index each child is responsible for
	int pid;					// Check if a process is child or parent
	int N_MEMORY_SIZE; 			// Dynamic size to allocate for the N element arrays
	int M_MEMORY_SIZE; 			// Dynamic size to allocate for the M element arrays

	int * input_arr;			// Stores the input nums
	int * temp_arr;				// Stores the initial array at the beginning of each iteration
	int * final_arr;			// Stores the final array at the end of each iteration
	int * working;				// Working array of size m to track the id of each child
	int * t;					// Used to switch the reference between temp and final arrays at the end of each iteration

	int tempSId;				// temp arrya shared segment id
	int finalSId;				// final array shared segment id
	int workingSId;				// working array shared segment id

	//printf("Finished declaring variables\n");

	if (argc == 5){
		n = atoi(argv[1]); 		// Read the integer n value
		input_file = argv[2]; 	// Store the input text file name
		output_file = argv[3]; 	// Store the output text file name
		m = atoi(argv[4]);		// Store the number of processes as an integer

	} else{
		// Number of input parameters does not match
		printf("Please enter the correct input values (n input_file output_file m)!\n");
		return 1;
	}

	N_MEMORY_SIZE = sizeof(int) * n;	// Total size for an array of n int values
	M_MEMORY_SIZE = sizeof(int) * m;	// Total size for an array of m int values
	numIter = ceil(log(n)/log(2));		//correct handle rounding

	// Initialize the current id to be 0
	id = 0;

	input_arr = (int *)malloc(N_MEMORY_SIZE); 	// Dynamically create an array to store input values

	// Create and store the shared segment id for each array

	tempSId = shmget(IPC_PRIVATE, N_MEMORY_SIZE, S_IRUSR | S_IWUSR);	// Create a shared memory segment of size N ints for temp_arr
	if ( tempSId < 0 ) errormsg( "ERROR in creating a shared memory segment for TEMP ARRAY\n" );

	finalSId = shmget(IPC_PRIVATE, N_MEMORY_SIZE, S_IRUSR | S_IWUSR);	// Create a shared memory segment of size N ints for final_arr
	if ( finalSId < 0 ) errormsg( "ERROR in creating a shared memory segment for FINAL ARRAY\n" );

	workingSId = shmget(IPC_PRIVATE, M_MEMORY_SIZE, S_IRUSR | S_IWUSR);	// Create a shared memory segment of size M ints for working array
	if ( workingSId < 0 ) errormsg( "ERROR in creating a shared memory segment for WORKING ARRAY\n" );

	// Read num values from the input file specified
	FILE* inFile = fopen(input_file, "rb");
	int num = 0; // Used to read each number in the file
	int numCount; // Stores the count of numbers in the input file to compare with N later
	for(numCount = 0; fscanf(inFile, "%d", &num) && !feof(inFile); numCount++)
		if (numCount < n){ // Make sure that the number of values in the input file do not exceed n (size of input_arr)
			input_arr[numCount] = num;	// Store each num value in the input_arr
		}
	fclose(inFile);

	// If the count of numbers in the file do not match the one specified in command line parameter N
	if (numCount != n){
		// Output an error
		printf("Input value n does not match the number of elemts in the input file.\n");
		return 1;
	}

	// Get the final and temp arrays from shared memory
	final_arr = (int *) shmat(finalSId, NULL, 0);
	temp_arr = (int *) shmat(tempSId, NULL, 0);
	working = (int *) shmat(workingSId, NULL, 0);

	// Fill the temp array with the initial input numbers
	for(int i = 0; i < n; i++){
		temp_arr[i] = input_arr[i];
	}

	// Each process will have a personal id
	// The id will be used for the process to figure out which index it needs to compute

	// Create M processes
	if (m > 1){
		pid = fork(); // Create a child
		while(pid < 0){
			pid = fork();
		}
		for( int i=1; i< m-1; i++) { // Iterate m times
			if (pid == 0) { // For every child
				id = i; 		// Assign the index/id to the child
				pid = fork(); 	// Create a new child
				while(pid < 0){
					pid = fork();
				}
			}
		}
		if (pid == 0){
			id = m - 1; // For the first child, set index to 1
		}
	}

	// Iterate log(n, base2) times
	for (int iter=0; iter<numIter; iter++) {
		// Declare that the id (current child) is ready to work
		working[id] = 1;

		// Wait until each process is ready to start working
		do {
			// Get the updated/current version from the shared memory
			working = (int *) shmat(workingSId, NULL, 0);
			// Hey sexy
			// Steven Lo and Nikhil Patil wrote this genius program
		} while(sum(working, m) != m);

		//printf("Starting work for iteration (%d) and id :: %d\n", iter, id);

		// This print is SACRED. NO TOUCH. THIS IS LEGACY MODULE
		printf("Working[%d] :: %d\n", id, working[id]);
		// Honestly tho, wth. Why does this comment make/break the code
		// It was placed here for OPTIMAL debugging purposes

		// Calculate unique index values in final based on id
			// Ex: n = 10, m = 3
			// id=0 is responsible for index (0, 3, 6, 9)
			// id=1 is responsible for index (1, 4, 7, 10)
			// id=2 is responsible for index (2, 5, 8)
		for (int j = id; j < n; j += m){	// Calculate final[j], increment j by number of processes for the next index
			if (j - pow(2,iter) < 0){
				final_arr[j] = temp_arr[j];	// Directly copy the values if new values can't be computed from previous array
			}
			else{
				final_arr[j] = temp_arr[j] + temp_arr[j-(int)(pow(2,iter))]; // Compute values from previous array
			}
		}

		// Declare the work finished
		working[id] = 0;

		// Wait until all processes are finished
		do {
			// Get the updated/current version from the shared memory
			working = (int *) shmat(workingSId, NULL, 0);
			// Hey sexy
			// Steven Lo and Nikhil Patil wrote this genius program
		} while(sum(working, m) != 0); // Check if the sum of all elements in working array is equal to 0

		// Output the final array to the terminal
		// Apparently this is also part of LEGACY CODE
		for(int i = 0; i < n; i++){
			printf("%d ", final_arr[i]);
		}
		printf("\n");
		// DO NOT MODIFY/DELETE this loop either

		// Copy all values from final to temp
		for(int i = 0; i < n && iter != numIter-1; i++){
			temp_arr[i] = final_arr[i];
		}

		// Go to next iteration :D
	}

	// Kill all processes to prevent any zombies
	for(int i = 0; i < m; i++){
		wait(NULL);
	}

	// Create an output file stream
	FILE* outFile = fopen(output_file, "w");
	if (outFile != NULL){
		for(int i = 0; i < n; i++){
			fprintf(outFile, "%d ", final_arr[i]); // Print the final array to the file
		}
	}
	fprintf(outFile, "\n");	// Print an empty line at the end of the file
	fclose(outFile);		// Close the file stream
	printf("\n");			// Print an empty line on terminal

	// Break the link between local and shared memory
	shmdt(final_arr);
	shmdt(temp_arr);
	shmdt(working);

	// Remove shared memory segment
	shmctl(finalSId, IPC_RMID, NULL);
	shmctl(tempSId, IPC_RMID, NULL);
	shmctl(workingSId, IPC_RMID, NULL);

	return 0;
}