/*
                컴퓨터 알고리즘 및 실험 4조
                

                뉴스 분류 시스템



                2008. 11. 28.

                2004114180 정보통신공학과 김대현
*/
#include <iostream>
#include <string>
#include <list>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <malloc.h>
#include <assert.h>
#include <atlcore.h>            // ATL 매크로 사용
#include <boost/regex.hpp>      // Boost.Regex lib
using namespace std;

const int BUFFER_SIZE = 5120;

//------------------------------
//      keyword_list.h
//------------------------------
namespace Keyword
{
        typedef struct _node {
                char *keyword;
                int weight;
                struct _node *next;
        } node;

        typedef struct {
                node *head;
                node *tail;
                int keyword_size;
                int article_size;
        } linkedList;

        linkedList *init_list(void);
        node *init_node(const char *, int priority = 1);
        BOOL list_insert(linkedList *, char *, int priority = 1);
        void list_print(linkedList *);
        int list_fprint(linkedList *, FILE *);
        void list_free(linkedList *);
}

//------------------------------
//      quicksort.h
//------------------------------
namespace Keyword
{
        node *quicksort_helper(node *);
        linkedList *node_quicksort(linkedList *);

        void sort_node(linkedList *);
}

//------------------------------
//      category_list.h
//------------------------------
namespace Category
{
        typedef struct _node {
                char category[20];
                void *vright;
                struct _node *down;
        } node;

        typedef struct {
                node *head;
                int size;
        } linkedList;

        linkedList *init_list(void);
        node *init_node(const char *);
        BOOL list_insert(linkedList *, char *, char *);
        void list_print(linkedList *);
        void list_fprint(linkedList *, FILE *);
        void list_free(linkedList *);
}

//------------------------------
//      main.h  사용자 인터페이스
//------------------------------
typedef struct _fitCategory {
        char *category;
        double fitness;
} fitCategory;

unsigned tokenise(list<wstring> &, wstring &);
char *set_category(const char *, Category::linkedList *);
void set_keyword(Keyword::linkedList *, Keyword::linkedList *);
Keyword::linkedList *get_keyword(const char *);
void treat_words(char *);
void set_category_keyword(Category::linkedList *, char *, Keyword::linkedList *);
Keyword::linkedList *get_category_keyword(Category::linkedList *, char *);
void list_all_free(Category::linkedList *);
void make_db(Category::linkedList *);

Keyword::linkedList *file_get_keyword(const char *);


double fitness_check_helper(Keyword::linkedList *, Keyword::linkedList *);
fitCategory *fitness_check(Category::linkedList *, Keyword::linkedList *);



