forked from apache/beam
/
tree.go
90 lines (77 loc) · 2.6 KB
/
tree.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
// Licensed to the Apache Software Foundation (ASF) under one or more
// contributor license agreements. See the NOTICE file distributed with
// this work for additional information regarding copyright ownership.
// The ASF licenses this file to You under the Apache License, Version 2.0
// (the "License"); you may not use this file except in compliance with
// the License. You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package graphx
import (
"github.com/apache/beam/sdks/go/pkg/beam/core/graph"
)
// NamedEdge is a named MultiEdge.
type NamedEdge struct {
Name string
Edge *graph.MultiEdge
}
// NamedScope is a named Scope.
type NamedScope struct {
Name string
Scope *graph.Scope
}
// ScopeTree is a convenient representation of the Scope-structure as a tree.
// Each ScopeTree may also be a subtree of another ScopeTree. The tree structure
// respects the underlying Scope structure, i.e., if Scope 'a' has a parent
// 'b' then the ScopeTree for 'b' must have the ScopeTree for 'a' as a child.
type ScopeTree struct {
// Scope is the named scope at the root of the (sub)tree.
Scope NamedScope
// Edges are the named edges directly under this scope.
Edges []NamedEdge
// Children are the scopes directly under this scope.
Children []*ScopeTree
}
// NewScopeTree computes the ScopeTree for a set of edges.
func NewScopeTree(edges []*graph.MultiEdge) *ScopeTree {
t := newTreeBuilder()
for _, edge := range edges {
t.addEdge(edge)
}
return t.root
}
// treeBuilder is a builder of a ScopeTree from any set of edges and
// scopes from the same graph.
type treeBuilder struct {
root *ScopeTree
id2tree map[int]*ScopeTree
}
func newTreeBuilder() *treeBuilder {
return &treeBuilder{
id2tree: make(map[int]*ScopeTree),
}
}
func (t *treeBuilder) addEdge(edge *graph.MultiEdge) {
tree := t.addScope(edge.Scope())
tree.Edges = append(tree.Edges, NamedEdge{Name: edge.Name(), Edge: edge})
}
func (t *treeBuilder) addScope(s *graph.Scope) *ScopeTree {
if tree, exists := t.id2tree[s.ID()]; exists {
return tree
}
tree := &ScopeTree{Scope: NamedScope{Name: s.Label, Scope: s}}
t.id2tree[s.ID()] = tree
if s.Parent == nil {
t.root = tree
} else {
parent := t.addScope(s.Parent)
parent.Children = append(parent.Children, tree)
}
return tree
}