/*
        집합
        
        2008. 11. 13.
*/
#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;

/*
*   선언부
*/
typedef struct _node{
    char *name;
    struct _node *next;
}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 char *);
BOOL list_ins_next(linkedList_h *, linkedList *, const char *);
int list_rem_next(linkedList_h *);
void list_print(linkedList_h *);

/*
*   사용자 인터페이스
*/
BOOL set_insert(Set *, char *);
BOOL set_is_member(Set *, char *);
Set *set_union(Set *, Set *);
Set *set_intersection(Set *, Set *);
Set *set_difference(Set *, Set *);

int main()
{
    Set *S1 = createSetHead();
    Set *S2 = createSetHead();
    Set *setu = createSetHead();
    Set *seti = createSetHead();
    Set *setd = createSetHead();

    set_insert(S1, "CC");
    set_insert(S1, "AA");
    set_insert(S1, "DD");
    set_insert(S1, "FF");

    set_insert(S2, "AA");
    set_insert(S2, "BB");
    set_insert(S2, "FF");

    list_print(S1);
    list_print(S2);

    puts("");
    setu = set_union(S1, S2); /* S1 과 S2 의 합집합 */
    list_print(setu);

    puts("");
    seti = set_intersection(S1, S2); /* S1 과 S2 의 교집합 */
    list_print(seti);

    puts("");
    setd = set_difference(S1, S2); /* S1 과 S2 의 차집합 */
    list_print(setd);

    return 0;
}

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

    return list_ins_next(S, str);
}

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

    while(p != NULL)
    {
        if(strcmp(p->name, str) == 0)
        {
            return TRUE;
        }
        p = p->next;
    }

    return FALSE;
}

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

    while(p != NULL)
    {
        list_ins_next(setu, S1->tail, p->name);
        p = p->next;
    }

    p = S2->head;
    while(p != NULL)
    {
        if(set_is_member(setu, p->name))
            {/* no work */}
        else
            list_ins_next(setu, S2->tail, p->name);
        p = p->next;
    }

    return setu;
}

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

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

    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->name))
        {
            list_ins_next(setd, p->name);
        }
        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 char *str)
{
    /*
        TODO: 새 노드 생성 후 데이터를 삽입한다.
    */
    linkedList *newNode = NULL;
    newNode = (linkedList*)malloc(sizeof(linkedList));
    if(newNode == NULL)
    {
        printf("Memory Set ERROR.\n");
        exit(1);
    }
    newNode->name = (char*)malloc(sizeof(char)*SZ_NAME);
    strcpy(newNode->name, str);
    newNode->next = NULL;

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

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

/*
    인자가 리스트 헤더, 노드, 입력 데이터면 전달받은 노드 뒤에 새 노드를 추가한다.
*/
BOOL list_ins_next(linkedList_h *L, linkedList *t, const char *str)
{
    /*
        TODO: 새 노드 생성 후 데이터를 삽입한다.
    */
    linkedList *newNode = NULL;
    newNode = (linkedList*)malloc(sizeof(linkedList));
    if(newNode == NULL)
    {
        printf("Memory Set ERROR.\n");
        exit(1);
    }
    newNode->name = (char*)malloc(sizeof(char)*SZ_NAME);
    strcpy(newNode->name, str);
    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 = atoi(p->name);
    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(" %s -> NULL\n", p->name);
            break;
        }
        else
        {
            printf(" %s ->", p->name);
        }
        p = p->next;
    }
}

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);
    }
}