Convertir la carte en arbre dans Go

Question

J'ai un problème très spécifique, je ne peux pas trouver une solution pour.

J'ai un map[string]Metric, que je veux convertir en un arbre pour l'utilisation dans un frontend. L'interface Metric a un Path() et une méthode Name(), la méthode name renvoie la dernière partie d'un chemin séparé par des points (donc un chemin de 'my.awesome.metric' signifiera que cette métrique porte le nom 'metric') L'arbre devrait être trié par le chemin et devrait contenir IndexNode s. Ce struct ressemble à ceci:

type IndexNode struct { 
    Name string 
    Path string 
    Children []*IndexNode 
} 

donc une carte comme celle-ci:

{ 
    my.awesome.metric.downloads 
    my.awesome.othermetric.downloads 
    my.awesome.othermetric.uploads 
    my.other.cool.metric 
} 

devrait conduire à un arbre comme celui-ci: (désolé pour l'art ascii brut)

 +-- other -- cool -- metric 
    | 
my --+    +-- metric -- downloads 
    |    | 
    +-- awesome --+     +-- downloads 
        |     | 
        +-- othermetric --+ 
            | 
            +-- uploads 

Remarque que je n'ai jamais qu'un seul nœud racine (mon dans ce cas). L'ordre à l'intérieur de l'arbre ne m'importe pas.

J'ai essayé de mon mieux et ne peut pas le comprendre ... Après beaucoup de googleing (qui ne m'a montré comment créer des arbres binaires de recherche et la bibliothèque DIEUX), je résigné et a décidé de poser ma première question ici

Merci pour votre aide!

Answer 1

Remplacez Children par map[string]*IndexNode et vous êtes à mi-chemin. Si cela ne vous dérange pas d'être beaucoup plus lent à regarder des choses, vous pouvez utiliser une tranche, mais cela signifie que vous devez rechercher la tranche pour trouver l'enfant que vous voulez chaque fois que vous traversez l'arbre. Une carte est plus rapide et plus facile dans ce cas.

Maintenant vous avez juste besoin d'écrire une fonction récursive qui descend l'arbre, en faisant des nœuds nécessaires pour chaque élément dans le chemin jusqu'à ce qu'il atteigne la fin.

Malheureusement, je n'ont pas accès à un exemple, tout mon code sur mon autre ordinateur :(

Un exemple rapide et sale:

type Tree struct { 
    Parent *Tree 
    Children map[string]*Tree 
    Payload bool // Your data here 
} 

func NewTree(parent *Tree, path []string, payload bool) *Tree { 
    if parent == nil { 
     parent = &Tree{nil, map[string]*Tree{}, false} 
    } 
    if len(path) == 0 { 
     parent.Payload = payload 
     return parent 
    } 

    child := parent.Children[path[0]] 
    if child == nil { 
     child = &Tree{parent, map[string]*Tree{}, false} 
     parent.Children[path[0]] = child 
    } 
    return NewTree(child, path[1:], payload) 
} 

Utilisation:

root := NewTree(nil, nil, false) 
newnode := NewTree(root, []string{"A", "B", "C"}, true) 

Try it on the Go Playground!

Answer 2

Voici une solution utilisant une carte, la traversant peut vous aider à peupler e la structure de données. Peut créer les nœuds où il est dit "Parent xxx Enfant xxx" dans l'arborescence de navigation https://play.golang.org/p/sVqBCVgiBG