1package quantile
2
3import (
4	"math"
5	"math/rand"
6	"sort"
7	"testing"
8)
9
10var (
11	Targets = map[float64]float64{
12		0.01: 0.001,
13		0.10: 0.01,
14		0.50: 0.05,
15		0.90: 0.01,
16		0.99: 0.001,
17	}
18	TargetsSmallEpsilon = map[float64]float64{
19		0.01: 0.0001,
20		0.10: 0.001,
21		0.50: 0.005,
22		0.90: 0.001,
23		0.99: 0.0001,
24	}
25	LowQuantiles  = []float64{0.01, 0.1, 0.5}
26	HighQuantiles = []float64{0.99, 0.9, 0.5}
27)
28
29const RelativeEpsilon = 0.01
30
31func verifyPercsWithAbsoluteEpsilon(t *testing.T, a []float64, s *Stream) {
32	sort.Float64s(a)
33	for quantile, epsilon := range Targets {
34		n := float64(len(a))
35		k := int(quantile * n)
36		if k < 1 {
37			k = 1
38		}
39		lower := int((quantile - epsilon) * n)
40		if lower < 1 {
41			lower = 1
42		}
43		upper := int(math.Ceil((quantile + epsilon) * n))
44		if upper > len(a) {
45			upper = len(a)
46		}
47		w, min, max := a[k-1], a[lower-1], a[upper-1]
48		if g := s.Query(quantile); g < min || g > max {
49			t.Errorf("q=%f: want %v [%f,%f], got %v", quantile, w, min, max, g)
50		}
51	}
52}
53
54func verifyLowPercsWithRelativeEpsilon(t *testing.T, a []float64, s *Stream) {
55	sort.Float64s(a)
56	for _, qu := range LowQuantiles {
57		n := float64(len(a))
58		k := int(qu * n)
59
60		lowerRank := int((1 - RelativeEpsilon) * qu * n)
61		upperRank := int(math.Ceil((1 + RelativeEpsilon) * qu * n))
62		w, min, max := a[k-1], a[lowerRank-1], a[upperRank-1]
63		if g := s.Query(qu); g < min || g > max {
64			t.Errorf("q=%f: want %v [%f,%f], got %v", qu, w, min, max, g)
65		}
66	}
67}
68
69func verifyHighPercsWithRelativeEpsilon(t *testing.T, a []float64, s *Stream) {
70	sort.Float64s(a)
71	for _, qu := range HighQuantiles {
72		n := float64(len(a))
73		k := int(qu * n)
74
75		lowerRank := int((1 - (1+RelativeEpsilon)*(1-qu)) * n)
76		upperRank := int(math.Ceil((1 - (1-RelativeEpsilon)*(1-qu)) * n))
77		w, min, max := a[k-1], a[lowerRank-1], a[upperRank-1]
78		if g := s.Query(qu); g < min || g > max {
79			t.Errorf("q=%f: want %v [%f,%f], got %v", qu, w, min, max, g)
80		}
81	}
82}
83
84func populateStream(s *Stream) []float64 {
85	a := make([]float64, 0, 1e5+100)
86	for i := 0; i < cap(a); i++ {
87		v := rand.NormFloat64()
88		// Add 5% asymmetric outliers.
89		if i%20 == 0 {
90			v = v*v + 1
91		}
92		s.Insert(v)
93		a = append(a, v)
94	}
95	return a
96}
97
98func TestTargetedQuery(t *testing.T) {
99	rand.Seed(42)
100	s := NewTargeted(Targets)
101	a := populateStream(s)
102	verifyPercsWithAbsoluteEpsilon(t, a, s)
103}
104
105func TestTargetedQuerySmallSampleSize(t *testing.T) {
106	rand.Seed(42)
107	s := NewTargeted(TargetsSmallEpsilon)
108	a := []float64{1, 2, 3, 4, 5}
109	for _, v := range a {
110		s.Insert(v)
111	}
112	verifyPercsWithAbsoluteEpsilon(t, a, s)
113	// If not yet flushed, results should be precise:
114	if !s.flushed() {
115		for φ, want := range map[float64]float64{
116			0.01: 1,
117			0.10: 1,
118			0.50: 3,
119			0.90: 5,
120			0.99: 5,
121		} {
122			if got := s.Query(φ); got != want {
123				t.Errorf("want %f for φ=%f, got %f", want, φ, got)
124			}
125		}
126	}
127}
128
129func TestLowBiasedQuery(t *testing.T) {
130	rand.Seed(42)
131	s := NewLowBiased(RelativeEpsilon)
132	a := populateStream(s)
133	verifyLowPercsWithRelativeEpsilon(t, a, s)
134}
135
136func TestHighBiasedQuery(t *testing.T) {
137	rand.Seed(42)
138	s := NewHighBiased(RelativeEpsilon)
139	a := populateStream(s)
140	verifyHighPercsWithRelativeEpsilon(t, a, s)
141}
142
143// BrokenTestTargetedMerge is broken, see Merge doc comment.
144func BrokenTestTargetedMerge(t *testing.T) {
145	rand.Seed(42)
146	s1 := NewTargeted(Targets)
147	s2 := NewTargeted(Targets)
148	a := populateStream(s1)
149	a = append(a, populateStream(s2)...)
150	s1.Merge(s2.Samples())
151	verifyPercsWithAbsoluteEpsilon(t, a, s1)
152}
153
154// BrokenTestLowBiasedMerge is broken, see Merge doc comment.
155func BrokenTestLowBiasedMerge(t *testing.T) {
156	rand.Seed(42)
157	s1 := NewLowBiased(RelativeEpsilon)
158	s2 := NewLowBiased(RelativeEpsilon)
159	a := populateStream(s1)
160	a = append(a, populateStream(s2)...)
161	s1.Merge(s2.Samples())
162	verifyLowPercsWithRelativeEpsilon(t, a, s2)
163}
164
165// BrokenTestHighBiasedMerge is broken, see Merge doc comment.
166func BrokenTestHighBiasedMerge(t *testing.T) {
167	rand.Seed(42)
168	s1 := NewHighBiased(RelativeEpsilon)
169	s2 := NewHighBiased(RelativeEpsilon)
170	a := populateStream(s1)
171	a = append(a, populateStream(s2)...)
172	s1.Merge(s2.Samples())
173	verifyHighPercsWithRelativeEpsilon(t, a, s2)
174}
175
176func TestUncompressed(t *testing.T) {
177	q := NewTargeted(Targets)
178	for i := 100; i > 0; i-- {
179		q.Insert(float64(i))
180	}
181	if g := q.Count(); g != 100 {
182		t.Errorf("want count 100, got %d", g)
183	}
184	// Before compression, Query should have 100% accuracy.
185	for quantile := range Targets {
186		w := quantile * 100
187		if g := q.Query(quantile); g != w {
188			t.Errorf("want %f, got %f", w, g)
189		}
190	}
191}
192
193func TestUncompressedSamples(t *testing.T) {
194	q := NewTargeted(map[float64]float64{0.99: 0.001})
195	for i := 1; i <= 100; i++ {
196		q.Insert(float64(i))
197	}
198	if g := q.Samples().Len(); g != 100 {
199		t.Errorf("want count 100, got %d", g)
200	}
201}
202
203func TestUncompressedOne(t *testing.T) {
204	q := NewTargeted(map[float64]float64{0.99: 0.01})
205	q.Insert(3.14)
206	if g := q.Query(0.90); g != 3.14 {
207		t.Error("want PI, got", g)
208	}
209}
210
211func TestDefaults(t *testing.T) {
212	if g := NewTargeted(map[float64]float64{0.99: 0.001}).Query(0.99); g != 0 {
213		t.Errorf("want 0, got %f", g)
214	}
215}
216