deque.gno
6.91 Kb · 326 lines
1// Package deque provides a doubly-linked deque with optional size limits,
2// optimized for minimal storage updates and O(1) operations in Gno environments.
3//
4// This implementation uses a doubly-linked list structure that provides:
5// - O(1) push back operations
6// - O(1) pop front operations
7// - O(1) access to first/last elements
8// - No array resizing or slice shifting
9// - Minimal allocations (one node per element)
10// - Minimal storage updates (typically 1-2 pointer updates per operation)
11// - Optional max-size eviction policy
12//
13// Optimized for Gno blockchain storage: each operation updates only specific nodes
14// rather than entire data structures, making it ideal for storage-efficient lists
15// that need simple read operations like first/last access, size checks, list
16// enumeration, and iteration with minimal storage update overhead.
17//
18// Example usage:
19//
20// // Unbounded deque
21// d := deque.New()
22// d.PushBack("a", "b", "c")
23//
24// // Bounded deque with automatic eviction
25// d = deque.NewBounded(3)
26// d.PushBack("a", "b", "c", "d") // "a" gets evicted
27//
28// first := d.PopFront() // Returns "b"
29// last := d.Last() // Returns "d"
30//
31// // Iterate forward
32// iter := d.All()
33// iter(func(val any) bool {
34// println(val)
35// return true // continue
36// })
37//
38// // Iterate backward
39// iter = d.Backward()
40// iter(func(val any) bool {
41// println(val)
42// return true // continue
43// })
44package deque
45
46// Node represents a single element in the doubly-linked list
47type Node struct {
48 value any
49 prev *Node
50 next *Node
51}
52
53// Deque represents a doubly-linked deque with optional size limits
54type Deque struct {
55 head *Node
56 tail *Node
57 size int
58 max int // 0 = unlimited
59}
60
61// New creates a new unbounded deque.
62func New() *Deque {
63 return &Deque{
64 max: 0, // unlimited
65 }
66}
67
68// NewBounded creates a new bounded deque with the specified maximum size.
69// When the deque exceeds maxSize, elements are removed from the front.
70func NewBounded(maxSize int) *Deque {
71 if maxSize <= 0 {
72 maxSize = 1
73 }
74 return &Deque{
75 max: maxSize,
76 }
77}
78
79// PushBack adds one or more elements to the back of the deque.
80// If the deque exceeds maxSize, elements are removed from the front.
81func (d *Deque) PushBack(items ...any) {
82 for _, item := range items {
83 d.pushBackSingle(item)
84 }
85}
86
87// pushBackSingle adds a single element to the back
88func (d *Deque) pushBackSingle(item any) {
89 node := &Node{value: item}
90
91 if d.tail == nil {
92 // First element
93 d.head = node
94 d.tail = node
95 } else {
96 // Link to existing tail
97 d.tail.next = node
98 node.prev = d.tail
99 d.tail = node
100 }
101
102 d.size++
103
104 // Handle size limit by removing from front
105 if d.max > 0 && d.size > d.max {
106 d.popFrontNode()
107 }
108}
109
110// PopFront removes and returns the front element.
111// Returns nil if the deque is empty.
112func (d *Deque) PopFront() any {
113 if d.head == nil {
114 return nil
115 }
116
117 value := d.head.value
118 d.popFrontNode()
119 return value
120}
121
122// popFrontNode removes the front node
123func (d *Deque) popFrontNode() {
124 if d.head == nil {
125 return
126 }
127
128 if d.head == d.tail {
129 // Only one element
130 d.head = nil
131 d.tail = nil
132 } else {
133 // Move head forward
134 d.head = d.head.next
135 d.head.prev = nil
136 }
137
138 d.size--
139}
140
141// PopBack removes and returns the back element.
142// Returns nil if the deque is empty.
143func (d *Deque) PopBack() any {
144 if d.tail == nil {
145 return nil
146 }
147
148 value := d.tail.value
149 d.popBackNode()
150 return value
151}
152
153// popBackNode removes the back node
154func (d *Deque) popBackNode() {
155 if d.tail == nil {
156 return
157 }
158
159 if d.head == d.tail {
160 // Only one element
161 d.head = nil
162 d.tail = nil
163 } else {
164 // Move tail backward
165 d.tail = d.tail.prev
166 d.tail.next = nil
167 }
168
169 d.size--
170}
171
172// PushFront adds one or more elements to the front of the deque.
173// If bounded and size limit is exceeded, elements are removed from the back.
174func (d *Deque) PushFront(items ...any) {
175 for _, item := range items {
176 d.pushFrontSingle(item)
177 }
178}
179
180// pushFrontSingle adds a single element to the front
181func (d *Deque) pushFrontSingle(item any) {
182 node := &Node{value: item}
183
184 if d.head == nil {
185 // First element
186 d.head = node
187 d.tail = node
188 } else {
189 // Link to existing head
190 d.head.prev = node
191 node.next = d.head
192 d.head = node
193 }
194
195 d.size++
196
197 // Handle size limit by removing from back
198 if d.max > 0 && d.size > d.max {
199 d.popBackNode()
200 }
201}
202
203// Size returns the current number of elements
204func (d *Deque) Size() int {
205 return d.size
206}
207
208// MaxSize returns the maximum size limit (0 = unlimited)
209func (d *Deque) MaxSize() int {
210 return d.max
211}
212
213// IsEmpty returns true if the deque is empty
214func (d *Deque) IsEmpty() bool {
215 return d.size == 0
216}
217
218// IsBounded returns true if the deque has a size limit
219func (d *Deque) IsBounded() bool {
220 return d.max > 0
221}
222
223// First returns the front element without removing it.
224// Returns nil if the deque is empty.
225func (d *Deque) First() any {
226 if d.head == nil {
227 return nil
228 }
229 return d.head.value
230}
231
232// Last returns the back element without removing it.
233// Returns nil if the deque is empty.
234func (d *Deque) Last() any {
235 if d.tail == nil {
236 return nil
237 }
238 return d.tail.value
239}
240
241// Get returns the element at the specified index (0 = front).
242// Returns nil if index is out of bounds.
243func (d *Deque) Get(index int) any {
244 if index < 0 || index >= d.size {
245 return nil
246 }
247
248 node := d.head
249 for i := 0; i < index; i++ {
250 node = node.next
251 }
252 return node.value
253}
254
255// List returns all elements as a slice, ordered from front to back
256func (d *Deque) List() []any {
257 if d.size == 0 {
258 return nil
259 }
260
261 result := make([]any, d.size)
262 node := d.head
263 for i := 0; i < d.size; i++ {
264 result[i] = node.value
265 node = node.next
266 }
267 return result
268}
269
270// Enumerate calls fn for each element with its index (0-based from front)
271func (d *Deque) Enumerate(fn func(index int, value any) bool) {
272 node := d.head
273 for i := 0; i < d.size; i++ {
274 if fn(i, node.value) {
275 break
276 }
277 node = node.next
278 }
279}
280
281// Clear removes all elements from the deque
282func (d *Deque) Clear() {
283 d.head = nil
284 d.tail = nil
285 d.size = 0
286}
287
288// SetMaxSize changes the maximum size limit.
289// If the new limit is smaller than current size, elements are removed from front.
290func (d *Deque) SetMaxSize(maxSize int) {
291 d.max = maxSize
292
293 if maxSize > 0 {
294 for d.size > maxSize {
295 d.popFrontNode()
296 }
297 }
298}
299
300// All returns an iterator function for forward traversal (Go 1.23+ compatible)
301// Note: range-over-func syntax is not yet supported in Gno, use iter() directly
302func (d *Deque) All() func(yield func(any) bool) {
303 return func(yield func(any) bool) {
304 current := d.head
305 for current != nil {
306 if !yield(current.value) {
307 return
308 }
309 current = current.next
310 }
311 }
312}
313
314// Backward returns an iterator function for backward traversal (Go 1.23+ compatible)
315// Note: range-over-func syntax is not yet supported in Gno, use iter() directly
316func (d *Deque) Backward() func(yield func(any) bool) {
317 return func(yield func(any) bool) {
318 current := d.tail
319 for current != nil {
320 if !yield(current.value) {
321 return
322 }
323 current = current.prev
324 }
325 }
326}
