// linklist2.cpp 		By: Aiman Hanna -  ©1993-2003 Aiman Hanna

// This program shows the creation and manipulation of linked lists.
// The program shows many examples of linked lists manipulations
// such as insertion and deletion from the list.  
// In addition the program shows the use of the 'this' pointer, and the 
// overloading of some of the C++ operators. 
//
// Key Pints: 	1) Linked list data Structure.
//		2) 'this' pointer.
//		3) 'friend' classes.
//		4) Operator Overloading. 
//		5) Pass by reference and pass by value
//
// 	Question: What does this program simulate: 
//			a Stack, a Queue, ...etc.?

#include "linklist2.h"

Node::Node()
{
 next = NULL;	
}


ostream& operator<< ( ostream& os, IntList lst )
{

  Node *ndptr = lst.first;

  while( ndptr )
  {
   	os << ndptr -> value;
	os << " ----> ";
	ndptr = ndptr -> next;
  }
  	os << "X" << endl;		 // 'X" here indicates NULL in the output.
  return os;		
}



IntList::IntList()
{
cout << " Executing default constructor of IntList" << endl;
 first = last = current = NULL;
 size = 0;
}





IntList::IntList( const IntList& lst )
{
cout << " Executing parameterized constructor of IntList" << endl;
  // Copy constructor. Expects a linked list as a parameter, Create 
  // a new identical list

  
  Node *srcptr = lst.first,  		// srcptr points to the passed list
       *destptr;	     		    // destptr points to the new created list

  if ( srcptr == NULL )	      	// The list that will be copied 'lst' is itself empty.
  {
   first = last = current = NULL;
   				// current points to any node in the list. Any
				// insertion or deletion will be based on the 
				// node pointed by current. 
   size = 0;
  }
  else 				// the source list has one or more nodes
  { 
   destptr = new Node;
   destptr -> value = srcptr -> value;
   
   if ( srcptr == lst.current )       	// detect where current is pointing in the 
   	current = destptr;	      		    // passed list
   
   first = destptr;
   srcptr = srcptr -> next;

   while( srcptr )
	{
      destptr -> next = new Node;    	// create a new node and move destptr to it
      destptr = destptr -> next;

      if ( srcptr == lst.current )   	// detect where current is pointing in the
      	   current = destptr;			// passed list

      destptr -> value = srcptr -> value;  // copy the value from the source node

      srcptr = srcptr -> next;			// Advance srcptr

	}

   // last node
   destptr -> next = NULL;	
   last = destptr;

   size = lst.size;	 		// copy the size from the source list
  }
}





IntList& IntList::operator= ( const IntList& lst )
{
 // Copy one list to another. 

 // first destroy the old list and construct a new one
 Node *destptr = first;		// Two pointers are needed to delete the list.
							// destptr and current will be used for that.
 current = first;		
 while ( current )
 {
  current = current -> next;
  delete destptr;
  destptr = current;
 }

 Node *srcptr = lst.first;		// a pointer to the src list (the list to be copied)

 if ( srcptr == NULL )	      	// The list that will be copied 'lst' is itself empty.
  {
   first = last = current = NULL;
   size = 0;
  }
  else
  {
   destptr = new Node;
   destptr -> value = srcptr -> value;
 
   if ( srcptr == lst.current )
   	current = destptr;
 
   first = destptr;
   srcptr = srcptr -> next;

   while( srcptr )
   {
      destptr -> next = new Node;
      destptr = destptr -> next;
 
      if ( srcptr == lst.current )
      	   current = destptr;
 
      destptr -> value = srcptr -> value;
 
      srcptr = srcptr -> next;

   }
 
   destptr -> next = NULL;	// last node
   last = destptr;
   size = lst.size;

  }

  return *this;
}






void IntList::InsertByBadImplementation( int x )
{
 // Insert x at the current position. Does this function work?
 // If so, why its implementation is considered bad?

 Node *destptr = new Node;	
 if ( current == NULL ) 	// list is empty
 {
    destptr -> value = x;
    destptr -> next = NULL;
    current = first = last = destptr;
 }
 else	     			// list is not empty. Always insert before the 
 {						// node currently pointed by current. 
    destptr -> value = current -> value;

    destptr -> next = current -> next;

    current -> value = x;

    current -> next = destptr;  

    if ( current == last ) 		// last new node was inserted at the end
         last = destptr;
 }
 size++;				// increment the list size anyway as you added one node.
}



void IntList::Insert( int x )
{
 // Insert x at the current position.

 Node *destptr = new Node,
      *tmpptr;	      		// tmpptr will be used to find where current is.

      destptr -> value = x;		// Just assign the value of the new node. 
      				// We still need to see where this node will be pointing,
					// and what will be pointing to that node.
		
 if ( first == NULL ) 		// list is empty
 {  
    destptr -> next = NULL;
    current = first = last = destptr;
 }
 else				// list is not empty.
 {
     if ( current == first ) 		// current points to the first node.
     {
      destptr -> next = current;
      current = first = destptr;
     }
     else  				// current is not pointing to the first node.
     {
        tmpptr = first;		// Point to the first node in the list.
        while ( tmpptr -> next != current )  	// Move tmmptr ahead until the previous
   				             	// node to where current is pointing. 	
        {
         tmpptr = tmpptr -> next;
        }
  
  	tmpptr -> next = destptr;
	destptr -> next = current;
	current = destptr;
     }       
  
 }
 size++;		// increment the list size anyway as you added one node.
}






