#include <iostream>
#include <string>

template<typename> struct List;

template<class T>
struct Node {
	using value_type = T;
	using self_type = Node<value_type>;
	using list_type = struct List<value_type>;
	
	friend struct List<T>;

	// Nodes come initialized pointing to themselves.
	Node(T* data_) : _data(data_), _next(this) {}
	
	// Not copyable or moveable
	Node(self_type&) = delete;
	Node(self_type&&) = delete;

	value_type* data() noexcept { return _data; }
	const value_type* data() const noexcept { return _data; }
	self_type* next() noexcept { return _next; }
	const self_type* next() const noexcept { return _next; }

private:
	value_type*	_data;
	self_type*	_next;
};

template<class T>
struct List
{
	using value_type = T;
	using self_type = List<value_type>;
	using node_type = struct Node<value_type>;
	
	List() : _head(nullptr) {}

	void free() {
		node_type* ptr;
		while ((ptr = _head)) {
			std::swap(_head, _head->_next);
			delete ptr;
		}
	}
	
	~List()
	{
		this->free();
	}
	
	node_type* push_front(value_type* data_)
	{
		node_type* insertion = new node_type(data_);
		std::swap(insertion->_next, _head);
		return insertion;
	}
	
	node_type* insert_after(node_type* node_, value_type* data_)
	{
		node_type* insertion = new node_type(data_);
		std::swap(insertion->_next, node_->_next);
		return insertion;
	}
	
	node_type* insert_before(node_type* node_, value_type* data_)
	{
		if (_head == node_)
			return push_front(data_);
		for (node_type* previous = _head; previous; previous = previous->_next) {
			if (previous->_next == node_)
				return insert_after(previous, data_);
		}
		return nullptr;
	}
	
	value_type* pop_front() {
		auto* node = _head;
		if (!_head)
			return nullptr;
		_head = node->_next;
		auto* data = node->_data;
		delete node;
		return data;
	}
	
	value_type* remove(node_type* node_)
	{
		node_type* previous = _head;
		if (previous == node_)
			return pop_front();
		while (previous) {
			auto next = previous->_next;
			if (next == node_) {
				auto* data = node_->_data;
				std::swap(previous->_next, node_->_next);
				delete node_;
				return data;
			}
			previous = next;
		}
	}
	
	bool empty() const noexcept { return _head == nullptr; }
	node_type* head() noexcept { return _head; }
	const node_type* head() const noexcept { return _head; }
	value_type* front() noexcept { return _head->data(); }
	const value_type* front() const noexcept { return _head->data(); }

	node_type* tail() const noexcept {
		node_type* node = _head;
		if (node != nullptr) {
			while (node->_next) {
				node = node->_next;
			}
		}
		return node;
	}

	void dump() {
		if (empty()) {
			std::cout << "list is empty\n";
		} else {
			for (auto* node = head(); node; node = node->next()) {
				std::cout << "\"" << *node->data() << "\", ";
			}
			std::cout << "(end)\n";
		}
	}

private:
	node_type* _head;
};

int main() {
	List<std::string> strings;

	strings.push_front(new std::string("hello"));
	strings.dump();
	strings.push_front(new std::string("mumble"));
	strings.dump();
	strings.push_front(new std::string("world"));
	strings.dump();

	auto* node = strings.head()->next();
	std::cout << "front->next = " << *(node->data()) << "\n";

	auto* removed = strings.remove(node);
	std::cout << "removed " << *removed << "\n";
	delete removed;

	strings.dump();

	node = strings.insert_before(strings.head()->next(), new std::string("mumble"));
	strings.dump();
	node = strings.insert_before(strings.head(), new std::string("wibble"));
	strings.dump();
	delete strings.pop_front();
	strings.dump();
	node = strings.tail();
	std::cout << "strings.tail() = " << *strings.tail()->data() << "\n";
	node = strings.insert_after(node, new std::string("*cough*"));
	strings.dump();
	delete strings.remove(node);
	strings.dump();
	
	return 0;
}