I was wondering if any of the members know a proper way to implement a generic binary tree in GoLang?
I tried it with a Btree interface and two struct’s empty and node which implement the Btree interface and it seems to work until I need function signatures for the Btree interface which require additional generic parameters. My solution. Just move the functionality out the Btree interface and create generic functions which take a Btree… Here’s the functionality I’m playing with:
btree.go
package btree
type Btree[T any] interface {
isEmpty() bool
Display(func(...any) (int, error))
Add(T, func(T, T) int) Btree[T]
Find(T, func(T, T) int) Btree[T]
Filter(func(T) bool) Btree[T]
}
//moved Fold out Btree bc of extra generic parameter
func Fold[T any, U any](bt Btree[T], f func(U, T) U, acc U) U {
if bt.isEmpty() {
return acc
} else {
n := bt.(node[T])
return Fold(n.right, f, Fold(n.left, f, f(acc, n.data)))
}
}
func mapb_aux[T any, U any](acc *Btree[U], bt Btree[T], f func(T) U, c func(U, U) int) {
if !bt.isEmpty() {
n := bt.(node[T])
mapb_aux(acc, n.left, f, c)
*acc = (*acc).Add(f(n.data), c)
mapb_aux(acc, n.right, f, c)
}
}
//moved MapB out Btree bc of extra generic parameter
func MapB[T any, U any](bt Btree[T], f func(T) U, c func(U, U) int) Btree[U] {
acc := CreateEmptyBtree[U]()
mapb_aux(&acc, bt, f, c)
return acc
}
func CreateEmptyBtree[T any]() Btree[T] {
return empty[T]{}
}
empty.go
package btree
type empty[T any] struct{}
func (empty[T]) isEmpty() bool {
return true
}
func (empty[T]) Display(f func(...any) (int, error)) {
f("Empty")
}
func (e empty[T]) Add(data T, f func(T, T) int) Btree[T] {
return node[T]{data, e, e}
}
func (e empty[T]) Find(_ T, f func(T, T) int) Btree[T] {
return e
}
func (e empty[T]) Filter(_ func(T) bool) Btree[T] {
return e
}
node.go
package btree
type node[T any] struct {
data T
left Btree[T]
right Btree[T]
}
func (node[T]) isEmpty() bool {
return false
}
func (n node[T]) Display(f func(...any) (int, error)) {
n.left.Display(f)
f(n.data)
n.right.Display(f)
}
func (n node[T]) Add(data T, f func(T, T) int) Btree[T] {
ans := f(n.data, data)
if ans < 0 {
return node[T]{n.data, n.left.Add(data, f), n.right}
} else if ans > 0 {
return node[T]{n.data, n.left, n.right.Add(data, f)}
}
return n
}
func (n node[T]) Find(data T, f func(T, T) int) Btree[T] {
ans := f(n.data, data)
if ans < 0 {
return n.left.Find(data, f)
} else if ans > 0 {
return n.right.Find(data, f)
}
return n
}
func join_branches[T any](left, right Btree[T]) Btree[T] {
if right.isEmpty() {
return left
}
n := right.(node[T])
return node[T]{n.data, join_branches(left, n.left), n.right}
}
func (n node[T]) Filter(f func(T) bool) Btree[T] {
if f(n.data) {
return join_branches(n.left, n.right).Filter(f)
}
return node[T]{n.data, n.left.Filter(f), n.right.Filter(f)}
}
main.go
package main
import (
"fmt"
"math/rand"
btree "packs/MyPacks/Btree"
"strconv"
"time"
)
func createRandomIntSlice(s []int) []int {
rand.Seed(time.Now().UnixNano())
rand.Shuffle(len(s), func(i, j int) { s[i], s[j] = s[j], s[i] })
return s
}
func compare_ints(i, j int) int {
if i < j {
return -1
} else if i > j {
return 1
}
return 0
}
func compare_strings(i, j string) int {
if i < j {
return -1
} else if i > j {
return 1
}
return 0
}
func main() {
bt := btree.CreateEmptyBtree[int]()
for _, e := range createRandomIntSlice([]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}) {
bt = bt.Add(e, compare_ints)
}
bt.Display(fmt.Println)
fmt.Println(bt)
fmt.Println("\n\nFind")
bt.Find(4, compare_ints).Display(fmt.Println)
fmt.Println(bt.Find(4, compare_ints))
fmt.Println("\n\nFilter")
bt.Filter(func(i int) bool { return i%2 == 0 }).Display(fmt.Println)
fmt.Println(bt.Filter(func(i int) bool { return i%2 == 0 }))
fmt.Println("\n\nFold")
fmt.Println(btree.Fold(bt, func(acc, e int) int { return acc + e }, 0))
bts := btree.MapB(bt, func(i int) string { return strconv.Itoa(i) }, compare_strings)
bts.Display(fmt.Println)
}
Is there any problems with creating a generic binary tree this way in GoLang?