//--------------------------
//      main.cpp
//--------------------------
int main()
{
        char news_article[] = "http://news.empas.com/show.tsp/";        // 기사 주소
        char category[20];              // 카테고리
        char cmd[80];                   // 시스템 커맨드
        char date_and_serial[15];       // 일자n일련번호
        int date = 20081207;    // 기사 일자
        int serial = 1;                 // 기사 일련번호
        int selecter = 0;               // 메뉴 셀렉터
        fitCategory fitc;               // 일치한 기사 분류 정보
        Category::linkedList *category_list = Category::init_list();
        Keyword::linkedList *keyword_list = Keyword::init_list();

        do{
                cout << "뉴스 분류 시스템" << endl;
                cout << "=======================" << endl;
                cout << "1. 분류 DB 생성 " << endl;
                cout << "2. 분류 DB 불러오기 " << endl;
                cout << "3. 분류 시작" << endl;
                cout << "4. 환경 설정" << endl;
                cout << "5. 프로그램 종료" << endl;
                cout << "=================" << endl;
                cout << "Select: ";
                cin >> selecter;
                getchar();

                switch(selecter){
                        case 1:
                                /*printf("1. 수집 날짜 입력(입력형식 yyyymmdd, 예:20081127) : ");
                                scanf("%d", &date);
                                printf("1. 시작 기사 번호 입력(입력형식 yyyymmdd, 예:20081127) : ");
                                scanf("%d", &serial);
                                getchar();*/
                                for(int i = 0; i < 20000; ++i, ++serial)
                                {
                                        strcpy(news_article, "http://news.empas.com/show.tsp/");
                                        sprintf(date_and_serial, "%dn%05d", date, serial);
                                        sprintf(cmd, "wget -q --tries=3 -N %s%s", news_article, date_and_serial);
                                        system(cmd);
                                        printf("--geturl %s%s\n", news_article, date_and_serial);
                                        strcpy(category, set_category(date_and_serial, category_list));

                                        if(category != "DOES NOT EXIST")
                                        {
                                                keyword_list = get_keyword(date_and_serial);
                                                set_category_keyword(category_list, category, keyword_list);
                                        }
                                        sprintf(cmd, "del %s", date_and_serial);
                                        system(cmd);

                                        if(serial%100 == 0)
                                                make_db(category_list);
                                }
                                make_db(category_list);
                                /******************
                                TODO : 구현 필요. 입력 형식이 올바른지 체크하는 함수                                 
                                if(checkVerify(number_of_day, number_of_news))
                                {
                                        cout << "입력 형식 오류." << endl;
                                        break;
                                }
                                */
                                break;
                        case 2:
                                printf("분류 입력 : ");
                                scanf("%s", category);
                                keyword_list = get_category_keyword(category_list, category);
                                Keyword::list_print(keyword_list);
                                break;
                        case 3:
                                keyword_list = file_get_keyword("aa.txt");
                                //fitc = fitness_check(category_list, keyword_list);
                                //Keyword::list_free(keyword_list);
                                //printf("%s %0.2f", fitc.category, fitc.fitness);
                                break;
                        case 4:
                                printf("프로그램을 종료합니다.\n");
                                break;
                        default:
                                printf("잘못된 명령입니다.\n");
                                break;
                }
        }while(selecter != 4);
        list_all_free(category_list);
        return 0;
}

//--------------------------
//      fitness_check.cpp
//--------------------------
double fitness_check_helper(Keyword::linkedList *ck_list, Keyword::linkedList *k_list)
{
        int total_weight = 0;   // 분류 키워드의 총 가중치
        int fit_weight = 0;             // 분류 키워드의 일치하는 가중치
        double fitness = 0.0;   // 리턴할 적합도 결과 0.00% ~ 100.00%

        Keyword::node *kp = k_list->head;
        Keyword::node *ckp = ck_list->head;

        while(kp != NULL)
        {
                ckp = ck_list->head             // rewind
                while(ckp != NULL)
                {
                        if(strcmp(kp->keyword, ckp->keyword) == 0)
                        {
                                fit_weight += kp->weight;
                        }
                        total_weight += kp->weight;
                        ckp = ckp->next;
                }
                kp = kp->next
        }
        return (fitness = fit_weight / static_cast<double>total_weight * 100);
}

fitCategory *fitness_check(Category::linkedList *c_list, Keyword::linkedList *k_list)
{
        Category::node *p = c_list->head;
        Category::node *pr = (Category::node *)p->vright;
        Keyword::linkedList *ck_list = NULL;
        double fitness = 0.0;
        fitCategory fitc;

        while(p != NULL)
        {
                pr = (Category::node *)p->vright;
                while(pr != NULL)
                {
                        ck_list = get_category_keyword(c_list, pr->category);
                        fitness = fitness_check_helper(ck_list, k_list);

                        if(fitc.fitness < fitness)
                        {
                                strcpy(fitc.category, pr->category);
                                fitc.fitness = fitness;
                        }
                        pr = pr->vright;
                }
                p = p->next;
        }
        return fitc;
}

