// Package obs implements the data-plane observability primitives: a
// bucketed latency Histogram whose percentiles aggregate correctly across
// instances (you cannot average p99s — you merge buckets), RED metrics,
// and W3C trace-context propagation. Stdlib-only.
package obs

import "sort"

// Histogram is a cumulative-bucket latency histogram (Prometheus-style).
// Percentiles are computed FROM the buckets, and two histograms with the
// same bounds can be Merged bucket-wise — which is how you get a correct
// fleet-wide percentile (averaging per-instance percentiles is wrong).
type Histogram struct {
	bounds []float64 // upper bounds, ascending (seconds)
	counts []int64   // len(bounds)+1; last is the +Inf overflow bucket
	sum    float64
	total  int64
}

// DefaultBounds are latency buckets sized around a typical SLO.
var DefaultBounds = []float64{.001, .005, .01, .025, .05, .1, .25, .5, 1, 2.5}

func NewHistogram(bounds []float64) *Histogram {
	b := append([]float64(nil), bounds...)
	sort.Float64s(b)
	return &Histogram{bounds: b, counts: make([]int64, len(b)+1)}
}

// Observe records a value (seconds).
func (h *Histogram) Observe(v float64) {
	i := sort.SearchFloat64s(h.bounds, v)
	// SearchFloat64s returns the index of the first bound >= v; if v is
	// larger than all bounds it returns len(bounds) (the +Inf bucket).
	if i < len(h.bounds) && v > h.bounds[i] {
		i++ // shouldn't happen given Search semantics, defensive
	}
	h.counts[i]++
	h.sum += v
	h.total++
}

// Total returns the number of observations.
func (h *Histogram) Total() int64 { return h.total }

// Quantile returns the upper bound of the bucket in which the q-th
// percentile falls (conservative bucket estimate). For the +Inf bucket it
// returns the largest finite bound.
func (h *Histogram) Quantile(q float64) float64 {
	if h.total == 0 {
		return 0
	}
	target := q * float64(h.total)
	var cum int64
	for i, c := range h.counts {
		cum += c
		if float64(cum) >= target {
			if i < len(h.bounds) {
				return h.bounds[i]
			}
			return h.bounds[len(h.bounds)-1] // +Inf bucket -> last finite bound
		}
	}
	return h.bounds[len(h.bounds)-1]
}

// Merge adds another histogram (same bounds) into this one — the correct
// way to combine per-instance histograms before computing a fleet
// percentile.
func (h *Histogram) Merge(o *Histogram) {
	for i := range h.counts {
		h.counts[i] += o.counts[i]
	}
	h.sum += o.sum
	h.total += o.total
}

// Clone returns a deep copy.
func (h *Histogram) Clone() *Histogram {
	c := NewHistogram(h.bounds)
	copy(c.counts, h.counts)
	c.sum = h.sum
	c.total = h.total
	return c
}