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

Thought: implement PartialOrd/Ord for things? #226

Open
daboross opened this issue Aug 18, 2019 · 11 comments
Open

Thought: implement PartialOrd/Ord for things? #226

daboross opened this issue Aug 18, 2019 · 11 comments
Labels
C-enhancement Category: A PR with an enhancement or a proposed on in an issue.

Comments

@daboross
Copy link
Collaborator

daboross commented Aug 18, 2019

Right now, almost nothing in the library has a "natural" ordering, and thus nothing implements Ord.

While this is reasonable, it means nothing can be stored as a key in a BTreeSet or BTreeMap, which might be desireable.

@ASalvail What do you think of having Position, RoomName, Resource, and all other constants which implement Hash also implement PartialOrd and Ord, using an arbitrary but consistent-within-releases ordering?

@ASalvail
Copy link
Collaborator

I'd say that's why Hash versions were invented: to give an unrelated mapping to integers that can be used for sorting? One could make an argument for RoomName or Position, but not Resource.

Any use cases for having an ordering on them that is all but arbitrary?
Maybe you have something @PatrickVdWillik ?

@PatrickVdWillik
Copy link
Contributor

Thanks for tagging me, I've been toying around with this myself but the biggest question I have is: Ordering in relation to what? Because while I got the stuff to work now, using a BTreeMap for my specific purpose, the calculation for the key value is offloaded into a separate function because the ordering has to make sense(in my case, a specific point on the map and the ordering is travel distance).

If you're going to order based on an arbitrary property, how useful will the ordering be? There's a pretty select set of use cases for rooms ordered by travel distance from origin (0, 0) (for instance). Wouldn't a set of structs that allow custom ordering via a closure (or similar mechanism) perhaps be more useful?

@ASalvail
Copy link
Collaborator

In that case, I'd vote to make sure Hash is derived, but let the end user figure out their own implementation for PartialOrd/Ord.

@ASalvail
Copy link
Collaborator

I went through the structs that we define. The only one I can see where it would make sense to add Ord is with screeps::constants::Density.

@daboross
Copy link
Collaborator Author

I'd say that's why Hash versions were invented: to give an unrelated mapping to integers that can be used for sorting? One could make an argument for RoomName or Position, but not Resource.

Hash is definitely good for this. My only problem with it is how it doesn't really integrate well with things expecting something naturally ordered, like [T]::binary_search or BTreeMap. It's possible to use together, but it requires coming up with a hashing algorithm since Hash is agnostic to how the combination is done, and then writing that glue code to turn the Hash impl into an Ord impl.

Any use cases for having an ordering on them that is all but arbitrary?

My main motivation is to be able to "just use" these things in BTreeMap and binary search, and other ordered structures, without having to care about how the ordering happens.

Maybe that's not a very good reason to do this though? Ord does kind of imply that one proper ordering exists, and it wouldn't be the worst thing to just use an OrdAsHash wrapper for stuff...

@ASalvail
Copy link
Collaborator

What if we added an ordering function (that returns a std::cmp::Ordering) to quickly implement PartialOrd with a wrapper type and that is efficient (like using the packedPos for Position)?

I'm not comfortable breaking the PartialOrd contract by implementing it directly.

@daboross
Copy link
Collaborator Author

I think an ordering function could be good, but it could still be pretty annoying to used compared to just being able to #[derive(PartialOrd, Ord)]. I mean a wrapper in my own code could just call .packed() on Position or use x as u32 for Resource/etc, though.

Would we really be breaking the PartialOrd contract if we implemented it? As long as the ordering is self-consistent, I don't think anything requires it to make sense. If we did something like literally sorting positions by their packed values, it would still satisfy antisymmetry and transitivity as described in PartialOrd's docs...

It does feel a bit against the spirit of PartialOrd, but I don't think that these implementations would be explicitly breaking it?

With that said, I'm OK with not adding these. Does feel like lying to say that Position and Resource can be ordered...

@daboross
Copy link
Collaborator Author

daboross commented Aug 23, 2019

I've posted about this issue, but not really pitched it. I think I can do better, after thinking about it. Here's an actual use case?

