<commit_before>package tdigest

import (
	"fmt"
	"math"
	"math/rand"

	"github.com/petar/GoLLRB/llrb"
)

type Centroid struct {
	mean  float64
	count uint32
}

func (c Centroid) String() string {
	return fmt.Sprintf("C<m=%.6f,c=%d>", c.mean, c.count)
}

func (c Centroid) Equals(other Centroid) bool {
	return c.mean == other.mean && c.count == other.count
}

func (c *Centroid) Update(x float64, weight uint32) {
	c.count += weight
	c.mean += float64(weight) * (x - c.mean) / float64(c.count)
}

var InvalidCentroid Centroid = Centroid{mean: 0.0, count: 0}

func compareCentroids(p, q interface{}) int {
	a := p.(Centroid).mean
	b := q.(Centroid).mean

	if a < b {
		return -1
	} else if a > b {
		return 1
	} else {
		return 0
	}
}

func centroidLess(p, q interface{}) bool {
	res := p.(Centroid).mean < q.(Centroid).mean
	return res
}

func centroidLessOrEquals(p, q interface{}) bool {
	a := p.(Centroid).mean
	b := q.(Centroid).mean
	return a <= b
}

type TDigest struct {
	summary     *Summary
	compression float64
	count       uint32
}

func New(compression float64) *TDigest {
	tdigest := TDigest{compression: compression, summary: newSummary(), count: 0}
	return &tdigest
}

func (t *TDigest) Percentile(p float64) float64 {
	if p < 0 || p > 1 {
		panic("Percentiles must be between 0 and 1 (inclusive)")
	}

	if t.summary.Len() == 0 {
		return math.NaN()
	} else if t.summary.Len() == 1 {
		return t.summary.Min().mean
	}

	p *= float64(t.count)
	var total float64 = 0
	i := 0

	for item := range t.summary.IterInOrder() {
		k := float64(item.(Centroid).count)

		if p < total+k {
			if i == 0 || i+1 == t.summary.Len() {
				return item.(Centroid).mean
			}
			succ, pred := t.successorAndPredecessorItems(item.(Centroid))
			delta := (succ.mean - pred.mean) / 2
			return item.(Centroid).mean + ((p-total)/k-0.5)*delta
		}

		i++
		total += k
	}

	return t.summary.Max().mean
}

func (t *TDigest) Update(value float64, weight uint32) {
	t.count += weight

	newCentroid := Centroid{value, weight}

	if t.summary.Len() == 0 {
		t.addCentroid(newCentroid)<commit_msg>Use Summary.IterInOrderWith to compute the Percentiles<commit_after>package tdigest

import (
	"fmt"
	"math"
	"math/rand"

	"github.com/petar/GoLLRB/llrb"
)

type Centroid struct {
	mean  float64
	count uint32
}

func (c Centroid) String() string {
	return fmt.Sprintf("C<m=%.6f,c=%d>", c.mean, c.count)
}

func (c Centroid) Equals(other Centroid) bool {
	return c.mean == other.mean && c.count == other.count
}

func (c *Centroid) Update(x float64, weight uint32) {
	c.count += weight
	c.mean += float64(weight) * (x - c.mean) / float64(c.count)
}

var InvalidCentroid Centroid = Centroid{mean: 0.0, count: 0}

func compareCentroids(p, q interface{}) int {
	a := p.(Centroid).mean
	b := q.(Centroid).mean

	if a < b {
		return -1
	} else if a > b {
		return 1
	} else {
		return 0
	}
}

func centroidLess(p, q interface{}) bool {
	res := p.(Centroid).mean < q.(Centroid).mean
	return res
}

func centroidLessOrEquals(p, q interface{}) bool {
	a := p.(Centroid).mean
	b := q.(Centroid).mean
	return a <= b
}

type TDigest struct {
	summary     *Summary
	compression float64
	count       uint32
}

func New(compression float64) *TDigest {
	tdigest := TDigest{compression: compression, summary: newSummary(), count: 0}
	return &tdigest
}

func (t *TDigest) Percentile(p float64) float64 {
	if p < 0 || p > 1 {
		panic("Percentiles must be between 0 and 1 (inclusive)")
	}

	if t.summary.Len() == 0 {
		return math.NaN()
	} else if t.summary.Len() == 1 {
		return t.summary.Min().mean
	}

	p *= float64(t.count)
	var total float64 = 0
	i := 0

	found := false
	var result float64

	t.summary.IterInOrderWith(func(item llrb.Item) bool {
		k := float64(item.(Centroid).count)

		if p < total+k {
			if i == 0 || i+1 == t.summary.Len() {
				result = item.(Centroid).mean
				found = true
				return false
			}
			succ, pred := t.successorAndPredecessorItems(item.(Centroid))
			delta := (succ.mean - pred.mean) / 2
			result = item.(Centroid).mean + ((p-total)/k-0.5)*delta
			found = true
			return false
		}

		i++
		total += k
		return true
	})

	if found {
		return result
	} else {
		return t.summary.Max().mean
	}
}

func (t *TDigest) Update(value float64, weight uint32) {
	t.count += weight

	newCentroid := Centroid{value, weight}

	if t.summary.Len() == 0 {
		t.addCentroid(newCentroid)
{'fraction_non_alphanumeric': 0.15433936340737348, 'fraction_numerical': 0.02518891687657431, 'mean_word_length': 3.316205533596838, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6830355', 'n_tokens_mistral': 1822, 'n_tokens_neox': 1662, 'n_words': 437}