Converting materialized paths into a tree with generics: a Golang kata
Tags: go, generics, go20, tree
Published: 2023-05-16 21:15:28


---
title: "Converting materialized paths into a tree with generics: a Golang kata"
published: true
description: I have finally switched over to go1.19, so it is time to start making use of generics. So here comes my next Golang kata.
tags: go, generics, go20, tree
cover_image: https://gannochenko.dev/static/9335a5582f4c26a08e63a69a17dd5f67/5715c/cover.webp
canonical_url: https://gannochenko.dev/blog/converting-materialized-paths-into-a-tree-with-generics-a-golang-kata
---

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 __&lt;P&gt;__ 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.

```go
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.

```go
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.

```go
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](https://github.com/samber/lo), 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](https://www.midjourney.com/app/)