Skip to content

chore: remove duplicates using the symmetric difference function #14469

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
Aug 29, 2024
Merged

chore: remove duplicates using the symmetric difference function #14469

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
4 changes: 2 additions & 2 deletions coderd/util/slice/example_test.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -10,8 +10,8 @@ import (
func ExampleSymmetricDifference() {
// The goal of this function is to find the elements to add & remove from
// set 'a' to make it equal to set 'b'.
a := []int{1, 2, 5, 6}
b := []int{2, 3, 4, 5}
a := []int{1, 2, 5, 6, 6, 6}
b := []int{2, 3, 3, 3, 4, 5}
add, remove := slice.SymmetricDifference(a, b)
fmt.Println("Elements to add:", add)
fmt.Println("Elements to remove:", remove)
Expand Down
20 changes: 18 additions & 2 deletions coderd/util/slice/slice.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -62,6 +62,20 @@ func Overlap[T comparable](a []T, b []T) bool {
})
}

func UniqueFunc[T any](a []T, equal func(a, b T) bool) []T {
cpy := make([]T, 0, len(a))

for _, v := range a {
if ContainsCompare(cpy, v, equal) {
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Why the repeated iteration? Can you not just keep a map[T]struct{} around? Or are you trying to avoid the comparable constraint?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I am trying to avoid the comparable constraint because the RBAC uses RoleIdentifier structs which are not comparable 😢.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Gotcha. We probably want to be careful that we don't use this for too large a slice then.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yea, atm the slices are in the order of 5-10 elements

continue
}

cpy = append(cpy, v)
}

return cpy
}

// Unique returns a new slice with all duplicate elements removed.
func Unique[T comparable](a []T) []T {
cpy := make([]T, 0, len(a))
Expand Down Expand Up @@ -109,15 +123,15 @@ func Descending[T constraints.Ordered](a, b T) int {
}

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

func SymmetricDifferenceFunc[T any](a, b []T, equal func(a, b T) bool) (add []T, remove []T) {
// Ignore all duplicates
a, b = UniqueFunc(a, equal), UniqueFunc(b, equal)
return DifferenceFunc(b, a, equal), DifferenceFunc(a, b, equal)
}

Expand Down
27 changes: 27 additions & 0 deletions coderd/util/slice/slice_test.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -52,6 +52,22 @@ func TestUnique(t *testing.T) {
slice.Unique([]string{
"a", "a", "a",
}))

require.ElementsMatch(t,
[]int{1, 2, 3, 4, 5},
slice.UniqueFunc([]int{
1, 2, 3, 4, 5, 1, 2, 3, 4, 5,
}, func(a, b int) bool {
return a == b
}))

require.ElementsMatch(t,
[]string{"a"},
slice.UniqueFunc([]string{
"a", "a", "a",
}, func(a, b string) bool {
return a == b
}))
}

func TestContains(t *testing.T) {
Expand Down Expand Up @@ -230,4 +246,15 @@ func TestSymmetricDifference(t *testing.T) {
require.ElementsMatch(t, []int{1, 2, 3}, add)
require.ElementsMatch(t, []int{}, remove)
})

t.Run("Duplicates", func(t *testing.T) {
t.Parallel()

add, remove := slice.SymmetricDifference(
[]int{5, 5, 5, 1, 1, 1, 3, 3, 3, 5, 5, 5},
[]int{2, 2, 2, 1, 1, 1, 2, 4, 4, 4, 5, 5, 5, 1, 1},
)
require.ElementsMatch(t, []int{2, 4}, add)
require.ElementsMatch(t, []int{3}, remove)
})
}
Loading