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

struct element {
	int k;
	struct element *next;
	struct element *prev;
};

void lista_wyswietl(struct element *head);
struct element *insert(struct element *head, int key, int new);
struct element *swap(struct element *head, int k,int n);
struct element *lista_zwolnij_pamiec(struct element *head);
struct element *lista_odwroc(struct element *head);
struct element *lista_szukaj(struct element *head, int klucz);
struct element *lista_usun1(struct element *head, int klucz);
struct element *lista_usun2(struct element *head,struct element *x);
struct element *lista_usun3(struct element *head);
struct element *lista_dodaj1(struct element *head, struct element *nowy);
struct element *lista_dodaj2(struct element *head, struct element *nowy);
struct element *lista_sortuj(struct element *head);
int lista_policz(struct element*head);
int lista_pusta(struct element*head);
int iitl(struct element *head, int key);

main()
{
	struct element *head = NULL, *nowy = NULL;
	char z;
	int liczba,liczba2,i=0;
	while (1)
	{
		if (i == 0) {
			printf("\nco chcesz zrobic?");
			printf("\nd - dodac");
			printf("\ns - szukac");
			printf("\nu - usunac");
			printf("\no – odwrocic liste");
			printf("\nw - wyswietlic");
			printf("\nk - dodaj na koniec");
			printf("\nq - wyjsc");
			printf("\ni - zamienic elementy");
			printf("\nz - zwolnic pamiec");
			printf("\nl - usun glowe");
			printf("\np - dlugosc listy");
			printf("\nc - sprawdzic czy element nalezy do listy");
			printf("\nb - zamienic element");
			printf("\nn - posortowac liste");
			printf("\n");
		}
			fflush(stdin);
			z = getchar();
			switch (z)
			{
			case 'd':
				nowy = (struct element*)malloc(sizeof(struct element));
				//printf("\npodaj wartosc elementu do wstawienia: ");
				scanf_s("%d", &liczba);
				nowy->k = liczba;
				head = lista_dodaj1(head, nowy);
				break;
			case 's':
				printf("jaki element szukac?\n");
				fflush(stdin);
				scanf_s("%d", &liczba);
				//(lista_szukaj(head,liczba)!=0) ? printf("%d", lista_szukaj(head,liczba)) : printf("nie ma takiego elementu\n");
				printf("%p", lista_szukaj(head, liczba));
				break;
			case 'w':
				if (!lista_pusta(head)) {
					lista_wyswietl(head);
					printf("\n");
				}
				else
					printf("lista pusta");
				break;
			case 'i':
				printf("\njakie elementy zamienic?\n");
				scanf_s("%d", &liczba);
				scanf_s("%d", &liczba2);
				head = swap(head, liczba,liczba2);
				lista_wyswietl(head);
					break;
			case'k':
				printf("Jaki element chcesz dodac?\n");
				fflush(stdin);
				scanf_s("%d", &liczba);
				nowy = (struct element*)malloc(sizeof(struct element));
				nowy->k = liczba;
				lista_dodaj2(head, nowy);
				break;
			case 'u':
				printf("Jaki element chcesz usunac?\n");
				fflush(stdin);
				scanf_s("%d", &liczba);
				lista_usun1(head, liczba);
				break;
			case'l':
				head=lista_usun3(head);
				break;
			case 'o':
				head = lista_odwroc(head);
				lista_wyswietl(head);
				break;
			case 'z':
				head=lista_zwolnij_pamiec(head);
				break;
			case 'p':
				printf("\n liczba elementow w liscie: %d \n", lista_policz(head));
				break;
			case 'c':
				printf("\nJaki element sprawdzic?");
				scanf_s("%d", &liczba);
				printf("\n%d\n", iitl(head, liczba));
				break;
			case'b':
				printf("\nJaki element zamienic? ");
				scanf_s("%d", &liczba);
				printf("Na jaki podmienic? ");
				fflush(stdin);
				scanf_s("%d", &liczba2);
				head = insert(head, liczba, liczba2);
				lista_wyswietl(head);
				break;
			case'n':
				head = lista_sortuj(head);
				lista_wyswietl(head);
				break;
			case 'q': return 0;
			}
			i++;

	}
}

void lista_wyswietl(struct element *head)
{
	struct element*x = head;
	while (x != NULL)
	{
		printf("%d ", x->k);
		x = x->next;
	}
}

struct element *lista_szukaj(struct element *head, int klucz) {
	struct element *x = head;
	while (x != NULL && x->k != klucz) {
		x = x->next;
	}
	return x;
}
struct element *lista_usun1(struct element *head, int klucz) {
	struct element *x = lista_szukaj(head, klucz);
	if (x->prev != NULL)
		x->prev->next = x->next;
	else
		head = x->next;

	if (x->next != NULL)
		x->next->prev = x->prev;

	free(x);
	return head;
}

struct element *lista_usun2(struct element *head, struct element *x) {
	if (x->prev != NULL)
		x->prev->next = x->next;
	else
		head = x->next;

	if (x->next != NULL)
		x->next->prev = x->prev;

	free(x);

	return head;
}


struct element *lista_dodaj1(struct element *head, struct element *nowy) {
	nowy->next = head;
	if (head != NULL) {
		head->prev = nowy;
	}
	head = nowy;
	nowy->prev = NULL;
	return head;
}

struct element *lista_dodaj2(struct element *head, struct element *nowy) {
	struct element *x = head;
	while (x->next != NULL)
		x = x->next;
	x->next = nowy;
	nowy->next = NULL;
	nowy->prev = x;
	return head;
}

struct element *lista_odwroc(struct element *head){
	struct element *x = head;
	struct element *temp = NULL;
	while (x->next != NULL) {
		temp = x->prev;
		x->prev = x->next;
		x->next = temp;
		x = x->prev;
	}
	x->next = x->prev;
	x->prev = NULL;
	return x;
}

int lista_policz(struct element*head) {
	int i = 0;
	struct element *x = head;
	while (x != NULL) {
		x = x->next;
		i++;
	}
	return i;
}

struct element *lista_usun3(struct element *head) {
	struct element*x = head;
	if (x->next == NULL){
		free(head);
		return NULL;
		}
	x->next->prev = NULL;
	x = x->next;
	free(head);
	head = x;
	return head;

}

struct element* lista_zwolnij_pamiec(struct element *head){

	while (!lista_pusta(head)) {

		head=lista_usun3(head);
	}
	return head;
}


int lista_pusta(struct element *head) {
	if (head == NULL)
		return 1;
	return 0;
}
struct element *swap(struct element *head,int k,int n) {
	struct element *w1 = lista_szukaj(head, k);
	struct element *w2 = lista_szukaj(head, n);
	int temp;
	temp = w1->k;
	w1->k = w2->k;
	w2->k = temp;
	return head;
}

int iitl(struct element *head, int key) {
	struct element *x = head;
	int bol=0;
	while (x != NULL) {
		if (key == x->k) bol = 1;
		x = x->next;
	}
	return bol;
}
struct element *insert(struct element *head, int key, int new) {
	struct element *x = head;
	if (iitl(head, key)) {
		while (x != NULL && key!=x->k) {
			x = x->next;
		}
		x->k = new;
	}
	return head;
}

struct element *lista_sortuj(struct element *head) {
	int i = lista_policz(head);
	int temp;
	struct element *x = head;

	do{
		while (x->next!= NULL) {
			if (x->k > x->next->k) {
				temp = x->k;
				x->k = x->next->k;
				x->next->k = temp;
			}
			x = x->next;
		}
		i = i - 1;
		x = head;
	} while (i > 1);
	return head;
}