# 2024q1 Homework1 (lab0)
contributed by < `164253` >

### Reviewed by `96121503`
* q_insert_head 中提到，沒有檢查 `node` 及 `val` 是否為空和有檢查的情況，可以補上兩種情況計算速度的比較結果。

> 後來發現不檢查會造成錯誤的記憶體釋放，因此不用測試這種錯誤作法

## 開發環境

:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::

空間滿了所以沒裝雙系統 所以我是 windows10 的 WSL2

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-10210U CPU @ 1.60GHz
    CPU family:          6
    Model:               142
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            12
    BogoMIPS:            4224.00

## 實作指定佇列操作

目前本機 100 分， `git push` 後僅有 95 分，無法通過第 17 筆的常數複雜度測試

### q_new
配置一個 `list_head` ，如果沒有空間要繼續嘗試直到成功
接著用 `INIT_LIST_HEAD` 初始化並回傳 `list_head`

### q_free
用 `list_for_each_entry_safe` 走訪所有節點，由於要刪除遇到的節點，所以用 `safe` 版
將途經節點的字串及節點本身釋放掉 最後釋放 `head`

### q_insert_head
配置一個 `element_t` 並用 `strdup` 處理字串配置
原本跳過 `node` 和 `val` 記憶體配置失敗的情況，但會造成錯誤的釋放記憶體

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *node = malloc(sizeof(element_t));
    char *val = strdup(s);
-   if (!node || !val || !head) {
-       free(node);
-       free(val);
-       return false;
-   }
-   node->value = val;
-   list_add(&node->list, head);
-   return true;
    
+   bool flag = false;
+   if (head && node && val) {
+       node->value = val;
+       list_add(&node->list, head);
+       flag = true;
+   } else {
+       if (node)
+           free(node);
+       if (val)
+           free(val);
+   }
+   return flag;
}

若 `node, val, head` 中記憶體有問題，釋放掉已經配置的記憶體
> 此處沒有檢查 `node, val` 是否為 NULL ，雖然不影響函式結果，但之後需要實驗補上速度差異
> > 不檢查會造成錯誤的記憶體釋放，因此無須討論這種狀況

否則將 `val` 字串給 `node` ，並用 `list_add` 將 `node` 插入至 `head`

:::danger
改進你的漢語表達
:::

### q_insert_tail
原本我複製 `q_insert_head` 的內容並改掉 `list_add` ，但有許多重複程式碼
因此改為呼叫 `q_insert_head(head->prev, s)` 達成插入在最後一項的功能

bool q_insert_tail(struct list_head *head, char *s)
{
-   element_t *node = malloc(sizeof(element_t));
-   char *val = strdup(s);
-    if (!node || !val || !head) {
-        free(node);
-        free(val);
-        return false;
-    }
-    node->value = val;
-    list_add_tail(&node->list, head);
-    return true;
+    return q_insert_head(head->prev, s);
}

### q_remove_head
若 `list` 指向 NULL 或者是空的，終止並回傳 NULL
否則用 `list_first_entry` 找到第一個元素，並用 `list_del` 移除他
將他的 `value` 存至 `sp`

### q_remove_tail
和 `q_insert_tail` 一樣 可以簡單的用 `q_remove_head` 完成
但由於 `q_remove_head` 是刪除 `head` 的下一個元素 應該傳入 `head->prev->prev` 才對

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
-   return q_remove_head(head->prev, sp, bufsize);
+   return list_empty(head) ? NULL
+                           : q_remove_head(head->prev->prev, sp, bufsize);
}

### q_size
特別處理 `head` 指向 NULL 的情況
其餘用 `list_for_each` 走訪過所有節點，並記錄共有幾個元素即可

### q_delete_mid
原本是用快慢指標的技巧找到中間那項並刪除

:::warning
針對環狀且雙向的佇列，是否有更快的方法？
:::

