/
string_set.go
134 lines (122 loc) · 2.85 KB
/
string_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
package report
import (
"sort"
)
// StringSet is a sorted set of unique strings. Clients must use the Add
// method to add strings.
type StringSet []string
var emptyStringSet StringSet
// MakeStringSet makes a new StringSet with the given strings.
func MakeStringSet(strs ...string) StringSet {
if len(strs) <= 0 {
return nil
}
result := make([]string, len(strs))
copy(result, strs)
sort.Strings(result)
for i := 1; i < len(result); { // shuffle down any duplicates
if result[i-1] == result[i] {
result = append(result[:i-1], result[i:]...)
continue
}
i++
}
return StringSet(result)
}
// Contains returns true if the string set includes the given string
func (s StringSet) Contains(str string) bool {
i := sort.Search(len(s), func(i int) bool { return s[i] >= str })
return i < len(s) && s[i] == str
}
// Intersection returns the intersections of a and b
func (s StringSet) Intersection(b StringSet) StringSet {
result, i, j := emptyStringSet, 0, 0
for i < len(s) && j < len(b) {
if s[i] == b[j] {
result = result.Add(s[i])
}
if s[i] < b[j] {
i++
} else {
j++
}
}
return result
}
// Equal returns true if a and b have the same contents
func (s StringSet) Equal(b StringSet) bool {
if len(s) != len(b) {
return false
}
for i := range s {
if s[i] != b[i] {
return false
}
}
return true
}
// Add adds the strings to the StringSet. Add is the only valid way to grow a
// StringSet. Add returns the StringSet to enable chaining.
func (s StringSet) Add(strs ...string) StringSet {
for _, str := range strs {
i := sort.Search(len(s), func(i int) bool { return s[i] >= str })
if i < len(s) && s[i] == str {
// The list already has the element.
continue
}
// It a new element, insert it in order.
s = append(s, "")
copy(s[i+1:], s[i:])
s[i] = str
}
return s
}
// Merge combines the two StringSets and returns a new result.
// Second return value is true if the return value is s
func (s StringSet) Merge(other StringSet) (StringSet, bool) {
switch {
case len(other) <= 0: // Optimise special case, to avoid allocating
return s, true // (note unit test DeepEquals breaks if we don't do this)
case len(s) <= 0:
return other, false
}
i, j := 0, 0
loop:
for i < len(s) {
switch {
case j >= len(other):
return s, true
case s[i] == other[j]:
i++
j++
case s[i] < other[j]:
i++
default:
break loop
}
}
if i >= len(s) && j >= len(other) {
return s, true
}
result := make(StringSet, i, len(s)+len(other))
copy(result, s[:i])
for i < len(s) {
switch {
case j >= len(other):
result = append(result, s[i:]...)
return result, false
case s[i] == other[j]:
result = append(result, s[i])
i++
j++
case s[i] < other[j]:
result = append(result, s[i])
i++
default:
result = append(result, other[j])
j++
}
}
result = append(result, other[j:]...)
return result, false
}