diff options
-rw-r--r-- | pkg/rbtree/print_test.go | 30 | ||||
-rw-r--r-- | pkg/rbtree/rbtree_test.go | 44 |
2 files changed, 38 insertions, 36 deletions
diff --git a/pkg/rbtree/print_test.go b/pkg/rbtree/print_test.go new file mode 100644 index 0000000..c4154c8 --- /dev/null +++ b/pkg/rbtree/print_test.go @@ -0,0 +1,30 @@ +package rbtree + +import ( + "fmt" + "io" + "strings" +) + +func (t *Tree[K, V]) ASCIIArt() string { + var out strings.Builder + t.root.asciiArt(&out, "", "", "") + return out.String() +} + +func (node *Node[V]) asciiArt(w io.Writer, u, m, l string) { + if node == nil { + fmt.Fprintf(w, "%snil\n", m) + return + } + + node.Right.asciiArt(w, u+" ", u+" ,--", u+" | ") + + if node.Color == Red { + fmt.Fprintf(w, "%sR(%v)\n", m, node.Value) + } else { + fmt.Fprintf(w, "%sB(%v)\n", m, node.Value) + } + + node.Left.asciiArt(w, l+" | ", l+" `--", l+" ") +} diff --git a/pkg/rbtree/rbtree_test.go b/pkg/rbtree/rbtree_test.go index 6c49127..7b3987f 100644 --- a/pkg/rbtree/rbtree_test.go +++ b/pkg/rbtree/rbtree_test.go @@ -1,8 +1,6 @@ package rbtree import ( - "fmt" - "strings" "testing" "github.com/stretchr/testify/assert" @@ -10,37 +8,6 @@ import ( "golang.org/x/exp/constraints" ) -func printTree[K constraints.Ordered, V any](t *testing.T, tree *Tree[K, V]) { - fmtBareNode := func(node *Node[V]) string { - if node == nil { - return "nil" - } - if node.Color == Red { - return fmt.Sprintf("R(%v)", node.Value) - } else { - return fmt.Sprintf("B(%v)", node.Value) - } - } - addIndent := func(indent string, lines []string) []string { - ret := make([]string, 0, len(lines)) - for _, line := range lines { - ret = append(ret, indent+line) - } - return ret - } - var fmtNode func(node *Node[V]) []string - fmtNode = func(node *Node[V]) []string { - if node == nil { - return []string{"nil"} - } - ret := addIndent(" ", fmtNode(node.Right)) - ret = append(ret, fmtBareNode(node)) - ret = append(ret, addIndent(" ", fmtNode(node.Left))...) - return ret - } - t.Log("\n" + strings.Join(fmtNode(tree.root), "\n")) -} - func checkTree[K constraints.Ordered, V any](t *testing.T, tree *Tree[K, V]) { // 1. Every node is either red or black @@ -79,9 +46,8 @@ func checkTree[K constraints.Ordered, V any](t *testing.T, tree *Tree[K, V]) { }) for i := range cnts { if cnts[0] != cnts[i] { - if !assert.Truef(t, false, "node %v: not all leafs have same black-count: %v", node.Value, cnts) { - printTree(t, tree) - } + assert.Truef(t, false, "node %v: not all leafs have same black-count: %v", node.Value, cnts) + break } } }) @@ -125,7 +91,13 @@ func FuzzTree(f *testing.F) { assert.Equal(t, val, node.Value) } else { t.Logf("Delete(%v)", val) + if val == 25 { + t.Logf("before:\n\n%s\n", tree.ASCIIArt()) + } tree.Delete(val) + if val == 25 { + t.Logf("after:\n\n%s\n", tree.ASCIIArt()) + } assert.Nil(t, tree.Lookup(val)) } checkTree(t, tree) |