//--------------------------
//      keyword_process.cpp
//--------------------------
void make_db(Category::linkedList *c_list)
{
        char filename[] = "DB_nnnn";
        int serial = 1;
        int article_size = 0;
        Category::node *p = c_list->head;
        Category::node *pr = (Category::node *)p->vright;
        FILE *fp = NULL;

        while(p != NULL)
        {
                pr = (Category::node *)p->vright;
                while(pr != NULL)
                {
                        sprintf(filename, "DB_%04d", serial);
                        fp = fopen(filename, "w");
                        fprintf(fp, "%s %s\n", p->category, pr->category);
                        //Keyword::sort_node((Keyword::linkedList *)pr->vright);
                        article_size += Keyword::list_fprint((Keyword::linkedList *)pr->vright, fp);
                        fclose(fp);
                        pr = pr->down;
                        ++serial;
                }
                p = p->down;
        }
        strcpy(filename, "DB_0000");
        fp = fopen(filename, "w");
        fprintf(fp, "total %d articles\n", article_size);
        fprintf(fp, "total %d categories\n", c_list->size);
        Category::list_fprint(c_list, fp);
        fclose(fp);
}

char *set_category(const char *getfile, Category::linkedList *c_list)
{
        using namespace Category;
        char buffer[BUFFER_SIZE] = { '0' };
        boost::regex does_not_exist("해당 기사를 찾을 수 없습니다");
        boost::regex expression("뉴스 홈</a> &gt;"); // 카테고리 시작을 알리는 정규식
        boost::cmatch matches;
        char return_value[20];

        FILE *fp = fopen(getfile, "r");
        while(fgets(buffer, BUFFER_SIZE, fp))
        {
                if(boost::regex_search(buffer, does_not_exist))
                {
                        fclose(fp);
                        return "DOES NOT EXIST";
                }
                if(boost::regex_search(buffer, expression))
                {
                        // 첫번째 카테고리
                        expression.assign("<a (?:\"[^\"]*\"|\'[^\']*\'|[^\'\">])*> ([^<]*)(.*)");
                        boost::regex_search(buffer, matches, expression);
                        string str1(matches[1].first, matches[1].second);

                        // 두번째 카테고리
                        fgets(buffer, 1024, fp);
                        expression.assign("<a (?:\"[^\"]*\"|\'[^\']*\'|[^\'\">])*>(.*)");
                        boost::regex_search(buffer, matches, expression);
                        string str2 = matches[1];
                        strcpy(return_value, str2.c_str());
                        if(strcmp(return_value, "속보") == 0)
                        {       // 만약 속보 카테고리면 리턴
                                fclose(fp);
                                return "DOES NOT EXIST";
                        }

                        // 카테고리 입력 
                        list_insert(c_list, const_cast<char*>(str1.c_str()), const_cast<char*>(str2.c_str()));
                        // list_print(c_list); // 디버깅 출력
                        break;
                }
        }
        fclose(fp);
        return return_value;
}

void set_keyword(Keyword::linkedList *targetList, Keyword::linkedList *addList)
{
        Keyword::node *p = targetList->head;
        Keyword::node *pa = addList->head;
        Keyword::node *temp = NULL;

        while(pa != NULL)
        {
                p = targetList->head;
                while(p != NULL)
                {       // 같은 키워드가 있으면 가중치 증가
                        if(strcmp(pa->keyword, p->keyword) == 0)
                        {
                                p->weight += pa->weight;
                                break;
                        }
                        p = p->next;
                }
                if(p == NULL)
                {       // 같은 키워드를 찾을 수 없으면 리스트에 추가
                        Keyword::list_insert(targetList, pa->keyword);
                }
                pa = pa->next;
        }
        //Keyword::node_quicksort(targetList);
}

