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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
|
// Package vecdeque implements a double-ended queue (deque) implemented with a
// growable ring buffer.
//
// This queue has O(1) amortized inserts and removals from both ends of the
// container. It also has O(1) indexing like a vector.
package deque
// The core implementation is "ported" (stolen) from Rust's VecDeque.
import (
"fmt"
"iter"
"slices"
)
// Deque is a double-ended queue. The zero value is ready for use.
type Deque[T any] struct {
head int
buf []T
}
// WithCapacity allocates a deque with the given capacity.
func WithCapacity[T any](cap int) *Deque[T] {
return &Deque[T]{buf: make([]T, 0, cap)}
}
// From creates a new queue using the given slice as the backing buffer.
func From[S ~[]T, T any](slice S) *Deque[T] {
return &Deque[T]{buf: slice}
}
func (q *Deque[T]) wrapAdd(i, addend int) int {
i += addend
if i >= cap(q.buf) {
return i - cap(q.buf)
}
return i
}
func (q *Deque[T]) toPhysicalIdx(i int) int {
return q.wrapAdd(q.head, i)
}
// At returns the item at position i.
func (q *Deque[T]) At(i int) T {
if !(0 <= i && i < len(q.buf)) {
panic(fmt.Sprintf("index out of range [%d] with length %d", i, len(q.buf)))
}
return q.buf[:cap(q.buf)][q.toPhysicalIdx(i)]
}
// Cap returns the number of elements the deque can hold without reallocating.
func (q *Deque[T]) Cap() int {
return cap(q.buf)
}
// Len returns the number of elements in the deque.
func (q *Deque[T]) Len() int {
return len(q.buf)
}
// PopFront removes and returns the item at index 0 if the deque is non-empty.
func (q *Deque[T]) PopFront() (T, bool) {
if len(q.buf) == 0 {
var zero T
return zero, false
}
oldHead := q.head
q.head = q.toPhysicalIdx(1)
q.buf = q.buf[:len(q.buf)-1]
return q.buf[:cap(q.buf)][oldHead], true
}
// PopBack removes and returns the last item in the deque if it is non-empty.
func (q *Deque[T]) PopBack() (T, bool) {
if len(q.buf) == 0 {
var zero T
return zero, false
}
q.buf = q.buf[:len(q.buf)-1]
return q.buf[:cap(q.buf)][q.toPhysicalIdx(len(q.buf))], true
}
// PushFront prepends the given items to the front of the deque.
func (q *Deque[T]) PushFront(values ...T) {
q.Grow(len(values))
q.buf = q.buf[:len(q.buf)+len(values)]
if q.head >= len(values) {
newHead := q.head - len(values)
copy(q.buf[newHead:q.head], values)
q.head = newHead
} else {
tailLen := len(values) - q.head
copy(q.buf[:q.head], values[tailLen:])
copy(q.buf[cap(q.buf)-tailLen:cap(q.buf)], values[:tailLen])
q.head = cap(q.buf) - tailLen
}
}
// PushBack appends the given items to the back of the deque.
func (q *Deque[T]) PushBack(values ...T) {
q.Grow(len(values))
endIdx := q.wrapAdd(q.head, len(q.buf))
if len(values) < cap(q.buf)-endIdx {
copy(q.buf[endIdx:endIdx+len(values)], values)
} else {
headLen := cap(q.buf) - endIdx
copy(q.buf[endIdx:cap(q.buf)], values[:headLen])
copy(q.buf[:len(values)-headLen], values[headLen:])
}
q.buf = q.buf[:len(q.buf)+len(values)]
}
// Reset empties the deque, retaining the underlying storage for use by
// future pushes.
func (q *Deque[T]) Reset() {
q.buf = q.buf[:0]
}
// Grow makes space for at least n more elements to be inserted in the given
// deque without reallocation.
func (q *Deque[T]) Grow(n int) {
if n <= cap(q.buf)-len(q.buf) {
return
}
oldCap := cap(q.buf)
q.buf = slices.Grow(q.buf, n)
newCap := cap(q.buf)
// Move the shortest contiguous section of the ring buffer
//
// H := head
// L := last element (`self.to_physical_idx(self.len - 1)`)
//
// H L
// [o o o o o o o o ]
// H L
// A [o o o o o o o o . . . . . . . . ]
// L H
// [o o o o o o o o ]
// H L
// B [. . . o o o o o o o o . . . . . ]
// L H
// [o o o o o o o o ]
// L H
// C [o o o o o o . . . . . . . . o o ]
if q.head <= oldCap-len(q.buf) {
// A
return
}
headLen := oldCap - q.head
tailLen := len(q.buf) - headLen
if headLen > tailLen && newCap-oldCap >= tailLen {
// B
copy(q.buf[oldCap:oldCap+tailLen], q.buf[:tailLen])
return
}
// C
newHead := newCap - headLen
copy(q.buf[newHead:newHead+headLen], q.buf[q.head:q.head+headLen])
q.head = newHead
}
// All returns an iterator over the elements in the deque. It does not pop
// any elements.
func (q *Deque[T]) All() iter.Seq2[int, T] {
return func(yield func(int, T) bool) {
// Don't use range over int in case the length changes while
// we're iterating
for i := 0; i < len(q.buf); i++ {
if !yield(i, q.buf[:cap(q.buf)][q.toPhysicalIdx(i)]) {
return
}
}
}
}
// PopAll empties the deque and returns an iterator over the popped elements.
// It's not safe to modify the deque while iterating using PopAll.
func (q *Deque[T]) PopAll() iter.Seq[T] {
n := len(q.buf)
q.buf = q.buf[:0]
return func(yield func(T) bool) {
for i := range n {
if !yield(q.buf[:cap(q.buf)][q.toPhysicalIdx(i)]) {
return
}
}
}
}
|
