func checkVarAndStd(t *testing.T, i int, x []float64, v varStder, tol float64) {
	variance := stat.Variance(x, nil)
	if !floats.EqualWithinAbsOrRel(variance, v.Variance(), tol, tol) {
		t.Errorf("Variance mismatch case %v: want: %v, got: %v", i, variance, v.Variance())
	}
	std := math.Sqrt(variance)
	if !floats.EqualWithinAbsOrRel(std, v.StdDev(), tol, tol) {
		t.Errorf("StdDev mismatch case %v: want: %v, got: %v", i, std, v.StdDev())
	}
}

func TestLegendre(t *testing.T) {
	for i, test := range []struct {
		f        func(float64) float64
		min, max float64
		n        []int
		tol      []float64
		ans      float64
	}{
		// Tolerances determined from intuition and a bit of post-hoc tweaking.
		{
			f:   func(x float64) float64 { return math.Exp(x) },
			min: -3,
			max: 5,
			n:   []int{3, 4, 6, 7, 15, 16, 300, 301},
			tol: []float64{5e-2, 5e-3, 5e-6, 1e-7, 1e-14, 1e-14, 1e-14, 1e-14},
			ans: math.Exp(5) - math.Exp(-3),
		},
	} {
		for j, n := range test.n {
			ans := Fixed(test.f, test.min, test.max, n, Legendre{}, 0)
			if !floats.EqualWithinAbsOrRel(ans, test.ans, test.tol[j], test.tol[j]) {
				t.Errorf("Mismatch. Case = %d, n = %d. Want %v, got %v", i, n, test.ans, ans)
			}
			ans2 := Fixed(test.f, test.min, test.max, n, Legendre{}, 3)
			if !floats.EqualWithinAbsOrRel(ans2, test.ans, test.tol[j], test.tol[j]) {
				t.Errorf("Mismatch concurrent. Case = %d, n = %d. Want %v, got %v", i, n, test.ans, ans)
			}
		}
	}
}

func TestHITS(t *testing.T) {
	for i, test := range hitsTests {
		g := concrete.NewDirectedGraph(0, math.Inf(1))
		for u, e := range test.g {
			// Add nodes that are not defined by an edge.
			if !g.Has(concrete.Node(u)) {
				g.AddNode(concrete.Node(u))
			}
			for v := range e {
				g.SetEdge(concrete.Edge{F: concrete.Node(u), T: concrete.Node(v)})
			}
		}
		got := HITS(g, test.tol)
		prec := 1 - int(math.Log10(test.wantTol))
		for n := range test.g {
			if !floats.EqualWithinAbsOrRel(got[n].Hub, test.want[n].Hub, test.wantTol, test.wantTol) {
				t.Errorf("unexpected HITS result for test %d:\ngot: %v\nwant:%v",
					i, orderedHubAuth(got, prec), orderedHubAuth(test.want, prec))
				break
			}
			if !floats.EqualWithinAbsOrRel(got[n].Authority, test.want[n].Authority, test.wantTol, test.wantTol) {
				t.Errorf("unexpected HITS result for test %d:\ngot: %v\nwant:%v",
					i, orderedHubAuth(got, prec), orderedHubAuth(test.want, prec))
				break
			}
		}
	}
}

func TestRankTwo(t *testing.T) {
	for _, test := range []struct {
		n int
	}{
		{n: 1},
		{n: 2},
		{n: 3},
		{n: 4},
		{n: 5},
		{n: 10},
	} {
		n := test.n
		alpha := 2.0
		a := NewSymDense(n, nil)
		for i := range a.mat.Data {
			a.mat.Data[i] = rand.Float64()
		}
		x := make([]float64, n)
		y := make([]float64, n)
		for i := range x {
			x[i] = rand.Float64()
			y[i] = rand.Float64()
		}

		xMat := NewDense(n, 1, x)
		yMat := NewDense(n, 1, y)
		var m Dense
		m.Mul(xMat, yMat.T())
		var tmp Dense
		tmp.Mul(yMat, xMat.T())
		m.Add(&m, &tmp)
		m.Scale(alpha, &m)
		m.Add(&m, a)

		// Check with new receiver
		s := NewSymDense(n, nil)
		s.RankTwo(a, alpha, NewVector(len(x), x), NewVector(len(y), y))
		for i := 0; i < n; i++ {
			for j := i; j < n; j++ {
				if !floats.EqualWithinAbsOrRel(s.At(i, j), m.At(i, j), 1e-14, 1e-14) {
					t.Errorf("unexpected element value at (%d,%d): got: %f want: %f", i, j, m.At(i, j), s.At(i, j))
				}
			}
		}

		// Check with reused receiver
		copy(s.mat.Data, a.mat.Data)
		s.RankTwo(s, alpha, NewVector(len(x), x), NewVector(len(y), y))
		for i := 0; i < n; i++ {
			for j := i; j < n; j++ {
				if !floats.EqualWithinAbsOrRel(s.At(i, j), m.At(i, j), 1e-14, 1e-14) {
					t.Errorf("unexpected element value at (%d,%d): got: %f want: %f", i, j, m.At(i, j), s.At(i, j))
				}
			}
		}
	}
}

func SameF64Approx(str string, c, native, absTol, relTol float64) {
	if math.IsNaN(c) && math.IsNaN(native) {
		return
	}
	if !floats.EqualWithinAbsOrRel(c, native, absTol, relTol) {
		cb := math.Float64bits(c)
		nb := math.Float64bits(native)
		same := floats.EqualWithinAbsOrRel(c, native, absTol, relTol)
		panic(fmt.Sprintf("Case %s: Float64 mismatch. c = %v, native = %v\n cb: %v, nb: %v\n%v,%v,%v", str, c, native, cb, nb, same, absTol, relTol))
	}
}

func TestReduceQConsistency(t *testing.T) {
tests:
	for _, test := range communityQTests {
		g := simple.NewUndirectedGraph(0, 0)
		for u, e := range test.g {
			// Add nodes that are not defined by an edge.
			if !g.Has(simple.Node(u)) {
				g.AddNode(simple.Node(u))
			}
			for v := range e {
				g.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v), W: 1})
			}
		}

		for _, structure := range test.structures {
			if math.IsNaN(structure.want) {
				continue tests
			}

			communities := make([][]graph.Node, len(structure.memberships))
			for i, c := range structure.memberships {
				for n := range c {
					communities[i] = append(communities[i], simple.Node(n))
				}
				sort.Sort(ordered.ByID(communities[i]))
			}

			gQ := Q(g, communities, structure.resolution)
			gQnull := Q(g, nil, 1)

			cg0 := reduce(g, nil)
			cg0Qnull := Q(cg0, cg0.Structure(), 1)
			if !floats.EqualWithinAbsOrRel(gQnull, cg0Qnull, structure.tol, structure.tol) {
				t.Errorf("disgagreement between null Q from method: %v and function: %v", cg0Qnull, gQnull)
			}
			cg0Q := Q(cg0, communities, structure.resolution)
			if !floats.EqualWithinAbsOrRel(gQ, cg0Q, structure.tol, structure.tol) {
				t.Errorf("unexpected Q result after initial conversion: got: %v want :%v", gQ, cg0Q)
			}

			cg1 := reduce(cg0, communities)
			cg1Q := Q(cg1, cg1.Structure(), structure.resolution)
			if !floats.EqualWithinAbsOrRel(gQ, cg1Q, structure.tol, structure.tol) {
				t.Errorf("unexpected Q result after initial condensation: got: %v want :%v", gQ, cg1Q)
			}
		}
	}
}

func TestEdgeBetweenness(t *testing.T) {
	for i, test := range betweennessTests {
		g := simple.NewUndirectedGraph(0, math.Inf(1))
		for u, e := range test.g {
			// Add nodes that are not defined by an edge.
			if !g.Has(simple.Node(u)) {
				g.AddNode(simple.Node(u))
			}
			for v := range e {
				// Weight omitted to show weight-independence.
				g.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v), W: 0})
			}
		}
		got := EdgeBetweenness(g)
		prec := 1 - int(math.Log10(test.wantTol))
	outer:
		for u := range test.g {
			for v := range test.g {
				wantQ, gotOK := got[[2]int{u, v}]
				gotQ, wantOK := test.wantEdges[[2]int{u, v}]
				if gotOK != wantOK {
					t.Errorf("unexpected betweenness result for test %d, edge (%c,%c)", i, u+'A', v+'A')
				}
				if !floats.EqualWithinAbsOrRel(gotQ, wantQ, test.wantTol, test.wantTol) {
					t.Errorf("unexpected betweenness result for test %d:\ngot: %v\nwant:%v",
						i, orderedPairFloats(got, prec), orderedPairFloats(test.wantEdges, prec))
					break outer
				}
			}
		}
	}
}

