javascriptgomaterialized-path-pattern

Issues with porting code from javascript to go


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


Solution

  • 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": []
          }
        ]
      }
    ]