#include <iostream>
#include <chrono>
#include "LinkedList.h"
#include "LinkedListNode.h"
#include "Array.h"

using namespace std;

static int iosif_ll(int step, int count)
{
	LinkedList<int> list;
	for (int i = count; i > 0; i--)
	{
		list.insertFirst(i);
	}
	list.makeCircular();
	LinkedListNode<int>* it = list.getStart();
	for (int i = 0; i < step - 2; i++)
	{
		it = it->getNext();
	}
	list.deleteAfter(it);
	while (list.getStart() != list.getStart()->getNext())
	{
		for (int i = 0; i < step - 1; i++)
		{
			it = it->getNext();
		}
		list.deleteAfter(it);
	}
	cout << "N = " << count << " " << "K = " << step << " survivor: " << list << " ";
	return 0;
}

int iosif_arr(int N, int K)
{
	Array arr(N);

	for (int i = 1; i <= N; i++)
	{

		arr.insert(i, i - 1);

	}

	int DELETE = 0;


	while (arr.getSize() > 1)
	{
		DELETE += (K - 1) % arr.getSize();
		if (DELETE >= arr.getSize())
		{
			DELETE = DELETE % arr.getSize();
			arr.remove(DELETE);
		}
		else
		{
			arr.remove(DELETE);
		}

	}
	cout << "N = " << N << " K = " << K << " survivor: " << arr[0];
	return 0;
}

int main()
{
	cout << "Linked list:" << endl;

	int K = 2, arr[7] = { 1000,5000,10000,50000,100000,500000,1000000 };
	for (int i = 0; i < 7; i++)
	{
		auto start = std::chrono::high_resolution_clock::now();
		iosif_ll(K, arr[i]);
		auto end = std::chrono::high_resolution_clock::now();
		std::chrono::duration<double> diff = end - start;
		std::cout << "Time " << diff.count() << endl;
	}

	cout << endl << endl << "Array:" << endl;

	for (int i = 0; i < 7; i++)
	{
		auto start = std::chrono::high_resolution_clock::now();
		iosif_arr(K, arr[i]);
		auto end = std::chrono::high_resolution_clock::now();
		std::chrono::duration<double> diff = end - start;
		std::cout << " Time " << diff.count() << endl;
	}
	return 0;
}