//////////////////////////////////////////////////////////////////////////////////////////////
//                                                                                          //
//                 CSE 428, Spring 2001, code for first exercise of HW #3                   //
//                                                                                          //
//              File S3_test.C (old A3_code_stack.C plus additional test cases)             //
//                                                                                          //
//////////////////////////////////////////////////////////////////////////////////////////////
//                                                                                          //
//                           Please compile your program by g++.                            //
//                          Please don't modify given interfaces.                           //
//                                                                                          //
//////////////////////////////////////////////////////////////////////////////////////////////


#include <iostream.h>
using namespace std;

//////////////////////////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////////////////////////
// The following three classes have the purpose of keeping counters which keep trace of
// the number of allocated objects of class element, stack1 and stack2. They are used to 
// check for memory leaks

class element_base  // auxiliary class to check memory leaks
{
   static int count;

public:

   element_base(){ count++; }
  
   ~element_base(){ count--; }
  
   static void setCount(int c){ count = c; }

   static int getCount(){ return count; }

};


class stack1_base // auxiliary class to check memory leaks
{
   static int count;

public:

   stack1_base() { count++; }
  
   ~stack1_base(){ count--; }
 
   static void setCount(int c){ count = c; }

   static int getCount(){ return count; }

};


class stack2_base // auxiliary class to check memory leaks
{
   static int count;

public:

   stack2_base(){ count++; }
  
   ~stack2_base(){ count--; }

   static void setCount(int c){ count = c; }  

   static int getCount(){ return count; }

};

int stack2_base::count;           

int stack1_base::count;             

int element_base::count; 

//////////////////////////////////////////////////////////////////////////////////////////////

class element: element_base
 { // This is an auxiliary class for stack1. It defines the elements of stack1

  
   int info;        // information content of an element
   element* next;   // pointer to the next (previously inserted) element in the stack

   element(int n, element* e)  // Constructor method for an element
   {
      info = n;
      next = e;
   }

   friend class stack1;
   // stack1 is a friend class: it can access all (private) fields and members of element
};

/////////////////////////////////////////////////////////////////////////////////////////////

class stack1: stack1_base 
{              // In this implementation, a stack is an object "stack1" which contains
               // the pointer to the first element (top) of a linked list of elements
private:

   element* top;  // pointer to the top element in the stack

public:

   stack1()  // Constructor of an empty stack
   {
      top = NULL;
   }

   void push(int n) // insert an element at the top of the stack
   {
      top = new element(n,top);
   }

   //////////////////////  THE FOLLOWING METHODS ARE TO BE DEFINED /////////////////////////

   ~stack1(); // destructor

   void pop(); // removes the element at the top

   int position(int x);
   // This function returns the position in the stack of the x last inserted and not yet
   // removed:
   // It returns 1 if x is at the top, 2 if x is in the second element from the top,  etc.
   // If x is not in the stack, it returns 0.
};

///////////////////////////////////////////////////////////////////////////////////////////////

class stack2: stack2_base
{              // In this implementation, an object "stack2" is the first
               // element of a linked list of elements. The significant part
               // of the stack starts from the second element of the list (top)
               // the info field in the first element of the list is not used
private:
     
   int info;     // information content of an element of the stack
   stack2* next; // pointer to the next element

   stack2(int n, stack2* s) // Private constructor for the insertion of a new element
   {
      info = n;
      next = s;
   }

public:
   stack2()  // Constructor. It constructs a stack whose significant part is empty
   {
      next = NULL;
   }

   void push(int n) // insert an element at the top of the stack
   {
      next = new stack2(n,next);
   }

   ~stack2() // destructor
   {
      delete next;
   }

   //////////////////////  THE FOLLOWING METHODS ARE TO BE DEFINED ////////////////////////

   void pop(); // remove the element at the top
   // Note: be careful when you define this method: Because of the way the destructor 
   // of class stack2 is defined, a naive definition of pop() may remove all the stack 
   // and cause dangling reference

   int position(int x);
   // This function returns the position in the stack of the x last inserted and not yet
   // removed:
   // It returns 1 if x is at the top of the stack, namely, in the second element of the
   // linked list. It returns 2 if x is in the third element of the list,  etc.
   // If x is not in the list, it returns 0.
};

///////////////////////////////////////////////////////////////////////////////////////////////
// Examples of use of the stacks

