#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// Замер времени
class timer {
	clock_t start;
	char buf[20];
public:
	timer();
	void init(); // начало замера
	const char* value(); // текущее значение
};

timer::timer()
{
	init();
}

void timer::init()
{
	start = clock();
}

// Вывод времени
const char* timer::value()
{
	clock_t t = clock() - start;
	int sec = t / CLOCKS_PER_SEC;
	if(sec > 1000) {
		sprintf(buf, "%.0f sec", (double)t / CLOCKS_PER_SEC);
	} else if(sec > 100) {
		sprintf(buf, "%.1f sec", (double)t / CLOCKS_PER_SEC);
	} else if(sec > 10) {
		sprintf(buf, "%.2f sec", (double)t / CLOCKS_PER_SEC);
	} else {
		sprintf(buf, "%.3f sec", (double)t / CLOCKS_PER_SEC);
	}
	return buf;
}

//******************************************************
// Размер тестового массива
#define TEST_SIZE 10000
//******************************************************

// Заполнение исходных данных
void init(int* arr)
{
	timer t;
	// Заполняем уникальными значениями
	for(int i = 0; i != TEST_SIZE; i++) arr[i] = i;
	// Перемешиваем
	int r = 54323; // ГСЧ с постоянной последовательстью
	for(int i = 0; i != TEST_SIZE; i++) {
		do {
			r = (r * 12347 + 1) % TEST_SIZE;
		} while(r < 0);
		
		int j = arr[i];
		arr[i] = arr[r];
		arr[r] = j;
	}
	printf("Init %u elements. %s\n", TEST_SIZE, t.value());
}

// Вывод содержимого массива
void print(const char* text, int* arr)
{
	printf(text);
	unsigned int check = 0;
	for(int i = 0; i < TEST_SIZE; i++) {
		if(i < 10) printf("%d ", arr[i]);
		check += i * arr[i];
	}
	printf(" sum %X\n", check);
}

// Решение перебором
void perebor(int* data, int* res)
{
	timer t;
	for(int i = 0; i < TEST_SIZE; i++) {
		for(int j = 0; j < i; j++) {
			if(data[j] > data[i]) res[i]++;
		}
	}
	printf("Perebor %s\n", t.value());
}


int compare_int(const void* a, const void* b)
{
  return ( **(int**)a - **(int**)b );
}

// С сортировкой и массивом счетчиков
void with_counter(int* data, int* res)
{
	timer t;
	int** idx = (int**)malloc(TEST_SIZE * sizeof(int*)); // индексы сортировки
	if(!idx) {
		printf("No memory\n");
		return;
	}
	// Заполнение индексов и сортировка
	for(int i = 0; i < TEST_SIZE; i++) idx[i] = &data[i];
	qsort(idx, TEST_SIZE, sizeof(int*), compare_int);

	// Выбор шага счетчика
	int step = 2; 
	int step_bit = 1; 
	int y = TEST_SIZE;
	while(true) {
		int x = step / 2 + TEST_SIZE / (step * 2);
		if(x > y || step >= TEST_SIZE) {
			step >>= 1;
			step_bit--;
			break;
		}
		y = x;
		step <<= 1;
		step_bit++;
	}
	// Массив счетчиков
	int cnt_size = TEST_SIZE / step + 1;
	int* cnt = (int*) malloc(cnt_size * sizeof(int)); // счетчики
	if(!cnt) {
		printf("No memory\n");
		free(idx);
		return;
	}
	for(int i = 0; i < cnt_size; i++) cnt[i] = step;
	// Расчет
	int min = *idx[0];
	int mask = 0x7FFFFFFF ^ (step - 1); // маска для поиска первого элемента группы
	for(int i = 0; i < TEST_SIZE; i++) {
		int pos = idx[i] - data; // индекс минимального элемента в data
		 // обнуление посчитанного
		data[pos] = min;
		int cnt_pos = pos >> step_bit; // индекс счетчика
		cnt[cnt_pos]--;
		// Подсчет от начала группы
		for(int j = pos & mask; j < pos; j++) {
			if(data[j] > data[pos]) res[pos]++;
		}
		// Добавление полных групп
		for(int j = 0; j < cnt_pos; j++) {
			res[pos] += cnt[j];
		}
	}
	free(cnt);
	free(idx);
	printf("Counters %s\n", t.value());
}


