#include <windows.h>
#include <stdio.h>

#include <string>
#include <vector>
#include <algorithm>
#include <time.h>

#define TEST_SIZE 10000000

bool is_sort(std::vector<std::string> &a) {
	if (a.size() <= 1) return true;
	for(size_t i = a.size() - 1; i > 0; i--) {
		if(a[i - 1] > a[i]) {
			return false;
		}
	}
	return true;
}

bool is_sort2(std::string *a, size_t size) {
	if (size <= 1) return true;
	for (size_t i = 1; i < size; i++) {
		if (a[i - 1] > a[i]) {
			return false;
		}
	}
	return true;
}

bool is_sort3(std::vector<std::string> &a) {
	if (a.size() <= 1) return true;
	for (std::vector<std::string>::iterator prev = a.begin(), it = a.begin() + 1; it != a.end(); it++, prev++) {
		if (*prev > *it) {
			return false;
		}
	}
	return true;
}

bool is_sort4(std::string *a, size_t size) {
	if (size <= 1) return true;
	std::string *end = &a[size];
	for (std::string *i = &a[1], *prev = &a[0]; i < end; i++, prev++) {
		if (*prev > *i) {
			return false;
		}
	}
	return true;
}

std::vector<std::string> a(TEST_SIZE);

__declspec(noinline) void test1() {
	clock_t t = clock();
	if (is_sort(a)) {
		printf("Ordered %d ms\n", clock() - t);
	}
	else {
		printf("Unordered %d ms\n", clock() - t);
	}
}

__declspec(noinline) void test2() {
	clock_t t = clock();
	if (is_sort2(&a[0], a.size())) {
		printf("Ordered2 %d ms\n", clock() - t);
	}
	else {
		printf("Unordered2 %d ms\n", clock() - t);
	}
}

__declspec(noinline) void test3() {
	clock_t t = clock();
	if (is_sort3(a)) {
		printf("Ordered3 %d ms\n", clock() - t);
	}
	else {
		printf("Unordered3 %d ms\n", clock() - t);
	}
}

__declspec(noinline) void test4() {
	clock_t t = clock();
	if (is_sort4(&a[0], a.size())) {
		printf("Ordered4 %d ms\n", clock() - t);
	}
	else {
		printf("Unordered4 %d ms\n", clock() - t);
	}
}

int main()
{
	uint32_t k = 123456;
	for (int i = 0; i < TEST_SIZE; i++) {
		char buf[10];
		_itoa(k, buf, 10);
		a[i] = buf;
		k = (k * 65537 + 2017) % 1000000;
	}
	printf("Load OK\n");
	clock_t t = clock();
	std::sort(a.begin(), a.end());
	printf("Sort %d ms\n", clock() - t);
	t = clock();
	std::sort(a.begin(), a.end());
	printf("Sort2 %d ms\n", clock() - t);
	test1();
	test1();
	test1();
	test2();
	test2();
	test2();
	test3();
	test3();
	test3();
	test4();
	test4();
	test4();

	return 0;
}