#include <iostream>
#include <Windows.h>
using namespace std;
const int mincapacity = 10;
const int percent = 65;

template <typename T> class Iterator;

template <typename T>
struct Node {
	T item;
	Node* next;
	Node* prev;
	Node(const T& a, Node* _next, Node* _prev) : item(a), next(_next), prev(_prev) {}
	Node() {}
};

template <typename T>
class Array
{
	friend class Iterator<T>;
	int count;
	Node<T>* Head;
	Node<T>* Tail;
	Node<T>* capacity_last;
	int capacity;
	Iterator<T> head, tail;

	void iterator_update()
	{
		head = Iterator<T>(Head);
		tail = Iterator<T>(Tail);
	}
public:
	Array()
	{
		count = 0;
		Head = Tail = capacity_last = NULL;
		capacity = 0;
		head = Iterator<T>(Head);
		tail = Iterator<T>(Tail);
	}
	Array(const int n)
	{
		count = 0;
		Head = Tail = capacity_last = NULL;
		capacity = 0;
		for (int i = 0; i < n; i++)
			push_back(T());
	}
	Array(const T& Item, const int n)
	{
		count = 0;
		Head = Tail = capacity_last = NULL;
		capacity = 0;
		for (int i = 0; i < n; i++)
			push_back(Item);
	}

	void push_back(const T& _item)
	{
		if (empty())
		{
			Head = Tail = new Node<T>(_item, NULL, NULL);
			capacity_last = Head;
			Change_cap(mincapacity);
		}
		else
		{
			if (Head != Tail)
			{
				Tail->next->item = _item;
				Tail->next->prev = Tail;
				Tail = Tail->next;
			}
			else
			{
				Tail = Head->next;
				Tail->item = _item;
				Tail->prev = Head;
				Head->next = Tail;
			}
		}
		count++;
		if (get_percent() > percent)
		{
			int newcapacity = capacity * 2;
			Change_cap(newcapacity);
		}
		iterator_update();
	}
	void push_front(const T& _item)
	{
		if (empty())
		{
			Head = Tail = new Node<T>(_item, nullptr, nullptr);
			capacity_last = Head;
			Change_cap(mincapacity);
		}
		else
		{
			if (Head != Tail)
			{
				Node<T>* next = Head;
				Head = new Node<T>(_item, next, nullptr);
			}
			else {
				Head = new Node<T>(_item, Tail, nullptr);
				Tail->prev = Head;
			}
		}
		count++;
		if (get_percent() > percent)
		{
			int newcapacity = capacity * 2;
			Change_cap(newcapacity);
		}
		iterator_update();
	}

	int pop_back()
	{
		if (empty())
			return 0;
		else
		{
			if (Tail->prev != nullptr)
			{
				Tail->item = T();
				Tail = Tail->prev;
			}
			else
			{
				Tail->item = T();
				Head = Tail = nullptr;
			}
		}
		count--;
		iterator_update();
	}
	int pop_front()
	{
		if (empty())
			return 0;
		else
		{
			if (Head != Tail)
			{
				Node<T>* next = Head->next;
				delete Head;
				Head = next;
				Head->prev = nullptr;
				capacity--;
				Change_cap(capacity + 1);
			}
			else
			{
				Head->item = T();
				Head = Tail = nullptr;
			}
		}
		count--;
		iterator_update();
	}

	bool empty()
	{
		return Head == NULL;
	}

	double get_percent() const
	{
		return count / (capacity / 100.0);
	}
	int get_length()
	{
		return count;
	}
	int get_capacity()
	{
		return capacity;
	}

	void Change_cap(const int Newcapacity)
	{
		Node<T>* cap = capacity_last;
		for (int i = capacity; i < Newcapacity; i++)
		{
			cap->next = new Node<T>(T(), NULL, cap);
			cap = cap->next;
			capacity_last = cap;
		}
		capacity = Newcapacity;
	}

	T& operator[] (const int id)
	{
		Node<T>* it = Head;
		for (int i = 0; i < id; i++)
			it = it->next;
		return it->item;
	}

	void clear()
	{
		while (!empty())
			pop_back();
	}

	Iterator<T> begin()
	{
		return head;
	}
	Iterator<T> end()
	{
		return tail;
	}

