#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

typedef struct DLlistNode {
	int data;
	struct DLlistNode* llink;
	struct DLlistNode* rlink;
} DLlistNode;

typedef struct DLlistType {
	DLlistNode* head;
} DLlistType;

int get_length(DLlistType* dlist);
void insert_node_pos(DLlistType* dlist, int pos, int data);
void insert_list_pos(DLlistType* dlist1, DLlistType* dlist2, int pos);
DLlistNode* cut_list_pos(DLlistType* dlist, int pos1, int pos2);
void modification(DLlistType* dlist, int pos, int data);
void copy_list(DLlistType* dlist1, DLlistType* dlist2);

void init(DLlistType* dq) {
	dq->head = NULL;
}

int is_empty(DLlistType* dlist) {
	if (dlist->head == NULL) return TRUE;
	else return FALSE;
}

void display(DLlistType* dlist) {
	DLlistNode* tmp = NULL;

	for (tmp = dlist->head; tmp != NULL; tmp = tmp->rlink) {
		printf("%d -> ", tmp->data);
	}
	printf("\n");
}

DLlistNode* create_node(DLlistNode* llink, int data, DLlistNode* rlink) {
	DLlistNode* new_node;

	new_node = (DLlistNode*)malloc(sizeof(DLlistNode));
	if (new_node == NULL) {
		printf("%s\n", "메모리 할당 오류");
		exit(1); // 메모리 오류가 발생하면 프로그램 종료
	}
	else {
		new_node->data = data;
		new_node->llink = llink;
		new_node->rlink = rlink;
	}

	return new_node;
}

/////////////////////////////////  구현 함수 //////////////////////////////////////
int get_length(DLlistType* dlist) {
    int cnt=0; // DLlistNode의 개수를 담을 변수 생성
    DLlistNode* cur = dlist->head; // cur가 dlist->head를 가리키도록 설정
    while(cur != NULL) { // cur가 오른쪽 끝까지 이동할 때 까지 반복
        cnt++; // 개수를 늘려줌
        cur = cur->rlink; // cur를 오른쪽으로 한칸 이동.
    }
    return cnt; // 세어준 개수를 리턴
}

/////////////////////////////////  구현 함수 //////////////////////////////////////
void insert_node_pos(DLlistType* dlist, int pos, int data) {
    int len = get_length(dlist); // dlist의 개수를 저장
    if(pos > len+1 || pos<=0 ){ // pos가 나올 수 없는 값일 때
        printf("position 오류: position은 %d ~ %d 선택\n", 1, len+1); // 에러 출력
        return; // 함수 종료
    }
    DLlistNode** cur = &(dlist->head); // cur는 dlist->head를 의미함.
    if(is_empty(dlist)) { // dlist가 비어있을 때
        *cur = create_node(NULL, data, NULL); // head에 새로운 노드를 만들어줌
        return; // 함수 종료
    }
    if(pos==1){ // head에 새로운 값을 넣어야 할 때
        DLlistNode *newNode = create_node((*cur)->llink, data, *cur); // 새로운 노드를 만들어서 주소값을 newNode에 대입. cur의 왼쪽과 cur 사이에 들어감
        (*cur)->llink=newNode; // 현재 위치(head)의 왼쪽에 새로운 노드를 넣어줌.
    }
    else if(pos==len+1){
        while((*cur)->rlink!=NULL) *cur=(*cur)->rlink; // cur를 가장 오른쪽으로 이동.
        DLlistNode *newNode = create_node(*cur, data, NULL); // 새로운 노드를 만들어서 주소값을 newNode에 대입. cur 오른쪽에 들어감.
        (*cur)->rlink=newNode; // 현재 위치(오른쪽 끝)의 오른쪽에 새로운 노드를 넣어줌.
    }
    else{
        for(int i=1; i<pos; ++i) *cur = (*cur)->rlink; // 삽입할 위치까지 cur를 오른쪽으로 이동.
        DLlistNode *newNode = create_node((*cur)->llink, data, *cur); // 새로운 노드를 만들어서 주소값을 noewNode에 대입. cur의 왼쪽과 cur 사이에 들어감.
        (*cur)->llink->rlink=newNode; // cur의 왼쪽에 있는 노드 기준에서 오른쪽에 새로운 노드가 와야 함.
        (*cur)->llink=newNode; // cur 기준에서 왼쪽에 새로운 노드가 와야 함.
    }
    while((*cur)->llink!=NULL) (*cur)=(*cur)->llink; // head가 가장 처음으로 오도록 원위치.
}

/////////////////////////////////  구현 함수 //////////////////////////////////////
void insert_list_pos(DLlistType* dlist1, DLlistType* dlist2, int pos) {
    int len1=get_length(dlist1); // dlist1의 길이 저장
    int len2=get_length(dlist2); // dlist2의 길이 저장
    if(len2 == 0) return; // dlist2가 비었으면 함수 종료.
    if(pos > len1+1 || pos<=0){ // pos가 올 수 없는 위치라면
        printf("position 오류: position은 %d ~ %d 선택\n", 1, len1+1); // 오류 메세지 출력
        return; // 함수 종료
    }
    DLlistNode **cur = &dlist1->head; // cur는 dlist1->head를 의미함.
    DLlistNode **cur2 = &dlist2->head; // cur2는 dlist2->head를 의미함.
    if(*cur==NULL) { // dlist1이 빈 리스트라면
        *cur = dlist2->head; // dlist2를 삽입
        return; // 함수 종료
    }
    if(pos==1){ // head에 바로 넣는 것이라면
        while((*cur2)->rlink!=NULL) *cur2=(*cur2)->rlink; // 먼저 cur2를 가장 오른쪽으로 이동.
        (*cur2)->rlink=*cur; // cur2의 오른쪽에 cur, 즉 dlist1->head를 넣어줌.
        (*cur)->llink=*cur2; // cur의 왼쪽에 cur2가 있어야 함.
        *cur2 = NULL; // cur2의 연결 요소 해제
        while((*cur)->llink!=NULL) *cur=(*cur)->llink; // cur이 head가 되도록 원위치.
    }
    else if(pos==len1+1){ // 가장 마지막에 넣는 것 이라면
        while((*cur)->rlink!=NULL) *cur=(*cur)->rlink; // 먼저 cur를 가장 오른쪽으로 이동
        (*cur)->rlink=(*cur2); // cur의 오른쪽에 cur2를 넣어줌.
        (*cur2)->llink=(*cur); // cur2의 왼쪽에 cur를 넣어줌.
        *cur2 = NULL; // cur2의 연결 요소 해제
        while((*cur)->llink!=NULL) *cur=(*cur)->llink; // cur이 head가 되도록 원위치
    }
    else{
        for(int i=1; i<pos-1; ++i) *cur=(*cur)->rlink; // 원하는 위치까지 cur를 오른쪽으로 한칸씩 이동
        while((*cur2)->rlink!=NULL) *cur2=(*cur2)->rlink; // cur2는 가장 오른쪽으로 이동.
        (*cur2)->rlink=(*cur)->rlink; // cur2의 오른쪽에 cur의 오른쪽 노드가 와야 함.
        (*cur)->rlink->llink=*cur2; // cur의 오른쪽 노드의 왼쪽에 cur2가 와야 함.
        while((*cur2)->llink!=NULL) *cur2=(*cur2)->llink; // cur2를 왼쪽 끝으로 (기존 dlist2->head)로 이동.
        (*cur)->rlink=*cur2; // cur의 오른쪽에 cur2가 와야 함.
        (*cur2)->llink=*cur; // cur2의 왼쪽에 cur이 와야 함.
        *cur2=NULL; // cur2의 연결 요소 해제
        while((*cur)->llink!=NULL) *cur=(*cur)->llink; // cur이 head가 되도록 원위치.
    }
}

/////////////////////////////////  구현 함수 //////////////////////////////////////
DLlistNode* cut_list_pos(DLlistType* dlist, int pos1, int pos2) {
    DLlistNode *l,*r; // l은 pos1에 위치한 노드를, r은 pos2에 위치한 노드를 담을 예정.
    int len = get_length(dlist); // dlist의 길이 저장.
    DLlistNode **cur = &dlist->head; // cur는 dlist->head를 의미함.
    if(cur==NULL) { // dlist가 비어있었다면
        printf("공백 삭제 오류\n"); // 오류 메세지 출력
        return NULL; // 함수 종료
    }
    if(pos1>pos2 || pos2 > len){ // 있을 수 없는 위치가 들어왔다면
        printf("position 오류: 1 <= position1 <= position2 <= %d 에서 선택\n", len); // 오류 메세지 출력
        return NULL; // 함수 종료
    }
    DLlistNode *ret; // 리턴할 리스트의 가장 첫 노드를 가리킬 예정.
    if(len==1){ // dlist에 노드가 1개 있다면
        ret=*cur; // ret에 cur를 담고
        *cur=NULL; // cur의 연결요소해제
        return ret; // ret 리턴
    }
    for(int i=1; i<=pos2; ++i){ // 1부터 pos2까지 반복
        if(i==pos1){ // pos1에 해당하는 노드를 만나면
            l=*cur; // l에 대입
        }
        if(i==pos2){ // pos2에 해당하는 노드를 만나면
            r=*cur; // r에 대입
        }
        if((*cur)->rlink!=NULL) *cur=(*cur)->rlink; // cur를 오른쪽으로 하나씩 이동
    }
    while((*cur)->llink!=NULL) *cur=(*cur)->llink; // cur를 다시 head로 원위치
    if(l->llink==NULL){ // l이 head라면
        while(*cur!=r) *cur=(*cur)->rlink; // cur를 r까지 옮김.
        *cur=(*cur)->rlink; // cur가 r의 바로 오른쪽에 오도록 이동.
        r->rlink=NULL; // r에서 cur로 가는 길을 막음.
        (*cur)->llink=NULL; // cur에서 r로 가는 길을 막음.
        ret=l; // ret에 l 대입
    }
    else{ // l이 head가 아니라면
        while(*cur != l) *cur=(*cur)->rlink; // cur이 l이 될 때까지 오른쪽으로 이동
        (*cur)->rlink=r->rlink; // cur의 오른쪽에 r의 오른쪽에 있던 노드가 오도록 함.
        if((*cur)->rlink!=NULL) (*cur)->rlink->llink=*cur; // cur이 마지막 노드가 아니라면 cur의 오른쪽 노드 기준 왼쪽 노드는 cur이 되도록 함.
        l->llink=NULL; // l과 기존 리스트의 연결 요소 해제
        r->rlink=NULL; // r과 기존 리스트의 연결 요소 해제
        ret=l; // ret에 l 대입
    }
    while((*cur)->llink!=NULL) *cur=(*cur)->llink; // cur이 head에 오도록 원위치
    return ret; // ret 리턴
}

