-
Notifications
You must be signed in to change notification settings - Fork 0
/
queue.go
122 lines (103 loc) · 2.13 KB
/
queue.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
package queue
const minSize = 3
type Queue[T any] struct {
items []T
size int
head, tail int
zero T
}
func New[T any](items ...T) *Queue[T] {
result := &Queue[T]{}
result.Fill(items)
return result
}
func (q *Queue[T]) IsEmpty() bool {
return q.head == q.tail
}
func (q *Queue[T]) Len() int {
return (q.tail + q.size + 1 - q.head) & q.size
}
func (q *Queue[T]) Items() []T {
if q.tail >= q.head {
return q.items[q.head:q.tail]
}
l := q.Len()
result := make([]T, l)
copy(result, q.items[q.head:q.size+1])
copy(result[q.size-q.head+1:], q.items[:q.tail])
return result
}
func (q *Queue[T]) Append(item T) *Queue[T] {
q.items[q.tail] = item
q.tail = (q.tail + 1) & q.size
if q.tail == q.head {
q.grow()
}
return q
}
func (q *Queue[T]) Prepend(item T) *Queue[T] {
q.head = (q.head - 1) & q.size
q.items[q.head] = item
if q.head == q.tail {
q.grow()
}
return q
}
func (q *Queue[T]) First() (T, bool) {
if q.head == q.tail {
return q.zero, false
}
result := q.items[q.head]
q.items[q.head] = q.zero
q.head = (q.head + 1) & q.size
if q.head == 0 && q.size > minSize && (q.tail<<2) <= q.size {
q.size = computeSize(q.tail << 1)
items := make([]T, q.size+1)
copy(items, q.items[:q.tail])
q.items = items
}
return result, true
}
func (q *Queue[T]) Last() (T, bool) {
if q.head == q.tail {
return q.zero, false
}
q.tail = (q.tail - 1) & q.size
result := q.items[q.tail]
q.items[q.tail] = q.zero
return result, true
}
func (q *Queue[T]) Fill(items []T) {
l := len(items)
q.head = 0
q.tail = l
q.size = computeSize(l)
q.items = make([]T, q.size+1)
copy(q.items, items)
}
func (q *Queue[T]) Clear() {
q.Fill(make([]T, 0))
}
func computeSize(length int) (size int) {
if length <= minSize {
size = minSize
} else {
length |= length >> 1
length |= length >> 2
length |= length >> 4
length |= length >> 8
size = length | length>>16
}
return
}
func (q *Queue[T]) grow() {
items := make([]T, (q.size+1)<<1)
copy(items, q.items[q.head:])
if q.head > 0 {
copy(items[q.size+1-q.head:], q.items[0:q.head])
}
q.head = 0
q.tail = q.size + 1
q.size = q.size + q.tail
q.items = items
}