/*
 *CS 212 
 *Linked List using class
 *Programmer: Ali Sabbir
 */

#include<iostream>
using namespace std;

struct info{
	int id;
	char name[25];
};

typedef info datatype;

/*Global Declaration of data types*/
struct node{
	datatype item;
	node *next;
};

typedef node* ptrtype;

/*Now the class declaration*/
class linked_list{
	private:
		ptrtype head;
		/*A function that returns a pointer
		 *to the i'th node in the linked list
		 */
		ptrtype ptr_to(int position); 
		int size;

	public:
		/*Default constructor*/
		linked_list();
		/*Copy Constructor*/
		linked_list(const linked_list& source);
		/*Destructor*/
		~linked_list();

		/*A function that returns the current
		 *size of linked list*/
		int list_size();

		/*A function that inserts a node in i'th 
		 *position and initializes it with 
		 *some given value 
		 */
		void list_insert(int position, datatype &item);

		/*A function that displays the item of i'th node*/
		void list_display(int position);

		/*A function that deletes a node from the linked list
		*The position of the node to be removed is given
		*/
		void list_delete(int position, datatype &item);
		
		

};


linked_list::linked_list(){
	cout<<"Constructing a linked list."<<endl<<endl;
	head = NULL;
	size = 0;
}

linked_list::linked_list(const linked_list& source){
	size =0;
	if(!source.head){
		head =NULL;
	}
	else{
		size++;
		ptrtype cur, aft;
		head = new node;
		head -> item = source.head ->item;
		cur = head;
		aft=source.head->next;
		while(aft){
			size++;
			cur->next=new node;
			cur=cur->next;
			cur->item=aft->item;
			aft = aft->next;

		}
		cur->next = NULL;


	}
}



linked_list::~linked_list(){
	datatype x;
	cout<<endl<<"Destructing ....."<<endl;
	while(size>0){cout<<"Deleting\n";list_delete(1,x);}
}

int linked_list::list_size(){
	
	return size;
}

ptrtype linked_list::ptr_to(int pos){
	ptrtype cur=head;
	//First check for the validity of the position
	if(pos<1 || pos > list_size()){
		cout<<"OOPS pos is "<<pos<<"\n";
		return NULL;
	}
	else{
		for(int index =1; index <pos; ++index) cur = cur -> next;
		return cur;
	}
}

void linked_list::list_insert(int pos, datatype &item){
	/*First validity of the position*/
	if(pos<1 || pos>list_size()+1) return ;
	else{
		ptrtype newptr =new node;
		newptr -> item = item;
		/*Special case: inserting a node in the beginning of the list*/
		if(pos ==1){
			newptr -> next = head;
			head = newptr;
		}
		else{
			ptrtype prev = ptr_to(pos-1);
			newptr -> next = prev -> next;
			prev -> next = newptr;
		}
	
	}
	size++;
}	
   
void linked_list::list_display(int pos){
	//Function displays only one field, namely id
	//of the item structure.
	ptrtype curptr = ptr_to(pos);
	cout<<curptr->item.id<<endl;
}

void linked_list::list_delete(int pos, datatype &item){
	//First validity of the position
	if(pos <1 || pos>list_size() ) return;
	else{
		ptrtype cur;
		// Special case: Deleting the head
		if(pos == 1){
			cur = head;
			head = head -> next;
		}
		else{
			ptrtype prev = ptr_to(pos-1);
			//First save a pointer to the node to be deleted
			cur = prev -> next;

			prev -> next = cur -> next;
		}
		
		//Now deallocate memory, i.e. give back the node to the system
		
		item = cur->item;
		cur -> next = NULL;
		delete cur;
		cur = NULL;
	}
	size--;
}

class stack{
private:
	linked_list st;
public:
	stack();
	void push(datatype item);
	void pop(datatype &item);
};

stack::stack(){
}
void stack::push(datatype item){
	st.list_insert(1,item);
}
void stack::pop(datatype &item){
	st.list_delete(1,item);
};

int main(){
	
	linked_list L;
	stack s1;
	datatype x;
	for(int i=1;i<=10;++i){
		x.id=i;
		//x.name is  not initialized, so it contains junk
		L.list_insert(i,x);
		s1.push(x);
	}
	for(i=1;i<=L.list_size();++i){
		//L.list_display(i);
		s1.pop(x);
		cout<<x.id<<endl;
	}
    
	cout<<endl;
	
	return 0;
}