Re: Collections objects

[Roger M. Burkhart]

> I'm working on rewriting some swarm code, which was done really
> kludgily because I didn't know about Collections objects.  It uses
> lots of pointers and things, and, not surprisingly, breaks when I try
> to compile it.  So I'm working on a new version.
> 
> My question is this:  can someone explain (or point to some good
> documentation) to me about List and Array objects?  I've read the
> interface references, but there are a couple things I'm still unclear
> on.

For some simple example test programs, see "GridTurtle test programs" in
the docs under "Collections Library" --> "Documentation and Implementation
Status."  They contain examples of exercising most List and Array
capability, though not in a way that's particularly tutorial oriented.
There's a lot of work in progress to finish all the planned capability in
the collections library (other things intruded over most of the summer)
and more introductory tutorial docs have been held up by that.

> Do Collections of objects actually contain the objects themselves, or
> just references to (pointers to?) the objects?  Collections has an
> Index object, which everything else inherits, that will let you
> iterate through the objects.  How do the Index objects for the various
> subclasses work?  I got lost trying to work it out...

Just references to objects.  The "id" type used to hold all Objective C
objects is really a pointer to the object, and that's the type stored as
members in a collections.

For Index, see examples.  An index is basically the same as an "iterator"
in other collections libraries such as the C++ Standard Template Library.
The canonical loop that iterates through collection members using an
index is:

  index = [aCollection begin: scratchZone];
  while ( (member = [index next]) ) {
    [member doSomething];
  }
  [index drop];

> Basically, what I need to do is this:  I have a bunch of Chimp
> objects.  I want to keep track of them in some ordered fashion for
> reference.  I also want to have access to them via two rankings: one
> is an ordered ranking based on a changing variable, the other is a
> randomized ranking based on the ordered ranking.
> 
> It seems that an Array would be appropriate for actually holding the
> objects and keeping track of them, and that then I'd like two Lists
> for the ranked ordering and the randomized ordering.  Is this right?

This sounds like a reasonable approach.  A list makes it very easy to
maintain a sequence, by removing and inserting members at any position,
but is slow to access by relative position.  An array makes it fast to
access by relative position, but hard to change the sequence.

> The other thing is that I'd like to use quicksort() to make the
> ranking each time; but that requires an array of pointers.  Any tips
> and suggestions on integrating that into what I'm doing?  I don't
> think it's real hard, but if there are any real pitfalls to going back
> and forth between pointers and reference objects, I'd appreciate it...

Array has the ability to access or supply a low-level C array that
contains a contiguous sequence of the member id's in the collection.
You could use that to sort the members out from underneath the array
object.  Another approach would be to sort the members using a sorted
Map, but an implementation of Map that would make this reasonably fast
(basic order n log n, like most sort algorithms) isn't there yet.
(Current implementation is a slow one based on insert into a linear
list, but it happens to work well for schedules that are changing
underneath as they are traversed.)

Roger Burkhart