/*
	HW 1 - Problem 7
	
	Merge Sorting(non-recursive)
	
	20027377 - Jungtaek Lim
 */
#include <stdio.h>
#include <stdlib.h>

#define INPUT_DATA_FILENAME	"input.txt"
#define MAX_DATA_COUNT		1000			// define for Max data count

typedef struct _STACK_NODE {
	int left;			// left position of range
	int right;			// right position of range
	int mid;			// middle position of range(use for merge turn)
	
	// if divide is true, it's divide turn
	// if not true, it's merge turn
	bool divide;
} STACK_NODE;

/*
	Stack class

	use for save/load operation(divide/merge) information
 */
class Stack {

public:
	Stack(int size);
	~Stack();

	void push(int left, int mid, int right, bool divide);
	STACK_NODE pop();
	bool isEmpty();
	bool isFull();

private:
	int top;
	int stack_size;

	STACK_NODE * m_stack; 
};

Stack::Stack(int size) {
	stack_size = size;
	m_stack = new STACK_NODE[stack_size];

	top = 0;
}

Stack::~Stack() {
	delete [] m_stack;
}

void Stack::push(int left, int mid, int right, bool divide) {
	STACK_NODE node;
	node.left = left;
	node.right = right;
	node.mid = mid;
	node.divide = divide;

	m_stack[top++] = node;
}

STACK_NODE Stack::pop() {
	top--;

	return m_stack[top];
}

bool Stack::isEmpty() {
	return (top <= 0);
}

bool Stack::isFull() {
	return (top >= stack_size);
}

// End of stack class

/*
	mergesort() callback function for comparing two elements
	
	if element1 > element2, return >0
	if element1 == element2, return 0
	if element1 < element2, return <0
	
	its return value is similar to strcmp()
 */
int intCompareFunc(const void * e1, const void * e2) {
	int e1Val = *((int *)e1);
	int e2Val = *((int *)e2);
	
	// return e1 - e2 since data type is integer
	return e1Val - e2Val;	
}

/*
	merge sort - non recursive
 */
void msort(void * base, size_t nel, size_t width, 
	int (*compar)(const void *, const void *)) {
	
	char * array = (char *)base;
	Stack stack(MAX_DATA_COUNT);
	
	// push to start divide
	stack.push(0, 0, nel - 1, true);
	
	while( !stack.isEmpty() ) {
		STACK_NODE node = stack.pop();

		// divide step
		if(node.divide) {
			/*
				recursive mergesort
				mergesort(left, mid)
				mergesort(mid+1, right)
				merge(left, mid, right)
			
				we need to push reverse sequence
			 */
			int mid = (node.left + node.right) / 2;
			
			// push merge step
			stack.push(node.left, mid, node.right, false);
			
			// push right side divide
			if(mid + 1 < node.right)
				stack.push(mid + 1, 0, node.right, true);
			
			// push left side divide
			if(node.left < mid)
				stack.push(node.left, 0, mid, true);
		}
		// merge step
		else {
			char * tempArray = new char[(node.right - node.left + 1) * width];
			
			int leftArrIdx = node.left;
			int rightArrIdx = node.mid + 1;
			int currIdx = 0;
			
			// loop while one of two partitions has no more element
			while(leftArrIdx <= node.mid && rightArrIdx <= node.right) {
				// left > right
				if( compar(array + (leftArrIdx * width) ,
						array + (rightArrIdx * width) ) > 0 ) {
					// copy right partition's element to temporary array
					memcpy(tempArray + (currIdx * width), array + (rightArrIdx * width), width);
					
					// increase indexes
					currIdx++; rightArrIdx++;
				}
				// left <= right
				else {
					// copy left partition's element to temporary array
					memcpy(tempArray + (currIdx * width), array + (leftArrIdx * width), width);
					
					// increase indexes
					currIdx++; leftArrIdx++;
				}
			}
			
			// copy remaining left partition to temporary array
			while(leftArrIdx <= node.mid) {
				memcpy(tempArray + (currIdx * width), array + (leftArrIdx * width), width);
				currIdx++; leftArrIdx++;
			}

			// copy remaining right partition to temporary array
			while(rightArrIdx <= node.right) {
				memcpy(tempArray + (currIdx * width), array + (rightArrIdx * width), width);
				currIdx++; rightArrIdx++;
			}
			
			// copy temporary array's whole elements to base's left position
			memcpy( ((char *)base) + (node.left * width), tempArray, currIdx * width);
						
			delete [] tempArray;
		}
	}
}

int main(int argc, char * argv[]) {
	int array[MAX_DATA_COUNT];
	int testCaseCount = 0;
	FILE * fpInput = NULL;
	
	fpInput = fopen(INPUT_DATA_FILENAME, "r");
	
	// exit program if input file is not accesible
	if( !fpInput )
		exit(-1);
	
	// load testcase count
	fscanf(fpInput, "%d", &testCaseCount);
	
	// loop for testcase's count
	for(int i = 0 ; i < testCaseCount ; i++) {
		int dataCount = 0;
		
		fscanf(fpInput, "%d", &dataCount);
		
		// load input values
		for(int j = 0 ; j < dataCount ; j++)
			fscanf(fpInput, "%d", &array[j]);
		
		/* 
			void msort(void *base, size_t nel, size_t width,
         		int (*compar)(const void *, const void *));

			nel is count of elements and width is size of data type
			we must implement compar function because msort() doesn't know how to compare
		*/
		msort(array, dataCount, sizeof(int), intCompareFunc);

		// print sort result
		for(int k = 0 ; k < dataCount ; k++)
			printf("%d ", array[k]);
		
		printf("\n");
	}

	// exit program normally
	return 0;
}

Exited: ExitFailure 255