var ErrOutOfBounds, ErrDeleted
Error variables
ulist source pure
Package ulist provides an append-only list implementation using a binary tree structure, optimized for scenarios requ...
Package ulist provides an append-only list implementation using a binary tree structure, optimized for scenarios requiring sequential inserts with auto-incrementing indices.
The implementation uses a binary tree where new elements are added by following a path determined by the binary representation of the index. This provides automatic balancing for append operations without requiring any balancing logic.
Unlike the AVL tree-based list implementation (p/demo/avl/list), ulist is specifically designed for append-only operations and does not require rebalancing. This makes it more efficient for sequential inserts but less flexible for general-purpose list operations.
Key differences from AVL list: * Append-only design (no arbitrary inserts) * No tree rebalancing needed * Simpler implementation * More memory efficient for sequential operations * Less flexible than AVL (no arbitrary inserts/reordering)
Key characteristics: * O(log n) append and access operations * Perfect balance for power-of-2 sizes * No balancing needed * Memory efficient * Natural support for range queries * Support for soft deletion of elements * Forward and reverse iteration capabilities * Offset-based iteration with count control
1
1
4
type Entry
structEntry represents a key-value pair in the list, where Index is the position and Value is the stored data
type IList
interface 1type IList interface {
2 // Basic operations
3 Append(values ...any)
4 Get(index int) any
5 Delete(indices ...int) error
6 Size() int
7 TotalSize() int
8 Set(index int, value any) error
9
10 // Must variants that panic instead of returning errors
11 MustDelete(indices ...int)
12 MustGet(index int) any
13 MustSet(index int, value any)
14
15 // Range operations
16 GetRange(start, end int) []Entry
17 GetByOffset(offset int, count int) []Entry
18
19 // Iterator operations
20 Iterator(start, end int, cb IterCbFn) bool
21 IteratorByOffset(offset int, count int, cb IterCbFn) bool
22}IList defines the interface for an ulist.List compatible structure.
type IterCbFn
funcIterCbFn is a callback function type used in iteration methods. Return true to stop iteration, false to continue.
type List
structList represents an append-only binary tree list
Methods on List
func Append
method on ListAppend adds one or more values to the end of the list. Values are added sequentially, and the list grows automatically.
func Delete
method on ListDelete marks the elements at the specified indices as deleted. Returns ErrOutOfBounds if any index is invalid or ErrDeleted if the element was already deleted.
func Get
method on ListGet retrieves the value at the specified index. Returns nil if the index is out of bounds or if the element was deleted.
func GetByOffset
method on ListGetByOffset returns a slice of Entry starting from offset for count elements. If count is positive, returns elements forward; if negative, returns elements backward. The operation stops after abs(count) elements or when reaching list bounds. Deleted elements are skipped.
func GetRange
method on ListGetRange returns a slice of Entry containing elements between start and end indices. If start > end, elements are returned in reverse order. Deleted elements are skipped.
func Iterator
method on ListIterator performs iteration between start and end indices, calling cb for each entry. If start > end, iteration is performed in reverse order. Returns true if iteration was stopped early by the callback returning true. Skips deleted elements.
func IteratorByOffset
method on ListIteratorByOffset performs iteration starting from offset for count elements. If count is positive, iterates forward; if negative, iterates backward. The iteration stops after abs(count) elements or when reaching list bounds. Skips deleted elements.
func MustDelete
method on ListMustDelete deletes elements at the specified indices. Panics if any index is invalid or if any element was already deleted.
func MustGet
method on ListMustGet retrieves the value at the specified index. Panics if the index is out of bounds or if the element was deleted.
func MustSet
method on ListMustSet updates or restores a value at the specified index. Panics if the index is out of bounds.
func Set
method on ListSet updates or restores a value at the specified index if within bounds Returns ErrOutOfBounds if the index is invalid
func Size
method on ListSize returns the number of active (non-deleted) elements in the list
func TotalSize
method on ListTotalSize returns the total number of elements ever added to the list, including deleted elements
1
- errors stdlib
