#ifndef __LIST_H__
#define __LIST_H__

#include <iostream>
#include <initializer_list>

// list:双向链表
template<typename DataType>
class list {
private:
    //struct默认是public,class默认是private
    //可以用class和friend，也可以class Node元素掌握设置为public
    struct Node {       
        DataType data;
        Node* prev;
        Node* next;
        Node() { }
        Node(const DataType& d) : data{ d }, prev{ nullptr }, next{nullptr} { }
        //这里不需要delete prev和next因为它们不是new出来的
        //否则会无限循环调用~Node()，这里可以不用写这个析构函数
        //~Node() { std::cout << "~Node()" << std::endl;}
    };

private:
    Node* head = nullptr;       //哨兵，不存储值
    Node* tail = nullptr;       //尾部，非哨兵
    int size = 0;

public:
    list();
    list(const list<DataType>& ls);
    list(std::initializer_list<DataType> init_list);
    ~list();
    const list<DataType>& operator=(const list<DataType>& ls);
    //返回DataType&，那么ls[n]可以赋值，比如ls[2]=xxx
    DataType& operator[](int index);
    //返回DataType，那么ls[n]不可以赋值，后面带const让const list对象有一个可以调用的版本
    DataType operator[](int index) const;           
    void insert(const DataType data, int pos);
    void remove(const DataType data);
    void remove_at(int index);
    void append(DataType data);                     //链表尾部追加
    void printList() const;
    bool empty() const;
    void clear();
    int length() const;

private:
    //因为operator[]() const里会调用get，所以get后面也要有const
    Node* get(int index) const;                     
    Node* search(DataType data);
    void append(Node* node);
    void remove(Node* node);
};

template<typename DataType>
list<DataType>::list() {
    head = new Node();
    head->prev = head->next = nullptr;
    tail = head;
    size = 0;
}

template<typename DataType>
list<DataType>::list(const list<DataType>& ls) : list() {   //委托list()初始化
    std::cout << "拷贝构造\n" << std::endl;
    Node* node = ls.head->next;
    while (node != nullptr) {
        //注意这里不能调用append(node)，
        //因为append(node)是将形参ls里的node添加到链表
        //而append(node->data)是会新建一个node添加到链表上
        append(node->data);
        node = node->next;
    }
}

template<typename DataType>
list<DataType>::list(std::initializer_list<DataType> init_list) : list() {
    for (auto e : init_list) 
        append(e);
}

template<typename DataType>
list<DataType>::~list() {
    std::cout << "~list()" << std::endl;
    clear();
    delete head;
    tail = head = nullptr;
    //注意这里不用delete tail
    //因为tail在clear()里已经被delete过了
    //否则会出现同一块内存delete了两次，会出错
}

template<typename DataType>
const list<DataType>& list<DataType>::operator=(const list<DataType>& ls) {
    std::cout << "=\n";
    if (&ls == this)
        return *this;

    clear();

    Node* node = ls.head->next;
    while (node != nullptr) {
        //注意这里不能调用append(node)
        //因为append(node)是将形参ls里的node添加到链表
        //而append(node->data)是会新建一个node添加到链表上
        append(node->data);
        node = node->next;
    }
    return *this;
}

template<typename DataType>
DataType& list<DataType>::operator[](int index) {
    return get(index)->data;
}

template<typename DataType>
DataType list<DataType>::operator[](int index) const{
    return get(index)->data;
}

template<typename DataType>
void list<DataType>::insert(const DataType data, int pos) { //pos从0开始
    if (pos > size ||pos < 0) {
        std::cerr << "index out of bound\n";
        exit(1);
    }
    if (pos == size) {      //在尾插入，直接调用append在尾部追加,如果合并到下面的话get(pos)会越界
        append(data);
    }
    else {      
        Node* node = get(pos);
        Node* insert_node = new Node(data);
        insert_node->next = node;
        insert_node->prev = node->prev;
        node->prev->next = insert_node;
        node->prev = insert_node;

        ++size;
    }
}

template<typename DataType>
void list<DataType>::remove(const DataType data) {
    Node* node = search(data);
    remove(node);
}

template<typename DataType>
void list<DataType>::remove_at(int index) {
    remove(get(index));
}

template<typename DataType>
void  list<DataType>::remove(Node* node) {
    if (node == nullptr)return;
    if (node == tail) {
        node->prev->next = nullptr;
        tail = node->prev;
    }
    else {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    delete node;
    --size;
}


template<typename DataType>
void list<DataType>::append(DataType data) {
    Node* node = new Node(data);
    append(node);
}

template<typename DataType>
void list<DataType>::append(Node* node) {
    if (head->next == nullptr) {    
        head->next = node;
        node->prev = head;
        tail = node;
    }
    else {  //如果head->next !=nullptr也意味着tail !=nullptr
        node->prev = tail;
        tail->next = node;
        tail = node;
    }
    ++size;
}
template<typename DataType>
 typename list<DataType>::Node* list<DataType>::get(int index) const{   //注意这里Node也要带类作用域符，而且前面要加typename
     if (index >= size || index < 0) {
         std::cerr << "index out of bound\n";
         exit(1);
     }
    int count;
    Node* node;
    //这里小优化一下，如果是小于等于size/2的，就从前往后数，否则从后往前数
    if (index <= size / 2) {
        count = 0;      //count表示head->next那个结点的index
        node = head->next;
        //循环退出条件是count==index（注意count也是从0开始,这里是后置++，那么count的含义和index一样了，也可以写成++count<=index）
        while (count++ < index) 
            node = node->next;
    }
    else {
        count = size - 1;       //count表示tail那个结点的index,这里要注意size是从1开始，所以要-1
        node = tail;
        while (count-- > index) //循环退出条件是countindex
            node = node->prev;
    }
    return node;
}

 template<typename DataType>
 typename list<DataType>::Node* list<DataType>::search(DataType data) {
    Node* node = head->next;
    while (node != nullptr) {
        if (node->data == data)
            return node;
        node = node->next;
    }

    return nullptr;
 }

template<typename DataType>
void list<DataType>::printList() const {
    if (size <=0 )
        return;

    Node* node = head->next;
    while (node != nullptr) {
        std::cout << node->data << " ";
        node = node->next;
    }
    std::cout << "length:" << length() << std::endl;
}

template<typename DataType>
bool  list<DataType> ::empty() const {
    return (size == 0);
}

template<typename DataType>
int  list<DataType>::length() const {
    return size;
}

template<typename DataType>
void list<DataType>::clear() {
    Node* node = head->next;
    while (node != nullptr) {
        Node* tmp = node;
        node = node->next;
        delete tmp;
    }
    head->prev = head->next = nullptr;
    size = 0;
}

#endif // !__LIST_H__

#include "list.h"
#include <iostream>

int main() {
    list<int> ls = { 1,2,3,4 };
    ls.printList();
    ls.append(5);
    ls.printList();
    ls.insert(0, 0);
    ls.insert(ls.length(), 6);
    ls.printList();
    ls.remove(0);
    ls.printList();
    ls.remove_at(0);
    ls.printList();
    ls.remove_at(ls.length()-1);
    ls.printList();
    ls[2] = 1;
    ls.printList();
    const list<int> const_ls = { 1,2,3 };
    std::cout << const_ls[2] << std::endl;
    const_ls.printList();

    list<int> ls1 = ls;     //调用拷贝构造
    ls1.printList();
    list<int> ls2;
    ls2 = ls;               //调用operator=
    ls2.printList();

    return 0;
}