将物有的路径转换为带有仿制药的树：golang kata-DEV365 开发者社区

我终于切换到GO1.19，所以是时候开始使用仿制药了。所以我的下一个Golang Kata来了。

许多语言仿制药都使用

符号。 Go的创建者决定以不同的方式使事情有所不同，并使用替代性 [p] 符号。从我的角度来看，
它使代码更难理解，因为这样的符号与slice声明融为一体。

我将解决将物有的路径转换为带有数字有效载荷的嵌套内存中树结构的任务。

结构

一个树节点有递归类型的孩子，名称和广义有效载荷。

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"`
}

因此，这里的 p 通用有限制，只能是类型int32或int64。

另外，节点字段是一个指向数组的指针，依次也包含指针。

实施

逻辑本身保存在单独的结构中，并使用其他方法插入路径并将树打印到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)
}

所以我在这里迭代路径段，并添加越来越多的树枝。为了防止搜索每个插入物，我保留一个
树节点的索引，由实现的子路径作为钥匙引用。

AddNode()函数具有O(N)的时间复杂性，其中N是提供的路径的深度。
内存复杂性是O(N+logM)，因为该大小M的图表存储了键。

此实现假设可以无序列出实现的路径列表，从而使算法更灵活。

另外，请注意，在存储节点时，我只能在各地使用指针。这是为了确保我避免数据克隆。
我花了半个小时的时间试图找出为什么我的树只有2个级别，而所有这些是因为append()函数实际上是对对象的副本，以防如果传递了非销钉值。如果一个人来自JavaScript背景，那么这个错误很容易犯。

运行东西

主文件非常简单，并且包含一些用于使用的演示数据。

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())
}

因此，正如我们所看到的那样，仿制药是一个了不起的工具，可以使GO代码真正灵活。然后将代码作为独立库，并在其他项目中重复使用。

顺便说一句，有一个good library，这全都与仿制药有关。绝对值得研究，因为它可能会节省许多代码。

ai Midjourney

封面图像