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
8import (
9	"fmt"
10)
11
12// CheckUp - check the up pointers for consistency
13func (tree *Tree) CheckUp() bool {
14	return checkUp(tree.root, nil)
15}
16
17// internal: consistency checker
18func checkUp(p *Node, up *Node) bool {
19	if nil == p {
20		return true
21	}
22	if p.up != up {
23		fmt.Printf("fail at node: %v   actual: %v  expected: %v\n", p.key, p.up.key, up.key)
24		return false
25	}
26	if !checkUp(p.left, p) {
27		return false
28	}
29	return checkUp(p.right, p)
30}
31
32// CheckCounts - check left and right node counts are ok
33func (tree *Tree) CheckCounts() bool {
34	b, _ := checkCounts(tree.root)
35	return b
36}
37
38func checkCounts(p *Node) (bool, int) {
39	if nil == p {
40		return true, 0
41	}
42	bl := true
43	nl := 0
44	if nil != p.left {
45		bl, nl = checkCounts(p.left)
46		if p.leftNodes != nl {
47			fmt.Printf("fail at node: %v  left actual: %d  record: %d\n", p.key, nl, p.leftNodes)
48			bl = false
49		}
50	}
51	br := true
52	nr := 0
53	if nil != p.right {
54		br, nr = checkCounts(p.right)
55		if p.rightNodes != nr {
56			fmt.Printf("fail at node: %v  right actual: %d  record: %d\n", p.key, nr, p.rightNodes)
57			br = false
58		}
59	}
60	return bl && br, 1 + nl + nr
61}
62