/*
 *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);
		void rec_list_insert(ptrtype& cur, datatype item);
		void rec_list_display(ptrtype cur);
		int rec_list_size(ptrtype cur);
		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);
		void insert_by_value(datatype item);
		void rec_list_insert_wrapper(datatype item);
		int  rec_list_size_wrapper();
		void rec_list_display_wrapper();
		
		

};


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--;
}

void linked_list::insert_by_value(datatype item){
	ptrtype temp = new node;
	temp->item = item;
	if(head==NULL || head->item.id>item.id){
		temp->next=head;
		head=temp;
	}
	else{
		for(ptrtype cur=head; cur->next!=NULL
					 && item.id>cur->next->item.id; cur=cur->next);
	
		temp->next=cur->next;
		cur->next=temp;
	}
	size++;
}

void linked_list::rec_list_display(ptrtype cur){
	if(cur==NULL) return;
	else {
		cout<<cur->item.id<<endl;
		rec_list_display(cur->next);
	}
}

void linked_list::rec_list_display_wrapper(){
	rec_list_display(head);
}

int linked_list::rec_list_size(ptrtype cur){
	if(cur==NULL) return 0;
	else return 1+rec_list_size(cur->next);
}

int linked_list::rec_list_size_wrapper(){
	return rec_list_size(head);
}

void linked_list::rec_list_insert(ptrtype& cur, datatype item){
	ptrtype temp=cur;
	if(cur==NULL || cur->item.id>item.id){
		cur=new node;
		cur->item=item;
		cur->next=temp;
		size++;
	}
	else rec_list_insert(cur->next,item);
}

void linked_list::rec_list_insert_wrapper(datatype item){
	rec_list_insert(head, item);
}



int main(){
	
	linked_list L;
	datatype x;
	int size;
	cout<<"size: ";
	cin>>size;
	for(int i=size;i>=1;--i){
		//x.id=i;
		cout<<"? ";
		cin>>x.id;
		//x.name is  not initialized, so it contains junk
		//L.list_insert(i,x);
		L.insert_by_value(x);
		//L.rec_list_insert_wrapper(x);

	}
	L.rec_list_display_wrapper();
	//for(i=1;i<=size;++i)L.list_display(i);
	cout<<endl<<"Size of the linked list: "//<<L.list_size();
		<<L.rec_list_size_wrapper()<<endl;
	
	return 0;
}