// Project 2
// CS2604 : Data Structures
// Hussein Suleman
// 14 July 1999

// ---------------------------------------------------------------------

#include <iostream.h>
#include <stdlib.h>

// ---------------------------------------------------------------------

// student's files 

#include "window.h"
#include "windowl.h"

// ---------------------------------------------------------------------

// model solution

class XWindow
{
public:
   XWindow ( char *s );
   ~XWindow ();
   char *GetData () { return Data; };
   XWindow *Next;
   XWindow *Prev;
   char *Data;
};

XWindow::XWindow ( char *s )
{
   Data = (char *)malloc(strlen (s)+1);
   strcpy (Data, s);
}

XWindow::~XWindow ()
{
   free (Data);
}

class XWindowList
{
public:
   XWindowList ();
   ~XWindowList ();
   void Traverse ( void (* Visit )( XWindow * ) );
   void AddWindow ( char *s );
   void DeleteWindow ();
   void NextWindow ();
   void PrevWindow ();
private:
   XWindow *Head;
};

XWindowList::XWindowList ()
{
   Head = NULL;
}

XWindowList::~XWindowList ()
{
   while (Head != NULL)
      DeleteWindow ();
}

void XWindowList::Traverse ( void (* Visit )( XWindow * ) )
{
   if (Head == NULL) return;
   XWindow *p = Head;
   Visit (p);
   p = p->Next;
   while (p != Head)
   {
      Visit (p);
      p = p->Next;
   }
}

void XWindowList::AddWindow ( char *s )
{
   if (Head == NULL)
   {
      Head = new XWindow (s);
      Head->Next = Head;
      Head->Prev = Head;
   }
   else
   {
      XWindow *p = new XWindow (s);
      p->Next = Head;
      p->Prev = Head->Prev;
      Head->Prev->Next = p;
      Head->Prev = p;
      Head = p;
   }
}

void XWindowList::DeleteWindow ()
{
   if (Head == NULL)
      return;
   if (Head == Head->Next)
   {
      delete Head;
      Head = NULL;
   }
   else
   {
      XWindow *p = Head;
      p->Prev->Next = p->Next;
      p->Next->Prev = p->Prev;
      Head = p->Next;
      delete p;
   }
}

void XWindowList::NextWindow ()
{
   if (Head != NULL)
      Head = Head->Next;
}

void XWindowList::PrevWindow ()
{
   if (Head != NULL)
      Head = Head->Prev;
}


// ---------------------------------------------------------------------

// list of windows for testing purposes

class YWindow
{
public:
   YWindow ( char *s );
   ~YWindow ();
   char *GetData () { return Data; };
   YWindow *Next;
   char *Data;
};

YWindow::YWindow ( char *s )
{
   Data = (char *)malloc(strlen (s)+1);
   strcpy (Data, s);
}

YWindow::~YWindow ()
{
   free (Data);
}

class TestStack
{
public:
   YWindow *Head;
   TestStack ();
   ~TestStack ();
   void Clear ();
   void Add ( char *s );
};

TestStack::TestStack ()
{
   Head = NULL;
}

TestStack::~TestStack ()
{
   Clear ();
}

void TestStack::Clear ()
{
   while (Head != NULL)
   {
      YWindow *p = Head;
      Head = Head->Next;
      delete p;
   }
}

void TestStack::Add ( char *s )
{
   YWindow *p = new YWindow (s);
   p->Next = Head;
   Head = p;
}

void CheckStacks ( TestStack *A, TestStack *B )
{
   YWindow *p = A->Head;
   YWindow *q = B->Head;
   int Error = 0;
   int mismatches = 0;
   while ((p!=NULL) && (q!=NULL))
   {
      if (strcmp (p->GetData (), q->GetData ()) != 0)
      {
         if (mismatches < 5)
         {
            cout << "\n---ERROR: Mismatch in windows : " << p->GetData () 
                 << " ... should be ... " << q->GetData ();
            Error = 1;
            mismatches++;
         }
      }
      p=p->Next;
      q=q->Next;
   }
   if ((q) && (!p))
   {
      cout << "\n---ERROR: Too few windows";
      Error = 1;
   }
   if ((p) && (!q))
   {
      cout << "\n---ERROR: Too many windows";
      Error = 1;
   }
   if (Error == 0)
      cout << "... OK!";
}

// ---------------------------------------------------------------------

TestStack *A, *B;

XWindowList *mine;
WindowList *yours;

void StartTest ()
{
   A = new TestStack;
   B = new TestStack;
   mine = new XWindowList ();
   yours = new WindowList ();
}

void StopTest ()
{
   delete A;
   delete B;
   delete mine;
   delete yours;
}