void IntList::Remove( )
{
 // Remove the node of the current position
 
 if ( current == NULL )  		
 {
     cerr << " List is empty. Will not remove any nodes!! " << endl;
 }
 else			// List is not empty
 {
  if ( current == first )
  {
     current = current -> next;
     delete first;
     first = current;
  }
  else
  {
     Node *destptr = first;
     while ( destptr -> next != current )
     		destptr = destptr -> next;
     
     destptr -> next = current -> next;
     delete current;
     current = destptr -> next;
  }
  size--;
 }
} 


void IntList::Head()
{
 // Reset current to point to the first node
 current = first;
}


void IntList::Tail()
{
 // Reset current to point to the last node
 current = last;
}



IntList& IntList::operator-- ()
{
 // Move current one node towards the head of the list
  if ( current != first )
 {
     Node *destptr = first;
     while ( destptr -> next != current )
     		destptr = destptr -> next;
     
     current = destptr;
  }
  return *this;
}


IntList& IntList::operator-- (int)
{
 // Will this code work? Why?
 static IntList templist = *this; 
 // Move current one node towards the head of the list 
 if ( current != first )
 {
     Node *destptr = first;
     while ( destptr -> next != current )
     		destptr = destptr -> next;
     
     current = destptr;
  }
  return templist;

}




IntList& IntList::operator++ ()
{
 // Move current one node towards the end of the list

  if ( current != last )
	current = current -> next;

  return *this;
}

IntList& IntList::operator++ (int)
{
 // Move current one node towards the end of the list
  static IntList templist = *this; 
  if ( current != last )
	current = current -> next;

  return templist;
}



int IntList::Retrieve() const
{
 // Return the value of the node pointed by current

 if ( current )
 	return current -> value;
 else
 {
  	cerr << " Error.. Can not retrieve a value from an empty list. " << endl;
	cout << " -1 is returned as an indication of retrieving error." << endl;
	return -1;
 }

}



void IntList::Update( int x )
{
// Change the value of the node pointed by current

 if ( current )
 	current -> value = x;
  else
  	cerr << " Error.. The list is empty, can not update. " << endl;

}



int IntList::Length()
{
 // Get the length of the list

 return size;
}




IntList::~IntList()
{
// de-allocate all dynamically allocated memory before terminating 
// to eliminate memory leak. 

Node *destptr = first;		// Two pointers are needed to delete the list.
				// destptr and current will be used for that.
 current = first;		
 while ( current )
 {
  current = current -> next;
  delete destptr;
  destptr = current;
 }
 first = last = current = NULL;
 size = 0;
 
}






