The Future's So Bright, I Gotta Implement 'Sort'

jasonharper

Developer
As of revision 6953, ASH has a 'sort' command for arrays & maps. It's always bothered me a bit that this couldn't be written in a completely generic manner in ASH itself - and it's quite possible that the near future will bring some additional things that you might want to sort.

The syntax is:
sort aggregate by keyExpr;
aggregate is a reference to the object to be sorted - arrays are probably the most useful things to sort, but any mapping type can be used (even multidimensional maps, but note that you can only sort along a single dimension at a time). The reference must not be enclosed in parentheses, as that would look like a call to a function named sort() - which is still perfectly valid, "sort" has not become a reserved word.

keyExpr is an arbitrary expression that defines how the items should be ordered. It is evaluated once for every entry in the aggregate, in a scope with two additional variables implicitly defined: 'index' and 'value', holding the details of that entry. The value of the keyExpr is used as the sort key; typically it would be an int or string, but can be any ASH type that can be compared via "<" and the other relational operators.

The most basic form of sorting would therefore be "sort ... by value", but many useful things can be done with the use of a more complex keyExpr - the only real restriction is that the expression should not modify the object you're sorting. For example, if you had an array of items, you could sort it "by autosell_price(value)". An array of weapon items could be sorted "by -get_power(value)" to put it in decreasing order of power. If the elements of your aggregate are records, you'd need to use something like "by value.fieldName", since the records themselves can't be meaningfully compared.

