setIndexFromMemberLoc: I finally go it!

[Paul E. Johnson]

When Doug explained the source of the problem in his code, I was
reminded that I had meant to find out exactly what
setIndexFromMemberLoc: does and I went in to the swarm archive and found
notes, one from me, asking what the hell is setIndexFromMemberLoc:

The closest I got to a clear explanation is by Manor Askenazi
http://www.santafe.edu/projects/swarm/archive/list-archive.9703/0023.html.

In there, I found this almost prophetic warning about Doug's problem:

"Also Note: if your object wants to be in two lists at the same time
then obviously you will need two listMembership blocks...
However, if you know for sure that you may reside on more
than one list but never concurrently then you can re-use
the same prev-next block."

Eerie, isn't it?  

But now I get what setIndexFromMember: is all about.  Let me see if I
can get this point across directly.  The method seems to live under a
cloud under which it is "discouraged" but not disavowed.  Since it does
exist, it seems important to document it and explain how things can go
wrong (to avoid problems like the one Doug discovered).

So here is my explanation. What do you think?

Consider the ordinary Swarm list.  An object has no self awareness of
its position. It has pointers to the next and previous list items, but
it does not know it is item number 10, for example.

This fact makes searching for specific items in lists take a long time,
since you start at the beginning and look at objects one at a time. 
Manor says this takes O(N) time.

Now suppose you adopt a new approach.  Instead of leaving objects in the
dark about their position, why not let them keep internal notes on the
list and their position in it.  Create a variable of type member_t (I've
not yet found out what that type is) inside each object you want to put
in a list.  Suppose that object is of class Agent.  And the instance
variable in Agent is 
   member_t listMembership;
Then  you create the list like this:

agentList = [OrderedSet createBegin: [self getZone]] ;
[agentList setIndexFromMemberLoc: offsetof( Agent, listMembership )] ;
agentList = [agentList createEnd] ;

What is vital here is that the C library macro offsetof is used to tell
the list object that, inside each Agent at a certain position, there is
a variable that is waiting to be a recordkeeper on the Agent's position
in the list.  That variable is called listMembership.

So when  you tell a list to drop a particular agent, the list is
supposed to think "now, where is that guy in here?" and it should be
able to access the position by doing something like
agent->listMembership to directly find out where the agent is.

Roger B's followup to Manor's note is a bit discouraging to me, as he
states that setIndexFromMemberLoc: is not really intended for ordinary
users.  One might guess as much, since the setIndexFromMemberLoc: method
is listed but it is not explained at all in Swarm Docs.  I think the
name of the method is confusing and misleading, making people think it
will concern a Swarm Index variable.  Something like
"storeMemberPositionInIVAR:" would be closer to the mark.

There is no documentation to indicate that, when one object is removed
from the list, then the member location information of all the other
objects is updated to reflect their status.   I wish I knew if the
setIndexFromMemberLoc: method would cause not only "delete:" but also
"contains:" methods to execute much faster.

If I understand it right, documentation about the setIndexFromMemberLoc:
method should be accompanied by some sharp, clear warnings..

1. all agents inserted into a list must be from the same class.  If
there were different classes being inserted, then the offsetof for one
class would not match the other and then the list would wreck some ivars
when it tries to store information.

2. The user must create one member_t ivar for each list.  This is
necessary to keep separate records on the position of the object in each
list.

3. This functionality, as Roger pointed out, is really intended for
lists in which no object can be inserted twice. He calls this a Set. 
But there is no implementation, apparently, of this restriction.

In other words, setIndexFromMemberLoc: might be a good way to speed up
selective deletion of objects, but there are enough
undocumented/troublesome features about it that I now see why the Swarm
team has not gone out of their way to explain to us all how to use it. 

-- 
Paul E. Johnson                         email: address@hidden
Dept. of Political Science              http://lark.cc.ukans.edu/~pauljohn
University of Kansas                    Office: (785) 864-9086
Lawrence, Kansas 66045                  FAX: (785) 864-5700

                  ==================================
   Swarm-Support is for discussion of the technical details of the day
   to day usage of Swarm.  For list administration needs (esp.
   [un]subscribing), please send a message to <address@hidden>
   with "help" in the body of the message.