1 files changed, 215 insertions, 0 deletions
diff --git a/vendor/github.com/beorn7/perks/quantile/stream_test.go b/vendor/github.com/beorn7/perks/quantile/stream_test.go
new file mode 100644
index 000000000..855195097
--- /dev/null
+++ b/vendor/github.com/beorn7/perks/quantile/stream_test.go
@@ -0,0 +1,215 @@
+package quantile
+
+import (
+	"math"
+	"math/rand"
+	"sort"
+	"testing"
+)
+
+var (
+	Targets = map[float64]float64{
+		0.01: 0.001,
+		0.10: 0.01,
+		0.50: 0.05,
+		0.90: 0.01,
+		0.99: 0.001,
+	}
+	TargetsSmallEpsilon = map[float64]float64{
+		0.01: 0.0001,
+		0.10: 0.001,
+		0.50: 0.005,
+		0.90: 0.001,
+		0.99: 0.0001,
+	}
+	LowQuantiles  = []float64{0.01, 0.1, 0.5}
+	HighQuantiles = []float64{0.99, 0.9, 0.5}
+)
+
+const RelativeEpsilon = 0.01
+
+func verifyPercsWithAbsoluteEpsilon(t *testing.T, a []float64, s *Stream) {
+	sort.Float64s(a)
+	for quantile, epsilon := range Targets {
+		n := float64(len(a))
+		k := int(quantile * n)
+		if k < 1 {
+			k = 1
+		}
+		lower := int((quantile - epsilon) * n)
+		if lower < 1 {
+			lower = 1
+		}
+		upper := int(math.Ceil((quantile + epsilon) * n))
+		if upper > len(a) {
+			upper = len(a)
+		}
+		w, min, max := a[k-1], a[lower-1], a[upper-1]
+		if g := s.Query(quantile); g < min || g > max {
+			t.Errorf("q=%f: want %v [%f,%f], got %v", quantile, w, min, max, g)
+		}
+	}
+}
+
+func verifyLowPercsWithRelativeEpsilon(t *testing.T, a []float64, s *Stream) {
+	sort.Float64s(a)
+	for _, qu := range LowQuantiles {
+		n := float64(len(a))
+		k := int(qu * n)
+
+		lowerRank := int((1 - RelativeEpsilon) * qu * n)
+		upperRank := int(math.Ceil((1 + RelativeEpsilon) * qu * n))
+		w, min, max := a[k-1], a[lowerRank-1], a[upperRank-1]
+		if g := s.Query(qu); g < min || g > max {
+			t.Errorf("q=%f: want %v [%f,%f], got %v", qu, w, min, max, g)
+		}
+	}
+}
+
+func verifyHighPercsWithRelativeEpsilon(t *testing.T, a []float64, s *Stream) {
+	sort.Float64s(a)
+	for _, qu := range HighQuantiles {
+		n := float64(len(a))
+		k := int(qu * n)
+
+		lowerRank := int((1 - (1+RelativeEpsilon)*(1-qu)) * n)
+		upperRank := int(math.Ceil((1 - (1-RelativeEpsilon)*(1-qu)) * n))
+		w, min, max := a[k-1], a[lowerRank-1], a[upperRank-1]
+		if g := s.Query(qu); g < min || g > max {
+			t.Errorf("q=%f: want %v [%f,%f], got %v", qu, w, min, max, g)
+		}
+	}
+}
+
+func populateStream(s *Stream) []float64 {
+	a := make([]float64, 0, 1e5+100)
+	for i := 0; i < cap(a); i++ {
+		v := rand.NormFloat64()
+		// Add 5% asymmetric outliers.
+		if i%20 == 0 {
+			v = v*v + 1
+		}
+		s.Insert(v)
+		a = append(a, v)
+	}
+	return a
+}
+
+func TestTargetedQuery(t *testing.T) {
+	rand.Seed(42)
+	s := NewTargeted(Targets)
+	a := populateStream(s)
+	verifyPercsWithAbsoluteEpsilon(t, a, s)
+}
+
+func TestTargetedQuerySmallSampleSize(t *testing.T) {
+	rand.Seed(42)
+	s := NewTargeted(TargetsSmallEpsilon)
+	a := []float64{1, 2, 3, 4, 5}
+	for _, v := range a {
+		s.Insert(v)
+	}
+	verifyPercsWithAbsoluteEpsilon(t, a, s)
+	// If not yet flushed, results should be precise:
+	if !s.flushed() {
+		for φ, want := range map[float64]float64{
+			0.01: 1,
+			0.10: 1,
+			0.50: 3,
+			0.90: 5,
+			0.99: 5,
+		} {
+			if got := s.Query(φ); got != want {
+				t.Errorf("want %f for φ=%f, got %f", want, φ, got)
+			}
+		}
+	}
+}
+
+func TestLowBiasedQuery(t *testing.T) {
+	rand.Seed(42)
+	s := NewLowBiased(RelativeEpsilon)
+	a := populateStream(s)
+	verifyLowPercsWithRelativeEpsilon(t, a, s)
+}
+
+func TestHighBiasedQuery(t *testing.T) {
+	rand.Seed(42)
+	s := NewHighBiased(RelativeEpsilon)
+	a := populateStream(s)
+	verifyHighPercsWithRelativeEpsilon(t, a, s)
+}
+
+// BrokenTestTargetedMerge is broken, see Merge doc comment.
+func BrokenTestTargetedMerge(t *testing.T) {
+	rand.Seed(42)
+	s1 := NewTargeted(Targets)
+	s2 := NewTargeted(Targets)
+	a := populateStream(s1)
+	a = append(a, populateStream(s2)...)
+	s1.Merge(s2.Samples())
+	verifyPercsWithAbsoluteEpsilon(t, a, s1)
+}
+
+// BrokenTestLowBiasedMerge is broken, see Merge doc comment.
+func BrokenTestLowBiasedMerge(t *testing.T) {
+	rand.Seed(42)
+	s1 := NewLowBiased(RelativeEpsilon)
+	s2 := NewLowBiased(RelativeEpsilon)
+	a := populateStream(s1)
+	a = append(a, populateStream(s2)...)
+	s1.Merge(s2.Samples())
+	verifyLowPercsWithRelativeEpsilon(t, a, s2)
+}
+
+// BrokenTestHighBiasedMerge is broken, see Merge doc comment.
+func BrokenTestHighBiasedMerge(t *testing.T) {
+	rand.Seed(42)
+	s1 := NewHighBiased(RelativeEpsilon)
+	s2 := NewHighBiased(RelativeEpsilon)
+	a := populateStream(s1)
+	a = append(a, populateStream(s2)...)
+	s1.Merge(s2.Samples())
+	verifyHighPercsWithRelativeEpsilon(t, a, s2)
+}
+
+func TestUncompressed(t *testing.T) {
+	q := NewTargeted(Targets)
+	for i := 100; i > 0; i-- {
+		q.Insert(float64(i))
+	}
+	if g := q.Count(); g != 100 {
+		t.Errorf("want count 100, got %d", g)
+	}
+	// Before compression, Query should have 100% accuracy.
+	for quantile := range Targets {
+		w := quantile * 100
+		if g := q.Query(quantile); g != w {
+			t.Errorf("want %f, got %f", w, g)
+		}
+	}
+}
+
+func TestUncompressedSamples(t *testing.T) {
+	q := NewTargeted(map[float64]float64{0.99: 0.001})
+	for i := 1; i <= 100; i++ {
+		q.Insert(float64(i))
+	}
+	if g := q.Samples().Len(); g != 100 {
+		t.Errorf("want count 100, got %d", g)
+	}
+}
+
+func TestUncompressedOne(t *testing.T) {
+	q := NewTargeted(map[float64]float64{0.99: 0.01})
+	q.Insert(3.14)
+	if g := q.Query(0.90); g != 3.14 {
+		t.Error("want PI, got", g)
+	}
+}
+
+func TestDefaults(t *testing.T) {
+	if g := NewTargeted(map[float64]float64{0.99: 0.001}).Query(0.99); g != 0 {
+		t.Errorf("want 0, got %f", g)
+	}
+}