// Testing of shrub.

#include <iostream>
#include <deque>
#include <list>
#include <ctime>

#include "shrub.h"

class FixedSize {
  int x[5];
} DumbData;


int main() {
	clock_t ticks;
	std::deque<FixedSize>* TestDeque = new std::deque<FixedSize>;
	shrub<FixedSize>* TestShrub = new shrub<FixedSize>;
	std::list<FixedSize>* TestList = new std::list<FixedSize>;
	int NumberOfTimes = 1000000;

	// The std::deque test.
	std::cout << "Deque test:" << std::endl;

	// Test #1: push_back.
	ticks = clock();
	for(int n = 0; n < NumberOfTimes; ++n) {
		TestDeque->push_back(DumbData);
	}
	ticks = clock() - ticks;
	std::cout << "Ticks it took to do " << NumberOfTimes << " push backs: " << ticks << std::endl;

	// Test #2: Iteration.
	ticks = clock();
	std::deque<FixedSize>::const_iterator DequeIter = TestDeque->begin();
	while(DequeIter != TestDeque->end()) {
		++DequeIter;
	}
	ticks = clock() - ticks;
	std::cout << "Ticks it took to iterate over the deque: " << ticks << std::endl;

	// Test #3: random access.
	ticks = clock();
	FixedSize DequeDummy;
	for(int n = 0; n < NumberOfTimes; ++n) {
		srand(time(nullptr));
		DequeDummy = TestDeque->at(rand() % (TestDeque->size() + 1));
	}
	ticks = clock() - ticks;
	std::cout << "Ticks it took to do " << NumberOfTimes << " random accesses: " << ticks << std::endl;

	// Test #4: pop_back.
	ticks = clock();
	for(int n = 0; n < NumberOfTimes; ++n) {
		TestDeque->pop_front();
	}
	ticks = clock() - ticks;
	std::cout << "Ticks it took to do " << NumberOfTimes << " pop fronts: " << ticks << std::endl;

	std::cout << "Random insertions and deletions on deques and vectors take thousands of ticks." << std::endl;
	std::cout << "They are not used in practice" << std::endl;

	/*
	// Test #5: random insertion.
	ticks = clock();
	for(int n = 0; n < NumberOfTimes; ++n) {
		srand(time(nullptr));
		TestDeque->insert(TestDeque->begin() + rand() % (TestDeque->size() + 1), DumbData);
	}
	ticks = clock() - ticks;
	std::cout << "Ticks it took to do " << NumberOfTimes << " pseudo random insertions: " << ticks << std::endl;

	// Test #6: random deletion.
	ticks = clock();
	for(int n = 0; n < NumberOfTimes; ++n) {
		srand(time(nullptr));
		TestDeque->erase(TestDeque->begin() + rand() % TestDeque->size());
	}
	ticks = clock() - ticks;
	std::cout << "Ticks it took to do " << NumberOfTimes << " pseudo random deletions: " << ticks << std::endl;
	*/

	// The shrub test.
	std::cout << std::endl << "Shrub test:" << std::endl;

	// Test #1: push_back.
	ticks = clock();
	for(int n = 0; n < NumberOfTimes; ++n) {
		TestShrub->push_back(DumbData);
	}
	ticks = clock() - ticks;
	std::cout << "Ticks it took to do " << NumberOfTimes << " push backs: " << ticks << std::endl;

	// Test #2: Iteration.
	ticks = clock();
	shrub<FixedSize>::const_iterator ShrubIter = TestShrub->begin();
	while(ShrubIter != TestShrub->end()) {
		++ShrubIter;
	}
	ticks = clock() - ticks;
	std::cout << "Ticks it took to iterate over the shrub: " << ticks << std::endl;

	// Test #3: pop_back.
	ticks = clock();
	for(int n = 0; n < NumberOfTimes; ++n) {
		TestShrub->pop_front();
	}
	ticks = clock() - ticks;
	std::cout << "Ticks it took to do " << NumberOfTimes << " pop fronts: " << ticks << std::endl;

	// Test #4: random insertion.
	ticks = clock();
	for(int n = 0; n < NumberOfTimes; ++n) {
		srand(time(nullptr));
		TestShrub->insert(TestShrub->position(rand() % (TestShrub->size() + 1)), DumbData);
	}
	ticks = clock() - ticks;
	std::cout << "Ticks it took to do " << NumberOfTimes << " pseudo random insertions: " << ticks << std::endl;

	// Test #5: random access.
	ticks = clock();
	FixedSize ShrubDummy;
	for(int n = 0; n < NumberOfTimes; ++n) {
		srand(time(nullptr));
		ShrubDummy = TestShrub->at(rand() % (TestDeque->size() + 1));
	}
	ticks = clock() - ticks;
	std::cout << "Ticks it took to do " << NumberOfTimes << " random accesses: " << ticks << std::endl;

	// Test #6: random deletion.
	ticks = clock();
	for(int n = 0; n < NumberOfTimes; ++n) {
		srand(time(nullptr));
		TestShrub->erase(TestShrub->position(rand() % TestShrub->size()));
	}
	ticks = clock() - ticks;
	std::cout << "Ticks it took to do " << NumberOfTimes << " pseudo random deletions: " << ticks << std::endl;

	// The std::list test.
	std::cout << std::endl << "List test:" << std::endl;

	// Test #1: push_back.
	ticks = clock();
	for(int n = 0; n < NumberOfTimes; ++n) {
		TestList->push_back(DumbData);
	}
	ticks = clock() - ticks;
	std::cout << "Ticks it took to do " << NumberOfTimes << " push backs: " << ticks << std::endl;

	// Test #2: Iteration.
	ticks = clock();
	std::list<FixedSize>::const_iterator ListIter = TestList->begin();
	while(ListIter != TestList->end()) {
		++ListIter;
	}
	ticks = clock() - ticks;
	std::cout << "Ticks it took to iterate over the list: " << ticks << std::endl;

	// Test #3: pop_back.
	ticks = clock();
	for(int n = 0; n < NumberOfTimes; ++n) {
		TestList->pop_front();
	}
	ticks = clock() - ticks;
	std::cout << "Ticks it took to do " << NumberOfTimes << " pop fronts: " << ticks << std::endl;

	// Test #4: random insertion.
	ticks = clock();
	for(int n = 0; n < NumberOfTimes; ++n) {
		srand(time(nullptr));
		ListIter = TestList->begin();
		for(int n = 0; n < rand() % (TestList->size() + 1); ++n) {
			++ListIter;
		}
		TestList->insert(ListIter, DumbData);
	}
	ticks = clock() - ticks;
	std::cout << "Ticks it took to do " << NumberOfTimes << " pseudo random insertions: " << ticks << std::endl;

	// Test #5: random access.
	ticks = clock();
	FixedSize ListDummy;
	for(int n = 0; n < NumberOfTimes; ++n) {
		srand(time(nullptr));
		ListIter = TestList->begin();
		for(int n = 0; n < rand() % (TestList->size() + 1); ++n) {
			++ListIter;
		}
		ListDummy = *ListIter;
	}
	ticks = clock() - ticks;
	std::cout << "Ticks it took to do " << NumberOfTimes << " random accesses: " << ticks << std::endl;

	// Test #6: random deletion.
	ticks = clock();
	for(int n = 0; n < NumberOfTimes; ++n) {
		srand(time(nullptr));
		ListIter = TestList->begin();
		for(int n = 0; n < rand() % TestList->size(); ++n) {
			++ListIter;
		}
		TestList->erase(ListIter);
	}
	ticks = clock() - ticks;
	std::cout << "Ticks it took to do " << NumberOfTimes << " pseudo random deletions: " << ticks << std::endl;
}