blob: caf705af03b5b08417470dc476cd46066de4cd7d [file] [log] [blame]
// Copyright 2021 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 (
"reflect"
"testing"
)
func TestIntervalTree(t *testing.T) {
t.Parallel()
inserts := []struct {
v float64
tree []int
median float64
}{
// These values were pulled from the appendix of the edm paper where the
// interval tree is described.
{0.09, []int{1, 1, 0, 1, 0, 0, 0}, 0.25},
{0.42, []int{2, 2, 0, 1, 1, 0, 0}, 0.125},
{0.99, []int{3, 2, 1, 1, 1, 0, 1}, 0.25},
{0.36, []int{4, 3, 1, 1, 2, 0, 1}, 0.375},
}
tree := NewIntervalTree(2)
if l := tree.NumElements(); l != 0 {
t.Errorf("tree.Length() = %d, expected 0", l)
}
if v := tree.Median(); v != 0 {
t.Errorf("tree.Median() = %f, expected 0", v)
}
for i, ins := range inserts {
tree.Insert(ins.v)
if !reflect.DeepEqual(tree.vals, ins.tree) {
t.Errorf("[%d] tree.Insert(%v) = %v, expected %v", i, ins.v, tree.vals, ins.tree)
}
if l := tree.NumElements(); l != i+1 {
t.Errorf("[%d] tree.Length() = %d, expected %d", i, l, i+1)
}
if v := tree.Median(); v != ins.median {
t.Errorf("[%d] tree.Median() = %f, expected %f", i, v, ins.median)
}
}
}