#pragma once

#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

namespace LL
{
	我們先寫結(jié)點(diǎn)類，這里用類模板，并且是用struct實(shí)現(xiàn)，默認(rèn)內(nèi)容是公開的,其他的類都可以調(diào)用 
	template<class T>
	其中結(jié)點(diǎn)類中要有三個變量，一個存值，兩個指針
	struct _list_node
	{
		T _val;
		_list_node<T>*  _next;
		_list_node<T>*  _prev;

		結(jié)點(diǎn)類中除了要有三個變量，還需要有一個構(gòu)造函數(shù)。當(dāng)我們定義一個新結(jié)點(diǎn)的時候，進(jìn)行構(gòu)造函數(shù)初始化
		我們這里的參數(shù)是一個缺省的val值 ，其中缺省參數(shù)給的是匿名構(gòu)造函數(shù)。最好以const接收。
		_list_node(const T& val = T())
			:_val(val)
			, _next(nullptr)
			, _prev(nullptr)
		{}
	};

	這里實(shí)現(xiàn)迭代器類。首先我們依舊是使用類模板 ，我們這里給三個模板參數(shù)，同時類還是用struct來實(shí)現(xiàn)
	在迭代器類中，我們主要實(shí)現(xiàn) 1、構(gòu)造 2、解引用操作  3、！= 和== 操作  3、前置++后置++ --操作
	template<class T, class Ref, class Ptr> 這里三個模板參數(shù)是什么意思呢?當(dāng)我們需要const迭代器和非const迭代器的時候我們可以根據(jù)第二個參數(shù)的不同來實(shí)例化出不同的迭代器，就不需要寫兩個迭代器了
	typedef _list_iterator<T,T&,T*> iterator;
	typedef _list_iterator<T,cosnt T&,const T*> const_iterator; 我們可以根據(jù)模板參數(shù)實(shí)例化出不同的迭代器。
	struct _list_iterator
	{
		typedef _list_node<T>  node;
		typedef _list_iterator<T, Ref, Ptr>  self;

		node* _pnode;

		構(gòu)造函數(shù)，把node傳進(jìn)來，然后把值賦給我們內(nèi)部創(chuàng)建的_pnode,總不能亂修改外部指針吧。
		_list_iterator(node * node)
			:_pnode(node)
		{}

		這里我們不需要實(shí)現(xiàn)拷貝構(gòu)造、operator=、析構(gòu)，直接用編譯器生成的，對于內(nèi)置類型直接進(jìn)行淺拷貝
		我們發(fā)現(xiàn)淺拷貝指針對于list來說完全沒問題。

