juliangruber / juliangruber/go-intersect

The Sorted, SortedGeneric functions are totally broken in v2.0.1

Open
#14 1 comment 1 reaction 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.