# 2021q1 Homework1 (lab0)
contributed by < [richard880523](https://github.com/richard880523) >

###### tags: `linux2021`

## 環境設置
安裝必要開發工具

$ sudo apt install build-essential git-core valgrind
$ sudo apt install cppcheck clang-format aspell colordiff valgrind

`cppcheck --version` 檢查 cppcheck 版本，若小於 1.90，則需要

$ sudo snap install cppcheck
$ export PATH=/snap/bin:$PATH

至於 `$PATH` 環境變數的更新，也可寫在 ~/.bashrc 檔案最底端，下次重開終端機就生效;
或是 `$ source ~/.bashrc` 也可

* 到 Home 的上一層找到 bin 目錄，執行 `vim ~/.bashrc` ，將 `export EDITOR=vim`和`export PATH=/snap/bin:$PATH` 寫在檔案底端

## 作業要求
實作並完善 `qtest` 中的函式功能，包含
* ==`new`== : 建立新的佇列
* ==`free`== : 釋放佇列所分配的記憶體空間
* ==`insert head / tail`== : 新增節點至佇列的開頭/結尾
* ==`remove head`== : 移除佇列開頭的元素
* ==`size`== : 計算佇列中的元素數量
* ==`reverse`== : 反轉佇列
* ==`sort`== : 以遞增順序來排序鏈結串列的元素

**queue structure**

typedef struct ELE {
    /* Pointer to array holding string.
     * This array needs to be explicitly allocated and freed
     */
    char *value;
    struct ELE *next;
} list_ele_t;

## 實作過程
修改 `queue.h`

In `struct queue_t`
由於作業要求 `insert` ,`remove` 以及查詢 `queue size` 之時間須在 $O(1)$ 內，因此
* 新增 `list_ele_t tail` : 指向queue的尾巴
* 新增 `int value` : 紀錄queue所鏈結的節點數

修改 `queue.c`

1. q_new():

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

2. q_free():

void q_free(queue_t *q)
{
    /* TODO: How about freeing the list elements and the strings? */
    if (!q) {
        return;
    }
    while (q->head) {
        list_ele_t *curr = q->head;
        q->head = q->head->next;
        /* Free queue structure */
        free(curr->value);
        free(curr);
    }
    free(q);
}

3. q_insert_head()：
- 首先檢查 q 是否為 `NULL` ，接著新增元素 `newh`
- 除了 malloc 一塊記憶體空間給 `list_ele_t` 的結構外，還需分配 `newh->value` 所需要的記憶體大小
==ques : difference between `strcpy` and `memcpy`?==

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);
    strncpy(newh->value, s, strlen(newh->value));
    
    newh->next = q->head;
    q->head = newh;
    if(!q->tail){
        q->tail = newh;
        q->tail->next = NULL; // can be removed!
    }
    q->size = q->size+1;
    return true;
}

4. q_insert_tail():

bool q_insert_tail(queue_t *q, char *s)
{
    /* Remember: It should operate in O(1) time */
    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));
    strncpy(newt->value, s, strlen(newt->value));
    
    newt->next = NULL;
    if (!q->head && !q->tail) {
        q->head = q->tail = newt;
    } else {
        q->tail->next = newt;
    }
    q->tail = newt;
    q->size = q->size + 1;
    
    return true;
}

## 測試方法
- 執行 `make check` 將 [trace/trace-eg.cmd](https://github.com/richard880523/lab0-c/blob/master/traces/trace-eg.cmd) 的檔案內容指派給 `qtest` ，並執行一連串的 queue 操作

- 執行 `./qtest` 並在 `cmd>` 輸入 `help` ，會條列出所有`queue commands`，可透過自行輸入指令得知 `queue` 的操作是否正常運行

---
在 git commit 之前，為達到一致的 programming style，可透過[clang-format](https://clang.llvm.org/docs/ClangFormat.html)來檢查提交出去的文件是否符合格式:

clang-format -i [file name]

## 參考連結
[Merge Sort for linked-list](https://www.geeksforgeeks.org/merge-sort-for-linked-list/)