/* Time Check Program of B Tree Operation.

*/
/////////////////////////////////////////////////////////////////////////////////////////
/************************************* pRoGrAm sTaRt ***********************************/
/////////////////////////////////////////////////////////////////////////////////////////

/*=====================================================================================*/
/************************************* PREPROCESSOR ************************************/
/*=====================================================================================*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
#include <windows.h>

#define TRUE		1
#define FALSE		0
#define	STR_MAX		30

/*=====================================================================================*/
/*************************** TYPE DEFINITION (STRUCTURE & ENUM) ************************/
/*=====================================================================================*/
typedef struct tree *tree_ptr; // structure pointer definition of trees
typedef struct tree{ // structure definition of trees
	tree_ptr left, middle, right; // link member
	int key1, key2; // key member
}tree;

typedef struct stack *stk_ptr; // structure pointer definition of stack
typedef struct stack{ // structure definition of stack
	tree_ptr ads; // address member(address of visited node)
	stk_ptr link; // link member
}stack;

typedef struct queue *que_ptr; // structure pointer definition of queue
typedef struct queue{ // structure definition of queue
	tree_ptr ads; // address member(address of node)
	que_ptr link; // link member
}queue;

/*=====================================================================================*/
/****************************** GLOVAL VARIABLE DECLARATION ****************************/
/*=====================================================================================*/
tree_ptr root; // root node of B+ tree(auto initial : NULL)
stk_ptr stk_top; // head node of stack(auto initial : NULL)
LARGE_INTEGER Frequency; // variable for time check
LARGE_INTEGER BeginTime; // variable for time check
LARGE_INTEGER Endtime; // variable for time check

/*=====================================================================================*/
/********************************* PROTOTYPE OF FUNCTION *******************************/
/*=====================================================================================*/
void initial_creator(char name[]);
void insertion(int in_key);
void deletion(int out_key);
void selection(int key);
void update(int key1, int key2);
void data_view();
void stack_push(tree_ptr ads);
tree_ptr stack_pop();
void queue_insert(que_ptr *front, que_ptr *rear, tree_ptr ads);
tree_ptr queue_delete(que_ptr *front);
void delay(clock_t sleep);

/*=====================================================================================*/
/************************************ main() FUNCTION **********************************/
/*=====================================================================================*/
/*>>> FUNCTION >>> 프로그램의 전반적인 흐름제어와 필요한 서브함수를 호출하여 작업을
                   수행하는 함수 */
/*>>> CALL FUNCTION >>> insertion(), deletion(), selection(), update(), data_view() */
void main(void){
	/* local variable declaration */
	__int64 elapsed; // variable for time check
	double duringtime; // variable for time check
	char buf[STR_MAX], op[10];
	int key1, key2;

	QueryPerformanceFrequency(&Frequency);
	printf("==========================================\n"); // main title
	printf("| TIME CHECK PROGRAM OF B TREE OPERATION |\n");
	printf("==========================================\n");
	
	printf(">> INPUT FILE NAME FOR INITIAL CREATION : ");
	gets(buf);
	initial_creator(buf); // initial creation

	do{
		printf("\n>>> INPUT COMMAND(insert/delete/update/select/show/exit) <<<\n");
		printf("COMMAND>> ");
		gets(buf);
		sscanf(buf, "%s", op);

		QueryPerformanceCounter(&BeginTime); // start time check
		
		//================================================================
		if(!strcmp(op, "insert")){ // insertion operation
			sscanf(buf, "%s%d", op, &key1);
			insertion(key1);
		}
		else if(!strcmp(op, "delete")){ // deletion operation
			sscanf(buf, "%s%d", op, &key1);
			deletion(key1);
		}
		else if(!strcmp(op, "select")){ // selection operation
			sscanf(buf, "%s%d", op, &key1);
			selection(key1);
		}
		else if(!strcmp(op, "update")){ // update operation
			sscanf(buf, "%s%d%d", op, &key1, &key2);
			update(key1, key2);
		}
		else if(!strcmp(op, "show")) data_view(); // show operation
		else if(!strcmp(op, "exit")){ // program exit
			printf("\nPrOgRaM EnD...ByE...\n\n");
			exit(1);
		}
		else printf("\n<WARNNING> UNCORRECT COMMAND!!!\n\a");
		//=================================================================

		QueryPerformanceCounter(&Endtime); // end time check
		elapsed = Endtime.QuadPart - BeginTime.QuadPart; 
		duringtime = (double)elapsed / (double)Frequency.QuadPart;
		printf("\nEXHAUSTED TIME : %f SEC\n", duringtime); // exhausted time print
	}while(1);

}