int main(int argc, char* argv[])
{

	int* data = (int*)calloc(TEST_SIZE, sizeof(int)); // массив исходных данных
	int* res = (int*)calloc(TEST_SIZE, sizeof(int)); // массив для результата
	if(!data || !res) {
		printf("No memory\n");
	} else {
		// Заполнение исходных данных
		init(data); 
		print("Data   ", data);
		// Расчет перебором
		perebor(data, res);
		print("Result ", res);
		memset(res, 0, sizeof(int)*TEST_SIZE);

		// Расчет c сортировкой и групповыми счетчиками
		with_counter(data, res);
		// Вывод результата
		print("Result ", res);
	}

	if(data) free(data);
	if(res) free(res);

	system("pause");
	return 0;
}

// С сортировкой и массивом счетчиков
void with_counter(int* data, int* res)
{
	timer t;
	int** idx = (int**)malloc(TEST_SIZE * sizeof(int*)); // индексы сортировки
	if(!idx) {
		printf("No memory\n");
		return;
	}
	// Заполнение индексов и сортировка
	for(int i = 0; i < TEST_SIZE; i++) idx[i] = &data[i];
	qsort(idx, TEST_SIZE, sizeof(int*), compare_int);

	// Выбор шага счетчика
	int step = (int)sqrt((double)TEST_SIZE);
	// Массив счетчиков
	int cnt_size = TEST_SIZE / step + 1;
	int* cnt = (int*) malloc(cnt_size * sizeof(int)); // счетчики
	if(!cnt) {
		printf("No memory\n");
		free(idx);
		return;
	}
	for(int i = 0; i < cnt_size; i++) cnt[i] = step;
	// Расчет
	int min = *idx[0];
	for(int i = 0; i < TEST_SIZE; i++) {
		int pos = idx[i] - data; // индекс минимального элемента в data
		 // обнуление посчитанного
		data[pos] = min;
		int cnt_pos = pos / step; // индекс счетчика
		cnt[cnt_pos]--;
		// Подсчет от начала группы
		for(int j = cnt_pos * step; j < pos; j++) {
			if(data[j] > data[pos]) res[pos]++;
		}
		// Добавление полных групп
		for(int j = 0; j < cnt_pos; j++) {
			res[pos] += cnt[j];
		}
	}
	free(cnt);
	free(idx);
	printf("Counters %s\n", t.value());
}

// С сортировкой и массивом счетчиков
void with_counter(int* data, int* res)
{
	timer t;
	int** idx = (int**)malloc(TEST_SIZE * sizeof(int*)); // индексы сортировки
	if(!idx) {
		printf("No memory\n");
	} else {
		// Заполнение индексов и сортировка
		for(int i = 0; i < TEST_SIZE; i++) idx[i] = &data[i];
		qsort(idx, TEST_SIZE, sizeof(int*), compare_int);
		// Выбор шага счетчика
		int step = (int)sqrt((double)TEST_SIZE);
		// Массив счетчиков
		int cnt_size = TEST_SIZE / step + 1;
		int* cnt = (int*) malloc(cnt_size * sizeof(int)); // счетчики
		if(!cnt) {
			printf("No memory\n");
		} else {
			for(int i = 0; i < cnt_size; i++) cnt[i] = step;
			// Расчет
			int min = *idx[0];
			for(int i = 0; i < TEST_SIZE; i++) {
				int pos = idx[i] - data; // индекс минимального элемента в data
				 // обнуление посчитанного
				data[pos] = min;
				int cnt_pos = pos / step; // индекс счетчика
				cnt[cnt_pos]--;
				// Подсчет от начала группы
				for(int j = cnt_pos * step; j < pos; j++) {
					if(data[j] > data[pos]) res[pos]++;
				}
				// Добавление полных групп
				for(int j = 0; j < cnt_pos; j++) {
					res[pos] += cnt[j];
				}
			}
			free(cnt);
		}
		free(idx);
	}
	printf("Counters %s\n", t.value());
}