int main()
{
 IntList lis1, lis2, lis3;

 // Test the insertion function

 lis1.Insert(3);
 lis1.Insert(5);
 lis1.Insert(9);
 lis1.Insert(2);
 lis1.Insert(8);

 cout << endl << " List1 is: " << lis1 << endl;

 // Test the overloaded operator=
 lis2 = lis1;

 cout << endl << " List2 is: " << lis2 << endl;

 // Test the Retrieve function. This will indicate where is the current position
 // also. We keep track of that when continue to test the rest of the functions.

 cout << " The value pointed by current position of List2 is: " 
      << lis2.Retrieve() << endl;

 // Test the overloaded operator++ & operator--
 lis1++; lis1++; lis1++;
 lis2++; 
 
 cout << " The value pointed by current position of List1 after 3 forward moves is: " 
      << lis1.Retrieve() << endl;
 
 cout << " The value pointed by current position of List2 after 1 forward move is: " 
      << lis2.Retrieve() << endl;

 lis1--;
 cout << " The value pointed by current position of List1 after 1 backward move is: " 
      << lis1.Retrieve() << endl;
 
  
 // Test the deletion function
 lis1.Remove();
 cout << "\n List1 after removing a node is: " << lis1 << endl;

 // Test the Update function
 lis2.Update( 18 );
 cout << "\n List2 after updating a node is: " << lis2 << endl;

 cout << " The value pointed by current position of List1 is: " 
      << lis1.Retrieve() << endl;

 cout << " The value pointed by current position of List2 is: " 
      << lis2.Retrieve() << endl;


 // Check some of the special cases
 cout << " \n \n Now some of the special cases will be checked.. " << endl;
 lis1--; 
 cout << " The value pointed by current position of List1 is: " 
      << lis1.Retrieve() << endl;
 lis1--; 
 cout << " The value pointed by current position of List1 is: " 
      << lis1.Retrieve() << endl;

 lis1--; 
 cout << " The value pointed by current position of List1 is: " 
      << lis1.Retrieve() << endl;
 
 lis1--; 
 cout << " The value pointed by current position of List1 is: " 
      << lis1.Retrieve() << endl;

 // Update, remove and retrieve from an empty list
 cout << endl << " List3 is: " << lis3 << endl;

 lis3.Update( 10 );
 lis3.Remove();
 lis3.Retrieve();

 // Now test the creation with the other constructor
 IntList lis4( lis1 );
 
 cout << endl << " List4 is: " << lis4 << endl;
 lis4.Head();
 cout << " The value pointed by current position of List4 after moving to the head is: " 
      << lis4.Retrieve() << endl;
 cout << " \n The length of List4 is: " << lis4.Length() << endl;
 lis4.Tail();
 cout << " The value pointed by current position of List4 after moving to the tail is: " 
      << lis4.Retrieve() << endl;

 // Now test the InsertByBadImplementation function
 IntList lis5;
 
 lis5.InsertByBadImplementation(3);
 lis5.InsertByBadImplementation(5);
 lis5.InsertByBadImplementation(9);
 lis5.InsertByBadImplementation(2);
 lis5.InsertByBadImplementation(8);

 cout << endl << " List5, which was created by 'InsertByBadImplementation' function, is: "
 								<< lis5 << endl;;

 cout << endl << " List1 is: " << lis1 << endl; 

 ++lis1;
 ++lis1;

 IntList lis11 = lis1; // make a copy of lis1 at this moment
 IntList lis6 = --lis1; 
 

 cout << " List1 after decremental is: " << lis1 << endl; 
 cout << " List1 current point is: " << lis1.Retrieve() << endl; 
 cout << " List6 current point is: " << lis6.Retrieve() << endl; 

 
 cout << endl << " List1 is: " << lis1 << endl; 
 IntList lis7 = lis11--;

 cout << " List11 after decremental is: " << lis11 << endl; 
 cout << " List11 current point is: " << lis11.Retrieve() << endl; 
 cout << " List7 current point is: " << lis7.Retrieve() << endl; 

 return 0;
}









// The result of running the program is:

/*
 Executing default constructor of IntList
 Executing default constructor of IntList
 Executing default constructor of IntList
 Executing parameterized constructor of IntList

 List1 is: 8 ----> 2 ----> 9 ----> 5 ----> 3 ----> X

 Executing parameterized constructor of IntList

 List2 is: 8 ----> 2 ----> 9 ----> 5 ----> 3 ----> X

 The value pointed by current position of List2 is: 8
 Executing parameterized constructor of IntList
 The value pointed by current position of List1 after 3 forward moves is: 5
 The value pointed by current position of List2 after 1 forward move is: 2
 Executing parameterized constructor of IntList
 The value pointed by current position of List1 after 1 backward move is: 9
 Executing parameterized constructor of IntList

 List1 after removing a node is: 8 ----> 2 ----> 5 ----> 3 ----> X

 Executing parameterized constructor of IntList

 List2 after updating a node is: 8 ----> 18 ----> 9 ----> 5 ----> 3 ----> X

 The value pointed by current position of List1 is: 5
 The value pointed by current position of List2 is: 18


 Now some of the special cases will be checked..
 The value pointed by current position of List1 is: 2
 The value pointed by current position of List1 is: 8
 The value pointed by current position of List1 is: 8
 The value pointed by current position of List1 is: 8
 Executing parameterized constructor of IntList

 List3 is: X

 Error.. The list is empty, can not update.
 List is empty. Will not remove any nodes!!
 Error.. Can not retrieve a value from an empty list.
 -1 is returned as an indication of retrieving error.
 Executing parameterized constructor of IntList
 Executing parameterized constructor of IntList

 List4 is: 8 ----> 2 ----> 5 ----> 3 ----> X

 The value pointed by current position of List4 after moving to the head is: 8

 The length of List4 is: 4
 The value pointed by current position of List4 after moving to the tail is: 3
 Executing default constructor of IntList
 Executing parameterized constructor of IntList

 List5, which was created by 'InsertByBadImplementation' function, is: 8 ----> 2
 ----> 9 ----> 5 ----> 3 ----> X

 Executing parameterized constructor of IntList

 List1 is: 8 ----> 2 ----> 5 ----> 3 ----> X

 Executing parameterized constructor of IntList
 Executing parameterized constructor of IntList
 Executing parameterized constructor of IntList
 List1 after decremental is: 8 ----> 2 ----> 5 ----> 3 ----> X

 List1 current point is: 2
 List6 current point is: 2
 Executing parameterized constructor of IntList

 List1 is: 8 ----> 2 ----> 5 ----> 3 ----> X

 Executing parameterized constructor of IntList
 Executing parameterized constructor of IntList
 List11 after decremental is: 8 ----> 2 ----> 5 ----> 3 ----> X

 List11 current point is: 2
 List7 current point is: 5
 */