#include <stdio.h>
#include <stdlib.h>

typedef struct node{
	int data;
	struct node* next;
}node,*LIST;

void display(LIST L){
	LIST temp;
	for(temp=L;temp!=NULL;temp=temp->next){
		printf("%d\n",temp->data);
	}
}

void initLL(LIST *L){

	*L = NULL;
}

void insertSorted(LIST *L, int elem)
{
	/*Step 1: Declare temp and trav.*/
	LIST temp,*trav;

	/*Step 2: Assign trav to head, and traverse the list until you find the right place for
		      insertion.*/
	for(trav=L; *trav!=NULL && (*trav)->data <= elem ; trav=&(*trav)->next){}

	/*Step 3: Allocate memory for a node using temp. After which, check if the malloc succeeded.*/
	temp= (LIST)malloc(sizeof(node));
	if(temp!=NULL){

		/*Step 4: Assign the data of temp to be the data which is to be inserted, then insert the
				  new node.*/
		temp->data=elem;
		temp->next=*trav;
		*trav=temp;

		printf("Insertion for %d is successful! \n", elem);
	}
}

void insertFirst(LIST *L, int elem){
	LIST temp;
	temp= (LIST)malloc(sizeof(node));
	if(temp!=NULL){
		temp->data=elem;
		temp->next=*L;
		*L=temp;
		printf("Insertion for %d is successful! \n", elem);
	}
}

void insertLastUnique(LIST *L, int elem)
{
	LIST temp, *trav;
	for(trav=L; *trav!=NULL && (*trav)->data != elem; trav= &(*trav)->next){}
		if(*trav==NULL){
			temp=(LIST)malloc(sizeof(node));
			if(temp!=NULL){
				temp->data=elem;
				temp->next=*trav;
				*trav=temp;
			}
			printf("Insertion for %d is successful! \n", elem);
		}else{
			printf("Failed! %d is found \n", elem);
		}

}

void insertLast(LIST *L, int elem)
{
	/*Step 1: Declare temp and trav.*/
	LIST temp, *trav;

	/*Step 2: Traverse the list until you've reached the end of the list.*/
	for(trav = L; *trav != NULL; trav = &(*trav)->next){}

	/*Step 3: Allocate space. After which, check if the malloc succeeded.*/
	temp = (LIST) malloc (sizeof(node));
	if(temp != NULL){

		/*Step 4: Insert the data into the newly allocated memory*/
		temp->data = elem;

		/*Step 5: Update the next.*/
		temp->next = *trav;

		/*Step 6: Update the trav.*/
		*trav = temp;
	}
	printf("Insertion for %d is successful! \n", elem);
}

int member(LIST L, int elem){
	LIST trav;
	for(trav=L; trav!=NULL && elem!=trav->data; trav=trav->next){}
		return (trav!=NULL)? 1:0;
}

void deleteMem(LIST *L, int elem)
{
	/*Step 1: Declare temp and trav.*/
	LIST temp, *trav;
	printf("Delete member 6...\n");

	/*Step 2: Assign trav to head, and traverse the list until you find the node to delete
			  or you've reached the end of the list.*/
	for(trav=L; *trav!=NULL && (*trav)->data!=elem; trav= &(*trav)->next){}

	/*Step 3: Check if you've reached the end of the list. If you haven't, then *trav is the node
			  to be deleted.*/
		if(*trav!=NULL){

			/*Step 4: Delete the node*/
			temp=*trav;
			*trav=temp->next;
			free(temp);
			printf("Successfully deleted %d\n",elem);
		}else{
		printf("\nItem does not belong in the list");
	}
}

void deleteMultiples(LIST *L, int elem){
	LIST temp, *trav;
	printf("Delete multiples of 2...\n");
	for(trav=L; *trav!=NULL;){
	    if((*trav)->data % elem == 0){
			temp=*trav;
			*trav=temp->next;
			free(temp);
		}else{
		    trav= &(*trav)->next;
		}
	}

}

void selectionSort(LIST head)
{
	int temp;
	LIST trav, store;
	for(;head!=NULL;head=head->next){
		store=head;
		for(trav=head;trav!=NULL;trav=trav->next){
			if(trav->data < store->data){
				store=trav;
			}
		}
		temp=store->data;
		store->data=head->data;
		head->data=temp;
	}
	printf("Selection sort:\n");
}

LIST copyAllElements1 (LIST A)
{
	LIST B = NULL;
	LIST temp, trav, *trav2;
	for(trav=A; trav!=NULL; trav=trav->next){
		for(trav2=&B; *trav2!=NULL; trav2=&(*trav2)->next){}
		temp= (LIST)malloc(sizeof(node));
		if(temp!=NULL){
			temp->data=trav->data;
			temp->next=*trav2;
			*trav2=temp;
		}
	}
	printf("Returning Linked list in ascending order...\n");
	return B;
}

LIST copyAllElements2 (LIST A)
{
	LIST B = NULL;
	LIST temp, trav;
	for(trav=A; trav!=NULL; trav=trav->next){
		temp= (LIST)malloc(sizeof(node));
		if(temp!=NULL){
			temp->data=trav->data;
			temp->next=B;
			B=temp;
		}
	}
	printf("Returning Linked list in descending order...\n");
	return B;
}

//int getSum(LIST L){ -->wla ni sir haha
//	LIST temp;
//	int sum=0;
//	for(temp=L;temp!=NULL;temp=temp->link){
//		sum+=temp->data;
//	}
//		printf("Sum: %d\n",sum);
//}

void initLL(LIST*);
void insertSorted(LIST*, int);
void insertFirst(LIST*, int);
void insertLastUnique(LIST*, int);
void insertLast(LIST*, int);
int member(LIST, int);
void deleteMem(LIST*, int);
void deleteMults(LIST*, int);
void selectionSort(LIST);
//int getSum (LIST);
void display(LIST);
LIST copyAllElements1(LIST);
LIST copyAllElements2(LIST);


int main() {
	LIST newLL;
	int x;

	initLL(&newLL);

	insertSorted(&newLL,9);
	insertSorted(&newLL,6);
	insertSorted(&newLL,5);
	insertSorted(&newLL,8);
	insertSorted(&newLL,4);

	selectionSort(newLL);

	display(newLL);

	insertFirst(&newLL,1);

	display(newLL);

	deleteMem(&newLL,6);

	display(newLL);

	deleteMultiples(&newLL,2);

	display(newLL);

	insertLastUnique(&newLL, 55);

	display(newLL);

	insertLast(&newLL, 100);

	display(newLL);

	LIST retVal= copyAllElements1(newLL);

	display(retVal);

	LIST retVal2= copyAllElements2(newLL);

	display(retVal2);



//	int sum;
//	for(x=0;x<3;x++){
//		insertFirst(&newAL,x+2);
//	}
//	sum=getSum(newAL);


	return 0;
}