1// SPDX-License-Identifier: ISC 2// Copyright (c) 2014-2020 Bitmark Inc. 3// Use of this source code is governed by an ISC 4// license that can be found in the LICENSE file. 5 6package avl 7 8// First - return the node with the lowest key value 9func (tree *Tree) First() *Node { 10 return tree.root.first() 11} 12 13// internal: lowest node in a sub-tree 14func (tree *Node) first() *Node { 15 if nil == tree { 16 return nil 17 } 18 for nil != tree.left { 19 tree = tree.left 20 } 21 return tree 22} 23 24// Last - return the node with the highest key value 25func (tree *Tree) Last() *Node { 26 return tree.root.last() 27} 28 29// internal: highest node in a sub-tree 30func (tree *Node) last() *Node { 31 if nil == tree { 32 return nil 33 } 34 for nil != tree.right { 35 tree = tree.right 36 } 37 return tree 38} 39 40// Next - given a node, return the node with the next highest key 41// value or nil if no more nodes. 42func (tree *Node) Next() *Node { 43 if nil == tree.right { 44 key := tree.key 45 for { 46 tree = tree.up 47 if nil == tree { 48 return nil 49 } 50 if 1 == tree.key.Compare(key) { // tree.key > key 51 return tree 52 } 53 } 54 } 55 return tree.right.first() 56} 57 58// Prev - given a node, return the node with the lowest key value or 59// nil if no more nodes 60func (tree *Node) Prev() *Node { 61 if nil == tree.left { 62 key := tree.key 63 for { 64 tree = tree.up 65 if nil == tree { 66 return nil 67 } 68 if -1 == tree.key.Compare(key) { // tree.key < key 69 return tree 70 } 71 } 72 } 73 return tree.left.last() 74} 75