# Facebookc Homework1

## Development Detail

### queue.h
* **q_struct**
* **head** -> the start of the linked list
* **tail** -> use for making $O(1)$ time in insert_tail

typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    int size;
} queue_t;

### queue.c

* **q_new**
* create a new queue
* initialize the queue

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

* **q_free**
* free the string first then free the node

void q_free(queue_t *q)
{
    if (q != NULL) {
        while (q->head != NULL) {
            list_ele_t *tmp = q->head->next;
            free(q->head->value);
            free(q->head);
            q->head = tmp;
        }
        free(q);
    }
}

* **q_insert_head**
* Three checking gate to prevent acting on NULL ,empty and lack of memory
* Contents a special case for the insertion when th queue is empty

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (newh == NULL) {
        free(newh);
        return false;
    }
    char *tmp = malloc(strlen(s) + 1);
    if (tmp == NULL) {
        free(tmp);
        free(newh);
        return false;
    }
    strncpy(tmp, s, strlen(s));
    tmp[strlen(s)] = '\0';
    if (q->head == NULL) // special case
        q->tail = newh;
    newh->value = tmp;
    newh->next = q->head;
    q->head = newh;
    q->size = q->size + 1;
    return true;
}

* **q_insert_tail**
* Three checking gate to prevent acting on NULL ,empty and lack of memory
* Contents a special case for the insertion when queue is empty

bool q_insert_tail(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *newt = malloc(sizeof(list_ele_t));
    if (newt == NULL) {
        free(newt);
        return false;
    }
    char *tmp = malloc(strlen(s) + 1);
    if (tmp == NULL) {
        free(tmp);
        free(newt);
        return false;
    }
    strncpy(tmp, s, strlen(s));
    tmp[strlen(s)] = '\0';
    newt->next = NULL;
    newt->value = tmp;
    if (q->tail == NULL) { // special case
        q->tail = newt;
        q->head = newt;
        return true;
    }
    q->tail->next = newt;
    q->tail = newt;
    q->size = q->size + 1;
    return true;
}

* **q_remove_head**
* A checking gate for NULL and empty queue
* A checking gate for NULL sp
* free the string first then the node

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->head == NULL)
        return false;
    if (sp != NULL) {
        strncpy(sp, q->head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_ele_t *tmp = q->head->next;
    free(q->head->value);
    free(q->head);
    q->head = tmp;
    q->size = q->size - 1;
    return true;
}

* **q_size**
* Operate in $O(1)$ time
* A checking gate for NULL and empty queue

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

* **q_reverse**
* First check if the queue has at least 2 elements
* Change the direction between each elements
* Break the loop if reach the end (NULL)

void q_reverse(queue_t *q)
{
    if (q != NULL && q->head != NULL && q->head->next != NULL) {
        q->tail = q->head;
        list_ele_t *tmp = q->head->next;
        list_ele_t *tmp2 = NULL;
        q->head->next = NULL;
        while (tmp != NULL) {
            tmp2 = tmp->next;
            tmp->next = q->head;
            q->head = tmp;
            tmp = tmp2;
        }
    }
}

* **q_sort**
* Add three function to complete the Task

void q_sort(queue_t *q)
{
    if (q == NULL || q->head == NULL || q->head->next == NULL)
        return;
    q->head = merge_split(q->head, q->size);
    q->tail = merge_find(q->size, q->head);
}

* **merge**
* The merging process
* **q1** and **q2** represents two linked list
* Can merge two linked list with diffrent size
* Return a **merged** linked list
* First if_else determine the head of **merged** linked list

list_ele_t *merge(list_ele_t *q1, list_ele_t *q2)
{
    list_ele_t *leads = NULL, *root;
    if (strcmp(q1->value, q2->value) < 0) {
        leads = q1;
        q1 = q1->next;
    } else {
        leads = q2;
        q2 = q2->next;
    }
    root = leads;
    while (q1 != NULL && q2 != NULL) {
        if (strcmp(q1->value, q2->value) < 0) {
            leads->next = q1;
            q1 = q1->next;
        } else {
            leads->next = q2;
            q2 = q2->next;
        }
        leads = leads->next;
    }
    if (q1 == NULL)
        leads->next = q2;
    else
        leads->next = q1;
    return root;
}

* **merge_find**
* Find the node in specific position

list_ele_t *merge_find(int a, list_ele_t *root)
{
    while (a > 1) {
        root = root->next;
        a = a - 1;
    }
    return root;
}

* **merge_split**
* First split the linked list to two linkend list
* The tail points to the NULL
* Do the merge-sort to the two linked list
* Recursively , return root if it has only ine elements
* Finally merge the two linked list to one
* Return the **merged-sorted** linked list

list_ele_t *merge_split(list_ele_t *root, int size)
{
    if (size / 2 > 0) {
        list_ele_t *tmp = merge_find(size / 2, root);
        list_ele_t *q2 = tmp->next;
        tmp->next = NULL;
        root = merge_split(root, size / 2);
        q2 = merge_split(q2, size - size / 2);
        return merge(root, q2);
    } else {
        root->next = NULL;
        return root;
    }
}