-
Notifications
You must be signed in to change notification settings - Fork 6
/
tree.go
154 lines (133 loc) · 3.81 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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
/*
Copyright IBM Corp. All Rights Reserved.
SPDX-License-Identifier: Apache-2.0
*/
package graph
// Iterator defines an iterator that can be used to traverse vertices
// of a graph
type Iterator interface {
// Next returns the next element in the iteration order,
// or nil if there is no such an element
Next() *TreeVertex
}
// TreeVertex defines a vertex of a tree
type TreeVertex struct {
Id string // id identifies uniquely the TreeVertex in the Tree
Data interface{} // data holds arbitrary data, to be used by the user of the package
Descendants []*TreeVertex // descendants are the vertices that this TreeVertex is their parent in the tree
Threshold int // threshold symbols the count of sub-trees / leaves to pick when creating tree permutations
}
// NewTreeVertex creates a new vertex with a given unique id and a given arbitrary data
func NewTreeVertex(id string, data interface{}, descendants ...*TreeVertex) *TreeVertex {
return &TreeVertex{
Id: id,
Data: data,
Descendants: descendants,
}
}
// IsLeaf returns whether the given vertex is a leaf
func (v *TreeVertex) IsLeaf() bool {
return len(v.Descendants) == 0
}
// AddDescendant creates a new vertex who's parent is the invoker vertex,
// with a given id and data. Returns the new vertex
func (v *TreeVertex) AddDescendant(u *TreeVertex) *TreeVertex {
v.Descendants = append(v.Descendants, u)
return u
}
// ToTree creates a Tree who's root vertex is the current vertex
func (v *TreeVertex) ToTree() *Tree {
return &Tree{
Root: v,
}
}
// Find searches for a vertex who's id is the given id.
// Returns the first vertex it finds with such an Id, or nil if not found
func (v *TreeVertex) Find(id string) *TreeVertex {
if v.Id == id {
return v
}
for _, u := range v.Descendants {
if r := u.Find(id); r != nil {
return r
}
}
return nil
}
// Exists searches for a vertex who's id is the given id,
// and returns whether such a vertex was found or not.
func (v *TreeVertex) Exists(id string) bool {
return v.Find(id) != nil
}
// Clone clones the tree who's root vertex is the current vertex.
func (v *TreeVertex) Clone() *TreeVertex {
var descendants []*TreeVertex
for _, u := range v.Descendants {
descendants = append(descendants, u.Clone())
}
copy := &TreeVertex{
Id: v.Id,
Descendants: descendants,
Data: v.Data,
}
return copy
}
// replace replaces the sub-tree of the vertex who's id is the given id
// with a sub-tree who's root vertex is r.
func (v *TreeVertex) replace(id string, r *TreeVertex) {
if v.Id == id {
v.Descendants = r.Descendants
return
}
for _, u := range v.Descendants {
u.replace(id, r)
}
}
// Tree defines a Tree of vertices of type TreeVertex
type Tree struct {
Root *TreeVertex
}
// Permute returns Trees that their vertices and edges all exist in the original tree.
// The permutations are calculated according to the thresholds of all vertices.
func (t *Tree) Permute() []*Tree {
return newTreePermutation(t.Root).permute()
}
// BFS returns an iterator that iterates the vertices
// in a Breadth-First-Search order
func (t *Tree) BFS() Iterator {
return newBFSIterator(t.Root)
}
type bfsIterator struct {
*queue
}
func newBFSIterator(v *TreeVertex) *bfsIterator {
return &bfsIterator{
queue: &queue{
arr: []*TreeVertex{v},
},
}
}
// Next returns the next element in the iteration order,
// or nil if there is no such an element
func (bfs *bfsIterator) Next() *TreeVertex {
if len(bfs.arr) == 0 {
return nil
}
v := bfs.dequeue()
for _, u := range v.Descendants {
bfs.enqueue(u)
}
return v
}
// a primitive implementation of a queue backed by a slice
type queue struct {
arr []*TreeVertex
}
func (q *queue) enqueue(v *TreeVertex) {
q.arr = append(q.arr, v)
}
func (q *queue) dequeue() *TreeVertex {
v := q.arr[0]
q.arr = q.arr[1:]
return v
}