考慮雙向環狀的條件可以發現，用兩個指標從頭和尾向對方移動，
只需要存取 $n$ 個節點就好，不需要快慢指標的 $\frac32n$個

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
-   struct list_head *slow = head, *fast = head;
-   while (fast->next != head->prev && fast->next->next != head->prev) {
-       slow = slow->next;
-       fast = fast->next->next;
-   }
-   list_del(slow);
-   q_release_element(list_entry(slow, element_t, list));
+   struct list_head *tail;
+   q_find_mid(head, head, tail);
+   list_del(head);
+   q_release_element(list_entry(head, element_t, list));
    return true;
}

由於 `q_sort` 採用 merge sort ，也需要尋找中間那項，獨立成函式 `q_find_mid`

### q_delete_dup
走訪除了第一個以外的節點
檢查上一個節點和現在的是否相同，重複就刪掉上一個，並記錄這個節點也是重複的
若上一個和現在不同但被記錄，也要將上一個刪除

由於和 `q_ascend` 與 `q_descend` 有許多重疊，使用另一個子函式一併實現

### q_swap
先將最後一項的 `next` 設為 NULL ，每遇到兩個節點就把他們的連結互換
由於 `head` 被留下來最後接回去，至少有一個 `next` 指針可以拿來更改
每修改一個指針，就會多出一個指向重複節點的指針，因此自由度始終是一，可以執行到底
最初實作時沒有注意到 `head` 和他後面那項會被交換，要存下來的是 `head->next`

後來直接用 `q_reverse(head, 2)` 取代

void q_swap(struct list_head *head)
{
    q_reverse(head, 2);
}

### q_reverse
走訪所有節點並交換 `prev, next`
用 `do while` 一直執行到遇到 `head`

### q_reverseK
可以重用 `q_reverse` 來實作，需要注意必須傳入環狀佇列，要將第 K 個跟第一個連起來

:::warning
TODO: 改進程式碼的重用程度。
:::

### q_ascend, q_descend
要求回傳一個非嚴格遞增或遞減的佇列，一種想法是用 monostack，但均攤需要 $O(2n)$
可以反過來做，如果下一個節點會破壞性質，就把他刪掉
為了重用程式碼 `q_descend` 可以選擇反轉後用 `q_ascend` 再反轉，並改成刪除左邊的節點
但需要 $O(3n)$

由於和 `qdelete_dup` 有許多重疊，使用另一個子函式一併實現，改進原本重用率低的問題

### q_merge
考量到要在 `q_sort` 中重用，我將 `q_merge_two` 獨立出來，整個 list 每兩項合併一次
若還有兩項以上重複進行，且會一直合併至只剩一個 list
但因為需要保留 `queue_contex_t` 的結構，結束函式後程式會自己回收
所以實際上不能把相鄰項直接移除，採用清空被合併的 list ，每次要合併時尋找非空的 list

許多同學實作上把所有 list 合併到第一個，假設總共 $n$ 個節點 $q$ 個 list
第一個 list 中有 $n-q+1$ 個節點，總共會需要 $q-1$ 次合併
比較則要 $\frac{(q-1)((n-q+1)+(n-1))}2=\frac{-q^2+(2n+2)q-(n+1)}2$
走訪 $n$ 個節點
比較次數最多發生在 $q=n+1+\sqrt{n(n+1)}$ ，但 $q$ 最多只能到 $n-1$
所以實際上最多比較次數會是 $\frac{(n-2)(n+1)}2$

而我的作法要 $q-1$ 次合併，走訪 $n^2$ 個節點，比較 $n\log_2n$ ，證明見 [2024-3-19 課程簡記](https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ?both#%E5%95%8F%E9%A1%8C%E4%B8%80-merge-sort-%E6%9C%80%E4%BD%B3%E6%9C%80%E5%B7%AE%E7%8B%80%E6%B3%81)

走訪節點的成本是固定的，但比較取決於資料型別，若是字串成本會很高

### q_sort
採用 merge sort ，將整個 list 切割開，並呼叫 `q_merge_two` 當作 n 個長度一的 list 合併
現在用 `q_delete_mid` 中尋找中點的做法，亦可用 `q_reverseK` ， K 設為 `q_size()+1>>1`