91 lines
2.1 KiB
Go
91 lines
2.1 KiB
Go
package main
|
|
|
|
import (
|
|
"fmt"
|
|
"strings"
|
|
)
|
|
|
|
const (
|
|
treeIndentStep = 2
|
|
treeStemWidth = treeIndentStep - 1
|
|
treeVertical = '\u2502'
|
|
treeThisAndMore = "\u251c"
|
|
treeJustThis = "\u2514"
|
|
treeStem = "\u2500"
|
|
)
|
|
|
|
type treeNode struct {
|
|
left, right string
|
|
notes []string
|
|
}
|
|
|
|
func selectRoot(nodes []treeNode) string {
|
|
children := make(map[string][]string)
|
|
areChildren := make(map[string]bool)
|
|
for _, node := range nodes {
|
|
areChildren[node.right] = true
|
|
if childlist, ok := children[node.left]; ok {
|
|
children[node.left] = append(childlist, node.right)
|
|
} else {
|
|
children[node.left] = []string{node.right}
|
|
}
|
|
}
|
|
favorite := ""
|
|
for left, right := range children {
|
|
if areChildren[left] {
|
|
continue
|
|
}
|
|
if favorite == "" {
|
|
favorite = left
|
|
} else if len(right) < len(children[favorite]) {
|
|
favorite = left
|
|
}
|
|
}
|
|
return favorite
|
|
}
|
|
|
|
func printSubTree(root string, nodes []treeNode, indent int, continued []int) []treeNode {
|
|
leftovers := []treeNode{}
|
|
children := []treeNode{}
|
|
for _, node := range nodes {
|
|
if node.left != root {
|
|
leftovers = append(leftovers, node)
|
|
continue
|
|
}
|
|
children = append(children, node)
|
|
}
|
|
for n, child := range children {
|
|
istring := []rune(strings.Repeat(" ", indent))
|
|
for _, column := range continued {
|
|
istring[column] = treeVertical
|
|
}
|
|
subc := continued[:]
|
|
header := treeJustThis
|
|
noteHeader := " "
|
|
if n < len(children)-1 {
|
|
subc = append(subc, indent)
|
|
header = treeThisAndMore
|
|
noteHeader = string(treeVertical)
|
|
}
|
|
fmt.Printf("%s%s%s%s\n", string(istring), header, strings.Repeat(treeStem, treeStemWidth), child.right)
|
|
for _, note := range child.notes {
|
|
fmt.Printf("%s%s%s%s\n", string(istring), noteHeader, strings.Repeat(" ", treeStemWidth), note)
|
|
}
|
|
leftovers = printSubTree(child.right, leftovers, indent+treeIndentStep, subc)
|
|
}
|
|
return leftovers
|
|
}
|
|
|
|
func printTree(nodes []treeNode) {
|
|
for len(nodes) > 0 {
|
|
root := selectRoot(nodes)
|
|
fmt.Printf("%s\n", root)
|
|
oldLength := len(nodes)
|
|
nodes = printSubTree(root, nodes, 0, []int{})
|
|
newLength := len(nodes)
|
|
if oldLength == newLength {
|
|
break
|
|
}
|
|
}
|
|
}
|