Keyword::linkedList *get_keyword(const char *getfile)
{
        using namespace Keyword;
        USES_CONVERSION;        // mbs <-> wcs 변환을 위한 ATL 매크로
        char buffer[BUFFER_SIZE];       // 파일 라인 버퍼
        boost::regex does_not_exist("해당 기사를 찾을 수 없습니다");
        boost::regex exp_post("<!--기사 제목-->");  // 기사 제목 구문
        boost::regex exp_body("DCM_BODY-->");           // 기사 본문 구문
        boost::regex expression;
        boost::cmatch matches;  // 매치될 변수
        list<wstring> post_l;   // 제목 키워드 리스트
        list<wstring> body_l;   // 본문 키워드 리스트
        wstring s;                              // 스플릿을 위한 와이드 스트링
        linkedList *return_list = init_list();
        unsigned int result = 0;

        FILE *fp = fopen(getfile, "r");
                assert(fp != NULL);
        while(fgets(buffer, BUFFER_SIZE, fp))
        {
                if(boost::regex_search(buffer, does_not_exist))
                {
                        break;
                }
                // 기사 제목 추출
                if(boost::regex_search(buffer, exp_post))
                {
                        fgets(buffer, BUFFER_SIZE, fp);

                        // 불용어 처리
                        treat_words(buffer);

                        //      제목 추출 
                        expression.assign("<!--DCM_TITLE--><b>(.*)</b><!--/DCM_TITLE-->");
                        boost::regex_search(buffer, matches, expression);
                        string match(matches[1].first, matches[1].second);

                        //      제목 토큰 분리
                        s = A2W(match.c_str());
                        result = tokenise(post_l, s);
                        while(post_l.size())
                        {
                                s = *(post_l.begin());
                                post_l.pop_front();
                                list_insert(return_list, W2A(s.c_str()), 5);    // 제목은 중요도가 5
                        }
                }
                // 본문 주제어 추출
                if(boost::regex_search(buffer, exp_body))
                {
                        // 불용어 처리
                        treat_words(buffer);

                        //      본문 토큰 분리
                        s = A2W(buffer);
                        result += tokenise(body_l, s);
                        while(body_l.size())
                        {
                                s = *(body_l.begin());
                                body_l.pop_front();
                                list_insert(return_list, W2A(s.c_str()));
                        }
                        node_quicksort(return_list);
                }
        }
        fclose(fp);
        printf("%d tokens found\n", result);
        if(result == 0)
                { return NULL; }
        return return_list;
}

Keyword::linkedList *file_get_keyword(const char *filename)
{
        using namespace Keyword;
        USES_CONVERSION;                // mbs <-> wcs 변환을 위한 ATL 매크로
        char buffer[BUFFER_SIZE] = { '0' };             // 파일 라인 버퍼

        FILE *fp = fopen(filename, "r");
                assert(fp != NULL);
        while(fgets(buffer, BUFFER_SIZE, fp))
        {
                // 불용어 처리
                treat_words(buffer);

                // 토큰 분리
                s = A2W(buffer);
                result = tokenise(post_l, s);
                while(post_l.size())
                {
                        s = *(post_l.begin());
                        post_l.pop_front();
                        list_insert(return_list, W2A(s.c_str()));       // 리스트 입력
                }
        }
        list_print(return_list);
        flose(fp);
        return return_list;
}

Keyword::linkedList *get_category_keyword(Category::linkedList *c_list, char *category)
{
        Category::node *p = c_list->head;
        Category::node *pr = (Category::node *)p->vright;
        int len = strlen(category);
        category[len] = '\n';
        category[len + 1] = '\0';

        while(p != NULL)
        {
                pr = (Category::node *)p->vright;
                while(pr != NULL)
                {
                        if(strcmp(pr->category, category) == 0)
                        {
                                return (Keyword::linkedList *)pr->vright;
                        }
                        pr = pr->down;
                }
                p = p->down;
        }

        return NULL;
}

void set_category_keyword(Category::linkedList *c_list, char *category, Keyword::linkedList *k_list)
{
        Category::node *p = c_list->head;
        Category::node *pr = (Category::node *)p->vright;

        while(p != NULL)
        {
                pr = (Category::node *)p->vright;
                while(pr != NULL)
                {
                        if(strcmp(pr->category, category) == 0)
                        {
                                if(pr->vright == NULL)
                                {
                                        pr->vright = k_list;    // 만약 카테고리에 키워드 리스트가 없으면 키워드 리스트 연결
                                }
                                else
                                {
                                        // 이미 키워드 리스트가 있으면 키워드 리스트 합치기
                                        ((Keyword::linkedList *)pr->vright)->article_size += 1;
                                        set_keyword((Keyword::linkedList *)pr->vright, k_list);
                                        Keyword::list_free(k_list);
                                        // Keyword::list_print((Keyword::linkedList *)pr->vright); // 디버깅 출력
                                }
                                return;
                        }
                        pr = pr->down;
                }
                p = p->down;
        }
}

