ulist.gno

  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)