Require PartialOrd instead of Ord for priorities

[kpinter3-14]

I was using priority-queue for implementing pathfinding and I ran into an issue when trying to use floats as priorities. Priorities require Ord, but f32 does not implement it, only PartialOrd. I was curious if Ord is really necessary, and as far as I can tell it's not. I replaced all Ord bounds with PartialOrd and it still compiled.

I'm new to Rust, so please let me know if I missed something.

Thank you!

[garro95]

The problem is that relying on PartialOrd can result in a behavior surprisingly wrong or different from what someone wants.
f32 offers a good example: NaNs are not lesser nor greater nor equal to any other f32, included NaN itself. So what is the correct place for NaN in the queue? Any arbitrary choice could be wrong or unexpected for the library user.

In my opinion the best solution in this case is to require the Priority type to be Ord and let the users take the responsibility to wrap their PartialOrd type and implement Ord on the wrapped type in the most correct way for their use case.

In the specific case of floats, there are also crates that specifically do that: https://crates.io/search?q=ordered%20float

[kpinter3-14]

Thank you for checking out my PR!

I think NaN does not have a correct place in the queue because it is an error value. If the user pushes an element with NaN for its priority then the queue should not be considered valid anymore, and it's on the user to deal with this.

Requiring Ord when the implementation only needs PartialOrd takes options away from the library user. If it was only PartialOrd, I could use f32s, knowing that I will get garbage results if I use NaN, but I could still use a wrapped type if I wanted to handle NaN it in a specific way.

I still think only requiring the bare minimum trait bounds is the better option, because it gives more information and options to the user.

I'm wondering if if would be a better alternative to also allow providing a comparator instead of requiring an Ord instance. If you're still against PartialOrd but you'd be open to allowing comparators I could try implementing it (without breaking the API of course).

[MatejSloboda]

Priority queue most definitely requires Ord to be correct. ParitalOrd does not guarantee that an arbitrary set of elements can be sorted unambiguously (barring equal elements, off course). Requiring Ord guarantees that the queue will never accidentally break because of weird edge-case user input.
Allowing to provide comparator instead of requiring Ord instance achieves the exact same thing as implementing Ord for your priority type (or a wrapper type).

I had this same exact issue when I was starting out. Floats not being Ord is really annoying, but there are good reasons behind it. It's the nature of Rust. It's very "bureaucratic" and forces you to handle all the weird edge cases. Luckily, it also provides you with tools to do so. As a result, it is harder to make your code actually compile without errors, but when it finally does, it is also far more likely to run without errors.

[kpinter3-14]

Requiring Ord guarantees that the queue will never accidentally break because of weird edge-case user input.

I disagree. You cannot guarantee anything with Ord. If you expect the user to input "weird edge-case" data, how can you be sure that the user will implement Ord correctly, in a way that satisfies the required properties? The compiler cannot check it.

Allowing to provide comparator instead of requiring Ord instance achieves the exact same thing as implementing Ord for your priority type (or a wrapper type).

It achieves the same thing, with different syntax. That is not insignificant.

I had this same exact issue when I was starting out. Floats not being Ord is really annoying, but there are good reasons behind it.

I have no issues with restrictions, strong typing, etc "bureaucracy". I started getting into Rust because I wanted a close-to-the-metal Haskell. I merely disagree with the solution to this problem.

Thank you all for taking the time to look at this PR and sharing your thoughts!

[garro95]

f you expect the user to input "weird edge-case" data, how can you be sure that the user will implement Ord correctly, in a way that satisfies the required properties?

Of course we cannot, but if the user implements Ord in an inconsistent way, that is a responsibility of the user and they can easily find the problem in their code and fix it.

As a user, I would be very surprised to find out a library smoothed out a requirement and, as a result, I have a bug in my code.
If I make mistakes in implementing Ord, I can only blame myself instead