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 maintaining3// 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 elements11// var l list.List12// l.Append(1, 2, 3)13//14// // Get and set elements15// value, _ := l.Get(1) // returns 216// l.Set(1, 42) // updates index 1 to 4217//18// // Delete elements19// l.Delete(0) // removes first element20//21// // Iterate over elements22// l.ForEach(func(index int, value any) bool {23// ufmt.Printf("index %d: %v\n", index, value)24// return false // continue iteration25// })26// // Output:27// // index 0: 4228// // index 1: 329//30// // Create a list using a variable declaration31// var l2 list.List32// l2.Append(4, 5, 6)33// println(l2.Len()) // Output: 334package list3536import (37 "gno.land/p/nt/bptree/rotree/v0"38 "gno.land/p/nt/bptree/v0"39 "gno.land/p/nt/seqid/v0"40)4142// IList defines the interface for list operations43type IList interface {44 Len() int45 Append(values ...any)46 Get(index int) (any, bool)47 Set(index int, value any) bool48 Delete(index int) (any, bool)49 Slice(startIndex, endIndex int) []any50 ForEach(fn func(index int, value any) bool)51 Clone() *List52 DeleteRange(startIndex, endIndex int) int53}5455// Verify List implements IList interface56var _ IList = (*List)(nil)5758// List represents an ordered sequence of items backed by a B+ tree59type List struct {60 tree bptree.BPTree61 idGen seqid.ID62}6364// Len returns the number of elements in the list.65func (l *List) Len() int {66 return l.tree.Size()67}6869// 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}7576// 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, false81 }82 _, value := l.tree.GetByIndex(index)83 return value, true84}8586// 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()9192 // Handle empty list case - only allow index 093 if size == 0 {94 if index == 0 {95 l.Append(value)96 return true97 }98 return false99 }100101 if index < 0 || index > size {102 return false103 }104105 // If setting at the end (append case)106 if index == size {107 l.Append(value)108 return true109 }110111 // Get the key at the specified index112 key, _ := l.tree.GetByIndex(index)113 if key == "" {114 return false115 }116117 // Update the value at the existing key118 l.tree.Set(key, value)119 return true120}121122// 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 list127 if size == 0 {128 return nil, false129 }130131 if index < 0 || index >= size {132 return nil, false133 }134135 key, value := l.tree.GetByIndex(index)136 if key == "" {137 return nil, false138 }139140 l.tree.Remove(key)141 return value, true142}143144// 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()148149 // Normalize bounds150 if startIndex < 0 {151 startIndex = 0152 }153 if endIndex > size {154 endIndex = size155 }156 if startIndex >= endIndex {157 return nil158 }159160 count := endIndex - startIndex161 result := make([]any, count)162163 i := 0164 l.tree.IterateByOffset(startIndex, count, func(_ string, value any) bool {165 result[i] = value166 i++167 return false168 })169 return result170}171172// 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 return176 }177178 index := 0179 l.tree.IterateByOffset(0, l.tree.Size(), func(_ string, value any) bool {180 result := fn(index, value)181 index++182 return result183 })184}185186// 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 }192193 size := l.tree.Size()194 if size == 0 {195 return newList196 }197198 l.tree.IterateByOffset(0, size, func(_ string, value any) bool {199 newList.Append(value)200 return false201 })202203 return newList204}205206// 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()210211 // Normalize bounds212 if startIndex < 0 {213 startIndex = 0214 }215 if endIndex > size {216 endIndex = size217 }218 if startIndex >= endIndex {219 return 0220 }221222 // Collect keys to delete223 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 false227 })228229 // Delete collected keys230 for _, key := range keysToDelete {231 l.tree.Remove(key)232 }233234 return len(keysToDelete)235}236237// 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}241Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.