# 2021q1 Homework1 (lab0)

contributed by < `kksweet8845` >

## Environment

$ uname-a
Darwin Nobers-MacBook-Pro.local 20.3.0 Darwin Kernel Version 20.3.0: Thu Jan 21 00:07:06 PST 2021; root:xnu-7195.81.3~1/RELEASE_X86_64 x86_64

$ gcc --version | head -1
Apple clang version 12.0.0 (clang-1200.0.32.29)

## Implementation

### q_new()
- Check if malloc return NULL. Otherwise, initialize the queue with NULL and '0'.

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* TODO: What if malloc returned NULL? */
    if(q == NULL)
        return NULL;
    else {
        q->head = NULL;
        q->tail = NULL;
        q->len = 0;
    }
    return q;
}

### q_free()
- Check if queue is `NULL`
- Free each node inside queue and need to store the address of `cur->next` in advance. If I don't take this action, it will happen segment fault by access a NULL adress of `next`.

void q_free(queue_t *q)
{
    /* Free queue structure */
    if(q == NULL)
        return;
    list_ele_t *cur, *temp;
    for(cur = q->head; cur != NULL; cur = temp){
        temp = cur->next;
        if(cur ->value != NULL)
            free(cur->value);
        if(cur != NULL)
            free(cur);
    }
    free(q);
}

### q_insert_head()
- Check if queue is `NULL`
- Create a `list_ele_t` type object and check if malloc return NULL
- Perform the insertion operation

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    if(q == NULL)
        return false;
    newh = list_new(s);
    if(newh == NULL)
        return false;
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->next = q->head;
    q->head = newh;
    q->len += 1;
    if(q->len == 1){
        q->tail = newh;
    }
    return true;
}

### q_insert_tail()
- Same precaution as `q_insert_head`
- There is different situation when perform insertion with size is 0.

bool q_insert_tail(queue_t *q, char *s)
{
    list_ele_t *newh;
    if(q == NULL)
        return false;
    newh = list_new(s);
    if(newh == NULL)
        return false;
    if(q->len != 0)
        q->tail->next = newh;
    q->tail = newh;
    q->len += 1;
    if(q->len == 1){
        q->head = newh;
    }
    return true;
}

## q_remove_head()
- Check if queue is NULL

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if(q == NULL || (q->head == NULL && q->tail == NULL) || q->len == 0 || sp == NULL){
        return false;
    }
    list_ele_t *cur = q->head;
    q->head = q->head->next;
    q->len -= 1;

    memset(sp, '\0', (bufsize) * sizeof(char));
    strncpy(sp, cur->value, bufsize-1);
    if(cur->value != NULL){
        free(cur->value);
    }
    if(cur != NULL){
        free(cur);
    }
    if(q->len == 0){
        q->tail = NULL;
        q->head = NULL;
    }

    return true;
}

## q_reverse()
- Perform the insertion to head.

void q_reverse(queue_t *q)
{
    if(q == NULL)
        return;
    list_ele_t *cur, *pre, *tmp_head = NULL;
    q->tail = q->head;
    for(cur = q->head; cur != NULL; cur = q->head){
        pre = tmp_head;
        tmp_head = cur;
        q->head = cur->next;
        cur->next = pre;
    }
    q->head = tmp_head;
}

## q_sort()
- Implement Merge sort
- It occurred worst case O(n^2) with a Descending order link list with quick sort.

list_ele_t* _m_sort(list_ele_t* list){

    if(list == NULL || list->next == NULL){
        return list;
    }

    list_ele_t* slow, *fast;

    fast = list;
    slow = list;
    for(slow=list;slow!= NULL;slow=slow->next){
        if(fast->next == NULL || fast->next->next == NULL)
            break;
        fast=fast->next->next;
    }

    fast = slow->next;
    slow->next = NULL;


    list_ele_t* l1 = _m_sort(list);
    list_ele_t* l2 = _m_sort(fast);


    list_ele_t* h = NULL, *cur = NULL;


    while(l1 != NULL && l2 != NULL){
        if(strcmp(l1->value, l2->value) < 0){
            if(h == NULL)
                cur = h = l1;
            else{
                cur->next = l1;
                cur = cur->next;
            }
            l1 = l1->next;
        }else{
            if(h == NULL)
                cur = h = l2;
            else{
                cur->next = l2;
                cur = cur->next;
            }
            l2 = l2->next;
        }
        cur->next = NULL;
    }

    if(l2 != NULL){
        while(l2){
            cur->next = l2;
            cur = cur->next;
            l2 = l2->next;
        }
    }

    if(l1 != NULL){
        while(l1){
            cur->next = l1;
            cur = cur->next;
            l1 = l1->next;
        }
    }
    cur->next = NULL;

    return h;

}


/*
 * 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->len <= 1)
        return;
    // _q_sort(&(q->head));
    q->head = _m_sort(q->head);
    while (q->tail->next) {
        q->tail = q->tail->next;
    }

}