Data Structures

From Kolmafia
Revision as of 14:46, 4 October 2009 by imported>Dj d
Jump to navigation Jump to search

maps

Most of this information was copied directly from ASH Maps Tutorial, by Veracity (http://kolmafia.sourceforge.net/advanced.html#maps)

A map is indexed by one data type (the key) and associates that key with another (or the same) data type (the value). The key can be any ASH simple data type: boolean, int, float, string, item, zodiac, location, class, stat, skill, effect, familiar, slot, or monster. The value can be any of those or can be an aggregate: another map. This effectively allows multi-dimensional maps and. In fact, that's how the syntax we provide for multi-dimensional aggregates actually operates: maps of maps of maps ...

You can declare a map any time you can declare a variable: as a top level (global) variable, as a function parameter, or as a local variable in any scope.

You can fetch data from a map any time you can provide a data value: in an expression, as a function parameter, on the right side of an assignment statement, from a "return" statement, as so on. You can pass around entire maps, individual elements, or intermediate maps: "slices".

assignments

If you use a map on the left side of an assignment, you set the whole map at once to the new value. If you specify a map and a complete set of indices (of the correct types) on the left side of an assignment statement, you set a single element. If you specify a map and a prefix of indices (of the correct type), you directly set one of the intermediate maps, a "slice".

declarations

The syntax for declaring the data type of a map:

    [ <key type>, ... ]  

references

The syntax for referencing an element (or slice) of a map:

   <variablename>[ <key expression>, ... ]  

All the key expressions will be evaluated at run time. If you specify all the keys the map expects, you fetch data of the type specified by the map. If you specify fewer keys than the map expects, you get an intermediate map, a "slice".

As an example:

   boolean [string, string] props;  

might be used to hold "properties" associated with names.

   props[ "dog", "mammal" ] = true; 
   props[ "dog", "pet" ] = true; 
   props[ "dog", "fun" ] = false;
   props[ "turtle", "mammal" ] = false;
   props[ "turtle", "pet" ] = true;
   props[ "turtle", "fun" ] = false;
   props[ "aardvark", "mammal" ] = true;
   props[ "aardvark", "pet" ] = false;
   props[ "aardvark", "fun" ] = true;  

references:

   props[ "dog", "mammal"] => true 
   boolean [string] animal = props[ "turtle" ]; 
   animal[ "fun" ] => false  

contains

You can test the presence of a key in a map using the "contains" operator:

   <aggregate reference expression> contains <key expression>  

Where <aggregate reference expression> must evaluate at run time to a map or slice, and must evaluate at run time to a key of the appropriate type. (Note that that is enforced at parse time; ASH can tell the datatype any expression will produce).

   props contains "dog" => true 
   props contains "elephant" => false 
   props[ "aardvark" ] contains "fun" => true 
   animal contains "pet" => true 
   animal contains "favorite food" => false  

remove

You can remove a key-value association from a map using the "remove" unary operator:

   remove <aggregate reference>  

For clarification, an aggregate reference is "<map name>[ <index 1> ... <index n> ]" where <map name>[ <index 1> ... <index n-1> ] specifies the "slice" and <index n> specifies the "key". Which is just what you expect, if you fully specify the indices; for a single dimensional map, "map[10]" -> "map" is the slice and 10 is the key. The "remove" operator removes the "key" from the "slice". For example:

 string [int] map1;
 map1[5] = "foo";
 print( count( map1 ) + " " + map1 contains 5 + " " + map1[5] );
 print( "remove: " + remove map1[5] );
 print( count( map1 ) + " " + map1 contains 5 + " "  + map1[5] );
 print( "remove: " + remove map1[5] );
 int [string, string] map2;
 map2["me","you"] = 17;
 print( count( map2["me"] ) + " " + map2["me"] contains "you" + " " + map2["me","you"] );
 print( "remove: " + remove map2["me", "you"] );
 print( count( map2["me"] ) + " " + map2["me"] contains "you" + " " + map2["me","you"] );
 print( "remove: " + remove map2["me", "you"] );
 print( count( map2 ) + " " + map2["me"] );
 print( "remove: " + remove map2["me"] );
 print( count( map2 ) + " " + map2["me"] );

yields:

 1 true foo
 remove: foo
 0 false
 remove:
 1 true 17
 remove: 17
 0 false 0
 remove: 0
 1 aggregate int [string]
 remove: aggregate int [string]
 0 aggregate int [string]

deletion

clear (theMap) will remove all entries


sort

From http://kolmafia.us/showthread.php?t=1738

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).