#include<iostream>
using namespace std;
namespace wwx
{
  //第一个封装（封装结点）
  template<class T>
  struct list_node//给一个结点结构体
  {               //并且此时要注意的是：我们的这个结构体使用的也是模板参数的形式，所以在使用ListNode结构体的时候，一定要记得把它的模板参数跟上
    list_node<T>* _next;
    list_node<T>* _prev;
    T _data;//不打算对成员的访问进行限制（就是谁都可以调用），此时我们就可以这样写，全部给成公有
    list_node(const T& x = T())//写构造函数，初始化
      :_next(nullptr),_prev(nullptr),_data(x)
    {}
  };
  template<class T,class Ref,class Ptr>//此时虽然表示的就是再添加一个模板参数，但是实际上的作用是很大的（目的是为了解决const迭代器问题）
  struct __list_iterator//此时由于地址不连续，所以我们需要再封装一个迭代器（通过next）去找上一个位置和下一个位置，然后间接调用的时候，进而实现加加减减
  {
    typedef list_node<T> node;
    typedef __list_iterator<T, Ref,Ptr> iterator;
    node* _node;//此时的这个结点指针就使用来构造迭代器的
    __list_iterator(node* n)
      :_node(n)//此时要注意这个构造函数初始化，本质上是浅拷贝（由于我们这个迭代器的类中没有实现析构函数，所以并不会报错），因为并没有对同一块空间中的数据析构两次，所以浅拷贝也不怕
    {}                                                        // 本质没有析构函数是因为，结点并不是属于该迭代器的类，而是属于下面链表类，所以可以不要有析构函数
    Ref& operator*()//此时的这个Ref返回值就是这里非常经典的一个地方，怎么传，就怎么返回，如果传const类型的，就是const类型的返回值，是普通类型的，就是普通类型的返回值
    {
      return _node->_data;
    }
    Ptr operator->()//此时由于我们模拟的是指针，所以需要在重载一个->运算符
    {
      return &_node->_data;
    }
    iterator& operator++()//这边不敢傻傻分不清，知道是返回一个地址（迭代器），就是返回一个地址呗（怎么敢写成T&的，此时并不需要链表成员变量）
    {//并且此时还要分清楚类型和类名
      _node = _node->_next;//这个意思表示的就是加加
      //return _node;//妥妥的string没去实现，这里敢写成这个样子
      return *this;//注意这种没有参数的函数（可以这样写的原因都是因为有一个默认的参数this指针，所以才可以很好的找打是谁调用了这个函数，然后把返回值给给它）
      //并且由于此时这个函数表示的是前置++，所以前置加加，返回的是加加之后的值，也就是自己，所以这里可以返回*this(区别于后置加加，后置加加就不可以这样写)
    }
    iterator operator++(int)//编译器规定好了，后置加加，一定要重载的话，就是多家一个int类型的参数给给它重载，这样有利于编译器识别
    {
      iterator tmp(*this);
      _node = _node->_next;
      return tmp;//后置加加的意思：就是返回加加之前的值，所以需要把加加之前的值，先给拷贝构造一份，然后再去向后走
    }
    iterator& operator--()
    {
      _node = _node->_prev;
      return *this;
    }
    iterator operator--(int)//此时后置加加和减减不能给引用的原因是：后置加加和减减本身返回的就是一个临时的值（tmp），所以此时给不给引用都无所谓的
    {
      iterator tmp(*this);
      _node = _node->_prev;
      return tmp;//此时该变量自己本身就是一个临时变量，并不会影响到*this，所以怎么返回都行，无所谓
    }
    bool operator!=(const iterator& s)
    {
      return _node != s._node;//比较不相等，就是比较，此时结点的指针是否相等
    }//但是要注意的是：此时的_node是一个node*类型的，也就是list_node<T>*类型的，所以它里面是包含了三个成员变量的（data，_prev，_next）,所以不可依比较数据data，要比较两个指针是否相同
    bool operator==(const iterator& s)
    {
      return _node == s._node;
    }
  };
  //这个位置先浅谈一下const迭代器
  //首先我们要的是 const T* 不是 T* const
  //所以不敢写成：typedef const iterator const_iterator;//这样写就直接导致我们的迭代器不能被修改了，但是本质上我们的迭代器是地址，地址是需要改变的
  //本质上是为了地址中的数据不可以被改变而已
  //我终于意识到了C++的不好学，哈哈哈！头一次2
  //所以此时我们就自己实现一个const类型的迭代器
  //template<class T>   //可以看出，上面的普通迭代器类和下面的const迭代器类只要在*解引用的时候的返回值有一些不同，冗余了，所以可以直接从上面的迭代器改进
  //struct __list_const_iterator
  //{
  //  typedef list_node<T> node;
  //  typedef __list_const_iterator<T> const_iterator;
  //  node* _node;
  //  __list_const_iterator(node* n)
  //    :_node(n)
  //  {}                                      
  //  const T& operator*()//这样写，就可以让我的数据不被修改，就实现了const迭代器了
  //  {
  //    return _node->_data;
  //  }
  //  const_iterator& operator++()
  //  {
  //    _node = _node->_next;
  //    return *this;
  //  }
  //  const_iterator operator++(int)
  //  {
  //    iterator tmp(*this);                                                              
  //    _node = _node->_next;
  //    return tmp;
  //  }
  //  const_iterator& operator--()
  //  {
  //    _node = _node->_prev;
  //    return *this;
  //  }
  //  const_iterator operator--(int)
  //  {
  //    iterator tmp(*this);
  //    _node = _node->_prev;
  //    return tmp;
  //  }
  //  bool operator!=(const const_iterator& s)
  //  {
  //    return _node != s._node;
  //  }
  //  bool operator==(const const_iterator& s)
  //  {
  //    return _node == s._node;
  //  }
  //};  
// 从上述我们自己封装一个迭代器，我们发现了
// 1.迭代器要么就是原生指针（指针）2.要目就是自定义类型对原生指针的封装，去模拟指针的行为（如上述链表迭代器的封装），模拟的就是node*的行为（int*），本质地址不连续
  //第三个封装（封装链表），所以前两个封装都是为了这第三个打基础而已
  template<class T>
  class my_list//此时不是那种无哨兵位的单向非循环链表，而是带头双向循环链表
  {
    typedef list_node<T> node;//此时为了防止每一次把这个模板参数T给写漏掉（是类型不是类名），此时我们就直接把它给typedef一下，这样就非常的方便
  public:
    typedef __list_iterator<T, T&, T*> iterator;//此时里面这个类和外面那个类的本质区别就是，里面这个类，属于内部类（表示封装的迭代器类本质是my_list类的类），并且没有把外面那个typedef写进来的原因是，私有成员变量有用到，并不是都是给公有函数使用的，所以定义成全局类，提供给整个类使用（而迭代器类，私有成员变量用不上，所以就可以写成内部类的写法）
    typedef __list_iterator<T, const T&, const T*> const_iterator;//通过这种多一个模板参数的形式来实现同一个迭代器实现两中类型的迭代器调用
    //typedef __list_const_iterator<T> const_iterator;//这样我们就自己实现了一个const类型的迭代器，这样const类型的begin和end函数就可以使用const迭代器了
    iterator begin()
    {
      //iterator it(_head->_next);//此时的这句代码就是在调用上述的那个迭代器（使用上面的迭代器去帮我们构造一个it出来）
      //return it;//此时要注意，只有当传上来的值和修改的值都是自己本身的时候，才return *this,而当传上来的值是自己，都返回的值不是自己的时候（是重新构造出来的），此时就应该返回那个重新构造出来的结点
      //这边反而是不喜欢上述的写法，喜欢直接使用经典的匿名对象就行替换
      return iterator(_head->_next);
    }
    const_iterator begin()const
    {
      return const_iterator(_head->_next);
    }
    iterator end()//此时这个位置我们的end给给哨兵位的意思是，我们的迭代器是左闭右开的，迭代器中最后一个位置是最后一个数据的后一个位置（所以此时表示的就是哨兵位的位置，所以不是给给_head->prev，而就是哨兵位，因为此时end是迭代器中的end）
    {
      return iterator(_head);//使用_head去构造一个迭代器对象（匿名），就是去调用上述迭代器中的构造函数，然后用括号里面的这个结点去初始化一个新的结点(这个结点就是我要的结点)
    }
    const_iterator end()const
    {
      return const_iterator(_head);//此时为什么_head是const类型，还可以改变呢？原因：表示的是_head不可以改变，但是_head中的指针（_next/_prev）是允许指向别的东西的（所以可以改变），并且由于此时是涉及拷贝问题，所以也是允许拷贝的
    }
    my_list()//带头双向循环链表 （明白此时的这个东西叫链表），所以遍历方式此时就只有使用迭代器，使用方括号和下标的方式纯属是搞笑的
    {//此时我们没有像源码一样，使用嵌套一个空初始化的函数，而是直接new
      _head = new node;//此时这个的意思表示的是开辟一个哨兵位的头结点出来(但是要注意，new后面跟的一定是一个类型，所以我们的ListNode是一个模板类型，那么此时就需要把它的模板参数给带上)
      _head->_next = _head;//然后此时让这个哨兵位的next指向自己
      _head->_prev = _head;//哨兵位的prev指针也指向自己
    }//注意：一定要把类名和类型给区分开来，类名是类名，类型是类型，类名加上模板参数就是类型
    void push_back(const T& x)//这种位置一定要搞清楚该函数的作用是什么，自然而然就知道了，我们传递的参数是什么，自然而然就知道怎么写了，最多就是多用了const+引用而已，并且一定要注意，此时的数据类型就是模板类型T
    {//这个就是普通的数据结构的写法，这边不需要太在意，带头双向循环链表，注意好头尾的位置就行
      node* tail = _head->_prev;//这句代码要注意，此时不是tail在控制_head->_prev,而是_head->_prev在控制_tail 
      node* new_node = new node(x);//注意好，此时的node是typedef过的（反正就是一个类类型的数据）例：string s1;
      tail->_next = new_node;//注意是双向循环
      new_node->_prev = tail;//注意是双向循环
      new_node->_next = _head;
      _head->_prev = new_node;//这样写就是一个经典的双向循环尾插（在哨兵位的前面找尾，然后插入，最快，根本不需要遍历）
    }
    void push_front(const T& x)
    {
      insert(begin(), x);//复用insert
      //如果是尾插的话，也是一个道理
      //insert(end(), x);//这里可以直接调用begin()或者end()的原因是，我们上述写了这两个函数，间接的通过_head获得了开始位置和最后位置
    }
    void insert(iterator pos, const T& x)
    {
      node* cur = pos._node;
      node* prev = cur->_prev;
      node* new_node = new node(x);
      prev->_next = new_node;
      new_node->_prev = prev;
      new_node->_next = cur;
      cur->_prev = new_node;
    }
    void erase(iterator pos)
    {
      assert(pos != end())//此时因为是带哨兵位的，所以不允许把哨兵位的头结点被删除(并且此时要注意的是，不可以用head去和pos比较，和pos比较需要是一个相同类型的迭代器才可以)
      node* prev = pos._node->_prev;
      node* next = pos._node->_next;
      prev->_next = next;
      next->_prev = prev;
      delete pos._node;
    }
    void pop_back()
    {
      erase(--end());//意思是end返回了一个迭代器对象，然后让这个对象去调用减减运算符，调用减减运算符的本质就是在找该结点的前一个结点
    }                  //减减的本质是因为，此时的end是迭代器中的end，是最后一个数据的下一个数据（_head），所以需要减减一下，表示的才是最后一个尾结点
    void pop_front()
    {
      erase(begin());
    }
  private:
    //struct ListNode* _head;//在C语言中正常的写法是这样的，但是在C++中的时候，就可以发现，我们不一定要跟上struct也可以
    //ListNode* _head;//记得因为是模板类型，所以要跟上模板参数
    node* _head;//看到这个就要注意是typedef过的
  };
  void print_list(const my_list<int>& lt)//此时最好是使用传引用的方式，不然一个一个数据的拷贝，代价很大
  {
    //要注意，此时的lt是一个const类型，导致权限放大了（解决方法，将begin和end函数重载一个const属性的）
    my_list<int>::const_iterator it = lt.begin();//此时还是类型和类名没有搞明白（类型就是类型，把它想象成一个类就行了，例：string）
    while (it != lt.end())
    {
    //  (*it) *= 2;//发现，此时就算是写成了const类型，此时该数据也允许被修改（所以是不对的），所以我们就需要再实现一个const类型的迭代器
      cout << *it << " ";
      ++it;
    }
    cout << endl;
  }
  //测试
  void test_my_list1()//一定要记住，此时的这个链表叫做带头双向循环链表(这个链表是非常优秀的一个数据结构)，带头可以省事挺多的
  {
    my_list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(5);
     // std::iterator it = begin();//数组使用迭代器由于空间连续所以非常的方便
     //所以此时由于链表的地址是非连续的，就不可以使用地址加加减减
    //因为我们使用的是定义new，所有开辟的地址都是未知的、随机的
    // 
    //当我们自己封装了迭代器之后，就可以使用了
    my_list<int>::iterator it = lt.begin();
    while (it != lt.end())//此时还是类和对象的那个道理，end()不需要传参，但是默认是已经把我们的lt的地址传给了this指针，此时使用this指针就是在使用这个li对象
    {//所以此时是返回this指针，还是返回一个新的对象，就看你是否有二次用到传上去的这个对象了
      cout << *it << " ";
      ++it;
    }
    cout << endl;
    for (auto e : lt)//在迭代器的实现方面，vector和list差异可以说是天差地别，但是用起来却是非常的相识（原因：就是底层的封装不同）
    {
      cout << e << " ";
    }
    cout << endl;
  }
  struct AA
  {
    int _a1;
    int _a2;
    AA(int a1 = 0, int a2 = 0)
      :_a1(a1)
      , _a2(a2)
    {}
  };
  void test_my_list2()
  {
    my_list<AA> lt;
    lt.push_back(AA(1, 1));
    lt.push_back(AA(2, 2));
    lt.push_back(AA(3, 3));
    my_list<AA>::iterator it = lt.begin();
    while (it != lt.end())
    {
      //cout << (*it)._a1 << ":" << (*it)._a2 << endl;//这种先解引用，然后再访问的写法非常的不高级，所以我们最后是去重载一个箭头运算符出来
      cout << it->_a1 << ":" << it->_a2 << endl;//但是此时重载了箭头，会发现，此时使用起来非常的怪（感觉像是少了一个箭头，少访问了一层）, //此时就会因为运算符重载的目的是为了增强代码的可读性，所以可以省略一个箭头
      cout << it.operator->()->_a1 << ":" << it.operator->()->_a2;//上面那句代码的本质就是下面这样子的，只是把调用的过程给省略掉了
      ++it;                                                
    }
    cout << endl;
  }
}
int main()
{
  wwx::my_list<int> list;
  wwx::test_my_list1();
}