132 lines
2.5 KiB
Go
132 lines
2.5 KiB
Go
package binheap_test
|
|
|
|
import (
|
|
"math/rand"
|
|
"testing"
|
|
|
|
"gogs.humancabbage.net/sam/priorityq/binheap"
|
|
)
|
|
|
|
func TestSmoke(t *testing.T) {
|
|
h := binheap.Make[int, int](10)
|
|
if h.Capacity() != 10 {
|
|
t.Errorf("expected heap capacity to be 10")
|
|
}
|
|
h.Insert(1, 1)
|
|
h.Insert(2, 2)
|
|
h.Insert(3, 3)
|
|
h.Insert(4, 4)
|
|
if h.Len() != 4 {
|
|
t.Errorf("expected heap length to be 4")
|
|
}
|
|
checkExtract := func(n int) {
|
|
_, extracted := h.Extract()
|
|
if extracted != n {
|
|
t.Errorf("expected to extract %d, got %d", n, extracted)
|
|
}
|
|
}
|
|
checkExtract(4)
|
|
checkExtract(3)
|
|
checkExtract(2)
|
|
checkExtract(1)
|
|
}
|
|
|
|
func TestInsertFullPanic(t *testing.T) {
|
|
h := binheap.Make[int, int](4)
|
|
h.Insert(1, 1)
|
|
h.Insert(2, 2)
|
|
h.Insert(3, 3)
|
|
h.Insert(4, 4)
|
|
defer func() {
|
|
if r := recover(); r == nil {
|
|
t.Errorf("expected final insert to panic")
|
|
}
|
|
}()
|
|
h.Insert(5, 5)
|
|
}
|
|
|
|
func TestExtractEmptyPanic(t *testing.T) {
|
|
h := binheap.Make[int, int](4)
|
|
defer func() {
|
|
if r := recover(); r == nil {
|
|
t.Errorf("expected extract to panic")
|
|
}
|
|
}()
|
|
h.Extract()
|
|
}
|
|
|
|
func TestRandomized(t *testing.T) {
|
|
h := binheap.Make[int, int](8192)
|
|
rs := rand.NewSource(0)
|
|
r := rand.New(rs)
|
|
// insert a bunch of random integers
|
|
for i := 0; i < h.Capacity(); i++ {
|
|
n := r.Int()
|
|
h.Insert(n, n)
|
|
}
|
|
// ensure that each extracted integer is <= the last extracted integer
|
|
var extracted []int
|
|
for h.CanExtract() {
|
|
id, item := h.Extract()
|
|
if id != item {
|
|
t.Errorf("id / item mismatch: %d %d", id, item)
|
|
}
|
|
lastIdx := len(extracted) - 1
|
|
extracted = append(extracted, item)
|
|
if lastIdx < 0 {
|
|
continue
|
|
}
|
|
if item > extracted[lastIdx] {
|
|
t.Errorf("newly extracted %d is greater than %d",
|
|
item, extracted[lastIdx])
|
|
}
|
|
}
|
|
}
|
|
|
|
func BenchmarkInsert(b *testing.B) {
|
|
h := binheap.Make[int, int](b.N)
|
|
rs := rand.NewSource(0)
|
|
r := rand.New(rs)
|
|
items := make([]int, b.N)
|
|
for i := 0; i < b.N; i++ {
|
|
items[i] = r.Int()
|
|
}
|
|
b.ResetTimer()
|
|
for i := 0; i < b.N; i++ {
|
|
h.Insert(items[i], items[i])
|
|
}
|
|
}
|
|
|
|
func BenchmarkExtract(b *testing.B) {
|
|
h := binheap.Make[int, int](b.N)
|
|
rs := rand.NewSource(0)
|
|
r := rand.New(rs)
|
|
for i := 0; i < b.N; i++ {
|
|
n := r.Int()
|
|
h.Insert(n, n)
|
|
}
|
|
b.ResetTimer()
|
|
for i := 0; i < b.N; i++ {
|
|
h.Extract()
|
|
}
|
|
}
|
|
|
|
func BenchmarkRepeatedInsertExtract(b *testing.B) {
|
|
h := binheap.Make[int, int](128)
|
|
rs := rand.NewSource(0)
|
|
r := rand.New(rs)
|
|
items := make([]int, b.N)
|
|
for i := 0; i < h.Capacity()-1; i++ {
|
|
n := r.Int()
|
|
h.Insert(n, n)
|
|
}
|
|
for i := 0; i < b.N; i++ {
|
|
items[i] = r.Int()
|
|
}
|
|
b.ResetTimer()
|
|
for i := 0; i < b.N; i++ {
|
|
h.Insert(items[i], items[i])
|
|
h.Extract()
|
|
}
|
|
}
|