	T& front()
	{
		return *begin();
	}
	T& back()
	{
		Iterator<T> it = end();
		--it;
		return *it;
	}

	void insert(Iterator<T> it, const T& r)
	{
		Node<T>* el = it.elem;
		if (it == end())
			push_back(r);
		else
		{
			Node<T>* nextel = it.elem->next;
			Node<T>* p = new Node<T>(r, nullptr, nullptr);
			p->next = nextel;
			p->prev = el;
			nextel->prev = p;
			el->next = p;
			++count;
		}
	}
	void erase(Iterator<T> it)
	{
		Node<T>* el = it.elem;
		if (it == begin())
			pop_front();
		else
			if (it == end())
				pop_back();
			else
			{
				Node<T>* prevel = it.elem->prev;
				Node<T>* nextel = it.elem->next;
				prevel->next = nextel;
				nextel->prev = prevel;
				delete el;
				--count;
			}
	}
};
template<typename T>
class Iterator
{
public:
	Node<T>* elem;
	Iterator(Node<T>* el) :elem(el) {}
	Iterator() :elem(0) {}
	Iterator(const Iterator& it) :elem(it.elem) {}

	Iterator& operator++()
	{
		if (elem != 0)
			elem = elem->next;
		return *this;
	}
	Iterator& operator--()
	{
		if (elem != 0)
			elem = elem->prev;
		return *this;
	}

	bool operator== (const Iterator& it)
	{
		return (elem == it.elem);
	}
	bool operator!= (const Iterator& it)
	{
		return (elem != it.elem);
	}
};
int main()
{/*
	SetConsoleCP(1251);
	SetConsoleOutputCP(1251);
	int size;
	cout << "Введите размер: ";
	cin >> size;
	Array<int> map(size);
	cout << "Заполните массив: ";
	for (int i = 0; i < map.get_length(); i++)
	{
		cin >> map[i];
	}
	char check;
	do
	{
		cout << "Выберите действие: " << endl;
		cout << "1 - Добавить элемент в конец" << endl;
		cout << "2 - Добавить элемент в начало" << endl;
		cout << "3 - Удалить элемент с конца" << endl;
		cout << "4 - Удалить элемент из начала" << endl;
		cout << "5 - Посмотреть размер" << endl;
		cout << "6 - Посмотреть capacity" << endl;
		cout << "7 - Очистить" << endl;
		cout << "8 - Показать массив" << endl;
		cout << "0 - Выход" << endl;
		cout << "Ваш выбор: ";
		cin >> check;
		char check1;
		switch (check)
		{
		case '1':
		{
			system("cls");
			int k;
			cout << "Введите число, которое будем вводить: ";
			cin >> k;
			map.push_back(k);
		}break;
		case '2':
		{
			system("cls");
			int k;
			cout << "Введите число, которое будем вводить: ";
			cin >> k;
			map.push_front(k);
		}break;
		case '3':
		{
			if (map.pop_back() == 0)
				return 0;
		}break;
		case '4':
		{
			if (map.pop_front() == 0)
				return 0;
		}break;
		case '5':
		{
			system("cls");
			cout << "Размер: " << map.get_length() << endl;
		}break;
		case '6':
		{
			system("cls");
			cout << "Capacity: " << map.get_capacity() << endl;
		}break;
		case '7':
		{
			map.clear();
		}break;
		case '8':
		{
			system("cls");
			cout << endl << "Массив: ";
			for (size_t i = 0; i < map.get_length(); i++)
			{
				cout << map[i] << '\t';
			}
			cout << endl;
		}break;
		}
	} while (check != '0');*/

	Array<int> s;
	s.push_back(5);
	s.push_back(6);
	s.push_back(7);
	s.push_back(8);
	for (int i = 0; i < s.get_length(); i++)
		cout << s[i] << " ";
	Iterator<int> it = s.begin();
	for (int i = 0; i < 0; i++)
		++it;

	s.erase(it);
	it = s.begin();
	for (int i = 0; i < 1; i++)
		++it;
	cout << endl;
	for (int i = 0; i < s.get_length(); i++)
		cout << s[i] << " ";
	s.insert(it, 5);
	cout << endl;
	for (int i = 0; i < s.get_length(); i++)
		cout << s[i] << " ";
	return 0;
}