QSort: What I've learned, what I would like to know

[Paul Johnson]

Whenever I learn how to implement some Swarm thing, I write it down
and sometimes doublecheck to the list to fill in the gaps. Then it may
become a FAQ entry or something else.  This is one of those times.

Here Goes:

The QSort method in Swarm implements a common, efficient method for
sorting lists of objects.  I first read about QSort in a Pascal text
called OH! Pascal and I was interested in using it to have agents
rank objects in terms of their desirability.

I found the manual pages on this somewhat cryptic because they mention
compare methods and functions but dont say much about how those are constructed
and how they work.  (I mean, they don't say much I can understand.) Last Friday
I bothered an SFI team member whose initials
are MD several times and I found one way to make QSort work. 

In the proposal.m file, I have a double  called "proposalUtility". Scores that
are lower are better.  There is a method "getTestNumber" which gives back
that double.  (I know, for convenience it ought to be "getProposalUtility"
but for some uknown reason, probably a typo, when I named the method that
it always returned 0. Hmmm)  Inside
the proposal.m file, there is also a "compare" method, exactly like so:

-(int) compare:  b
{
   double valb = [b getTestNumber];

   return proposalUtility  < valb ? -1 : proposalUtility != valb;
}

It took me a while to understand this very elegant comparison that MD 
sent me.  This comparison returns a -1, 0, or 1. It says "if proposalUtility <
valb, then give back -1.  Else give back this boolean statement, which
gets evaluated as 1 if proposalUtility and valb are not equal and 0 if they are.
Very slick, I thought.  If I had done this myself, I'd have had to write
if-else-else or such. (Maybe this one of those clever C tricks you learn if
you actually take a class in programming?) 

In another file "citizen.m" a citizen creates a list of objects of type
proposal, that list is  called invitationsList.  That file includes
simtools.h at the top, so you get some free objects, like NSelect and QSort.  
These are objects created inside the swarm kernel and they can be told to
carry out jobs. Very convenient! The invitationsList is QSorted by this command:

         [QSort sortObjectsIn: invitationsList];

Because no additional parameters are included, the QSort method by default
uses the compare method that is given for the object type in the
invitationsList.  It works fine.


Now here is what I wish I understood.  If an object has no compare method, one
can make a function that compares the doubles.  It is in the manual, but I
just don't get it! MD explained that this
is a function, not a method, it is global and is inserted in an m file,
typically  before the @implementation.  Here is the example:

int
compare (const void *obj1, const void *obj2)
{
   double val1 = *(double *)obj1;
   double val2 = *(double *)obj2;

   return val1 < val2 ? -1 : val1 != val2;
}

And to QSort with this, you use this command:

[QSort sortObjectsIn: invitationsList using: compare];

I don't understand how to adapt this compare example to fit my problem. Unlike
the other one, where I understood how proposalUtility was getting into the
compare method, I don't understand how proposalUtility is supposed to get into
this compare function. 

If you know, please tell me and I can close on this topic

Paul E. Johnson                      address@hidden
Dept. of Political Science           http://lark.cc.ukans.edu/~pauljohn
University of Kansas                 Office: (913) 864-9086
Lawrence, Kansas 66045               FAX: (913) 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.
                  ==================================