Re: Need help/examples with enumerated lists (ooops...)

[Ken Cline]

On Thu, 16 Jul 1998, Benedikt Stefansson wrote:

> for(i=0;i<[memberList getCount];i++) {
>     member=[memberList atOffset: i];
>     if([contactList contains: member]==1)
>         [contactList remove: member];
> }
> 
> I wrote it the other way first, because the contains: and
> remove: methods in collections duplicate the same effort
> (to find the member pointer). There might be a faster way
> to do this, but certainly it would be messier code.

I always had a question about using `atOffset:' with any
collection other than arrays... From what I can tell, the
only two implementations of `atOffset:' are found in Array.m
and Collection.m.  The implementation in Collection.m uses
`next' to increment an index to the correct offset so that
means the for loop above would run in O( (n+1)n/2 ), right?
(where `n' is the size of `memberList' and I'm ignoring the
execution time of `remove').

I think the following while loop version should run in O(n):
(again, I'm ignoring the execution time of `remove')

   index = [ memberList begin: [self getZone] ];
   while ( [index next] != NULL )
      [ contactList remove: [index get] ];

   [ index drop ];

Ken.

_________________________________________________________
Ken Cline                             address@hidden
SAIC                                 VOICE (410) 571-0413
Annapolis, MD                          FAX (301) 261-8427



                  ==================================
   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.
                  ==================================