/*
 * tdigest.h - merging t-digest (Dunning & Ertl, arXiv:1902.04023, Algorithm 1)
 * with the four scale functions k0..k3 of Section 2.8 and the interpolation
 * rules of Section 2.9. Written for the experiments in this directory.
 */
#ifndef TDIGEST_H
#define TDIGEST_H

#include <stddef.h>

typedef struct {
    double mean;
    double weight;
} centroid_t;

enum { K0 = 0, K1 = 1, K2 = 2, K3 = 3 };

typedef struct {
    double delta;      /* compression parameter */
    int scale;         /* K0..K3 */
    int alternate;     /* alternate merge direction on successive merges */
    centroid_t *c;     /* merged centroids, ascending by mean */
    size_t nc, cap_c;
    centroid_t *buf;   /* unmerged points */
    size_t nb, cap_b;
    double total;      /* weight in c */
    double buf_weight; /* weight in buf */
    double min, max;
    long merges;
    centroid_t *tmp;   /* scratch for merging */
    size_t cap_tmp;
} tdigest_t;

/* buffer_factor: buffer capacity = buffer_factor * ceil(delta) points */
tdigest_t *td_new(double delta, int scale, int buffer_factor);
void td_free(tdigest_t *td);
void td_add(tdigest_t *td, double x, double w);
/* merge buffer into centroids using compression `delta` (use td->delta normally) */
void td_compress(tdigest_t *td, double delta);
/* add all centroids of `src` into `dst`'s buffer (src must be compressed) */
void td_merge_into(tdigest_t *dst, const tdigest_t *src);
double td_quantile(tdigest_t *td, double q);
double td_cdf(tdigest_t *td, double x);
double td_count(const tdigest_t *td);

/* scale function and its inverse; n is the total weight (used by k2, k3) */
double td_k(int scale, double q, double delta, double n);
double td_kinv(int scale, double k, double delta, double n);

#endif