Repository navigation
Expand file tree
/
Copy patharraydeque.go
More file actions
276 lines (244 loc) · 6.96 KB
/
Copy patharraydeque.go
File metadata and controls
276 lines (244 loc) · 6.96 KB
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
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
package collections
import (
"bytes"
"encoding/gob"
"encoding/json"
"encoding/json/jsontext"
jsonv2 "encoding/json/v2"
"iter"
)
// arrayDeque is a double-ended queue implemented as a circular buffer.
// Push/Pop at both ends are O(1) amortized; grows by doubling when full.
type arrayDeque[T any] struct {
buf []T
head int // index of first element
tail int // index one past the last element
size int
}
// NewArrayDeque creates an empty deque.
func NewArrayDeque[T any]() Deque[T] {
return &arrayDeque[T]{buf: make([]T, 0)}
}
// NewArrayDequeWithCapacity creates a deque with capacity hint.
// If capacity <= 0, an empty buffer is created and will grow on first insert.
func NewArrayDequeWithCapacity[T any](capacity int) Deque[T] {
if capacity < 0 {
capacity = 0
}
return &arrayDeque[T]{buf: make([]T, capacity)}
}
// NewArrayDequeFrom creates a deque from elements (front to back in given order).
func NewArrayDequeFrom[T any](elements ...T) Deque[T] {
cp := make([]T, len(elements))
copy(cp, elements)
// The buffer is exactly full, so the circular one-past-last index wraps to 0.
return &arrayDeque[T]{buf: cp, head: 0, tail: 0, size: len(cp)}
}
// Size returns the number of elements.
func (d *arrayDeque[T]) Size() int { return d.size }
// IsEmpty reports whether the deque is empty.
func (d *arrayDeque[T]) IsEmpty() bool { return d.size == 0 }
func (d *arrayDeque[T]) IsNotEmpty() bool { return !d.IsEmpty() }
// Clear removes all elements (retains capacity).
func (d *arrayDeque[T]) Clear() {
clear(d.buf)
d.head, d.tail, d.size = 0, 0, 0
}
// String returns a concise representation (front..back).
func (d *arrayDeque[T]) String() string {
return formatCollection("arrayDeque", d.Seq())
}
// PushFront adds an element to the front.
// The invariant tail == mod(head+size, len(buf)) holds at every mutation
// point, so moving head back while tail stays put keeps it intact.
func (d *arrayDeque[T]) PushFront(element T) {
d.ensureCapacityForOne()
d.head = d.mod(d.head-1, len(d.buf))
d.buf[d.head] = element
d.size++
}
// PopFront removes and returns the front element.
func (d *arrayDeque[T]) PopFront() (T, bool) {
if d.size == 0 {
var zero T
return zero, false
}
v := d.buf[d.head]
// Clear slot to drop references promptly.
var zero T
d.buf[d.head] = zero
d.head = d.mod(d.head+1, len(d.buf))
d.size--
return v, true
}
// PeekFront returns the front element without removing it.
func (d *arrayDeque[T]) PeekFront() (T, bool) {
if d.size == 0 {
var zero T
return zero, false
}
return d.buf[d.head], true
}
// PushBack adds an element to the back.
func (d *arrayDeque[T]) PushBack(element T) {
d.ensureCapacityForOne()
d.buf[d.tail] = element
d.tail = d.mod(d.tail+1, len(d.buf))
d.size++
}
// PopBack removes and returns the back element.
func (d *arrayDeque[T]) PopBack() (T, bool) {
if d.size == 0 {
var zero T
return zero, false
}
d.tail = d.mod(d.tail-1, len(d.buf))
v := d.buf[d.tail]
// Clear slot to drop references promptly.
var zero T
d.buf[d.tail] = zero
d.size--
return v, true
}
// PeekBack returns the back element without removing it.
func (d *arrayDeque[T]) PeekBack() (T, bool) {
if d.size == 0 {
var zero T
return zero, false
}
idx := d.mod(d.tail-1, len(d.buf))
return d.buf[idx], true
}
// ToSlice returns elements from front to back.
func (d *arrayDeque[T]) ToSlice() []T {
out := make([]T, d.size)
d.copyTo(out)
return out
}
// copyTo copies all elements front-to-back into dst (len(dst) >= size).
// The circular buffer holds at most two contiguous segments, so two copy
// calls replace a per-element loop with its modulo per element.
func (d *arrayDeque[T]) copyTo(dst []T) {
if d.size == 0 {
return
}
n := copy(dst, d.buf[d.head:min(d.head+d.size, len(d.buf))])
copy(dst[n:], d.buf[:d.size-n])
}
// Seq returns a sequence from front to back.
func (d *arrayDeque[T]) Seq() iter.Seq[T] {
return func(yield func(T) bool) {
for i := range d.size {
if !yield(d.at(i)) {
return
}
}
}
}
// Reversed returns a sequence from back to front.
func (d *arrayDeque[T]) Reversed() iter.Seq[T] {
return func(yield func(T) bool) {
for i := d.size - 1; i >= 0; i-- {
if !yield(d.at(i)) {
return
}
}
}
}
// ensureCapacityForOne ensures there is room for one more element.
func (d *arrayDeque[T]) ensureCapacityForOne() {
if d.size < len(d.buf) {
return
}
newCap := 1
if len(d.buf) > 0 {
newCap = len(d.buf) * 2
}
newBuf := make([]T, newCap)
d.copyTo(newBuf)
d.buf = newBuf
d.head = 0
d.tail = d.size
}
// at returns the element at logical index i (0..size-1).
func (d *arrayDeque[T]) at(i int) T {
return d.buf[d.mod(d.head+i, len(d.buf))]
}
// mod wraps n within [0,m). Callers guarantee m > 0: every call site runs
// after ensureCapacityForOne or behind a size > 0 guard.
func (*arrayDeque[T]) mod(n, m int) int {
n %= m
if n < 0 {
n += m
}
return n
}
// Note on growth strategy:
// We double the buffer capacity when full (geometric growth by 2x). This keeps amortized
// PushFront/PushBack at O(1) and reduces the number of resizes for long-lived deques.
// The copy during growth preserves logical order (front..back) in the new buffer.
// ==========================
// Serialization
// ==========================
// MarshalJSON implements json.Marshaler.
// Serializes from front to back as a JSON array.
func (d *arrayDeque[T]) MarshalJSON() ([]byte, error) {
return json.Marshal(d.ToSlice())
}
// UnmarshalJSON implements json.Unmarshaler.
// Deserializes from a JSON array.
func (d *arrayDeque[T]) UnmarshalJSON(data []byte) error {
var slice []T
if err := json.Unmarshal(data, &slice); err != nil {
return err
}
d.replaceFromSlice(slice)
return nil
}
// replaceFromSlice rebuilds the deque from slice; the buffer is exactly
// full, so tail wraps to 0.
func (d *arrayDeque[T]) replaceFromSlice(slice []T) {
d.buf = make([]T, len(slice))
copy(d.buf, slice)
d.head = 0
d.tail = 0
d.size = len(slice)
}
// MarshalJSONTo implements jsonv2.MarshalerTo.
// Streams the same JSON as MarshalJSON into enc.
func (d *arrayDeque[T]) MarshalJSONTo(enc *jsontext.Encoder) error {
return jsonv2.MarshalEncode(enc, d.ToSlice())
}
// UnmarshalJSONFrom implements jsonv2.UnmarshalerFrom.
// Accepts the same JSON as UnmarshalJSON, streamed from dec.
func (d *arrayDeque[T]) UnmarshalJSONFrom(dec *jsontext.Decoder) error {
var slice []T
if err := jsonv2.UnmarshalDecode(dec, &slice); err != nil {
return err
}
d.replaceFromSlice(slice)
return nil
}
// GobEncode implements gob.GobEncoder.
func (d *arrayDeque[T]) GobEncode() ([]byte, error) {
var buf bytes.Buffer
enc := gob.NewEncoder(&buf)
if err := enc.Encode(d.ToSlice()); err != nil {
return nil, err
}
return buf.Bytes(), nil
}
// GobDecode implements gob.GobDecoder.
func (d *arrayDeque[T]) GobDecode(data []byte) error {
var slice []T
dec := gob.NewDecoder(bytes.NewReader(data))
if err := dec.Decode(&slice); err != nil {
return err
}
d.replaceFromSlice(slice)
return nil
}
// Compile-time conformance.
var (
_ Deque[int] = (*arrayDeque[int])(nil)
)