

/*
	구간히프 - 최대히프
	지열별 히프- 최대히프

*/



#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 1000
#define TRUE 1
#define FALSE 0
#define MALLOC(p, s) if (!((p) = malloc(s))) { printf("Insufficient memory!\n"); exit(1); }
////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////// AVL TREE 자료구조 정의 /////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
typedef struct {
	int key;
} element;
typedef struct treeNode *treePointer;
struct treeNode {
	treePointer leftChild;
	element data;
	short int bf;
	treePointer rightChild;
};
int unbalanced = FALSE;
////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////// 데이터파일 자료구조 정의 ///////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
typedef struct {
	int group;	// 모집그룹 (1.가/2.나/3.다 군)
	char name[30];	// 대학명
	char major[30];	// 학과
	int score;	// 점수 (표점)
	int number;	// 반영 영역 개수 ex) 언수외탐->4개 ; 4           수외탐->3개 ; 3
} DATA_1;	// 대학정보 데이터

typedef struct {
	int group;	// 모집그룹 (1.가/2.나/3.다 군)
	char name[30];	// 대학
	int kor, mat, eng, sub;	// 반영 비율 : 국.수.영.탐
	int indicator;	// 반영지표 : 표준점수(1) or 백분위(2)
	int score;	// 계산된 점수
	// char region[10];	// 지역    ex) 충북, 강원, 서울
	treePointer AVL_root;	// 각 대학교별 학과를 AVL로 구성
} DATA_2;	// 모집요강 데이터

typedef struct {
	int course;	// 인문계(1) / 자연계(2)
	int kor, mat, eng, sub1, sub2;	// 점수 : 국.수.영.탐1.탐2
	char region[10];	// 지역    ex) 충북, 강원, 서울
	// data...
} DATA_3;	// 학생데이터

////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////// MAX Heap 자료구조 정의 /////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
#define HEAP_FULL(n) (n == MAX_ELEMENTS-1)
#define HEAP_EMPTY(n) (!n)
element heap[MAX];
int n = 0;

typedef struct {
	element* link[16];	// 우리나라 지역
	/*
		0 : 서울
		1 : 인천
		2 : 경기
		3 : 강원
		4 : 충남
		5 : 충북
		6 : 대전
		7 : 경북
		8 : 대구
		9 : 울산
		10 : 부산
		11 : 경남
		12 : 전북
		13 : 전남
		14 : 광주
		15 : 제주
	*/
} ROOT;

ROOT root;	// 루트

////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////// 전역변수 선언 //////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
DATA_1 university[MAX];	// 대학 데이터
DATA_2 guidelines[MAX];	// 모집요강 데이터
DATA_3 profile;	// 학생정보 데이터
int n_of_univ = 0;	// 대학교 개수
int total_number;	// 입력된 전체 대학수

////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////// 함수 선언 //////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
void input_student_data();	// 학생정보 입력
void load_data();	// 데이터 불러오기
void save_data();	// 데이터 저장하기 (지원가능 대학교 text에 저장)
void calculate_score();	// 점수 계산
void avlInsert(treePointer *parent, element x, int *unbalanced);	// AVL 트리에서의 삽입
void leftRotation(treePointer *parent, int *unbalanced);	// leftRotation 함수
void rightRotation(treePointer *parent, int *unbalanced);	// rightRotation 함수
void push(element item, int *n);	// 최대히프 삽입
void classify();	// 대학별로 분류
element pop(int *n);	// 최대히프 삭제

////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////// 메인 함수 //////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
int main(void)
{
	int menu;	// 메뉴선택 번호

	while (1) {	// 메인 메뉴
		printf("\n\n");
		printf("1. 성적입력\n");
		printf("2. 지원가능대학조회\n");
		printf("3. 데이터저장\n");
		printf("4. 종료\n");
		printf("No.   ");
		scanf("%d", &menu);
		

		switch (menu) {
		case 1:	// 1. 성적입력
			input_student_data();	// 테스팅
			load_data(1);	// 테스팅
			calculate_score();	// 테스팅
			break;
		case 2:	// 2. 지원가능대학조회
			classify();
			break;
		case 3:	// 3. 데이터저장
			break;
		case 4:	// 종료
			exit(1);
		default :	// else. 메뉴선택 예외처리
			printf("메뉴를 잘못 선택했습니다.\n");
			break;
		}
	}
	
	return 0;
}

////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////// leftRotation 함수 //////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
void leftRotation(treePointer *parent, int *unbalanced)
{
	treePointer grandChild, child;
	child = (*parent)->leftChild;

	if (child->bf == 1) {
		(*parent)->leftChild = child->rightChild;
		child->rightChild = *parent;
		(*parent)->bf = 0;
		(*parent) = child;
	}
	else {
		grandChild = child->rightChild;
		child->rightChild = grandChild->leftChild;
		grandChild->leftChild = child;
		(*parent)->leftChild = grandChild->rightChild;
		grandChild->rightChild = *parent;

		switch (grandChild->bf) {
			case 1:
				(*parent)->bf = -1;
				child->bf = 0;
				break;
			case 0:
				(*parent)->bf = child->bf = 0;
				break;
			case -1:
				(*parent)->bf = 0;
				child->bf = 1;
				break;
		}
		*parent = grandChild;
	}

	(*parent)->bf = 0;
	*unbalanced = FALSE;
}

