func (d *tDigest) mergeCentroid(
	currIndex float64,
	currWeight float64,
	totalWeight float64,
	c Centroid,
	mergeResult []Centroid,
) (float64, []Centroid) {
	nextIndex := d.nextIndex((currWeight + c.Weight) / totalWeight)
	if nextIndex-currIndex > 1 || len(mergeResult) == 0 {
		mergeResult = d.appendCentroid(mergeResult, c)
		return d.nextIndex(currWeight / totalWeight), mergeResult
	}
	numResults := len(mergeResult)
	mergeResult[numResults-1].Weight += c.Weight
	mergeResult[numResults-1].Mean += (c.Mean - mergeResult[numResults-1].Mean) * c.Weight / mergeResult[numResults-1].Weight
	return currIndex, mergeResult
}
mergeCentroid merges a centroid into the list of merged centroids.
package tdigest
import (
	"math"
	"sort"
)
var (
	nan              = math.NaN()
	positiveInfinity = math.Inf(1)
	negativeInfinity = math.Inf(-1)
	sentinelCentroid = Centroid{Mean: positiveInfinity, Weight: 0.0}
)
type centroidsByMeanAsc []Centroid
func (c centroidsByMeanAsc) Len() int           { return len(c) }
func (c centroidsByMeanAsc) Less(i, j int) bool { return c[i].Mean < c[j].Mean }
func (c centroidsByMeanAsc) Swap(i, j int)      { c[i], c[j] = c[j], c[i] }
type mergeCentroidFn func(
	currIndex float64,
	currWeight float64,
	totalWeight float64,
	c Centroid,
	mergeResult []Centroid,
) (float64, []Centroid)
type tDigest struct {
	compression      float64          
	mergedCapacity   int              
	unmergedCapacity int              
	multiplier       int64            
	mergeCentroidFn  mergeCentroidFn  
	centroidsPool    CentroidsPool    
	closed         bool        
	merged         []Centroid  
	mergedWeight   float64     
	unmerged       []Centroid  
	unmergedWeight float64     
	minValue       float64     
	maxValue       float64     
}
func mergedCapacity(compression float64) int {
	return int(math.Ceil(math.Pi*compression + 0.5))
}
func unmergedCapacity(compression float64) int {
	compression = math.Min(math.Max(20, compression), 1000)
	return int(7.5 + 0.37*compression - 2e-4*compression*compression)
}
func NewTDigest(opts Options) TDigest {
	centroidsPool := opts.CentroidsPool()
	compression := opts.Compression()
	mergedCapacity := mergedCapacity(compression)
	unmergedCapacity := unmergedCapacity(compression)
	var multiplier int64
	if precision := opts.Precision(); precision != 0 {
		multiplier = int64(math.Pow10(precision))
	}
	d := &tDigest{
		compression:      opts.Compression(),
		multiplier:       multiplier,
		centroidsPool:    centroidsPool,
		mergedCapacity:   mergedCapacity,
		unmergedCapacity: unmergedCapacity,
	}
	d.mergeCentroidFn = d.mergeCentroid
	d.Reset()
	return d
}
func (d *tDigest) Merged() []Centroid {
	return d.merged
}
func (d *tDigest) Unmerged() []Centroid {
	return d.unmerged
}
func (d *tDigest) Add(value float64) {
	d.add(value, 1.0)
}
func (d *tDigest) Min() float64 {
	return d.Quantile(0.0)
}
func (d *tDigest) Max() float64 {
	return d.Quantile(1.0)
}
func (d *tDigest) Quantile(q float64) float64 {
	if q < 0.0 || q > 1.0 {
		return nan
	}
	d.compress()
	if len(d.merged) == 0 {
		return 0.0
	}
	if q == 0.0 {
		return d.minValue
	}
	if q == 1.0 {
		return d.maxValue
	}
	var (
		targetWeight = q * d.mergedWeight
		currWeight   = 0.0
		lowerBound   = d.minValue
		upperBound   float64
	)
	for i, c := range d.merged {
		upperBound = d.upperBound(i)
		if targetWeight <= currWeight+c.Weight {
			ratio := (targetWeight - currWeight) / c.Weight
			quantile := lowerBound + ratio*(upperBound-lowerBound)
			if d.multiplier != 0 {
				quantile = math.Trunc(quantile*float64(d.multiplier)) / float64(d.multiplier)
			}
			return quantile
		}
		currWeight += c.Weight
		lowerBound = upperBound
	}
	return nan
}
func (d *tDigest) Merge(tdigest TDigest) {
	merged := tdigest.Merged()
	for _, c := range merged {
		d.add(c.Mean, c.Weight)
	}
	unmerged := tdigest.Unmerged()
	for _, c := range unmerged {
		d.add(c.Mean, c.Weight)
	}
}
func (d *tDigest) Close() {
	if d.closed {
		return
	}
	d.closed = true
	d.centroidsPool.Put(d.merged)
	d.centroidsPool.Put(d.unmerged)
}
func (d *tDigest) Reset() {
	d.closed = false
	d.merged = d.centroidsPool.Get(d.mergedCapacity)
	d.mergedWeight = 0.0
	d.unmerged = d.centroidsPool.Get(d.unmergedCapacity)
	d.unmergedWeight = 0.0
	d.minValue = positiveInfinity
	d.maxValue = negativeInfinity
}
func (d *tDigest) compress() {
	if len(d.unmerged) == 0 {
		return
	}
	sort.Sort(centroidsByMeanAsc(d.unmerged))
	var (
		totalWeight   = d.mergedWeight + d.unmergedWeight
		currWeight    = 0.0
		currIndex     = 0.0
		mergedIndex   = 0
		unmergedIndex = 0
		mergeResult   = d.centroidsPool.Get(len(d.merged) + len(d.unmerged))
	)
	for mergedIndex < len(d.merged) || unmergedIndex < len(d.unmerged) {
		currUnmerged := sentinelCentroid
		if unmergedIndex < len(d.unmerged) {
			currUnmerged = d.unmerged[unmergedIndex]
		}
		currMerged := sentinelCentroid
		if mergedIndex < len(d.merged) {
			currMerged = d.merged[mergedIndex]
		}
		if currUnmerged.Mean < currMerged.Mean {
			currIndex, mergeResult = d.mergeCentroidFn(currIndex, currWeight, totalWeight, currUnmerged, mergeResult)
			currWeight += currUnmerged.Weight
			unmergedIndex++
		} else {
			currIndex, mergeResult = d.mergeCentroidFn(currIndex, currWeight, totalWeight, currMerged, mergeResult)
			currWeight += currMerged.Weight
			mergedIndex++
		}
	}
	d.centroidsPool.Put(d.merged)
	d.merged = mergeResult
	d.mergedWeight = totalWeight
	d.unmerged = d.unmerged[:0]
	d.unmergedWeight = 0.0
}