I have finally switched over to go1.19, so it's time to start making use of generics. So here comes my next Golang kata.
Many languages generics use the <P> notation. The creators of Go decided to make things differently and use an alternative [P] notation instead. In my perspective,
it made code a bit harder to comprehend, because such a notation blends in with slice declarations.
I am going to solve a task of converting materialized path into a nested in-memory tree structure with numeric payload on leafs.
Structures
A tree node has children of the recursive type, a name, and also a generalized payload.
package tree
type PayloadType interface {
int32 | int64
}
type Node[P PayloadType] struct {
Name string `json:"name"`
Nodes *[]*Node[P] `json:"nodes"`
Payload P `json:"payload"`
}
So here the P generic has a restriction, and can only be of type int32 or int64.
Also, the Nodes field is a pointer to an array, which is, in its turn, contains pointers as well.
The implementation
The logic itself is kept in a separate structure with additional methods for inserting a path and printing the tree out into JSON.
package tree
import (
"encoding/json"
"strings"
"tree/internal/domain/tree"
)
type Tree[P tree.PayloadType] struct {
Root *tree.Node[P]
Refs map[string]*tree.Node[P]
}
func New[P tree.PayloadType]() *Tree[P] {
items := make([]*tree.Node[P], 0)
rootNode := &tree.Node[P]{
Nodes: &items,
}
refs := make(map[string]*tree.Node[P])
refs[""] = rootNode
return &Tree[P]{
Root: rootNode,
Refs: refs,
}
}
func (t *Tree[P]) AddNode(path []string, payload P) {
if len(path) > 0 {
pathParts := make([]string, 0)
for index, pathElement := range path {
pathParts = append(pathParts, pathElement)
parentPath := path[:len(pathParts)-1]
pathKey := strings.Join(pathParts, ".")
parentPathKey := strings.Join(parentPath, ".")
if _, ok := t.Refs[pathKey]; !ok {
items := make([]*tree.Node[P], 0)
newNode := tree.Node[P]{
Name: pathElement,
Nodes: &items,
}
if index == len(path)-1 {
// it's a leaf, adding payload there
newNode.Payload = payload
}
toNode := t.Refs[parentPathKey]
toNodeNodesDeref := *toNode.Nodes
toNodeNodesDeref = append(toNodeNodesDeref, &newNode)
toNode.Nodes = &toNodeNodesDeref
t.Refs[pathKey] = &newNode
}
}
}
}
func (t *Tree[P]) ToJSON() string {
jsonData, _ := json.MarshalIndent(t.Root, "", " ")
return string(jsonData)
}
So here I iterate over the path segment and add more and more tree branches. To prevent searching on every insert, I keep an
index of tree nodes, referenced by a materialized sub-path as a key.
The AddNode() function has time complexity of O(N), where N is the depth of the path provided.
The memory complexity is O(N+logM), because of that map of size M to store the keys.
This implementation assumes, that the materialized path list can be unordered, which gives the algorithm more flexibility.
Also, please note that when it comes to storing the nodes, I operate only with pointers everywhere. This is to make sure that I avoid data cloning.
I spent half an hour trying to figure why my tree was only 2 levels deep, and all that was because the append() function actually makes a copy of an object in case if a non-pointer value is passed. This mistake is easy to make if a person comes from the Javascript background, like myself.
Running the thing
The main file is fairly simple and contains some demo data to work with.
package main
import (
"fmt"
"strings"
"tree/internal/lib/tree"
)
func main() {
materialisedTree := map[string]int32{
"shop.foo.bar": 1,
"shop.foo.baz": 3,
"package.foo.bar": 7,
"package.foo.m": 10,
}
treeInst := tree.New[int32]()
for path, weight := range materialisedTree {
treeInst.AddNode(strings.Split(path, "."), weight)
}
fmt.Println(treeInst.ToJSON())
}
So, as we can see, generics is an amazing tool, that can make Go code really flexible. The code an be then shipped as a standalone library and re-used in the other projects.
By the way, there is a good library, and it's all about generics. Definitely worth looking into, as it may save a lot of lines of code.
Cover image by AI at Midjourney
Top comments (0)