I have this code in JS, which converts some sort of materialized path to tree structure:
var input = [[1201], [1201,1202,1203,1204], [1201,1202,1203], [1201,1202], [1201,1205]];
var output = [];
for (var i = 0; i < input.length; i++) {
var chain = input[i];
var currentNode = output;
for (var j = 0; j < chain.length; j++) {
var wantedNode = chain[j];
var lastNode = currentNode;
for (var k = 0; k < currentNode.length; k++) {
if (currentNode[k].name == wantedNode) {
currentNode = currentNode[k].children;
break;
}
}
if (lastNode == currentNode) {
var newNode = currentNode[k] = {name: wantedNode, children: []};
currentNode = newNode.children;
}
}
}
It works fine and giving me the result I expect:
[
{
"name": 1201,
"children": [
{
"name": 1202,
"children": [
{
"name": 1203,
"children": [
{
"name": 1204,
"children": []
}
]
}
]
},
{
"name": 1205,
"children": []
}
]
}
]
But I have some issues with porting it to Go. The closest solution by far is:
type tree struct {
ID int `json:"name"`
Children []*tree `json:"children"`
}
func (t *tree) get(id int) *tree {
for _, c := range t.Children {
if c.ID == id {
return c
}
}
return nil
}
func (t *tree) hasChild(id int) bool {
for _, c := range t.Children {
if c.ID == id {
return true
}
}
return false
}
root := tree{}
var tmpRoot *tree
for _, chain := range input {
if len(chain) == 1 {
root.ID = chain[0]
root.Children = make([]*tree, 0)
tmpRoot = &root
} else {
// id := chain[len(chain)-1]
parentID := chain[len(chain)-2]
for i, id := range chain {
if len(chain) < 2 || i == 0 {
continue
}
if tmpRoot.ID == parentID {
tmpRoot.Children = append(tmpRoot.Children, &tree{
ID: id,
Children: make([]*tree, 0),
})
} else {
if !tmpRoot.hasChild(id) {
tmpRoot = &tree{
ID: id,
Children: make([]*tree, 0),
}
tmpRoot.Children = append(root.Children, tmpRoot)
}
tmpRoot = tmpRoot.get(id)
}
}
}
}
But still some values are missing on different inputs, say
[[1201], [1201, 1205], [1201, 1207], [1201, 1202], [1201, 1202, 1206], [1201, 1202, 1203], [1201, 1202, 1203, 1204], [1201, 1202, 1203, 1208]]
gives me
{"name":1201,"children":[{"name":1205,"children":[]},{"name":1207,"children":[]},{"name":1202,"children":[{"name":1206,"children":[]},{"name":1202,"children":[]},{"name":1203,"children":[]}]}]}
Any help appreciated.
Go Playground: https://play.golang.org/p/XIHbaDHkp0m
Done. This is the working code:
type tree struct {
ID int `json:"id"`
Children []*tree `json:"children"`
}
func main() {
input := [][]int{
[]int{1201},
[]int{1201, 1205},
[]int{1201, 1207},
[]int{1201, 1202},
[]int{1201, 1202, 1206},
[]int{1201, 1202, 1203},
[]int{1201, 1202, 1203, 1204},
[]int{1201, 1202, 1203, 1208},
[]int{1201, 1209},
[]int{1201, 1202, 1210},
}
output := make([]*tree, 0)
for _, chain := range input {
currentNode := &output
for _, id := range chain {
wantedNode := id
lastNode := currentNode
var k int
for _, cn := range *currentNode {
if cn.ID == wantedNode {
currentNode = &((*currentNode)[k].Children)
break
}
k++
}
if reflect.DeepEqual(lastNode, currentNode) {
newNode := &tree{ID: wantedNode, Children: make([]*tree, 0)}
*currentNode = append(*currentNode, newNode)
currentNode = &newNode.Children
}
}
}
d, _ := json.Marshal(&output)
fmt.Printf(string(d))
}
Output:
[
{
"id": 1201,
"children": [
{
"id": 1205,
"children": []
},
{
"id": 1207,
"children": []
},
{
"id": 1202,
"children": [
{
"id": 1206,
"children": []
},
{
"id": 1203,
"children": [
{
"id": 1204,
"children": []
},
{
"id": 1208,
"children": []
}
]
},
{
"id": 1210,
"children": []
}
]
},
{
"id": 1209,
"children": []
}
]
}
]