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