//
//  DoubleLink.c
//  DataStructureAndAlgorithm
//
//  Created by wanyakun on 2016/10/27.
//  Copyright © 2016年 com.ucaiyuan. All rights reserved.
//

#include "DoubleLink.h"
#include <stdlib.h>

//typedef struct ElementType ElemType;

typedef struct DoubleLinkNode {
    struct DoubleLinkNode *preNode;
    struct DoubleLinkNode *nextNode;

    void *data;
} DLNode;


/// 表头。不存放元素值
static DLNode *head = NULL;
/// 节点个数
static int count = 0;

static DLNode * createNode(void *data) {
    DLNode *node = NULL;
    node = (DLNode *)malloc(sizeof(node));
    if (!node) {
        printf("create node error!\n");
        return NULL;
    }

    // 默认node的前一节点和后一节点都指向自身
    node->preNode = node->nextNode = node;
    // 节点的值为data
    node->data = data;

    return node;
}

int createDLink() {
    head = createNode(NULL);
    if (!head) {
        return -1;
    }

    count = 0;

    return 0;
}

int destroyDLink() {
    if (!head) {
        printf("%s failed! DLink is null!\n", __func__);
        return -1;
    }

    DLNode *node = head->nextNode;
    DLNode *temp = NULL;
    while (node != head) {
        temp = node;
        node = node->nextNode;
        free(temp);
    }

    free(head);
    head = NULL;
    count = 0;

    return 0;
}

int isDLinkEmpty() {
    return count == 0;
}

int dLinkSize() {
    return count;
}

static DLNode * _getNode(int index) {
    if (index < 0 || index >= count) {
        printf("%s failed! index out of bound!\n", __func__);
        return NULL;
    }

    if (index <= count/2) {
        int i = 0;
        DLNode *node = head->nextNode;
        while ((i++) < index) {
            node = node->nextNode;
        }
        return node;
    }

    int j = 0;
    int rIndex = count - index - 1;
    DLNode *node = head->preNode;
    while ((j++) < rIndex) {
        node = node->preNode;
    }
    return node;
}

void* getNodeData(int index) {
    DLNode *node = _getNode(index);
    if (!node) {
        printf("%s failed!\n", __func__);
        return NULL;
    }

    return node->data;
}

void* firstNodeData() {
    return getNodeData(0);
}

void* lastNodeData() {
    return getNodeData(count-1);
}

int insertData(int index, void *data) {
    if (index == 0) {
        return insertFirst(data);
    }

    DLNode *indexNode = _getNode(index);
    if (!indexNode) {
        return -1;
    }

    DLNode *node = createNode(data);
    if (!node) {
        return -1;
    }

    node->preNode = indexNode->preNode;
    node->nextNode = indexNode;
    indexNode->preNode->nextNode = node;
    indexNode->preNode = node;

    count++;

    return 0;
}

int insertFirst(void *data) {
    DLNode *node = createNode(data);
    if (!node) {
        return -1;
    }

    node->preNode = head;
    node->nextNode = head->nextNode;
    head->nextNode->preNode = node;
    head->nextNode = node;

    count++;

    return 0;
}

int appendData(void *data) {
    DLNode *node = createNode(data);
    if (!node) {
        return -1;
    }

    node->nextNode = head;
    node->preNode = head->preNode;
    head->preNode->nextNode = node;
    head->preNode = node;

    count++;

    return 0;
}

int deleteNode(int index) {
    DLNode *node = _getNode(index);
    if (!node) {
        printf("%s failed! the index is out of bound!\n", __func__);
        return -1;
    }

    node->nextNode->preNode = node->preNode;
    node->preNode->nextNode = node->nextNode;
    free(node);
    count--;

    return 0;
}

int deleteFirstNode() {
    return deleteNode(0);
}

int deleteLastNode() {
    return deleteNode(count-1);
}