/*NODU dæmi
Búa til i c++ clasa sem heldur um eintengdanLista með þessum aðferðum
1)Upphafstilla tóman Lista
2)Insert at end (setja nodu i enda skjals)
3)Insert at K (setja nodu i sæti k)
4)Delete at end (eyða nodu aftast)
5)Delete at k ( eyða node i sæti k)
6)Search at k (finna nodu i sæti k)
7)Search by val (finna nodu með gildi val)
8)lenght (hverssu laangur er listi)
9)ToString (prentar allar Nodur)
*/


#include <map>
#include <vector>
#include <fstream>
#include <iostream>
#include <string>
#include <fstream>
#include <unordered_set>
#include <set>

using namespace std;

class Node {
public:
	Node* next;
	int data;
	Node(int data, Node* next) {
		this->data = data;
		this->next = next;
	}
};
class EintengdurListi {
public:
	Node * head;//Geymsla á hau Nodu
	int size;//geymsla á stærð Nodu
			 //Smiður sem Upphafstillir tóman haus og stærð
	EintengdurListi() {
		this->head = NULL;
		this->size = 0;
	}
	//Insertion á nodu á endan
	void InsertNodeAtEnd(int data) {
		//athugar  hvort Hausin okkar er tómur eða ekki ef tómur þá látum hausin vera nýja noda
		if (this->head == NULL) { this->head = new Node(data, NULL); this->size++; return; }
		//búum til current Node sem mun fara yfir listan ef við notum haus nodu fyrir
		//þetta þá missum við staðsetninguna á hausnum og þá eyðilegst all hjá okkur
		Node* curr = this->head;
		//förum i gengum allar nodur þangað til við erum komin að seinastu nodu og svo
		//búum til nýja nodu og tengjum seinustu nodu við hana
		while (curr->next != NULL) { curr = curr->next; }
		Node* nyrNode = new Node(data, NULL);//búum til nýja nodu
		curr->next = nyrNode;//tenjum seinustu nodu við nýja nodu okkar
		this->size++;//bætum stærð við
	}
	//Insertion á node i staðsetningu K
	void InsertNodeAtK(int data, int k) {
		//ef við erum að reyna að setja inn staðsetningu sem er of stór
		if (k > this->size) { cout << "Array Is Out of Range"; return; }
		//ef hann vill búa til haus Nodu
		if (k == 0) {
			//búum til nýja nodu með data og sem visar á hausin
			Node * NyrNoda= new Node(data, this->head);
			//gerum þessa nodu sem hausin þvi að þvi erum buin að tengja NyrNoda með hausin
			//við missum ekki staðsetninguna þegar við stillum hana sem nýjan haus
			this->head = NyrNoda;
			this->size++;
			return;//þarf alltaf að skila annars höldum við áfram
		}
		int i = 1; //teljari fyrir sætin
		Node* curr = this->head;//current
		//utaf ég þarf að setja nodu á milli tveim nodum þá þarf að halda um báðar nodur
		Node* currcurr = curr->next;
		while (currcurr != NULL) {
			if (i == k) {//ef ég er komin á staðsetninguna mina
				/* [curr]->[currcurr]
				   [curr]->[NyrNoda]->[currcurr]*/
				Node* nyrNoda = new Node(data, currcurr);//by til nýja nodu og setja tengi við hana i þarnæstu nodu
				curr->next = nyrNoda;//tengi current nodu við nýjanodu
				this->size++;
				return;//hætti
			}
			i++;
			currcurr = currcurr->next;
			curr = curr->next;
		}
		//ef hann komst i genum all þá vitum við að seinasti staður sem þetta getur verið á er á endanum á lista
		InsertNodeAtEnd(data);
	}
	//Delete fyrir endan á listan
	void DeleteNodeAtEnd() {
		//Við erum bara með Haus nodu i listanum þá eyðym hana og hættum
		if (this->head->next == NULL) {this->head = NULL; this->size--; return; }
		Node* curr = this->head;
		//kikjum hvort þarnæsta noda er null eða ekki þvi við verðum að eyða seinustu nodu
		//og svo stilla næstseinustu lika þannig að hun myndi ekki visa á neitt
		while (curr->next->next != NULL) {curr = curr->next;}
		curr->next = NULL;//nullstillum næstseinasta bendill
		this->size--;
	}
	//Delete fyrir staðsetningu K
	void DeleteNodeAtK(int k) {
		if (k > this->size) { cout << "Array Is Out of Range"; return; }//ef við erum að eyða i sæti sem er ekki til
		if (k == 0) { this->head = this -> head->next; this->size--; }//ef við viljum eyða hausin þá færum okkur um einn
		int i = 1;
		Node * curr = this->head;
		//forum i gegnum allan lista
		while (curr->next != NULL) {
			if (i == k) {//komin á staðsetninguna okkar
				//eina sem við þurfum að gera er bara að hoppa yfir eina nodu
				curr->next = curr->next->next;
				this->size--;
				return;
			}
			curr = curr->next;
			i++;
		}
		DeleteNodeAtEnd();
	}
	//sem skilar gildi i sæti nodu K
	int SearchNodeAtK(int k) {
		if (k > this->size) { cout << "Array Is Out of Range"; return-1; }//ef við erum að eyða i sæti sem er ekki til
		Node * curr = this->head;
		int i = 0;
		//forum i gegnum nodur
		while (curr->next != NULL) {
			if (i == k) { return curr->data;}//ef við finnum tölu þá skilum við henni
			i++;
			curr = curr->next;
		}
		return -1;//ef við myndum komast herna sem myndi þiða villa
	}
	//fall sem skilar nodu með gildi v
	Node* GetNodeWithVal(int v) {
		Node* curr = this->head;
		//forum i gegnum listan þangað til við finnum nodu með gögn sem við erun að leita að
		while (curr!= NULL) {
			if (curr->data == v) { return curr; }//ef gildið er fundið þá skilum við nodu
			curr = curr->next;
		}
		return NULL;//ef það var einginn fund þá skilum við NULL
	}
	//fall sem skilar lengd á listanum
	int Lenght() {
		int i = 0;//breyta sem mun halda um lengd
		Node* curr = this->head;
		//fer i gegnum allar nodur og fyrir hverja nodu þá bæti við teljarann
		while (curr != NULL) {
			i++;
			curr = curr->next;
		}
		this->size = i;//gott að uppfæra size
		return i;
	}
	//Fall sem fer i gegnum allar nodur og skilar streng með alla nodu gildi
	string toString() {
		Node * curr = this->head;//curr
		string txt = "";//tómur strengur sem mun vera samskeitaður
		//forum ignum allar nodur og samskeitum gildin þeirra með strengin
		while (curr != NULL) {
		//fyrir hverja nodu samskeiti ég hana, ég noda to_string sem er aðferð ur #include <string>
			txt = txt + to_string(curr->data) + "|";
			curr = curr->next;
		}
		return txt;//skilum samskeitnum texta
	}
};

int main() {
	EintengdurListi listi;
	listi.InsertNodeAtEnd(3);//testum fallið til að setja nodu fyrir haus
	listi.InsertNodeAtEnd(4);//test fyrir fallið til að setja nodu i enda
	listi.InsertNodeAtK(1, 0);//test fyrir að setja k sem nýjan haus
	listi.InsertNodeAtK(2, 1);//test fyrir að setja nodu á milli tvær nodur
	listi.InsertNodeAtK(5, 4);//test fyrir að setja nodu i enda

	Node* Fundin = listi.GetNodeWithVal(2);//náum i nodu með gildi
	//--------------------------------------------------------------------------------------------
	//við teljum nodur frá 0-1-2-3-4
	cout << "gildi i saeti 3 er :" + to_string(listi.SearchNodeAtK(3)) << endl;//testum search fall
	cout << "Noda sem var fundin med gildi value 2 er fundin " + to_string(Fundin->data) << endl;
	//---------------------------------------------------------------------------------------
	cout << listi.toString()<< endl;
	cout << "Lend a listanum er :" + to_string(listi.Lenght()) << endl;//profum lengt fallið
	//---------------------------------------------------------------------------------------
	listi.DeleteNodeAtEnd();//eyðum seinustu nodu
	cout << listi.toString() << endl;//prentum út nyja listan
	cout << "Lend a listanum er :" + to_string(listi.Lenght()) << endl;//profum lengt fallið
	//---------------------------------------------------------------------------------------
	listi.DeleteNodeAtK(0);//test fyrir eyðslu á haus
	cout << listi.toString() << endl;
	cout << "Lend a listanum er :" + to_string(listi.Lenght()) << endl;//profum lengt fallið
	//---------------------------------------------------------------------------------------
	listi.DeleteNodeAtK(1);//test fyrir eyðslu milli hnuta
	cout << listi.toString() << endl;
	cout << "Lend a listanum er :" + to_string(listi.Lenght()) << endl;//profum lengt fallið
	//-------------------------------------------------------------------------------------
	listi.DeleteNodeAtK(1);//test fyrir á enda hnuts
	cout << listi.toString() << endl;
	cout << "Lend a listanum er :" + to_string(listi.Lenght()) << endl;//profum lengt fallið
	//--------------------------------------------------------------------------------------
	system("PAUSE");
	return 0;
}