Skip to content
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.

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

SortedArray handles incomparable values poorly #27

Closed
kriskowal opened this issue Sep 9, 2013 · 1 comment
Closed

SortedArray handles incomparable values poorly #27

kriskowal opened this issue Sep 9, 2013 · 1 comment
Assignees
Milestone

Comments

@kriskowal
Copy link
Member

If multiple, incomparable values are added to a sorted array, and subsequently removed, the sorted array should behave effectively like a plain array with push and pop. As yet, the search functions are returning indeterminate values and adding removing values from seemingly random positions.

See: montagejs/frb#13

@simon-weber
Copy link
Contributor

One problem I see is that callers of search that deal in equality (eg searchFirst/Last) make assumptions about the equality of elements around the result index. But, search only guarantees that the index is somewhere in streak of one or more incomparable values.

I think the fix is to adjust searchFirst/Last to scan both left and right from search's index, then scan within that range for their final result.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants