authParallelAndDistributedSystemsCourseExercise2/dev/knnSerial (copy).c

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

#define DEBUG	0

typedef struct neighbor{
	double distance;
	int neighborId;
} neighbor;

void getArgs(int argc, char** argv);
void init(double ***pointsArray, neighbor ***sortedNeighborsArray);
int readPointsArrayFromFile(double ***array);
void printArray(int rows, int columns, double ***array);
void addDistanceAndShift(neighbor ***sortedNeighborsArray, int firstPointId, int secondPointId, double pointsDistance);
void cleanUp(double ***pointsArray, neighbor ***sortedNeighborsArray);

int numberOfPoints, numberOfDimensions, numberOfNeighbors;

int main(int argc, char **argv){
	double **pointsArray;
	neighbor **sortedNeighborsArray;
	
	getArgs(argc, argv);
	init(&pointsArray, &sortedNeighborsArray);
	//printArray(numberOfPoints, numberOfDimensions, &pointsArray);
	//printf("HERE\n");
	for (int firstPoint=0; firstPoint<numberOfPoints; ++firstPoint){
		for (int secondPoint=0; secondPoint<numberOfPoints; ++secondPoint){
			if (firstPoint == secondPoint){
				continue;
			}
			double distance = 0;
			for (int dimensionIndex=0; dimensionIndex<numberOfDimensions; ++dimensionIndex){
				double diff = pointsArray[firstPoint][dimensionIndex] - pointsArray[secondPoint][dimensionIndex];
				distance += pow(diff ,2);
			}
			addDistanceAndShift(&sortedNeighborsArray, firstPoint, secondPoint, distance);
		}
	}
	printf("HERE\n");
	
	for (int x=0; x<numberOfPoints; ++x){
		for (int y=0; y<numberOfNeighbors; ++y){
			printf("%d to %d = %f\n", x, sortedNeighborsArray[x][y].neighborId, sortedNeighborsArray[x][y].distance);
		}
		printf("\n");
	}
	
	cleanUp(&pointsArray, &sortedNeighborsArray);
	printf("Done! Press any key to exit.\n");
	getchar();
}

void getArgs(int argc, char** argv){
	/*if (argc != 4) {
		printf("Usage: %s p d k\nwhere:\n\tp is the the number of points\n\td is the number of dimensions of each point\n", 
			argv[0]);
		printf("\tk is the number of neighbors to search for\n");
		exit(1);
	}*/
	/*numberOfPoints = atoi(argv[1]);
	numberOfDimensions = atoi(argv[2]);
	numberOfNeighbors = atoi(argv[3]);
	if (numberOfNeighbors >= numberOfPoints)	{
		numberOfNeighbors = numberOfPoints - 1;
	}*/
	numberOfPoints = 10;
	numberOfDimensions = 10;
	numberOfNeighbors = 5;
}

void init(double ***pointsArray, neighbor ***sortedNeighborsArray){
	//Allocates memory for points array
	if ((*pointsArray = malloc((sizeof(double *)) * numberOfPoints)) != NULL){
		for (int row = 0; row < numberOfPoints; ++row){
			if (((*pointsArray)[row] = malloc((sizeof(double)) * numberOfDimensions)) == NULL){
				if (DEBUG){
					printf("Error allocating memory\n");
				}
				exit(1);
			}
		}
	} else {
		if (DEBUG){
			printf("Error allocating memory\n");
		}
		exit(1);
	}

	//Allocates memory for neighbors array
	if ((*sortedNeighborsArray = malloc((sizeof(neighbor *)) * numberOfPoints)) != NULL){
		for (int row = 0; row < numberOfPoints; ++row){
			if (((*sortedNeighborsArray)[row] = malloc((sizeof(neighbor)) * numberOfNeighbors)) == NULL){
				if (DEBUG){
					printf("Error allocating memory\n");
				}
				exit(1);
			}
		}
	} else {
		if (DEBUG){
			printf("Error allocating memory\n");
		}
		exit(1);
	}

	//Reads coordinates for the file
	if (readPointsArrayFromFile(pointsArray)){
		if (DEBUG){
			printf("Press any key to exit.\n");
			getchar();
		}
		exit(1);
	}

	//Initializes neighbors array distances to -1
	for (int row=0; row<numberOfPoints; ++row){
		for(int column=0; column<numberOfNeighbors; ++column){
			(*sortedNeighborsArray)[row][column].distance = -1;
		}
	}
}

int readPointsArrayFromFile(double ***array){
	FILE *pointsBinaryFile;
	pointsBinaryFile = fopen("data.bin","rb");

	for (int point=0; point<numberOfPoints; ++point){
		if (fread((*array)[point], sizeof(double), numberOfDimensions, pointsBinaryFile) != numberOfDimensions) {
			if(feof(pointsBinaryFile)){
				printf("There were info after the end of file.\n");
			} else{
				printf("Error reading points file.");
			}
			return 1;
		}
	}
	fclose(pointsBinaryFile);
	
	return 0;
}

void printArray(int rows, int columns, double ***array){
	for (int row=0; row<rows; ++row){
		for (int column=0; column<columns; ++column){
			printf("[%d][%d] = %f\n", row, column, (*array)[row][column]);
		}
		printf("\n");
	}
}


void addDistanceAndShift(neighbor ***sortedNeighborsArray, int firstPointId, int secondPointId, double pointsDistance){
	if (DEBUG){
		printf("Got %d and %d = %f\n", firstPointId, secondPointId, pointsDistance);
	}

	for (int arrayIndex=0; arrayIndex<numberOfNeighbors; ++arrayIndex){
		//Gets distance stored in the array for this index
		double thisNeighborDistance = (*sortedNeighborsArray)[firstPointId][arrayIndex].distance;

		if (thisNeighborDistance == -1){ //Loop reached the end of the array
			(*sortedNeighborsArray)[firstPointId][arrayIndex].distance = pointsDistance;
			(*sortedNeighborsArray)[firstPointId][arrayIndex].neighborId = secondPointId;
			break;
		} else if (thisNeighborDistance > pointsDistance){ //Distance at the this index is greater than the distance being inserted
			//Shifts right all non empty columns holding distances lower than pointsDistance
			for (int moveColumn=numberOfNeighbors-2; moveColumn>=arrayIndex; --moveColumn){
				double tempDistance = (*sortedNeighborsArray)[firstPointId][moveColumn].distance;
				if (tempDistance == -1){ //Skips empty columns
					continue;
				}
				(*sortedNeighborsArray)[firstPointId][moveColumn+1].distance = tempDistance;
				(*sortedNeighborsArray)[firstPointId][moveColumn+1].neighborId = (*sortedNeighborsArray)[firstPointId][moveColumn].neighborId;
			}
			//Inserts pointsDistance in the space created after shifting
			(*sortedNeighborsArray)[firstPointId][arrayIndex].distance = pointsDistance;
			(*sortedNeighborsArray)[firstPointId][arrayIndex].neighborId = secondPointId;
			break;
		}
	}
}

void cleanUp(double ***pointsArray, neighbor ***sortedNeighborsArray){
	for (int row=0; row<numberOfPoints; ++row){
		free((*pointsArray)[row]);
	}
	free(*pointsArray);

	//Crashes for some reason...
	/*for (int row=0; row<numberOfNeighbors; ++row){
		printf("%f\n", (*sortedNeighborsArray)[row][0]);
		free((*sortedNeighborsArray)[row]);
	}*/
	//free(*sortedNeighborsArray);
}