////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////// rightRotation 함수 /////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
void rightRotation(treePointer *parent, int *unbalanced)
{
	treePointer grandChild, child;
	child = (*parent)->rightChild;

	if (child->bf == -1) {
		(*parent)->rightChild = child->leftChild;
		child->leftChild = *parent;
		(*parent)->bf = 0;
		(*parent) = child;
	}
	else {
		grandChild = child->leftChild;
		child->leftChild = grandChild->rightChild;
		grandChild->rightChild = child;
		(*parent)->rightChild = grandChild->leftChild;
		grandChild->leftChild = *parent;

		switch (grandChild->bf) {
			case 1:
				(*parent)->bf = 0;
				child->bf = -1;
				break;
			case 0:
				(*parent)->bf = child->bf = 0;
				break;
			case -1:
				(*parent)->bf = 1;
				child->bf = 0;
				break;
		}
		*parent = grandChild;
	}

	(*parent)->bf = 0;
	*unbalanced = FALSE;
}

////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////// AVL 트리에서의 삽입 ////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
void avlInsert(treePointer *parent, element x, int *unbalanced)
{
	if (!*parent) {	// 비어있는 트리에 원소를 삽입한다.
		*unbalanced = TRUE;
		MALLOC(*parent, sizeof(treePointer));
		(*parent)->leftChild = (*parent)->rightChild = NULL;
		(*parent)->bf = 0;
		(*parent)->data = x;
	}
	else if (x.key < (*parent)->data.key) {
		avlInsert(&(*parent)->leftChild, x, unbalanced);

		if(*unbalanced)
			switch ((*parent)->bf) {
				case -1: 
					(*parent)->bf = 0;
					*unbalanced = FALSE;
					break;
				case 0:
					(*parent)->bf = 1;
					break;
				case 1:
					leftRotation(parent, unbalanced);
		}
	}
	else if (x.key > (*parent)->data.key) {
		avlInsert(&(*parent)->rightChild, x, unbalanced);
		if(*unbalanced)
			switch ((*parent)->bf) {
				case 1: 
					(*parent)->bf = 0;
					*unbalanced = FALSE;
					break;
				case 0:
					(*parent)->bf = -1;
					break;
				case -1:
					rightRotation(parent, unbalanced);
		}
	}
	else {
		*unbalanced = FALSE;
		printf("The key is already in the tree\n");
	}
}


/*
////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////// 최대히프 삽입 //////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
void push(element item, int *n)
{
	int i;

	if (HEAP_FULL(*n)) {
		printf("The heap is full.\n");
		exit(1);
	}

	i = ++(*n);

	while ((i != 1) && (item.key > heap[i/2].key)) {
		heap[i] = heap[i/2];
		i /= 2;
	}

	heap[i] = item;
}

////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////// 최대히프 삭제 //////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
element pop(int *n)
{
	int parent, child;
	element item, temp;

	if (HEAP_EMPTY(*n)) {
		printf("The heap is empty.\n");
		exit(1);
	}

	item = heap[1];
	temp = heap[(*n)--];
	parent = 1;
	child = 2;

	while (child <= *n) {
		if ((child < *n) && (heap[child].key < heap[child+1].key))
			child++;

		if (temp.key >= heap[child].key)
			break;

		heap[parent] = heap[child];
		parent = child;
		child *= 2;
	}

	heap[parent] = temp;
	return item;
}
*/


