priority-queue/priorityqueue_test.go at master · dannoane/priority-queue · GitHub

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
package priorityqueue

import (
	"testing"
)

func assert(condition bool, t *testing.T, msg string, args ...interface{}) {
	if !condition {
		t.Errorf(msg, args...)
	}
}

func TestInititalization(t *testing.T) {
	queue := NewPriorityQueue()

	assert(queue.Len() == 0, t, "Empty priority queue length should be 0, not %d", queue.Len())
}

func TestPush(t *testing.T) {
	queue := NewPriorityQueue()
	queue.Push(&Element{Value: 1, Priority: 5})

	assert(queue.Len() == 1, t, "Priority queue length should be 1, not %d", queue.Len())
	assert(queue.At(0).Value == 1, t, "Element at index 0 should have value 1")

	queue.Push(&Element{Value: 0, Priority: 6})
	assert(queue.At(0).Value == 0, t, "Element at index 0 should have value 0")
	assert(queue.At(1).Value == 1, t, "Element at index 1 should have value 1")
}

func TestPeek(t *testing.T) {
	queue := NewPriorityQueue()

	queue.Push(&Element{Value: 1, Priority: 100})
	elem := queue.Peek()
	assert(elem.Value == 1, t, "Top element should have value 1")
	assert(!queue.IsEmpty(), t, "The priority queue should not be empty")

	queue.Push(&Element{Value: 2, Priority: 200})
	elem = queue.Peek()
	assert(elem.Value == 2, t, "Top element should have value 2")
	assert(!queue.IsEmpty(), t, "The priority queue should not be empty")

	queue.Push(&Element{Value: 3, Priority: -100})
	elem = queue.Peek()
	assert(elem.Value != 3, t, "Top element should have value 2")
}

func TestPop(t *testing.T) {
	queue := NewPriorityQueue()
	queue.Push(&Element{Value: 1, Priority: 10})
	queue.Push(&Element{Value: 2, Priority: 3})
	queue.Push(&Element{Value: 3, Priority: 15})
	queue.Push(&Element{Value: 4, Priority: -12})

	assert(queue.Pop().Value == 3, t, "First element to be removed should have value 3")
	assert(queue.Pop().Value == 1, t, "Second element to be removed should have value 1")
	assert(queue.Pop().Value == 2, t, "Third element to be removed should have value 2")
	assert(queue.Pop().Value == 4, t, "Fourth element to be removed should have value 4")
	assert(queue.Len() == 0, t, "Priority queue length should be 0, not %d", queue.Len())
}

func TestPopLowest(t *testing.T) {
	queue := NewPriorityQueue()
	queue.Push(&Element{Value: 1, Priority: 10})
	queue.Push(&Element{Value: 2, Priority: 3})
	queue.Push(&Element{Value: 3, Priority: 15})
	queue.Push(&Element{Value: 4, Priority: -12})

	assert(queue.PopLowest().Value == 4, t, "First element to be removed should have value 4")
	assert(queue.PopLowest().Value == 2, t, "Second element to be removed should have value 2")
	assert(queue.PopLowest().Value == 1, t, "Third element to be removed should have value 1")
	assert(queue.PopLowest().Value == 3, t, "Fourth element to be removed should have value 3")
	assert(queue.IsEmpty(), t, "Priority queue length should be 0, not %d", queue.Len())
}

func TestRemove(t *testing.T) {
	queue := NewPriorityQueue()
	queue.Push(&Element{Value: 1, Priority: 15})
	queue.Push(&Element{Value: 2, Priority: -12})
	queue.Push(&Element{Value: 3, Priority: 10})
	queue.Push(&Element{Value: 4, Priority: 14})
	queue.Push(&Element{Value: 5, Priority: 4})

	// The heap will keep the elements in the following order (by priority) [15, 14, 10, -12, 4]

	assert(queue.Remove(1).Value == 4, t, "Removed element at index 1 should have value 4")
	assert(queue.Remove(1).Value == 5, t, "Removed element at index 1 should have value 5")
	assert(queue.Remove(2).Value == 3, t, "Removed element at index 2 should have value 3")
	assert(queue.Remove(1).Value == 2, t, "Removed element at index 1 should have value 2")
	assert(queue.Remove(0).Value == 1, t, "Removed element at index 0 should have value 1")
	assert(queue.Len() == 0, t, "Priority queue length should be 0, not %d", queue.Len())
}