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 path5// determined by the binary representation of the index. This provides automatic balancing6// for append operations without requiring any balancing logic.7//8// Unlike the AVL tree-based list implementation (p/demo/avl/list), ulist is specifically9// designed for append-only operations and does not require rebalancing. This makes it more10// 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 needed15// * Simpler implementation16// * More memory efficient for sequential operations17// * Less flexible than AVL (no arbitrary inserts/reordering)18//19// Key characteristics:20// * O(log n) append and access operations21// * Perfect balance for power-of-2 sizes22// * No balancing needed23// * Memory efficient24// * Natural support for range queries25// * Support for soft deletion of elements26// * Forward and reverse iteration capabilities27// * Offset-based iteration with count control28package ulist2930// 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.3435import (36 "errors"37)3839// List represents an append-only binary tree list40type List struct {41 root *treeNode42 totalSize int43 activeSize int44}4546// Entry represents a key-value pair in the list, where Index is the position47// and Value is the stored data48type Entry struct {49 Index int50 Value any51}5253// treeNode represents a node in the binary tree54type treeNode struct {55 data any56 left *treeNode57 right *treeNode58}5960// Error variables61var (62 ErrOutOfBounds = errors.New("index out of bounds")63 ErrDeleted = errors.New("element already deleted")64)6566// New creates a new empty List instance67func New() *List {68 return &List{}69}7071// 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.totalSize76 node := l.findNode(index, true)77 node.data = value78 l.totalSize++79 l.activeSize++80 }81}8283// 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 nil89 }90 return node.data91}9293// Delete marks the elements at the specified indices as deleted.94// Returns ErrOutOfBounds if any index is invalid or ErrDeleted if95// the element was already deleted.96func (l *List) Delete(indices ...int) error {97 if len(indices) == 0 {98 return nil99 }100 if l == nil || l.totalSize == 0 {101 return ErrOutOfBounds102 }103104 for _, index := range indices {105 if index < 0 || index >= l.totalSize {106 return ErrOutOfBounds107 }108109 node := l.findNode(index, false)110 if node == nil || node.data == nil {111 return ErrDeleted112 }113 node.data = nil114 l.activeSize--115 }116117 return nil118}119120// Set updates or restores a value at the specified index if within bounds121// Returns ErrOutOfBounds if the index is invalid122func (l *List) Set(index int, value any) error {123 if l == nil || index < 0 || index >= l.totalSize {124 return ErrOutOfBounds125 }126127 node := l.findNode(index, false)128 if node == nil {129 return ErrOutOfBounds130 }131132 // If this is restoring a deleted element133 if value != nil && node.data == nil {134 l.activeSize++135 }136137 // If this is deleting an element138 if value == nil && node.data != nil {139 l.activeSize--140 }141142 node.data = value143 return nil144}145146// Size returns the number of active (non-deleted) elements in the list147func (l *List) Size() int {148 if l == nil {149 return 0150 }151 return l.activeSize152}153154// TotalSize returns the total number of elements ever added to the list,155// including deleted elements156func (l *List) TotalSize() int {157 if l == nil {158 return 0159 }160 return l.totalSize161}162163// 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) bool166167// 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 range173 if l == nil || l.totalSize == 0 {174 return false175 }176 if start < 0 && end < 0 {177 return false178 }179 if start >= l.totalSize && end >= l.totalSize {180 return false181 }182183 // Normalize indices184 if start < 0 {185 start = 0186 }187 if end < 0 {188 end = 0189 }190 if end >= l.totalSize {191 end = l.totalSize - 1192 }193 if start >= l.totalSize {194 start = l.totalSize - 1195 }196197 // Handle reverse iteration198 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 true204 }205 }206 }207 return false208 }209210 // Handle forward iteration211 for i := start; i <= end; i++ {212 val := l.Get(i)213 if val != nil {214 if cb(i, val) {215 return true216 }217 }218 }219 return false220}221222// 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 false229 }230231 // Normalize offset232 if offset < 0 {233 offset = 0234 }235 if offset >= l.totalSize {236 offset = l.totalSize - 1237 }238239 // Determine end based on count direction240 var end int241 if count > 0 {242 end = l.totalSize - 1243 } else {244 end = 0245 }246247 wrapperReturned := false248249 // Wrap the callback to limit iterations250 remaining := abs(count)251 wrapper := func(index int, value any) bool {252 if remaining <= 0 {253 wrapperReturned = true254 return true255 }256 remaining--257 return cb(index, value)258 }259 ret := l.Iterator(offset, end, wrapper)260 if wrapperReturned {261 return false262 }263 return ret264}265266// abs returns the absolute value of x267func abs(x int) int {268 if x < 0 {269 return -x270 }271 return x272}273274// 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 binary276// representation of the index. For example, a tree with 15 elements would look like:277//278// 0279// / \280// 1 2281// / \ / \282// 3 4 5 6283// / \ / \ / \ / \284// 7 8 9 10 11 12 13 14285//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-2290// 4. Read bits from left to right:291// - 1 -> go right to 2292// - 1 -> go right to 6293// - 0 -> go left to 13294//295// Special cases:296// - Index 0 always returns the root node297// - For create=true, missing nodes are created along the path298// - For create=false, returns nil if any node is missing299func (l *List) findNode(index int, create bool) *treeNode {300 // For read operations, check bounds strictly301 if !create && (l == nil || index < 0 || index >= l.totalSize) {302 return nil303 }304305 // For create operations, allow index == totalSize for append306 if create && (l == nil || index < 0 || index > l.totalSize) {307 return nil308 }309310 // Initialize root if needed311 if l.root == nil {312 if !create {313 return nil314 }315 l.root = &treeNode{}316 return l.root317 }318319 node := l.root320321 // Special case for root node322 if index == 0 {323 return node324 }325326 // Calculate the number of bits needed (inline highestBit logic)327 bits := 0328 n := index + 1329 for n > 0 {330 n >>= 1331 bits++332 }333334 // Start from the second highest bit335 for level := bits - 2; level >= 0; level-- {336 bit := (index & (1 << uint(level))) != 0337338 if bit {339 if node.right == nil {340 if !create {341 return nil342 }343 node.right = &treeNode{}344 }345 node = node.right346 } else {347 if node.left == nil {348 if !create {349 return nil350 }351 node.left = &treeNode{}352 }353 node = node.left354 }355 }356357 return node358}359360// 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}367368// 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 value379}380381// 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}388389// 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 []Entry394 l.Iterator(start, end, func(index int, value any) bool {395 entries = append(entries, Entry{Index: index, Value: value})396 return false397 })398 return entries399}400401// 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 []Entry407 l.IteratorByOffset(offset, count, func(index int, value any) bool {408 entries = append(entries, Entry{Index: index, Value: value})409 return false410 })411 return entries412}413414// IList defines the interface for an ulist.List compatible structure.415type IList interface {416 // Basic operations417 Append(values ...any)418 Get(index int) any419 Delete(indices ...int) error420 Size() int421 TotalSize() int422 Set(index int, value any) error423424 // Must variants that panic instead of returning errors425 MustDelete(indices ...int)426 MustGet(index int) any427 MustSet(index int, value any)428429 // Range operations430 GetRange(start, end int) []Entry431 GetByOffset(offset int, count int) []Entry432433 // Iterator operations434 Iterator(start, end int, cb IterCbFn) bool435 IteratorByOffset(offset int, count int, cb IterCbFn) bool436}437438// Verify that List implements IList439var _ IList = (*List)(nil)440Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.