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

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

using namespace std;



struct node {
	string val;
	node *next;
	node *prev;
};

struct list {
	node *head;
	node *tail;
	unsigned int count;
};



//vol1



void add(node *&head, string nval) {
	node *new_elem = new node;
	new_elem->val = nval;
	new_elem->next = head;
	new_elem->prev = NULL;
	head->prev = new_elem;
	head = new_elem;
}

void show(node *head, int &licznik) {
	node *p = head;
	int i = 0;
	while (p->next != NULL) {
		cout << p->val << "\t";
		p = p->next;
		i++;
	}
	licznik = i;
}

void readfromfile(node *&head) {
	ifstream plik("plik.txt");
	string  nval;
	if (plik.good() == true) {
		while (!plik.eof()) {
			plik >> nval;
			node *new_elem = new node;
			new_elem->val = nval;
			new_elem->next = head;
			new_elem->prev = NULL;
			//head->prev = new_elem;
			head = new_elem;
		}

	}
	else {
		cout << "Blad odczytu! ";
	}
}

void destroy(node *&head) {  //poczatek listy
	if (head != NULL) {
		node *p = head;
		head = head->next;
		delete p;
	}

}

/*void damage(node *&head) {
node *p = head;
while (p) {
p = p->next;
}
p->prev = p->next;
delete p;
}*/

void pick_one(node *&head, string a) {//szukanie po wartosci
	node *p = head;
	while (p->next != NULL) {
		if (p->val == a) {
			cout << p->val;
			break;
		}
		else if (p->next->val == a) {
			cout << p->next->val;
			break;
		}
		else {
			p = p->next;
		}
	}
}

void pick_indeks(node *&head, int licznik, int indeks) {//szukanie po indeksie
	node *p = new node;
	p = head;
	string zmienna;
	if (licznik == 0) {
		cout << "Pusta lista.";

	}
	else {
		for (int i = 1; i <= licznik; i++)
		{
			if (i == indeks) {
				cout << "Podaj wartosc ";
				cin >> zmienna;
				p->val = zmienna;
			}

			else {
				p = p->next;
			}
		}
	}
}

/*void podziel(node *&head,int licznik) {
node *H1 = new node;
node *H2 = new node;
H1= head;
H2 = head->next;
bool s = false;
if (licznik <= 1) {
cout << "lista pusta lub ma jeden element -nie mozna jej podzielic." << endl;
}
else {
while (head)
{
if (s) {
H2->next = head;
H2 = H2->next;
}
else {
H1->next = head;
H1 = H1->next;
}
head = head->next;
s = !s;
}
H1->next = H2->next = NULL;
add(H1);
add(H2);
}

}
*/



//vol2


void push_front(list &L, string nval) {
	node *p = new node;
	p->val = nval;
	p->next = L.head;
	p->prev = NULL;
	L.head = p;
	L.count++;
	if (p->next) {
		p->next->prev = p;
	}
	else {
		L.tail = p;
	}
}

void push_back(list &L, string nval) {
	node *p = new node;
	p->val = nval;
	p->next = NULL;
	p->prev = L.tail;
	L.tail = p;
	L.count++;
	if (p->prev) {
		p->prev->next = p;
	}
	else {
		L.head = p;
	}
}

void pokaz(list &L) {
	node *p;
	p = L.head;
	while (p) {
		cout << p->val << "\t";
		p = p->next;
	}

}

void remove(list &L, node *e) {
	L.count--;
	if (e->prev) {
		e->prev->next = e->next;
	}
	else if (e->next) {
		e->next->prev = e->prev;
	}
	else {
		L.tail = e->prev;
	}

	delete e;
}

void remove_front(list &L) {
	if (L.count) {
		remove(L, L.head);
	}
}

void remove_back(list &L) {
	if (L.count) {
		remove(L, L.tail);
	}
}
/*
node *podziel(node *&head) {
if (head == NULL || head->next==NULL) {
cout << "Pusta lista lub ma jeden element" << endl;
}
else {
node *newListP = NULL;
node *newListN = NULL;
node *p = head;
int counter = 0;
while (p->next != NULL)
{
if (counter % 2 == 0) {
cout << p->val;
//add(newListP,p->val);
}
else {
cout << p->val;
//add(newListN,p->val);
}
counter ++ ;
p = p->next;
}
if (p->next == NULL) {
if (counter % 2 == 0)
{
add(newListP, p->val);
}
else
{
add(newListN, p->val);
}
head = newListN;
show(head,counter);
cout << endl;
show(newListP,counter);
}
return newListP;

}

}*/