/*=====================================================================================*/
/******************************* initial_creator() FUNCTION ****************************/
/*=====================================================================================*/
/*>>> FUNCTION >>> 초기 데이터의 생성 작업을 수행하는 함수 */
/*>>> CALL FUNCTION >>> insertion() */
void initial_creator(char name[]){
	__int64 elapsed; // variable for time check
	double duringtime; // variable for time check
	char buf[STR_MAX];
	FILE *in_fp;
	int key;

	if((in_fp = fopen(name, "r")) == NULL){
		printf("\n<WARNNING> FILE OPEN ERROR!!!\n\a");
		exit(1);
	}

	while(fgets(buf, STR_MAX, in_fp) != NULL){ // 줄 단위로 저장함
		sscanf(buf, "%d", &key); // 숫자로 저장시킴

		QueryPerformanceCounter(&BeginTime); // start time check

		insertion(key); // insertion() function call

		QueryPerformanceCounter(&Endtime); // end time check
		elapsed = Endtime.QuadPart - BeginTime.QuadPart; 
		duringtime = (double)elapsed / (double)Frequency.QuadPart;
		printf("\nEXHAUSTED TIME : %f SEC\n", duringtime); // exhausted time print
	}
}

/*=====================================================================================*/
/********************************** insertion() FUNCTION *******************************/
/*=====================================================================================*/
/*>>> FUNCTION >>> B Tree의 삽입 작업을 수행하는 함수 */
/*>>> CALL FUNCTION >>> NONE */
void insertion(int key){
	/* local variable declaration */
	tree_ptr temp, tmp1, tmp2, new_node; // temporary space
	int Found=FALSE, Finished; // falg variable
	int k[3]; // temporary space

	//============================================================== work start
	if(!root){ // 처음 삽입일 경우
		temp=(tree_ptr)malloc(sizeof(tree)); // dynamic allocation
		temp->key1=key;
		temp->key2=INT_MAX;
		temp->left=temp->middle=temp->right=NULL; // 링크값의 초기화
		root=temp;
		return;
	}

	temp=root; // address assignment
	delay(1); // program delay

	do{
		stack_push(temp); // stack push
		if((key==temp->key1) || (key==temp->key2)){ // 같은 키 값을 발견했을 때
			Found=TRUE;
			break;
		}

		if(!temp->left){ // leaf노드일 경우
			stack_pop(); // stack pop
			break;
		}
		else{ // leaf노드가 아닐 경우 경로를 따라감
			if(key < temp->key1) temp=temp->left; // move to left
			else if(key > temp->key1 && key < temp->key2) temp=temp->middle; // move to middle
			else temp=temp->right; // move to right
		}
	}while(!Found);

	if(Found){ // 같은 키 값이 이미 트리에 존재할 경우
		printf("\n<WARNNING> ALREADY EXIST SAME KEY!!!\n\a");
		return;
	}
	else{ // 같은 키 값이 트리에 없을 경우 --> 삽입 시작
		Finished=FALSE; // Finished변수의 초기화
		do{
			if(temp->key2==INT_MAX){ // 현재 노드에 빈공간이 있을 경우

				if(key > temp->key1){
					if(temp->left) temp->right=tmp2;
					temp->key2=key; // 키 값의 순서를 유지하면서 적절히~~~ 삽입
				}
				else{
					temp->key2=temp->key1;
					temp->key1=key;
					if(temp->left){
						temp->right=temp->middle;
						temp->middle=new_node;
					}
				}
				Finished=TRUE; // Finished변수를 TRUE로 만들어 루프를 빠져나온다.
			}
			else{ // 현재 노드에 빈공간이 없을 경우
				if(key < temp->key1){
					k[0]=key; k[1]=temp->key1; k[2]=temp->key2;
				}
				else if(key > temp->key1 && key < temp->key2){
					k[0]=temp->key1; k[1]=key; k[2]=temp->key2;
				}
				else{
					k[0]=temp->key1; k[1]=temp->key2; k[2]=key;
				}
				temp->key1=k[0]; temp->key2=INT_MAX; // value save
				
				new_node=(tree_ptr)malloc(sizeof(tree)); // dynamic allocation
				new_node->key1=k[2]; new_node->key2=INT_MAX; // value save

				if(temp->left){ // leaf가 아닐 경우
					if(temp->middle->key1 > tmp2->key1){
						new_node->left=temp->middle; new_node->middle=temp->right; new_node->right=NULL; // link save
						temp->right=NULL; temp->middle=tmp2;						
					}
					else if(temp->right->key1 < new_node->key1){
						new_node->left=temp->right; new_node->middle=tmp2; new_node->right=NULL; // link save
						temp->right=NULL;
					}
					else{
						new_node->left=tmp2; new_node->middle=temp->right; new_node->right=NULL; // link save
						temp->right=NULL;
					}
				}
				else new_node->left=new_node->middle=new_node->right=NULL; // link save

				tmp2=new_node; // address assignment
				
				if(stk_top){ // STACK의 TOP이 NULL이 아닐 경우
					temp=stack_pop();
					key=k[1];
				}
				else{ // STACK의 TOP이 NULL일 경우 --> 트리의 레벨이 1증가
					tmp1=(tree_ptr)malloc(sizeof(tree)); // dynamic allocation
					tmp1->key1=k[1]; tmp1->key2=INT_MAX; // value save
					tmp1->left=temp; tmp1->middle=new_node; tmp1->right=NULL; // link save
					root=tmp1; // address assignment
					Finished = TRUE;
				}
			}
		}while(!Finished);
	}

	while(stk_top) temp=stack_pop(); // STACK공간을 RELEASE하고 TOP을 초기화
	stk_top = NULL; // 스택의 재 초기화
}