func TestCommunityQ(t *testing.T) {
	for _, test := range communityQTests {
		g := simple.NewUndirectedGraph(0, 0)
		for u, e := range test.g {
			// Add nodes that are not defined by an edge.
			if !g.Has(simple.Node(u)) {
				g.AddNode(simple.Node(u))
			}
			for v := range e {
				g.SetEdge(simple.Edge{F: simple.Node(u), T: simple.Node(v), W: 1})
			}
		}
		for _, structure := range test.structures {
			communities := make([][]graph.Node, len(structure.memberships))
			for i, c := range structure.memberships {
				for n := range c {
					communities[i] = append(communities[i], simple.Node(n))
				}
			}
			got := Q(g, communities, structure.resolution)
			if !floats.EqualWithinAbsOrRel(got, structure.want, structure.tol, structure.tol) && math.IsNaN(got) != math.IsNaN(structure.want) {
				for _, c := range communities {
					sort.Sort(ordered.ByID(c))
				}
				t.Errorf("unexpected Q value for %q %v: got: %v want: %v",
					test.name, communities, got, structure.want)
			}
		}
	}
}

func Dorg2rTest(t *testing.T, impl Dorg2rer) {
	rnd := rand.New(rand.NewSource(1))
	for _, test := range []struct {
		m, n, k, lda int
	}{
		{3, 3, 0, 0},
		{4, 3, 0, 0},
		{3, 3, 2, 0},
		{4, 3, 2, 0},

		{5, 5, 0, 20},
		{5, 5, 3, 20},
		{10, 5, 0, 20},
		{10, 5, 2, 20},
	} {
		m := test.m
		n := test.n
		lda := test.lda
		if lda == 0 {
			lda = test.n
		}
		a := make([]float64, m*lda)
		for i := range a {
			a[i] = rnd.NormFloat64()
		}
		k := min(m, n)
		tau := make([]float64, k)
		work := make([]float64, 1)
		impl.Dgeqrf(m, n, a, lda, tau, work, -1)
		work = make([]float64, int(work[0]))
		impl.Dgeqrf(m, n, a, lda, tau, work, len(work))

		k = test.k
		if k == 0 {
			k = n
		}
		q := constructQK("QR", m, n, k, a, lda, tau)

		impl.Dorg2r(m, n, k, a, lda, tau, work)

		// Check that the first n columns match.
		same := true
		for i := 0; i < m; i++ {
			for j := 0; j < n; j++ {
				if !floats.EqualWithinAbsOrRel(q.Data[i*q.Stride+j], a[i*lda+j], 1e-12, 1e-12) {
					same = false
					break
				}
			}
		}
		if !same {
			fmt.Println()
			fmt.Println("a =")
			printRowise(a, m, n, lda, false)
			fmt.Println("q =")
			printRowise(q.Data, q.Rows, q.Cols, q.Stride, false)
			t.Errorf("Q mismatch")
		}
	}
}

func TestBetweennessWeighted(t *testing.T) {
	for i, test := range betweennessTests {
		g := concrete.NewGraph(0, math.Inf(1))
		for u, e := range test.g {
			// Add nodes that are not defined by an edge.
			if !g.Has(concrete.Node(u)) {
				g.AddNode(concrete.Node(u))
			}
			for v := range e {
				g.SetEdge(concrete.Edge{F: concrete.Node(u), T: concrete.Node(v), W: 1})
			}
		}

		p, ok := path.FloydWarshall(g)
		if !ok {
			t.Errorf("unexpected negative cycle in test %d", i)
			continue
		}

		got := BetweennessWeighted(g, p)
		prec := 1 - int(math.Log10(test.wantTol))
		for n := range test.g {
			gotN, gotOK := got[n]
			wantN, wantOK := test.want[n]
			if gotOK != wantOK {
				t.Errorf("unexpected betweenness existence for test %d, node %d", i, n)
			}
			if !floats.EqualWithinAbsOrRel(gotN, wantN, test.wantTol, test.wantTol) {
				t.Errorf("unexpected betweenness result for test %d:\ngot: %v\nwant:%v",
					i, orderedFloats(got, prec), orderedFloats(test.want, prec))
				break
			}
		}
	}
}

