#pragma once

#include <string>
using namespace std;

class node {
public:
	node * next;
	string data;

};

class linkedList {

private:
	node * head;

public:
	linkedList() {
		head = NULL;
	}

	void addFront(string item) {
		node * temp = new node;

		temp->data = item;
		temp->next = head;
		head = temp;
	}

	void addBack(string item) {
		node * temp = new node;
		temp->data = item;
		temp->next = NULL;

		// empty list
		if (head == NULL) {
			head = temp;
		}
		// not empty list
		else {
			node * current = head;

			while (current->next != NULL) {
				current = current->next;
			}
			current->next = temp;
		}
	}

	// returns the first item on the list and removes it
	string pop() {
		string t = head->data;
		node * deleteThis = head;
		head = head->next;
		delete deleteThis;
		return t;
	}

	void remove(string item) {
		if (head == NULL) {

		}
		else if (head->next == NULL) {
			head = NULL;
		}
		else {
			// special cases, if items isnt found
			bool flag = false;

			node * previous = head;
			node * current = head;
			while (current != NULL) {
				if (current->data != item) {
					current = current->next;
					if (previous->next != current) {
						previous = previous->next;
					}
				}
				else {
					flag = true;
					break;
				}
			}
			if (flag) {
				if (current->next == NULL) {
					previous->next = NULL;
				}
				else {
					if (previous == head) {
						head = head->next;
					}
					else {
						previous->next = current->next;
					}
				}
			}
			else {
				// debugg code
				cout << "item " << item << " wasn't found in the list" << endl;
			}
			delete current;
		}
	}
	
	// sort the items of the linked list
	void sort() {

		if (head == NULL  || head->next == NULL) {
			// list is either empty, or has one item, no need to sort
		}
		else {
			node * lefter = head;
			node * smallest = head;
			node * zombie = head->next;

			while (lefter != NULL) {
				zombie = lefter;
				while (zombie != NULL) {
					if (zombie->data < smallest->data) {
						cout << "smaller one  = " << zombie->data << endl;
						smallest = zombie;
					}
					zombie = zombie->next;
				}

				// switch the values
				string l = lefter->data;
				lefter->data = smallest->data;
				smallest->data = l;
				
				lefter = lefter->next;
			}
		}
	}

	void display() {
		cout << "\n\n== START OF DISPLAY ==" << endl;
		node * zomb = head;

		while (zomb != NULL) {
			cout << zomb->data << endl;
			zomb = zomb->next;
		}
		cout << "== END OF DISPLAY ==\n\n" << endl;
	}
};