#pragma once
// Implementation of a generic linked list
template<typename T>
class LinkedList {
public:
	LinkedList();
	~LinkedList();

	// The number of items in the list.
	int GetLength();
	// Adds the item to the front of the list.
	void Add(T item);
	// Removes item at specified index.
	void RemoveAt(int index);
	// Removes the first item in the list that matches item.
	void RemoveFirst(T item);
	// Removes all items in the list which match item.
	void RemoveAll(T item);
	// Removes all items from the list.
	void Clear();
	// Does the list contain the specified item?
	bool Contains(T item);
	// Concatenates list to this list.
	void Concatenate(LinkedList<T> & list);

	T& operator [] (int index) const;
private:
	int length;
	// Must be allocated with new as some members cause suicide (delete this)
	class Node {
	public:
		Node(Node* next, T item);
		~Node();
		T data;
		Node* removeAt(int index, int currentIndex);
		Node* removeFirst(T item);
		Node* atIndex(int index, int currentIndex);
		Node* last();
		void concatenate(Node* toAdd);
		bool contains(T item);
	private:
		Node* next;
	};
	Node* head;
};

// LinkedList member implementation. Mostly delegates to Node.

template<typename T>
LinkedList<T>::LinkedList() {
	length = 0;
	head = nullptr;
}

template<typename T>
LinkedList<T>::~LinkedList() { if (head != nullptr) delete head; head = nullptr; }

template<typename T>
int LinkedList<T>::GetLength() {
	return length;
}

template<typename T>
void LinkedList<T>::Add(T item) {
	Node* node = new Node(this->head, item);
	head = node;
	length++;
}

template<typename T>
void LinkedList<T>::RemoveAt(int index) {
	if (index > length - 1) return;
	if (head != nullptr) {
		head = head->removeAt(index, 0);
		length--;
	}
}

template<typename T>
void LinkedList<T>::RemoveFirst(T item) { 
	if (head != nullptr && head->contains(item)) {
		head = head->removeFirst(item);
		length--;
	}
}

template<typename T>
void LinkedList<T>::RemoveAll(T item) {
	while (Contains(item)) {
		head = head->removeFirst(item);
		length--;
	}
}

template<typename T>
void LinkedList<T>::Clear() {
	if (head != nullptr) { delete head; head = nullptr; length = 0; }
}

template<typename T>
bool LinkedList<T>::Contains(T item) { 
	if (head != nullptr) return head->contains(item);
	return false;
}

template<typename T>
void LinkedList<T>::Concatenate(LinkedList<T>& list) {
	if (head == nullptr)head = list.head;
	else head->concatenate(list.head);
	length += list.length;
}

// LinkedList operator implementation.

template<typename T>
T& LinkedList<T>::operator[] (int index) const {
	// TODO: return path for null head
	return head->atIndex(index, 0)->data;
}

// Node member implementation

template<typename T>
LinkedList<T>::Node::Node(Node* next, T item) : data(item) {
	this->next = next;
}

template<typename T>
LinkedList<T>::Node::~Node() {
	if (next != nullptr) delete next; next = nullptr;
}

// Most of these are recursive.

template<typename T>
typename LinkedList<T>::Node* LinkedList<T>::Node::removeAt(int index, int currentIndex) {
	if (index == currentIndex) {
		Node* nextNode = next;
		next = nullptr;
		delete this;
		return nextNode;
	}
	if (next != nullptr) next = next->removeAt(index, currentIndex++);
	return this;
}

template<typename T>
typename LinkedList<T>::Node* LinkedList<T>::Node::removeFirst(T item) {
	if (data == item) {
		Node* nextNode = next;
		next = nullptr;
		delete this;
		return nextNode;
	}
	if (next != nullptr) next = next->removeFirst(item);
	return this;
}

template<typename T>
typename LinkedList<T>::Node* LinkedList<T>::Node::atIndex(int index, int currentIndex) {
	if (currentIndex == index) return this;
	return next->atIndex(index, ++currentIndex);
}

template<typename T>
bool LinkedList<T>::Node::contains(T item) {
	if (data == item) return true;
	if (next == nullptr) return false;
	return next->contains(item);
}

template<typename T>
typename LinkedList<T>::Node* LinkedList<T>::Node::last() {
	if (next == nullptr) return this;
	return next->last();
}

template<typename T>
void LinkedList<T>::Node::concatenate(Node* toAdd) {
	last()->next = toAdd;
}
