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
|
package set
import (
"sort"
)
// Add inserts the given value into the receiving Set.
//
// This mutates the set in-place. This operation is not thread-safe.
func (s Set) Add(val interface{}) {
hv := s.rules.Hash(val)
if _, ok := s.vals[hv]; !ok {
s.vals[hv] = make([]interface{}, 0, 1)
}
bucket := s.vals[hv]
// See if an equivalent value is already present
for _, ev := range bucket {
if s.rules.Equivalent(val, ev) {
return
}
}
s.vals[hv] = append(bucket, val)
}
// Remove deletes the given value from the receiving set, if indeed it was
// there in the first place. If the value is not present, this is a no-op.
func (s Set) Remove(val interface{}) {
hv := s.rules.Hash(val)
bucket, ok := s.vals[hv]
if !ok {
return
}
for i, ev := range bucket {
if s.rules.Equivalent(val, ev) {
newBucket := make([]interface{}, 0, len(bucket)-1)
newBucket = append(newBucket, bucket[:i]...)
newBucket = append(newBucket, bucket[i+1:]...)
if len(newBucket) > 0 {
s.vals[hv] = newBucket
} else {
delete(s.vals, hv)
}
return
}
}
}
// Has returns true if the given value is in the receiving set, or false if
// it is not.
func (s Set) Has(val interface{}) bool {
hv := s.rules.Hash(val)
bucket, ok := s.vals[hv]
if !ok {
return false
}
for _, ev := range bucket {
if s.rules.Equivalent(val, ev) {
return true
}
}
return false
}
// Copy performs a shallow copy of the receiving set, returning a new set
// with the same rules and elements.
func (s Set) Copy() Set {
ret := NewSet(s.rules)
for k, v := range s.vals {
ret.vals[k] = v
}
return ret
}
// Iterator returns an iterator over values in the set, in an undefined order
// that callers should not depend on.
//
// The pattern for using the returned iterator is:
//
// it := set.Iterator()
// for it.Next() {
// val := it.Value()
// // ...
// }
//
// Once an iterator has been created for a set, the set *must not* be mutated
// until the iterator is no longer in use.
func (s Set) Iterator() *Iterator {
// Sort the bucketIds to ensure that we always traverse in a
// consistent order.
bucketIds := make([]int, 0, len(s.vals))
for id := range s.vals {
bucketIds = append(bucketIds, id)
}
sort.Ints(bucketIds)
return &Iterator{
bucketIds: bucketIds,
vals: s.vals,
bucketIdx: -1,
}
}
// EachValue calls the given callback once for each value in the set, in an
// undefined order that callers should not depend on.
func (s Set) EachValue(cb func(interface{})) {
it := s.Iterator()
for it.Next() {
cb(it.Value())
}
}
// Values returns a slice of all of the values in the set in no particular
// order. This is just a wrapper around EachValue that accumulates the results
// in a slice for caller convenience.
//
// The returned slice will be nil if there are no values in the set.
func (s Set) Values() []interface{} {
var ret []interface{}
s.EachValue(func(v interface{}) {
ret = append(ret, v)
})
return ret
}
// Length returns the number of values in the set.
func (s Set) Length() int {
var count int
for _, bucket := range s.vals {
count = count + len(bucket)
}
return count
}
// Union returns a new set that contains all of the members of both the
// receiving set and the given set. Both sets must have the same rules, or
// else this function will panic.
func (s1 Set) Union(s2 Set) Set {
mustHaveSameRules(s1, s2)
rs := NewSet(s1.rules)
s1.EachValue(func(v interface{}) {
rs.Add(v)
})
s2.EachValue(func(v interface{}) {
rs.Add(v)
})
return rs
}
// Intersection returns a new set that contains the values that both the
// receiver and given sets have in common. Both sets must have the same rules,
// or else this function will panic.
func (s1 Set) Intersection(s2 Set) Set {
mustHaveSameRules(s1, s2)
rs := NewSet(s1.rules)
s1.EachValue(func(v interface{}) {
if s2.Has(v) {
rs.Add(v)
}
})
return rs
}
// Subtract returns a new set that contains all of the values from the receiver
// that are not also in the given set. Both sets must have the same rules,
// or else this function will panic.
func (s1 Set) Subtract(s2 Set) Set {
mustHaveSameRules(s1, s2)
rs := NewSet(s1.rules)
s1.EachValue(func(v interface{}) {
if !s2.Has(v) {
rs.Add(v)
}
})
return rs
}
// SymmetricDifference returns a new set that contains all of the values from
// both the receiver and given sets, except those that both sets have in
// common. Both sets must have the same rules, or else this function will
// panic.
func (s1 Set) SymmetricDifference(s2 Set) Set {
mustHaveSameRules(s1, s2)
rs := NewSet(s1.rules)
s1.EachValue(func(v interface{}) {
if !s2.Has(v) {
rs.Add(v)
}
})
s2.EachValue(func(v interface{}) {
if !s1.Has(v) {
rs.Add(v)
}
})
return rs
}
|