int test1()
{

   //////////////////////////////////////////////////////////////////////////////////////////
   // Initialization of the counters for checking the memory leaks

   element_base::setCount(0);
   stack1_base::setCount(0);
   stack2_base::setCount(0);

   //////////////////////////////////////////////////////////////////////////////////////////
   // Same operations on a stack of type stack1
   cout << "------ Test 1 (basic: 35 points)-------" << endl;

   stack1* s1 = new stack1();
  
   //cout << "Stack1 created. Pushing the numbers 5, 5, 6 and 7 \n";
   s1->push(5);
   s1->push(5);
   s1->push(6);
   s1->push(7);
   //cout << "Testing the presence of number 5 \n";
   cout << 5 << " is in position(3) " << s1->position(5) << "\n";  
                //It should print 3

   //cout << "Popping one element from the stack1 \n";
   s1->pop();   //It should eliminate the top element without leaving memory leaks
                //and without creating dangling references

   //cout << "Testing the presence of number 5 \n";
   cout << 5 << " is in position(2) " << s1->position(5) << "\n";  
                //It should print 2

   delete s1;   //It should eliminate the stack without leaving memory leaks
   s1 = NULL;

   //////////////////////////////////////////////////////////////////////////////////////////
   // Now we perform similar operations on a stack of type stack2

   stack2* s2 = new stack2();
   //cout << "\nStack2 created. Pushing the numbers 5, 6 and 6 \n";
   s2->push(5);
   s2->push(6);
   s2->push(6);

   //cout << "Testing the presence of number 6 \n";
   cout << 6 << " is in position(1) " << s2->position(6) << "\n";  
                //It should print 1

   //cout << "Popping an element from the stack2 \n";
   s2->pop();   //It should eliminate the top element without leaving memory leaks
                //and without creating dangling references

   //cout << "Pushing the numbers 7, 8 and 9 \n";
   s2->push(7);
   s2->push(8);
   s2->push(9);

   //cout << "Testing the presence of number 6 \n";
   cout << 6 << " is in position(4) " << s2->position(6) << "\n";  
                //It should print 4

   delete s2;   //It eliminates the stack without leaving memory leaks
   s2 = NULL;

   //////////////////////////////////////////////////////////////////////////////////////////
   // Print the values of the counters to verify that there are no memory leaks. 
   // In all the three cases, the value printed should be 0

   //cout << "\nTesting the presence of memory leaks \n";
   //cout << "element count: " << element_base::getCount() << endl;
   //cout << "stack1  count: " << stack1_base::getCount() << endl;
   //cout << "stack2  count: " << stack2_base::getCount() << endl;
   if  (element_base::getCount()+stack1_base::getCount()+stack2_base::getCount()==0)
      cout << "No memory leaks. Great! \n";
   else 
      cout << "Warning: some memory leaks!\n";
}

///////////////////////////////////////////////////////////////////////////////////////////////

int test2()
{


   element_base::setCount(0);
   stack1_base::setCount(0);
   stack2_base::setCount(0);

   cout << "------- Test 2 (position should return 0) --------" << endl;

   stack1* s1 = new stack1();
  
   //cout << "Stack1 created. Pushing the numbers 5, 5, 6 and 7 \n";
   s1->push(5);
   s1->push(5);
   s1->push(6);
   s1->push(7);

   cout << 9 << " is in position(0) " << s1->position(9) << endl;

   delete s1;   //It should eliminate the stack without leaving memory leaks
   s1 = NULL;

   //////////////////////////////////////////////////////////////////////////////////////////
   // Now we perform similar operations on a stack of type stack2

   stack2* s2 = new stack2();
   //cout << "\nStack2 created. Pushing the numbers 5, 6 and 6 \n";
   s2->push(5);
   s2->push(5);
   s2->push(6);
   s2->push(7);

   //cout << "Testing the presence of number 6 \n";
   cout << 9 << " is in position(0) " << s2->position(9) << "\n";  
                //It should print 0


   delete s2;   //It eliminates the stack without leaving memory leaks
   s2 = NULL;

   //////////////////////////////////////////////////////////////////////////////////////////
   // Print the values of the counters to verify that there are no memory leaks. 
   // In all the three cases, the value printed should be 0

   //cout << "\nTesting the presence of memory leaks \n";
   //cout << "element count: " << element_base::getCount() << endl;
   //cout << "stack1  count: " << stack1_base::getCount() << endl;
   //cout << "stack2  count: " << stack2_base::getCount() << endl;
   if  (element_base::getCount()+stack1_base::getCount()+stack2_base::getCount()==0)
      cout << "No memory leaks. Great! \n";
   else 
      cout << "Warning: some memory leaks!\n";

}

