316 {
317 bool new_cluster;
318 float *centres;
319 int32_t entry;
321 int32_t best_cluster;
322 int32_t new_centre = 0;
323 int32_t new_mode;
325 float dist;
326 float min_dist;
327 int32_t cluster_count;
328
329 if (buckets_ == nullptr || max_clusters < 1)
330 return 0;
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;
335 cluster_count++) {
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_
342 entry--) {
345 clusters[cluster_count].
add(entry,
count);
347 }
348 }
349 for (entry = new_centre + 1; entry - centres[cluster_count] < lower
350 && entry < rangemax_
352 entry++) {
355 clusters[cluster_count].
add(entry,
count);
357 }
358 }
359 }
360 cluster_count--;
361
362 if (cluster_count == 0) {
363 clusters[0].
set_range(rangemin_, rangemax_);
364 }
365 do {
366 new_cluster = false;
367 new_mode = 0;
368 for (entry = 0; entry < rangemax_ - rangemin_; entry++) {
369 count = buckets_[entry] - clusters[0].buckets_[entry];
370
372 min_dist = static_cast<float>(INT32_MAX);
373 best_cluster = 0;
375 dist = entry + rangemin_ - centres[
cluster];
376
377 if (dist < 0)
378 dist = -dist;
379 if (dist < min_dist) {
380 min_dist = dist;
382 }
383 }
384 if (min_dist > upper
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_;
391 }
392 }
393 }
394 }
395
396 if (new_mode > 0 && cluster_count < max_clusters) {
397 cluster_count++;
398 new_cluster = true;
399 if (!clusters[cluster_count].
set_range(rangemin_, rangemax_)) {
400 delete [] centres;
401 return 0;
402 }
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);
413 }
414 }
415 for (entry = new_centre + 1; entry - centres[cluster_count] < lower
416 && entry < rangemax_
420 clusters[cluster_count].
add(entry,
count);
422 }
423 }
424 centres[cluster_count] =
425 static_cast<float>(clusters[cluster_count].
ile(0.5));
426 }
427 } while (new_cluster && cluster_count < max_clusters);
428 delete [] centres;
429 return cluster_count;
430}
int32_t cluster(float lower, float upper, float multiple, int32_t max_clusters, STATS *clusters)
int32_t pile_count(int32_t value) const
void add(int32_t value, int32_t count)
bool set_range(int32_t min_bucket_value, int32_t max_bucket_value_plus_1)
double ile(double frac) const