forked from openshift/origin
-
Notifications
You must be signed in to change notification settings - Fork 0
/
set.go
211 lines (174 loc) · 4.43 KB
/
set.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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
// Copyright ©2014 The gonum Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package internal
import (
"unsafe"
"github.com/gonum/graph"
)
// IntSet is a set of integer identifiers.
type IntSet map[int]struct{}
// The simple accessor methods for Set are provided to allow ease of
// implementation change should the need arise.
// Add inserts an element into the set.
func (s IntSet) Add(e int) {
s[e] = struct{}{}
}
// Has reports the existence of the element in the set.
func (s IntSet) Has(e int) bool {
_, ok := s[e]
return ok
}
// Remove deletes the specified element from the set.
func (s IntSet) Remove(e int) {
delete(s, e)
}
// Count reports the number of elements stored in the set.
func (s IntSet) Count() int {
return len(s)
}
// Same determines whether two sets are backed by the same store. In the
// current implementation using hash maps it makes use of the fact that
// hash maps (at least in the gc implementation) are passed as a pointer
// to a runtime Hmap struct.
//
// A map is not seen by the runtime as a pointer though, so we cannot
// directly compare the sets converted to unsafe.Pointer and need to take
// the sets' addressed and dereference them as pointers to some comparable
// type.
func Same(s1, s2 Set) bool {
return *(*uintptr)(unsafe.Pointer(&s1)) == *(*uintptr)(unsafe.Pointer(&s2))
}
// A set is a set of nodes keyed in their integer identifiers.
type Set map[int]graph.Node
// The simple accessor methods for Set are provided to allow ease of
// implementation change should the need arise.
// Add inserts an element into the set.
func (s Set) Add(n graph.Node) {
s[n.ID()] = n
}
// Remove deletes the specified element from the set.
func (s Set) Remove(e graph.Node) {
delete(s, e.ID())
}
// Has reports the existence of the element in the set.
func (s Set) Has(n graph.Node) bool {
_, ok := s[n.ID()]
return ok
}
// Clear returns an empty set, possibly using the same backing store.
// Clear is not provided as a method since there is no way to replace
// the calling value if clearing is performed by a make(set). Clear
// should never be called without keeping the returned value.
func Clear(s Set) Set {
if len(s) == 0 {
return s
}
return make(Set)
}
// Copy performs a perfect copy from s1 to dst (meaning the sets will
// be equal).
func (dst Set) Copy(src Set) Set {
if Same(src, dst) {
return dst
}
if len(dst) > 0 {
dst = make(Set, len(src))
}
for e, n := range src {
dst[e] = n
}
return dst
}
// Equal reports set equality between the parameters. Sets are equal if
// and only if they have the same elements.
func Equal(s1, s2 Set) bool {
if Same(s1, s2) {
return true
}
if len(s1) != len(s2) {
return false
}
for e := range s1 {
if _, ok := s2[e]; !ok {
return false
}
}
return true
}
// Union takes the union of s1 and s2, and stores it in dst.
//
// The union of two sets, s1 and s2, is the set containing all the
// elements of each, for instance:
//
// {a,b,c} UNION {d,e,f} = {a,b,c,d,e,f}
//
// Since sets may not have repetition, unions of two sets that overlap
// do not contain repeat elements, that is:
//
// {a,b,c} UNION {b,c,d} = {a,b,c,d}
//
func (dst Set) Union(s1, s2 Set) Set {
if Same(s1, s2) {
return dst.Copy(s1)
}
if !Same(s1, dst) && !Same(s2, dst) {
dst = Clear(dst)
}
if !Same(dst, s1) {
for e, n := range s1 {
dst[e] = n
}
}
if !Same(dst, s2) {
for e, n := range s2 {
dst[e] = n
}
}
return dst
}
// Intersect takes the intersection of s1 and s2, and stores it in dst.
//
// The intersection of two sets, s1 and s2, is the set containing all
// the elements shared between the two sets, for instance:
//
// {a,b,c} INTERSECT {b,c,d} = {b,c}
//
// The intersection between a set and itself is itself, and thus
// effectively a copy operation:
//
// {a,b,c} INTERSECT {a,b,c} = {a,b,c}
//
// The intersection between two sets that share no elements is the empty
// set:
//
// {a,b,c} INTERSECT {d,e,f} = {}
//
func (dst Set) Intersect(s1, s2 Set) Set {
var swap Set
if Same(s1, s2) {
return dst.Copy(s1)
}
if Same(s1, dst) {
swap = s2
} else if Same(s2, dst) {
swap = s1
} else {
dst = Clear(dst)
if len(s1) > len(s2) {
s1, s2 = s2, s1
}
for e, n := range s1 {
if _, ok := s2[e]; ok {
dst[e] = n
}
}
return dst
}
for e := range dst {
if _, ok := swap[e]; !ok {
delete(dst, e)
}
}
return dst
}