
#pragma once

#include <iostream>
#include <iomanip>
using namespace std;

template <class T>
	class Node {
	public:
		T key;
		Node<T>* next;
		Node(T data, Node<T>* n = NULL) : key(data), next(n) {};
	};

template <class T>
class LList {


	Node<T>* head, *crnt, *tail;
	int n;

	void DeleteList();
	void CopyList(const LList<T>& obj);

public:

	LList();
	~LList();
	LList(const LList<T>& obj) ;
	LList<T>& operator=(const LList<T>& obj);

	Node<T>* Search(const T& x);

	void Insert(const T& x);
	void ToEnd(const T& x) { Insert(x); }
	void InsertAfter(Node<T> *p, const T& x);
	void InsertBefore(Node<T> *p, const T& x);

	void DeleteAfter(Node<T> *p, T& x);
	void Delete(Node<T> *p, T& x);
	void DeleteBefore(Node<T> *p, T& x);

	int Length() { return n; }
	void Print();

	void IterStart(Node<T>* p = NULL) {
		if (p) crnt = p;
		else crnt = head;
	}

	Node<T>* Iter() {
		Node<T> *p = crnt;
		if (crnt) crnt = crnt -> next;
		return p;
	}

};

template <class T>
void LList<T>::CopyList(const LList<T> &obj) {

	if (obj.head) {

		DeleteList();

		Node<T> *p = new Node<T>(obj.head -> key, NULL);
		head = tail = p;

		Node<T>* q = obj.head -> next;
		while (q) {
			
			p -> next = new Node<T>(q -> key, NULL);
			tail = p -> next;

			p = p -> next;
			q = q -> next;

		}

		n = obj.n;

	} else {

		head = crnt = tail = NULL;
		n = 0;

	}

}

template <class T>
void LList<T>::DeleteList() {

	Node<T> *p = head;
	while (p) {
		head = p; p = p -> next;
		delete head;
	}

	head = crnt = tail = NULL;
	n = 0;
	
}

template <class T>
LList<T>::LList()  : head(NULL), crnt(NULL), tail(NULL), n(0) {
}

template <class T>
LList<T>::~LList() {

	DeleteList();

}

template <class T>
LList<T>::LList(const LList<T>& obj) : head(NULL), crnt(NULL), tail(NULL), n(0)  {

	if (obj.head) {
		DeleteList();
		CopyList(obj);
		n = obj.n;
	} 

}

template <class T>
LList<T>& LList<T>::operator=(const LList<T>& obj) {

	if (this != &obj) {
		DeleteList();
		CopyList(obj);
		n = obj.n;
	}

	return *this;

}

template <class T>
Node<T>* LList<T>::Search(const T& x) {

	IterStart();
	Node<T>* p; 

	while ( (p = Iter()) && (p -> key != x) ) ;

	return p;

}

template <class T>
void LList<T>::Insert(const T& x) {

	Node<T> *p = new Node<T>(x, NULL);
	if (tail) {
		tail -> next = p;
		tail = p;
	} else {
		head = tail = p;
	}
	n++;

}

template <class T>
void LList<T>::InsertAfter(Node<T> *p, const T& x) {
	if (p) {
		Node<T> *q = new Node<T>(x, p -> next);
		p -> next = q;
		if (p == tail) tail = q;
		n++;
	}
}

template <class T>
void LList<T>::InsertBefore(Node<T> *p, const T& x) {
	if (p) {
		Node<T> *q = new Node<T>(p -> key, p -> next);
		p -> key = x;
		p -> next = q;
		if (p == tail) tail = q;
		n++;
	}
}

template <class T>
void LList<T>::DeleteAfter(Node<T> *p, T& x) {

	if (p && p -> next) {

		Node<T>* q = p -> next;
		x = q -> key;
		
		p -> next = q -> next;

		if (q == tail) tail = p;
		delete q;

	}

}

template <class T>
void LList<T>::Delete(Node<T> *p, T& x) {

	if (p == head) {

		x = p -> key;

		if (head == tail) {
			head = tail = NULL;
		} else {
			head = p -> next;
		}

		delete p;

	} else {

		Node<T> *q = head;
		while (q -> next != p) q = q -> next;
		DeleteAfter(q, x);

	}

	n--;
}

template <class T>
void LList<T>::DeleteBefore(Node<T> *p, T& x) {

	if (p != head) {
		Node<T> *q = head;
		while (q -> next != p) q = q -> next;
		Delete(q, x);
	}

}


template <class T>
void LList<T>::Print() {
	if (head) {
		Node<T> *p = head;
		while (p) {
			cout << setw(5) << p -> key;
			p = p -> next;
		}
		cout << endl;
	} else {
		cout << "empty...\n" << endl;
	}
}
 