void Travmine ( XWindow * aWin )
{
   A->Add (aWin->GetData ());
}

void Travyours ( Window * aWin )
{
   B->Add (aWin->GetData ());
}

void DoTest ()
{
   A->Clear ();
   B->Clear ();
   mine->Traverse (&Travmine);
   yours->Traverse (&Travyours);
   CheckStacks (A, B);
}

void AddBoth ( char *s )
{
   mine->AddWindow (s);
   yours->AddWindow (s);
}

void DeleteBoth ()
{
   mine->DeleteWindow ();
   yours->DeleteWindow ();
}

void NextBoth ()
{
   mine->NextWindow ();
   yours->NextWindow ();
}

void PrevBoth ()
{
   mine->PrevWindow ();
   yours->PrevWindow ();
}

char *Element[] = {"One", "Two", "Three", "Four", "Five"};

int main ()
{
   int i;

   cout << "Testing AddWindow/Traversal:\n";
   StartTest ();

   cout << "Testing empty lists ... ";
   DoTest ();

   AddBoth (Element[0]);
   cout << "\nTesting one element ... ";
   DoTest ();

   AddBoth (Element[1]);
   cout << "\nTesting two elements ... ";
   DoTest ();

   AddBoth (Element[2]);
   cout << "\nTesting three elements ... ";
   DoTest ();

   StopTest ();

   cout << "\n\nTesting DeleteWindow:\n";
   StartTest ();

   for ( i=0; i<3; i++ )
      AddBoth (Element[i]);
   cout << "Add 3 elements ... ";
   DoTest ();

   DeleteBoth ();
   cout << "\nRemove first element ... ";
   DoTest ();

   DeleteBoth ();
   cout << "\nRemove second element ... ";
   DoTest ();

   DeleteBoth ();
   cout << "\nRemove third element ... ";
   DoTest ();

   DeleteBoth ();
   cout << "\nRemove fourth element ... ";
   DoTest ();

   DeleteBoth ();
   cout << "\nRemove fifth element ... ";
   DoTest ();

   StopTest ();

   cout << "\n\nTesting NextWindow:\n";
   StartTest ();

   NextBoth ();
   cout << "Empty list ... ";
   DoTest ();

   AddBoth (Element[0]);
   NextBoth ();
   cout << "\nFirst next on single window ... ";
   DoTest ();

   NextBoth ();
   cout << "\nSecond next on single window ... ";
   DoTest ();

   AddBoth (Element[1]);
   NextBoth ();
   cout << "\nFirst next on two windows ... ";
   DoTest ();

   NextBoth ();
   cout << "\nSecond next on two windows ... ";
   DoTest ();

   NextBoth ();
   cout << "\nThird next on two windows ... ";
   DoTest ();

   StopTest ();

   cout << "\n\nTesting PrevWindow:\n";
   StartTest ();

   PrevBoth ();
   cout << "Empty list ... ";
   DoTest ();

   AddBoth (Element[0]);
   PrevBoth ();
   cout << "\nFirst prev on single window ... ";
   DoTest ();

   PrevBoth ();
   cout << "\nSecond prev on single window ... ";
   DoTest ();

   AddBoth (Element[1]);
   PrevBoth ();
   cout << "\nFirst prev on two windows ... ";
   DoTest ();

   PrevBoth ();
   cout << "\nSecond prev on two windows ... ";
   DoTest ();

   PrevBoth ();
   cout << "\nThird prev on two windows ... ";
   DoTest ();

   StopTest ();

   cout << "\n\nTesting large memory allocation:\n";
   StartTest ();

   for ( i=0; i<10000; i++ )
      AddBoth (Element[i % 5]);
   cout << "Adding 10000 elements ... ";
   DoTest ();

   for ( i=0; i<10000; i++ )
      DeleteBoth ();
   cout << "\nDeleting 10000 elements ...";
   DoTest ();

   StopTest ();

   cout << "\n\nTesting random sequence of commands:\n";
   StartTest ();

   int cc[4];
   cc[0] = 0; cc[1]=0; cc[2]=0; cc[3]=0;
   for ( i=0; i<10000; i++ )
   {
      long t = rand ();
      if (t < 8192)
      {
         AddBoth (Element[t % 5]); cc[0]++; 
      }
      else if (t < 16384)
      {
         DeleteBoth (); cc[1]++;
      }
      else if (t < 24576)
      {
         NextBoth (); cc[2]++;
      }
      else
      {
         PrevBoth (); cc[3]++;
      }
   }
   cout << "10000 operations ... " << cc[0] << "/" << cc[1] << "/" 
        << cc[2] << "/" << cc[3] << " ";
   DoTest ();

   StopTest ();

   cout << "\n\n";
}