list.gno
7.11 Kb ยท 331 lines
1// Package list implements a dynamic list data structure backed by an AVL tree.
2// It provides O(log n) operations for most list operations while maintaining
3// order stability.
4//
5// The list supports various operations including append, get, set, delete,
6// range queries, and iteration. It can store values of any type.
7//
8// Example usage:
9//
10// // Create a new list and add elements
11// var l list.List
12// l.Append(1, 2, 3)
13//
14// // Get and set elements
15// value := l.Get(1) // returns 2
16// l.Set(1, 42) // updates index 1 to 42
17//
18// // Delete elements
19// l.Delete(0) // removes first element
20//
21// // Iterate over elements
22// l.ForEach(func(index int, value any) bool {
23// ufmt.Printf("index %d: %v\n", index, value)
24// return false // continue iteration
25// })
26// // Output:
27// // index 0: 42
28// // index 1: 3
29//
30// // Create a list of specific size
31// l = list.Make(3, "default") // creates [default, default, default]
32//
33// // Create a list using a variable declaration
34// var l2 list.List
35// l2.Append(4, 5, 6)
36// println(l2.Len()) // Output: 3
37package list
38
39import (
40 "gno.land/p/nt/avl"
41 "gno.land/p/nt/avl/rotree"
42 "gno.land/p/nt/seqid"
43)
44
45// IList defines the interface for list operations
46type IList interface {
47 Len() int
48 Append(values ...any)
49 Get(index int) any
50 Set(index int, value any) bool
51 Delete(index int) (any, bool)
52 Slice(startIndex, endIndex int) []any
53 ForEach(fn func(index int, value any) bool)
54 Clone() *List
55 DeleteRange(startIndex, endIndex int) int
56}
57
58// Verify List implements IList interface
59var _ IList = (*List)(nil)
60
61// List represents an ordered sequence of items backed by an AVL tree
62type List struct {
63 tree avl.Tree
64 idGen seqid.ID
65}
66
67// Len returns the number of elements in the list.
68//
69// Example:
70//
71// var l list.List
72// l.Append(1, 2, 3)
73// println(l.Len()) // Output: 3
74func (l *List) Len() int {
75 return l.tree.Size()
76}
77
78// Append adds one or more values to the end of the list.
79//
80// Example:
81//
82// var l list.List
83// l.Append(1) // adds single value
84// l.Append(2, 3, 4) // adds multiple values
85// println(l.Len()) // Output: 4
86func (l *List) Append(values ...any) {
87 for _, v := range values {
88 l.tree.Set(l.idGen.Next().String(), v)
89 }
90}
91
92// Get returns the value at the specified index.
93// Returns nil if index is out of bounds.
94//
95// Example:
96//
97// var l list.List
98// l.Append(1, 2, 3)
99// println(l.Get(1)) // Output: 2
100// println(l.Get(-1)) // Output: nil
101// println(l.Get(999)) // Output: nil
102func (l *List) Get(index int) any {
103 if index < 0 || index >= l.tree.Size() {
104 return nil
105 }
106 _, value := l.tree.GetByIndex(index)
107 return value
108}
109
110// Set updates or appends a value at the specified index.
111// Returns true if the operation was successful, false otherwise.
112// For empty lists, only index 0 is valid (append case).
113//
114// Example:
115//
116// var l list.List
117// l.Append(1, 2, 3)
118//
119// l.Set(1, 42) // updates existing index
120// println(l.Get(1)) // Output: 42
121//
122// l.Set(3, 4) // appends at end
123// println(l.Get(3)) // Output: 4
124//
125// l.Set(-1, 5) // invalid index
126// println(l.Len()) // Output: 4 (list unchanged)
127func (l *List) Set(index int, value any) bool {
128 size := l.tree.Size()
129
130 // Handle empty list case - only allow index 0
131 if size == 0 {
132 if index == 0 {
133 l.Append(value)
134 return true
135 }
136 return false
137 }
138
139 if index < 0 || index > size {
140 return false
141 }
142
143 // If setting at the end (append case)
144 if index == size {
145 l.Append(value)
146 return true
147 }
148
149 // Get the key at the specified index
150 key, _ := l.tree.GetByIndex(index)
151 if key == "" {
152 return false
153 }
154
155 // Update the value at the existing key
156 l.tree.Set(key, value)
157 return true
158}
159
160// Delete removes the element at the specified index.
161// Returns the deleted value and true if successful, nil and false otherwise.
162//
163// Example:
164//
165// var l list.List
166// l.Append(1, 2, 3)
167//
168// val, ok := l.Delete(1)
169// println(val, ok) // Output: 2 true
170// println(l.Len()) // Output: 2
171//
172// val, ok = l.Delete(-1)
173// println(val, ok) // Output: nil false
174func (l *List) Delete(index int) (any, bool) {
175 size := l.tree.Size()
176 // Always return nil, false for empty list
177 if size == 0 {
178 return nil, false
179 }
180
181 if index < 0 || index >= size {
182 return nil, false
183 }
184
185 key, value := l.tree.GetByIndex(index)
186 if key == "" {
187 return nil, false
188 }
189
190 l.tree.Remove(key)
191 return value, true
192}
193
194// Slice returns a slice of values from startIndex (inclusive) to endIndex (exclusive).
195// Returns nil if the range is invalid.
196//
197// Example:
198//
199// var l list.List
200// l.Append(1, 2, 3, 4, 5)
201//
202// println(l.Slice(1, 4)) // Output: [2 3 4]
203// println(l.Slice(-1, 2)) // Output: [1 2]
204// println(l.Slice(3, 999)) // Output: [4 5]
205// println(l.Slice(3, 2)) // Output: nil
206func (l *List) Slice(startIndex, endIndex int) []any {
207 size := l.tree.Size()
208
209 // Normalize bounds
210 if startIndex < 0 {
211 startIndex = 0
212 }
213 if endIndex > size {
214 endIndex = size
215 }
216 if startIndex >= endIndex {
217 return nil
218 }
219
220 count := endIndex - startIndex
221 result := make([]any, count)
222
223 i := 0
224 l.tree.IterateByOffset(startIndex, count, func(_ string, value any) bool {
225 result[i] = value
226 i++
227 return false
228 })
229 return result
230}
231
232// ForEach iterates through all elements in the list.
233func (l *List) ForEach(fn func(index int, value any) bool) {
234 if l.tree.Size() == 0 {
235 return
236 }
237
238 index := 0
239 l.tree.IterateByOffset(0, l.tree.Size(), func(_ string, value any) bool {
240 result := fn(index, value)
241 index++
242 return result
243 })
244}
245
246// Clone creates a shallow copy of the list.
247//
248// Example:
249//
250// var l list.List
251// l.Append(1, 2, 3)
252//
253// clone := l.Clone()
254// clone.Set(0, 42)
255//
256// println(l.Get(0)) // Output: 1
257// println(clone.Get(0)) // Output: 42
258func (l *List) Clone() *List {
259 newList := &List{
260 tree: avl.Tree{},
261 idGen: l.idGen,
262 }
263
264 size := l.tree.Size()
265 if size == 0 {
266 return newList
267 }
268
269 l.tree.IterateByOffset(0, size, func(_ string, value any) bool {
270 newList.Append(value)
271 return false
272 })
273
274 return newList
275}
276
277// DeleteRange removes elements from startIndex (inclusive) to endIndex (exclusive).
278// Returns the number of elements deleted.
279//
280// Example:
281//
282// var l list.List
283// l.Append(1, 2, 3, 4, 5)
284//
285// deleted := l.DeleteRange(1, 4)
286// println(deleted) // Output: 3
287// println(l.Range(0, l.Len())) // Output: [1 5]
288func (l *List) DeleteRange(startIndex, endIndex int) int {
289 size := l.tree.Size()
290
291 // Normalize bounds
292 if startIndex < 0 {
293 startIndex = 0
294 }
295 if endIndex > size {
296 endIndex = size
297 }
298 if startIndex >= endIndex {
299 return 0
300 }
301
302 // Collect keys to delete
303 keysToDelete := make([]string, 0, endIndex-startIndex)
304 l.tree.IterateByOffset(startIndex, endIndex-startIndex, func(key string, _ any) bool {
305 keysToDelete = append(keysToDelete, key)
306 return false
307 })
308
309 // Delete collected keys
310 for _, key := range keysToDelete {
311 l.tree.Remove(key)
312 }
313
314 return len(keysToDelete)
315}
316
317// Tree returns a read-only pointer to the underlying AVL tree.
318//
319// Example:
320//
321// var l list.List
322// l.Append(1, 2, 3)
323//
324// rotree := l.Tree()
325// rotree.ReverseIterateByOffset(0, rotree.Size(), func(key string, value any) bool {
326// println(value) // Output: 3 2 1
327// return false
328// })
329func (l *List) Tree() *rotree.ReadOnlyTree {
330 return rotree.Wrap(&l.tree, nil)
331}
