# 2020q3 Homework1 (lab0)
contributed by < `zzzxxx0001` >
## 開發環境

$ uname -a
Linux itlab-right 5.4.0-47-generic #51~18.04.1-Ubuntu SMP Sat Sep 5 14:35:50 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
Copyright (C) 2017 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.

## 作業要求
* 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: 以遞增順序來排序鏈結串列的元素

## 開發過程
* **queue.h**
* 根據題目q_insert_tail所需，達到時間複雜度$O(1)$的目標，必須新增tail指標，提供Queue快速尋訪。
* 為快速計算Queue中的node數量，達到時間複雜度$O(1)$的目標，加入`int size`，每成功新增一個節點size加1。

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

* **q_new()**
* 透過`malloc`分配記憶體空間給Queue，在初始化之前先確認是否成功分配，以免造成空指標的操作。

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

* **q_free**
* 操作前先確認Queue是否存在，以免造成後續執行錯誤。
* 透過`*temp`指標指向欲刪除的head node。
* 透過while迴圈訪問所有節點，將節點空間依序釋放。

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

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

* **q_insert_head**
* 操作前先確認Queue是否存在，以免造成後續執行錯誤。
* 透過`list_ele_t *newh = malloc(sizeof(list_ele_t))`分配記憶體給新的節點，並確認是否成功分配，以免後續操作錯誤。
* 透過`newh->value = malloc(sizeof(char)*( strlen(s)+1 ))`分配適當的記憶體空間，提供給`newh->value`複製`char *s`內容，預留多一格的長度==strlen(s)+1==置放字串終結字元('\0')。
* 透過`strncpy(newh->value, s, strlen(s)+1)`將字串含終結碼一併複製到`newh->value`，因此複製長度為**strlen(s)+1**
* insert head分為兩個case：
* 如果q->head不存在，則將head與tail指向newh
* 如果q->head已存在，newh成為新的head，並將newh->next指向原本的head

bool q_insert_head(queue_t *q, char *s)
{
    if(!q) return false ;
    
    list_ele_t *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 ;
    }

    q->size ++ ;
    strncpy(newh->value, s, strlen(s)+1);


    if(!q->head)
    {
        newh->next = NULL ;
        q->head = q->tail = newh ;
        return true ;
    }

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

    return true;
}

* **q_insert_tail**
* 操作前先確認Queue是否存在，以免造成後續執行錯誤。
* 透過`list_ele_t *newh = malloc(sizeof(list_ele_t))`分配記憶體給新的節點，並確認是否成功分配，以免後續操作錯誤。
* 透過`newh->value = malloc(sizeof(char)*( strlen(s)+1 ))`分配適當的記憶體空間，提供給`newh->value`複製`char *s`內容，預留多一格的長度==strlen(s)+1==置放字串終結字元('\0')。
* insert tail分為兩個case：
* 如果q->head不存在，則將head與tail指向newh。
* 如果q->head已存在，則將tail->next指向newh，並將newh設為新的tail。

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

    list_ele_t *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 ;
    }

    q->size ++ ;
    strncpy(newh->value, s, strlen(s)+1) ;
    newh->next = NULL ;

    if(!q->head)
    {
        q->head = q->tail = newh ;
    }
    else
    {
        q->tail->next = newh ;
        q->tail = newh ;
    }
    return true;
}

* **q_remove_head**
* 操作前先確認Queue或Queue->head是否存在，以免造成後續執行錯誤。
* 依循題目提示，將條件寫入if條件式。
>If sp is non-NULL and an element is removed, copy the removed string to *sp (up to a maximum of bufsize-1 characters, plus a null terminator.)
* 透過`memset(sp, '\0', bufsize)`將陣列`sp`初始化。
* 因最後一格空間需保留給字串終結字元，因此實際複製字串長度為==bufsize-1==。
* 透過`rm_node`指標指向欲刪除的head node。
* head則由head->next進行取代。
* 將rm_node內所有資料記憶體釋放後，再將rm_node記憶體空間釋放。

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if(q && q->head)
    {
        if(strlen(q->head->value) >= bufsize && !sp)   return false ;
        list_ele_t *rm_node = q->head ;

        memset(sp, '\0', bufsize) ;
        strncpy(sp, rm_node->value, bufsize-1) ;

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

        if(q->size == 0)        q->tail = NULL ;

        return true ;
    }
    return false ;
}

* **q_size**
* 操作前先確認Queue是否存在，如果不存在則回傳0。
* 直接將`q->size`回傳，代表Queue中的節點數量。

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

* **q_reverse**
* 此部分參考[quiz_1](https://hackmd.io/@sysprog/sysprog2020-quiz1)中link list的`node_t *reverse(node_t *head)`。
* 操作前先確認Queue狀態，如果Queue不存在、Queue->head不存在或是Queue->size小於2都無法操作reverse，則直接return。
* reverse操作概念已在[quiz1_reverse](https://hackmd.io/y5g1z2z5Ta2Ru8itT39yPQ?view#reverse)中解釋。
* 預先將`q->tail`指向`q->head`，操作完reverse後，再將`q->head`指向目前的`head(cursor)`。

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

    list_ele_t *cursor = NULL ;
    q->tail = q->head ;
    while(q->head)
    {
        list_ele_t *next = q->head->next ;
        q->head->next = cursor ;
        cursor = q->head ;
        q->head = next ;
    }
    q->head = cursor ;
}

* **q_sort**
* Sort方始採merge sort，可達到時間複雜度$O(nlogn)$的理想目標。
* 演算法部分參考[Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)。

list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
    list_ele_t *head = NULL;
    list_ele_t **temp = &head;

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

    if (l1)
        *temp = l1;
    if (l2)
        *temp = l2;

    return head;
}

list_ele_t *mergeSortList(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 = mergeSortList(head);
    list_ele_t *l2 = mergeSortList(fast);

    return merge(l1, l2);
}

void q_sort(queue_t *q)
{
    if (!q || q->size == 1)
        return;

    q->head = mergeSortList(q->head);
    while (q->tail)
        q->tail = q->tail->next;
}

## 程式測試
* 透過 `make test` 驗證程式執行狀態是否合乎題意。
* 透過 `clang-format -i <filename>` 修正程式碼編排方式。

$ make test
  CC    qtest.o
  CC    report.o
  CC    console.o
  CC    harness.o
  CC    queue.o
  CC    random.o
  CC    dudect/constant.o
  CC    dudect/fixture.o
  CC    dudect/ttest.o
  LD    qtest
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