# 2020q3 Homework1 (lab0)
contributed by <`ngokchaoho`>

## 作業要求

[queue.c](https://github.com/sysprog21/lab0-c/blob/master/queue.c) 僅提供介面 ([interface](https://en.wikipedia.org/wiki/Interface-based_programming)) 但尚未有完整程式實作，需要由學員補完並逐步精進，包含以下:
* `q_new`: 建立新的「空」佇列;
* `q_free`: 釋放佇列所佔用的記憶體;
* `q_insert_head`: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
* `q_insert_tail`: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
* `q_remove_head`: 在佇列開頭 (head) 移去 (remove) 給定的元素。
* `q_size`: 計算佇列中的元素數量。
* `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
* ==`q_sort`==: 「[Linux 核心設計](http://wiki.csie.ncku.edu.tw/linux/schedule)」課程所新增，以==遞增順序==來排序鏈結串列的元素，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法;

## 系統環境
Distributor ID: Ubuntu
Description: Ubuntu 20.04.1 LTS
Release: 20.04
Codename: focal
我想藉寫這個作業學習使用 Vim，結果寫共筆的時候我發現沒法使用 Clipboard, 在vim底下使用`:version` 會顯示`-clipboard`, Google 以後發現是這個版本的 Vim 不支援 Clipboard的意思。

安裝vtm-gtk以後，就可以使用v鍵選取程式碼，再用`"+y`複製到系統Clipboard, 然後就可以在HackMD上面Ctrl+V了。

sudo apt-get install vtm-gtk

## 實作流程

#### `q_size`
題目要求q_size是$O(1)$, 所以在queue.t這個struct裡面增加size這個member

int q_size(queue_t *q)
{
    if (q == NULL || q->head == NULL)
        return 0;
    return q->size;
}

#### `q_new`
用 Pointer 檢查了 malloc 是否成功，這裡可以看到queue_t除了 head 和 size, 還有一個 tail 的 member，這是為了可以在$O(1)$ insert tail 而加的。

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

#### `q_free`
從 Head 數過去，一個一個釋放。

void q_free(queue_t *q)
{
    if (q == NULL)
        return;
    if (q->head != NULL) {
        list_ele_t *curr_ele = q->head;
        while (curr_ele != NULL) {
            free(curr_ele->value);
            list_ele_t *prev_ele = curr_ele;
            if (curr_ele->next != NULL) {
                curr_ele = curr_ele->next;
            } else {
                free(curr_ele);
                break;
            }
            free(prev_ele);
        }
    }

    free(q);
}

#### `q_insert_head`
因為要用到兩個malloc，均有可能失敗，所以要free兩次。當只有一個元素時，Head和Tail是指向同一記憶體的。

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    if (q == NULL)
        return false;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;
    newh->value = malloc(strlen(s) + 1);
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, strlen(s)+1);
    newh->next = q->head;
    q->head = newh;
    q->size += 1;
    if (q->size == 1)
        q->tail = q->head;
    return true;
}

#### `q_remove_head`

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->head == NULL)
        return false;
    if (sp != NULL) {
        strncat(sp, q->head->value, bufsize - 1);
    }
    list_ele_t *prev_head = q->head;
    q->head = q->head->next;
    free(prev_head->value);
    free(prev_head);
    q->size -= 1;
    return true;
}

#### `q_insert_tail`
為了可以在$O(1)$時間內完成，如上所述地在 queue_t 這個 struct 裡面加入了tail, 因此如果不是 empty queue 的話只要記得加 size 和 tail 要指向新的記憶體就可以了, 與 insert head 相同，malloc 有可能失敗，所以如果失敗要free兩次。當只有一個元素時，Head和Tail是指向同一記憶體的。這裡一開始使用了不安全的 strcpy, 因為 destination 的空間是由 malloc source 出來的，如果malloc成功，則不會有 overflow 的問題。

然而 git commit hook不允許strcpy，因此改用strncpy。

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

    list_ele_t *newt;
    newt = malloc(sizeof(list_ele_t));
    if (newt == NULL)
        return false;
    newt->value = malloc(strlen(s) + 1);
    if (newt->value == NULL) {
        free(newt);
        return false;
    }
    newt->next = NULL;
    strncpy(newt->value, s, strlen(s)+1);
    q->size += 1;
    if (q->size > 1) {
        q->tail->next = newt;
        q->tail = newt;
    } else {
        /*from empty queue*/
        q->head = newt;
        q->tail = newt;
    }
    return true;
}

#### `q_reverse`
依照註解提示所寫

void q_reverse(queue_t *q)
{
    if (q == NULL || q->head == NULL)
        return;
    list_ele_t *curr_ele = q->head;
    list_ele_t *prev_ele = NULL;
    while (curr_ele != q->tail) {
        list_ele_t *next_ele = curr_ele->next;
        curr_ele->next = prev_ele;
        prev_ele = curr_ele;
        curr_ele = next_ele;
    }
    curr_ele->next = prev_ele;
    list_ele_t *tmp = q->head;
    q->head = q->tail;
    q->tail = tmp;
}

#### `q_remove_head`

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->head == NULL)
        return false;
    if (sp != NULL) {
        strncat(sp, q->head->value, bufsize - 1);
    }
    list_ele_t *prev_head = q->head;
    q->head = q->head->next;
    free(prev_head->value);
    free(prev_head);
    q->size -= 1;
    return true;
}

#### `q_sort`

參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/), 試作了 linked list 的 selection sort，
因為時間複雜度是$O(N^2)$, 所以沒有通過TESTING trace trace-16-perf。預期可以通過改用merge sort解決。

因為不經修改地嵌入了strnatcmp，從網上討論區得知這是不能通過+++ TESTING trace trace-15-perf的其中一個原因，預期可透過解決strnatcmp。

void q_sort(queue_t *q)
{
    /* TODO: You need to write the code for this function */
    /* TODO: Remove the above comment when you are about to implement. */
    if (q == NULL || q->head == NULL || q->size == 1)
        return;
    list_ele_t *sorted_tail = q->tail;
    list_ele_t *unsorted_head = q->head;
    list_ele_t *prev = NULL;
    list_ele_t *curr = NULL;
    list_ele_t *minNode = NULL;
    list_ele_t *min_Prev = NULL;
    for (int i = q->size; i > 0; i--) {
        curr = unsorted_head;
        minNode = unsorted_head;
        prev = unsorted_head;
        min_Prev = unsorted_head;
        for (int j = 0; j < i; j++) {
            // printf("%s ",curr->value);
            // printf("%s ",minNode->value);
            // printf("%d\n",strnatcmp(curr->value,minNode->value));
            if (strnatcmp(curr->value, minNode->value) < 0) {
                minNode = curr;
                min_Prev = prev;
            }
            curr = curr->next;
            if (j != 0)
                prev = prev->next;
        }
        // printf("%s",minNode->value);
        sorted_tail->next = minNode;
        sorted_tail = sorted_tail->next;
        if (minNode == unsorted_head) {
            unsorted_head = unsorted_head->next;  // moved comparision windows
        } else {
            min_Prev->next = minNode->next;
        }
        sorted_tail->next = NULL;
        if (i == q->size)
            q->head = sorted_tail;
    }
    q->tail = sorted_tail;
}

至此能通過除了15，16，17（17有的時候能通過）以外的unit test。

改用遞迴版的 merge sort 之後，16和17都能通過了。

list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
    if (!l2)
        return l1;
    if (!l1)
        return l2;

    if (strnatcmp(l1->value, l2->value) < 0) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

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

    list_ele_t *fast = head->next;
    list_ele_t *slow = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;

    list_ele_t *l1 = merge_sort_list(head);
    list_ele_t *l2 = merge_sort_list(fast);

    return merge(l1, l2);
}
/*
 * Sort elements of queue in ascending order
 * No effect if q is NULL or empty. In addition, if q has only one
 * element, do nothing.
 */
void q_sort(queue_t *q)
{
    if (q == NULL || q->head == NULL || q->size == 1)
        return;
    q->head = merge_sort_list(q->head);
    list_ele_t *tmp = q->head;
    while (tmp->next != NULL)
        tmp = tmp->next;
    q->tail = tmp;
}

經查閲執行 traces 15，發現有segmentation error, 推測是因為用了遞迴，於是修改使用while loop

list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
    list_ele_t *temp = NULL;
    list_ele_t *head = NULL;
    while (l1 && l2) {
        if (strnatcmp(l1->value, l2->value) < 0) {
            if (temp == NULL) {
                temp = l1;
                head = l1;
                l1 = l1->next;
            } else {
                temp->next = l1;
                temp = l1;
                l1 = l1->next;
            }
        } else {
            if (temp == NULL) {
                temp = l2;
                head = l2;
                l2 = l2->next;
            } else {
                temp->next = l2;
                temp = l2;
                l2 = l2->next;
            }
        }
    }
    if (l1)
        temp->next = l1;
    if (l2)
        temp->next = l2;
    return head;
}

至此所有 unit test都能通過了。

nch@nch-desktop:~/lab0-c$ make test
scripts/driver.py -c
---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---	trace-01-ops	6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
---	trace-02-ops	6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
---	trace-03-ops	6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
---	trace-05-ops	5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
---	trace-06-string	6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
---	trace-07-robust	6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---	trace-08-robust	6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---	trace-09-robust	6/6
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
---	trace-10-malloc	6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---	trace-11-malloc	6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---	trace-12-malloc	6/6
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
---	trace-13-perf	6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
---	trace-14-perf	6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
---	trace-15-perf	6/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---	trace-16-perf	6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---	TOTAL		100/100