search

rustyscreeps / screeps-game-api

Typed bindings to the Screeps in-game API for WASM Rust AIs
MIT License
138 stars 45 forks source link

Thought: implement PartialOrd/Ord for things? #226

Open daboross opened 5 years ago

daboross commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

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:

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 commented 5 years ago

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 commented 5 years ago

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 commented 5 years ago

You go ahead then. And don't worry, I am mostly convinced by the implementations you suggested. It's better than object ids in python in any case!

I suppose it's my background in math that pushed me to push back on any kind of ordering on R^2.

On Thu, Aug 22, 2019, 22:35 David Ross notifications@github.com wrote:

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.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/rustyscreeps/screeps-game-api/issues/226?email_source=notifications&email_token=ABBF5FDA7GLOHC5LWMP6XYDQF5EHNA5CNFSM4IMRLLGKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD466EPI#issuecomment-524149309, or mute the thread https://github.com/notifications/unsubscribe-auth/ABBF5FD3F6BYZT5XQZQYZTLQF5EHNANCNFSM4IMRLLGA .