1package avl23type Node struct {4 key string // key is the unique identifier for the node.5 value any // value is the data stored in the node.6 height int8 // height is the height of the node in the tree.7 size int // size is the number of leaf nodes (key-value pairs) in the subtree rooted at this node.8 leftNode *Node // leftNode is the left child of the node.9 rightNode *Node // rightNode is the right child of the node.10}1112func NewNode(key string, value any) *Node {13 return &Node{14 key: key,15 value: value,16 height: 0,17 size: 1,18 }19}2021func (node *Node) Size() int {22 if node == nil {23 return 024 }25 return node.size26}2728func (node *Node) IsLeaf() bool {29 return node.height == 030}3132func (node *Node) Key() string {33 return node.key34}3536func (node *Node) Value() any {37 return node.value38}3940func (node *Node) _copy() *Node {41 if node.height == 0 {42 panic("Why are you copying a value node?")43 }44 return &Node{45 key: node.key,46 height: node.height,47 size: node.size,48 leftNode: node.leftNode,49 rightNode: node.rightNode,50 }51}5253func (node *Node) Has(key string) (has bool) {54 if node == nil {55 return false56 }57 if node.key == key {58 return true59 }60 if node.height == 0 {61 return false62 } else {63 if key < node.key {64 return node.getLeftNode().Has(key)65 } else {66 return node.getRightNode().Has(key)67 }68 }69}7071func (node *Node) Get(key string) (index int, value any, exists bool) {72 if node == nil {73 return 0, nil, false74 }7576 if node.height == 0 {77 if node.key == key {78 return 0, node.value, true79 } else if node.key < key {80 return 1, nil, false81 } else {82 return 0, nil, false83 }84 } else {85 if key < node.key {86 return node.getLeftNode().Get(key)87 } else {88 rightNode := node.getRightNode()89 index, value, exists = rightNode.Get(key)90 index += node.size - rightNode.size91 return index, value, exists92 }93 }94}9596func (node *Node) GetByIndex(index int) (key string, value any) {97 if index < 0 {98 panic("GetByIndex: negative index not allowed")99 }100101 if node.height == 0 {102 if index != 0 {103 panic("GetByIndex asked for invalid index")104 }105 return node.key, node.value106 } else {107 leftNode := node.getLeftNode()108 if index < leftNode.size {109 return leftNode.GetByIndex(index)110 } else {111 return node.getRightNode().GetByIndex(index - leftNode.size)112 }113 }114}115116func (node *Node) Set(key string, value any) (newSelf *Node, updated bool) {117 if node == nil {118 return NewNode(key, value), false119 }120 if node.height == 0 {121 if key < node.key {122 return &Node{123 key: node.key,124 height: 1,125 size: 2,126 leftNode: NewNode(key, value),127 rightNode: node,128 }, false129 } else if key == node.key {130 return NewNode(key, value), true131 } else {132 return &Node{133 key: key,134 height: 1,135 size: 2,136 leftNode: node,137 rightNode: NewNode(key, value),138 }, false139 }140 } else {141 node = node._copy()142 if key < node.key {143 node.leftNode, updated = node.getLeftNode().Set(key, value)144 } else {145 node.rightNode, updated = node.getRightNode().Set(key, value)146 }147 if updated {148 return node, updated149 } else {150 node.calcHeightAndSize()151 return node.balance(), updated152 }153 }154}155156func (node *Node) Remove(key string) (157 newNode *Node, newKey string, value any, removed bool,158) {159 if node == nil {160 return nil, "", nil, false161 }162 if node.height == 0 {163 if key == node.key {164 return nil, "", node.value, true165 } else {166 return node, "", nil, false167 }168 } else {169 if key < node.key {170 var newLeftNode *Node171 newLeftNode, newKey, value, removed = node.getLeftNode().Remove(key)172 if !removed {173 return node, "", value, false174 } else if newLeftNode == nil { // left node held value, was removed175 return node.rightNode, node.key, value, true176 }177 node = node._copy()178 node.leftNode = newLeftNode179 node.calcHeightAndSize()180 node = node.balance()181 return node, newKey, value, true182 } else {183 var newRightNode *Node184 newRightNode, newKey, value, removed = node.getRightNode().Remove(key)185 if !removed {186 return node, "", value, false187 } else if newRightNode == nil { // right node held value, was removed188 return node.leftNode, "", value, true189 }190 node = node._copy()191 node.rightNode = newRightNode192 if newKey != "" {193 node.key = newKey194 }195 node.calcHeightAndSize()196 node = node.balance()197 return node, "", value, true198 }199 }200}201202func (node *Node) getLeftNode() *Node {203 return node.leftNode204}205206func (node *Node) getRightNode() *Node {207 return node.rightNode208}209210func (node *Node) rotateRight() *Node {211 node = node._copy()212 l := node.getLeftNode()213 _l := l._copy()214215 _lrCached := _l.rightNode216 _l.rightNode = node217 node.leftNode = _lrCached218219 node.calcHeightAndSize()220 _l.calcHeightAndSize()221222 return _l223}224225func (node *Node) rotateLeft() *Node {226 node = node._copy()227 r := node.getRightNode()228 _r := r._copy()229230 _rlCached := _r.leftNode231 _r.leftNode = node232 node.rightNode = _rlCached233234 node.calcHeightAndSize()235 _r.calcHeightAndSize()236237 return _r238}239240func (node *Node) calcHeightAndSize() {241 node.height = maxInt8(node.getLeftNode().height, node.getRightNode().height) + 1242 node.size = node.getLeftNode().size + node.getRightNode().size243}244245func (node *Node) calcBalance() int {246 return int(node.getLeftNode().height) - int(node.getRightNode().height)247}248249func (node *Node) balance() (newSelf *Node) {250 balance := node.calcBalance()251 if balance > 1 {252 if node.getLeftNode().calcBalance() >= 0 {253 return node.rotateRight()254 } else {255 left := node.getLeftNode()256 node.leftNode = left.rotateLeft()257 return node.rotateRight()258 }259 }260 if balance < -1 {261 if node.getRightNode().calcBalance() <= 0 {262 return node.rotateLeft()263 } else {264 right := node.getRightNode()265 node.rightNode = right.rotateRight()266 return node.rotateLeft()267 }268 }269 return node270}271272func (node *Node) Iterate(start, end string, cb func(*Node) bool) bool {273 return node.TraverseInRange(start, end, true, true, cb)274}275276func (node *Node) ReverseIterate(start, end string, cb func(*Node) bool) bool {277 return node.TraverseInRange(start, end, false, true, cb)278}279280func (node *Node) TraverseInRange(start, end string, ascending bool, leavesOnly bool, cb func(*Node) bool) bool {281 if node == nil {282 return false283 }284 afterStart := (start == "" || start < node.key)285 startOrAfter := (start == "" || start <= node.key)286 beforeEnd := false287 if ascending {288 beforeEnd = (end == "" || node.key < end)289 } else {290 beforeEnd = (end == "" || node.key <= end)291 }292293 stop := false294 if (!node.IsLeaf() && !leavesOnly) ||295 (node.IsLeaf() && startOrAfter && beforeEnd) {296 stop = cb(node)297 if stop {298 return stop299 }300 }301 if node.IsLeaf() {302 return stop303 }304305 if ascending {306 if afterStart {307 stop = node.getLeftNode().TraverseInRange(start, end, ascending, leavesOnly, cb)308 }309 if stop {310 return stop311 }312 if beforeEnd {313 stop = node.getRightNode().TraverseInRange(start, end, ascending, leavesOnly, cb)314 }315 } else {316 if beforeEnd {317 stop = node.getRightNode().TraverseInRange(start, end, ascending, leavesOnly, cb)318 }319 if stop {320 return stop321 }322 if afterStart {323 stop = node.getLeftNode().TraverseInRange(start, end, ascending, leavesOnly, cb)324 }325 }326327 return stop328}329330func (node *Node) TraverseByOffset(offset, limit int, ascending bool, leavesOnly bool, cb func(*Node) bool) bool {331 if node == nil {332 return false333 }334335 if offset < 0 {336 offset = 0337 }338339 if limit <= 0 || offset >= node.size {340 return false341 }342 if node.IsLeaf() {343 if offset > 0 {344 return false345 }346 return cb(node)347 }348349 return node.traverseByOffset(offset, limit, ascending, leavesOnly, cb)350}351352func (node *Node) traverseByOffset(offset, limit int, ascending bool, leavesOnly bool, cb func(*Node) bool) bool {353 if !leavesOnly {354 if cb(node) {355 return true // Stop traversal if callback returns true356 }357 }358 first, second := node.getLeftNode(), node.getRightNode()359 if !ascending {360 first, second = second, first361 }362 if first.IsLeaf() {363 if offset > 0 {364 offset--365 } else {366 if cb(first) {367 return true // Stop traversal if callback returns true368 }369 limit--370 if limit <= 0 {371 return true // Stop traversal when limit is reached372 }373 }374 } else {375 if offset >= first.size {376 offset -= first.size // 1377 } else {378 if first.traverseByOffset(offset, limit, ascending, leavesOnly, cb) {379 return true380 }381 delta := first.size - offset382 offset = 0383 if delta >= limit {384 return true // 3385 }386 limit -= delta // 2387 }388 }389390 if second.IsLeaf() {391 return cb(second)392 }393 return second.traverseByOffset(offset, limit, ascending, leavesOnly, cb)394}395396func (node *Node) lmd() *Node {397 if node.height == 0 {398 return node399 }400 return node.getLeftNode().lmd()401}402403func (node *Node) rmd() *Node {404 if node.height == 0 {405 return node406 }407 return node.getRightNode().rmd()408}409410func maxInt8(a, b int8) int8 {411 if a > b {412 return a413 }414 return b415}416Signatures reconstructed verbatim from vm/qfuncs — interface params keep their inline definitions.