#include <iostream>
#include "IntDoubleLinkedList.h"
#include "IntDoubleLink.h"

IntDoubleLinkedList::IntDoubleLinkedList() { }
IntDoubleLinkedList::~IntDoubleLinkedList() { }

void IntDoubleLinkedList::initFirstElement(int value) {
	this->head = new IntDoubleLink(value, nullptr, nullptr);
	this->tail = this->head;
}

void IntDoubleLinkedList::insertAtStart(int value) {
	this->size++;
	if (this->size == 1) return initFirstElement(value);

	// this->tail->prev is used as the new instance holder
	this->tail->prev = new IntDoubleLink(value, nullptr, this->tail);
	this->tail->prev->next = this->tail; // yes
	this->tail = this->tail->prev;
}

void IntDoubleLinkedList::insertAtEnd(int value) {
	this->size++;
	if (this->size == 1) return initFirstElement(value);

	this->head->next = new IntDoubleLink(value, this->head, nullptr);
	this->head->next->prev = this->head;
	this->head = this->head->next;
}

bool IntDoubleLinkedList::removeAtStart() {
	// can't remove anything from an empty list
	if (this->tail == nullptr) return false;

	// clear list if last element remaining is deleted
	if (this->tail->next == nullptr) {
		head = tail = nullptr;
		size = 0;
		return true;
	}

	// delete and shift
	IntDoubleLink* node = this->tail;
	this->tail = this->tail->next;
	delete node;
	size--;

	return true;
}

bool IntDoubleLinkedList::removeAtEnd() {
	// can't remove anything from an empty list
	if (this->head == nullptr) return false;

	// clear list if last element remaining is deleted
	if (this->head->prev == nullptr) {
		head = tail = nullptr;
		size = 0;
		return true;
	}

	// delete and shift
	IntDoubleLink* node = this->head;
	this->head = this->head->prev;
	delete node;
	size--;

	return true;
}

IntDoubleLink* IntDoubleLinkedList::getHead() { return this->head; }
IntDoubleLink* IntDoubleLinkedList::getTail() { return this->tail; }

int IntDoubleLinkedList::_indexOf(IntDoubleLink* s) {
	int i = 0;
	IntDoubleLink* c = tail;
	while (c != nullptr) {
		if (c == s) return i;
		i++;
		c = c->next;
	}

	return -1;
}

void IntDoubleLinkedList::rapidBubbleSort() {
	// waarom moet hier   v   ook een pointer sterretje staan!?
	IntDoubleLink *outer, *inner;
	bool sorted;
	for (outer = tail; outer != head; outer = outer->next) {
		sorted = true; // check if array was modified during inner loop
		for (inner = head->prev; inner != outer->prev; inner = inner->prev) {
			// printf("inner [%d, %d]\n", _indexOf(inner), _indexOf(inner->next));
			if (inner->value >= inner->next->value) {
				std::swap(inner->value, inner->next->value);
				sorted = false;
			}
		}
		// printf("outer %d: ", _indexOf(outer)); // indexOf printing for loop debugging
		// showAll();
		if (sorted) break; // break if nothing changed (already sorted)
	}
}

/*
 * metingen van de duur van het sorteren...
 *
 * aantal waarden: duur in us:
 * 1000   4718
 * 2000   19976
 * 5000   131068
 * 10000  547875
 * ...
 */ 

/*
 * gemeten snelheid van dit algoritme: O(n^2)
 * onderbouwing:
 *
 * aan de structuur van de zoekfunctie is niets veranderd, er zijn nog steeds
 * twee for-lussen waar het aantal iteraties recht evenredig is met de
 * arraygrotte. mijn zoekfunctie gebruikt geen getAt of setAt, dus er worden
 * geen extra 'factoren' van n toegevoegd
 */

/*
 * Vergelijking met bubblesort van week 3 deel 1
 *
 * hij draait wel een ordergrootte sneller dan in deel 1 :^)
 */

void IntDoubleLinkedList::insertAction(int code) {
	while (head != actionCursor)
		if (!removeAtEnd()) break;
	insertAtEnd(code);
	actionCursor = head;
}

int IntDoubleLinkedList::undo() {
	if (actionCursor->prev != nullptr)
		actionCursor = actionCursor->prev;
	return actionCursor->value;
}

int IntDoubleLinkedList::redo() {
	if (actionCursor->next != nullptr)
		actionCursor = actionCursor->next;
	return actionCursor->value;
}

int IntDoubleLinkedList::getCurrentAction() {
	return actionCursor->value;
}

void IntDoubleLinkedList::showAll() {
	std::cout << "[";
	IntDoubleLink* node = this->tail;
	while (node != nullptr) {
		if (node == actionCursor) std::cout << "{"; // curly braces for highlighting actionCursor
		std::cout << node->value;
		if (node == actionCursor) std::cout << "}";
		node = node->next;
		if (node != nullptr) std::cout << ", ";
	}
	std::cout << "]" << std::endl;
}