#include <stdbool.h>
#include <stddef.h>

/* element struct in queue */
typedef struct list_ele {
    char *value;
    struct list_ele *next;
} list_ele_t;

typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    int size; // use the above two variable to record the size of the queue to avoid traversal
} queue_t;

/* Create empty queue. */
queue_t *queue_new(void);

/* Free ALL storage used by queue. */
void queue_free(queue_t *q);

/* Attempt to insert element at head of queue. */
bool queue_insert_head(queue_t *q, const char *s);

/* Attempt to insert element at tail of queue. */
bool queue_insert_tail(queue_t *q, const char *s);

/* Attempt to remove element from head of queue. */
bool queue_remove_head(queue_t *q, char *sp, size_t bufsize);

/* Return number of elements in queue. */
size_t queue_size(queue_t *q);

/* Reverse elements in queue */
void queue_reverse(queue_t *q);

/**
 * @brief Allocates a new queue
 * @return The new queue, or NULL if memory allocation failed
 */
queue_t *queue_new(void) {
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (q == NULL) {
        return NULL;
    } else {
        q->head = NULL;
        q->tail = NULL;
        q->size = 0;
        return q;
    }
}

/**
 * @brief Frees all memory used by a queue
 * @param[in] q The queue to free
 */
void queue_free(queue_t *q) {
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    if (q == NULL) {
        return;
    } else {
        list_ele_t *tmp;
        while (q->head != NULL) {
            tmp = q->head;
            q->head = q->head->next;
            free(tmp->value); // free element's value
            free(tmp) // free element itself
        }
    }
    free(q); // free queue
}

/**
 * @brief Attempts to insert an element at head of a queue
 *
 * This function explicitly allocates space to create a copy of `s`.
 * The inserted element points to a copy of `s`, instead of `s` itself.
 *
 * @param[in] q The queue to insert into
 * @param[in] s String to be copied and inserted into the queue
 *
 * @return true if insertion was successful
 * @return false if q is NULL, or memory allocation failed
 */
bool queue_insert_head(queue_t *q, const char *s) {
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    if (q == NULL) {
        return false;
    }
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL) {
        return false;
    } else {
        newh->value = malloc(sizeof(char) * (strlen(s) + 1));
        if (newh->value == NULL) {
            free(newh); // must free the space if malloc failed
            return false;
        } else {
            strcpy(newh->value, s);
            newh->next = q->head;
            q->head = newh;

            if (q->tail == NULL) {
                q->tail = newh;
            }
            ++q->size;
            return true;
        }
    }
}

/**
 * @brief Attempts to insert an element at tail of a queue
 *
 * This function explicitly allocates space to create a copy of `s`.
 * The inserted element points to a copy of `s`, instead of `s` itself.
 *
 * @param[in] q The queue to insert into
 * @param[in] s String to be copied and inserted into the queue
 *
 * @return true if insertion was successful
 * @return false if q is NULL, or memory allocation failed
 */
bool queue_insert_tail(queue_t *q, const char *s) {
    /* You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */
    list_ele_t *newt;
    /* What should you do if the q is NULL? */
    if (q == NULL) {
        return false;
    }
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newt = malloc(sizeof(list_ele_t));
    if (newt == NULL) {
        return false;
    } else {
        newt->value = malloc(sizeof(char) * (strlen(s) + 1));
        if (newt->value == NULL) {
            free(newt);
            return false;
        } else {
            strcpy(newt->value, s);
            newt->next = NULL;

            if (q->tail != NULL) {
                q->tail->next = newt;
                q->tail = newt;
            } else {
                q->head = newt;
                q->tail = newt;
            }
            ++q->size;
            return true;
        }
    }
}

/**
 * @brief Attempts to remove an element from head of a queue
 *
 * If removal succeeds, this function frees all memory used by the
 * removed list element and its string value before returning.
 *
 * If removal succeeds and `buf` is non-NULL, this function copies up to
 * `bufsize - 1` characters from the removed string into `buf`, and writes
 * a null terminator '\0' after the copied string.
 *
 * @param[in]  q       The queue to remove from
 * @param[out] buf     Output buffer to write a string value into
 * @param[in]  bufsize Size of the buffer `buf` points to
 *
 * @return true if removal succeeded
 * @return false if q is NULL or empty
 */
bool queue_remove_head(queue_t *q, char *buf, size_t bufsize) {
    if (q == NULL) {
        return false;
    }
    if (q->head == NULL) {
        return false;
    } else {
        list_ele_t *temp = q->head;
        q->head = q->head->next;
        if (buf != NULL) {
            strncpy(buf, temp->value, bufsize - 1);
            buf[bufsize - 1] = '\0';
        }
        free(temp->value);
        free(temp);
        --q->size;
    }
    return true;
}

/**
 * @brief Returns the number of elements in a queue
 *
 * This function runs in O(1) time.
 *
 * @param[in] q The queue to examine
 *
 * @return the number of elements in the queue, or
 *         0 if q is NULL or empty
 */
size_t queue_size(queue_t *q) {
    /* You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    if (q == NULL) {
        return 0;
    } else {
        return q->size;
    }
}

/**
 * @brief Reverse the elements in a queue
 *
 * This function does not allocate or free any list elements, i.e. it does
 * not call malloc or free, including inside helper functions. Instead, it
 * rearranges the existing elements of the queue.
 *
 * @param[in] q The queue to reverse
 */
void queue_reverse(queue_t *q) {
    /* You need to write the code for this function */
    if (q == NULL || q->head == NULL) {
        return;
    } else {
        list_ele_t *oldHead = q->head;
        list_ele_t *oldTail = q->tail;

        list_ele_t *temp = q->head;
        list_ele_t *prev = NULL;
        list_ele_t *next = NULL;
        while (temp != NULL) {
            next = temp->next;
            temp->next = prev;
            prev = temp;
            temp = next;
        }
        q->head = oldTail;
        q->tail = oldHead;
    }
}