// w aplikacji występuje zakleszczenie. Proszę je wyeliminować dbając o to, aby rozwiązanie było poprawne (bez wyścigów).

// shared_ptr<T> to sprytny wskaźnik, przechowuje obiekt i licznik odwołań do obiektu, W funkcji 'main' występują obiekty 'ref(x)'. Są to obiekty pomocnicze, które zapobiegają tworzeniu kopii obiektu, więc np. 'thread thrd1( ref(p1) );'
// oznacza, że konstruktor 'std::thread' nie wykona kopii obiektu 'p1'. Nie jest to kluczowe do znalezienia rozwiązania.

// Posługujemy się także listą dwukierunkową list<int>, z operacjami 'push_back' -- wstawiania na koniec, 'pop_front' -- usuwanie początkowego elementu,
// 'front' -- zwraca początkowy element listy


#include <memory>
#include <thread>
#include <atomic>

#include <iostream>

using namespace std;

using Data = int;
const Data EMPTY = -1; //reprezentuje brak danych


//kolejka lock-free
struct Node;
using PNode = shared_ptr<Node>;
struct Node {
    Node(Data v, PNode n) : value(v), next(n) {}
    Data value;
    PNode next;
};

//szybsze, gdy atomic<shared_ptr> jest lock free
struct Queue {
    std::atomic<PNode> head_;

    bool isEmpty() {
        return head_.load() != nullptr;
    }

    void write(int val) {
        PNode new_node = make_shared<Node>( val, head_.load() );
        while (! head_.compare_exchange_weak(new_node->next, new_node))
            {}
    }

    Data read() {
        Data out = EMPTY;
        PNode ret_node = head_.load();
        while( ret_node && ! head_.compare_exchange_weak(ret_node, ret_node->next) )
            {}
        if( ret_node )
            out = ret_node->value;
        return out;
    }
};

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

    void finish() { finish_ = true; }

    void operator()() {
        while(!finish_) {
            if(! queue_.isEmpty() ) {
                Data d = queue_.read();
                //process data
                std::this_thread::sleep_for( chrono::milliseconds(1));
            }
        }
    }
private:
    Queue& queue_;
    volatile bool finish_;
};


class Writer {
public:
    Writer(Queue& q) : finish_(false), queue_(q) {}

    void finish() { finish_ = true; }

    void operator()() {
        int i = 0;
        while(!finish_) {
            //calculation
            std::this_thread::sleep_for( chrono::milliseconds(1));

            Data d = ++i;
            queue_.write(d);
        }
    }
private:
    Queue& queue_;
    volatile bool finish_;
};


int main () {
    atomic<PNode> a;
    cout << a.is_lock_free() << endl;
    atomic<int> b;
    cout << b.is_lock_free() << endl;
    Queue q;
    Reader r1(q), r2(q);
    Writer w1(q), w2(q);

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

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

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

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

}