Skip to content

Instantly share code, notes, and snippets.

@tuesd4y
Created November 26, 2018 17:04
Show Gist options
  • Save tuesd4y/bb87933afdb463b750ecd5b83a18e019 to your computer and use it in GitHub Desktop.
Save tuesd4y/bb87933afdb463b750ecd5b83a18e019 to your computer and use it in GitHub Desktop.
abc
object BTreePrinter {
fun printNode(root: AVLNode, showHeight: Boolean = false) {
val maxLevel = BTreePrinter.maxLevel(root)
printNodeInternal(listOf(root), 1, maxLevel, showHeight)
}
private fun printNodeInternal(nodes: List<AVLNode?>, level: Int, maxLevel: Int, showHeight: Boolean) {
if (nodes.isEmpty() || BTreePrinter.isAllElementsNull(nodes))
return
val floor = maxLevel - level
val edgeLines = Math.pow(2.0, Math.max(floor - 1, 0).toDouble()).toInt()
val firstSpaces = Math.pow(2.0, floor.toDouble()).toInt() - 1
val betweenSpaces = Math.pow(2.0, (floor + 1).toDouble()).toInt() - 1
BTreePrinter.printWhitespaces(firstSpaces)
val newNodes = arrayListOf<AVLNode?>()
for (node in nodes) {
if (node != null) {
if (!showHeight) print("\b\b")
print(if (showHeight) node.height else node.elem)
newNodes.add(node.left)
newNodes.add(node.right)
} else {
newNodes.add(null)
newNodes.add(null)
print(" ")
}
BTreePrinter.printWhitespaces(betweenSpaces)
}
println("")
for (i in 1..edgeLines) {
for (j in nodes.indices) {
BTreePrinter.printWhitespaces(firstSpaces - i)
if (nodes[j] == null) {
BTreePrinter.printWhitespaces(edgeLines + edgeLines + i + 1)
continue
}
if (nodes[j]?.left != null)
print("/")
else
BTreePrinter.printWhitespaces(1)
BTreePrinter.printWhitespaces(i + i - 1)
if (nodes[j]?.right != null)
print("\\")
else
BTreePrinter.printWhitespaces(1)
BTreePrinter.printWhitespaces(edgeLines + edgeLines - i)
}
println("")
}
printNodeInternal(newNodes, level + 1, maxLevel, showHeight)
}
private fun printWhitespaces(count: Int) {
for (i in 0 until count)
print(" ")
}
private fun maxLevel(node: AVLNode?): Int {
return if (node == null) 0 else Math.max(BTreePrinter.maxLevel(node.left), BTreePrinter.maxLevel(node.right)) + 1
}
private fun <T> isAllElementsNull(list: List<T>): Boolean {
for (`object` in list) {
if (`object` != null)
return false
}
return true
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment