/*

                컴퓨터 알고리즘 및 실험

                집합
                
                2004114180 정보통신공학과 김대현

                2008. 11. 20.
*/
#define WIN32_LEAN_AND_MEAN
#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int SZ_NAME = 64;
const int SZ_BUFF = 20;
const int SZ_ENTER_ELEMENT = 3;

/*
*       선언
*/
typedef struct _node{
        int data;
        struct _node *next;
        struct _node *prev;
}linkedList;

typedef struct {
        linkedList *head;
        linkedList *tail;
        int size;
}linkedList_h;

typedef linkedList_h Set;
#define createSetHead createListHead

/*
*       내부 인터페이스
*/
linkedList_h *createListHead();
BOOL list_ins_next(linkedList_h *, const int);
BOOL list_ins_next(linkedList_h *, linkedList *, const int);
int list_rem_next(linkedList_h *);
void list_print(linkedList_h *);
void list_rprint(linkedList_h *);
void list_free(linkedList_h *);

/*
*       사용자 인터페이스
*/
BOOL set_insert(Set *, int);
BOOL set_is_member(Set *, int);
Set *set_intersection(Set *, int arr_n[]);
Set *set_difference(Set *, Set *);

int main()
{
        Set *S1 = createSetHead();
        Set *seti = createSetHead();
        Set *setd = createSetHead();
        int selecter = 0;
        int arr_n[2];

        while(selecter != 4)
        {
                puts("\n집합 실행 메뉴");
                puts("=========================");
                puts("1. Insert of element");
                puts("2. Intersection of set");
                puts("3. Difference of set");
                puts("4. End of program");
                puts("=========================");
                printf("Select: ");
                fflush(stdin);
                if(scanf("%d",&selecter) != 1)
                {
                        fflush(stdin);
                        printf("입력 형식 오류.\n");
                        continue;
                }

                switch(selecter){
                        case 1:
                                /* 1. Insert of element */
                                printf("Enter element : ");
                                if(scanf("%d", &arr_n[0]) != 1)
                                {
                                        printf("입력 형식 오류.\n");
                                        fflush(stdin);
                                }
                                if(set_is_member(S1, arr_n[0]))
                                {
                                        printf("Failed\n");
                                }
                                else
                                {
                                        printf("Success!!\n");
                                        set_insert(S1, arr_n[0]);
                                }
                                printf("Element of Set :");
                                list_rprint(S1);
                                break;
                        case 2:
                                /* 2. Intersection of set */
                                printf("Enter New Set : ");
                                if(scanf("%d %d %d", &arr_n[0], &arr_n[1], &arr_n[2]) != 3)
                                {
                                        printf("입력 형식 오류.\n");
                                        fflush(stdin);
                                        break;
                                }
                                seti = set_intersection(S1, arr_n);
                                if(seti->head == NULL)
                                {
                                        printf("일치하는 원소 : 존재하지 않음!\n");
                                }
                                else
                                {
                                        printf("일치하는 원소 : ");
                                        list_rprint(seti);
                                        printf("교집합 연산 결과\n");
                                }
                                list_free(S1);
                                S1 = seti;
                                printf("Element of Set : ");
                                list_rprint(S1);
                                break;
                        case 3:
                                /* 3. Difference of set */
                                printf("Enter New Set : ");
                                if(scanf("%d %d %d", &arr_n[0], &arr_n[1], &arr_n[2]) != 3)
                                {
                                        printf("입력 형식 오류.\n");
                                        fflush(stdin);
                                        break;
                                }
                                seti = set_intersection(S1, arr_n);
                                if(seti->head == NULL)
                                {
                                        printf("일치하는 원소 : 존재하지 않음!\n");
                                }
                                else
                                {
                                        printf("일치하는 원소 : ");
                                        list_rprint(seti);
                                        printf("차집합 연산 결과\n");
                                        setd = set_difference(S1, seti);
                                        list_free(S1);
                                        S1 = setd;
                                }
                                printf("Element of Set : ");
                                list_rprint(S1);
                                break;
                        case 4:
                                /* 4. End of program */
                                printf("프로그램을 종료합니다.\n");
                                break;
                        default:
                                printf("잘못된 명령입니다.\n");
                                break;
                }
        }

        list_free(S1);

        return 0;
}

/*
*       집합 정의
*/
BOOL set_insert(Set *S, int n)
{
        /*
                TODO: 집합에 같은 멤버가 있으면 리턴한다. 중복 삽입을 방지.
        */
        if(set_is_member(S, n))
        {
                return TRUE;
        }

        return list_ins_next(S, n);
}

BOOL set_is_member(Set *S, int n)
{
        linkedList *p = S->head;

        while(p != NULL)
        {
                if(p->data == n)
                {
                        return TRUE;
                }
                p = p->next;
        }

        return FALSE;
}

Set *set_intersection(Set *S1, int arr_n[])
{
        Set *seti = createSetHead();

        for(int i = 0; i < SZ_ENTER_ELEMENT; ++i)
        {
                if(set_is_member(S1, arr_n[i]))
                {
                        list_ins_next(seti, arr_n[i]);
                }
        }

        return seti;
}

Set *set_difference(Set *S1, Set *S2)
{
        Set *setd = createSetHead();
        linkedList *p = S1->head;

        while(p != NULL)
        {
                if(!set_is_member(S2, p->data))
                {
                        list_ins_next(setd, p->data);
                }
                p = p->next;
        }

        return setd;
}

/*
*       연결 리스트 정의
*/
linkedList_h *createListHead()
{
        linkedList_h *r = NULL;
        r=(linkedList_h*)malloc(sizeof(linkedList_h));
        r->head=NULL;
        r->tail=NULL;
        r->size=0;
        return r;
}

BOOL list_ins_next(linkedList_h *L, const int n)
{
        /*
                TODO: 새 노드 생성 후 데이터를 삽입한다.
        */
        linkedList *newNode = NULL;
        newNode = (linkedList*)malloc(sizeof(linkedList));
        if(newNode == NULL)
        {
                printf("Memory Set ERROR.\n");
                exit(1);
        }
        newNode->data = n;
        newNode->next = NULL;
        newNode->prev = NULL;

        /*
                TODO: 리스트에 노드가 없으면 헤드에 새 노드를 넣고 리턴한다.
        */
        if(L->head == NULL)
        {
                L->head = newNode;
                L->tail = newNode;
                ++(L->size);
                return TRUE;
        }

        /*
                TODO: 가장 앞 노드(L->head)에 새 노드를 추가한다.
        */
        L->head->prev = newNode;
        newNode->next = L->head;
        L->head = newNode;
        ++(L->size);
        return TRUE;
}

BOOL list_ins_next(linkedList_h *L, linkedList *t, const int n)
{
        /*
                TODO: 새 노드 생성 후 데이터를 삽입한다.
        */
        linkedList *newNode = NULL;
        newNode = (linkedList*)malloc(sizeof(linkedList));
        if(newNode == NULL)
        {
                printf("Memory Set ERROR.\n");
                exit(1);
        }
        newNode->data = n;
        newNode->next = NULL;

        /*
                TODO: 리스트에 노드가 없으면 헤드에 새 노드를 넣고 리턴한다.
        */
        if(L->head == NULL)
        {
                L->head = newNode;
                L->tail = newNode;
                ++(L->size);
                return FALSE;
        }

        /*
                TODO: 타겟 노드까지 이동한다.
        */
        linkedList *p = L->head;
        while(p->next != NULL || p == t)
        {
                p = p->next;
        }

        /*
                TODO: 타겟 노드 뒤에 새 노드를 추가한다.
        */
        newNode->next = p->next;
        p->next=newNode;
        ++(L->size);
        if(L->tail->next != L->head)
        {       /* 추가된 노드가 테일이면 L->tail 을 새 노드로 한다. */
                L->tail = newNode;
        }
        return FALSE;
}

int list_rem_next(linkedList_h *L)
{
        int r = 0;
        linkedList *p = L->head;

        L->head = L->head->next;

        r = p->data;
        free(p);

        return r;
}

void list_print(linkedList_h *L)
{
        if(L->head == NULL)
        {
                printf("공집합\n");
                return;
        }

        linkedList *p = L->head;

        while(1){
                if(p->next == NULL)
                {
                        printf(" %d\n", p->data);
                        break;
                }
                else
                {
                        printf(" %d, ", p->data);
                }
                p = p->next;
        }
}

void list_rprint(linkedList_h *L)
{
        if(L->head == NULL)
        {
                printf("공집합\n");
                return;
        }

        linkedList *p = L->tail;

        while(1){
                if(p->prev == NULL)
                {
                        printf(" %d\n", p->data);
                        break;
                }
                else
                {
                        printf(" %d, ", p->data);
                }
                p = p->prev;
        }
}


void list_free(linkedList_h *L)
{
        if(L->head == NULL)
                return;

        linkedList *p = L->head;
        while(1)
        {
                if(L->head == L->tail)
                {
                        free(L->head);
                        free(L);
                        break;
                }
                p = L->head;
                L->head = L->head->next;
                free(p);
        }
}