package gheap

import (
	"container/heap"
	"fmt"
	"math/rand"
	"testing"
)

const N = 10000000

var ints []int
var out1, out2 []int

func init() {
	for i := 0; i < N; i++ {
		ints = append(ints, rand.Int())
	}
	out1 = make([]int, N)
	out2 = make([]int, N)
}

func UseTypeAssertion(n int) {
	mh := myHeap(make([]int, 0, n))
	h := &mh

	a, b := n/2, n/4
	c := a + b

	for i := 0; i < a; i++ {
		heap.Push(h, ints[i])
	}
	for i := 0; i < b; i++ {
		out1[i] = heap.Pop(h).(int)
	}
	for i := a; i < c; i++ {
		heap.Push(h, ints[i])
	}
	for i := b; i < a; i++ {
		out1[i] = heap.Pop(h).(int)
	}
	for i := c; i < n; i++ {
		heap.Push(h, ints[i])
	}
	for i := a; i < n; i++ {
		out1[i] = heap.Pop(h).(int)
	}
}

func NotUseTypeAssertion(n int) {
	mh := myGHeap(make([]int, 0, n))
	h := &mh

	a, b := n/2, n/4
	c := a + b

	for i := 0; i < a; i++ {
		h.Push(ints[i])
	}
	for i := 0; i < b; i++ {
		out2[i] = h.Pop()
	}
	for i := a; i < c; i++ {
		h.Push(ints[i])
	}
	for i := b; i < a; i++ {
		out2[i] = h.Pop()
	}
	for i := c; i < n; i++ {
		h.Push(ints[i])
	}
	for i := a; i < n; i++ {
		out2[i] = h.Pop()
	}
}

func areEq(n int) bool {
	for i := 0; i < n; i++ {
		if out1[i] != out2[i] {
			fmt.Println("mismatch!")
			return false
		}
	}
	return true
}

func benchmark(f func(int), n int, b *testing.B) {
	for i := 0; i < b.N; i++ {
		f(n)
	}
}

func BenchmarkStdHeap1000(b *testing.B)     { benchmark(UseTypeAssertion, 1000, b) }
func BenchmarkMyGHeap1000(b *testing.B)     { benchmark(NotUseTypeAssertion, 1000, b) }
func BenchmarkCheckEq1000(b *testing.B)     { areEq(1000) }
func BenchmarkStdHeap10000(b *testing.B)    { benchmark(UseTypeAssertion, 10000, b) }
func BenchmarkMyGHeap10000(b *testing.B)    { benchmark(NotUseTypeAssertion, 10000, b) }
func BenchmarkCheckEq10000(b *testing.B)    { areEq(10000) }
func BenchmarkStdHeap100000(b *testing.B)   { benchmark(UseTypeAssertion, 100000, b) }
func BenchmarkMyGHeap100000(b *testing.B)   { benchmark(NotUseTypeAssertion, 100000, b) }
func BenchmarkCheckEq100000(b *testing.B)   { areEq(100000) }
func BenchmarkStdHeap1000000(b *testing.B)  { benchmark(UseTypeAssertion, 1000000, b) }
func BenchmarkMyGHeap1000000(b *testing.B)  { benchmark(NotUseTypeAssertion, 1000000, b) }
func BenchmarkCheckEq1000000(b *testing.B)  { areEq(1000000) }
func BenchmarkStdHeap10000000(b *testing.B) { benchmark(UseTypeAssertion, 10000000, b) }
func BenchmarkMyGHeap10000000(b *testing.B) { benchmark(NotUseTypeAssertion, 10000000, b) }
func BenchmarkCheckEq10000000(b *testing.B) { areEq(10000000) }

// for without type assertion version
type myGHeap []int

func (h *myGHeap) Less(i, j int) bool {
	return (*h)[i] < (*h)[j]
}
func (h *myGHeap) Swap(i, j int) {
	(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}
func (h *myGHeap) Len() int {
	return len(*h)
}
func (h *myGHeap) Pop() (v int) {
	//~ gheap.Pop(h)
	Pop(h)
	*h, v = (*h)[:h.Len()-1], (*h)[h.Len()-1]
	return
}
func (h *myGHeap) Push(v int) {
	*h = append(*h, v)
	//~ gheap.Push(h)
	Push(h)
}

// for type assertion version
type myHeap []int

func (h *myHeap) Less(i, j int) bool {
	return (*h)[i] < (*h)[j]
}
func (h *myHeap) Swap(i, j int) {
	(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}
func (h *myHeap) Len() int {
	return len(*h)
}
func (h *myHeap) Pop() (v interface{}) {
	*h, v = (*h)[:h.Len()-1], (*h)[h.Len()-1]
	return
}
func (h *myHeap) Push(v interface{}) {
	*h = append(*h, v.(int))
}