#include <iostream>

#include "IntLinkedList.h"
#include "IntLink.h"

IntLinkedList::IntLinkedList() { }

IntLinkedList::~IntLinkedList() {
	IntLink* node = this->next;
	while (node != nullptr) {
		IntLink* next = node->next;
		delete node;
		node = next;
	}
}

IntLink* IntLinkedList::getAt(int index) const {
	if (this->size == 0) return nullptr;
	IntLink* out = this->next;
	for (size_t i = 0; i < this->size; i++) {
		if (out == nullptr) return nullptr;
		if (i > 0) out = out->next;
		if (i == index) return out;
	}
	return nullptr;
}

bool IntLinkedList::setAt(int index, int value) {
	IntLink* node = getAt(index);
	if (node == nullptr) return false;
	node->value = value;
	return true;
}

int IntLinkedList::length1() const {
	size_t accu = 0;
	IntLink* node = this->next;
	while (node != nullptr) {
		accu++;
		node = node->next;
	}
	return accu;
}

int IntLinkedList::length2() const {
	return this->size;
}

void IntLinkedList::bubbleSort() {
	int outer, inner;
	bool sorted;
	for (outer = 0; outer < this->size - 2; outer++) {
		sorted = true; // check if array was modified during inner loop
		for (inner = this->size - 2; inner >= outer; inner--) {
			IntLink* inner_node = getAt(inner);
			if (inner_node->value >= inner_node->next->value) {
				std::swap(inner_node->value, inner_node->next->value);
				sorted = false;
			}
		}
		printf("outer %d:  ", outer);
		showAll();
		if (sorted) break; // break if nothing changed (already sorted)
	}
}

/*
 * geschatte snelheid van dit algoritme: O(n^3)
 *
 * onderbouwing:
 *
 * bubble sort is O(n^2), de getAt functie is O(n). getAt wordt afhankelijk van
 * de grootte van de array een aantal keer uitgevoerd, n^2 * n == n^3 -> O(n^3)
 */

 /*
 * metingen van de duur van het sorteren...
 *
 * aantal waarden: duur in us:
 * 1000   114410
 * 2000   275901
 * 5000   1443233
 * 10000  5585394
 * ...
 */ 

/*
 * gemeten snelheid van dit algoritme: O(n^3)
 * onderbouwing:
 *
 * ik heb google spreadsheets gebruikt om de metingen om te zetten naar een
 * grafiek, en vervolgens een automatische trendlijn te laten maken. bij een
 * exponentiele lijn is er nog wat afwijking van de metingen, terwijl er bij de
 * kwadratische lijn geen afwijking is.
 */

void IntLinkedList::addToStart(int value) {
	this->next = new IntLink(value, this->next);
	this->size++;
}

void IntLinkedList::showAll() const {
	std::cout << "[";
	IntLink* node = this->next;
	while (node != nullptr) {
		std::cout << node->value;
		node = node->next;
		if (node != nullptr) std::cout << ", ";
	}
	std::cout << "]" << std::endl;
}