123 lines
2.4 KiB
Go
123 lines
2.4 KiB
Go
// Copyright (c) 2024 Celestino Amoroso (celestino.amoroso@gmail.com).
|
|
// All rights reserved.
|
|
|
|
// graph.go
|
|
package expr
|
|
|
|
import (
|
|
"fmt"
|
|
"strings"
|
|
)
|
|
|
|
func BuildGraph(root *term) (g string) {
|
|
//var sb strings.Builder
|
|
g = fmt.Sprintf("tree: %v", root)
|
|
|
|
r := NewReticle(root)
|
|
fmt.Println(r)
|
|
return
|
|
}
|
|
|
|
type NodeRef struct {
|
|
node *term
|
|
pos int
|
|
label string
|
|
}
|
|
|
|
type Level []*NodeRef
|
|
|
|
type Reticle struct {
|
|
levels []Level
|
|
left, right int
|
|
colsWidth []int
|
|
}
|
|
|
|
func NewExprReticle(e Expr) *Reticle {
|
|
tree, _ := e.(*ast)
|
|
return NewReticle(tree.root)
|
|
}
|
|
|
|
func NewReticle(tree *term) *Reticle {
|
|
r := &Reticle{levels: make([]Level, 0)}
|
|
r.build(tree, 0, 0)
|
|
r.computeCharWidth()
|
|
return r
|
|
}
|
|
|
|
func (r *Reticle) computeCharWidth() {
|
|
numCol := r.right - r.left + 1
|
|
r.colsWidth = make([]int, numCol)
|
|
for _, level := range r.levels {
|
|
for _, ref := range level {
|
|
c := ref.pos - r.left
|
|
if v := ref.node.value(); v != nil {
|
|
ref.label = fmt.Sprintf("%v", v)
|
|
} else {
|
|
ref.label = ref.node.source()
|
|
}
|
|
r.colsWidth[c] = max(r.colsWidth[c], len(ref.label)+2) // +2 to make room for brakets
|
|
}
|
|
}
|
|
}
|
|
|
|
func (r *Reticle) build(node *term, depth, pos int) {
|
|
var level Level
|
|
if node == nil {
|
|
return
|
|
}
|
|
if len(r.levels) == depth {
|
|
level = make(Level, 0)
|
|
r.levels = append(r.levels, level)
|
|
} else {
|
|
level = r.levels[depth]
|
|
}
|
|
ref := &NodeRef{node: node, pos: pos}
|
|
level = append(level, ref)
|
|
if r.left > pos {
|
|
r.left = pos
|
|
}
|
|
if r.right < pos {
|
|
r.right = pos
|
|
}
|
|
if node.children != nil {
|
|
halfPos := len(node.children) / 2
|
|
childPos := pos - halfPos - 1
|
|
for _, child := range node.children {
|
|
childPos++
|
|
if childPos == pos && (len(node.children)&1) == 0 {
|
|
childPos++
|
|
}
|
|
r.build(child, depth+1, childPos)
|
|
}
|
|
}
|
|
r.levels[depth] = level
|
|
}
|
|
|
|
func (r *Reticle) nodeInLevel(level []*NodeRef, index int) (node *NodeRef) {
|
|
for _, ref := range level {
|
|
if ref.pos-r.left == index {
|
|
node = ref
|
|
break
|
|
}
|
|
}
|
|
return
|
|
}
|
|
|
|
func (r *Reticle) String() string {
|
|
var sb strings.Builder
|
|
for _, level := range r.levels {
|
|
for j, w := range r.colsWidth {
|
|
var label string
|
|
if ref := r.nodeInLevel(level, j); ref != nil {
|
|
s := "(" + ref.label + ")"
|
|
label = fmt.Sprintf("%[1]*s", -w, fmt.Sprintf("%[1]*s", (w+len(s))/2, s))
|
|
} else {
|
|
label = strings.Repeat(" ", w)
|
|
}
|
|
sb.WriteString(label)
|
|
}
|
|
sb.WriteByte('\n')
|
|
}
|
|
return sb.String()
|
|
}
|