/*=====================================================================================*/
/********************************** deletion() FUNCTION ********************************/
/*=====================================================================================*/
/*>>> FUNCTION >>> B Tree의 삭제 작업을 수행하는 함수 */
/*>>> CALL FUNCTION >>> NONE */
void deletion(int key){
	/* local variable declaration */
	int Found=FALSE, Finished; // falg variable
	tree_ptr temp, tmp1, tmp2, tmp3; // temporary space
	int num_t;

	//============================================================== work start
	if(!root){ // 공 트리일 경우
		printf("\n<WARNNING> TREE IS EMPTY!!!\n\a");
		return;
	}

	temp=root; // address assignment
	delay(1); // program delay

	do{
		stack_push(temp); // stack push
		if((key==temp->key1) || (key==temp->key2)){ // 같은 키 값을 발견했을 때
			if(!temp->left) stack_pop();
			Found=TRUE;
			break;
		}
		else{ // 현재 노드에 삭제키 값과 같은 키값이 없을 경우 경로를 따라감.
			if(key < temp->key1) temp=temp->left; // move to left
			else if(key > temp->key1 && key < temp->key2) temp=temp->middle; // move to middle
			else temp=temp->right; // move to right
		}
		if(!temp) break; // 같은 키 값을 발견하지 못했을 경우 루프를 빠져나감
	}while(!Found);

	if(!temp && !Found){ // 삭제할 키 값과 같은 키 값이 없을 경우
		printf("\n<WARNNING> OUT_KEY IS NOT EXIST IN TREE\n\a");
		return;
	}

	Finished=FALSE; // Finished변수의 초기화
	do{
		if(!temp->left){ // 삭제키가 leaf에 있을 경우
			if(temp->key2!=INT_MAX){ // 삭제키를 가진 노드가 두 개의 키를 가질 경우
				if(key==temp->key1)	temp->key1=temp->key2;
				temp->key2=INT_MAX;
				Finished=TRUE;
			}
			else{ // 삭제키를 가진 노드가 한 개의 키를 가질 경우(언더플로우 발생)========================
				if(stk_top){ // STACK의 TOP이 NULL이 아닐 경우
					tmp1=stack_pop(); // stack pop
						if(tmp1->middle->key1==temp->key1){ // 삭제키 값이 중간 자식일 경우
						tmp2=tmp1->left; tmp3=tmp1->right; // address assignment
							if(tmp2->key2!=INT_MAX){ // 왼쪽 인접형제노드가 두 개의 키 값을 가질 경우(재분배)
							temp->key1=tmp1->key1; tmp1->key1=tmp2->key2;
							tmp2->key2=INT_MAX;
						}
						else{ // 왼쪽 인접형제노드가 한 개의 키 값을 가질 경우
							if(tmp1->key2!=INT_MAX){ // 부모노드가 두 개의 키 값을 가질 경우(합병)
								tmp2->key2=tmp1->key1; tmp1->key1=tmp1->key2;
								tmp1->key2=INT_MAX; tmp1->middle=tmp3; tmp1->right=NULL;
								free(temp);
							}
							else{ // 부모노드가 한 개의 키 값을 가질 경우(합병)
								tmp1->key2=tmp1->key1; tmp1->key1=tmp2->key1;
								tmp1->left=tmp1->middle=tmp1->right=NULL;
								free(temp); free(tmp2);
							}
						}					
					}
					else if(tmp1->left->key1==temp->key1){ // 삭제키 값이 왼쪽 자식일 경우
						tmp2=tmp1->middle; tmp3=tmp1->right; // address assignment
						if(tmp2->key2!=INT_MAX){ // 인접형제노드가 두 개의 키 값을 가질 경우(재분배)
							temp->key1=tmp1->key1; tmp1->key1=tmp2->key1;
							tmp2->key1=tmp2->key2; tmp2->key2=INT_MAX;
						}
						else{ // 인접형제노드가 한 개의 키 값을 가질 경우
							if(tmp1->key2!=INT_MAX){ // 부모노드가 두 개의 키 값을 가질 경우(합병)
								tmp2->key2=tmp2->key1; tmp2->key1=tmp1->key1;
								tmp1->key1=tmp1->key2; tmp1->key2=INT_MAX;
								tmp1->left=tmp2; tmp1->middle=tmp3; tmp1->right=NULL;
								free(temp);
							}
							else{ // 부모노드가 한 개의 키 값을 가질 경우(합병)
								tmp1->key2=tmp2->key1;
								tmp1->left=tmp1->middle=tmp1->right=NULL;
								free(temp); free(tmp2);
							}
						}
					}
						else if(tmp1->right->key1==temp->key1){ // 삭제키 값이 오른쪽 자식일 경우
						tmp2=tmp1->middle; tmp3=tmp1->left; // address assignment
						if(tmp2->key2!=INT_MAX){ // 인접형제노드가 두 개의 키 값을 가질 경우(재분배)
							temp->key1=tmp1->key2; tmp1->key2=tmp2->key2; tmp2->key2=INT_MAX;
						}
						else{ // 인접형제노드가 한 개의 키 값을 가질 경우(합병)
							tmp2->key2=tmp1->key2; tmp1->key2=INT_MAX; tmp1->right=NULL;
							free(temp);
						}
					}
					else{ // 아무것도 아닐경우 ---치명적 오류
						printf("\n<WARNNING> !!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n\a");
						exit(1);
					}
					Finished=TRUE;
				}
				else{ // STACK의 TOP이 NULL일 경우
					free(temp);
					root=NULL;
					Finished=TRUE;
				}
			}
		}
		else{ // 삭제키가 일반노드에 있을 경우
			if(temp->key2!=INT_MAX){ // 삭제키를 가진 노드가 두 개의 키를 가질 경우
				



			}
			else{ // 삭제키를 가진 노드가 한 개의 키를 가질 경우(언더플로우 발생)
				tmp1=temp->left;
				while(temp->left){ // leaf노드가 아닐 동안 루프를 반복한다.
					if(tmp1->key2!=INT_MAX){ // 좌측 노드가 가진 키의 개수가 두 개일 경우
						num_t=temp->key1;
						temp->key1=tmp1->key2;
						tmp1->key2=num_t;
					}
					else{ // 좌측 노드가 가진 키의 개수가 한 개일 경우
						num_t=temp->key1;
						temp->key1=tmp1->key1;
						tmp1->key1=num_t;
					}
					temp=tmp1;
					tmp1=temp->left;
				}
			}
		}
	}while(!Finished);

	while(stk_top) temp=stack_pop(); // STACK공간을 RELEASE하고 TOP을 초기화
	stk_top = NULL; // 스택의 재 초기화
}