////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////// 파일 입출력 ////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
void load_data(int type)
{
	FILE *fp;
	char file[6][100];	// 파일 이름을 일시적으로 저장할 공간
	char fname[100];
	int number, count = 0;
	int i, index;

	if (type == 1) {	// 1. 인문계
		strcpy(file[0], "인문_가_대학.txt"); strcpy(file[1], "인문_나_대학.txt"); strcpy(file[2], "인문_다_대학.txt");
		strcpy(file[3], "인문_가_요강.txt"); strcpy(file[4], "인문_나_요강.txt"); strcpy(file[5], "인문_다_요강.txt");
		
		index = 0;
		for (i=0; i<1; i++) {	// 대학점수에 대해 데이터를 읽어옴
			strcpy(fname, file[i]);
			if ((fp = fopen(fname, "r")) == NULL) {	// 파일 입출력 예외처리
				printf("성적파일 %s을 열 수 없습니다.\n", fname);
				exit(1);
			}
			
			while (!feof(fp)) {
				university[index].group = i+1;	// group 초기화 (1. 가/ 2. 나/ 3. 다)
				fscanf(fp, "%s %s %d", &university[index].name, &university[index].major, &university[index].score);
				index++;
			}
		}

		index = 0;
		for (i=3; i<4; i++) {	// 모집요강에 대해 데이터를 읽어옴
			strcpy(fname, file[i]);
			if ((fp = fopen(fname, "r")) == NULL) {	// 파일 입출력 예외처리
				printf("성적파일 %s을 열 수 없습니다.\n", fname);
				exit(1);
			}
			
			while (!feof(fp)) {
				guidelines[index].group = i-2;	// group 초기화 (1. 가/ 2. 나/ 3. 다)
				fscanf(fp, "%s %d %d %d %d %d", &guidelines[index].name, &guidelines[index].kor, &guidelines[index].mat, 
					&guidelines[index].eng, &guidelines[index].sub, &guidelines[index].indicator);
				index++;
				n_of_univ++;	// 대학교 개수 카운팅
			}
		}
	}

	else if (type == 2) {	// 2. 자연계
		strcpy(file[0], "자연_가_대학.txt"); strcpy(file[1], "자연_나_대학.txt"); strcpy(file[2], "자연_다_대학.txt");
		strcpy(file[3], "자연_가_요강.txt"); strcpy(file[4], "자연_나_요강.txt"); strcpy(file[5], "자연_다_요강.txt");
		
		index = 0;
		for (i=0; i<1; i++) {	// 대학점수에 대해 데이터를 읽어옴
			strcpy(fname, file[i]);
			if ((fp = fopen(fname, "r")) == NULL) {	// 파일 입출력 예외처리
				printf("성적파일 %s을 열 수 없습니다.\n", fname);
				exit(1);
			}

			while (!feof(fp)) {
				university[index].group = i+1;	// group 초기화 (1. 가/ 2. 나/ 3. 다)
				fscanf(fp, "%s %s %d", &university[index].name, &university[index].major, &university[index].score);
				index++;
			}
		}

		index = 0;
		for (i=3; i<4; i++) {	// 모집요강에 대해 데이터를 읽어옴
			strcpy(fname, file[i]);
			if ((fp = fopen(fname, "r")) == NULL) {	// 파일 입출력 예외처리
				printf("성적파일 %s을 열 수 없습니다.\n", fname);
				exit(1);
			}
			
			
			while (!feof(fp)) {
				guidelines[index].group = i-2;	// group 초기화 (1. 가/ 2. 나/ 3. 다)
				fscanf(fp, "%s %d %d %d %d %d", &guidelines[index].name, &guidelines[index].kor, &guidelines[index].mat, 
					&guidelines[index].eng, &guidelines[index].sub, &guidelines[index].indicator);
				index++;
				n_of_univ++;	// 대학교 개수 카운팅
			}
		}
	}
	total_number = index;
}

////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////// 대학별 반영점수 계산 ///////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
void calculate_score() 
{
	int i;

	for (i=0; i<n_of_univ; i++) {
		if (guidelines[i].indicator == 1) {	// 표준점수 반영이면
			guidelines[i].score = ((profile.kor * guidelines[i].kor +
									profile.mat * guidelines[i].mat +
									profile.eng * guidelines[i].eng +
									(profile.sub1 + profile.sub2) * guidelines[i].sub) / 100) * 4;
		}
		else {	// 백분위점수 반영이면
			guidelines[i].score = (profile.kor * guidelines[i].kor +
									profile.mat * guidelines[i].mat +
									profile.eng * guidelines[i].eng +
									(profile.sub1 + profile.sub2) / 2 * guidelines[i].sub) / 100;
		}
	}
}

////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////// 학생정보 입력 //////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
void input_student_data()
{
	printf("계열을 선택해 주시오(1. 인문    2. 자연\n");
	scanf("%d", &profile.course);
	printf("국어 수학 영어 탐구1 탐구2 성적을 입력해 주시오 :");
	scanf("%d %d %d %d %d", &profile.kor, &profile.mat, &profile.eng, &profile.sub1, &profile.sub2);
	// 지역 선택 받기
	// 대학별 반영점수 계산함수 호출
}

////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////// 대학별로 분류 //////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
void classify()
{
	int i, j;
	element x;
	
	// 가군
	for (i=0; i<n_of_univ-1; i++)
		for (j=0; j<total_number-1; j++) {
			if ((strcmp(university[j].name, guidelines[i].name) == 0) && guidelines[i].group == 1) {	
				x.key = university[j].score;							// 같은 대학끼리
				avlInsert(&guidelines[i].AVL_root, x, &unbalanced);		// AVL 트리를 형성한다.
			}
		}
	// 나군
	for (i=0; i<n_of_univ; i++)
		for (j=0; j<total_number; j++) {
			if ((strcmp(university[j].name, guidelines[i].name) == 0) && guidelines[i].group == 2) {	
				x.key = university[i].score;							// 같은 대학끼리
				avlInsert(&guidelines[i].AVL_root, x, &unbalanced);		// AVL 트리를 형성한다.
			}
		}
	// 다군
	for (i=0; i<n_of_univ; i++)
		for (j=0; j<total_number; j++) {
			if ((strcmp(university[j].name, guidelines[i].name) == 0) && guidelines[i].group == 3) {	
				x.key = university[i].score;							// 같은 대학끼리
				avlInsert(&guidelines[i].AVL_root, x, &unbalanced);		// AVL 트리를 형성한다.
			}
		}			
}