func TestBetweenness(t *testing.T) {
	for i, test := range betweennessTests {
		g := concrete.NewGraph()
		for u, e := range test.g {
			// Add nodes that are not defined by an edge.
			if !g.Has(concrete.Node(u)) {
				g.AddNode(concrete.Node(u))
			}
			for v := range e {
				g.SetEdge(concrete.Edge{F: concrete.Node(u), T: concrete.Node(v)}, 0)
			}
		}
		got := Betweenness(g)
		prec := 1 - int(math.Log10(test.wantTol))
		for n := range test.g {
			wantN, gotOK := got[n]
			gotN, wantOK := test.want[n]
			if gotOK != wantOK {
				t.Errorf("unexpected betweenness result for test %d, node %d", i, n)
			}
			if !floats.EqualWithinAbsOrRel(gotN, wantN, test.wantTol, test.wantTol) {
				t.Errorf("unexpected betweenness result for test %d:\ngot: %v\nwant:%v",
					i, orderedFloats(got, prec), orderedFloats(test.want, prec))
				break
			}
		}
	}
}

func checkQuantileCDFSurvival(t *testing.T, i int, xs []float64, c cumulanter, tol float64) {
	// Quantile, CDF, and survival check.
	for i, p := range []float64{0.1, 0.25, 0.5, 0.75, 0.9} {
		x := c.Quantile(p)
		cdf := c.CDF(x)
		estCDF := stat.CDF(x, stat.Empirical, xs, nil)
		if !floats.EqualWithinAbsOrRel(cdf, estCDF, tol, tol) {
			t.Errorf("CDF mismatch case %v: want: %v, got: %v", i, estCDF, cdf)
		}
		if !floats.EqualWithinAbsOrRel(cdf, p, tol, tol) {
			t.Errorf("Quantile/CDF mismatch case %v: want: %v, got: %v", i, p, cdf)
		}
		if math.Abs(1-cdf-c.Survival(x)) > 1e-14 {
			t.Errorf("Survival/CDF mismatch case %v: want: %v, got: %v", i, 1-cdf, c.Survival(x))
		}
	}
}

func TestGeneralizedBinomial(t *testing.T) {
	for cas, test := range binomialTests {
		ans := GeneralizedBinomial(float64(test.n), float64(test.k))
		if !floats.EqualWithinAbsOrRel(ans, float64(test.ans), 1e-14, 1e-14) {
			t.Errorf("Case %v: Binomial mismatch. Got %v, want %v.", cas, ans, test.ans)
		}
	}
}

func checkEntropy(t *testing.T, i int, x []float64, e entropyer, tol float64) {
	tmp := make([]float64, len(x))
	for i, v := range x {
		tmp[i] = -e.LogProb(v)
	}
	entropy := stat.Mean(tmp, nil)
	if !floats.EqualWithinAbsOrRel(entropy, e.Entropy(), tol, tol) {
		t.Errorf("Entropy mismatch case %v: want: %v, got: %v", i, entropy, e.Entropy())
	}
}

func approxEqual(a, b []float64, epsilon float64) bool {
	if len(a) != len(b) {
		return false
	}
	for i, v := range a {
		if !floats.EqualWithinAbsOrRel(v, b[i], epsilon, epsilon) {
			return false
		}
	}
	return true
}

// Take returns an index from the Weighted with probability proportional
// to the weight of the item. The weight of the item is then set to zero.
// Take returns false if there are no items remaining.
func (s Weighted) Take() (idx int, ok bool) {
	const small = 1e-12
	if floats.EqualWithinAbsOrRel(s.heap[0], 0, small, small) {
		return -1, false
	}

	var r float64
	if s.src == nil {
		r = s.heap[0] * rand.Float64()
	} else {
		r = s.heap[0] * s.src.Float64()
	}
	i := 1
	last := -1
	left := len(s.weights)
	for {
		if r -= s.weights[i-1]; r <= 0 {
			break // Fall within item i-1.
		}
		i <<= 1 // Move to left child.
		if d := s.heap[i-1]; r > d {
			r -= d
			// If enough r to pass left child
			// move to right child state will
			// be caught at break above.
			i++
		}
		if i == last || left < 0 {
			// No progression.
			return -1, false
		}
		last = i
		left--
	}

	w, idx := s.weights[i-1], i-1

	s.weights[i-1] = 0
	for i > 0 {
		s.heap[i-1] -= w
		// The following condition is necessary to
		// handle floating point error. If we see
		// a heap value below zero, we know we need
		// to rebuild it.
		if s.heap[i-1] < 0 {
			s.reset()
			return idx, true
		}
		i >>= 1
	}

	return idx, true
}

