Imagine I have sorted arrays looking like so:
["A", "B", "C"]
["A", "B", "D"]
["A", "E"]
["F", "G"]
Which I now want to have converted to
type Node struct {
NodeID string
Children []Node
}
What I did try is to write a way to do this by recursion.
This is my current attempt written in Go:
func Test_toNodes(t *testing.T) {
in := [][]string{
{"A", "B", "C"},
{"A", "B", "D"},
{"A", "E"},
{"F", "G"},
}
want := []Node{
{
Name: "A",
Children: []Node{
{
Name: "B",
Children: []Node{
{
Name: "C",
},
{
Name: "D",
},
},
},
{
Name: "E",
},
},
},
{
Name: "F",
},
}
got := toNodes(in)
if !reflect.DeepEqual(got, want) {
t.Fatalf("got %v, want %v", got, want)
}
}
func toNodes(in [][]string) []Node {
var (
tmp [][]string
out []Node
)
for i, hierarchy := range in {
current := nodeAt(in, i)
next := nodeAt(in, i+1)
if current == next {
if len(hierarchy) > 0 {
tmp = append(tmp, hierarchy[1:])
}
} else {
out = append(out, Node{
Name: current,
Children: toNodes(tmp),
})
}
}
return out
}
func nodeAt(h [][]string, i int) string {
if i > len(h)-1 {
return ""
}
v := h[i]
if len(v) == 0 {
return ""
}
return v[0]
}
This clearly does not render the correct results, and does not handle all the edge cases — so is there a general "algorithm", that can be applied here?
Here is a recursive solution that passes on your sample input. You didn't say much about the input and what edge cases there might be, so let me know if it fails on some input and provide the input.
I also fixed your expected result in the test. You forgot the child of F node G. Hope this helps.
type Node struct {
Name string
Children []Node
}
func Test_toNodes(t *testing.T) {
in := [][]string{
{"A", "B", "C"},
{"A", "B", "D"},
{"A", "E"},
{"F", "G"},
}
want := []Node{
{
Name: "A",
Children: []Node{
{
Name: "B",
Children: []Node{
{
Name: "C",
},
{
Name: "D",
},
},
},
{
Name: "E",
},
},
},
{
Name: "F",
Children: []Node{
{
Name: "G",
},
},
},
}
got := toNodes(in, 0, 0, len(in))
if !reflect.DeepEqual(got, want) {
t.Fatalf("got %v, want %v", got, want)
}
}
func toNodes(in [][]string, i, j, k int) []Node {
res := []Node{}
for m := j; m < k; m++ {
curr := nodeAt(in, i, m)
next := nodeAt(in, i, m+1)
if next != curr {
children := toNodes(in, i+1, j, m+1)
if len(children) == 0 {
children = nil
}
res = append(res, Node{
Name: curr,
Children: children,
})
j = m + 1
}
}
return res
}
func nodeAt(h [][]string, i, j int) string {
if j >= len(h) || i >= len(h[j]) {
return ""
}
return h[j][i]
}