This repository has been archived by the owner on Dec 13, 2019. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
index_fibonacci_min_pq_test.go
103 lines (97 loc) · 1.87 KB
/
index_fibonacci_min_pq_test.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package heap
import "testing"
func TestInsert(t *testing.T) {
pq, err := NewIndexFibonacciMinPQ(10)
if err != nil {
t.Fatal(err)
}
err = pq.Insert(2, 1)
if err != nil {
t.Fatalf("insert returned unexpected error: %v", err)
}
err = pq.Insert(1, 2)
if err != nil {
t.Fatalf("insert returned unexpected error: %v", err)
}
if pq.Len() != 2 {
t.Fatalf("expected pq length 2, but got %d", pq.Len())
}
if pq.IsEmpty() {
t.Fatal("expected non empty queue")
}
}
func TestInsertAndDelMin(t *testing.T) {
pq, err := NewIndexFibonacciMinPQ(10)
if err != nil {
t.Fatal(err)
}
testData := []struct {
i int
k float32
}{
{1, 0.1},
{4, 0.4},
{9, 0.9},
{2, 0.2},
{3, 0.3},
{5, 0.5},
{7, 0.7},
{8, 0.8},
{6, 0.6},
}
for _, testCase := range testData {
if err := pq.Insert(testCase.i, testCase.k); err != nil {
t.Fatal(err)
}
}
if pq.Len() != 9 {
t.Fatalf("expected pq length 9, but got %d", pq.Len())
}
expectedDel := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
for n := 0; !pq.IsEmpty(); n++ {
i, err := pq.DelMin()
if err != nil {
t.Fatalf("delete minimun failed: %v", err)
}
if expectedDel[n] != i {
t.Fatalf("expected %d, but got %d", expectedDel[i], i)
}
}
}
func TestDecreaseKey(t *testing.T) {
pq, err := NewIndexFibonacciMinPQ(10)
if err != nil {
t.Fatal(err)
}
testData := []struct {
i int
k float32
}{
{1, 0.1},
{4, 0.4},
{9, 0.9},
{2, 0.2},
{3, 0.3},
{5, 0.5},
{7, 0.7},
{8, 0.8},
{6, 0.6},
}
for _, testCase := range testData {
if err = pq.Insert(testCase.i, testCase.k); err != nil {
t.Fatal(err)
}
}
for i := 0; i < len(testData); i++ {
err = pq.DecreaseKey(i+1, 0.01)
if err != nil {
t.Fatal(err)
}
if key, err := pq.DelMin(); key != i+1 {
t.Fatalf("expected key %d, but got %d", i+1, key)
if err != nil {
t.Fatalf("delete minumum returned an error: %v", err)
}
}
}
}