-
Notifications
You must be signed in to change notification settings - Fork 103
/
circular_queue_using_array_test.go
136 lines (120 loc) · 3.95 KB
/
circular_queue_using_array_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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
package queue
import "testing"
/*
TestCircularQueue tests solution(s) with the following signature and problem description:
func (queue *UsingCircularArray) enqueue(n int) error
func (queue *UsingCircularArray) dequeue() (int, error)
Given a size, implement a circular queue using an array.
A circular queue also called a ring buffer is different from a normal queue in that
the last element is connected to the first element.
*/
func TestCircularQueue(t *testing.T) {
// Tests a queue by enqueues given items,
// then dequeues a number of times and finally checks the value from the last dequeue.
// The same process then may be repeated for a second time with different values.
tests := []struct {
size int
firstRound *testCase
secondRound *testCase
}{
{0, &testCase{[]int{1, 2, 3, 4}, -1, -1, true, false}, nil},
{4, &testCase{[]int{1, 2, 3, 4}, 1, 1, false, false}, nil},
{4, &testCase{[]int{1, 2, 3, 4}, 2, 2, false, false}, nil},
{4, &testCase{[]int{1, 2, 3, 4}, 3, 3, false, false}, nil},
{4, &testCase{[]int{1, 2, 2, 3}, 2, 2, false, false}, nil},
{2, &testCase{[]int{1, 2, 2, 3}, 2, 2, true, false}, nil},
{2, &testCase{[]int{1, 2}, 3, -1, false, true}, nil},
{2, &testCase{[]int{1, 2}, 2, 2, false, false}, &testCase{[]int{1, 2}, 1, 1, false, false}},
{2, &testCase{[]int{1, 2}, 1, 1, false, false}, &testCase{[]int{1}, 2, 1, false, false}},
}
for i, test := range tests {
queue := NewCircularQueue(test.size)
enqueueDequeueAndCheckValue(t, queue, i, test.firstRound)
if test.secondRound != nil {
enqueueDequeueAndCheckValue(t, queue, i, test.secondRound)
}
}
}
type testCase struct {
enqueue []int
dequeueTimes int
expectedLastDequeuedItem int
expectEnqueueErr bool
expectDequeueErr bool
}
const (
operationTypeEnqueue = iota
operationTypeDequeue
)
var queueOperations = []struct {
operationType int
operationValue int
}{
{operationTypeEnqueue, 3},
{operationTypeEnqueue, 2},
{operationTypeEnqueue, 1},
{operationTypeDequeue, 0},
{operationTypeDequeue, 0},
{operationTypeDequeue, 0},
{operationTypeEnqueue, 3},
{operationTypeEnqueue, 2},
{operationTypeEnqueue, 1},
{operationTypeDequeue, 0},
{operationTypeDequeue, 0},
{operationTypeDequeue, 0},
{operationTypeEnqueue, 5},
{operationTypeDequeue, 0},
{operationTypeEnqueue, 1},
{operationTypeDequeue, 0},
{operationTypeEnqueue, 1},
}
func enqueueDequeueAndCheckValue(t *testing.T, queue *CircularQueue, testID int, test *testCase) {
t.Helper()
for _, n := range test.enqueue {
if err := queue.enqueue(n); err != nil {
if test.expectEnqueueErr {
t.Skipf("Skipping test case #%d. Expected error occurred. Error %s", testID, err)
}
t.Fatalf("Failed test case #%d. Did not expect enqueuing error. Error %s", testID, err)
}
}
var n int
var err error
for j := 1; j <= test.dequeueTimes; j++ {
n, err = queue.dequeue()
if err != nil {
if test.expectDequeueErr {
t.Skipf("Skipping test case #%d. Expected error occurred. Error %s", testID, err)
}
t.Fatalf("Failed test case #%d. Did not expect dequeuing error. Error %s", testID, err)
}
}
if n != test.expectedLastDequeuedItem {
t.Fatalf("Failed test case #%d. Want %d got %d", testID, test.expectedLastDequeuedItem, n)
}
}
func TestMultipleOperations(t *testing.T) {
queue := NewCircularQueue(3)
if _, err := queue.dequeue(); err == nil {
t.Fatal("Expected error for dequeue-ing an empty queue")
}
for i, queueOperation := range queueOperations {
switch queueOperation.operationType {
case operationTypeEnqueue:
if err := queue.enqueue(queueOperation.operationValue); err != nil {
t.Fatalf("operation #%d, unexpected error: %s", i, err)
}
case operationTypeDequeue:
if _, err := queue.dequeue(); err != nil {
t.Fatalf("operation #%d, unexpected error: %s", i, err)
}
}
}
n, err := queue.dequeue()
if err != nil {
t.Fatalf("Failed to dequeue. Error %s", err)
}
if n != 1 {
t.Fatalf("Wanted %d, got %d", 1, n)
}
}