14.4. Swarm Maps

Experienced programmers are familiar with the term "key" as it refers to management of collections. People who are new to programming and Swarm often find this idea quite confusing. Hence, we will explain.

Think of a Map as two rows of objects. The bottom row contains the objects you want to store and retrieve. The top row contains the names of the objects. If you put an object into a Map, you tell the Map its name and the Map handles the problem of inserting the object into the bottom row and putting the name in the top row. When an object is removed from a Map, its name is also removed from the top row. If you need to get an object, you tell the Map its name and the Map then goes to the right position in the top row and then it gives back the corresponding object in the bottom row.

The names of the objects are called "keys" in Swarm (and other programming languages). The usage of keys is somewhat confusing and difficult for newcomers because the keys should be Swarm objects.


Example 14-1. Maps and keys

Here is a simple example. Suppose we are creating a series of objects in a for loop. In each step, we tell the class Person, which is subclassed from SwarmObject to create an instance aFriend and we add that Person to a listOfPeople. Then we tell the class Preferences to create an instance and we insert the instance into a Map, using the Person object as the key. Note that the Map and List are declared before the loop.


id <List> listOfPeople;
id <Map> mapOfPreferences;
listOfPeople=[List create: [self getZone]];
mapOfPreferences=[Map create: [self getZone]];

for(i=0; i < 50; i++)
{
id aFriend, aPreference;
aFriend = [Person createBegin: [self getZone]];
aFriend = [aFriend createEnd];

[listOfPeople addLast: aFriend];

aPreference = [Preferences createBegin: [self getZone]];
aPreference = [aPreference createEnd];

[mapOfPreferences at: aFriend insert: aPreference];
}

To retrieve a preference object, it is first necessary to figure out which person you want and then tell the Map to return that person's preference. For example, suppose you decide to grab the 6th person and find out what their preferences are. Then try this:

id aParticularPerson, thePreference;
aParticularFriend=[listOfPeople atOffset: 6];
thePreference=[mapOfPreferences at: aParticularFriend];
// here you can do anything you want to with thePreference you get back.

Similarly, you could cycle through the listOfPeople by creating a Swarm index for the listOfPeople and then use the returned value from [index next] as the key:

id index, aPerson;
index= [listOfPeople begin: [self getZone]];
while( (aPerson=[index next])!=nil )
{
  id thePreference;
thePreference = [mapOfPreferences at: aPerson];
// here you insert some code that does something with the retrieved preference!
}

This example works because the Map object automatically compares the objects acting as keys to see if they are identical. This is the default compare: method of the class SwarmObject. If one wishes to compare the objects by another criterion, then a comparison function can be declared when the Map is created. Lacking a user-defined comparison function, the Map will always use the compare: that is defined in the key object. Lacking such a function, the program should not run.

When an object that is being used as a key has a compare: function, then the Map will use that function to decide if the two objects are equal. If a comparison function is declared when the Map is created, then that comparison function will be used instead. Swarm includes some built-in comparison functions, but, as we will see, the usage of customized functions is quite easy and convenient. If no comparison function is declared, then the fall-back approach checks for a compare: method in the key object itself. Since all objects that are based on Swarm inherit from the defined object class, all such objects have (at least) access to the bare minimum compare: that checks to see if two objects are identical. Classes from which key objects are created can, of course, create more informative comparison methods.

Lets begin with the problem of using integers as keys. There are two possible approaches, typecasting and the creation of "integer wrappers." The typecasting approach is used in many Swarm applications. The essence of this approach is to use type casting to trick the Swarm library to make it treat an integer as if it were an object. Without going too deeply into the computer science of the issue, it may not be possible to explain this, but we will take a stab at it. On many computer systems, a pointer uses the same amount of space as an integer. Hence, it is possible to cast an integer as a pointer to "fool" the compiler, and then to retrieve the value of the integer from the place in memory where the pointer was supposed to be. (Confusing? Many users say, yes!) Instead of inserting objects into a Map with objects as keys, using this casting trick, one can insert objects at integer values that are cast as objects of type id. For example:

[mapOfPreferences at: (id) 13 insert: aFriend]

In order for this to work, the mapOfPreferences has to be created so that it knows integers are going to be passed through in this way. At create time, the Map must be told to use the built-in comparison function that will uncast the pointers and compare them.

