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
Documentation does not specify behavior for equal priorities #29
Comments
The order is arbitrary but deterministic, in the sense that you can repeat the exact same experiment with the same results, but equal element inserted in a certain order can be extracted in reverse order. It does not depend on the hasher, but only on the heap algorithm. I will properly update the documentation with this information. |
To clarify, is this test guaranteed to succeed?
In other words, if I have two queues and apply the same operations in the same order, are they guaranteed to remain synchronized? |
Yes. And also use priority_queue::PriorityQueue;
use hashbrown::hash_map::DefaultHashBuilder;
fn main() {
let mut a = PriorityQueue::new();
let mut b = PriorityQueue::<_, _, DefaultHashBuilder>::with_default_hasher();
a.push("Apples", 1);
b.push("Apples", 1);
a.push("Oranges", 1);
b.push("Oranges", 1);
a.push("Pears", 2);
b.push("Pears", 2);
a.push("Lemons", 1);
b.push("Lemons", 1);
// note, we don't care if "Apples" get popped before "Oranges"
// we only care that queues 'a' and 'b' will pop them in the same (arbitrary) order
// if we performed the same operations in the same order on queues 'a' and 'b'
assert_eq!(a.pop(), b.pop());
assert_eq!(a.pop(), b.pop());
assert_eq!(a.pop(), b.pop());
assert_eq!(a.pop(), b.pop());
} does not fail |
How will the items be sorted and popped, if their priority is equal? Is it insertion order? Is it arbitrary order? Is the order deterministic/repeatable? Does it depend on hasher? It would be nice if the documentation specified what minimum guarantee I can assume. At the moment I must assume the worst case scenario of completely random order, since the documentation doesn't indicate otherwise.
The text was updated successfully, but these errors were encountered: