Converting materialized paths into a tree with generics: a Golang kata
I have finally switched over to go1.20, 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 treetype 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 treeimport ("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[""] = rootNodereturn &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 therenewNode.Payload = payload}toNode := t.Refs[parentPathKey]toNodeNodesDeref := *toNode.NodestoNodeNodesDeref = append(toNodeNodesDeref, &newNode)toNode.Nodes = &toNodeNodesDereft.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 mainimport ("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 can 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 code lines.
As usual, the code of the kata is available here. Have fun!
Sergei Gannochenko
Golang, React, TypeScript, Docker, AWS, Jamstack.
19+ years in dev.