#include<stdio.h>
#include<stdlib.h>

/*******************************************************************************
 *                      data structure and macro definition
 *******************************************************************************/
#define MAX 5
typedef enum{
    OK =1,
    ERROR = -1
}STATUS_EN;

typedef enum{
    TRUE = 1,
    FALSE = 0
}BOOL;

typedef int Elemtype;
typedef struct LNode
{
    Elemtype data;
    struct LNode *next;
}LNode,*LinkList;


/******************************************************************************
 *                          function implement
 ******************************************************************************/

/******************************************************************************
 * function     : destroy_list
 * description  : destroy link list
 * input        : struct LNode **ppHead(a pointer to the link head pointer)
 * output       : struct LNode **pphead
 * return value : void
 * AUthor       : HanyoungXue
 * Date         : 2018-4-14 
 ******************************************************************************/

// a link list with a head node
void destroy_list(LinkList *ppHead){
    LNode *p = *ppHead;//head pointer
    LNode *q = p->next;

    while(p && p->next){
        q = p->next;
        p = q->next;
        free(q);
        q = NULL;
    }
    free(*ppHead);
    *ppHead = NULL;
}
/******************************************************************************
 * function     : init_list
 * description  : init list
 * input        : struct LNode **ppHead
 * output       : struct Londe **ppHead
 * return value : STATUS_EN(OK/ERROR)
 * author       : HanyoungXue
 * date         : 2018-4-14
 ******************************************************************************/

STATUS_EN init_list(LinkList *ppHead){
    if (*ppHead){
        destroy_list(ppHead);
    }

    LNode *p = (LNode*)malloc(sizeof(LNode));
    p->next = NULL;
    p->data = 0;
    *ppHead = p;
    return OK;
}





/*****************************************************************************
 * function     : insert_elem
 * description  : insert element at index == i
 * input        : struct LNode **pphead;
                  const int pos
                  const Elemtype elem
 * output       : struct LNode **pphead
 * return value : STATUS_EN(OK/ERROR)
 * Author       : HanyoungXue
 * Date         : 2018-4-14
 ****************************************************************************/

STATUS_EN insert_elem(LinkList *ppHead,const int pos,Elemtype elem){
    LNode *p = *ppHead;
    LNode *s = NULL;

    // finds the last node front the node with index = pos
    int i = 0;
    while(p && i< pos){
        p = p->next;
        i++;
    }

    // if doesn't find the last node, then return error
    if (!p || i > pos)
    {
        return ERROR;
    }

    // new a Node
    s = (LNode*)malloc(sizeof(LNode));
    if (!s)
    {
        return ERROR;
    }

    // insert the node
    s->data = elem;
    s->next = p->next;
    p->next = s;

    return OK;
}


/* ***************************************************************************
 * function     : remove_elem
 * description  : remove the elem at index=pos,and return elem's data
 * input        : struct Lnode **pphead
                  const int pos
                  Elemtype *pElem
 * output       : struct LNode **ppHead
                  ElemType *pElem
 * return value : STATUS_EN(OK/ERROR)
 * Author       : HanyoungXue
 * Date         : 2018-4-14
 *****************************************************************************/

STATUS_EN remove_elem(LinkList *ppHead,const int pos,Elemtype *pElem){
    LNode *p = *ppHead;
    LNode *q = NULL;
    int i=0;
    while(p && p->next &&i<pos){
        p = p->next;
        i++;
    }

    // the postion of delete is unvalidable
    if (!(p->next)||i>pos)
    {
        return ERROR;
    }

    // delete and release the node
    q = p->next;
    *pElem = q->data;
    p->next = q->next;
    free(q);
    return OK;
}

/**********************************************************************************
 * function     : create_list
 * description  : create a single linkList bases on a array
 * input        : struct LNode **ppHead,
                  const ElemType elems[],
                  const int n
 * output       : struct LNode **ppHead
 * return value : STATUS_EN(OK/ERROR)
 * Author       : HanyoungXUe
 * date         : 2018-4-14
 *********************************************************************************/