		解引用，解引用我們返回值寫為Ref ，這樣可以根據(jù)const和非const，并且就是引用返回可讀可修改，如果ref為const，那就不可修改只可讀。
		這里不需要傳入?yún)?shù)，我們直接進(jìn)行調(diào)用，返回值當(dāng)然為對應(yīng)的val引用.
		Ref operator * ()
		{
			return _pnode->_val;
		}
		同理的我們寫一下這個指針解引用，這里返回值依舊用模板參數(shù)，很方便啊。我們應(yīng)該返回一個地址。
		Ptr operator ->()
		{
			return &(_pnode->_val);
		}

		！= 和 == ，當(dāng)我們使用迭代器的時候，需要比較兩個迭代器是否相等來進(jìn)行循環(huán)條件判定，所以這是必要的。
		我們這里返回值當(dāng)然是bool，參數(shù)傳入我們的迭代器，比較迭代器內(nèi)的節(jié)點(diǎn)是否相等。再加上const最好。
		bool operator != (const self& s) const
		{
			return _pnode != s._pnode;
		}
		bool operator == (const self& s) const
		{
			return _pnode == s._pnode;
		}
		接著我們實(shí)現(xiàn)前置后置++--
		前置 ++ it  我們返回值是 原迭代器
		self& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}
		后置 ++ it ，我們需要進(jìn)行傳參，第一個參數(shù)就是默認(rèn)的this，第二個參數(shù)為0
		it ++ --> it.operator ++(&it,0);我們可以缺省掉第二個參數(shù)，因?yàn)槟J(rèn)是從參數(shù)列表末尾開始匹配的。
		當(dāng)然返回值就不能返回引用了，因?yàn)檫@里我們要用臨時變量進(jìn)行返回,我們先用傳入的it拷貝構(gòu)造一個臨時迭代器。然后在進(jìn)行++操作。
		因?yàn)楹笾眉蛹邮窍荣x值再++所以我們先用臨時變量保存一下之前的迭代器，再給之前的迭代器++，最后再返回未修改的臨時迭代器。
		self operator++(int)
		{
			self tmp(*this);
			_pnode = _pnode->_next;
			return tmp;
		}

		self& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}
		self operator--(int)
		{
			self tmp(*this);
			_pnode = _pnode->_prev;
			return tmp;
		}


	};




	接下來我們開始寫list類,當(dāng)然也要用類模板來寫，里面要實(shí)現(xiàn)1、迭代器 2、構(gòu)造 3、push_back 。我們這里的list是帶頭雙向循環(huán)列表
	template <class T>
	class list
	{
		我們先來實(shí)現(xiàn)一下迭代器,我們首先需要typedef 我們的迭代器 ，所以先實(shí)現(xiàn)迭代器。然后需要定義const和非const的beginend ,
		這里需要記住end和begin要有非const和cosnt，因?yàn)闊o法同時滿足可修改和可讀。比如const迭代器調(diào)用只能掉const的end，非const的迭代器雖然可以調(diào)用const的end，但是導(dǎo)致權(quán)限縮小，無法修改內(nèi)容。
		typedef _list_node<T> node;
	public:
		typedef _list_iterator<T, T&, T*> iterator;
		typedef _list_iterator<T, const T&, const T*> const_iterator;

		iterator begin()                   //begin指頭結(jié)點(diǎn)后第一個結(jié)點(diǎn)，end指頭結(jié)點(diǎn)。
		{
			return iterator(_head->_next); //這里調(diào)用的是匿名構(gòu)造然后直接返回。
		}
		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}


		構(gòu)造函數(shù)，這里直接進(jìn)行頭結(jié)點(diǎn)的創(chuàng)建（自己鏈自己）
		list()
		{
			_head = new node(T());    當(dāng)然可以有這種寫法，我們用匿名構(gòu)造一個頭結(jié)點(diǎn)，可以是各種類型。這里和上文中，結(jié)點(diǎn)的構(gòu)造函數(shù)是一樣的，我們寫一個就好了。
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		push_back 我們傳入一個要插入的值，創(chuàng)建新節(jié)點(diǎn)進(jìn)行鏈接的更新。
		void push_back(const T& val)
		{
			node* newnode = new node(val);   //這里因?yàn)槲覀冊诮Y(jié)點(diǎn)的構(gòu)造函數(shù)中寫了模板參數(shù)類型匿名構(gòu)造，可以傳任意類型。
			node* tail = _head->_prev;
			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;

		}

		拷貝構(gòu)造  1、創(chuàng)造新的頭結(jié)點(diǎn)，把傳入的list循環(huán)賦值給新的頭結(jié)點(diǎn)。
		list(const list<T>& l)
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
			const_iterator it = l.begin();
			while (it != l.end())
			{
				push_back(*it);
				++it;
			}
		}

		insert，在指定位置插入元素，我們不用返回值，參數(shù)是pos迭代器和val
		先給一個cur 存pos位置的結(jié)點(diǎn)，然后定義一個我們的prev，為了之后和新節(jié)點(diǎn)鏈接。2、創(chuàng)建新節(jié)點(diǎn)，更新鏈接就好了。
		void insert(iterator pos, const T& val)   //這里不需要用const 因?yàn)?，const迭代器對應(yīng)了constlist ，const list怎么會來插入數(shù)據(jù)呢？
		{
			node* cur = pos._pnode;
			node* prev = cur->_prev;
			node* newnode = new node(val);

			newnode->_next = cur;
			newnode->_prev = prev;
			prev->_next = newnode;
			cur->_prev = newnode;
		}

		erase ,返回下一個位置的迭代器，傳入一個pos
		1、保存指向結(jié)點(diǎn)，并找到前后的兩節(jié)點(diǎn) 2、更新鏈接 刪除掉當(dāng)前節(jié)點(diǎn)。3、返回迭代器。這里需要強(qiáng)轉(zhuǎn)，從指針轉(zhuǎn)成迭代器類型。
		iterator erase(iterator pos)
		{
			node* cur = pos._pnode;
			node* prev = cur->_prev;
			node* next = cur->_next;
			
			prev->_next = next;
			next->_prev = prev;
			delete cur;
			return (iterator)next;
		}


		那我們在賦值運(yùn)算符重載的時候需要先清理掉自身的結(jié)點(diǎn)，所以我們實(shí)現(xiàn)一下clear
		clear 清空list中除了頭結(jié)點(diǎn)以外的所有結(jié)點(diǎn)。很好實(shí)現(xiàn)，我們循環(huán)erase就好了，erase返回下一個的迭代器，所以接收其返回值就好了。
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		賦值運(yùn)算符重載，返回值是類型的引用 ，參數(shù)傳入list
		1、首先判斷是否給自己賦值，否則我們刪除后會發(fā)生野指針的問題 2、條件成立我們先清除現(xiàn)在的一切，然后循環(huán)賦值。最后返回*this；
		list<T>& operator = (list<T>& l)
		{
			if (this != &l)
			{
				clear ();
				iterator it = l.begin();
				while (it != l.end())
				{
					push_back(*it);
					it++;
				}
				
			}
			return *this;
		}

		析構(gòu)：析構(gòu)要做的就是析構(gòu)一切，先clear，在delete 頭，并給頭賦空
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
			cout << "析構(gòu)執(zhí)行成功" << endl;
		}

		獲得第一個元素，返回一定是類型的引用,這里應(yīng)該有兩個版本，否則當(dāng)const對象調(diào)用的時候，會無法調(diào)用。這里返回也要返回const，否則你給人家偷偷擴(kuò)大了權(quán)限。
		T& front()
		{
			return _head->_next->_val;
		}

		const T& front() const
		{
			return _head->_next->_val;
		}
		獲得最后一個元素
		
		T& back()
		{
			return _head->_prev->_val;

		}
		const T& back() const
		{
			return _head->_prev->_val;

		}

		交換兩個list,傳入list。我們只需要交換一下頭結(jié)點(diǎn)就可以了
		void swap(list<T>& l)
		{
			::swap(_head, l._head);
		}

		void push_back_insert(const T& val)
		{
			insert(end(), val);
		}

		void push_front_insert(const T& val)
		{
			insert(begin(), val);
		}

		void pop_front_erase()
		{
			erase(begin());
		}
		void pop_back_erase()
		{
			erase(--end());
		}

		求結(jié)點(diǎn)個數(shù)循環(huán)計數(shù)
		size_t size()
		{
			size_t count = 0;
			auto it = begin();
			while (it != end())
			{
				++it;
				++count;

			}
			return count;
		}

		bool empty()
		{
			return begin() == end();		
		}

		resize ,開辟n個空間并賦初始值，用匿名構(gòu)造賦值。
		1、計算舊結(jié)點(diǎn)個數(shù)，如果就空間比新的空間大，我們就刪除多余的空間2、否則就從新空間開始給其賦初值。
		void resize(size_t newsize, T& val = T())
		{
			size_t oldsize = size();
			if (oldsize > newsize)
			{
				for (int i = newsize; i < oldsize; i++)
				{
					pop_back_erase();
				}
			}
			else
			{
				for (int i = oldsize; i < newsize; i++)
				{
					push_back_insert(val);
				}
			}
		}




	private:
		node* _head;
	};

}

