rpdata2/tag/tree.go

package tag

import (
	"git.aiterp.net/rpdata2-take2/rpdata2/auth"
	"git.aiterp.net/rpdata2-take2/rpdata2/internal/genutils"
)

type Node struct {
	Tag

	Children []Node `json:"children"`
}

func (n Node) WithoutSecret(reqUser *auth.UserInfo) *Node {
	return n.filter(func(n Node) bool {
		if !n.Secret {
			return false
		}

		return reqUser != nil && reqUser.HasIDOrPermission(n.OwnerID, "tag", "view_secret")
	})
}

func (n Node) WithoutUnlisted() *Node {
	return n.filter(func(n Node) bool { return n.Listed })
}

func (n Node) filter(cb func(n Node) bool) *Node {
	if !cb(n) {
		return nil
	}

	filtered := make([]Node, 0, len(n.Children))
	for _, child := range n.Children {
		pruned := child.filter(cb)
		if pruned == nil {
			continue
		}

		filtered = append(filtered, *pruned)
	}

	n.Children = filtered
	return &n
}

func (n Node) Less(n2 Node) bool {
	if n.Kind < n2.Kind {
		return true
	}

	return n.Name < n2.Name
}

func BuildForest(tags []Tag) []Node {
	nodes := make(map[string]*Node)
	for _, tag := range tags {
		nodes[tag.ID] = &Node{Tag: tag, Children: []Node{}}
	}

	children := make(map[string][]*Node, len(tags))
	for _, node := range nodes {
		if node.ParentID != nil {
			children[*node.ParentID] = append(children[*node.ParentID], node)
		}
	}

	cleared := make(map[string]bool)
	for len(cleared) < len(nodes) {
		anyCleared := false
		for _, node := range nodes {
			if cleared[node.ID] {
				continue
			}

			good := true
			for _, child := range children[node.ID] {
				if !cleared[child.ID] {
					good = false
					break
				}
			}

			if good {
				genutils.SortSlice(node.Children)

				cleared[node.ID] = true
				anyCleared = true
				if node.ParentID != nil {
					nodes[*node.ParentID].Children = append(nodes[*node.ParentID].Children, *node)
				}
			}
		}

		if !anyCleared {
			panic("deadlock in tag.BuildForest")
		}
	}

	res := make([]Node, 0, 8)
	for _, node := range nodes {
		if node.ParentID == nil {
			res = append(res, *node)
		}
	}

	genutils.SortSlice(res)

	return res
}