Flat nested set to nested structs in Go

Question

Maybe its just late in the day and this is making my brain melt.

I'm trying to convert a flat list of nested sets into a multi-dimensional nested array.

I have a bunch of structured CMS entries as follows:

entries := []TreeEntry{
        {
            Slug:  "about-us",
            Title: "About us",
            Left:  2,
            Right: 11,
            Level: 1,
        },
        {
            Slug:  "more-about-us",
            Title: "More about us",
            Left:  3,
            Right: 6,
            Level: 2,
        },
        {
            Slug:  "even-more-about-us",
            Title: "Even more about us",
            Left:  4,
            Right: 5,
            Level: 3,
        },
        {
            Slug:  "contact-us",
            Title: "Contact us",
            Left:  2,
            Right: 7,
            Level: 1,
        },
    }

And I want to unflatten them as follows:

entries := []TreeEntry{
        {
            Slug:  "about-us",
            Title: "About us",
            Left:  2,
            Right: 11,
            Level: 1,
            Children: []TreeEntry{
                {
                    Slug:  "more-about-us",
                    Title: "More about us",
                    Left:  3,
                    Right: 6,
                    Level: 2,
                    Children: []TreeEntry{
                        {
                            Slug:  "even-more-about-us",
                            Title: "Even more about us",
                            Left:  4,
                            Right: 5,
                            Level: 3,
                        },
                    },
                },
            },
        },
        {
            Slug:  "contact-us",
            Title: "Contact us",
            Left:  2,
            Right: 7,
            Level: 1,
        },
    }

The aim here is ultimately to return a menu structure with the slugs contact'ed together as appropriate, but some reason, I just cannot get my head around achieving this in Go.

Can anybody point me in the correct direction?

Edit: Added non-working example of what I've attempted:

https://play.golang.org/p/oKWo21lu__7

The results never add below the first level.

Thanks, J

Please show what you tried. Also, the desired structure based on the field values isn't clear, what are `Left`, `Right`, and `Level` and how are they used to build the tree? — Marc, Jan 31 '18 at 18:03
I've tried re-implementing this, in go: https://stackoverflow.com/questions/16999530/how-do-i-format-nested-set-model-data-into-an-array Left, Right and Level come from a database (not mine) and are the normal nested set values. — JimBlizz, Jan 31 '18 at 18:07
The link that you've provided already contains a recursive solution, you just need to translate that in go. And like Marc mention, it's easier to help if you showed us what you tried. — ahmy, Jan 31 '18 at 19:56
I've tried to tidy up my example, and given an idea of what i'm trying here: https://play.golang.org/p/oKWo21lu__7 The problem here is it never gets past the first nested level, and i'm unsure why. The data is sorted in level order from the database. — JimBlizz, Feb 01 '18 at 09:04

score 0 · Answer 1 · answered Feb 01 '18 at 10:03

As it turns out, I needed to use pointers to hold the child entries. The following setup works:

type TreeEntry struct {
    Id       int64        `db:"elementId" json:"id"`
    Slug     string       `db:"slug" json:"slug"`
    Title    string       `db:"title" json:"title"`
    Left     int          `db:"lft" json:"-"`
    Right    int          `db:"rgt" json:"-"`
    Level    int          `db:"level" json:"-"`
    Children []*TreeEntry `json:"children"`
}

func (t *TreeEntry) AddNestedChild(newEntry TreeEntry) {
    // If this child is one level below the current node, just add it here for now
    if newEntry.Level == t.Level+1 {
        t.Children = append(t.Children, &newEntry)
    } else {
        // Loop through the children and see if it fits anywhere
        for _, child := range t.Children {
            if newEntry.Left > child.Left && newEntry.Right < child.Right {
                child.AddNestedChild(newEntry)
                break
            }
        }
    }
}

Flat nested set to nested structs in Go

1 Answers1