#include "pch.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>



struct Node
{
	char* data;
	Node* next;
};

struct List
{
	Node* head;
};

bool isEmpty(List* list)
{
	assert(list != NULL);

	if (list->head == NULL)
		return  true;
	else
		return false;
}

int getSize(List* list)
{
	assert(list != NULL);
	int size = 0;

	if (list->head != NULL)
	{
		size++;
		Node* p = list->head;
		while (p->next != NULL)
		{
			size++;
			p = p->next;
		}
	}
	return size;
}

//нахождение последнего элемента
Node* getLastNodeIfNotEmpty(List* list)
{
	assert(list != NULL);
	assert(!isEmpty(list));
	Node* i = list->head;
	while (i->next != NULL)
	{
		i = i->next;
	}
	return i;
}

//вставка в любое место
void insertMiddle(List* list, char* value, int number)
{
	char *s;
	Node* tmp = (Node*)malloc(sizeof(Node));
	tmp->data = value;
	Node* current = list->head;
	for (int i = 0; i < number; i++)
	{
		current = current->next;
	}
	tmp->next = current->next->next;
	current->next = tmp;
}

//вставка в конец
void insertBack(List* list, char* value)
{
	assert(list != NULL);
	Node* tmp = (Node*)malloc(sizeof(Node));
	tmp->data = value;
	tmp->next = NULL;
	if (list->head == NULL)
	{
		list->head = tmp;

	}
	else
	{
		Node* last = getLastNodeIfNotEmpty(list);
		last->next = tmp;
	}
}

void swap(char* a, char* b)
{
	char c;
	c = *a;
	*a = *b;
	*b = c;
}

bool sort_two(Node* first_node)
{
	assert(first_node != NULL);
	assert(first_node->next != NULL);

	if (first_node->data > first_node->next->data)
	{
		swap(first_node->data, first_node->next->data);
		return true;
	}
	return false;
}

//нахождение последнего элемента
bool isLast(Node* node)
{
	if (node->next == NULL)
		return true;
	else
		return false;
}

void sort(List* list)
{
	if (isEmpty(list))
		return;

	int size = getSize(list);
	if (size == 1)
		return;
	else if (size > 1)
	{
		for (int k = 0; k < size; k++)
		{
			Node* i = list->head;
			while (!isLast(i))
			{
				sort_two(i);
				i = i->next;
			}
		}
	}
}

void printList(List* list)
{
	assert(list != NULL);
	Node* i = list->head;
	while (i != NULL)
	{
		printf("%s ", i->data);
		i = i->next;
	}
}

List makeEmptyList()
{
	List empty_list;
	empty_list.head = NULL;
	return empty_list;
}

void writeList(List* list, int number)
{
	for (int i = 0; i < number; i++)
	{
		printf("Vvedite element: ");
		Node* UsingMem = (Node*)malloc(sizeof(Node));
		char* str = (char*)malloc(1000);
		gets_s(str, 1000);
		UsingMem->data = str;
		insertBack(list, UsingMem->data);
	}
}

int main()
{
	List l = makeEmptyList();
	isEmpty(&l) == true;
	int k;
	printf("Vvedite kolichestvo elementov: ");
	scanf_s("%d", &k);


	/*Node* UsingMem = (Node*)malloc(sizeof(Node));
	char* str = (char*)malloc(1000);
	gets_s(str, 1000);
	UsingMem->data = str;
	printf("%s", UsingMem->data);*/

	//char* tmp = (char*)malloc(sizeof(char));

		//Node* UsingMem = (Node*)malloc(sizeof(Node));
	for (int i = 0; i < k; i++)
	{
		char* str = (char*)malloc(1000);
		printf("Vvedite element: ");
		gets_s(str, 1000);
		printf("Entered string (%d): %s", i, str);
		insertBack(&l, str);
	}
	//writeList(&l, k);
	printList(&l);
	printf("Enter element number:");
	int number;
	scanf_s("%d", &number);
	printf("Enter element: ");

	//insertMiddle(&l, value, number);
		printf("Before sort:\n    ");
	printList(&l);
	sort(&l);
	printf("After sort:\n    ");
	printList(&l);
}