#include <stdlib.h>
#include <stdio.h>
/*
written on 2018-5-29 23:31:47
some errors not fixed at func::clear
然后我就曲线救了一下国，clear2函数可以正常使用
这一段代码还有一些其他的错误，比如，在gdb进行调试的时候会出现SIGTRAP的问题，但是能正常运行
原因不明
*/

// 实现链队列，这里非循环队列
typedef int ElemType;
typedef struct node{
    ElemType data;
    struct node *next;
}node;
typedef struct{
    node *front;
    node *rear;
}LQueue;

void init(LQueue *q){
    // 初始化队列
    node *head = malloc(sizeof(node));  // head node
    if (!head) exit(1); // allocation failed
    head->data = 0;
    q->front = head;
    q->rear = head;
    q->rear->next = NULL;
}

void destory(LQueue *q){
    // 销毁队列, 自己实现的版本，不优雅，书上实现的方法在下面
    while (q->rear != q->front){
        node *temp = q->front;
        free(q->front);
        q->front = temp +1;
    }
    free(q->front);
}

void destoryTextbook(LQueue *q){
    while(q->front){
        q->rear = q->front->next;
        free(q->front);
        q->front = q->rear;
    }
}

void clear(LQueue *q){
    // 清空队列, this method has some unknow errors
    node *temp = q->rear;
    while (temp != q->front){
        node *temp2 = temp;
        temp = temp->next;
        free(temp2);
    }
}

void clear2(LQueue *q){
    q->rear = q->front;
    node *temp = q->front->next;
    while (temp){
        node *p = temp->next;
        free(temp);
        temp = p;
    }
}

int length(LQueue q){
    return (int) (q.rear - q.front);
}

int isEmpty(LQueue q){
    // 1 means true, 0 means false
    if (q.rear == q.front){
        return 1;
    }else{
        return 0; // not empty
    }
}

void getTop(LQueue q, ElemType *e){
    if (q.rear != q.front) *e = q.front->data;
}

void enqueue(LQueue *q, ElemType e){
    // 插入元素e到rear
    node *new = malloc(sizeof(ElemType));
    if (!new) exit(1);  // can't malloc memory
    new->data = e;
    new ->next = NULL;
    q->rear->next=new;
    q->rear = new;
}

void dequeue(LQueue *q, ElemType *e){
    // 出队, 即队首出队, 这里注意了，容易产生错误，我们在之前的enqueue中定义了，即，我们的头结点是没有数据在里面的
    if(q->front == q->rear) exit(1); //空队列，不能出队列
    node *temp = q->front->next;
    *e = temp->data;
    q->front->next = temp->next;
    // 这里又是容易错误的地方
    if (q->rear == temp) q->rear = q->front;
    free(temp); 
}

void traverse(LQueue q, void (*visit)(node *n)){
    node *temp = q.front;
    while (temp != q.rear){

        visit(temp->next);
        temp = temp->next;
    }
}

void print(node *n){
    printf("Traverse func: data is %d\n", n->data);
}

void main(){
    LQueue q;
    init(&q);
    printf("**************测试isEmpty函数**************\n这里返回值应该为：1, 实际为%d\n", isEmpty(q));
    printf("**************测试enqueue函数**************\n这里应该输出元素：1");
    enqueue(&q, 1);
    traverse(q, print);
    printf("**************测试enqueue函数**************\n这里应该输出元素：1,2");
    enqueue(&q, 2);
    traverse(q, print);
    printf("**************测试dequeue函数**************\n这里应该输出元素1，和遍历队列2\n");
    ElemType e;
    dequeue(&q, &e);
    printf("the value of e is %d",e);
    traverse(q, print);
    printf("**************测试getTop函数**************\n这里应该输出元素2，输出");
    getTop(q, &e);
    printf("%d\n",e);
    printf("**************测试length函数**************\n这里应该输出元素1，输出%d\n", length(q));
    printf("**************测试clear函数**************\n这里应该输出元素1，输出");
    clear2(&q);
    printf("%d\n", isEmpty(q));
}