-
Notifications
You must be signed in to change notification settings - Fork 232
/
tree.go
90 lines (84 loc) · 2.08 KB
/
tree.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
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
}
}
}