#ifndef UTILS_H

#define UTILS_H

#include <cassert></cassert>

#include <cstdio></cstdio>

#include <atomic></atomic>

#include <thread></thread>

#include <chrono></chrono>

#define ShowDebugMSG(...) do { \

	printf("DEBUG %10ld %s:%s:%d:", \

		std::chrono::duration_cast<std::chrono::milliseconds>( \</std::chrono::milliseconds>

			std::chrono::steady_clock::now().time_since_epoch() ).count(), \

		__FILE__, __func__, __LINE__); \

	printf(" " __VA_ARGS__); \

	printf("\n"); \

	fflush(stdout); \

} while(0)

#define HideDebugMSG(...) do {} while(0)

class ReadProtector {

private:

	std::atomic<int> enters;</int>

	std::atomic<int> exits;</int>

public:

	inline ReadProtector(): enters(0), exits(0) { }

	inline ~ReadProtector() { assert(!(enters - exits)); }

	inline void lock() { enters++; }

	inline void unlock() { exits++; }

	inline void wait() const {

		int en = enters;

		while(en - exits > 0) std::this_thread::yield();

	}

};

class ReadLock {

private:

	ReadProtector &protector;

	ReadLock(const ReadLock&) = delete;

public:

	inline explicit ReadLock(ReadProtector &protector): protector(protector) { protector.lock(); }

	inline ~ReadLock() { protector.unlock(); }

};

template<typename t*="" t,="" t::*nextfield=""></typename>

class ChainFuncs {

private:

	ChainFuncs() { }

public:

	typedef T Type;

	static constexpr Type* Type::*Next = NextField;

	static inline void push(Type* &first, Type &item)

		{ assert(!(item.*Next)); item.*Next = first; first = &item; }

	static inline void push(std::atomic<type*> &first, Type &item)</type*>

		{ assert(!(item.*Next)); item.*Next = first; while(!first.compare_exchange_weak(item.*Next, &item)); }

	static inline Type* pop(Type* &first) {

		Type *item = first;

		if (!item) return nullptr;

		first = item->next;

		item->next = nullptr;

		return item;

	}

	static inline Type* pop(std::atomic<type*> &first) {</type*>

		Type *item = first;

		do {

			if (!item) return nullptr;

		} while(!first.compare_exchange_weak(item, item->*Next));

		item->next = nullptr;

		return item;

	}

	static inline void invert(Type* &first) {

		if (Type *curr = first) {

			Type *prev = nullptr;

			while(Type *next = curr->*Next)

				{ curr->*Next = prev; prev = curr; curr = next; }

			first = curr;

		}

	}

	static inline Type* inverted(Type *first)

		{ invert(first); return first; }

};

// multhreaded input, single threaded output

// simultaneus read and write are allowed

template<typename t*="" t,="" t::*nextfield=""></typename>

class QueueMISO {

public:

	typedef T Type;

	typedef ChainFuncs<type, nextfield=""> Funcs;</type,>

	static constexpr Type* Type::*Next = NextField;

private:

	std::atomic<type*> pushed;</type*>

	Type *first;

public:

	inline QueueMISO():

		pushed(nullptr), first() { }

	inline ~QueueMISO()

		{ assert(!pushed && !first); }

	inline void push(Type &item)

		{ Funcs::push(pushed, item); }

	inline Type& pop()

		{ assert(first); return *Funcs::pop(first); }

	inline void unpop(Type &item)

		{ return Funcs::push(first, item); }

	inline Type *peek()

		{ return first ? first : (first = Funcs::inverted(pushed.exchange(nullptr))); }

};

template<typename t*="" t,="" t::*nextfield=""></typename>

class CounteredQueueMISO: public QueueMISO<t, nextfield=""> {</t,>

public:

	typedef T Type;

	typedef QueueMISO<type, nextfield=""> Queue;</type,>

private:

	std::atomic<int> counter;</int>

public:

	inline CounteredQueueMISO():

		counter(0) { }

	inline ~CounteredQueueMISO()

		{ assert(!counter); }

	inline void push(Type &item)

		{ Queue::push(item); counter++; }

	inline Type& pop()

		{ Type &item = Queue::pop(); counter--; return item; }

	inline void unpop(Type &item)

		{ return Queue::unpop(item); counter++; }

	inline int count() const

		{ return counter; }

};

#endif