int test3()
{
   // Initialization of the counters for checking the memory leaks

   element_base::setCount(0);
   stack1_base::setCount(0);
   stack2_base::setCount(0);

   cout << "------- Test 3 (pop from an empty stack) --------" << endl;

   // test stack1
   stack1* s1 = new stack1();
   //cout << "Stack1 created. Pushing the numbers 5, 5, 6 and 7 \n";
   s1->push(5);
   s1->push(5);
   s1->push(6);
   s1->push(7);
   s1->pop();
   s1->pop();
   s1->pop();
   s1->pop();
   cout << "Stack1 is now empty" << endl;
   
   cout << "Pop from Stack1(empty)" << endl;
   s1->pop();
   cout << endl << "-- OK --" << endl;

   cout << "push 1 into the Stack1" << endl;
   s1->push(1);
   cout << endl << "-- OK --" << endl;
   cout << 1 << " is in position(1) " << s1->position(1) << "\n";  

   delete s1;   //It should eliminate the stack without leaving memory leaks
   s1 = NULL;

   
   // test satck2
   stack2* s2 = new stack2();
   //cout << "Stack2 created. Pushing the numbers 5, 5, 6 and 7 \n";
   s2->push(5);
   s2->push(5);
   s2->push(6);
   s2->push(7);
   s2->pop();
   s2->pop();
   s2->pop();
   s2->pop();
   //cout << "Stack2 is now empty" << endl;
   
   cout << "Pop from Stack2(empty)" << endl;
   s2->pop();
   cout << endl << "-- OK --" << endl;

   cout << "push 1 into the Stack2" << endl;
   s2->push(1);
   cout << endl <<"-- OK --" << endl;
   cout << 1 << " is in position(1) " << s2->position(1) << "\n";  
                //It should print 1
   delete s2;   //It should eliminate the stack without leaving memory leaks
   s2 = NULL;

   // Print the values of the counters to verify that there are no memory leaks. 
   // In all the three cases, the value printed should be 0
   //cout << "\nTesting the presence of memory leaks \n";
   //cout << "element count: " << element_base::getCount() << endl;
   //cout << "stack1  count: " << stack1_base::getCount() << endl;
   //cout << "stack2  count: " << stack2_base::getCount() << endl;
   if  (element_base::getCount()+stack1_base::getCount()+stack2_base::getCount()==0)
      cout << "No memory leaks. Great! \n";
   else 
      cout << "Warning: some memory leaks!\n";
}

int test4()
{
   // Initialization of the counters for checking the memory leaks

   element_base::setCount(0);
   stack1_base::setCount(0);
   stack2_base::setCount(0);

   cout << "------- Test 4 (position in an empty stack) --------" << endl;

   // test stack1
   stack1* s1 = new stack1();
   //cout << "Stack1 created. Pushing the numbers 5, 5, 6 and 7 \n";
   s1->push(5);
   s1->push(5);
   s1->push(6);
   s1->push(7);
   s1->pop();
   s1->pop();
   s1->pop();
   s1->pop();
   cout << "Stack1 is now empty" << endl;
   cout << 1 << " is in position(0) " << s1->position(1) << "\n";  
                //It should print 0
   delete s1;   //It should eliminate the stack without leaving memory leaks
   s1 = NULL;

   
   // test satck2
   stack2* s2 = new stack2();
   //cout << "Stack2 created. Pushing the numbers 5, 5, 6 and 7 \n";
   s2->push(5);
   s2->push(5);
   s2->push(6);
   s2->push(7);
   s2->pop();
   s2->pop();
   s2->pop();
   s2->pop();
   cout << "Stack2 is now empty" << endl;
   cout << 1 << " is in position(0) " << s2->position(1) << "\n";  
                //It should print 1
   delete s2;   //It should eliminate the stack without leaving memory leaks
   s2 = NULL;

   // Print the values of the counters to verify that there are no memory leaks. 
   // In all the three cases, the value printed should be 0
   //cout << "\nTesting the presence of memory leaks \n";
   //cout << "element count: " << element_base::getCount() << endl;
   //cout << "stack1  count: " << stack1_base::getCount() << endl;
   //cout << "stack2  count: " << stack2_base::getCount() << endl;
   if  (element_base::getCount()+stack1_base::getCount()+stack2_base::getCount()==0)
      cout << "No memory leaks. Great! \n";
   else 
      cout << "Warning: some memory leaks!\n";

}

main()
{
#ifdef T1
  test1();
#endif
#ifdef T2
  test2();
#endif
#ifdef T4
  test4();
#endif
#ifdef T3
  test3();
#endif
}