Fast Removal of List Members

[Manor Askenazi]

        Fast Removal of List Members
        ----------------------------

I received the following question (from Wengui Su) about some code in
arborgames. I think the answer would be relevant to anybody using Lists.

The Question:

  >  [treeList setIndexFromMemberLoc: offsetof(tree, listMembership)];
  >
  >  Where the message SetIndexFromMemberLoc from. There is no this
  >  method listed both in OrderedSet or its superclass in the Doc.
  >  Also the offsetof(Tree, listmembership) I do not understand what
  >  it means.

I think the best thing to do is to explain the idea first and then
attempt to point out where these things are defined in the collections
library, because I've tried to look up one coherent reference to
this feature and I'm a bit lost myself...

The Basic Idea
--------------

The idea is the following. In a normal linked-list you will have
some kind of list-node containing pointers to the previous node
the next node and the data item stored in that node:


   -------------       -------------       -------------
   |           |       |   next    | --->  |           |
   -------------       -------------       -------------
   |           | <---  |   prev    |       |           |
   -------------       -------------       -------------
   |           |       |  element  |       |           |
   -------------       -------------       -------------
                             |
                             |
                             V

                        -----------
                        | MyAgent |
                        -----------

Now, this works really well for insertion, traversal etc. etc. but if
you want to remove objects from lists (and you want to do it a lot, and
you have bazillions of objects in your list, you run into a problem
because object removal takes linear time in the number of elements
on the list (you basically have to go over every node and see if its
'element' pointer is equal to the agent you intend to remove and if so
the list node is removed).

Here is a really good fix for the problem. If we allocate some memory
within the object being stored for 'prev' and 'next' then you can do
away with the list-node data-structure and you get:


                         My Agent
   -------------       -------------       -------------
   |           |       |           |       |           |
   -------------       -------------       -------------
   |           |       |           |       |           |
   -------------       -------------       -------------
   |           |       |   next    | --->  |           |
   -------------       -------------       -------------
   |           | <---  |   prev    |       |           |
   -------------       -------------       -------------

Now, if you ask the list to remove an object:

                    [list remove: agent]

then the list will simply poke into the agent and 'tie' the previous
agent to the next agent, and there is no need for a linear time search.
In other words you go from O(N) to O(1), which is always a good thing :)

How to do this in Swarm
-----------------------

The way I did it in pre-V1.0 times is apparently being phased-out,
but is still supported:

1. When defining an agent we need to set aside some space for the
   prev-next block, as follows:

   @interface Agent: SwarmObject {
     int    age ;
     double energyLevel ;
     member_t listMembership ; <------------------------------
   }

2. When creating the appropriate KeyedCollection the fact that the
   objects can store the next-prev stuff internally must be stated:

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

   Note: the offsetof(Agent, listMembership) is a macro which returns the
         offset of the listMembership block within the Agent.
         See for example:

            http://www.delorie.com/djgpp/doc/libc-1.12/libc_273.html

   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.


How to do it in V1.0 (and beyond)
---------------------------------

Well, I'm not really sure how that is supposed to happen in V1.0, but
here is what I've found...

In collections.h the method "setIndexFromMemberLoc:" can be found at
the bottom of the file and is described as an 'obselete message' name.
Indeed if you look in KeyedCollection there is a variant on this theme
which may be relevant called "setIndexFromMember:". However, I haven't
found any matching implementation for this message, so I'm not sure it
really exists...

The situation is more interesting in the documentation where methods
called 'setMemberSlot:' and 'getMemberSlot' are defined (and getMember
Slot is even documented):

http://www.santafe.edu/projects/swarm/swarmdocs/src/collections/KeyedCltn.html

But they are not yet implemented and are not in the collections.h of the
current release. If there is a new way to do this internal slot 'trick'
which will work in future releases of collection _and_ in the current
one, Roger would be the one to ask about that...

Hope this helps,

Manor.