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

Get rid of insertBehind #35

Open
treeowl opened this issue Nov 18, 2020 · 3 comments
Open

Get rid of insertBehind #35

treeowl opened this issue Nov 18, 2020 · 3 comments
Milestone

Comments

@treeowl
Copy link
Collaborator

treeowl commented Nov 18, 2020

It's extremely slow, breaks on union, and relies in a brittle fashion on the exact implementation of minView. Let's be rid of it! The operation makes much more sense in priority queues based on finger trees, where the elements are stored in insertion order and the structure is annotated with subtree minima. (Specifically, a 2-3 finger tree whose digits can be 0 or 1 should do the trick).

@treeowl treeowl added this to the Release 1.5 milestone Dec 8, 2021
@treeowl
Copy link
Collaborator Author

treeowl commented Dec 9, 2021

Serious question: does this function even work at the moment? I have no idea if the new deletion implementation satisfies its brittle needs. If not, we may need to make a make a major release next just so we can kill this thing. It should never have gone in to begin with.

@treeowl
Copy link
Collaborator Author

treeowl commented Dec 9, 2021

Maybe I've been unfair. I thought this broke on union, but maybe it doesn't. And I haven't been able to break it (yet) with the new deletion function. So... maybe it's okay? It's really slow though!

@treeowl
Copy link
Collaborator Author

treeowl commented Dec 9, 2021

I just don't like how brittle it is. Every single operation in the module has to be written to preserve the order of insertBehind even though the module header explicitly documents unstable ordering. If it were fast, that might be worth doing (for stable sorts), but it's not, so I'd much rather not have that landmine.

treeowl added a commit to treeowl/pqueue that referenced this issue Mar 27, 2023
`insertBehind` does not interact in any particularly sensible way with
merges. I don't have a lot of faith that it works in other cases at
all—it's far too fragile. It's also too slow to be really useful.

First stage in lspitzner#35
treeowl added a commit to treeowl/pqueue that referenced this issue Mar 27, 2023
`insertBehind` does not interact in any particularly sensible way with
merges. I don't have a lot of faith that it works in other cases at
all—it's far too fragile. It's also too slow to be really useful.

First stage in lspitzner#35
treeowl added a commit that referenced this issue Mar 27, 2023
`insertBehind` does not interact in any particularly sensible way with
merges. I don't have a lot of faith that it works in other cases at
all—it's far too fragile. It's also too slow to be really useful.

First stage in #35
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

1 participant