// dlist
#pragma once

#define nil 0

typedef int type;

struct node {
    node* next;
    node* prev;
    type data;
};

int size();

node* head();

node* tail();

void add_head(node* p);

void add_tail(node* p);

void del_head();

void del_tail();

int insert(type data, bool bInsHead = false);

int remove(type data, bool bDelSame = false);

void remove_all(int bDelFromHead = false);

node* find_first_of(type data);

node* find_last_of(type data);

int count_same(type data);

int modify(type data, bool bModSame = false);

void print_all(bool bFromHead = true);

-------------------------------------------------------

// dlist.cpp
#include "dlist.h"
#include <stdlib.h>

static node *h, *t;
static int n;

int size() { return n; }

node* head() { return h; }

node* tail() { return t;  }

void add_head(node* p) {
    if (!head()) {    // 空链表
        p->next = h;  // 将节点p摆在头指针的前面
        h = t = p;    // 只有一个节点，所以都指向一个地址
    }
    else {            // 否则，非空链表
        p->next = h;  // p上最前面
        h->prev = p;  // 头指针指向的节点的前驱就是p指向的节点
        h = h->prev;  // 向前拨动头指针，使它指向最前面的节点
    }
    n++;
}

void add_tail(node* p) {
    if (!tail()) {
        p->prev = h;
        h = t = p;
    }
    else {
        t->next = p;
        p->prev = t;
        t = t->next;
    }
    n++;
}

void del_head() {
    if (!head()) return; // 空链表
    node* p = h;         // p临时与头指针指向头节点
    h = h->next;         // 向后拨动头指针，让头节点悬空 
    h->prev = nil;       // 砍断头节点与链表的联系
    h ? h->prev = nil : h; // 如果头指针确实指向个节点，就把该节点的前向指针清零，否则对头指针什么也不做
    free(p);
    n--;
}

void del_tail() {
    if (!tail()) return;
    node* p = t;
    t = t->prev;
    t->next = nil;
    t ? t->next = nil : t;
    free(p);
    n--;
}

int insert(type data, bool bInsHead) {
    node* p = (node*)malloc(sizeof(node));
    if (!p) return 0;
    p->prev = p->next = nil;
    p->data = data;
    bInsHead ? add_head(p) : add_tail(p);
    return 1;
}

iint remove(type data, bool bDelSame) {
    int cnt = 0;
    if (!(cnt = size())) return 0;
    for (node* p = head(), *q = p->next; q; p = q, q = q->next) {
        if (!p->prev && q && p->data == data) {       // 出现在链表头部
            del_head();
            if (!(p = head()) || !bDelSame) break;    // 更新指针p
        }
        else if (p && !q->next && q->data == data) {  // 出现在链表尾部
            del_tail();
            break;                                    // 已经删到链表尾部，理当break
        }
        else if(p && q->next && q->data == data) {    // 出现在链表中部
            p->next = q->next;
            q->next->prev = p;
            free(q), q = p, n--;
        }
    }
    return cnt - size();
}

void remove_all(int bDelFromHead) {
    node* p = nil;
    bDelFromHead ? p = head() : p = tail();
    while (size()) {
        bDelFromHead ? del_head()  : del_tail();
        bDelFromHead ? p = p->next : p = p->prev;
    }
}

node* find_first_of(type data) {
    if (!size()) return NULL;
    for (node* p = head(), *q = p->next; q; p = q, q = q->next)
        if (p->data == data) return p;
        else if (q->data == data) return q;
    return NULL;
}

node* find_last_of(type data) {
    if (!size()) return NULL;
    for (node* p = tail(), *q = p->prev; q; p = q, q = q->prev)
        if (p->data == data) return p;
        else if (q->data == data) return q;
    return NULL;
}

int count_same(type data) {
    if (!size()) return NULL;
    int cnt = 0;
    for (node* p = head(), *q = p->next; q; p = q, q = q->next) {
        if (p->data == data) cnt++;
        else if (q->data == data) cnt++;
    }
    return cnt;
}

int modify(type data, bool bModSame) {
    if (!size()) return NULL;
    int cnt = 0;
    for (node* p = head(), *q = p->next; q; p = q, q = q->next) {
        if (p->data == data) {
            p->data = data;
            cnt++;
            if (!bModSame) break;
        }
        else if (q->data == data) {
            q->data = data;
            cnt++;
            if (!bModSame) break;
        }
    }
    return cnt;
}

------------------------------------------------------------

// main.cpp
#include "dlist.h"
#include <stdio.h>

void print_all(bool bPrintFromHead) {
    node* p = nil;
    bPrintFromHead ? p = head() : p = tail();
    while (p) {
        printf("data = [ %2d ], address = [ %p ]\n", p->data, p);
        bPrintFromHead ? p = p->next : p = p->prev;
    }
}

int main() {
    insert(3, false);
    insert(3, false);
    insert(9, false);
    insert(4, false);
    insert(9, false);
    insert(3, false);
    insert(2, false);
    insert(8, false);
    insert(3, false);
    insert(3, false);
    print_all();

    int x = 3;
    printf("Elements [ %d ] in records has been deleted [ %d ] times\n", x, remove(x, true));
    puts("Remains Elements in double list");
    print_all(false);
    printf("[ %d ]'s elements in double list\n", size());
    return 0;
}