ulist.gno
10.68 Kb · 439 lines
1// Package ulist provides an append-only list implementation using a binary tree structure,
2// optimized for scenarios requiring sequential inserts with auto-incrementing indices.
3//
4// The implementation uses a binary tree where new elements are added by following a path
5// determined by the binary representation of the index. This provides automatic balancing
6// for append operations without requiring any balancing logic.
7//
8// Unlike the AVL tree-based list implementation (p/demo/avl/list), ulist is specifically
9// designed for append-only operations and does not require rebalancing. This makes it more
10// efficient for sequential inserts but less flexible for general-purpose list operations.
11//
12// Key differences from AVL list:
13// * Append-only design (no arbitrary inserts)
14// * No tree rebalancing needed
15// * Simpler implementation
16// * More memory efficient for sequential operations
17// * Less flexible than AVL (no arbitrary inserts/reordering)
18//
19// Key characteristics:
20// * O(log n) append and access operations
21// * Perfect balance for power-of-2 sizes
22// * No balancing needed
23// * Memory efficient
24// * Natural support for range queries
25// * Support for soft deletion of elements
26// * Forward and reverse iteration capabilities
27// * Offset-based iteration with count control
28package ulist
29
30// TODO: Make avl/pager compatible in some way. Explain the limitations (not always 10 items because of nil ones).
31// TODO: Use this ulist in moul/collection for the primary index.
32// TODO: Consider adding a "compact" method that removes nil nodes.
33// TODO: Benchmarks.
34
35import (
36 "errors"
37)
38
39// List represents an append-only binary tree list
40type List struct {
41 root *treeNode
42 totalSize int
43 activeSize int
44}
45
46// Entry represents a key-value pair in the list, where Index is the position
47// and Value is the stored data
48type Entry struct {
49 Index int
50 Value any
51}
52
53// treeNode represents a node in the binary tree
54type treeNode struct {
55 data any
56 left *treeNode
57 right *treeNode
58}
59
60// Error variables
61var (
62 ErrOutOfBounds = errors.New("index out of bounds")
63 ErrDeleted = errors.New("element already deleted")
64)
65
66// New creates a new empty List instance
67func New() *List {
68 return &List{}
69}
70
71// Append adds one or more values to the end of the list.
72// Values are added sequentially, and the list grows automatically.
73func (l *List) Append(values ...any) {
74 for _, value := range values {
75 index := l.totalSize
76 node := l.findNode(index, true)
77 node.data = value
78 l.totalSize++
79 l.activeSize++
80 }
81}
82
83// Get retrieves the value at the specified index.
84// Returns nil if the index is out of bounds or if the element was deleted.
85func (l *List) Get(index int) any {
86 node := l.findNode(index, false)
87 if node == nil {
88 return nil
89 }
90 return node.data
91}
92
93// Delete marks the elements at the specified indices as deleted.
94// Returns ErrOutOfBounds if any index is invalid or ErrDeleted if
95// the element was already deleted.
96func (l *List) Delete(indices ...int) error {
97 if len(indices) == 0 {
98 return nil
99 }
100 if l == nil || l.totalSize == 0 {
101 return ErrOutOfBounds
102 }
103
104 for _, index := range indices {
105 if index < 0 || index >= l.totalSize {
106 return ErrOutOfBounds
107 }
108
109 node := l.findNode(index, false)
110 if node == nil || node.data == nil {
111 return ErrDeleted
112 }
113 node.data = nil
114 l.activeSize--
115 }
116
117 return nil
118}
119
120// Set updates or restores a value at the specified index if within bounds
121// Returns ErrOutOfBounds if the index is invalid
122func (l *List) Set(index int, value any) error {
123 if l == nil || index < 0 || index >= l.totalSize {
124 return ErrOutOfBounds
125 }
126
127 node := l.findNode(index, false)
128 if node == nil {
129 return ErrOutOfBounds
130 }
131
132 // If this is restoring a deleted element
133 if value != nil && node.data == nil {
134 l.activeSize++
135 }
136
137 // If this is deleting an element
138 if value == nil && node.data != nil {
139 l.activeSize--
140 }
141
142 node.data = value
143 return nil
144}
145
146// Size returns the number of active (non-deleted) elements in the list
147func (l *List) Size() int {
148 if l == nil {
149 return 0
150 }
151 return l.activeSize
152}
153
154// TotalSize returns the total number of elements ever added to the list,
155// including deleted elements
156func (l *List) TotalSize() int {
157 if l == nil {
158 return 0
159 }
160 return l.totalSize
161}
162
163// IterCbFn is a callback function type used in iteration methods.
164// Return true to stop iteration, false to continue.
165type IterCbFn func(index int, value any) bool
166
167// Iterator performs iteration between start and end indices, calling cb for each entry.
168// If start > end, iteration is performed in reverse order.
169// Returns true if iteration was stopped early by the callback returning true.
170// Skips deleted elements.
171func (l *List) Iterator(start, end int, cb IterCbFn) bool {
172 // For empty list or invalid range
173 if l == nil || l.totalSize == 0 {
174 return false
175 }
176 if start < 0 && end < 0 {
177 return false
178 }
179 if start >= l.totalSize && end >= l.totalSize {
180 return false
181 }
182
183 // Normalize indices
184 if start < 0 {
185 start = 0
186 }
187 if end < 0 {
188 end = 0
189 }
190 if end >= l.totalSize {
191 end = l.totalSize - 1
192 }
193 if start >= l.totalSize {
194 start = l.totalSize - 1
195 }
196
197 // Handle reverse iteration
198 if start > end {
199 for i := start; i >= end; i-- {
200 val := l.Get(i)
201 if val != nil {
202 if cb(i, val) {
203 return true
204 }
205 }
206 }
207 return false
208 }
209
210 // Handle forward iteration
211 for i := start; i <= end; i++ {
212 val := l.Get(i)
213 if val != nil {
214 if cb(i, val) {
215 return true
216 }
217 }
218 }
219 return false
220}
221
222// IteratorByOffset performs iteration starting from offset for count elements.
223// If count is positive, iterates forward; if negative, iterates backward.
224// The iteration stops after abs(count) elements or when reaching list bounds.
225// Skips deleted elements.
226func (l *List) IteratorByOffset(offset int, count int, cb IterCbFn) bool {
227 if count == 0 || l == nil || l.totalSize == 0 {
228 return false
229 }
230
231 // Normalize offset
232 if offset < 0 {
233 offset = 0
234 }
235 if offset >= l.totalSize {
236 offset = l.totalSize - 1
237 }
238
239 // Determine end based on count direction
240 var end int
241 if count > 0 {
242 end = l.totalSize - 1
243 } else {
244 end = 0
245 }
246
247 wrapperReturned := false
248
249 // Wrap the callback to limit iterations
250 remaining := abs(count)
251 wrapper := func(index int, value any) bool {
252 if remaining <= 0 {
253 wrapperReturned = true
254 return true
255 }
256 remaining--
257 return cb(index, value)
258 }
259 ret := l.Iterator(offset, end, wrapper)
260 if wrapperReturned {
261 return false
262 }
263 return ret
264}
265
266// abs returns the absolute value of x
267func abs(x int) int {
268 if x < 0 {
269 return -x
270 }
271 return x
272}
273
274// findNode locates or creates a node at the given index in the binary tree.
275// The tree is structured such that the path to a node is determined by the binary
276// representation of the index. For example, a tree with 15 elements would look like:
277//
278// 0
279// / \
280// 1 2
281// / \ / \
282// 3 4 5 6
283// / \ / \ / \ / \
284// 7 8 9 10 11 12 13 14
285//
286// To find index 13 (binary 1101):
287// 1. Start at root (0)
288// 2. Calculate bits needed (4 bits for index 13)
289// 3. Skip the highest bit position and start from bits-2
290// 4. Read bits from left to right:
291// - 1 -> go right to 2
292// - 1 -> go right to 6
293// - 0 -> go left to 13
294//
295// Special cases:
296// - Index 0 always returns the root node
297// - For create=true, missing nodes are created along the path
298// - For create=false, returns nil if any node is missing
299func (l *List) findNode(index int, create bool) *treeNode {
300 // For read operations, check bounds strictly
301 if !create && (l == nil || index < 0 || index >= l.totalSize) {
302 return nil
303 }
304
305 // For create operations, allow index == totalSize for append
306 if create && (l == nil || index < 0 || index > l.totalSize) {
307 return nil
308 }
309
310 // Initialize root if needed
311 if l.root == nil {
312 if !create {
313 return nil
314 }
315 l.root = &treeNode{}
316 return l.root
317 }
318
319 node := l.root
320
321 // Special case for root node
322 if index == 0 {
323 return node
324 }
325
326 // Calculate the number of bits needed (inline highestBit logic)
327 bits := 0
328 n := index + 1
329 for n > 0 {
330 n >>= 1
331 bits++
332 }
333
334 // Start from the second highest bit
335 for level := bits - 2; level >= 0; level-- {
336 bit := (index & (1 << uint(level))) != 0
337
338 if bit {
339 if node.right == nil {
340 if !create {
341 return nil
342 }
343 node.right = &treeNode{}
344 }
345 node = node.right
346 } else {
347 if node.left == nil {
348 if !create {
349 return nil
350 }
351 node.left = &treeNode{}
352 }
353 node = node.left
354 }
355 }
356
357 return node
358}
359
360// MustDelete deletes elements at the specified indices.
361// Panics if any index is invalid or if any element was already deleted.
362func (l *List) MustDelete(indices ...int) {
363 if err := l.Delete(indices...); err != nil {
364 panic(err)
365 }
366}
367
368// MustGet retrieves the value at the specified index.
369// Panics if the index is out of bounds or if the element was deleted.
370func (l *List) MustGet(index int) any {
371 if l == nil || index < 0 || index >= l.totalSize {
372 panic(ErrOutOfBounds)
373 }
374 value := l.Get(index)
375 if value == nil {
376 panic(ErrDeleted)
377 }
378 return value
379}
380
381// MustSet updates or restores a value at the specified index.
382// Panics if the index is out of bounds.
383func (l *List) MustSet(index int, value any) {
384 if err := l.Set(index, value); err != nil {
385 panic(err)
386 }
387}
388
389// GetRange returns a slice of Entry containing elements between start and end indices.
390// If start > end, elements are returned in reverse order.
391// Deleted elements are skipped.
392func (l *List) GetRange(start, end int) []Entry {
393 var entries []Entry
394 l.Iterator(start, end, func(index int, value any) bool {
395 entries = append(entries, Entry{Index: index, Value: value})
396 return false
397 })
398 return entries
399}
400
401// GetByOffset returns a slice of Entry starting from offset for count elements.
402// If count is positive, returns elements forward; if negative, returns elements backward.
403// The operation stops after abs(count) elements or when reaching list bounds.
404// Deleted elements are skipped.
405func (l *List) GetByOffset(offset int, count int) []Entry {
406 var entries []Entry
407 l.IteratorByOffset(offset, count, func(index int, value any) bool {
408 entries = append(entries, Entry{Index: index, Value: value})
409 return false
410 })
411 return entries
412}
413
414// IList defines the interface for an ulist.List compatible structure.
415type IList interface {
416 // Basic operations
417 Append(values ...any)
418 Get(index int) any
419 Delete(indices ...int) error
420 Size() int
421 TotalSize() int
422 Set(index int, value any) error
423
424 // Must variants that panic instead of returning errors
425 MustDelete(indices ...int)
426 MustGet(index int) any
427 MustSet(index int, value any)
428
429 // Range operations
430 GetRange(start, end int) []Entry
431 GetByOffset(offset int, count int) []Entry
432
433 // Iterator operations
434 Iterator(start, end int, cb IterCbFn) bool
435 IteratorByOffset(offset int, count int, cb IterCbFn) bool
436}
437
438// Verify that List implements IList
439var _ IList = (*List)(nil)