STATUS_EN create_list(LinkList *ppHead,const Elemtype elems[],const int n){
    int i = 0;
    STATUS_EN status = OK;

    for (int i = 0; i < n; i++)
    {
        status = insert_elem(ppHead,i,elems[i]);
        if (status!=OK)
        {
            return status;
        }
    }
    return OK;
}


/* *****************************************************************************
 * function     : is_empty_list
 * description  : to judge whether a list is null
 * input        : struct LNode **ppHead
 * output       : N/A
 * return value : BOOL
 * Author       : HanyoungXue
 * date         : 2018-4-14
 *******************************************************************************/

BOOL is_empty_list(LinkList pHead){

    if (!pHead ||!(pHead->next)){
        return TRUE;
    }else{
        return FALSE;
    }

}

/* *****************************************************************************
 * function     : get_elem
 * description  : get an elem from single LinkList where index = pos
 * input        : struct LNode *pHead,
 *                Elemtype *pElem,
 *                const int pos
 * output       : Elemtype *pElem
 * return value : STATUS_EN(OK/ERROR)
 * author       : HanyoungXue
 * date         : 2018-4-14
 *******************************************************************************/

STATUS_EN get_elem(LinkList pHead,Elemtype *pElem,const int pos){
    int i=0;
    LNode *p = pHead -> next;
    while(p && i<= pos){
        if (i==pos){
            *pElem = p->data;
            return OK;
        }else{
            p = p->next;
            i++;
        }
    }
    return ERROR;
}

/* ******************************************************************************
 * function     : locate_elem
 * description  : gets the position which the elem be firstly found on LinkList.
 *                if doesn't find it, then return -1
 * input        : struct LNode *pHead
 *                const Elemtype elem
 * output       : N/A
 * return value : int
 * author       : HanyoungXue
 * date         : 2018-4-14
 ********************************************************************************/

int locate_elem(LinkList pHead,const Elemtype elem){
    LNode *p = pHead ->next;
    int pos = 0;
    while(p){
        if (p->data==elem){
            return pos;
        }else{
            pos ++;
            p = p->next;
        }
    }
    return -1;
}

/********************************************************************************
 * function     : get_length
 * description  : get the length of single LinkList
 * input        : struct LNode *pHead
 * output       : N/A
 * return value : int
 * author       : HanyoungXue
 * date         : 2018-4-14
 ********************************************************************************/

int get_length(LinkList pHead){
    
    if (!pHead ||!(pHead->next)){
        return 0;
    }

    int length = 0;
    LNode *p = pHead->next;
    while(p){
        p = p->next;
        length ++;
    }

    return length;
}

/*********************************************************************************
 * function     : print_list
 * description  : print the all list
 * input        : struct LNode *pHead
 * output       : N/A
 * return value : N/A
 * author       : HanyougXue
 * date         : 2018-4-14
 *********************************************************************************/

void print_list(LinkList pHead){
    if (is_empty_list(pHead)){
        printf("link is empty!\n");
        return;
    }
    LNode *p = pHead->next;
    printf("linkList:\n");
    while(p){
        printf("%d\t", p->data);
        p = p->next;
    }
    printf("\n");
}

/*********************************************************************************
 * function     : reverse_list
 * description  : reverse single LinkList
 * input        : struct LNode **ppHead
 * output       : struct LNode **ppHead
 * return value : N/A
 * author       : HanyoungXue
 * date         : 2018-4-14
 *********************************************************************************/

void reverse_list(LinkList *ppHead){
    if (!(*ppHead)||!((*ppHead)->next)){
        return;
    }

    LNode *prev = NULL;
    LNode *cur = (*ppHead)->next;
    LNode *nex = NULL;
    while(cur){
        nex = cur->next;
        cur->next = prev;
        prev = cur;
        cur = nex;
    }
    (*ppHead)->next = prev;
}

int main(int argc, char const *argv[]){
    Elemtype A[MAX] = {4,5,2,1,3};
    LinkList list = NULL;
    init_list(&list);
    create_list(&list,A,MAX);
    print_list(list);
    reverse_list(&list);
    print_list(list);
    insert_elem(&list,5,6);
    print_list(list);
    return 0;
}