#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <vector>

#include "AVLCommands.h"

#define SAMPLE_SIZE 1000
#define NUM_TESTS 10000

int main() {
	//int whileLoopNum = 0;

	// C++11 random number tutorial: https://gist.github.com/PhDP/5289449
	// Seed random number generator
	std::mt19937_64 rng(time(0));
	// Create uniform distribution
	std::uniform_int_distribution<int> unif(
		std::numeric_limits<int>::min(), std::numeric_limits<int>::max());
	std::uniform_int_distribution<int> op(0,10);

	std::vector<int> sampleData, AVLSortedData;
	sampleData.reserve(SAMPLE_SIZE);
	AVLSortedData.reserve(SAMPLE_SIZE);
	std::cout << "Running tests..." << std::flush;
	for (unsigned int sample = 0; sample < NUM_TESTS; sample++) {
		AVLCommands avl;
		// On size_t usage here: https://stackoverflow.com/questions/131803/unsigned-int-vs-size-t
		for (size_t i = 0; i < SAMPLE_SIZE; i++) {
			//std::cout << "Loop number: " << i << std::endl;
			//std::cout << "for sample: " << sample << std::endl;
			if (op(rng) == 0 && !avl.empty()) {
				//std::cout << "I will delete!" << std::endl;
				avl.Delete(sampleData.back());
				//std::cout << "I have deleted!" << std::endl;
				sampleData.pop_back();
			} else {
				// Add random integer to array
				int x = unif(rng);
				//std::cout << "I will insert!" << std::endl;
				avl.Insert(x);
				//std::cout << "I have inserted!" << std::endl;
				sampleData.push_back(x);
			}
		}
		while (!avl.empty()) {
			//std::cout << "I will delete the min!" << std::endl;
			AVLSortedData.push_back(avl.DeleteMin());
			//whileLoopNum++;
			//std::cout << "I have delete " << whileLoopNum << " mins!" << std::endl;
		}
		//whileLoopNum = 0;
		std::sort(sampleData.begin(), sampleData.end());
		assert(sampleData == AVLSortedData);
		AVLSortedData.clear();
		sampleData.clear();
		if (sample % (NUM_TESTS / 10) == 0) {
			std::cout << "." << std::flush;
		}
	}
	std::cout << "Tests complete.\n";
}