Converting materialized paths into a tree with generics: a Golang kata

← Back to list

Posted on 15.05.2023

Last updated on 04.12.2024

Image by AI on Midjourney

Refill!

Structures

The implementation

Running the thing

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.

👉 📃 internal/domain/tree/tree.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"`
}

The code is licensed under the MIT license

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.

👉 📃 internal/lib/tree/tree.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)
}

The code is licensed under the MIT license

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.

👉 📃 cmd/main.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())
}

The code is licensed under the MIT license

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

Business-oriented fullstack engineer, in ❤️ with Tech.
Golang, React, TypeScript, Docker, AWS, Jamstack.
19+ years in dev.

Converting materialized paths into a tree with generics: a Golang kata

Table of contents

# Structures

# The implementation

# Running the thing

Sergei Gannochenko