Skip to content

Commit 6dbfe6f

Browse files
EmyrkEmyrk
authored
chore: remove duplicates using the symmetric difference function (#14469)
The `SymmetricDifferenceFunc` used to include duplicates, which was incorrect.
1 parent 15d74a1 commit 6dbfe6f

3 files changed

Lines changed: 47 additions & 4 deletions

File tree

‎coderd/util/slice/example_test.go‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -10,8 +10,8 @@ import (
1010
func ExampleSymmetricDifference() {
1111
// The goal of this function is to find the elements to add & remove from
1212
// set 'a' to make it equal to set 'b'.
13-
a := []int{1, 2, 5, 6}
14-
b := []int{2, 3, 4, 5}
13+
a := []int{1, 2, 5, 6, 6, 6}
14+
b := []int{2, 3, 3, 3, 4, 5}
1515
add, remove := slice.SymmetricDifference(a, b)
1616
fmt.Println("Elements to add:", add)
1717
fmt.Println("Elements to remove:", remove)

‎coderd/util/slice/slice.go‎

Lines changed: 18 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -62,6 +62,20 @@ func Overlap[T comparable](a []T, b []T) bool {
6262
})
6363
}
6464

65+
func UniqueFunc[T any](a []T, equal func(a, b T) bool) []T {
66+
cpy := make([]T, 0, len(a))
67+
68+
for _, v := range a {
69+
if ContainsCompare(cpy, v, equal) {
70+
continue
71+
}
72+
73+
cpy = append(cpy, v)
74+
}
75+
76+
return cpy
77+
}
78+
6579
// Unique returns a new slice with all duplicate elements removed.
6680
func Unique[T comparable](a []T) []T {
6781
cpy := make([]T, 0, len(a))
@@ -109,15 +123,15 @@ func Descending[T constraints.Ordered](a, b T) int {
109123
}
110124

111125
// SymmetricDifference returns the elements that need to be added and removed
112-
// to get from set 'a' to set 'b'.
126+
// to get from set 'a' to set 'b'. Note that duplicates are ignored in sets.
113127
// In classical set theory notation, SymmetricDifference returns
114128
// all elements of {add} and {remove} together. It is more useful to
115129
// return them as their own slices.
116130
// Notation: A Δ B = (A\B) ∪ (B\A)
117131
// Example:
118132
//
119133
// a := []int{1, 3, 4}
120-
// b := []int{1, 2}
134+
// b := []int{1, 2, 2, 2}
121135
// add, remove := SymmetricDifference(a, b)
122136
// fmt.Println(add) // [2]
123137
// fmt.Println(remove) // [3, 4]
@@ -127,6 +141,8 @@ func SymmetricDifference[T comparable](a, b []T) (add []T, remove []T) {
127141
}
128142

129143
func SymmetricDifferenceFunc[T any](a, b []T, equal func(a, b T) bool) (add []T, remove []T) {
144+
// Ignore all duplicates
145+
a, b = UniqueFunc(a, equal), UniqueFunc(b, equal)
130146
return DifferenceFunc(b, a, equal), DifferenceFunc(a, b, equal)
131147
}
132148

‎coderd/util/slice/slice_test.go‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -52,6 +52,22 @@ func TestUnique(t *testing.T) {
5252
slice.Unique([]string{
5353
"a", "a", "a",
5454
}))
55+
56+
require.ElementsMatch(t,
57+
[]int{1, 2, 3, 4, 5},
58+
slice.UniqueFunc([]int{
59+
1, 2, 3, 4, 5, 1, 2, 3, 4, 5,
60+
}, func(a, b int) bool {
61+
return a == b
62+
}))
63+
64+
require.ElementsMatch(t,
65+
[]string{"a"},
66+
slice.UniqueFunc([]string{
67+
"a", "a", "a",
68+
}, func(a, b string) bool {
69+
return a == b
70+
}))
5571
}
5672

5773
func TestContains(t *testing.T) {
@@ -230,4 +246,15 @@ func TestSymmetricDifference(t *testing.T) {
230246
require.ElementsMatch(t, []int{1, 2, 3}, add)
231247
require.ElementsMatch(t, []int{}, remove)
232248
})
249+
250+
t.Run("Duplicates", func(t *testing.T) {
251+
t.Parallel()
252+
253+
add, remove := slice.SymmetricDifference(
254+
[]int{5, 5, 5, 1, 1, 1, 3, 3, 3, 5, 5, 5},
255+
[]int{2, 2, 2, 1, 1, 1, 2, 4, 4, 4, 5, 5, 5, 1, 1},
256+
)
257+
require.ElementsMatch(t, []int{2, 4}, add)
258+
require.ElementsMatch(t, []int{3}, remove)
259+
})
233260
}

0 commit comments

Comments
 (0)