1// Copyright 2017 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package trace
6
7import (
8	"math"
9	"math/rand"
10	"testing"
11)
12
13func TestMUD(t *testing.T) {
14	// Insert random uniforms and check histogram mass and
15	// cumulative sum approximations.
16	rnd := rand.New(rand.NewSource(42))
17	mass := 0.0
18	var mud mud
19	for i := 0; i < 100; i++ {
20		area, l, r := rnd.Float64(), rnd.Float64(), rnd.Float64()
21		if rnd.Intn(10) == 0 {
22			r = l
23		}
24		t.Log(l, r, area)
25		mud.add(l, r, area)
26		mass += area
27
28		// Check total histogram weight.
29		hmass := 0.0
30		for _, val := range mud.hist {
31			hmass += val
32		}
33		if !aeq(mass, hmass) {
34			t.Fatalf("want mass %g, got %g", mass, hmass)
35		}
36
37		// Check inverse cumulative sum approximations.
38		for j := 0.0; j < mass; j += mass * 0.099 {
39			mud.setTrackMass(j)
40			l, u, ok := mud.approxInvCumulativeSum()
41			inv, ok2 := mud.invCumulativeSum(j)
42			if !ok || !ok2 {
43				t.Fatalf("inverse cumulative sum failed: approx %v, exact %v", ok, ok2)
44			}
45			if !(l <= inv && inv < u) {
46				t.Fatalf("inverse(%g) = %g, not ∈ [%g, %g)", j, inv, l, u)
47			}
48		}
49	}
50}
51
52func TestMUDTracking(t *testing.T) {
53	// Test that the tracked mass is tracked correctly across
54	// updates.
55	rnd := rand.New(rand.NewSource(42))
56	const uniforms = 100
57	for trackMass := 0.0; trackMass < uniforms; trackMass += uniforms / 50 {
58		var mud mud
59		mass := 0.0
60		mud.setTrackMass(trackMass)
61		for i := 0; i < uniforms; i++ {
62			area, l, r := rnd.Float64(), rnd.Float64(), rnd.Float64()
63			mud.add(l, r, area)
64			mass += area
65			l, u, ok := mud.approxInvCumulativeSum()
66			inv, ok2 := mud.invCumulativeSum(trackMass)
67
68			if mass < trackMass {
69				if ok {
70					t.Errorf("approx(%g) = [%g, %g), but mass = %g", trackMass, l, u, mass)
71				}
72				if ok2 {
73					t.Errorf("exact(%g) = %g, but mass = %g", trackMass, inv, mass)
74				}
75			} else {
76				if !ok {
77					t.Errorf("approx(%g) failed, but mass = %g", trackMass, mass)
78				}
79				if !ok2 {
80					t.Errorf("exact(%g) failed, but mass = %g", trackMass, mass)
81				}
82				if ok && ok2 && !(l <= inv && inv < u) {
83					t.Errorf("inverse(%g) = %g, not ∈ [%g, %g)", trackMass, inv, l, u)
84				}
85			}
86		}
87	}
88}
89
90// aeq returns true if x and y are equal up to 8 digits (1 part in 100
91// million).
92// TODO(amedee) dup of gc_test.go
93func aeq(x, y float64) bool {
94	if x < 0 && y < 0 {
95		x, y = -x, -y
96	}
97	const digits = 8
98	factor := 1 - math.Pow(10, -digits+1)
99	return x*factor <= y && y*factor <= x
100}
101