hist.go

// Copyright 2015 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package stats

import "math"

// TODO: Implement histograms on top of scales.

type Histogram interface {
	// Add adds a sample with value x to histogram h.
	Add(x float64)

	// Counts returns the number of samples less than the lowest
	// bin, a slice of the number of samples in each bin,
	// and the number of samples greater than the highest bin.
	Counts() (under uint, counts []uint, over uint)

	// BinToValue returns the value that would appear at the given
	// bin index.
	//
	// For integral values of bin, BinToValue returns the lower
	// bound of bin.  That is, a sample value x will be in bin if
	// bin is integral and
	//
	//    BinToValue(bin) <= x < BinToValue(bin + 1)
	//
	// For non-integral values of bin, BinToValue interpolates
	// between the lower and upper bounds of math.Floor(bin).
	//
	// BinToValue is undefined if bin > 1 + the number of bins.
	BinToValue(bin float64) float64
}

// HistogramPercentile returns the x such that n*percentile samples in
// hist are <= x, assuming values are distibuted within each bin
// according to hist's distibution.
//
// If the percentile'th sample falls below the lowest bin or above the
// highest bin, returns NaN.
func HistogramPercentile(hist Histogram, percentile float64) float64 {
	under, counts, over := hist.Counts()
	total := under + over
	for _, count := range counts {
		total += count
	}

	goal := uint(float64(total) * percentile)
	if goal <= under || goal > total-over {
		return math.NaN()
	}
	for bin, count := range counts {
		if count > goal {
			return hist.BinToValue(float64(bin) + float64(goal)/float64(count))
		}
		goal -= count
	}
	panic("goal count not reached")
}

// HistogramIQR returns the interquartile range of the samples in
// hist.
func HistogramIQR(hist Histogram) float64 {
	return HistogramPercentile(hist, 0.75) - HistogramPercentile(hist, 0.25)
}