#include <cstdlib>
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

class IntLinkedList
{
    private:
        struct Node
        {
            Node(int elt) : data(elt), next(NULL) {};
            int data;
            Node *next;
        };
        
        Node *head;
        Node *tail;
        int  cardinality;
    
    public: 
        IntLinkedList() : head(NULL), tail(NULL), cardinality(0) {}
                
        IntLinkedList(const IntLinkedList &ill);
        ~IntLinkedList();
        IntLinkedList& operator=(const IntLinkedList & rhs);
        
        void push_back(int elt);
        void pop_back();
        // erase first occurrence of the element.
        bool erase(int elt);         
        int &at(int i);          
        int size() const;
        bool empty() const;
        string toString() const;    
        
        void clear();          
};

int main(){
    IntLinkedList list1; 
    cout << "The size of the list is " << list1.size() << endl;   
    list1.push_back(20);    
    list1.push_back(30);    
    list1.push_back(40);
    list1.push_back(30);
    cout << list1.toString() << endl;
    cout << "The size of list 1 is " << list1.size() << endl;     
    list1.erase(30);     
    cout << list1.toString() << endl; 
    cout << "The size of  list 1 is " << list1.size() << endl;  
    list1.push_back(123);
    cout << list1.toString() << endl; 
    cout << "The size of  list 1 is " << list1.size() << endl;  
       
    IntLinkedList list2(list1);
    list2.pop_back();
     
           
    cout << list1.toString() << endl;
    cout << list2.toString() << endl;  
    
    IntLinkedList list3;
    list3 = list1;
    list3.push_back(45000);
    cout << list1.toString() << endl;
    cout << list3.toString() << endl;
    
    list1.clear();
    cout << list1.toString() << endl;    
    system("pause");
    return 0;
}

IntLinkedList::~IntLinkedList(){
    clear();
}
IntLinkedList::IntLinkedList(const IntLinkedList & ill) {
   head = tail = NULL;
   cardinality = 0;
   for(Node *cursor = ill.head; cursor != NULL; cursor = cursor -> next){                     
            push_back(cursor -> data);        
    }    
}   
    
IntLinkedList & IntLinkedList::operator=(const IntLinkedList & rhs){
    // checking for self assignment.	    
	if(this == &rhs) {        
         return *this;
    }    
    clear();
    for(Node *cursor = rhs.head; cursor != NULL; cursor = cursor -> next) {
       
        push_back(cursor -> data);
    }
    return *this;
}    
    
bool IntLinkedList::empty() const{
    return cardinality == 0;
}
int IntLinkedList::size() const{
    return cardinality;
}
void IntLinkedList::push_back(int elt){
    Node *newNode = new Node(elt);
    if(!empty()){
        tail -> next = newNode;
        tail = newNode;
    }else{
        head = tail = newNode;
    }    
    ++cardinality;    
}
void IntLinkedList::clear() {
    for(Node *cursor = head; cursor != NULL; cursor = head){
        head = cursor -> next;
        delete cursor;
    }
    tail = NULL;
    cardinality = 0;
}   

string IntLinkedList::toString() const{
    if(empty()){
        return "List is empty";
    }
    
    ostringstream str;
    Node *cursor = head;
    while(cursor != NULL){       
        str << cursor -> data << ' ';
        cursor = cursor -> next;
    }
    return str.str();     
}
bool IntLinkedList::erase(int elt)
{
    // if list is empty nothing to delete.   
   if(empty()){
        return false;
   }      
   Node *cursor = head;  
   // if the node containing the element is at the head 
   if(head -> data == elt){
        // if the size is 1, create an empty list        
        if(size() == 1){           
            head = tail = NULL;
        }else{              
            head = head -> next;
        }
        --cardinality;
        delete cursor;
        return true;
    }    
   
   // we want to stop at the node before the node that contains
   // the element.      
   // this loop will terminate if we hit the tail or we arive
   // at the node before the node that contains the element 
   while(cursor != tail && cursor -> next -> data != elt) {
        cursor = cursor -> next;
   }  

   if(cursor == tail){
        // if the tail contains the element call pop_back
        if(tail -> data == elt){ 
            pop_back();
            return true;
        }
         return false;
    }
      
   Node *temp = cursor -> next;
   cursor -> next = temp -> next; 
   delete temp;
   --cardinality;
   return true;
}
void IntLinkedList::pop_back(){
    
	// if empty nothing to pop
	if(empty()){
         return;
    }
	// if head is equal to tail, then the list has one node
	if(head == tail){
        delete head;
        head = tail = NULL;
    }
	// else we need to find the node before the tail	
	else{
        Node *cursor = head;
		while(cursor -> next != tail) {
             cursor = cursor->next;
        }
        
	    // if cursor -> next is equal to tail then cursor is pointing
		// to the node just before the tail.
    	delete tail;
	    //cursor becomes the new tail
		tail = cursor;		
	    tail -> next = NULL;
    }
    --cardinality;
	return;
}
int & IntLinkedList::at(int index){
    Node *cursor = head;
    for(int i = 0; i < index; i++) {
        cursor = cursor -> next;
    }    
    return cursor -> data;
}