21 #include "config_auto.h"
40 STATS::STATS(int32_t min_bucket_value, int32_t max_bucket_value_plus_1) {
41 if (max_bucket_value_plus_1 <= min_bucket_value) {
43 max_bucket_value_plus_1 = 1;
45 rangemin_ = min_bucket_value;
46 rangemax_ = max_bucket_value_plus_1;
47 buckets_ =
new int32_t[rangemax_ - rangemin_];
56 bool STATS::set_range(int32_t min_bucket_value, int32_t max_bucket_value_plus_1) {
57 if (max_bucket_value_plus_1 <= min_bucket_value) {
60 if (rangemax_ - rangemin_ != max_bucket_value_plus_1 - min_bucket_value) {
62 buckets_ =
new int32_t[max_bucket_value_plus_1 - min_bucket_value];
64 rangemin_ = min_bucket_value;
65 rangemax_ = max_bucket_value_plus_1;
77 if (buckets_ !=
nullptr)
78 memset(buckets_, 0, (rangemax_ - rangemin_) *
sizeof(buckets_[0]));
94 if (buckets_ ==
nullptr) {
97 value =
ClipToRange(value, rangemin_, rangemax_ - 1);
98 buckets_[value - rangemin_] +=
count;
99 total_count_ +=
count;
108 if (buckets_ ==
nullptr) {
111 int32_t max = buckets_[0];
112 int32_t maxindex = 0;
113 for (
int index = rangemax_ - rangemin_ - 1; index > 0; --index) {
114 if (buckets_[index] > max) {
115 max = buckets_[index];
119 return maxindex + rangemin_;
128 if (buckets_ ==
nullptr || total_count_ <= 0) {
129 return static_cast<double>(rangemin_);
132 for (
int index = rangemax_ - rangemin_ - 1; index >= 0; --index) {
133 sum += static_cast<int64_t>(index) * buckets_[index];
135 return static_cast<double>(sum) / total_count_ + rangemin_;
144 if (buckets_ ==
nullptr || total_count_ <= 0) {
149 for (
int index = rangemax_ - rangemin_ - 1; index >= 0; --index) {
150 sum += static_cast<int64_t>(index) * buckets_[index];
151 sqsum += static_cast<double>(index) * index * buckets_[index];
153 double variance = static_cast<double>(sum) / total_count_;
154 variance = sqsum / total_count_ - variance * variance;
156 return sqrt(variance);
167 if (buckets_ ==
nullptr || total_count_ == 0) {
168 return static_cast<double>(rangemin_);
177 double target = frac * total_count_;
178 target =
ClipToRange(target, 1.0, static_cast<double>(total_count_));
182 for (index = 0; index < rangemax_ - rangemin_ && sum < target;
183 sum += buckets_[index++]);
186 return rangemin_ + index -
187 static_cast<double>(sum - target) / buckets_[index - 1];
189 return static_cast<double>(rangemin_);
199 if (buckets_ ==
nullptr || total_count_ == 0) {
203 for (min = 0; (min < rangemax_ - rangemin_) && (buckets_[min] == 0); min++);
204 return rangemin_ + min;
214 if (buckets_ ==
nullptr || total_count_ == 0) {
218 for (max = rangemax_ - rangemin_ - 1; max > 0 && buckets_[max] == 0; max--);
219 return rangemin_ + max;
232 if (buckets_ ==
nullptr) {
233 return static_cast<double>(rangemin_);
236 int median_pile = static_cast<int>(floor(
median));
237 if ((total_count_ > 1) && (
pile_count(median_pile) == 0)) {
241 for (min_pile = median_pile;
pile_count(min_pile) == 0; min_pile--);
243 for (max_pile = median_pile;
pile_count(max_pile) == 0; max_pile++);
244 median = (min_pile + max_pile) / 2.0;
255 if (buckets_ ==
nullptr) {
258 x =
ClipToRange(x, rangemin_, rangemax_ - 1) - rangemin_;
259 if (buckets_[x] == 0)
262 for (index = x - 1; index >= 0 && buckets_[index] == buckets_[x]; --index);
263 if (index >= 0 && buckets_[index] < buckets_[x])
265 for (index = x + 1; index < rangemax_ - rangemin_ &&
266 buckets_[index] == buckets_[x]; ++index);
267 if (index < rangemax_ - rangemin_ && buckets_[index] < buckets_[x])
282 if (buckets_ ==
nullptr || factor < 2) {
285 STATS result(rangemin_, rangemax_);
286 int entrycount = rangemax_ - rangemin_;
287 for (
int entry = 0; entry < entrycount; entry++) {
289 int count = buckets_[entry] * factor;
290 for (
int offset = 1; offset < factor; offset++) {
291 if (entry - offset >= 0)
292 count += buckets_[entry - offset] * (factor - offset);
293 if (entry + offset < entrycount)
294 count += buckets_[entry + offset] * (factor - offset);
296 result.add(entry + rangemin_,
count);
298 total_count_ = result.total_count_;
299 memcpy(buckets_, result.buckets_, entrycount *
sizeof(buckets_[0]));
315 int32_t max_clusters,
321 int32_t best_cluster;
322 int32_t new_centre = 0;
327 int32_t cluster_count;
329 if (buckets_ ==
nullptr || max_clusters < 1)
331 centres =
new float[max_clusters + 1];
332 for (cluster_count = 1; cluster_count <= max_clusters
333 && clusters[cluster_count].buckets_ !=
nullptr
334 && clusters[cluster_count].total_count_ > 0;
336 centres[cluster_count] =
337 static_cast<float>(clusters[cluster_count].
ile(0.5));
338 new_centre = clusters[cluster_count].
mode();
339 for (entry = new_centre - 1; centres[cluster_count] - entry < lower
340 && entry >= rangemin_
345 clusters[cluster_count].
add(entry,
count);
349 for (entry = new_centre + 1; entry - centres[cluster_count] < lower
355 clusters[cluster_count].
add(entry,
count);
362 if (cluster_count == 0) {
363 clusters[0].
set_range(rangemin_, rangemax_);
368 for (entry = 0; entry < rangemax_ - rangemin_; entry++) {
369 count = buckets_[entry] - clusters[0].buckets_[entry];
372 min_dist = static_cast<float>(INT32_MAX);
375 dist = entry + rangemin_ - centres[
cluster];
379 if (dist < min_dist) {
385 && (best_cluster == 0
386 || entry + rangemin_ > centres[best_cluster] * multiple
387 || entry + rangemin_ < centres[best_cluster] / multiple)) {
388 if (
count > new_mode) {
390 new_centre = entry + rangemin_;
396 if (new_mode > 0 && cluster_count < max_clusters) {
399 if (!clusters[cluster_count].
set_range(rangemin_, rangemax_)) {
403 centres[cluster_count] = static_cast<float>(new_centre);
404 clusters[cluster_count].
add(new_centre, new_mode);
405 clusters[0].
add(new_centre, new_mode);
406 for (entry = new_centre - 1; centres[cluster_count] - entry < lower
407 && entry >= rangemin_
411 clusters[cluster_count].
add(entry,
count);
415 for (entry = new_centre + 1; entry - centres[cluster_count] < lower
420 clusters[cluster_count].
add(entry,
count);
424 centres[cluster_count] =
425 static_cast<float>(clusters[cluster_count].
ile(0.5));
427 }
while (new_cluster && cluster_count < max_clusters);
429 return cluster_count;
438 static bool GatherPeak(
int index,
const int* src_buckets,
int* used_buckets,
439 int* prev_count,
int* total_count,
double* total_value) {
440 int pile_count = src_buckets[index] - used_buckets[index];
441 if (pile_count <= *prev_count && pile_count > 0) {
443 *total_count += pile_count;
444 *total_value += index * pile_count;
446 used_buckets[index] = src_buckets[index];
447 *prev_count = pile_count;
463 if (max_modes <= 0)
return 0;
464 int src_count = rangemax_ - rangemin_;
466 STATS used(rangemin_, rangemax_);
476 for (
int src_index = 0; src_index < src_count; src_index++) {
477 int pile_count = buckets_[src_index] - used.buckets_[src_index];
480 max_index = src_index;
485 used.buckets_[max_index] = max_count;
487 double total_value = max_index * max_count;
488 int total_count = max_count;
489 int prev_pile = max_count;
490 for (
int offset = 1; max_index + offset < src_count; ++offset) {
491 if (!GatherPeak(max_index + offset, buckets_, used.buckets_,
492 &prev_pile, &total_count, &total_value))
495 prev_pile = buckets_[max_index];
496 for (
int offset = 1; max_index - offset >= 0; ++offset) {
497 if (!GatherPeak(max_index - offset, buckets_, used.buckets_,
498 &prev_pile, &total_count, &total_value))
501 if (total_count > least_count || modes->size() < max_modes) {
503 if (modes->size() == max_modes)
504 modes->truncate(max_modes - 1);
505 int target_index = 0;
507 while (target_index < modes->size() &&
508 (*modes)[target_index].data >= total_count)
511 static_cast<float>(total_value / total_count + rangemin_);
514 least_count = modes->back().data;
517 }
while (max_count > 0);
518 return modes->size();
527 if (buckets_ ==
nullptr) {
534 for (
int index = min; index <= max; index++) {
535 if (buckets_[index] != 0) {
536 tprintf(
"%4d:%-3d ", rangemin_ + index, buckets_[index]);
537 if (++num_printed % 8 == 0)
553 if (buckets_ ==
nullptr) {
559 tprintf(
"Min=%.2f Really=%d\n",
ile(0.0), min);
563 tprintf(
"Max=%.2f Really=%d\n",
ile(1.0), max);
564 tprintf(
"Range=%d\n", max + 1 - min);
576 #ifndef GRAPHICS_DISABLED
583 if (buckets_ ==
nullptr) {
588 for (
int index = 0; index < rangemax_ - rangemin_; index++) {
589 window->
Rectangle(xorigin + xscale * index, yorigin,
590 xorigin + xscale * (index + 1),
591 yorigin + yscale * buckets_[index]);
603 #ifndef GRAPHICS_DISABLED
610 if (buckets_ ==
nullptr) {
614 window->
SetCursor(xorigin, yorigin + yscale * buckets_[0]);
615 for (
int index = 0; index < rangemax_ - rangemin_; index++) {
616 window->
DrawTo(xorigin + xscale * index,
617 yorigin + yscale * buckets_[index]);
633 int32_t prev_greater;
641 if (array[0] < array[1]) {
642 return index >= 1 ? 1 : 0;
645 return index >= 1 ? 0 : 1;
651 else if (index >=
count)
653 equal_count = static_cast<int32_t>(rand() %
count);
654 pivot = array[equal_count];
656 array[equal_count] = array[0];
658 prev_greater =
count;
660 for (next_sample = 1; next_sample < prev_greater;) {
661 sample = array[next_sample];
664 array[next_lesser++] =
sample;
667 else if (
sample > pivot) {
670 array[next_sample] = array[prev_greater];
671 array[prev_greater] =
sample;
678 for (next_sample = next_lesser; next_sample < prev_greater;)
679 array[next_sample++] = pivot;
680 if (index < next_lesser)
682 else if (index < prev_greater)
686 array + prev_greater,
687 count - prev_greater) + prev_greater;
698 int (*compar)(
const void*,
const void*)) {
702 int32_t prev_greater;
709 if (compar (array, static_cast<char *>(array) + size) < 0) {
710 return index >= 1 ? 1 : 0;
713 return index >= 1 ? 0 : 1;
718 else if (index >=
count)
720 pivot = static_cast<int32_t>(rand () %
count);
723 prev_greater =
count;
725 for (next_sample = 1; next_sample < prev_greater;) {
727 compar (static_cast<char *>(array) + size * next_sample,
728 static_cast<char *>(array) + size * next_lesser);
730 swap_entries (array, size, next_lesser++, next_sample++);
733 else if (result > 0) {
742 if (index < next_lesser)
744 else if (index < prev_greater)
748 static_cast<char *>(array) + size * prev_greater,
749 count - prev_greater, size,
750 compar) + prev_greater;
767 ptr1 = static_cast<char *>(array) + index1 * size;
768 ptr2 = static_cast<char *>(array) + index2 * size;