-
Notifications
You must be signed in to change notification settings - Fork 39.3k
/
edgeholder.go
122 lines (114 loc) · 2.9 KB
/
edgeholder.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
package simple
import "k8s.io/kubernetes/third_party/forked/gonum/graph"
// edgeHolder represents a set of edges, with no more than one edge to or from a particular neighbor node
type edgeHolder interface {
// Visit invokes visitor with each edge and the id of the neighbor node in the edge
Visit(visitor func(neighbor int, edge graph.Edge))
// Delete removes edges to or from the specified neighbor
Delete(neighbor int) edgeHolder
// Set stores the edge to or from the specified neighbor
Set(neighbor int, edge graph.Edge) edgeHolder
// Get returns the edge to or from the specified neighbor
Get(neighbor int) (graph.Edge, bool)
// Len returns the number of edges
Len() int
}
// sliceEdgeHolder holds a list of edges to or from self
type sliceEdgeHolder struct {
self int
edges []graph.Edge
}
func (e *sliceEdgeHolder) Visit(visitor func(neighbor int, edge graph.Edge)) {
for _, edge := range e.edges {
if edge.From().ID() == e.self {
visitor(edge.To().ID(), edge)
} else {
visitor(edge.From().ID(), edge)
}
}
}
func (e *sliceEdgeHolder) Delete(neighbor int) edgeHolder {
edges := e.edges[:0]
for i, edge := range e.edges {
if edge.From().ID() == e.self {
if edge.To().ID() == neighbor {
continue
}
} else {
if edge.From().ID() == neighbor {
continue
}
}
edges = append(edges, e.edges[i])
}
e.edges = edges
return e
}
func (e *sliceEdgeHolder) Set(neighbor int, newEdge graph.Edge) edgeHolder {
for i, edge := range e.edges {
if edge.From().ID() == e.self {
if edge.To().ID() == neighbor {
e.edges[i] = newEdge
return e
}
} else {
if edge.From().ID() == neighbor {
e.edges[i] = newEdge
return e
}
}
}
if len(e.edges) < 4 {
e.edges = append(e.edges, newEdge)
return e
}
h := mapEdgeHolder(make(map[int]graph.Edge, len(e.edges)+1))
for i, edge := range e.edges {
if edge.From().ID() == e.self {
h[edge.To().ID()] = e.edges[i]
} else {
h[edge.From().ID()] = e.edges[i]
}
}
h[neighbor] = newEdge
return h
}
func (e *sliceEdgeHolder) Get(neighbor int) (graph.Edge, bool) {
for _, edge := range e.edges {
if edge.From().ID() == e.self {
if edge.To().ID() == neighbor {
return edge, true
}
} else {
if edge.From().ID() == neighbor {
return edge, true
}
}
}
return nil, false
}
func (e *sliceEdgeHolder) Len() int {
return len(e.edges)
}
// mapEdgeHolder holds a map of neighbors to edges
type mapEdgeHolder map[int]graph.Edge
func (e mapEdgeHolder) Visit(visitor func(neighbor int, edge graph.Edge)) {
for neighbor, edge := range e {
visitor(neighbor, edge)
}
}
func (e mapEdgeHolder) Delete(neighbor int) edgeHolder {
delete(e, neighbor)
return e
}
func (e mapEdgeHolder) Set(neighbor int, edge graph.Edge) edgeHolder {
e[neighbor] = edge
return e
}
func (e mapEdgeHolder) Get(neighbor int) (graph.Edge, bool) {
edge, ok := e[neighbor]
return edge, ok
}
func (e mapEdgeHolder) Len() int {
return len(e)
}