/////////////////////////////////  구현 함수 //////////////////////////////////////
void modification(DLlistType* dlist, int pos, int data) {
    DLlistNode *cur = dlist->head; // cur이 dlist->head를 가리킴.
    if(cur==NULL){ // dlist가 비어있을 때
        printf("공백 수정 오류\n"); // 오류 메세지 출력
        return; // 함수 종료
    }
    int len = get_length(dlist); // dlist의 길이 저장
    if(pos > len || pos<=0){ // pos 값이 올바르지 않을 때
        printf("position 오류: position은 %d ~ %d 에서 선택\n", 1, len); // 오류 메세지 출력
        return; // 함수 종료
    }
    for(int i=1; i<pos; ++i) cur=cur->rlink; // 원하는 위치까지 cur를 오른쪽으로 이동
    cur->data=data; // 원하는 위치의 노드의 data를 원하는 data로 수정
}

/////////////////////////////////  구현 함수 //////////////////////////////////////
void copy_list(DLlistType* dlist1, DLlistType* dlist2) {
    DLlistNode **cur = &dlist1->head; // cur은 dlist1->head를 의미함.
    DLlistNode **cur2 = &dlist2->head; // cur2는 dlist2->head를 의미함.
    DLlistNode *newNode = create_node(NULL, (*cur2)->data, NULL); // cur2의 데이터를 가진 새로운 노드를 생성.
    (*cur)=newNode; // cur에 새로운 노드를 넣어줌.
    while((*cur2)->rlink!=NULL){ // cur2가 오른쪽 끝에 도달할 때 까지
        (*cur2)=(*cur2)->rlink; // cur2를 먼저 오른쪽으로 하나 이동
        (*cur)->rlink = create_node((*cur), (*cur2)->data, NULL); // cur2의 데이터를 가진 새로운 노드를 생성 후 cur의 오른쪽에 넣어줌.
        (*cur)->rlink->llink=*cur; // 방금 추가한 노드의 왼쪽은 cur이 되어야 함.
        *cur=(*cur)->rlink; // cur도 오른쪽으로 하나 이동
    }
    while((*cur)->llink!=NULL) (*cur)=(*cur)->llink; // cur을 head로 원위치
    while((*cur2)->llink!=NULL) (*cur2)=(*cur2)->llink; // cur2를 head로 원위치
}

int main() {
	DLlistType  dList1, dList2;
	DLlistNode* removed_node = NULL;
	int len, i;
	
	init(&dList1); init(&dList2);

	printf("insert_node_pos(): \n");
	insert_node_pos(&dList1, 1, 90);
	insert_node_pos(&dList1, 1, 20);
	insert_node_pos(&dList1, 1, 10);
	printf("dList1 : ");
	display(&dList1); printf("\n");

	printf("copy_list(): \n");
	copy_list(&dList2, &dList1);
	printf("dList2 : ");
	display(&dList2); printf("\n");

	printf("modification(): \n");
	modification(&dList2, 1, 30);
	modification(&dList2, 2, 40);
	modification(&dList2, 3, 50);
	printf("dList2 : ");
	display(&dList2); 	printf("\n");

	printf("insert_list_pos(): \n");
	insert_list_pos(&dList1, &dList2, 3);
	printf("dList1 : ");
	display(&dList1); 	printf("\n");

	len = get_length(&dList1);
	printf("dList1 length by get_length(): %d \n\n", len);

	printf("cut_list_pos(): \n");
	for (i = 1; i<= len; i++) {
		removed_node = cut_list_pos(&dList1, 1, 1);
		printf("node %d data : %d \n\n",i, removed_node->data);
		free(removed_node);
	}

	return 0;
}