#ifndef LINKEDLIST
#define LINKEDLIST

#include <stdexcept>

template <class T>
class LinkedList {
	struct Node {
		T data;
		Node* next;
		Node(const T& data, Node* next = nullptr) : data(data), next(next) {}
	};

	Node* head;
	Node* tail;
	unsigned listSize;

	Node* nodeAt(unsigned index);

public:
	class Iterator {
		Node* current;
		Iterator(Node* current) : current(current) {}
	public:
		Iterator& operator++() {
			if (current == nullptr) return *this;

			current = current->next;
			return *this;
		}
		Iterator operator++(int) {
			Iterator old = *this;
			++(*this);
			return old;
		}
		bool operator==(Iterator& other) {
			return this->current == other.current;
		}
		bool operator!=(Iterator& other) {
			return !(*this == other);
		}
		T& operator*() {
			return current->data;
		}
		friend class LinkedList;
	};
	Iterator begin();
	Iterator end();

	class ConstIterator {
		const Node* current;
		ConstIterator(Node* current) : current(current) {}
	public:
		ConstIterator& operator++() {
			if (current == nullptr) return *this;

			current = current->next;
			return *this;
		}
		ConstIterator operator++(int) {
			ConstIterator old = *this;
			++(*this);
			return old;
		}
		bool operator==(const ConstIterator* other) const {
			return this->current == other->current;
		}
		bool operator!=(const ConstIterator* other) const {
			return !(*this == *other);
		}
		const T& operator*() const {
			return current->data;
		}
		friend class LinkedList;
	};
	ConstIterator cbegin() const;
	ConstIterator cend() const;

	void push_front(const T& elem);
	void push_back(const T& elem);
	void push_at(unsigned ind, const T& elem);
	void pop_front();
	void pop_back();
	void pop_at(unsigned ind);
	T& front();
	unsigned size();
	bool empty();
	

	LinkedList() : head(nullptr) {}
	~LinkedList();
	LinkedList(LinkedList& other) = delete;
	LinkedList& operator=(LinkedList& other) = delete;
};

template <class T>
typename LinkedList<T>::Iterator LinkedList<T>::begin() {
	return Iterator(head);
}

template <class T>
typename LinkedList<T>::Iterator LinkedList<T>::end() {
	return Iterator(nullptr);
}

template <class T>
typename LinkedList<T>::ConstIterator LinkedList<T>::cbegin() const {
	return ConstIterator(head);
}

template <class T>
typename LinkedList<T>::ConstIterator LinkedList<T>::cend() const {
	return ConstIterator(nullptr);
}

template <class T>
typename LinkedList<T>::Node* LinkedList<T>::nodeAt(unsigned index) {
	if (index > listSize)
		throw std::runtime_error("Index too large!");

	Node* nat;
	for (nat = head; index > 0; index--) {
		nat = nat->next;
	}
	return nat;
}

template <class T>
void LinkedList<T>::push_front(const T& elem) {
	if (empty()) {
		head = tail = new Node(elem);
	}
	else {
		head = new Node(elem, head);
	}
	listSize++;
}

template <class T>
void LinkedList<T>::push_back(const T& elem) {
	if (empty()) {
		head = tail = new Node(elem);
	}
	else {
		tail = (tail->next = new Node(elem));
	}
	listSize++;
}

template <class T>
void LinkedList<T>::push_at(unsigned ind, const T& elem) {
	if (ind >= listSize) {
		push_back(elem);
	}
	else if (ind == 0) {
		push_front(elem);
	}
	else {
		Node* prev = nodeAt(ind - 1);
		prev->next = new Node(elem, prev->next);
		listSize++;
	}
}

template <class T>
void LinkedList<T>::pop_front() {
	if (empty())
		throw std::runtime_error("Pop empty list!");

	Node* old = head;
	head = head->next;
	delete old;
	listSize--;

	if (empty()) tail = nullptr;
}

template <class T>
void LinkedList<T>::pop_back() {
	if (empty())
		throw std::runtime_error("Pop empty list!");

	Node* old = tail;
	tail = nodeAt(listSize - 2);
	tail->next = nullptr;
	delete old;
	listSize--;

	if (empty()) head = nullptr;
}

template <class T>
void LinkedList<T>::pop_at(unsigned ind) {
	if (ind >= listSize - 1) {
		pop_back();
	}
	else if (ind == 0) {
		pop_front();
	}
	else {
		Node* prev = nodeAt(ind - 1);
		Node* curr = prev->next;
		prev->next = curr->next;
		delete curr;
		listSize--;
	}
}

template <class T>
T& LinkedList<T>::front() {
	return head->data;
}

template <class T>
unsigned LinkedList<T>::size() {
	return listSize;
}

template <class T>
bool LinkedList<T>::empty() {
	return listSize == 0;
}

template <class T>
LinkedList<T>::~LinkedList() {
	while (!empty())
		pop_front();
}

#endif