#include <iostream>
#include "queueLinkedList.cpp"
 
using namespace std;
 
/*struct Item : Data
{
    int value;
    Item *next;      
};*/
 
class mergeSort : public Queue
{
     public:
            Data* divide(Data*);
            Data* merge(Data*, Data*);
            Data* mergesort(Data*);
            Data* mergesort(void);
            Queue queue;
};
 
Data *
mergeSort::divide(Data *a)
{
   Data *b, *c;
 
   b = a;
   c = a->next;
   c = c->next;
 
   while(c != NULL)
   {
       c = c->next;
       b = b->next;
 
       if(c != NULL)
          c = c->next;
   }    
 
   c = b->next;
   b->next = NULL;
 
   return c;       
}
 
Data *
mergeSort::merge(Data *p, Data *q)
{
     Data *r, *start;
     int num;
     if(p->value <= q->value)
     {
          r = p;
          num = p->value;
          addToQueue(num);
          p = p->next; 
          print();           
     }           
 
     else
     {
         r = q;
         num = q->value;
         addToQueue(num);
         q = q->next;    
     }
 
     start = r;
 
     while(p != NULL && q != NULL)
     {
         if(p->value <= q->value)
         {
              r->next = p;
              r = p;
              p = p->next;         
         }
 
         else
         {
             r->next = q;
             r = q;
             q = q->next;
         }
     }
 
     if(p == NULL)
          r->next = q;
     else
         r->next = p;
 
     return start;
}
 
Data *
mergeSort::mergesort(Data *p)
{
   Data *q;
   if(p != NULL)
   {
        if(p->next != NULL)
        {
            q = divide(p);
            p = mergesort(p);
            q = mergesort(q);
            p = merge(p, q);
        }
   }
   return p;
}
 
Data *
mergeSort::mergesort()
{
    mergeSort(top);  
}
 
int 
main()
{
 
    int number = -1;
    Data *list;
    mergeSort sort;
 
    while(number != 0)
    {
           cout << "Enter a number: " << endl;
           cin >> number;   
           if(number != 0)
           { 
             sort.addToQueue(number); 
           } 
    } 
 
    cout << "Results: " << endl;
    sort.print();
 
    sort.mergesort();
 
    cout << "Sorted results: " << endl;
    sort.print();
 
    system("pause");
}

/**********************************************
* A program that stores data to a linked list *
* Tests if linked list is full or empty       *
* Adds or removes data from linked list       *
* Author: Kimberlie Davis                     *
* Version: 3/26/09                            *
***********************************************/
#include <iostream>
 
using namespace std;
 
struct Data
{
   int value;
   Data *next;
};
class Queue
{
 private:
        int fill, remove;
        Data *rear;
 
 public:
        Queue(void);
        void initialize(void);
        int takeAway(void);
        bool full(void);
        bool empty(void);
        void addToQueue(int);
        Data *top;
        int print(void);
        //Data * returnTop(void);
};
 
/*
* Constructor
* Initializes fill, remove and count
*/
Queue::Queue(void)
{ 
      top = NULL; 
      rear = NULL;
 
}
 
/*
* method initialize
* Reinitializes the variables
*/
void
Queue::initialize()
{ 
}
/*
* Method takeAway
* Removes items from the list
*/
int
Queue::takeAway()
{
      Data *p;
      char letter;
      initialize();
      if(top == NULL)
        cout << "Queue Overflow" << endl;
      else
      {
            p = top;
            letter = p->value;
            top = p->next;
            delete p;
            if(top == NULL)
                   rear = NULL;
            return letter;
 
      }  
}
 
/*
* method full
* Returns true if list is full
*/
bool
Queue::full()
{
      if(rear == NULL)
      {
         cout << "Queue Overflow" << endl;
         return true;
      }
      else
         return false; 
}
 
/*
* method empty
* returns true if list is empty
*/
bool
Queue::empty()
{
      if(top == NULL)
      {
         cout << "Queue Empty" << endl;
         return true;
      }
      else
         return false;           
}
 
/*
* method addToQueue
* Takes in value from user
* Adds the value to the list
*/
void 
Queue::addToQueue(int number)
{
          Data *p;
          p = new Data;
          p->value = number;
 
          if(top == NULL)
          {
              top = p;
              rear = p;
          }
 
          else
          {
             rear->next = p;
             rear = p;   
          }
 
          p->next = NULL;
 
}
 
/*Data *
Queue::returnTop()
{
    return top;              
}*/
int
Queue::print()
{
      Data *p;
      p = new Data;
      p = top;
     // Data *p;
      //p = new Data;
      int num;
 
 
      while(top != NULL)
      {
         num = p->value;
         top = p->next;
         p = p->next; 
 
         cout <<  num << endl;     
      }        
}