juliangruber / juliangruber/go-intersect
The Sorted, SortedGeneric functions are totally broken in v2.0.1
- Dominant language
- Go
- Stars
- 118
- Forks
- 22
- PR merge metrics
- No merged PRs in 30d
Description
TL;DR Functions `intersect.Sorted` and `intersect.SortedGeneric()` in v2.0.1 are calling [`sort.Search`](https://pkg.go.dev/sort#Search) [incorrectly](https://github.com/juliangruber/go-intersect/blob/43d88bb8f8668c0192269c5843bd6746ae964c45/intersect.go#L26) and are therefore broken. Trivial demonstration: https://go.dev/play/p/Wgy5ee6lggF
Longer version: In the Sorted* API implementation, go-intersect tries to leverage the fact that the slices are sorted -- as expected. However, to be able to do that with the promised complexity, it must be able to determine whether a particular value is sorts before another one. (Essentially, the binary search, which gives the log(n) in the complexity, needs to know which of the two ways to go.) Currently, when it searches, it compares values for equality, which is not what `sort.Search` requires, hence the breakage.
I guess the current Sorted* API could be kept backwards compatible and with the promised complexity for some special cases (ints, floats, strings); or it could be made return correct results, but with the complexity of the Simple* API.
Fixing the Sorted* API in the general case, while keeping the current complexity promise, requires an additional argument: Probably a `less` function as in `sort.Slice`; or an interface with a method like `sort.Interface.Less`.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start in intersect.go at the sort.Search call around line 26 and reproduce the failure using the linked Go Playground example. Compare the behavior of intersect.Sorted and intersect.SortedGeneric with their documented inputs; done means both return correct intersections, with the API and complexity implications of ordering comparisons resolved.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go
- Domain
- tooling
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 30/100