list.gno
6.72 Kb ยท 314 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/demo/avl"
41 "gno.land/p/demo/seqid"
42)
43
44// IList defines the interface for list operations
45type IList interface {
46 Len() int
47 Append(values ...any)
48 Get(index int) any
49 Set(index int, value any) bool
50 Delete(index int) (any, bool)
51 Slice(startIndex, endIndex int) []any
52 ForEach(fn func(index int, value any) bool)
53 Clone() *List
54 DeleteRange(startIndex, endIndex int) int
55}
56
57// Verify List implements IList interface
58var _ IList = (*List)(nil)
59
60// List represents an ordered sequence of items backed by an AVL tree
61type List struct {
62 tree avl.Tree
63 idGen seqid.ID
64}
65
66// Len returns the number of elements in the list.
67//
68// Example:
69//
70// l := list.New()
71// l.Append(1, 2, 3)
72// println(l.Len()) // Output: 3
73func (l *List) Len() int {
74 return l.tree.Size()
75}
76
77// Append adds one or more values to the end of the list.
78//
79// Example:
80//
81// l := list.New()
82// l.Append(1) // adds single value
83// l.Append(2, 3, 4) // adds multiple values
84// println(l.Len()) // Output: 4
85func (l *List) Append(values ...any) {
86 for _, v := range values {
87 l.tree.Set(l.idGen.Next().String(), v)
88 }
89}
90
91// Get returns the value at the specified index.
92// Returns nil if index is out of bounds.
93//
94// Example:
95//
96// l := list.New()
97// l.Append(1, 2, 3)
98// println(l.Get(1)) // Output: 2
99// println(l.Get(-1)) // Output: nil
100// println(l.Get(999)) // Output: nil
101func (l *List) Get(index int) any {
102 if index < 0 || index >= l.tree.Size() {
103 return nil
104 }
105 _, value := l.tree.GetByIndex(index)
106 return value
107}
108
109// Set updates or appends a value at the specified index.
110// Returns true if the operation was successful, false otherwise.
111// For empty lists, only index 0 is valid (append case).
112//
113// Example:
114//
115// l := list.New()
116// l.Append(1, 2, 3)
117//
118// l.Set(1, 42) // updates existing index
119// println(l.Get(1)) // Output: 42
120//
121// l.Set(3, 4) // appends at end
122// println(l.Get(3)) // Output: 4
123//
124// l.Set(-1, 5) // invalid index
125// println(l.Len()) // Output: 4 (list unchanged)
126func (l *List) Set(index int, value any) bool {
127 size := l.tree.Size()
128
129 // Handle empty list case - only allow index 0
130 if size == 0 {
131 if index == 0 {
132 l.Append(value)
133 return true
134 }
135 return false
136 }
137
138 if index < 0 || index > size {
139 return false
140 }
141
142 // If setting at the end (append case)
143 if index == size {
144 l.Append(value)
145 return true
146 }
147
148 // Get the key at the specified index
149 key, _ := l.tree.GetByIndex(index)
150 if key == "" {
151 return false
152 }
153
154 // Update the value at the existing key
155 l.tree.Set(key, value)
156 return true
157}
158
159// Delete removes the element at the specified index.
160// Returns the deleted value and true if successful, nil and false otherwise.
161//
162// Example:
163//
164// l := list.New()
165// l.Append(1, 2, 3)
166//
167// val, ok := l.Delete(1)
168// println(val, ok) // Output: 2 true
169// println(l.Len()) // Output: 2
170//
171// val, ok = l.Delete(-1)
172// println(val, ok) // Output: nil false
173func (l *List) Delete(index int) (any, bool) {
174 size := l.tree.Size()
175 // Always return nil, false for empty list
176 if size == 0 {
177 return nil, false
178 }
179
180 if index < 0 || index >= size {
181 return nil, false
182 }
183
184 key, value := l.tree.GetByIndex(index)
185 if key == "" {
186 return nil, false
187 }
188
189 l.tree.Remove(key)
190 return value, true
191}
192
193// Slice returns a slice of values from startIndex (inclusive) to endIndex (exclusive).
194// Returns nil if the range is invalid.
195//
196// Example:
197//
198// l := list.New()
199// l.Append(1, 2, 3, 4, 5)
200//
201// println(l.Slice(1, 4)) // Output: [2 3 4]
202// println(l.Slice(-1, 2)) // Output: [1 2]
203// println(l.Slice(3, 999)) // Output: [4 5]
204// println(l.Slice(3, 2)) // Output: nil
205func (l *List) Slice(startIndex, endIndex int) []any {
206 size := l.tree.Size()
207
208 // Normalize bounds
209 if startIndex < 0 {
210 startIndex = 0
211 }
212 if endIndex > size {
213 endIndex = size
214 }
215 if startIndex >= endIndex {
216 return nil
217 }
218
219 count := endIndex - startIndex
220 result := make([]any, count)
221
222 i := 0
223 l.tree.IterateByOffset(startIndex, count, func(_ string, value any) bool {
224 result[i] = value
225 i++
226 return false
227 })
228 return result
229}
230
231// ForEach iterates through all elements in the list.
232func (l *List) ForEach(fn func(index int, value any) bool) {
233 if l.tree.Size() == 0 {
234 return
235 }
236
237 index := 0
238 l.tree.IterateByOffset(0, l.tree.Size(), func(_ string, value any) bool {
239 result := fn(index, value)
240 index++
241 return result
242 })
243}
244
245// Clone creates a shallow copy of the list.
246//
247// Example:
248//
249// l := list.New()
250// l.Append(1, 2, 3)
251//
252// clone := l.Clone()
253// clone.Set(0, 42)
254//
255// println(l.Get(0)) // Output: 1
256// println(clone.Get(0)) // Output: 42
257func (l *List) Clone() *List {
258 newList := &List{
259 tree: avl.Tree{},
260 idGen: l.idGen,
261 }
262
263 size := l.tree.Size()
264 if size == 0 {
265 return newList
266 }
267
268 l.tree.IterateByOffset(0, size, func(_ string, value any) bool {
269 newList.Append(value)
270 return false
271 })
272
273 return newList
274}
275
276// DeleteRange removes elements from startIndex (inclusive) to endIndex (exclusive).
277// Returns the number of elements deleted.
278//
279// Example:
280//
281// l := list.New()
282// l.Append(1, 2, 3, 4, 5)
283//
284// deleted := l.DeleteRange(1, 4)
285// println(deleted) // Output: 3
286// println(l.Range(0, l.Len())) // Output: [1 5]
287func (l *List) DeleteRange(startIndex, endIndex int) int {
288 size := l.tree.Size()
289
290 // Normalize bounds
291 if startIndex < 0 {
292 startIndex = 0
293 }
294 if endIndex > size {
295 endIndex = size
296 }
297 if startIndex >= endIndex {
298 return 0
299 }
300
301 // Collect keys to delete
302 keysToDelete := make([]string, 0, endIndex-startIndex)
303 l.tree.IterateByOffset(startIndex, endIndex-startIndex, func(key string, _ any) bool {
304 keysToDelete = append(keysToDelete, key)
305 return false
306 })
307
308 // Delete collected keys
309 for _, key := range keysToDelete {
310 l.tree.Remove(key)
311 }
312
313 return len(keysToDelete)
314}