#include "List.h"

//printlist 打印不需要返回什么，參數(shù)是一個模板參數(shù)類型的列表
template<class Con>
void PrintContainer(const Con& c)
{
	Con::const_iterator it = c.begin();
	while (it != c.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

}

void test_list1()
{
	cout << "list1使用pushback插入數(shù)據(jù)的打印" << endl;
	LL::list<int> lt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);
	lt1.push_back(4);
	lt1.push_back(5);
	lt1.push_back(6);
	PrintContainer(lt1);
	//for (auto e : lt)
	//{
	//	cout << e << " ";

	//}
	//cout << endl;

	//LL::list<int>::iterator it = lt.begin();
	//while (it != lt.end())
	//{
	//	(*it)++;
	//	cout << *it << " ";
	//	++it;
	//}
	//cout << endl;


	cout << "拷貝構(gòu)造list2的打印" << endl;
	LL::list<int> lt2(lt1);
	PrintContainer(lt2);
	
	//cout << "在list2的2位置前insert一個0并打印" << endl;
	//LL::list<int>::iterator pos = find(lt2.begin(), lt2.end(),2);		
	//lt2.insert(pos,0);
	//PrintContainer(lt2);

	//cout << "在list2的2位置前insert一個0并打印" << endl;
	//lt2.erase(pos);
	//PrintContainer(lt2);

	cout << "用list2給list3賦值,并打印" << endl;
	LL::list<int> lt3;
	lt3 = lt2;
	PrintContainer(lt3);

	cout << "獲得list3的第一個元素和最后一個元素" << endl;
	cout << lt3.front() <<"  ";
	cout << lt3.back() << endl;

	cout << "整一個全是0的list4，并打印" << endl;
	LL::list<int> lt4;
	lt4.push_back(0);
	lt4.push_back(0);
	lt4.push_back(0);
	lt4.push_back(0);
	lt4.push_back(0);
	lt4.push_back(0);
	PrintContainer(lt4);

	cout << "交換鏈表list1和list4、并打印" << endl;
	lt1.swap(lt4);
	PrintContainer(lt4);


	cout << "頭刪list4" << endl;
	lt4.pop_front_erase();
	PrintContainer(lt4);
	cout << "頭插list4" << endl;
	lt4.push_front_insert(0);
	PrintContainer(lt4);
	cout << "尾刪list4" << endl;
	lt4.pop_back_erase();
	PrintContainer(lt4);
	cout << "尾插list4" << endl;
	lt4.push_back_insert(0);
	PrintContainer(lt4);


	cout << "list4的節(jié)點(diǎn)個數(shù)" << endl;
	cout << lt4.size() << endl;

	cout << "判斷是list1是否為空鏈表" << endl;
	cout << lt1.empty() << endl;




	cout << "    " << endl;
	cout << "    " << endl;
	cout << "    " << endl;
	cout << "    " << endl;

	cout << "    " << endl;
	cout << "    " << endl;
}


int main()
{

	test_list1();
	return 0;
}