# 2019 q3 Homework1 (lab0)
## 作業要求
- ```q_new```: 建立新的「空」佇列
- ```q_free```: 釋放佇列所佔用的記憶體
- ```q_insert_head```: 在佇列開頭加入給定的新元素
- ```q_insert_tail```: 在佇列尾端加入給定的新元素
- ```q_remove_head```: 在佇列開頭移除給定的元素
- ```q_size```: 計算佇列中的元素數量
- ```q_reverse```: 以反向順序重新排列鏈結串列
- ```q_sort```: 以遞增順序來排序鏈結串列的元素

## 實做

### queue.h
- #### queue_t
- 在```queue.h```中新增```list_ele_t *tail```用來加速函式```q_insert_tail()```
- 在```queue.h```中新增```int size```用來加速函式```q_size()```

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size;
} queue_t;

- #### IS_NULL_POINTER()
- 使用macro讓null pointer的檢查更為方便
- 為了避免在編譯結束後產生dangling else，所以多加了while迴圈

#define IS_NULL_POINTER(p) \
    do {                   \
        if (!p)            \
            return 0;      \
    } while (0);

### queue.c
- #### q_new()
- 宣告一個```queue```並用```IS_NULL_POINTER(q)```去檢查```malloc()```是否成功，若失敗直接回傳```false```
- 初始化```queue```中所有參數

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    IS_NULL_POINTER(q);
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

- #### q_free()
- 先檢查```q```是否存在，若不存在，直接回傳
- 跑迴圈，要注意```list_ele_t```中，除了本身要```free()```外，還有當中的```char *value```也要
- 最後也要記的```q```本身也要```free()```

void q_free(queue_t *q)
{
    if (!q) {
        return;
    }
    while (q->head) {
        list_ele_t *tmp;
        tmp = q->head;
        q->head = q->head->next;
        free(tmp->value);
        free(tmp);
    }
    free(q);
}

- #### q_insert_head()
- 要檢查```q```和```s```是否為null pointer，自己```malloc()```的指標```newh```和```cpy```也要
- 注意如果```cpy```為null pointer，要記得把```newh```釋放掉
- ```cpy```的長度要設為目標字串長度+1，並在最後一格加上```\0```避免在之後使用字串函式時產生錯誤
- 在最後如果這個節點是第一個加入的節點，要把這個節點加入```q->tail```避免在搜索時候產生錯誤

    bool q_insert_head(queue_t *q, char *s)
{
    IS_NULL_POINTER(q);
    IS_NULL_POINTER(s);
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    IS_NULL_POINTER(newh);
    int len = strlen(s);
    char *cpy = malloc(sizeof(char) * len + 1);
    if (!cpy) {
        free(newh);
        return false;
    }
    for (int i = 0; i < len; i++) {
        *(cpy + i) = *(s + i);
    }
    *(cpy + len) = '\0';
    newh->value = cpy;
    newh->next = q->head;
    q->head = newh;
    if (!q->tail) {
        q->tail = newh;
    }
    q->size += 1;
    return true;
}

- #### q_insert_tail()
- 這邊要注意如果```q```中還沒有任何節點，要把這個節點設入```q->head```中，避免程式錯誤

bool q_insert_tail(queue_t *q, char *s)
{
    IS_NULL_POINTER(q);
    IS_NULL_POINTER(s);
    list_ele_t *newt = malloc(sizeof(list_ele_t));
    IS_NULL_POINTER(newt);
    int len = strlen(s);
    char *cpy = malloc(sizeof(char) * len + 1);
    if (!cpy) {
        free(newt);
        return false;
    }
    for (int i = 0; i < len; i++) {
        *(cpy + i) = *(s + i);
    }
    *(cpy + len) = '\0';
    newt->value = cpy;
    newt->next = NULL;
    if (q->tail) {  // if tail is not null
        q->tail->next = newt;
        q->tail = newt;
        q->size += 1;
        return true;
    } else {
        q->head = newt;
        q->tail = newt;
        q->size += 1;
        return true;
    }
    return false;
}

- #### q_remove_head()
- 要注意如果原節點的```value```字串長度超過```bursize```要截斷字串，並把最後一個字元設為```\0```

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    IS_NULL_POINTER(q);
    IS_NULL_POINTER(q->head);
    IS_NULL_POINTER(sp);
    int head_value_len = strlen(q->head->value);
    for (int i = 0; i < bufsize; i++) {
        if (i >= head_value_len) {
            *(sp + i) = '\0';
            break;
        }
        *(sp + i) = *((q->head->value) + i);
    }
    if (head_value_len >= bufsize) {
        *(sp + bufsize - 1) = '\0';
    }

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

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

- #### q_size()
- 因為有存```q->size```的值，所以直接回傳參數即可，以達到O(1)的速度

int q_size(queue_t *q)
{
    IS_NULL_POINTER(q);
    return q->size;
}

- #### q_reverse()

void q_reverse(queue_t *q)
{
    if (!q || q->head == NULL || q->size <= 1) {
        return;
    }
    list_ele_t *left = NULL, *right = q->head->next;
    q->tail = q->head;
    while (right != NULL) {
        q->head->next = left;
        left = q->head;
        q->head = right;
        right = right->next;
    }
    q->head->next = left;

- #### q_sort()
- ```merge_sort()```用來把節點拆開來，```merge()```用來排序把節點接回去

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

    q->head = merge_sort(q->head);
    return;
}

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

    list_ele_t *slow = head, *fast;
    for (fast = head->next; fast && fast->next; fast = fast->next->next) {
        slow = slow->next;
    }

    list_ele_t *mid = slow->next;
    slow->next = NULL;
    return merge(merge_sort(head), merge_sort(mid));
}

list_ele_t *merge(list_ele_t *left, list_ele_t *right)
{
    list_ele_t *head = NULL;
    for (list_ele_t **iter = &head; true; iter = &((*iter)->next)) {
        if (!left) {
            *iter = right;
            break;
        }
        if (!right) {
            *iter = left;
            break;
        }
        if (strcmp(left->value, right->value) < 0) {
            *iter = left;
            left = left->next;
        } else {
            *iter = right;
            right = right->next;
        }
    }

    return head;
}