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

typedef struct Node {
	int data;
	struct Node * prev;
	struct Node * next;
}Node;
struct Node* head;//global variable
struct Node* newNode(int value){

	struct Node* element = (struct Node*) malloc(sizeof(struct Node));
	element -> data = value;
	element -> prev = NULL;
	element -> next = NULL;
	return element;
};
void print_dll(Node* head){
	Node* temp = head;
	while(temp != NULL){
		printf("%d\n", temp->data);
		temp = temp->next;
	}
	printf("\n");
}

void insert_after(Node* head, int valueToInsertAfter, int valueToBeInserted){
	Node* temp = head;
	Node* prevTemp;
	Node* insertedNode = newNode(valueToBeInserted);
	head = (head == NULL)?insertedNode:head;
	while(temp!= NULL && temp -> data != valueToInsertAfter){
		temp = temp -> next;
	}

	if(temp == NULL){
		temp= insertedNode;
	}else{
		insertedNode -> next = temp -> next;
		insertedNode -> prev = temp;
		temp -> next -> prev = insertedNode;
		temp -> next = insertedNode;
	}


}
void delete_element(Node* head, int valueTobeDeleted){
	Node* temp = head;
	while(temp!= NULL && temp-> data != valueTobeDeleted){
		temp = temp -> next;
	}
	if(temp != NULL){
		temp -> prev -> next = temp -> next;
		temp -> next -> prev = temp -> prev;
		free(temp);
	}
	printf("delete");
}
void sort_dll(Node* head){
	if(head == NULL && head->next == NULL){
		return ; //need two elements to sort
	}
	Node* first = head;
	Node* second = head -> next;
	int swapped; //count for the elements in dll
	//If swapping occurred, swapped will be incremented
	do{
		swapped = 0; //Re-zero swapped at the beginning of do-while loop
		while(first != NULL && second != NULL){

			if(first -> data > second -> data){
				printf("sort");

				second -> prev = first -> prev;
				first -> prev = second;
				first -> next = second -> next;
				second -> next -> prev = first;
				second -> next = first;
				first = second;
				second = second-> next;
				swapped += 1;
			}
			first = first-> next;
			second = second -> next;

		}
		 //If one of them was NULL, point them back to head and head.next.
	}while(swapped != 0);//If no swapping occurred, terminate the loop.


}
void freeDll(Node* head){
	Node* temp = head;
	Node* delete = head;
	while(temp != NULL){
		free(temp);
		temp = delete -> next;
	}
	printf("free");

}
Node* create_dll_from_array(int array[], int size){
	Node* dummy = (struct Node*) malloc(sizeof(struct Node));
	Node* temp =  dummy;
	for(int i= 0; i< size; i++){
		temp -> next = newNode(array[i]);
		temp -> prev = temp;
		temp = temp-> next;
	}
	return dummy->next;

}
int main(){
	int array[5] = {11,2,7,22,4};
	Node* head;
	head = create_dll_from_array(array,5);
	//	print_dll(head);
	//
	//	insert_after(head,7,13);
	//	insert_after(head,21,29);
	//
	//	print_dll(head);
	//
	//	delete_element(head,22);
	//	print_dll(head);

	sort_dll(head);
	printf("\n sort test\n");
	print_dll(head);
	printf("\n print test\n");

	//freeDll(head);
	printf("xx");

	return 0;
}