#include "array_report.h" static int before(const ra_cell *cells, unsigned left, unsigned right) { if (cells[left].value != cells[right].value) { return cells[left].value < cells[right].value; } return cells[left].position < cells[right].position; } void ra_order(const ra_cell *cells, size_t size, unsigned *order) { for (size_t index = 0; index < size; ++index) { order[index] = (unsigned)index; } for (size_t index = 1; index < size; ++index) { unsigned key = order[index]; size_t destination = index; while (destination > 0 && before(cells, key, order[destination - 1])) { order[destination] = order[destination - 1]; destination -= 1; } order[destination] = key; } } static long long distinct_count(const ra_cell *cells, const unsigned *order, size_t size) { if (size == 0) { return 0; } long long result = 1; for (size_t index = 1; index < size; ++index) { int previous = cells[order[index - 1]].value; int current = cells[order[index]].value; if (current != previous) { result += 1; } } return result; } static long long lower_quantile(const ra_cell *cells, const unsigned *order, size_t size, unsigned numerator) { if (size == 0) { return 0; } size_t rank = (size - 1) * numerator / 4; return cells[order[rank]].value; } static long long sorted_weight(const ra_cell *cells, const unsigned *order, size_t size) { long long result = 0; for (size_t index = 0; index < size; ++index) { long long weight = (long long)index + 1; result += weight * cells[order[index]].value; } return result; } static long long adjacent_gap(const ra_cell *cells, const unsigned *order, size_t size) { long long result = 0; for (size_t index = 1; index < size; ++index) { long long lower = cells[order[index - 1]].value; long long upper = cells[order[index]].value; long long gap = upper - lower; if (gap > result) { result = gap; } } return result; } static long long median_distance(const ra_cell *cells, const unsigned *order, size_t size) { if (size == 0) { return 0; } int median = cells[order[(size - 1) / 2]].value; long long result = 0; for (size_t index = 0; index < size; ++index) { long long difference = (long long)cells[index].value - median; result += difference < 0 ? -difference : difference; } return result; } static size_t bucket_of(int value, int lower, int upper, size_t bins) { if (lower == upper) { return 0; } long long offset = (long long)value - lower; long long span = (long long)upper - lower + 1; size_t bucket = (size_t)(offset * (long long)bins / span); if (bucket >= bins) { bucket = bins - 1; } return bucket; } static void bucket_summary(const ra_request *request, const ra_cell *cells, const unsigned *order, size_t size, ra_report *report) { if (size == 0) { return; } size_t counts[8] = {0}; int lower = cells[order[0]].value; int upper = cells[order[size - 1]].value; size_t bins = (size_t)request->bins; for (size_t index = 0; index < size; ++index) { size_t bucket = bucket_of(cells[index].value, lower, upper, bins); counts[bucket] += 1; } size_t busiest = 0; size_t occupied = 0; long long weight = 0; for (size_t bucket = 0; bucket < bins; ++bucket) { if (counts[bucket] > counts[busiest]) { busiest = bucket; } if (counts[bucket] != 0) { occupied += 1; } weight += (long long)(bucket + 1) * (long long)counts[bucket]; } report->v[31] = (long long)busiest; report->v[32] = (long long)counts[busiest]; report->v[33] = (long long)occupied; report->v[34] = weight; } static long long inversion_count(const ra_cell *cells, size_t size) { long long result = 0; for (size_t left = 0; left < size; ++left) { for (size_t right = left + 1; right < size; ++right) { if (cells[left].value > cells[right].value) { result += 1; } } } return result; } void ra_rank(const ra_request *request, const ra_cell *cells, const unsigned *order, size_t size, ra_report *report) { report->v[23] = distinct_count(cells, order, size); report->v[24] = lower_quantile(cells, order, size, 1); report->v[25] = lower_quantile(cells, order, size, 2); report->v[26] = lower_quantile(cells, order, size, 3); report->v[27] = sorted_weight(cells, order, size); report->v[28] = adjacent_gap(cells, order, size); report->v[29] = median_distance(cells, order, size); if (size != 0) { report->v[30] = cells[order[0]].position; } bucket_summary(request, cells, order, size, report); report->v[35] = inversion_count(cells, size); }