mapOfPreferences  = [Map createBegin: aZone];
[mapOfPreferences  setCompareFunction: compareIntegers];
mapOfPreferences = [mapOfPreferences createEnd];

The GridTurtle code example grid3b.m uses this appoach.

This "casting" approach to creating a keys has some serious shortcomings. Most importantly, it is severely nonportable. Code written in this way on a Linux system might not work on a DEC Unix system. Why? On DEC Unix, an integer and a pointer do not have the same size.

What is the alternative if one wants to enter objects into a Map using integers as keys? The answer is: create an "integer wrapper" class. This integer wrapper can store and retrieve the values of integers, and these objects can be used as keys in Swarm Maps.

Here is the integer wrapper class [1], which is called Integer:

//Integer.h
#import <defobj/Create.h>

@interface Integer: CreateDrop
{
 int value;
 member_t link;
}
- setValue: (int)value;
- (int)getValue;
@end

//Integer.m
@implementation Integer
- setValue: (int)theValue
{
 value = theValue;
 return self;
}

- (int)getValue
{
 return value;
}

@end

In order to use the Integer class keys, the Map has to be told how to compare them, so it knows when it has found a key that matches what it is searching for. In the example, the comparison function is called compareIntegerObjects ( ) and it takes two objects, and it then retrieves the value from each object, and returns the difference of the two. When 0 is returned, it is treated as a "match". The following code snip creates 50 Preference objects and it creates an Integer object for each one. Each time the user wants to insert an object into a Map, an Integer wrapper is created.

#include Integer.h
#include Preference.h

// Here is a "comparison function"
int
compareIntegerObjects (id obj1, id obj2)
{
return ((Integer *) obj1)->value - ((Integer *) obj2)->value;
}

id <List> listOfPeople;
id <Array> arrayOfIntegers;
id <Map> mapOfPreferences;

mapOfPreferences = [[[Map createBegin: [self getZone]]
    setCompareFunction: compareIntegerObjects]
   createEnd];

for (i = 0; i < 50; i++)
{
  id aPreference;

  aPreference = [Preference createBegin: [self getZone]];
  aPreference = [aPreference createEnd];

  anInteger = [[Integer createBegin: [self getZone] setValue: i] createEnd];

  [mapOfPreferences at: anInteger insert: aPreference];
}

After the mapOfPreferences is filled with objects, then they can be retrieved by their key values. One can create a single Integer object, and then insert a value into it, and then use it as the key. The following will work to retrieve the Preference object corresponding to the Integer key with value 23. Supposing the Preference class has a method outputVitalInfo, this will retrieve those objects and tell them to execute that method.

id desiredPreferenceObject;

Integer * key = INTEGER(0);
key->value =23;   //same as [key setValue: 23];
desiredPreferenceObject= [mapOfPreferences at: key];
printf("The preference Object gives this output \n");
[desiredPreferenceObject outputVitalInfo];

This is written out this way to make the code as clear as possible. The example program cited above includes a number of macro definitions that can be used to make working with the Integer class more elegant (and less tedious).

The same kind of approaches can be used if one wants to use strings as keys in a Map. The easiest way to use strings as the keys is to use the Swarm String protocol to create objects that act as "wrappers" for the string names. In the Swarm Documentation, one can find the GridTurtle test programs for the Collections library. The file grid3.m contains an example that does exactly this. The code in grid3.m creates a string, equal to the index variable i, and then sets that string into a String object, which is in turn used as the key. Of course, there is no reason that the chosen character string had to be a simple number. If you want to, you can create strings for all your friends and wrap them inside String objects.

Unless you define a comparison function, the String objects are compared according to the compare: method that is defined for Swarm Strings. This function is defined in the Swarm library in the file StringObject.m. The comparison uses the C function strcmp to find out if the object's own string is the same as the string retrieved from the other object (which is called aString):

- (int)compare: aString
{
  return strcmp (string, ((String_c *) aString)->string);
}

As in the case of integers, the built-in compare: method can be over-ridden by a customized comparison function declared by the user.

Notes

[1]

There is an example of a program by Marcus Daniels that uses integer wrappers at MapIntegerIndex.txt.