Right now, all constants, and things #[derive(Hash, PartialEq, Eq)] containing constants can be used as HashMap keys. However, they cannot be used as BTreeMap.

I'd really like to enable using constants in BTreeMap. For example, struct X(u32, ResourceType) could be a meaningful key in a BTreeMap, and could be sorted up to the resource type. The current best way I know to implement this is a BTreeMap<u32, HashMap<ResourceType, V>> - this works, but requires extra code, and extra indirection in memory.

The second best way is to manually implement Ord, using a cast.

impl Ord for X {
    fn cmp(&self, other: &Self) -> Ordering {
        self.0.cmp(other.0).then_with(|| (self.1 as u32).cmp(other.1 as u32))
    }
}

Not too painful, but has boilerplate. I believe using a custom method which returns Ordering would result in very similar code.

If we #[derive(PartialOrd, Ord)] for constants, then the above behavior could be achieved with #[derive(ParitalOrd, Ord)] struct X(u32, ResourceType);.

As I understand it, the trait contract of Ord requires is that types "form a total order". This is trivially true for enums which form finite sets with ordering based on declaration order. I believe this is also true for the integers, and Position, RoomName and ObjectId would defer their ordering to the integers contained within.

From a perspective ignoring sensibility of implemented traits, I would see this as a positive change.


I don't want to ignore the sensibility of ordering, though. If we just stick #[derive(PartialOrd, Ord)] on the enums, the ordering would be declaration order. That wouldn't have any reason for existing.

I'm not comfortable breaking the PartialOrd contract by implementing it directly.

What would you think if instead, we introduce arbitrary but rational orderings?

We could order:

  • enums representing strings in screeps by the lexicographical ordering of the strings.

  • enums representing integers in screeps by the ordering present in the integers.

  • Position first by world_x, and then by world_y.

    0,a < 1,b for any a, b, and c,0 < c,1 for any c.

  • RoomName first by world_x and then by world_y.

    The total ordering would be 127N127W, N127W126, N127W125, ..., N127W0, N127E0, ..., N127E127, N126W127, ..., S127E126, S127E127.

  • ObjectId by inner object id.

    For servers backed by MongoDB, the first 4 bytes in an ID represent seconds since the Unix epoch. Thus ordering would be roughly sorted by object creation time.

These orderings are not particularly useful. However, they are logical, and reproducible in other programming languages. The string constants, the integer constants and ObjectId ordering will directly agree with JavaScript's natural ordering. Position and room name ordering should be reasonably reproducible with effort


Anyways, that's my pitch. It should be at least somewhat reasonable, and if not, at least the idea is now well documented.

@ASalvail I'm hoping this address some of the reasonability of implementing PartialOrd / Ord on things which don't have a single expected ordering?

@ASalvail
Copy link
Collaborator

Clearly you want this implemented more than I want it not implemented 😛

I'm good with the orderings you suggested, with one exception: for Position and RoomName, sort first by y, then by x (which I think is that you meant, as it follows reading order).

Plus, make sure to document the ordering!

Do you need help for any of it?

@daboross
Copy link
Collaborator Author

Clearly you want this implemented more than I want it not implemented stuck_out_tongue

I mean that's fair, but I'd hope to convince you too :p.

I'm glad to have gone through and thought of logical ways of doing this, in any case. Much better than my original idea of just slapping #[derive(PartialOrd, Ord)] on everything.

I'm good with the orderings you suggested, with one exception: for Position and RoomName, sort first by y, then by x (which I think is that you meant, as it follows reading order).

This... is what I meant. Thanks!

Plus, make sure to document the ordering!

Do you need help for any of it?

Will do! I think I should be good to just implementing this, though if you'd like to I can hand off some to you?

As you say though, I'm kind of the one driving this - so it seems reasonable for me to do the implementation work.

@ASalvail
Copy link
Collaborator

ASalvail commented Aug 23, 2019 via email

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
C-enhancement Category: A PR with an enhancement or a proposed on in an issue.
Projects
None yet
Development

No branches or pull requests

4 participants