After the sort statement, the aggregate will have exactly the same sets of keys and values as before (even if the keys weren't consecutive), and the iteration order of the keys will be the same, but the values will likely be associated with different keys. The sort is stable - in other words, elements with sort keys that compare as equal will remain in the same order. This means that you can sort on multiple criteria by simply performing separate sorts for each of the criteria, in increasing order of significance.

A few more examples of things you can do:
* "by -value" sorts integers in decreasing order (there's no similar trick for string values).
* "by -index" reverses the existing order of an array (or map with integer keys).
* "by random(1000000)" shuffles into a random order.
* "by otherArray[index]" uses values from a parallel array as the sort keys (you'd then need to do "sort otherArray by value;" if you wanted the two arrays to remain in sync).
 
Last edited:

Bale

Minion
item [int] options;
int [item] maxval;
sort options by maxval;

Will that sort options by the associated integer value in the second map?

eg,
options [1] = $item[tonic water];
options [2] = $item[$item[bottle of Monsieur Bubble]];
options [3] = $item[Knob Goblin seltzer];
maxval[$item[tonic water]] = 50;
maxval[$item[bottle of Monsieur Bubble]] = 65;
maxval[$item[Knob Goblin seltzer]] = 12

Will become:
options[1] == $item[Knob Goblin seltzer]
options[2] == $item[tonic water]
options[3] == $item[bottle of Monsieur Bubble]
 
Last edited:

jasonharper

Developer
That should be: sort options by maxval[value];
There is pretty much always going to be a reference to 'value' (or less commonly, 'index') in the expression; without that, the entry's new position won't have anything to do with its current value, which is a fairly uncommon need.
 

Spiny

Member
A bit of a necro here, but as there is no documentation of "sort" anywhere, other than here, and my question is a by-product of sorting, I'm asking here :)

I have an array that I'm sorting by index. Some items in the array are capitalized and others are not. I'd like to sort ignoring case, is there an easy way to do that?

Thanks,
-Spiny
 

Spiny

Member
Not sure if this will work, but have you tried

sort my_array by to_lower_case(index);

Thanks Bale,

I was thinking about to_lower_case for this at the same time I was posting my message last night. I wasn't sure that I'd be able to use it, but it worked.

I was using:
Code:
sort my_array by my_array[index];
Your suggestion prompted me to change it to:
Code:
sort my_array by to_lower_case(my_array[index]);
and that works :)

Thanks!
-Spiny
 

dj_d

Member
So I love sort. But I also really like maps (sort of, even though they often make my brain hurt). Could the language support something like this:

foreach x in aggregate sort by value

This would only affect the order in which the map values are extracted, and wouldn't affect the map itself.
 

jasonharper

Developer
Could you give an example of what that would do? It's hard to imagine any sort of useful sorting behavior that "wouldn't affect the map itself".
 

dj_d

Member
Here's what I'd like to do, although my syntax may not be right:

Code:
record rec
{
  int stuff;
  int morestuff;
};
rec [loc] locations;
foreach loc in locations sort by value.stuff
  print(loc);
This would print locations ordered by the associated stuff value, but not actually modify the map. (I actually don't care if the map was modified - it just seemed like the "right" way to make this work. If there's a way to use sort to accomplish the aforementioned functionality, with or without modifiying the map, then that's great too.)
 

Bale

Minion
If you want to not effect the original, then perhaps you should copy the map and work with the copy?
 
Last edited:

dj_d

Member
The "not affect the original" is just a side effect of how I thought it would work. Is there a way to do what I'm asking with existing functionality? Using "sort" with maps (vs arrays) isn't totally spelled out so perhaps I missed it.
 

jasonharper

Developer
Changing the order in which foreach presents the elements of the map isn't really practical - the iteration order is a pretty fundamental property of the map itself. You need to use a map (perhaps a copy, perhaps a different way of representing the data in the first place) in which the keys are already in the order you want.

The way you have your map set up, you can't meaningfully sort it anyway. It is storing information via the association of the keys (the location) and the values (the stuff & morestuff that goes with that location); sorting changes those associations, that's its whole purpose.

Basically, 'sort' is only useful in cases where your data exists entirely in the values of the map; the keys can have no meaning beyond simply being distinct. Typically this would imply the use of an array, or a map with sequential int keys (which has the advantage over an actual array that you don't have to know the exact size in advance).
 

dj_d

Member
The second two paragraphs make sense, which is why I thought the implementation wouldn't affect the map. But I don't follow the first sentence. Why can't you have foreach iterate through the map in a user-specified order? I realize it might not be a fast operation as you have to search the whole map structure each time to see what comes next, but I don't see why it's not possible. It'd sure be handy. :)

Although your point that I can use a map indexed by ints to workaround the fixed array size limitation is a good and helpful one.
 

Winterbay

Active member
Ok. Sorry for the necro of this rather old thread, but as Spiny stated earler in it the documentation of said feature is only in this (and the same text on the wiki).

I have currently a rather big map defined as
Code:
record sushi
{
	string name;
	sushiparts ingredient1;
	sushiparts ingredient2;
	sushiparts ingredient3;
	sushiparts ingredient4;
	sushiparts ingredient5;
	int total_cost;
	int fishy;
	int adventures;
	float[int] ratio;
};

It consists of all sushis you can make and a few properties they have. I have for the purpose of sorting things created a two copies of this map (called sushis and sushis_sorted) and tried to do this on it:

Code:
sort sushis_sorted by sushis_sorted[index].ratio[1];

In order to sort it according to the first value in ratio. This seems to work just fine however it seems to have the side effect of leading to the original map (sushis) also being sorted which confuses the hell out of me...

Can anyone explain this with the information given? Or do you need the script as well (it is hurrobly cluttered atm)?
 

StDoodle

Minion
Did you make the copy by using a foreach loop on the original to populate the copy, or did you do "sushi [int] sushis_sorted = sushis;"

'Cause if you did the latter, sushis_sorted and sushi would be effectively the same (ie a change in one is a change in both).
 

Winterbay

Active member
I did indeed use the second method thinking that that would create a new map-entity. I shall retry with a foreach loop instead.

Edit: Thank you, that seems to have fixed that.
 
Last edited:

jasonharper

Developer
For maximum efficiency, that should be
sort sushis_sorted by value.ratio[1];
instead of
sort sushis_sorted by sushis_sorted[index].ratio[1];
...which redundantly looks up each item in your map even though the sort mechanism has already done so.
 
Top