#include <algorithm>
#include <atomic>
#include <chrono>
#include <functional>
#include <iostream>
#include <iterator>
#include <string>
#include <thread>
#include <vector>

template <typename TaskType>
struct task_list {

	struct node {
		node(std::function<TaskType> task)
			: task(task), next(nullptr) { }

		std::function<void()> task;
		std::atomic<node*> next;
	};

	std::atomic<node*> tail{ nullptr };

	void push_task(std::function<TaskType> task) {
		node* new_node = new node(task);
		node* old_tail = tail.exchange(new_node, std::memory_order_relaxed);

		if(old_tail == nullptr || old_tail->next.exchange(new_node, std::memory_order_consume) == old_tail) {
			delete old_tail;

			node* current = new_node;
			for(;;) {
				current->task();
				node* expected = current->next.exchange(current, std::memory_order_release);
				if(expected == nullptr) return;
				else {
					delete current;
					current = expected;
				}
			}
		}
	}

	~task_list() {
		delete tail.load();
	}
};

int main() {
	task_list<void()> list;

	std::vector<std::thread> threads;
	std::string hello = "Hello, World!\n";

	auto task = [&list, &hello] {
		std::transform(std::begin(hello), std::end(hello), std::ostream_iterator<char>(std::cout), [](auto c) {
			std::this_thread::yield();
			std::this_thread::yield();
			return c;
		});
	};

	std::cout << "Ugly:\n";
	for(int i = 0; i < 10; ++i) {
		threads.emplace_back([&list, task] {
			task();
		});
	}
	
	for(auto& thread : threads)
		if(thread.joinable()) thread.join();
	threads.clear();

	std::cout << "\nNice:\n";
	for(int i = 0; i < 10; ++i) {
		threads.emplace_back([&list, task] {
			list.push_task(task);
		});
	}

	for(auto& thread : threads)
		if(thread.joinable()) thread.join();
}