unsigned tokenise(list<wstring> &l, wstring &s)
{
   return boost::regex_split(back_inserter(l), s);
}

void treat_words(char *buffer)
{
        boost::regex expression;
        string sbuffer = buffer;
        string exp_batch;

        //--------------------------------------------------
        //      모든 기사 마지막에는 기자 혹은 저작권자 이름과 이메일이 있어 이메일 이후를 잘라낸다.
        string email = "[0-9a-zA-Z]([-_.]?[0-9a-zA-Z])*@[0-9a-zA-Z]([-_.]?[0-9a-zA-Z])*.[a-zA-Z]{2,3}";
        string to_end = ".*$";
        exp_batch = email + to_end;
        expression.assign(exp_batch);
        sbuffer = boost::regex_replace(sbuffer, expression, " ", boost::format_all);


        //--------------------------------------------------
        //      HTML, 숫자, 기호, 특수 기호를 공백으로 치환
        //string jamo = "[\\u3008-\\u3009]";
        string html = "<(\"[^\"]*\"|\'[^\']*\'|[^\'\">])*>"; // HTML 매치
        string num_and_sign = "[-0-9#&+%@=/\\:;\.,\'\"^`~_|!\?*$#<>()]|&([0-9a-z]+);"; // 숫자와 기호 매치
        string or = "|"; // 또는
        exp_batch = html + or + num_and_sign;
        expression.assign(exp_batch);
        sbuffer = boost::regex_replace(sbuffer, expression, " ", boost::format_all);

        //--------------------------------------------------
        //      한 문자로 된 단어를 공백으로 치환
        string single_letter = " [a-zA-Z] ";
        expression.assign(single_letter);
        sbuffer = boost::regex_replace(sbuffer, expression, " ", boost::format_all);

        //--------------------------------------------------
        //      영어와 한글 불용어를 공백 치환
        FILE *fp2 = fopen("stop_words.txt", "r");       // 불용어 목록 파일 오픈
        char buffer2[BUFFER_SIZE] = { '0' };            // 파일 라인 버퍼
        fgets(buffer2, BUFFER_SIZE, fp2);       // 영어 불용어 목록 읽음
        string en_stop = buffer2;
        fgets(buffer2, BUFFER_SIZE, fp2);       // 한글 불용어 목록 읽음
        string kr_stop = buffer2;
        expression.assign(en_stop + or + kr_stop);
        sbuffer = boost::regex_replace(sbuffer, expression, " ", boost::format_all);
        fclose(fp2);

        //--------------------------------------------------
        //      연속 공백 제거
        string serial_space = " +";
        expression.assign(serial_space);
        sbuffer = boost::regex_replace(sbuffer, expression, " ", boost::format_all);

        strcpy(buffer, sbuffer.c_str());
}

void list_all_free(Category::linkedList *c_list)
{
        if(c_list->head == NULL)
                return;
        Category::node *p = c_list->head;
        Category::node *pr = (Category::node *)p->vright;

        while(p != NULL)
        {
                pr = (Category::node *)p->vright;
                while(pr != NULL)
                {
                        Keyword::list_free((Keyword::linkedList *)pr->vright);
                        pr = pr->down;
                }
                p = p->down;
        }

        Category::list_free(c_list);
}

//--------------------------
//      category_list.cpp
//--------------------------
namespace Category
{
        linkedList *init_list()
        {
                linkedList *r = NULL;
                r = new linkedList;
                        assert(NULL != r);
                r->head = NULL;
                r->size = 0;
                return r;
        }

