list.gno
5.32 Kb · 240 lines
1// Package list implements a dynamic list data structure backed by a B+ 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 using a variable declaration
31// var l2 list.List
32// l2.Append(4, 5, 6)
33// println(l2.Len()) // Output: 3
34package list
35
36import (
37 "gno.land/p/nt/bptree/v0"
38 "gno.land/p/nt/bptree/v0/rotree"
39 "gno.land/p/nt/seqid/v0"
40)
41
42// IList defines the interface for list operations
43type IList interface {
44 Len() int
45 Append(values ...any)
46 Get(index int) (any, bool)
47 Set(index int, value any) bool
48 Delete(index int) (any, bool)
49 Slice(startIndex, endIndex int) []any
50 ForEach(fn func(index int, value any) bool)
51 Clone() *List
52 DeleteRange(startIndex, endIndex int) int
53}
54
55// Verify List implements IList interface
56var _ IList = (*List)(nil)
57
58// List represents an ordered sequence of items backed by a B+ tree
59type List struct {
60 tree bptree.BPTree
61 idGen seqid.ID
62}
63
64// Len returns the number of elements in the list.
65func (l *List) Len() int {
66 return l.tree.Size()
67}
68
69// Append adds one or more values to the end of the list.
70func (l *List) Append(values ...any) {
71 for _, v := range values {
72 l.tree.Set(l.idGen.Next().String(), v)
73 }
74}
75
76// Get returns the value at the specified index and true if the index is valid.
77// Returns (nil, false) if index is out of bounds.
78func (l *List) Get(index int) (any, bool) {
79 if index < 0 || index >= l.tree.Size() {
80 return nil, false
81 }
82 _, value := l.tree.GetByIndex(index)
83 return value, true
84}
85
86// Set updates or appends a value at the specified index.
87// Returns true if the operation was successful, false otherwise.
88// For empty lists, only index 0 is valid (append case).
89func (l *List) Set(index int, value any) bool {
90 size := l.tree.Size()
91
92 // Handle empty list case - only allow index 0
93 if size == 0 {
94 if index == 0 {
95 l.Append(value)
96 return true
97 }
98 return false
99 }
100
101 if index < 0 || index > size {
102 return false
103 }
104
105 // If setting at the end (append case)
106 if index == size {
107 l.Append(value)
108 return true
109 }
110
111 // Get the key at the specified index
112 key, _ := l.tree.GetByIndex(index)
113 if key == "" {
114 return false
115 }
116
117 // Update the value at the existing key
118 l.tree.Set(key, value)
119 return true
120}
121
122// Delete removes the element at the specified index.
123// Returns the deleted value and true if successful, nil and false otherwise.
124func (l *List) Delete(index int) (any, bool) {
125 size := l.tree.Size()
126 // Always return nil, false for empty list
127 if size == 0 {
128 return nil, false
129 }
130
131 if index < 0 || index >= size {
132 return nil, false
133 }
134
135 key, value := l.tree.GetByIndex(index)
136 if key == "" {
137 return nil, false
138 }
139
140 l.tree.Remove(key)
141 return value, true
142}
143
144// Slice returns a slice of values from startIndex (inclusive) to endIndex (exclusive).
145// Returns nil if the range is invalid.
146func (l *List) Slice(startIndex, endIndex int) []any {
147 size := l.tree.Size()
148
149 // Normalize bounds
150 if startIndex < 0 {
151 startIndex = 0
152 }
153 if endIndex > size {
154 endIndex = size
155 }
156 if startIndex >= endIndex {
157 return nil
158 }
159
160 count := endIndex - startIndex
161 result := make([]any, count)
162
163 i := 0
164 l.tree.IterateByOffset(startIndex, count, func(_ string, value any) bool {
165 result[i] = value
166 i++
167 return false
168 })
169 return result
170}
171
172// ForEach iterates through all elements in the list.
173func (l *List) ForEach(fn func(index int, value any) bool) {
174 if l.tree.Size() == 0 {
175 return
176 }
177
178 index := 0
179 l.tree.IterateByOffset(0, l.tree.Size(), func(_ string, value any) bool {
180 result := fn(index, value)
181 index++
182 return result
183 })
184}
185
186// Clone creates a shallow copy of the list.
187func (l *List) Clone() *List {
188 newList := &List{
189 tree: bptree.BPTree{},
190 idGen: l.idGen,
191 }
192
193 size := l.tree.Size()
194 if size == 0 {
195 return newList
196 }
197
198 l.tree.IterateByOffset(0, size, func(_ string, value any) bool {
199 newList.Append(value)
200 return false
201 })
202
203 return newList
204}
205
206// DeleteRange removes elements from startIndex (inclusive) to endIndex (exclusive).
207// Returns the number of elements deleted.
208func (l *List) DeleteRange(startIndex, endIndex int) int {
209 size := l.tree.Size()
210
211 // Normalize bounds
212 if startIndex < 0 {
213 startIndex = 0
214 }
215 if endIndex > size {
216 endIndex = size
217 }
218 if startIndex >= endIndex {
219 return 0
220 }
221
222 // Collect keys to delete
223 keysToDelete := make([]string, 0, endIndex-startIndex)
224 l.tree.IterateByOffset(startIndex, endIndex-startIndex, func(key string, _ any) bool {
225 keysToDelete = append(keysToDelete, key)
226 return false
227 })
228
229 // Delete collected keys
230 for _, key := range keysToDelete {
231 l.tree.Remove(key)
232 }
233
234 return len(keysToDelete)
235}
236
237// Tree returns a read-only pointer to the underlying B+ tree.
238func (l *List) Tree() *rotree.ReadOnlyTree {
239 return rotree.Wrap(&l.tree, nil)
240}