/*=====================================================================================*/
/********************************** selection() FUNCTION *******************************/
/*=====================================================================================*/
/*>>> FUNCTION >>> B Tree의 선택 작업을 수행하는 함수 */
/*>>> CALL FUNCTION >>> NONE */
void selection(int key){
	/* local variable declaration */
	tree_ptr temp;
	int Found=FALSE;

	//============================================================== work start
	if(!root){ // 공 트리일 경우
		printf("\n<WARNNING> TREE IS EMPTY!!!\n\a");
		return;
	}

	temp=root; // address assignment
	delay(1); // program delay

	do{
		if((key==temp->key1) || (key==temp->key2)){ // 같은 키 값을 발견했을 때
			Found=TRUE;
			break;
		}
		else{ // 현재 노드에 삭제키 값과 같은 키값이 없을 경우 경로를 따라감.
			if(key < temp->key1) temp=temp->left; // move to left
			else if(key > temp->key1 && key < temp->key2) temp=temp->middle; // move to middle
			else temp=temp->right; // move to right
		}
		if(!temp) break; // 같은 키 값을 발견하지 못했을 경우 루프를 빠져나감
	}while(!Found);

	if(!temp && !Found){ // 삭제할 키 값과 같은 키 값이 없을 경우
		printf("\n>> (KEY VALUE : %d) IS  NOT EXIST IN TREE\n\a", key);
		return;
	}
	else printf("\n>> (KEY VALUE : %d) IS EXIST IN TREE\n", key);
	//============================================================== work end
}

