#include <stdio.h>	/* fopen(), fclose(), fprintf(), printf(), fscanf() */
#include <stdlib.h>	/* exit() */
#include <errno.h>	/* errno */
#include "error_msg.h"	/* error_message[] */

#define ARRAY_SIZE 1024


FILE	*in, *out;

/************************************************************************/
/* partition: rearanges subarray arr[left]..arr[right], returns index	*/
/* returns index i from <left,right>,                                   */
/*   s.t. for all j <= i: arr[j] <= arr[i],                             */
/*	  and for all j > i: arr[j] > arr[i]   (j is from <left,right>)	*/
/************************************************************************/

int
partition(arr, left, right)
	int arr[];
	int left, right;
{
	int pivot, temp;

	pivot = arr[(left+right)/2];
	left--;
	right++;
	while (1) {
		do right--; while (arr[right] > pivot);
		do left++; while (arr[left] < pivot);
		if (left < right) {
			temp = arr[left];
			arr[left] = arr[right];
			arr[right] = temp;
		} else
			return right;
	}
}

/****************************************************************/
/* quicksort: sorts a range of array using quicksort method 	*/
/* pre: i,j are valid indeces					*/
/* post: arr[i] <= arr[i+1] <= ... <= arr[j]			*/
/****************************************************************/

void
quicksort(arr, i, j)
	int arr[];
	int i, j;
{
	int k;

	if (i<j) {
		k = partition(arr, i, j);
		quicksort(arr, i, k);
		quicksort(arr, k+1, j);
	}
}

/**************************************************************************/
/* sortfile: reads 'in' file into an array and outputs sorted values into */
/*		'out' file						  */
/* pre: 'in' is a file of at most ARRAY_SIZE integers separated by comma  */
/* post: 'out' is a sorted file of integers separated by comma 		  */
/**************************************************************************/

void
sortfile()
{
	int arry[ARRAY_SIZE];
	int i, temp;

	i =0;
	while ((fscanf(in,"%d,", &temp)!= EOF) && (i<ARRAY_SIZE)){
		arry[i++] = temp;
	}
	quicksort(arry,0,i-1);
	if (i > 0)
		fprintf(out,"%d",arry[0]);
	for(temp=1; temp < i; temp++)
		fprintf(out,",%d",arry[temp]);
	fprintf(out,"\n");
}

/***************************************************************/
/* initialize: opens input and output files according to       */
/*   1st and 2nd arguments                                     */
/***************************************************************/

void initialize(argc, argv)
	int argc;
	char *argv[];
{
	if ((argc > 3) || (argc == 1)){
		printf("1 or 2 parameters expected:\n");
		printf("1st parameter : input file\n");
		printf("2nd parameter : output file\n");
		exit(1);
	}		
	if (argc > 1)
		if ((in = fopen(argv[1],"r")) == NULL) {
			fprintf(stderr, "%s: can't open %s\n", argv[0], argv[1]);
			fprintf(stderr, "\terror %d: %s\n", errno, error_message[errno]);
			exit(1);
		}
	out =  stdout;
	if (argc>2)
		if ((out = fopen(argv[2],"w")) == NULL) {
			fprintf(stderr, "%s: can't open %s\n", argv[0], argv[2]);
			fprintf(stderr, "\terror %d: %s\n", errno, error_message[errno]);
			exit(1);
		}
}


main(argc, argv) 
	int argc;
	char *argv[];
{
	initialize(argc, argv);
	sortfile();
	fclose(in);
	fclose(out);
	return 0;
}