Sunday, June 15, 2008

Common Idioms 2

Associative arrays are one of the driving force behind the adoption of so-called scripting languages such as JavaScript or Ruby. Strangely enough, they're absent from the mainstream generalist languages of the C++/C#/Java family.

Associative arrays are like standard arrays but can be indexed with any given collection of values (whereas Java arrays can only be indexed with 0-based integers). Alternatively, associative arrays can be thought of as maps with built-in language support and a fixed an immutable set of keys (refering to a non-existent key raises an ArrayIndexOutOfBoundsException). Here is the OptimJ version of the canonical example from Wikipedia :

  String[String] phoneBook = {
    "Sally Smart" -> "555-9999",
    "John Doe" -> "555-1212",
    "J. Random Hacker" -> "553-1337"

  // iterate over the values
  for(String number : phoneBook) {

  // iterate over the keys
  for(String name : phoneBook.keys) {
    System.out.println(name + " -> " + phoneBook[name]);

Notice the type String[String] that denotes an array of strings indexed by strings.

To see how associative arrays differ from Java arrays, consider the two definitions :
  String[] a1 = { "a", "b", "c" };
  String[int] a2 = { 12 -> "a", 3 -> "b", 7 -> "c" };

Here a1 is indexed by 0, 1, 2 and a2 is indexed by 3, 7, 12. Note how their types are different.

Java and associative array dimensions can be mixed freely:
  int[String][][double] a;

a is a 3-dimensional array. The first dimension is associative, indexed by doubles. The second dimension is a Java array dimension, indexed by 0-based integers. The third dimension is associative, indexed by strings.

As usual in Java, an array index expression is written with indices in the opposite order of the types:

Associative arrays are common in algebraic modeling languages such as AMPL, GAMS, OPL, etc., where they allow for a concise and mathematical-like expression of optimization problems.