/*=====================================================================================*/
/*********************************** update() FUNCTION *********************************/
/*=====================================================================================*/
/*>>> FUNCTION >>> B Tree의 수정 작업을 수행하는 함수 */
/*>>> CALL FUNCTION >>> insertion(), deletion() */
void update(int key1, int key2){
	
	//============================================================== work start
	deletion(key1); // 수정할 키 값 삭제
	insertion(key2); // 새로운 키 값 삽입
	//============================================================== work end
}

/*=====================================================================================*/
/********************************* data_view() FUNCTION ********************************/
/*=====================================================================================*/
/*>>> FUNCTION >>> B Tree의 현재 내용을 출력하는 함수(LEVEL ORDER TRAVERSAL) */
/*>>> CALL FUNCTION >>> NONE */
void data_view(){
	/* local variable declaration */
	que_ptr front=NULL, rear=NULL; // index variable declaration of queue & initial
	tree_ptr temp = root; // address assignment

	if(!temp){ // case : empty tree (error message print & return)
		printf("\n<WARNNING> NONE DATA IN TREE\n\a");
		return;
	}
	queue_insert(&front, &rear, temp); // queue insertion

	while(1){
		temp = queue_delete(&front); // queue deletion
		printf("\n");
		if(temp){ // case : temp != NULL
			if(temp->key1!=INT_MAX) printf("%d  ", temp->key1);
			if(temp->key2!=INT_MAX) printf("%d  ", temp->key2);
			if(temp->left) queue_insert(&front, &rear, temp->left);
			if(temp->middle) queue_insert(&front, &rear, temp->middle);
			if(temp->right) queue_insert(&front, &rear, temp->right);
		}
		else break; // case : temp == NULL
	}
	printf("\n");
}

