how does sort work?

Q

QVamp

Member
I was trying to create a simple script to find out how much of each item I owned, and I'm not sure I understand 'sort' (I read through the thread linked in the wiki and it didn't help me). This example gives odd results... and quantities of things I know I don't own. I think this is sorting the keys and not values, or vice versa... or maybe both. Could you guys tell me what's wrong with my script? Once I understand, I'll add this as an example to the wiki.

Code: 
int[item] whatGot;     // what do I own

foreach it in get_inventory() {
  int num = item_amount(it);
	whatGot[it] = num;
}

sort whatGot by value;

foreach it in whatGot {
   print(whatGot[it] + ' of ' + it);
}

print_html('<b>Done!</b>');
 
Oh dear. First of all, maps are always in order. If the index is a string, then they are in alphabetical order. If the index is an integer, they are in numerical order. If the index is an item, the order makes no useful sense whatsoever.

When you sort a map, you change the values that correspond to the index. In this case, you were sorting the quantities to associate with different items. You should never try to sort a map that isn't indexed by ordered integers because it just isn't very useful unless you find a really unusual case. What you really wanted to do is this:

Code: 
item [int] whatGot;

foreach it in get_inventory()
   whatGot[count(whatGot)] = it;

sort whatGot by item_amount(value);

foreach x, it in whatGot
   print(item_amount(it) + ' of ' + it);

print_html('<b>Done!</b>');

Note that I'm making use of an optional feature of foreach there. The second variable in the foreach is the value of whatGot[x]. I like it because it improves readability remarkably and lets me type less.
 
Last edited:
I'd also like to point out that get_inventory() returns an int [item] map where int is the quantity of item in your inventory. This is what your original whatGot map is, so you're doing more work than you need to in that sense.

In the case of your original example, one might think that item_amount(index) would work, but unfortunately it won't. This is because the aggregate key is an item which can't be meaningfully sorted. In Bale's example, the aggregate key is an int, which is where the major difference lies.

Edit: My only potential criticism of Bale's code is the way he is populating the whatGot map. Whilst it is incredibly easy to read, it does lead to a bunch of unnecessary calls to count(). An alternative solution would be to populate the map like so:

Code: 
int i;
foreach it in get_inventory() {
   i+=1;
   whatGot[i] = it;
}
 
Last edited:
Bale said:
Code: 
   whatGot[count(whatGot)] = it;
Click to expand...

I also don't like this because it *looks* (or can look on a glance) like you are counting amount of it and using *that* as the index (<- not what happens, but I had to think for a second to realize that).
 
I've ran into a couple situations where I couldn't figure out how to use sort to do what I wanted. Like this example: I've parsed all the boozes I've drank from my last X days of log files, and now booze_list contains the boozes I've drank and the number of days since the last time I drank it. Sometimes there's just not a readily available function like item_amount() that you can apply to the sorted map, but an extra for loop did the trick.

Code: 
int [item] booze_list;

for i from 0 to days - 1 {
    foreach booze, d in booze_list if (i == d) {
        print_html("It's been " + i + " day" + (i == 1 ? "" : "s") + " since your last " + booze);
    }
}

It could be nice if there was a way to sort maps that didn't dissociate the keys from the values. If I didn't know what the highest value of days was going to be in that booze example, it might be difficult to know when to stop the outer for loop.
 
Last edited:
You should probably use an additional key, or a record, in such a case. It helps to think of maps as a list of locations of data objects, with specific data at each location. Yes, sometimes you can save time / energy / code by using the location itself as data, but if you need to manipulate your map you need another key.
 
Last edited:
One of these things:

Code: 
Y[X] orig; // mapYouWantSorted;
X[X] m; // mapYouWillActuallySort;

foreach i in orig { m[i] = i; };
sort m by someFunction(orig[value]);
// the values of m are now properly sorted keys into orig
foreach i,v in m { print v + " : " + orig[v]; } // the keys into m are still in the same order, only values were sorted

This can work better if you are in control of your data structures (because you can use the record from the beginning and thus avoid the copying):
Code: 
Y[X] orig;
record wrapper { X key; Y value; }
wrapper [X] m;

foreach i in orig { wrapper w; w.key = i; w.value = orig[i]; m[i] = wrapper; };
sort m by someFunction(value.value);
foreach i,v in m { print v.key + " : " + v.value; }
 
StDoodle said:
You should probably use an additional key, or a record, in such a case.
Click to expand...

Interesting. This works more or less the way I've always wanted it to:
Code: 
int [item, int] test;
test [$item[banana], 1] = 5;
test [$item[astral hot dog], 2] = 4;
test [$item[elephant stinger], 3] = 3;
test [$item[collapsible baton], 4] = 2;
test [$item[doc's miracle cure], 5] = 1;

sort test by value;

foreach x, y, z in test print_html(x + " " + y + " " + z);


And just for contrast, this works in a way that I didn't expect at all:
Code: 
int [item] test;
test [$item[banana]] = 5;
test [$item[astral hot dog]] = 4;
test [$item[elephant stinger]] = 3;
test [$item[collapsible baton]] = 2;
test [$item[doc's miracle cure]] = 1;

sort test by value;

foreach x, y in test print_html(x + " " + y);


The difference is pretty surprising, is that intentional or accidental?
 
In the thread mentioned in sort's mafiawiki page, here is JasonHarper's post that made me understand how I can use sort:
jasonharper said:
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).
Click to expand...
Which is just what StDoodle and xkiv are trying to say too.
 
Okay, so it looks like sorting a map with multiple keys is an exception, and using int indexed maps of records is an easy (and legal) way to keep multiple values coordinated. /me makes notes
 
If your map has multiple keys, like your [int][item][int] test, [int] is the key, and [int][item] is the data. The data will be sorted according to [item] (the value), and the last [int] just tags along its corresponding [item].
 
To combine those two concepts into one question...

int [string] [item] name;
sort name by value;

That's creating a string indexed map full of item indexed maps of ints, then sorting them by the string? Maybe? Am I close?
 
That wouldn't actually work at all. The values would be int[item] maps, which aren't comparable. You could sort it by an expression like value[$item[seal tooth]], but it's hard to imagine that producing meaningful results.
 
It's really funny that you say that it shouldn't produce meaningful results, because the first time I sorted a map with two keys a little bit ago was the first time I saw results from sort that kept all the keys and values coordinated with each other like I'd always wanted. If it's not supposed to work like that though, I don't mind using a record properly instead of misusing maps.
 
ASH map assignment can become pretty confusing.

int [item] [float] [string] myMap; equivalent to int [item, float, string] myMap;

Will return a map with an [item] key and int [float, string] value.

The int [float, string] value is a [float] indexed map with int [string] value.

The int [string] value is a string indexed map with int value.

Notice that this final int value is the only non-aggregate data type in the entire map.

It may seem a little counter-intuitive to people who look at int [item, float, string] and think it's an int indexed map containing item, float and string values.
 
Last edited:
Oh god no. You're giving me flashbacks. All those little irritating single parenthesis... they're going to get me!
 
jasonharper said:
That wouldn't actually work at all. The values would be int[item] maps, which aren't comparable. You could sort it by an expression like value[$item[seal tooth]], but it's hard to imagine that producing meaningful results.
Click to expand...
If I am reading the code correctly, compare(map, map) will always return -1 (and not throw any error), which just means sort() will sort them in an "undefined" order (the order will be defined by the underlying sorting algorithm).
I suspect that at least oen implementation of sort() [I don't know outhand how small the list/array/map must be to switch to the "simple case" algorithm, but that might be irrelevant] compares the element in such order that always returning -1 from compareTo will result in sort() thinking that the list is already in sorted order.
(compareTo(element1, element2) == -1 -> OK, element1 and element2 are in correct order,
compareTo(element2, element3) == -1 -> OK, element2 and element3 are in correct order,
...)


Bale said:
Oh god no. You're giving me flashbacks. All those little irritating single parenthesis... they're going to get me!
Click to expand...

I think they are trying to car you.
 
You must log in or register to reply here.
Back
Top