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

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_

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

typedef struct Person
{
	char *name;
	char *surname;
	char *dateBirth;
	char *email;
	char *phone;
	char *address;
}Person;

typedef struct Member
{
	Person *person;
	struct Member *previous;
	struct Member *next;
}Member;

typedef struct List
{
	Member *first;
	Member *last;
}List;

extern List *createList();
extern void deleteList(List *head);
extern void addElement(List *head, Person *person);
extern void deleteElement(List *head, Person *person);
extern Person *searchElement(List *head, char *name, char *surname);
extern void sortList(List *head);
extern void quickSort(Member *first,Member *last);
extern Member *partition(Member *first,Member *last);
extern void swap(Member *a,Member *b);
extern List *mergeSort(List *head);
extern List *merge(List *left, List *right);
extern Member *center(List *head);
extern void printPerson(Person *person);
extern void printList(List *head);
extern Person *createPerson(char *name, char *surname, char *dateBirth, char *email, char *phone, char *address);

#endif

List *createList()
{
	List *head = (List*)malloc(sizeof(List));
	head->first = NULL;
	head->last = NULL;
	return head;
}

void deleteList(List *head)
{
	Member *first = head->first;

	if (first == NULL)return;
	while (first != NULL)
	{
		Member *tmp = first;
		first = first->next;
		free(tmp->person->name);
		free(tmp->person->surname);
		free(tmp->person->dateBirth);
		free(tmp->person->email);
		free(tmp->person->phone);
		free(tmp->person->address);
		free(tmp->person);
		free(tmp);
	}
}

void addElement(List *head, Person *person)
{
	Member *last = head->last;
	Member *newMem = (Member*)malloc(sizeof(Member));
	newMem->person = person;
	newMem->previous = newMem->next = NULL;
	if (last == NULL)
	{
		head->first = head->last = newMem;
		return;
	}

	last->next = newMem;
	newMem->previous = last;
	head->last = newMem;
}

void deleteElement(List *head, Person *person)
{
	if (head == NULL || person == NULL)return;

	Member *member = head->first;
	while (member != NULL && member->person != person)member = member->next;

	if (member == NULL)return;

	if (member == head->first)
	{
		if (member == head->last)
		{
			head->first = head->last = NULL;
		}
		else
		{
			head->first = head->first->next;
			head->first->previous = NULL;
		}
	}
	else
	{
		if (member == head->last)
		{
			head->last = head->last->previous;
			head->last->next = NULL;
		}
		else
		{
			member->previous->next = member->next;
		}
	}
	free(member->person->name);
	free(member->person->surname);
	free(member->person->dateBirth);
	free(member->person->email);
	free(member->person->phone);
	free(member->person->address);
	free(member->person);
	free(member);
}

Person *searchElement(List *head, char *name, char *surname)
{
	Member *tmp = head->first;
	while (tmp != NULL)
	{
		if (strcmp(tmp->person->name, name) == 0 && strcmp(tmp->person->surname, surname) == 0)
			return tmp->person;
		tmp=tmp->next;
	}
	return NULL;
}

void sortList(List *head)
{
	quickSort(head->first,head->last);
}

void quickSort(Member *first,Member *last)
{
	if (first!= NULL && last!=NULL && first!=last && first!=last->next)
	{
		Member *p = partition(first,last);
		quickSort(first, p->previous);
		quickSort(p->next,last);
	}
}

Member *partition(Member *first,Member *last)
{
	Person *pivot=last->person;
	Member *i=first->previous;
	Member *j=first;
	for(j;j!=last;j=j->next)
	{
		if(strcmp(j->person->surname,pivot->surname)<0)
		{
			i=(i==NULL) ? first : i->next;
			swap(i,j);
		}
	}
	i =(i==NULL)? first : i->next;
	swap(i,last);
	return i;
}

void swap(Member *a,Member *b)
{
	Person *tmp=a->person;
	a->person=b->person;
	b->person=tmp;
}

List *mergeSort(List *head)
{
	if (head->first == NULL || head->first == head->last)return head;

	Member *mid = center(head);

	if (mid->next != NULL)mid->next->previous = NULL;
	List *left = createList();
	List *right = createList();

	right->first = mid->next;
	right->last = mid->next == NULL ? NULL : head->last;
	left->first = head->first;
	left->last = mid;
	left->last->next=NULL;
	left = mergeSort(left);
	right = mergeSort(right);
	return merge(left, right);
}