        node *init_node(const char *str)
        {
                node *r = NULL;
                r = new node;
                        assert(NULL != r);
                strcpy(r->category, str);
                r->vright = NULL;
                r->down = NULL;
                return r;
        }

        BOOL list_insert(linkedList *L, char *str1, char *str2)
        {
                node *p = L->head;
                //------------------------------
                // 첫번째 카테고리 입력
                if(L->head == NULL)
                {
                        // 만약 리스트가 비었으면 첫 노드에 바로 입력
                        node *newNode = init_node(str1);
                        L->head = newNode;
                        p = L->head;
                }
                else
                {
                        // 리스트에서 동일한 카테고리까지 이동
                        while(p->down != NULL)
                        {
                                if(strcmp(p->category, str1) == 0)
                                {
                                        break;
                                }
                                p = p->down     ;
                        }

                        if(strcmp(p->category, str1) == 0)
                        {
                                /* 아무 일도 하지 않음 */;
                        }
                        else
                        {
                                node *newNode = init_node(str1);
                                p->down = newNode;
                                p = p->down;
                        }
                }

                //------------------------------
                // 두번째 카테고리 입력
                if(p->vright == NULL)
                {
                        node *newNode2 = init_node(str2);
                        p->vright = newNode2;
                        ++L->size;
                }
                else
                {
                        p = (node *)p->vright;
                        while(p->down != NULL)
                        {
                                if(strcmp(p->category, str2) == 0)
                                {
                                        break;
                                }
                                p = p->down     ;
                        }
                        if(strcmp(p->category, str2) != 0)
                        {       // 두번째 카테고리에서 동일한 카테고리가 없으면 새 카테고리 추가
                                node *newNode2 = init_node(str2);
                                p->down = newNode2;
                                ++L->size;
                        }
                }
                return TRUE;
        }

        void list_print(linkedList *L)
        {
                if(L->head == NULL)
                {
                        printf("list empty\n");
                        return;
                }
                node *p = L->head;
                node *rp = (node *)p->vright;

                while(p != NULL){
                        rp = (node *)p->vright;
                        printf("%s\n", p->category);
                        while(rp != NULL)
                        {
                                printf("\t%s\n", rp->category);
                                rp = rp->down;
                        }
                        p = p->down;
                }
        }

        void list_fprint(linkedList *L, FILE *fp)
        {
                node *p = L->head;
                node *rp = (node *)p->vright;

                while(p != NULL){
                        rp = (node *)p->vright;
                        fprintf(fp, "%s\n", p->category);
                        while(rp != NULL)
                        {
                                fprintf(fp, "\t%s\n", rp->category);
                                rp = rp->down;
                        }
                        p = p->down;
                }
        }

        void list_free(linkedList *L)
        {
                if(L->head == NULL)
                        return;
                node *p = L->head;
                node *rp = (node *)p->vright;
                node *tmp = NULL;

                while(L->head != NULL){
                        // 두번째 카테고리 메모리 해제
                        while(rp != NULL){
                                tmp = rp;
                                rp = rp->down;
                                free(tmp);
                        }
                        // 첫번째 카테고리 메모리 해제
                        p = L->head->down;
                        free(L->head);
                        L->head = p;
                }
        }
}

//--------------------------
//      keyword_list.cpp
//--------------------------
namespace Keyword
{
        linkedList *init_list()
        {
                linkedList *r = NULL;
                r = new linkedList;
                        assert(NULL != r);
                r->head = NULL;
                r->tail = NULL;
                r->keyword_size = 0;
                r->article_size = 1;
                return r;
        }

        node *init_node(const char *str, int priority)
        {
                node *r = NULL;
                r = new node;
                        assert(NULL != r);
                r->keyword = (char *)malloc(sizeof(char) * (strlen(str) + 1));
                strcpy(r->keyword, str);
                r->weight = priority;
                r->next = NULL;
                return r;
        }

        BOOL list_insert(linkedList *L, char *str, int priority)
        {
                // 리스트에 노드가 없으면 리스트에 새 노드를 추가하고 리턴
                if(L->head == NULL)
                {
                        node *newNode = init_node(str, priority);
                        L->head = newNode;
                        L->tail = newNode;
                        ++L->keyword_size;
                        return FALSE;
                }

                // 리스트를 탐색해가며 동일한 키워드가 존재하는지 보고 있으면 가중치 증가
                node *p = L->head;
                while(p->next != NULL)
                {
                        if(strcmp(p->keyword, str) == 0)
                        {
                                p->weight += priority;
                                return TRUE;
                        }
                        p = p->next;
                }

                // 리스트에 키워드가 없으면 리스트 끝에 새 노드 추가
                node *newNode = init_node(str, priority);
                p->next = newNode;
                L->tail = newNode;
                ++L->keyword_size;
                return FALSE;
        }

        void list_print(linkedList *L)
        {
                if(L->head == NULL)
                {
                        printf("list empty\n");
                        return;
                }
                node *p = L->head;

                while(1)
                {
                        if(p->next == NULL)
                        {
                                printf("%s(%d) : %d", p->keyword, p->weight, L->keyword_size);
                                break;
                        }
                        else
                        {
                                printf("%s(%d)->", p->keyword, p->weight);
                        }
                        p = p->next;
                }
        }

        int list_fprint(linkedList *L, FILE *fp)
        {
                node *p = L->head;

                while(p != NULL)
                {
                        fprintf(fp, "%s %d\n", p->keyword, p->weight);
                        p = p->next;
                }
                fprintf(fp, "\ntotal %d keywords\n", L->keyword_size);
                fprintf(fp, "total %d articles\n", L->article_size);
                return L->article_size;
        }

        void list_free(linkedList *L)
        {
                if(L->head == NULL)
                        return;
                node *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);
                }
        }
}




namespace Keyword
{
        void sort_node(linkedList *L)
        {
                if(L->head == NULL){
                        return;
                }
                node *gp_head = L->head;
                node *current, **ptr;
                int i, j,cnt;

                current = gp_head, cnt = 1;
                while(current->next != NULL){
                        cnt++;
                        current = current->next;
                }

                ptr = (node**)malloc(sizeof(node*) * cnt);
                for(i = 0, current = gp_head; i < cnt; i++, current = current->next) ptr[i] = current;

                for(i = 0; i < cnt; i++){
                        for(j = i+1; j < cnt; j++){
                                if(ptr[i]->weight < ptr[j]->weight){
                                        current = ptr[i];
                                        ptr[i] = ptr[j];
                                        ptr[j] = current;
                                }
                        }
                }

                for(gp_head = ptr[0], current = gp_head, i = 1; i < cnt; i++, current = current->next){
                        current->next = ptr[i];
                }
                current->next = NULL;
                free(ptr);
        }
}

//--------------------------
//      quicksort.cpp
//--------------------------
namespace Keyword
{
        node *quicksort_helper(node *r)
        {
                if(r == NULL)
                {
                        return NULL;
                }
                node *pivot = r;
                node *left = NULL;
                node *right = NULL;
                r = r->next;

                while(r != NULL)
                {
                        node **which_side = NULL;
                        node *temp = NULL;

                        if(r->weight < pivot->weight)
                                which_side = &right;
                        else
                                which_side = &left;
                        temp = r;
                        r = r->next;
                        temp->next = *which_side;
                        *which_side = temp;
                }

                left = quicksort_helper(left);
                right = quicksort_helper(right);
                pivot->next = right;

                // 대량의 노드를 처리할 때 위 재귀함수에서 스택 오버플로우 7~800개 이하에서만 사용 가능
                if(left == NULL)
                {
                        r = pivot;
                }
                else
                {
                        r = left;
                        while(left->next != NULL)
                        {
                                left = left->next;
                        }
                        left->next = pivot;
                }
                return r;
        }

        linkedList *node_quicksort(linkedList *r)
        {
                node *head = quicksort_helper(r->head);
                r->head = head;
                return r;
        }
}