#include<iostream>
#include<cstring>
#include<cassert>
using namespace std;
//节 点
template<typename T>
struct ListNode{
    T data;
    ListNode<T>* pre;
    ListNode<T>*next;
    ListNode(const T& value=T()):
    data(value),
    pre(nullptr),
    next(nullptr){
    }
};
//正向迭 代器
template<typename T,typename ref1,typename ptr1>
struct Iterator{
    ListNode<T>* node;
    typedef ref1 ref;
    typedef ptr1 ptr;
    typedef Iterator<T,ref,ptr> self;
    Iterator(ListNode<T>* value= nullptr):
    node(value){
    }
    //////////////////////////////////////////
    // 注意：迭代器必须要具有指针类似的功能

    // 解引用  ->  ++/--
    ref operator*(){
        return node->data;
    }
    // 当T是自定义类型才有意义
    ptr operator->(){
        return &node->data;
    };
   self& operator++(){
       this->node=this->node->next;
       return *this;
   }
   self& operator++(int){
       self temp(*this);
       this->node=this->node->next;
       return temp;
   }
   self& operator--(){
       this->node=this->node->pre;
       return *this;
   }
   self& operator--(int){
       self temp(*this);
       this->node=this->node->pre;
       return temp;
   }
    // 两个迭代器要可以比较
   bool operator==(const self& v){
       return this->node==v.node;
   }
   bool operator!=(const self& v){
       return this->node!=v.node;
   }
};
//反向迭代器
template<typename iterator>
struct ReverseIterator{
   typedef ReverseIterator<iterator> self;
    typedef typename iterator::ref ref;
    typedef typename iterator::ptr ptr;
     iterator it;
   ReverseIterator(iterator value):
   it(value){}
   ref operator*(){
      auto temp=it;
      --temp;
      return *temp;
   }
   ptr operator->(){
       return &(operator*());
   }
   self& operator++(){
       --it;
       return *(this);
   }
   self& operator++(int){
       self temp(*this);
       --it;
       return temp;
   }
   self& operator--(){
       ++it;
       return *(this);
   }
   self& operator--(int){
       self temp(*this);
       ++it;
       return temp;
   }
   bool operator==(const self& value){
       return this->it==value.it;
   }
   bool operator!=(const self& value){
       return this->it!=value.it;
   }
};

template<typename T>
class List{

    typedef Iterator<T,const T&,const T*> ConstIterator;
    typedef Iterator<T,T&,T*> Iterator;
    typedef ReverseIterator<ConstIterator> ConstReverseIterator;
    typedef ReverseIterator<Iterator> ReverseIterator;
    typedef ListNode<T> Node;
private:
    Node* head;
    void CreateHead(){
        this->head=new Node();
        (this->head)->next=this->head;
        this->head->pre=this->head;
    }
public:
    List(){
        this->CreateHead();
    }
    List(int n,const T& value=T()){
        this->CreateHead();
        for(int i=0;i<n;i++){
            this->push_back(value);
        }
    }
    List(const List<T>& list){
        auto begin=list.cbegin();
        auto end=list.cend();
        this->CreateHead();
        while(begin!=end){
            this->push_back(*begin);
            ++begin;
        }
    }

    template<typename I>
    List(I begin,I end){
        this->CreateHead();
        while(begin!=end){
            this->push_back(*begin);
            ++begin;
        }
    }
    List<T>& operator=(const List<T>& list){
        if(&list!=this){
            clear();  // 清空this中所有的节点
            auto it = list.cbegin();
            while (it != list.cend())
            {
                push_back(*it);
                ++it;
            }
        }
        return *this;
    }
    ~List(){
        this->clear();
        delete this->head;
        this->head= nullptr;
    }
    void push_back(const T& value=T()){
        this->insert(this->end(),value);
    }
    void pop_back(){
        if(this->empty())
            return;
        auto it=this->end();
        --it;
        this->erase(it);
    }
    void push_front(const T& value=T()){
        this->insert(this->begin(),value);
    }
    void pop_front(){
        this->erase(this->begin());
    }
    Iterator insert(Iterator begin,const T& value=T()){
        Node* newNode=new Node(value);
        Node* current=begin.node;
        newNode->next=current;
        newNode->pre=current->pre;
        current->pre->next=newNode;
        current->pre=newNode;
        return Iterator(newNode);
    }

    Iterator erase(Iterator begin){
        if(begin==this->end()){
            return this->end();
        }
        Node* current=begin.node;
        current->next->pre=current->pre;
        current->pre->next=current->next;
        Node* next=current->next;
        delete current;
        return Iterator(next);
    }
    Iterator erase(Iterator begin,Iterator end){
        while(begin!=end){
            begin=this->erase(begin);
        }
        return end;
    }
    void clear(){
        this->erase(this->begin(),this->end());
    }
    void print(){
        Iterator current=this->begin();
        Iterator end=this->end();
        while(current!=end){
            cout<<current.node->data<<' ';
            ++current;
        }
        cout<<endl;
    }
    Iterator begin(){
        return Iterator(this->head->next);
    }
    Iterator end(){
        return Iterator(this->head);
    }
    ConstIterator cbegin()const{
        return ConstIterator(this->head->next);
    }
    ConstIterator cend()const{
        return ConstIterator(this->head);
    }
    ReverseIterator rbegin(){
        return ReverseIterator(this->end());
    };
    ReverseIterator rend(){
        return ReverseIterator(this->begin());
    };
    ConstReverseIterator  rcbegin()const{
        return ConstReverseIterator(this->cend());
    }
    ConstReverseIterator  rcend()const{
        return ConstReverseIterator (this->cbegin());
    }
    std::size_t size()const{
        std::size_t n=0;
        auto it=this->cbegin();
        while(it!=this->cend()){
            n++;
            ++it;
        }
        return n;
    }
    bool empty(){
        return this->cend()==this->cbegin();
    }
    void resize(std::size_t newsize,const T& value=T()){
        std::size_t size=this->size();
        if(newsize<=size){
            for(int i=newsize;i<size;i++)
                this->pop_back();
        }else{
            for(int i=size;i<newsize;i++)
                this->push_back(value);
        }
    }
    // 元素访问
    T& front()
    {
        return *begin();
    }

    const T& front()const
    {
        return *cbegin();
    }

    T& back()
    {
        // return head->prev->data;
        auto it = end();
        --it;
        return *it;
    }

    const T& back()const
    {
        // return head->prev->data;
        auto it = cend();
        --it;
        return *it;
    }
    void swap(List<T>& list){
        std::swap(this->head,list.head);
    }
};


struct A
{
	int a;
	int b;
	int c;
};

//迭代器operator->的使用
void TestList3()
{
	A aa{ 1, 2, 3 };
	A bb{ 2, 3, 4 };
	A cc{ 3, 4, 5 };
	bite::list<A> L;
	L.push_back(aa);
	L.push_back(bb);
	L.push_back(cc);

	auto it = L.begin();
	while (it != L.end())
	{//本来应该是it->->a,但编译器优化了
		cout << it->a << " " << it->b << " " << it->c << endl;
		++it;
	}
	cout << endl;
}