// lista.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <ctime>
#include <fstream>

using namespace std;

//wezel listy
struct Wezel {
	int klucz;
	double liczba;
	char znak;
	Wezel *poprzednik;
	Wezel *nastepnik;
};

//Lista dwukierunkowa cykliczna
struct Lista {
	Wezel *poczatek;
	int ilosc;
};
//tworzenie listy
void tworzenie_listy(Lista *lista) {
	lista->poczatek = NULL;
	lista->ilosc = 0;
}
//wypisywanie od poczatku
void od_poczatku(Lista *lista, int ilosc) {

	if (lista->poczatek == NULL)
		return;

	Wezel *pomocniczy = lista->poczatek;
	cout << "Elementy od poczatku listy : " << endl;

	while (pomocniczy != NULL && ilosc > 0) {
		cout << pomocniczy->klucz << endl;
		pomocniczy = pomocniczy->nastepnik;
		ilosc--;
	}
}
//wypisywanie od konca
void od_konca(Lista *lista, int ilosc) {

	if (lista->poczatek == NULL)
		return;

	Wezel *pomocniczy = lista->poczatek;
	cout << "Elementy od konca listy : " << endl;

	while (pomocniczy != NULL && ilosc > 0) {
		pomocniczy = pomocniczy->poprzednik;
		cout << pomocniczy->klucz << endl;
		ilosc--;
	}
}

//ilosc
void ilosc_elementow(Lista *lista) {
	cout << "Ilosc elementow : " << lista->ilosc << endl;
}

//szukanie elementu o podanym kluczu
Wezel *szukanie_klucza(Lista *lista, int klucz) {

	if (lista->poczatek == NULL)
		return NULL;

	Wezel *pomocniczy = lista->poczatek;
	for(int i=0; i<lista->ilosc;i++)
	{
		if (pomocniczy->klucz == klucz)
		{
			return pomocniczy;
		}
		pomocniczy = pomocniczy->nastepnik;
	}
	return NULL;
}
//szukanie wezla przed ktorym mamy wstawic
Wezel *szukanie_nas_elementu(Lista *lista, int klucz)
{
	if (lista->poczatek == NULL)
	{
		return NULL;
	}

	Wezel *pomocniczy = lista->poczatek;

	for (int i = 0; i < lista->ilosc; i++)
	{
		if (pomocniczy->klucz >= klucz)
		{
			return pomocniczy;
		}
		pomocniczy = pomocniczy->nastepnik;
	}
	return lista->poczatek;
}

// wstawia kolejny klucz na listę
bool wstaw(Lista *lista, int klucz, double liczba, char znak)
{
	if (szukanie_klucza(lista, klucz) != NULL)
	{
		return false;
	}

	Wezel *nastepnyWezel = szukanie_nas_elementu(lista, klucz);
	Wezel *aktualnyWezel = new Wezel();
	aktualnyWezel->klucz = klucz;
	aktualnyWezel->liczba = liczba;
	aktualnyWezel->znak = znak;
	aktualnyWezel->nastepnik = NULL;
	aktualnyWezel->poprzednik = NULL;

	// lista jest pusta
	if (lista->ilosc == 0)
	{
		aktualnyWezel->nastepnik = aktualnyWezel;
		aktualnyWezel->poprzednik = aktualnyWezel;
		lista->poczatek = aktualnyWezel;
	}
	// lista ma przynajmniej 1 element
	else
	{
		aktualnyWezel->nastepnik = nastepnyWezel;
		aktualnyWezel->poprzednik = nastepnyWezel->poprzednik;
		nastepnyWezel->poprzednik->nastepnik = aktualnyWezel;
		nastepnyWezel->poprzednik = aktualnyWezel;
	}

	// jeżeli wstawiany klucz jest mniejszy od klucza korzenia
	if (lista->poczatek->klucz > klucz)
		// zastąp korzeń kluczem wstawianym
		lista->poczatek = aktualnyWezel;

	lista->ilosc++;

	return true;
}


//wstawianie losowego wezla
void wstaw_losowo(Lista *lista, int iloscWezlow)
{
	// inicjalizuj generator losowy aktualnym czasem
	srand(time(NULL));

	while (iloscWezlow-- > 0)
	{
		int klucz = (99 + (rand() % (999999 - 99 + 1)));
		double liczba = (0 + (rand() % (100 - 0 + 1)));
		char znak = (97 + (rand() % (122 - 97 + 1)));

		wstaw(lista, klucz, liczba, znak);
	}
}

bool usuwanie_wez(Lista *lista, int klucz) {

	Wezel *aktualnyWezel = szukanie_klucza(lista, klucz);

	if (aktualnyWezel == NULL)
		return false;

	aktualnyWezel->poprzednik->nastepnik = aktualnyWezel->nastepnik;
	aktualnyWezel->nastepnik->poprzednik = aktualnyWezel->poprzednik;
	if (lista->poczatek == aktualnyWezel)
		lista->poczatek = lista->poczatek->nastepnik;

	delete aktualnyWezel;
	lista->ilosc--;

	return true;
}

void usuwanie_lista(Lista *lista) {

	Wezel *pomocniczy = lista->poczatek;

	for (int klucz = 0;klucz < lista->ilosc;klucz++) {

		Wezel *usuwany = pomocniczy;
		pomocniczy = pomocniczy->nastepnik;
		delete usuwany;
	}

	tworzenie_listy(lista);

}


int main() {

	// star pomiar czasu
	clock_t begin, end;
	double time;
	begin = clock();


	ifstream plik;
	plik.open("inlab02.txt");
	if (plik.good())
		cout << "Masz dostep do pliku." << endl;
	else
		cout << "nie masz dostep do pliku." << endl;

	int X, k1, k2, k3, k4, k5;

	// wczytaj dane z pliku
	plik >> X >> k1 >> k2 >> k3 >> k4 >> k5;
	plik.close();

	Lista lista;
	tworzenie_listy(&lista);

	Wezel *pomocniczy = szukanie_klucza(&lista, k1);

	if (pomocniczy != NULL)
		cout << "znaleziono " << k1 << endl;
	else
		cout << "nie znaleziono " << k1 << endl;

	wstaw_losowo(&lista, X);
	ilosc_elementow(&lista);
	od_poczatku(&lista, 20);
	wstaw(&lista, k2, 0, 'T');
	od_poczatku(&lista, 20);
	wstaw(&lista, k3, 0, 'T');
	od_poczatku(&lista, 20);
	wstaw(&lista, k4, 0, 'T');
	od_poczatku(&lista, 20);
	wstaw(&lista, k5, 0, 'T');

	usuwanie_wez(&lista, k3);
	od_poczatku(&lista, 20);
	usuwanie_wez(&lista, k2);
	od_poczatku(&lista, 20);
	usuwanie_wez(&lista, k5);
	ilosc_elementow(&lista);
	pomocniczy = szukanie_klucza(&lista, k5);
	if (pomocniczy != NULL)
		cout << "znaleziono " << k5 << endl;
	else
		cout << "nie znaleziono " << k5 << endl;

	od_konca(&lista, 11);
	usuwanie_lista(&lista);
	od_konca(&lista, 11);
	ilosc_elementow(&lista);

	end = clock();
	time = (double)(end - begin) / CLOCKS_PER_SEC;
	cout << "Koniec.Czas wykonaniu programu : " << time << endl;

	system("pause");
	return 0;
}