#include <vector>
#include <algorithm>
bool compare_int_ptr(int* i,int* j) { return (*i < *j); }

// С сортировкой и деревом счетчиков
void with_counter_tree(int* data, int* res)
{
	timer t;
	// Подготовка индекса с порядком обхода
	std::vector<int*> idx(TEST_SIZE);
	for(int i = 0; i < TEST_SIZE; i++) idx[i] = &data[i];
	std::sort(idx.begin(), idx.end(), compare_int_ptr);
	// Инициализация дерева счетчиков
	std::vector<std::vector<int>> cnt_tree;
	for(int i = 2; i < TEST_SIZE; i <<= 1) {
		cnt_tree.resize(cnt_tree.size() + 1);
		cnt_tree.back().resize(TEST_SIZE / i + 1);
	}
	int cnt_levels = cnt_tree.size();
	// Расчет
	for(int i = 0; i < TEST_SIZE; i++) {
		int pos = idx[i] - data; // индекс минимального элемента в data
		res[pos] = pos;
		// подсчет кол-ва меньших data[pos]
		for(int l = 0, j = pos - 1; l < cnt_levels && j >= 0; l++) {
			j >>= 1;
			do {
				res[pos] -= cnt_tree[l][j];
				j--;
			} while((j & 1) == 0);
		}
		// увеличение счетчиков заполненных
		for(int l = 0, j = pos; l < cnt_levels; l++) {
			j >>= 1;
			cnt_tree[l][j]++;
		}
	}
	printf("Counters tree %s\n", t.value());
}

void with_counter_tree_1(int* data, int* res)
{
	// Подготовка индекса с порядком обхода
	std::vector<int*> idx(TEST_SIZE);
	for(int i = 0; i < TEST_SIZE; i++) idx[i] = &data[i];
	std::sort(idx.begin(), idx.end(), compare_int_ptr);
	// Расчет
	for(int i = 0; i < TEST_SIZE; i++) {
		int pos = idx[i] - data; // индекс минимального элемента в data
		printf("insert data[%d] = %d\n", pos, data[pos]);
	}
}

#include <vector>
#include <algorithm>
bool compare_int_ptr(int* i,int* j) { return (*i < *j); }
// С сортировкой и деревом счетчиков
void with_counter_tree(int* data, int* res)
{
	timer t;
	// Подготовка индекса с порядком обхода
	std::vector<int*> idx(TEST_SIZE);
	for(int i = 0; i < TEST_SIZE; i++) idx[i] = &data[i];
	std::sort(idx.begin(), idx.end(), compare_int_ptr);
	// Инициализация дерева счетчиков
	std::vector<std::vector<int>> cnt_tree;
	for(int i = 2; i < TEST_SIZE; i <<= 1) {
		cnt_tree.resize(cnt_tree.size() + 1);
		cnt_tree.back().resize(TEST_SIZE / i + 1);
	}
	int cnt_levels = cnt_tree.size();
	// Расчет
	for(int i = 0; i < TEST_SIZE; i++) {
		int pos = idx[i] - data; // индекс минимального элемента в data
		res[pos] = pos;
		// подсчет кол-ва меньших data[pos]
		for(int l = 0, j = pos - 1; l < cnt_levels && j >= 0; l++) {
			j >>= 1;
			if((j & 1) == 0) {
				res[pos] -= cnt_tree[l][j];
				j--;
			};
		}
		// увеличение счетчиков заполненных
		for(int l = 0, j = pos; l < cnt_levels; l++) {
			j >>= 1;
			cnt_tree[l][j]++;
		}
	}
	printf("Counters tree %s\n", t.value());
}

#include <set>
void with_set(int* data, int* res)
{
	timer t;
	std::set<int> tree;
	tree.get_allocator().allocate(TEST_SIZE);
	for(int i = 0; i < TEST_SIZE; i++) {
		// добавляем элемент
		tree.insert(data[i]);
	}
	printf("Fill tree %s\n", t.value());
	timer t2;
	tree.clear();
	printf("Clear tree %s\n", t2.value());
}