func DpotrfTest(t *testing.T, impl Dpotrfer) {
	rnd := rand.New(rand.NewSource(1))
	bi := blas64.Implementation()
	for i, test := range []struct {
		n int
	}{
		{n: 10},
		{n: 30},
		{n: 63},
		{n: 65},
		{n: 128},
		{n: 1000},
	} {
		n := test.n
		// Construct a positive-definite symmetric matrix
		base := make([]float64, n*n)
		for i := range base {
			base[i] = rnd.Float64()
		}
		a := make([]float64, len(base))
		bi.Dgemm(blas.Trans, blas.NoTrans, n, n, n, 1, base, n, base, n, 0, a, n)

		aCopy := make([]float64, len(a))
		copy(aCopy, a)

		// Test with Upper
		impl.Dpotrf(blas.Upper, n, a, n)

		// zero all the other elements
		for i := 0; i < n; i++ {
			for j := 0; j < i; j++ {
				a[i*n+j] = 0
			}
		}
		// Multiply u^T * u
		ans := make([]float64, len(a))
		bi.Dsyrk(blas.Upper, blas.Trans, n, n, 1, a, n, 0, ans, n)

		match := true
		for i := 0; i < n; i++ {
			for j := i; j < n; j++ {
				if !floats.EqualWithinAbsOrRel(ans[i*n+j], aCopy[i*n+j], 1e-14, 1e-14) {
					match = false
				}
			}
		}
		if !match {
			//fmt.Println(aCopy)
			//fmt.Println(ans)
			t.Errorf("Case %v: Mismatch for upper", i)
		}
	}
}

func TestFixedNonSingle(t *testing.T) {
	// TODO(btracey): Add tests with infinite bounds when we have native support
	// for indefinite integrals.
	for i, test := range []struct {
		f        func(float64) float64
		min, max float64
		n        []int
		tol      []float64
		ans      float64
	}{
		// Tolerances determined from intuition and a bit of post-hoc tweaking.
		{
			f:   func(x float64) float64 { return math.Exp(x) },
			min: -3,
			max: 5,
			n:   []int{3, 4, 6, 7, 15, 16, 300, 301},
			tol: []float64{5e-2, 5e-3, 5e-6, 1e-7, 1e-14, 1e-14, 1e-14, 1e-14},
			ans: math.Exp(5) - math.Exp(-3),
		},
		{
			f:   func(x float64) float64 { return math.Exp(x) },
			min: 3,
			max: 3,
			n:   []int{3, 4, 6, 7, 15, 16, 300, 301},
			tol: []float64{0, 0, 0, 0, 0, 0, 0, 0},
			ans: 0,
		},
	} {
		for j, n := range test.n {
			ans := Fixed(test.f, test.min, test.max, n, legendreNonSingle{}, 0)
			if !floats.EqualWithinAbsOrRel(ans, test.ans, test.tol[j], test.tol[j]) {
				t.Errorf("Case = %d, n = %d: Mismatch. Want %v, got %v", i, n, test.ans, ans)
			}
			ans2 := Fixed(test.f, test.min, test.max, n, legendreNonSingle{}, 3)
			if !floats.EqualWithinAbsOrRel(ans2, test.ans, test.tol[j], test.tol[j]) {
				t.Errorf("Case = %d, n = %d: Mismatch concurrent. Want %v, got %v", i, n, test.ans, ans)
			}
		}
	}
}

func checkSkewness(t *testing.T, i int, x []float64, s skewnesser, tol float64) {
	mean := s.Mean()
	std := s.StdDev()
	tmp := make([]float64, len(x))
	for i, v := range x {
		tmp[i] = math.Pow(v-mean, 3)
	}
	mu3 := stat.Mean(tmp, nil)
	skewness := mu3 / math.Pow(std, 3)
	if !floats.EqualWithinAbsOrRel(skewness, s.Skewness(), tol, tol) {
		t.Errorf("ExKurtosis mismatch case %v: want: %v, got: %v", i, skewness, s.Skewness())
	}
}

func checkExKurtosis(t *testing.T, i int, x []float64, e exKurtosiser, tol float64) {
	mean := e.Mean()
	tmp := make([]float64, len(x))
	for i, x := range x {
		tmp[i] = math.Pow(x-mean, 4)
	}
	variance := stat.Variance(x, nil)
	mu4 := stat.Mean(tmp, nil)
	kurtosis := mu4/(variance*variance) - 3
	if !floats.EqualWithinAbsOrRel(kurtosis, e.ExKurtosis(), tol, tol) {
		t.Errorf("ExKurtosis mismatch case %v: want: %v, got: %v", i, kurtosis, e.ExKurtosis())
	}
}