// Copyright 2017 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 trace

import (
	"math"
	"math/rand"
	"testing"
)

func TestMUD(t *testing.T) {
	// Insert random uniforms and check histogram mass and
	// cumulative sum approximations.
	rnd := rand.New(rand.NewSource(42))
	mass := 0.0
	var mud mud
	for i := 0; i < 100; i++ {
		area, l, r := rnd.Float64(), rnd.Float64(), rnd.Float64()
		if rnd.Intn(10) == 0 {
			r = l
		}
		t.Log(l, r, area)
		mud.add(l, r, area)
		mass += area

		// Check total histogram weight.
		hmass := 0.0
		for _, val := range mud.hist {
			hmass += val
		}
		if !aeq(mass, hmass) {
			t.Fatalf("want mass %g, got %g", mass, hmass)
		}

		// Check inverse cumulative sum approximations.
		for j := 0.0; j < mass; j += mass * 0.099 {
			mud.setTrackMass(j)
			l, u, ok := mud.approxInvCumulativeSum()
			inv, ok2 := mud.invCumulativeSum(j)
			if !ok || !ok2 {
				t.Fatalf("inverse cumulative sum failed: approx %v, exact %v", ok, ok2)
			}
			if !(l <= inv && inv < u) {
				t.Fatalf("inverse(%g) = %g, not ∈ [%g, %g)", j, inv, l, u)
			}
		}
	}
}

func TestMUDTracking(t *testing.T) {
	// Test that the tracked mass is tracked correctly across
	// updates.
	rnd := rand.New(rand.NewSource(42))
	const uniforms = 100
	for trackMass := 0.0; trackMass < uniforms; trackMass += uniforms / 50 {
		var mud mud
		mass := 0.0
		mud.setTrackMass(trackMass)
		for i := 0; i < uniforms; i++ {
			area, l, r := rnd.Float64(), rnd.Float64(), rnd.Float64()
			mud.add(l, r, area)
			mass += area
			l, u, ok := mud.approxInvCumulativeSum()
			inv, ok2 := mud.invCumulativeSum(trackMass)

			if mass < trackMass {
				if ok {
					t.Errorf("approx(%g) = [%g, %g), but mass = %g", trackMass, l, u, mass)
				}
				if ok2 {
					t.Errorf("exact(%g) = %g, but mass = %g", trackMass, inv, mass)
				}
			} else {
				if !ok {
					t.Errorf("approx(%g) failed, but mass = %g", trackMass, mass)
				}
				if !ok2 {
					t.Errorf("exact(%g) failed, but mass = %g", trackMass, mass)
				}
				if ok && ok2 && !(l <= inv && inv < u) {
					t.Errorf("inverse(%g) = %g, not ∈ [%g, %g)", trackMass, inv, l, u)
				}
			}
		}
	}
}

// aeq returns true if x and y are equal up to 8 digits (1 part in 100
// million).
// TODO(amedee) dup of gc_test.go
func aeq(x, y float64) bool {
	if x < 0 && y < 0 {
		x, y = -x, -y
	}
	const digits = 8
	factor := 1 - math.Pow(10, -digits+1)
	return x*factor <= y && y*factor <= x
}