/*=====================================================================================*/
/********************************* stack_push() FUNCTION *******************************/
/*=====================================================================================*/
/*>>> FUNCTION >>> STACK의 PUSH 연산을 수행하는 함수(방문한 노드의 주소 저장) */
/*>>> CALL FUNCTION >>> NONE */
void stack_push(tree_ptr ads){
	/* local variable declaration */
	stk_ptr temp=(stk_ptr)malloc(sizeof(stack)); // dynamic allocation

	if(!temp){ // case : failed allocation (error message print & exit)
		printf("\n<WARNNING> MEMORY IS FULL!!!\n");
		exit(1);
	}
	temp->ads = ads; // address : save
	temp->link = stk_top; // link : save
	stk_top = temp; // top : re-adjustment
}

/*=====================================================================================*/
/********************************** stack_pop() FUNCTION *******************************/
/*=====================================================================================*/
/*>>> FUNCTION >>> STACK의 POP 연산을 수행하는 함수(노드의 주소 리턴) */
/*>>> CALL FUNCTION >>> NONE */
tree_ptr stack_pop(){
	/* local variable declaration */
	stk_ptr temp = stk_top; // address assignment
	tree_ptr item;

	if(!temp){ // case : stack is empty (error message print & exit)
		printf("\n<WARNNING> THE STACK IS EMPTY\n\a");
		exit(1);
	}
	item = temp->ads; // address : save
	stk_top = temp->link; // link : save
	free(temp);
	return item;
}

/*=====================================================================================*/
/******************************** queue_insert() FUNCTION ******************************/
/*=====================================================================================*/
/*>>> FUNCTION >>> QUEUE의 INSERTION 연산을 수행하는 함수(노드의 주소 저장) */
/*>>> CALL FUNCTION >>> NONE */
void queue_insert(que_ptr *front, que_ptr *rear, tree_ptr ads){
	/* local variable declaration */
	que_ptr temp = (que_ptr)malloc(sizeof(queue)); // dynamic allocation

	if(!temp){ // case : failed allocation (error message print & exit)
		printf("\n<WARNNING> MEMORY IS FULL!!!\n");
		exit(1);
	}
	temp->ads = ads; // address : save
	temp->link = NULL; // link : save
	if(*front) (*rear)->link = temp;
	else (*front) = temp;
	(*rear) = temp;
}

/*=====================================================================================*/
/******************************** queue_delete() FUNCTION ******************************/
/*=====================================================================================*/
/*>>> FUNCTION >>> QUEUE의 DELETION 연산을 수행하는 함수(노드의 주소 리턴) */
/*>>> CALL FUNCTION >>> NONE */
tree_ptr queue_delete(que_ptr *front){
	/* local variable declaration */
	que_ptr temp = (*front); // address assignment
	tree_ptr item;
	
	if(!temp) return 0;
	
	item = temp->ads; // address : save
	(*front) = temp->link; // link : save
	free(temp);
	return item;
}

/*=====================================================================================*/
/*********************************** delay() FUNCTION **********************************/
/*=====================================================================================*/
/*>>> FUNCTION >>> 지연시간을 주는 함수 */
/*>>> CALL FUNCTION >>> NONE */
void delay(clock_t sleep){
	clock_t cur = clock(), el;
	for(;;){              /* 무한루프를 돌린다. */ 
		el = clock();  /* 현재까지 프로그램이 실행된 TICK */
		if((el - cur) > sleep) break ;
	}
}

/////////////////////////////////////////////////////////////////////////////////////////
/************************************** pRoGrAm eNd ************************************/
/////////////////////////////////////////////////////////////////////////////////////////