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

Use UniqueStash instead of Stash #1

Open
FedericoStra opened this issue Jul 16, 2018 · 0 comments
Open

Use UniqueStash instead of Stash #1

FedericoStra opened this issue Jul 16, 2018 · 0 comments

Comments

@FedericoStra
Copy link

I think it would be safer to use UniqueStash instead of Stash in order to prevent decreasing an unwanted item with an outdated Handle. Consider the following example:

let mut heap = DefaultPairingHeap::new();
let h1 = heap.push('a', 1);
heap.pop(); // we pop the item `h1` was referring to
let _h2 = heap.push('b', 1);
heap.decrease_key(h1, 0); // here `h1` should no longer be valid
println!("{:?}", heap)

which outputs

PairingHeap { min: Handle(0), roots: [Handle(0)],
    data: {0: Node { pos: Root(0), entry: Entry { key: 0, elem: 'b' }, children: [] }} }

It shows that we have actually accidentally decreased the element indexed by h2, and not the the no longer existing item 'a', which originally gave us the handle.

I think the current implementation breaks the usual guarantees of rust, namely that references should not accidentally change the object they are referring to (and yes, the Handle plays the role of a reference; it's only a trick to circumvent the impossibility of using an actual reference)

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