# 2020q3 Homework1 (lab0)
contributed by < `chi-ming5566` >

## 開發環境

$ uname -a
Linux yx 5.3.0-40-generic #32-Ubuntu SMP Fri Jan 31 20:24:34 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 9.2.1-9ubuntu2) 9.2.1 20191008
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

## 作業要求
在 queue.c/queue.h 中完成以下實作

*新增 int size 這個新成員到 struct queue_t
*更改q_free、q_insert_head、q_insert_tail、q_remove_head、q_size、q_reverse、q_sort等函式

## 實作流程

### queue.h
* 新增int size 這個新成員到 struct queue_t

typedef struct {
    list_ele_t *head; 
    list_ele_t *tail;
    int size;         
} queue_t;

### queue.c
* q_free
*增加 變數 tmp 作為釋放用的節點

void q_free(queue_t *q)
{
    if (!q)
        return;

    list_ele_t *tmp = q->head;
    while (q->head) {
        q->head = q->head->next;
        tmp->next = NULL;
        free(tmp->value);
        free(tmp);
        tmp = q->head;
    }

    free(q);
}

* q_insert_head
*將新變數 list_ele_t 放入 queue 的前端
*先判斷傳入的 q 是否為 NULL，是為了預防在分配memory後才發現 q 為 NULL，造成 memory leak
*在分配memory給新的變數後，判斷是否分配成功，若失敗，則將之前所分配的 newh 清除
*以 <string.h> 的 strncpy 複製 s，放入新變數的值
*使用 memset 將 newh->value 歸零

bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;

    list_ele_t *newh;

    newh = malloc(sizeof(list_ele_t));
    if (!newh) {
        return false;
    }
    newh->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (!newh->value) {
        free(newh);
        return false;
    }
    memset(newh->value, '\0', strlen(s) + 1);
    strncpy(newh->value, s, strlen(s));

    newh->next = q->head;
    q->head = newh;

    if (!q->rail) {
        q->tail = q->head;
    } else {
        while (q->tail->next) {
            q->tail = q->tail->next;
        }
    }
    q->size += 1;
    return true;
}

* q_insert_tail
*將新元素 (list_ele_t) 放入 queue 的尾端

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q)
        return false;

    list_ele_t *newt;
    newt = malloc(sizeof(list_ele_t));
    if (!newt)
        return false;

    newt->value = malloc(sizeof(char) * strlen(s) + 1);
    if (!newt->value) {
        free(newt);
        return false;
    }
    memset(newt->value, '\0', strlen(s) + 1);
    strncpy(newt->value, s, strlen(s));
    newt->next = NULL;

    if (!q->tail) {
        q->tail = q->head = newt;
    } else {
        q->tail->next = newt;
        q->tail = newt;
    }

    q->size += 1;
    return true;
}

* q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->head) {
        return false;
    }
    if (sp) {
        size_t realbufsize = (bufsize > strlen(q->head->value))
                                 ? strlen(q->head->value)
                                 : bufsize - 1;
        memset(sp, '\0', realbufsize + 1);
        strncpy(sp, q->head->value, realbufsize);
    }

    list_ele_t *tmp;

    tmp = q->head;
    q->head = q->head->next;
    tmp->next = NULL;
    free(tmp->value);
    free(tmp);


    q->size -= 1;
    return true;
}

* q_size

int q_size(queue_t *q)
{
    return !q ? 0 : q->size;
}

* q_reverse

void q_reverse(queue_t *q)
{
    if (!q || q->size < 2) {
        return;
    }


    list_ele_t *tmp;
    tmp = q->head->next;
    q->tail->next = q->head;

    while (tmp != q->tail) {
        tmp = tmp->next;
        q->head->next->next = q->tail->next;
        q->tail->next = q->head->next;
        q->head->next = tmp;
    }
    q->tail = q->head;
    q->head = q->head->next;
    q->tail->next = NULL;
}

* q_sort
*使用 Merge sort 排序

void merge(list_ele_t **head)
{
    if (!(*head) || !((*head)->next))
        return;

    list_ele_t *l1 = (*head)->next;
    list_ele_t *l2 = *head;

    while (l1 && l1->next) {
        l2 = l2->next;
        l1 = l1->next->next;
    }
    l1 = l2->next;
    l2->next = NULL;
    l2 = *head;

    merge(&l2);
    merge(&l1);

    *head = NULL;

    list_ele_t **tmp = head;

    while (l1 && l2) {
        if (strcmp(l1->value, l2->value) < 0) {
            *tmp = l1;
            l1 = l1->next;
        } else {
            *tmp = l2;
            l2 = l2->next;
        }
        tmp = &((*tmp)->next);
    }
    *tmp = l1 ? l1 : l2;
}

*q_sort

void q_sort(queue_t *q)
{
    if (!q || q->head == q->tail) {
        return;
    }

    merge(&q->head);

    while (q->tail->next) {
        q->tail = q->tail->next;
    }
}