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