#include "library.h"

// Remember that this is an example of a race condition.
// if ever add_to_end and take_from_front are executed
// simultaneously it could fail.

// This example does not show the solution to the problem.
// If you want to learn about that, you'll have to take
// EEN521 (Operating Systems) one day.

const string end_of_data_signal = "*** END ***";

class queue_of_strings
{ protected:
    struct node
    { string data;
      node * next;

      node(string s)
      { data=s; next=NULL; } };

    node * first, * last;

  public:
    queue_of_strings()
    { first = NULL;
      last = NULL; }

    bool is_empty()
    { return first==NULL; }

    void add_to_end(string s)
    { node * n = new node(s);
      if (last==NULL)
        first = n;
      else
        last->next = n;
      last = n; }

    string take_from_front()
    { // fails if the queue is empty
      node * oldfirst = first;
      string s = first->data;
      first = oldfirst->next;
      if (first==NULL)
        last = NULL;
      delete oldfirst;
      return s; } };

class tree_of_strings
{ protected:
    struct node
    { string data;
      node * left, * right;

      node(string s)
      { data=s; left=NULL; right=NULL; } };

    node * root;

  public:
    tree_of_strings()
    { root=NULL; }

    void add(node * & t, string s)
    { if (t==NULL)
        t = new node(s);
      else if (s < t->data)
        add(t->left, s);
      else
        add(t->right, s); }

    void add(string s)
    { add(root, s); }

    void enumerate_into(node * t, queue_of_strings * q)
    { if (t==NULL)
        return;
      enumerate_into(t->left, q);
      q->add_to_end(t->data);
      enumerate_into(t->right, q); }

    void enumerate_into(queue_of_strings * q)
    { enumerate_into(root, q);
      q->add_to_end(end_of_data_signal); } };

class tree_to_queue_thread: public thread
{ public:
    tree_of_strings * tree;
    queue_of_strings * queue;

    tree_to_queue_thread(tree_of_strings * t, queue_of_strings * q)
    { tree=t; queue=q; }

    void main()
    { tree->enumerate_into(queue); } };

class queue_compare_thread: public thread
{ public:
    queue_of_strings * queue1, * queue2;

    queue_compare_thread(queue_of_strings * q1, queue_of_strings * q2)
    { queue1 = q1;
      queue2 = q2; }

    void main()
    { while (true)
      { while (queue1->is_empty()) sleep(0.001);
        string s1 = queue1->take_from_front();
        while (queue2->is_empty()) sleep(0.001);
        string s2 = queue2->take_from_front();
        if (s1==end_of_data_signal && s2==end_of_data_signal)
          break;
        if (s1 == s2)
          cout << s1 << ", " << s2 << ", same\n";
        else
          cout << s1 << ", " << s2 << ", DIFFERENT\n"; } } };

void main()
{ tree_of_strings * t1 = new tree_of_strings;
  t1->add("E");
  t1->add("G");
  t1->add("F");
  t1->add("A");
  t1->add("K");
  t1->add("C");
  t1->add("L");
  t1->add("I");
  t1->add("B");
  t1->add("H");
  t1->add("D");
  t1->add("M");
  t1->add("J");
  tree_of_strings * t2 = new tree_of_strings;
  t2->add("J");
  t2->add("E");
  t2->add("L");
  t2->add("K");
  t2->add("F");
  t2->add("H");
  t2->add("B");
  t2->add("D");
  t2->add("A");
  t2->add("M");
  t2->add("C");
  t2->add("G");
  t2->add("I");
  queue_of_strings * q1 = new queue_of_strings;
  queue_of_strings * q2 = new queue_of_strings;

  tree_to_queue_thread * qt1 = new tree_to_queue_thread(t1, q1);
  tree_to_queue_thread * qt2 = new tree_to_queue_thread(t2, q2);
  queue_compare_thread * qc = new queue_compare_thread(q1, q2);

  qc->start();
  qt1->start();
  qt2->start(); }