List *merge(List *left, List *right)
{
	if (left->first == right->first && left->last == right->last)
	{
		free(right);
		return left;
	}

	Member *leftMem = left->first;
	Member *rightMem = right->first;
	Member *tmp;

	if(rightMem==NULL)return left;
	if(leftMem==NULL)return right;

	if (strcmp(leftMem->person->name, rightMem->person->name)<0)
	{
		tmp = leftMem;
		leftMem = leftMem->next;
	}
	else
	{
		tmp = rightMem;
		rightMem = rightMem->next;
	}
	left->first = tmp;

	while (leftMem != NULL && rightMem != NULL)
	{
		if (strcmp(leftMem->person->name, rightMem->person->name)<0)
		{
			tmp->next = leftMem;
			leftMem->previous = tmp;
			tmp = leftMem;
			leftMem = leftMem->next;
		}
		else
		{
			tmp->next = rightMem;
			rightMem->previous = tmp;
			tmp = rightMem;
			rightMem = rightMem->next;
		}
	}

	if (leftMem != NULL)
	{
		tmp->next = leftMem;
		leftMem->previous = tmp;
	}
	else if (rightMem != NULL)
	{
		tmp->next = rightMem;
		rightMem->previous = tmp;
	}

	while (tmp->next != NULL)
	{
		tmp = tmp->next;
	}

	left->last = tmp;
	free(right);

	return left;
}

Member *center(List *head)
{
	Member *slower = head->first;
	if (slower->next == NULL)return slower;
	Member *faster = slower->next;
	while (slower != NULL && faster->next != NULL)
	{
		slower = slower->next;
		faster = faster->next->next;

	}
	return slower;
}

void printPerson(Person *person)
{
	if (person == NULL)return;
	printf("%s %s %s %s %s %s\n", person->name, person->surname, person->dateBirth, person->email, person->phone, person->address);
}

void printList(List *head)
{
	Member *tmp = head->first;
	while (tmp != NULL)
	{
		printPerson(tmp->person);
		tmp = tmp->next;
	}
}

Person *createPerson(char *name, char *surname, char *dateBirth, char *email, char *phone, char *address)
{
	Person *person = (Person*)malloc(sizeof(Person));

	person->name = name;
	person->surname = surname;
	person->dateBirth = dateBirth;
	person->email = email;
	person->phone = phone;
	person->address = address;

	return person;
}


char *allocate(char *a);

int main()
{
    srand(time(NULL));
	char* names[]={"Adam","Bartosz","Cyprian","Danuta","Eustachy","Frania","Gabriel","Halina"};
	char* surnames[]={"Kowalski","Nowak","Job","Kolasa","Perdek","Slowik","Wisniewski","Rinner"};
	char* birthDates[]={"01-01-1991","02-02-1992","03-03-1993","04-04-1994",
					"05-05-1995","06-06-1996","07-07-1997","08-08-1998"};
	char* emails[]={"adam.kowalski@gmail.com","bartosz.nowak@gmail.com","cyprian.job@gmail.com","danuta.kolasa@gmail.com",
				"eustachy.perdek@gmail.com","frania.slowik@gmail.com","gabriel.wisniewski@gmail.com","halina.rinner@gmail.com"};
	char* numbers[]={"111111111","222222222","333333333","444444444","555555555","666666666","777777777","888888888"};
	char* adresses[]={"Krakow","Warszawa","Plock","Gdynia","Rzeszow","Katowice","Wroclaw","Poznan"};

	int N=8;

	List* head=createList();
	int i=0;
	for(i=0;i<N;i++)
	{
		Person *person=createPerson(allocate(names[rand()%8]),allocate(surnames[rand()%8]),allocate(birthDates[rand()%8]),allocate(emails[rand()%8]),allocate(numbers[rand()%8]),allocate(adresses[rand()%8]));
		addElement(head,person);
	}
	printf("\n");
	printList(head);

	sortList(head);
	printf("Posortowane:\n");
	printList(head);
	printf("\n");
	printf("Szukany element:\n");
	Person *searched=searchElement(head,"Eustachy","Nowak");
	if(searched!=NULL)printPerson(searched);
	printf("\n");
	printf("Usuniety element:\n");
	deleteElement(head,searched);
	printList(head);

	deleteList(head);

	return 0;
}

char *allocate(char *a)
{

	char *b=(char*)malloc(strlen(a)+1);
	strcpy(b,a);
	return b;
}