rust-lang/rust — pull request #16047 by Gankro (2014-07-28 15:00:22+00:00)
Title: WIP comparators for pqueue

Rough draft of implementing comparators. WIP, just looking for general design discussion. Do not merge.

Notes:

* First part of the file should really be moved to a separate module, maybe where `Ord` is defined? Realistically I'd like to migrate a lot of std away from requiring `Ord`, and instead requiring a `Comparator` (the former being trivial to move to the latter with `NaturalOrdering` and `RevOrdering`).

* I tried using `default_type_params`, but it never seemed to do anything meaningful.

* I tried making comparators impl `Fn`, but as far as I can tell, the type they'd have to impl would be be `Fn<(&T, &T), Ordering>`, but the references need to have lifetimes, and I see no sane way to do that generically? Just feeding in 'a,'b everywhere certainly didn't work.

* I made two "I don't care about comparators" constructors `min_heap` and `max_heap` as simply public functions, because they didn't make a lot of sense as static methods.

* I made `max_heap` the default behaviour to match previous behaviour, but now that they're trivially interchangeable, I recommend `min_heap` be the default, since that matches sorting more closely.

* Comparators are currently overengineered for this use case, (they could just have a single `lt` method), but again I'd like to refactor them out into a separate module and use them more everywhere. In that context they should return a proper `Ord`. Might be some overhead right now from doing `cmp(x,y) == Greater`, rather than `gt(x, y)`.

* Comparators could also provide `lt`/`gt`/`eq`/`neq` automatically; desirable?

* Weirdly `Extend` is demanding that the comparator be `Default`, even though I see no reason for this to be the case.

* Rust seems very bad at inferring the type the comparator wraps, even when it should be unambiguous from context; see: `tests.test_iterator`

* Could introduce even more combinatoric explosion in the constructors with e.g. `from_vec_natural` if desired.

* Tests have been rewritten to pass, but no new tests have been added. Similarly docs have not been updated. Didn't consider it a valuable use of time since this is WIP.