#include <thread>
#include <mutex>
#include <memory>
#include <atomic>
#include <iostream>

using namespace std;

using Data = int; //Data to paczka danych do przetwarzania, wielkość paczki to ok. 1MB.
const Data EMPTY = -1; //reprezentuje brak danych
struct Node;
using PNode = shared_ptr<Node>;
struct Node {
    Node(Data v, PNode n) : value(v), next(n) {}
    Data value;
    PNode next;
};

struct Queue1 {
	PNode head_;
    mutex mutex_;

    Data read() {
        Data out = EMPTY;
        lock_guard<mutex> lock(mutex_);
		if( head_ ) {
			out = head_->value;
			head_ = head_->next;
		}
        return out;
    }
    void write(Data val) {
        lock_guard<mutex> lock(mutex_);
        PNode node = make_shared<Node>( val, head_ );
		head_ = node;
    }
};

//kolejka lock-free

//szybsze, gdy atomic<shared_ptr> jest lock free
struct Queue2 {
    std::atomic<PNode> head_;
    Data read() {
        Data out = EMPTY;
        PNode node = head_.load();
        while( node && ! head_.compare_exchange_weak(node, node->next) )
            {}
        if( node )
            out = node->value;
        return out;
    }
    void write(Data val) {
        PNode node = make_shared<Node>( val, head_.load() );
        while (! head_.compare_exchange_weak(node->next, new_node))
            {}
    }
};

class Reader {
public:
    Reader(Queue1& q) : finish_(false), queue_(q) {}

    void finish() { finish_ = true; }

    void operator()() {
        while(!finish_) {
			Data d = queue_.read();
			std::this_thread::sleep_for( chrono::milliseconds(100));
		}
    }
private:
    Queue1& queue_;
    volatile bool finish_;
};

class Writer {
public:
    Writer(Queue1& q) : finish_(false), queue_(q) {}
    void finish() { finish_ = true; }
    void operator()() {
        int i = 0;
        while(!finish_) {
            Data d = ++i; //obliczenia dla danej d
            std::this_thread::sleep_for( chrono::milliseconds(100));
            queue_.write(d);
        }
    }
private:
    Queue1& queue_;
    volatile bool finish_;
};


int main () {
    atomic<PNode> a;
    cout << a.is_lock_free() << endl;
    atomic<int> b;
    cout << b.is_lock_free() << endl;

    Queue1 q;

    Reader r1(q), r2(q), r3(q);
    Writer w1(q), w2(q);

    thread thrd1( ref(r1) );
    thread thrd2( ref(r2) );
    thread thrd3( ref(r3) );
    thread thrd4( ref(w1) );
    thread thrd5( ref(w2) );

    std::this_thread::sleep_for( chrono::milliseconds(2000));

    r1.finish();
    r2.finish();
    r3.finish();
    w1.finish();
    w2.finish();

    thrd1.join();
    thrd2.join();
    thrd3.join();
    thrd4.join();
    thrd5.join();
    return 0;
}