void swapElem(list &L, unsigned int nr_el1, unsigned int nr_el2)
{
	node* pom1 = new node;
	node* pom2 = new node;
	node* tmp1 = new node;
	node* tmp2 = new node;
	pom1 = L.head;
	if (nr_el1 > nr_el2)
	{
		unsigned int pom;
		pom = nr_el1;
		nr_el1 = nr_el2;
		nr_el2 = pom;
	}
	for (unsigned int i = 1; i < nr_el2; i++)
	{
		tmp1 = pom1;
		pom1 = pom1->next;
		if (pom1 != NULL) continue;
		else {
			cout << "Lista konczy sie na elemencie nr" << i << "!\n";
			pom1 = NULL;
			pom2 = NULL;
			break;
		}
	}
	cout << "Tmp1 =" << tmp1->val << " Pom1 = " << pom1->val << endl;
	if (pom1 == NULL && pom2 == NULL) { cout << "Zamiana nie powiodla sie\n"; }
	else {
		pom2 = L.head;
		tmp2 = L.head;
		for (unsigned int i = 1; i < nr_el1; i++)
		{
			tmp2 = pom2;
			pom2 = pom2->next;
		}
		if ((nr_el2 - nr_el1) > 1) {
			cout << "Tmp2 =" << tmp2->val << " Pom2 = " << pom2->val << endl;


			if (nr_el1 != 1)
			{
				/*pom2->next = pom1->next;
				tmp1->next = pom2;
				pom1->next = tmp1;
				tmp2->next = pom1;*/
				tmp1->next = pom2->next;
				tmp2->next = pom1;
				pom2->next = pom1->next;
				pom1->next = tmp1->next;
				tmp1->next = pom2;
				//head = tmp2;
			}
			else {
				tmp2 = pom2->next;
				pom2->next = pom1->next;
				tmp1->next = pom2;
				pom1->next = tmp2;
				L.head = pom1;
			}

		}
		else
		{
			tmp1->next = pom1->next;
			pom1->next = pom2;
			if (nr_el1 != 1)
			{
				tmp2->next = pom1;
				//head = tmp2;
			}
			else L.head = pom1;
		}
		cout << "Zamiana powiodla sie\n";
	}
}

void Bombel(list &L) {
	node *p = new node;
	node *temp = new node;
	while (p) {
		p = L.head;
		temp = p->next;
		L.count = 1;
		bool swapped = false;
		while (temp) {
			if (p->val <= temp->val) {
				p = temp;
				temp = temp->next;
				L.count++;
				break;
			}
			else {
				swapElem(L, L.count, L.count++);
				p = temp;
				temp = temp->next;
				swapped = true;
				L.count++;
				break;
			}

		}

		if (swapped) {
			L.head = p;
			p = nullptr;
		}
		else {
			L.head = p;
			break;
		}

	}
}

int main()
{
	//vol1
	unsigned int nr_el1, nr_el2;
	/*
	node *head = NULL;
	head = new node;
	head->next = NULL;
	head->prev = NULL;


	node *tail = NULL;
	tail = new node;
	tail->next = NULL;
	tail->prev = NULL;


	string a, b;
	int n, licznik, indeks;
	licznik = 0;

	cout << "Podaj ilosc elementow listy:";
	cin >> n;
	for (int i = 0; i < n; i++) {
	cout << "Podaj a:";
	cin >> a;
	add(head, a);

	}
	cout << "Elementy listy to: \n";
	show(head, licznik);
	cout << endl << endl;

	cout << "Odczytanie z pliku.\n";
	readfromfile(head);
	show(head,licznik);
	cout << endl << endl;

	destroy(head);
	//damage(head);
	show(head,licznik);

	cout << "Podaj szukana wartosc: ";
	cin >> b;
	pick_one(head, b);

	cout << "Podaj indeks: ";
	cin >> indeks;
	pick_indeks(head,licznik,indeks);
	show(head, licznik);



	cout << "podaj elementy do zamiany ";
	cin >> nr_el1 >> nr_el2;
	swapElem(head, nr_el1, nr_el2);
	show(head, licznik);
	*/

	//vol2


	list L;
	string a;
	L.head = L.tail = NULL;
	L.count = 0;

	int n;

	cout << "Podaj ilosc elementow tablicy:";
	cin >> n;
	for (int i = 0; i < n; i++) {
	cout << "Podaj a:";
	cin >> a;
	push_back(L, a);

	}
	/*
	readfromfile(L.head);
	pokaz(L);
	cout << endl << endl;

	remove(L, L.head->next);
	pokaz(L);
	*/

	Bombel(L);
	pokaz(L);

	system("Pause");
	return 0;
}